Szyfrowanie z pseudolosowym odstępem


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Liniowe generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
  Projekt generatora LCG
Szyfrowanie
Deszyfrowanie
 

Problem

Opracować algorytm szyfrujący i deszyfrujący z pseudolosowym odstępem

 

 

Szyfr Cezara posiada kilka wad, które uniemożliwiają praktyczne zastosowanie. Po pierwsze wystarczy odkryć wartość przesunięcia kodów (oryginalnie wynosi ono 3, lecz można je zmieniać w zakresie od 1 do 25), aby rozszyfrować całą wiadomość. W tym celu należy przeprowadzić 25 prób, co dla współczesnych komputerów nie stanowi żadnego problemu.

 

Przesunięcie kodów Szyfr
0 ALA MA KOTA
 + 1 BMB NB LPUB
 + 2 CNC OC MQVC
 + 3 DOD PD NRWD
 + 4 EPE QE OSXE
 + 5 FQF RF PTYF

 

Po drugie, z uwagi na stałe przesunięcie kodów, te same znaki są zawsze szyfrowane tak samo. Jeśli na przykład zaszyfrujemy AAAAAAAAAA, to otrzymamy ciąg DDDDDDDDDD.

Aby znacząco utrudnić rozszyfrowanie wiadomości zaprojektujemy szyfr, w którym przesunięcie kodów będzie się zmieniało w zakresie od 0 do 25 w trakcie szyfrowania znaków. Do tego celu potrzebna nam jest możliwość generacji tych samych ciągów liczbowych przy szyfrowaniu oraz rozszyfrowywaniu. Wykorzystamy generator pseudolosowy LCG, który startując od określonego ziarna tworzy zawsze te same ciągi liczb pseudolosowych. Kluczem szyfrującym będą parametry generatora oraz wartość ziarna pseudolosowego. Parametry generatora: moduł m, mnożnik a oraz przyrost c zostaną na stałe zdefiniowane w programie (możesz je zmienić, wtedy zmianie ulegnie sposób szyfrowania). Użytkownik będzie jedynie podawał wartość ziarna pseudolosowego Xo. Sposób projektowania generatora LCG opisaliśmy w rozdziale o liczbach pseudolosowych.

 

Projekt generatora LCG

Im większy zakres generowanych liczb pseudolosowych, tym dłuższy okres powtarzania tworzonego ciągu. W efekcie trudniejsze jest złamanie szyfru. Kryptologia potrafi bez większych problemów łamać szyfry oparte na prostych generatorach pseudolosowych z uwagi na ich właściwości, dlatego nie są one stosowane w praktycznych systemach szyfrowania – użyty generator musi być kryptologicznie bezpieczny. My się tym nie będziemy przejmowali, ponieważ nasz projekt jest czysto dydaktyczny.

 

Wybieramy zakres od 0 do Xmax = 3956279999.

Moduł m jest równy Xmax + 1 = 3956280000

Czynniki pierwsze modułu m = 3956280000 = 2 × 2 × 2 × 2 × 2 × 2 × 3 × 5 × 5 × 5 × 5 × 32969

Przyrost c = 7 × 11 × 17 = 1309

Mnożnik a - 1 = 2 × 2 × 3 × 5 × 32969 = 1978140, stąd a = 1978141.

Podsumowując otrzymujemy następujący generator LCG:

LCG(3956280000,1978141,1309,Xo)

Ziarno Xo jest w zakresie od 0 do Xmax, czyli od 0 do 3956279999. Liczba ta będzie naszym kluczem szyfrującym.

 

Szyfrowanie

Zasada szyfrowania jest następująca:

 

Odczytujemy klucz i wprowadzamy go do ziarna pseudolosowego naszego generatora LCG. Na podstawie tego klucza generator LCG będzie tworzył ściśle określony ciąg liczb pseudolosowych. Odczytujemy następnie łańcuch s, który ma zostać zaszyfrowany. Zamieniamy wszystkie litery z małych na duże (nasz algorytm szyfruje tylko duże znaki). Przetwarzamy kolejne znaki tego łańcucha. Dla każdego znaku generujemy liczbę pseudolosową X. Teraz sprawdzamy, czy przetwarzany znak łańcucha s jest dużą literą od A do Z. Jeśli tak, to obliczamy jego kod ch i przekształcamy go zgodnie ze wzorem:

 

ch = 65 + (ch - 65 + X mod 26) mod 26

 

Wynik jest kodem zaszyfrowanego znaku – umieszczamy go w łańcuchu s na miejscu przetwarzanego znaku i kontynuujemy te same operacje aż do przetworzenia wszystkich znaków w s. Na końcu łańcuch s zwracamy jako wynik szyfrowania.

 

