Str042 (2)

80    .1. Kryptografii

Przykład 2. Przypuśćmy, że przejęliśmy wiadomość „FQOCUDEM”, o której wiemy, ii została zaszyfrowana za pomocą przesunięcia pojedynczych liter alfabetu 26-litcrowego, jak w poprzednim przykładzie. Pozostaje znaleźć b. Jedna metoda polega na analizie częstoki. Działa ona w następujący sposób. Przyjmijmy, że wcześniej przejęliśmy długi tekst zaszyfrowany, powiedzmy mający kilkaset liter. Wiemy, że w języku angielskim najczęściej występującą literą jest „li". Zatem rozsądnie jest założyć, że najczęstsza litera tekstu zaszyfrowanego jest zaszyfrowaną literą E. Przypuśćmy dalej, że stwierdziliśmy, iż litera „U" występuje najczęściej w tekście zaszyfrowanym. To oznacza, że przesunięcie przeprowadza „E” = 4 na „U” = 20, tzn. 20 — 4 -l- b (mod 26), czyli h ss 16. Aby odczytać wiadomość, wystarczy więc odjąć 16 (modulo 26) od każdego liczbowego odpowiednika liter w „FQOCUDEM”:

„FQOCUDEM” = 5 16 14 2 20 3 4 12

15 0 24 12 4 13 14 22 = „PAYMENOW” (zapiać mi teraz).

Gdy szyfrujemy za pomocą przesunięć pojedynczych liter alfabetu 26--literowego, nie musimy nawet znać długiego tekstu zaszyfrowanego, by poznać najczęściej występującą literę. Ostatecznie jest tylko 26 możliwości dla b i możemy sprawdzić je wszystkie. Najprawdopodobniej tylko jedna da wiadomość sensowną i ta wartość b jest kluczem szyfrowania.

Tak więc system kryptograficzny tego typu jest zbyt prosty, by mógł być dobry. Zbyt łatwo go złamać. Pewnym ulepszeniem jest użycie bardziej ogólnego typu przekształceń Z[NZ, zwanych przekształceniami afinicznymi: C = aP + b (mod JV), gdzie a i b są ustalonymi liczbami całkowitymi (razem tworzą one klucz szyfrowania). Jeśli na przykład, używając 26-literowego alfabetu, chcemy zaszyfrować naszą wiadomość „PAYMENOW” za pomocą przekształcenia afinicznego z kluczem szyfrowania a = 7, b = 12, to otrzymamy

15 0 24 12 4 13 14 22t-+ 13 12 24 18 14 25 6 10 = „NMYSOZGK”.

Aby rozszyfrować wiadomość zaszyfrowaną za pomocą przekształcenia afinicznego C s aP + b (mod N), musimy najpierw wyrazić P za pomocą C, otrzymując P = a'C + b' (mod N), gdzie a' jest liczbą odwrotną do a modulo N, a liczba b' jest równa -a~ ^lb w ZjNZ. Zauważmy, że ta metoda jest dobra tylko wtedy, kiedy NWD(a, N) = 1; w przeciwnym razie nie można wyrazić P za pomocą C. Jeśli NWD(a, N) > 1, to łatwo można wskazać więcej niż jeden tekst jawny dający ten sam tekst zaszyfrowany, a więc nie możemy jednoznacznie odtworzyć tekstu jawnego z tekstu zaszyfrowanego. Zgodnie z definicją nie jest to przekształcenie szyfrujące: wymagamy zawsze, by to przekształcenie było równowartościowe, tzn. by tekst jawny był jednoznacznie wyznaczony przez tekst zaszyfrowany. Podsumowując, afiniczny system kryptograficzny

3.1. Frotte ty nemy kryptnptficme    81

_w ^-literowym alfabecie z parametrami aę(7j/N'Z)* i beZINT* jest wyznaczony przez wzory:

C= aP + b (mod //),    P^a'C-f b' (mod tfj,

gdzie

a’ = a~^l w (Z/NZ)*, b'=-a 'b.

W szczególnym przypadku możemy w systemie afinicznym przyjąć o = 1, by otrzymać system oparty na przesunięciu. Inny szczególny przypadek, to b = 0: P = aC (mod iV), C = a~^lP (mod ń/j, Dla 6 = 0 przekształcenie szyfrujące nazywamy przekształceniem liniowym, co oznacza, że takie przekształcenie przeprowadza sumę na sumę, czyli jeśli C, szyfruje P, i C₂ szyfruje p_v to C, + C_z szyfruje P_Ł + P₂ (oczywiście dodajemy modulo $).

Przypuśćmy teraz, że wiemy, iż przechwycona wiadomość została zaszyfrowana za pomocą przekształcenia afinicznego pojedynczych liter ^-literowego alfabetu. Chcemy znaleźć klucz szyfrowania a, b tak, aby móc odczytać tę wiadomość. Potrzebujemy do tego dwóch informacji.

Przykład 3. W dalszym ciągu używamy alfabetu 26-Iiterowego. Załóżmy, że literą występującą najczęściej w tekście zaszyfrowanym jest Jt”, a literą drugą pod względem częstości występowania jest „D”. Rozsądnie jest przyjąć, że szyfrują one odpowiednio „E” i „T”; są to dwie najczęściej występujące litery alfabetu w języku angielskim. Zatem, zastępując litery ich odpowiednikami liczbowymi, otrzymamy:

10a' + 6'= 4 (mod 26),

3 a' + 6' = 19 (mod 26).

Mamy dwie kongruencje z dwiema niewiadomymi, a' i b'. Najszybszą metodą rozwiązania jest odjęcie tych dwóch kongruencji stronami, by wyeliminować b'. Otrzymujemy la' = 11 (mod 26) i stąd a' s V¹11 s 9 (mod 26). Teraz możemy obliczyć b\ podstawiając otrzymaną wartość a' do jednej z tych kon-gruencji: 6' = 4 — 10a' s 18 (mod 26). Wiadomość może więc być rozszyfrowana za pomocą wzoru P = 9C + 18 (mod 26).

Przypomnijmy z algebry liniowej, że n równań wystarczy do znalezienia n niewiadomych tylko wtedy, gdy te równania są niezależne (tzn. wyznacznik układu jest niezerowy). Na przykład dla dwóch równań z dwiema niewiadomymi oznacza to, że linie proste, będące wykresami tych równań, przecinają się w jednym punkcie (nie są równoległe). W naszej sytuacji, gdy próbujemy złamać afiniczny system kryptograficzny na podstawie znajomości dwóch najczęściej występujących liter tekstu zaszyfrowanego, może okazać się, że nie potrafimy jednoznacznie wyznaczyć a' i b'.