Dr inż. Robert Wójcik



Pobieranie 2,08 Mb.
Strona2/13
Data14.02.2018
Rozmiar2,08 Mb.
1   2   3   4   5   6   7   8   9   ...   13

Szyfry przesunięte
Odmianą szyfrów monoalfabetowych są szyfry przesunięte.
W szyfrach tych alfabetem tajnym f(m) jest alfabet przesunięty cyklicznie o pewną liczbę pozycji k.
Przykładem takiego szyfru jest szyfr Cezara, w którym k = 3.
Jeśli korzystamy z alfabetu n = 26 literowego, to jego znaki możemy zakodować za pomocą liczb w sposób pokazany w tabeli:

Liczby odpowiadające znakom informacji m w alfabecie przesuniętym oblicza się z zależności
f(m) = (m + k) mod n,
gdzie n jest liczbą znaków.
Jeśli znakiem kryptogramu jest znak c, to przekształcenie deszyfrujące ma postać:
f−1(c) = (c − k) mod n.
Gdy stosujemy szyfr Cezara, dla którego k = 3, tekstowi jawnemu KRYPTOGRAFIA odpowiada kryptogram NUBSWRJUDILD.
Można stosować szyfr podstawieniowy z iloczynem, w którym znaki tekstu jawnego mnoży się przez klucz k:
f(m) = m k mod n,
gdzie n jest liczbą znaków.
Ze względu na warunek jednoznacznego deszyfrowania klucz k wybiera się w taki sposób, aby k i n były względnie pierwsze, tj. NWD(n,k) = 1 (NWD – największy wspólny dzielnik).
Do deszyfrowania stosuje się liczbę odwrotną k-1 liczoną modulo n, którą oblicza się z zależności:
k k-1 (mod n) = 1,
czyli dla danych k i n, liczba k-1 jest rozwiązaniem równania
k k-1 = t n + 1, gdzie k-1 i t są liczbami całkowitymi.

Równania modularne (kongruencje) mod n mają nieskończenie wiele rozwiązań w liczbach całkowitych, dlatego dla potrzeb kryptograficznych przyjmujemy element k-1, będący najmniejszą liczbą dodatnią.


Funkcja deszyfrująca dla szyfru, w którym zastosowano iloczyn, będzie postaci:
f-1(c) = c k-1 mod n.
Szyfrowanie i deszyfrowanie za pomocą szyfru podstawieniowego z iloczynem.
Zaszyfrujmy znak tekstu jawnego S - 18 dla k=7 i n=26. Znak kryptogramu obliczamy ze wzoru, podstawiając za m liczbę 18 odpowiadającą literze S.
f(m) = m k mod n = 18⋅7 mod 26 = 22.
Literze S - 18 tekstu jawnego odpowiada litera W - 22 kryptogramu.
Liczba k-1=15, ponieważ 7 ⋅15 (mod 26) = 1.
Znak tekstu jawnego odpowiadający znakowi kryptogramu W - 22 obliczamy z równania:
f-1(c) = c k-1 mod n = 22⋅15 mod 26 = 18.
W wyniku deszyfrowania otrzymaliśmy literę S - 18.
Liczbę odwrotną k-1 modulo n obliczamy, rozwiązując kongruencję
k k-1 (mod n) = 1,

Każda kongruencja ma nieskończenie wiele rozwiązań. Dla celów kryptograficznych potrzebny jest pierwiastek będący najmniejszą liczbą dodatnią.


Rozwiązanie takie można znaleźć, rozwiązując następujące równanie w dziedzinie liczb całkowitych