Algorytm szyfrowania z pseudolosowym odstępem

Wejście
X  –  klucz, X N
m,a, c  – parametry generatora LCG, m,a,c N
s  – łańcuch tekstowy
Wyjście:

Zaszyfrowany łańcuch s

Elementy pomocnicze:
i  –  indeks, i N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x na odpowiadający mu znak ASCII
Lista kroków:
K01: Dla i = 0,1,...,|s| - 1, wykonuj K02...K04 ; przetwarzamy kolejne znaki łańcucha s
K02:     X ← (a × X + c) mod m ; obliczamy nową liczbę pseudolosową
K03:     Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01 ; pomijamy znaki nie będące literami od A do Z
K04:     s[i] = znak(65 + (kod(s[i]) - 65 + X mod 26) mod 26) ; szyfrujemy
K05: Pisz s ; wyprowadzamy szyfr
K06: Zakończ ; gotowe

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje kolejno klucz X oraz łańcuch s, który szyfruje kodem o pseudolosowym odstępie i wypisuje wynik. Parametry generatora LCG są zdefiniowane wewnątrz programu. Zakres kluczy jest od 0 do 3956279999.

 

Lazarus
// Szyfrowanie z pseudolosowym odstępem
// Data: 20.08.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s : string;
  i : integer;
  X,a,m,c : qword;

begin

// definiujemy generator LCG

  m := 3956280000;
  a := 1978141;
  c := 1309;

// odczytujemy klucz i wiersz znaków

  readln(X); readln(s);

// zamieniamy małe litery na duże

  s := upcase(s);

// szyfrujemy

  for i := 1 to length(s) do
  begin

// obliczamy kolejną liczbę pseudolosową

    X := (a * X + c) mod m;

// szyfrujemy literkę

    if s[i] in ['A'..'Z'] then s[i] := chr(65 + (ord(s[i]) - 65 + X mod 26) mod 26);
  end;

// wypisujemy zaszyfrowany tekst

  writeln(s);
  writeln;
end.
Code::Blocks
// Szyfrowanie z pseudolosowym odstępem
// Data: 20.08.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  int i;
  unsigned long long X,a,m,c;

// definiujemy generator LCG

  m = 3956280000ull;
  a = 1978141ull;
  c = 1309ull;

// odczytujemy klucz i wiersz znaków

  cin >> X; cin.ignore(256,'\n');
  getline(cin,s);

// szyfrujemy

  for(i = 0; i < s.length(); i++)
  {

// obliczamy kolejną liczbę pseudolosową

    X = (a * X + c) % m;

// szyfrujemy literkę

    s[i] = toupper(s[i]);
    if((s[i] >= 'A') && (s[i] <= 'Z')) s[i] = 65 + (s[i] - 65 + X % 26) % 26;
  }

// wypisujemy zaszyfrowany tekst

  cout << s << endl << endl;
  return 0;
}
Free Basic
' Szyfrowanie z pseudolosowym odstępem
' Data: 20.08.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s
Dim As Integer i
Dim As Ulongint X,a,m,c

' definiujemy generator LCG

m = 3956280000
a = 1978141
c = 1309

' odczytujemy klucz i wiersz znaków

Input X
Line Input s

' zamieniamy małe litery na duże

s = Ucase(s)

' szyfrujemy

For i = 1 To Len(s)

' obliczamy kolejną liczbę pseudolosową

  X = (a * X + c) Mod m

' szyfrujemy literkę

  If Mid(s,i,1) >= "A" And Mid(s,i,1) <= "Z" Then Mid(s,i,1) = Chr(65 + (Asc(Mid(s,i,1)) - 65 + X Mod 26) Mod 26)
Next

' wypisujemy zaszyfrowany tekst

Print s
Print
End
Wynik
1001
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA
WRELMD MUVJQVHPJOXUE ESVRDSNBN V SSXQ SNIRED

1002
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA
FKHGVU HHGMNMAQCVYHP PRWKILEOI U BDOP VSDUPE

1003
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA
ODKRUL MURPUNDRFSJUK AGHDNOLRN J UOFE YHOXAV

 

Zwróć uwagę, iż dla różnych kluczy otrzymujemy zupełnie inne szyfry. Co więcej powtarzające się literki (tutaj A przed i za tekstem) zostają zaszyfrowane w różne znaki – to zaleta szyfru z pseudolosowym odstępem. Aby ukryć odstępy między wyrazami, które pozwalają zidentyfikować słowa, można wpisywać w ich miejsce wybraną literkę (np.X – tak postępowali operatorzy niemieckich maszyn Enigma w czasie II Wojny Światowej). Wtedy szyfr stanie się jednolitym blokiem liter.

 