(*) k k-1 − t n = 1,
gdzie k i n są wiadome, a szukamy k-1.
Równanie to można rozwiązać, odwracając algorytm Euklidesa.
Algorytm Euklidesa stosuje się do wyznaczania największego wspólnego dzielnika NWD. Jeśli d = NWD(a,b), to NWD można przedstawić w postaci kombinacji liniowej liczb a i b ze współczynnikami całkowitymi, to jest d = u a + v b. Opierając się na tym twierdzeniu, można rozwiązać równanie (*).
Ilustruje to przykład: wyznaczenie liczby odwrotnej modulo n.
Przyjmijmy dane z przykładu: k=7 i n=26. Szukamy k-1, stosując algorytm Euklidesa. W tym celu należy rozwiązać równanie (*).
k-1 ⋅ 7 − t ⋅ 26 = 1.
Najpierw wyznaczamy NWD(7,26), który jest ostatnią niezerową resztą:
26 = 3⋅7 + 5, 7 = 1⋅5 + 2, 5 = 2⋅2 + 1 (ostatnia reszta).
W tym przypadku NWD(7,26) = 1.
Aby przedstawić liczbę 1 jako kombinację liniową liczb k=7 i n=26, wykorzystujemy ciąg równości od ostatniej do pierwszej w algorytmie Euklidesa.
W każdym kroku zapisujemy liczbę 1 wykorzystując wcześniejsze reszty, aż dojdziemy do samych liczb k=7 i n=26:
1 = 5 - 2⋅2 = 5 - 2(7 - 1⋅5) = 3⋅5 - 2⋅7 = 3⋅(26 - 3⋅7) - 2⋅7 =

= 3 ⋅ 26 - 11 ⋅ 7.


W niektórych przypadkach występuje potrzeba zmiany znaków liczb w końcowym wyrażeniu. Aby zmienić znaki liczb, dodajemy i odejmujemy liczbę równą 7 ⋅ 26:
1 = 3 ⋅ 26 ( -7 ⋅ 26 + 26 ⋅ 7) - 11⋅ 7 = 15 ⋅ 7 − 4 ⋅ 26 = k-1k − t n = 1 .
Porównując pierwsze równanie tego przykładu z otrzymanym wynikiem, widzimy, że
k-1 = 15,

k = 7,


t = 4,

n = 26.
Metodę przesunięcia i mnożenia w szyfrach prostych można łączyć, w wyniku czego otrzymujemy przekształcenie afiniczne (szyfr afiniczny):


f(m) = (m k1 + k2) mod n,
gdzie k1 i n są liczbami względnie pierwszymi.
Kluczem jest tu para liczb k1 i k2.

Szyfry monoalfabetyczne można łatwo złamać, stosując analizę statystyczną.


Jeśli znamy tekst jawny odpowiadający kryptogramowi, to badamy rozkład częstości występowania znaków w tekście jawnym i kryptogramie. Następnie kojarzymy znaki o zbliżonej częstości.
Jeśli nie znamy tekstu jawnego, to badamy rozkład częstości występowania znaków w kryptogramie. Następnie kojarzymy znaki o zbliżonej częstości na podstawie tabeli określającej częstość występowania wybranych znaków w tekstach jawnych w danym języku. Znaki o podobnych częstościach odpowiadają sobie.

Względną częstość występowania liter, spacji, liczb oraz kropki i przecinka w języku literackim angielskim i polskim oraz programach w Pascalu pokazano w tabeli. Kreska w tabeli oznacza, że częstość występowania znaku jest mniejsza od 0,0005.
Najłatwiej złamać szyfry oparte na alfabetach przesuniętych, ponieważ każda litera kryptogramu znajduje się w stałej odległości od odpowiedniej litery tekstu jawnego. W przypadku szyfrów,

w których korzysta się z przekształceń afinicznych współczynniki k1 i k2 można wyznaczyć, rozwiązując układ równań:

(m1 k1 + k2) mod n = c1,
(m2 k1 + k2) mod n = c2, (***)

(mt k1 + k2) mod n = ct,
gdzie mi są liczbami odpowiadającymi znakom tekstu jawnego, a ci liczbami odpowiadającymi znakom kryptogramu.



1   2   3   4   5   6   7   8   9   ...   13


©operacji.org 2017
wyślij wiadomość

    Strona główna