Szyfrowanie kodem o pseudolosowym odstępie
(C)2012 mgr Jerzy Wałaszek


Klucz 0 ... 3956279999 :


.

 

Deszyfrowanie

Zasada rozszyfrowywania jest prawie identyczna jak przy szyfrowaniu. Jedyna różnica leży we wzorze obliczania kodu znaku z kodu szyfru:

 

ch = 65 + (ch - 39 - X mod 26) mod 26

 

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście
X  –  klucz, X N
m, a, c  – parametry generatora LCG, m,a,c N
s  – zaszyfrowany łańcuch tekstowy
Wyjście:

Rozszyfrowany łańcuch s

Elementy pomocnicze:
i  –  indeks, i N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x na odpowiadający mu znak ASCII
Lista kroków:
K01: Dla i = 0,1,...,|s| - 1, wykonuj K02...K04 ; przetwarzamy kolejne znaki łańcucha s
K02:     X ← (a × X + c) mod m ; obliczamy nową liczbę pseudolosową
K03:     Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01 ; pomijamy znaki nie będące literami od A do Z
K04:     s[i] = znak(65 + (kod(s[i]) - 39 - X mod 26) mod 26) ; rozszyfrowujemy
K05: Pisz s ; wyprowadzamy tekst
K06: Zakończ ; gotowe

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje kolejno klucz X oraz łańcuch s, który rozszyfrowuje kodem o pseudolosowym odstępie i wypisuje wynik. Parametry generatora LCG są zdefiniowane wewnątrz programu. Zakres kluczy jest od 0 do 3956279999.

 

Lazarus
// Deszyfrowanie z pseudolosowym odstępem
// Data: 20.08.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s : string;
  i : integer;
  X,a,m,c : qword;

begin

// definiujemy generator LCG

  m := 3956280000;
  a := 1978141;
  c := 1309;

// odczytujemy klucz i szyfr

  readln(X); readln(s);

// zamieniamy małe litery na duże

  s := upcase(s);

// deszyfrujemy

  for i := 1 to length(s) do
  begin

// obliczamy kolejną liczbę pseudolosową

    X := (a * X + c) mod m;

// deszyfrujemy literkę

    if s[i] in ['A'..'Z'] then s[i] := chr(65 + (ord(s[i]) - 39 - X mod 26) mod 26);
  end;

// wypisujemy rozszyfrowany tekst

  writeln(s);
  writeln;
end.
Code::Blocks
// Deszyfrowanie z pseudolosowym odstępem
// Data: 20.08.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  int i;
  unsigned long long X,a,m,c;

// definiujemy generator LCG

  m = 3956280000ull;
  a = 1978141ull;
  c = 1309ull;

// odczytujemy klucz i szyfr

  cin >> X; cin.ignore(256,'\n');
  getline(cin,s);

// deszyfrujemy

  for(i = 0; i < s.length(); i++)
  {

// obliczamy kolejną liczbę pseudolosową

    X = (a * X + c) % m;

// deszyfrujemy literkę

    s[i] = toupper(s[i]);
    if((s[i] >= 'A') && (s[i] <= 'Z')) s[i] = 65 + (s[i] - 39 - X % 26) % 26;
  }

// wypisujemy rozszyfrowany tekst

  cout << s << endl << endl;
  return 0;
}
Free Basic
' Deszyfrowanie z pseudolosowym odstępem
' Data: 20.08.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s
Dim As Integer i
Dim As Ulongint X,a,m,c

' definiujemy generator LCG

m = 3956280000
a = 1978141
c = 1309

' odczytujemy klucz i szyfr

Input X
Line Input s

' zamieniamy małe litery na duże

s = Ucase(s)

' deszyfrujemy

For i = 1 To Len(s)

' obliczamy kolejną liczbę pseudolosową

  X = (a * X + c) Mod m

' deszyfrujemy literkę

  If Mid(s,i,1) >= "A" And Mid(s,i,1) <= "Z" Then Mid(s,i,1) = Chr(65 + (Asc(Mid(s,i,1)) - 39 - X Mod 26) Mod 26)
Next

' wypisujemy rozszyfrowany tekst

Print s
Print
End
Wynik
1001
WRELMD MUVJQVHPJOXUE ESVRDSNBN V SSXQ SNIRED
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA

1002
FKHGVU HHGMNMAQCVYHP PRWKILEOI U BDOP VSDUPE
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA

1003
ODKRUL MURPUNDRFSJUK AGHDNOLRN J UOFE YHOXAV
AAAAAA NIEPRZYJACIEL ZAATAKUJE W NOCY AAAAAA
 

Deszyfrowanie kodu o pseudolosowym odstępie
(C)2012 mgr Jerzy Wałaszek


Klucz 0 ... 3956279999 :


.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.