Str044 (2)

84    3. Kryptografii)

dużych próbek tekstu zaszyfrowanego wynika, że najczęstszymi digramami są (w tym porządku) „ZA“, „IA” oraz „IW”. Załóżmy następnie, że najczęstszymi digramami języka angielskiego (dla tekstów zapisanych za pomocą tego alfabetu ^literowego) są „E ” (tj. „li odstęp”), „S ”, „ T”. Wiemy też, że w systemie kryptograficznym korzysta się z przekształcenia aflnicznego modułu 729. Znajdźmy klucz rozszyfrowujący i odczytajmy wiadomość „NDXBHO". Znajdźmy również klucz szyfrowania.

Rozwiązanie. Wiemy, że teksty jawne są szyfrowane zgodnie ze wzorem C = aT + b (mod 729) oraz że kryptogramy mogą być rozszyfrowane za pomocą wzoru P b a'C + b' (mod 729); liczby a, b tworzą tu klucz szyfrowania, a liczby a\ b' tworzą klucz rozszyfrowujący. Najpierw chcemy znaleźć a' i b\ Wiemy, jak są zaszyfrowane trzy digramy, co po zastąpieniu digramów ich odpowiednikami liczbowymi daje nam trzy kongruencję:

675fl' + ń'= 134 (mod 729),

216a' + b’ = 512 (mod 729),

238a' + b' = 721 (mod 729).

Jeśli spróbujemy wyeliminować b¹, odejmując stronami pierwsze dwie kongru-encje, to dostaniemy kongruencję 459a' = 351 (mod 729), nie mającą jednoznacznego rozwiązania a' modulo 729 (istnieje 27 rozwiązań). Uzyskamy lepszy efekt, jeśli odejmiemy trzecią kongruencję od pierwszej, otrzymując 437a' = 142 (mod 729). Aby rozwiązać tę kongruencję, musimy znaleźć liczbę odwrotną do 437 modulo 729. Dla przypomnienia algorytmu Euklidesa prześledzimy dokładnie wszystkie szczegóły obliczeń;

729 = 437 + 292 4371292 + 145 292 = 2 • 145 + 2 145 = 72-2+1

a następnie

1 = 145-72-2 =

= 145 - 72(292 - 2-145) =

= 145 • 145 - 72 • 292 =

= 145(437 - 292) - 72 • 292 =

= 145 • 437 - 217 • 292 =

= 145 • 437 - 217(729 - 437) = ^s 362 • 437 (mod 729).

Zatem a' - 362 • 142 a 374 (mod 729) i stąd 6' - 134 - 675 • 374 s 647 (mod 729). Zastosujemy teraz przekształcenie rozszyfrowujące do digramów _ł(ND^M, „XB” i „HO” naszej wiadomości - odpowiadają one kolejno liczbom 354, 622 i 203 - i otrzymamy w wyniku liczby 365, 724 i 24. Zapiszemy je w postaci 365= 13-27 + 14,724 = 26- 27 + 22,24 = 0*27 + 24 i uzyskamy trzy digramy tekstu otwartego składające się na wiadomość „NO WAY”. Wreszcie znajdujemy klucz szyfrowania, obliczając a s a^r 5 s 374"¹ = 614 (mod 729) (znów korzystamy tu z algorytmu Euklidesa) i 6= -a'' V = s -614 • 647 s 47 (mod 729).

Uwaga. Pomimo że afiniczne systemy kryptograficzne, w których stosuje się digramy (tzn. modulo W²), są lepsze niż systemy, w których używa się pojedynczych liter (tzn. modulo N), mają one jednak pewne słabości. Zauważmy, że druga litera każdego digramu kryptogramu zależy tylko od drugiej litery digramu tekstu jawnego. Jest tak dlatego, że druga litera zależy tylko od wartości modulo N liczby C = aP+ b (mod W²), a ta wartość zależy tylko od P modulo N, czyli od drugiej litery digramu tekstu jawnego. Zatem możemy uzyskać wiele informacji (mianowicie a i b modulo N) z analizy częstości liter występujących w kryptogramie na miejscach parzystych. Podobna uwaga dotyczy przekształceń afinicznych modulo N^k bloków fc-literowych.

Ćwiczenia

1. Użytkownicy pewnych sieci komputerowych mają zwyczaj przesyłania wiadomości, które mogą kogoś urazić (np. nieprzyzwoitych dowcipów), szyfrując litery (ale nie szyfrując odstępów i znaków przestankowych) za pomocą przesunięcia C=P + b (mod 26). Każdy, kto zechce, może wtedy łatwo odszyfrować taki tekst, ale nikt nie jest zmuszony do czytania wiadomości, które mogą działać na nerwy. Odczytaj zaszyfrowaną pointę następującego dowcipu (dokonaj analizy częstości, by znaleźć b): Na międzynarodowym kongresie chirurgów przedstawiciele różnych narodów porównywali swoje ostatnie osiągnięcia polegające na przyszywaniu utraconych części ciała. Szczególnie mocno spierali się Francuz, Rosjanin i Amerykanin. Chirurg francuski powiedział: „przyszyliśmy nogę kontuzjowanemu biegaczowi i rok później wystartował on w mistrzostwach w biegu na 1000 metrów.” „Za pomocą najbardziej skomplikowanych zabiegów chirurgicznych”, wtrącił się chirurg rosyjski, „mogliśmy przyszyć całą rękę lekkoatlecie i rok później tą właśnie ręką ustanowił on nowy rekord świata w pchnięciu kulą.” Ich zdumienie nie miało granic, gdy Amerykanin przelicytował ich stwierdzeniem: „Jr frjrq n fzvyr ba n ubefr’f nff, naq n lrne yngre vg jnf ryrpgrq Cerfvqrag!" (Uwaga. Jest to tekst angielski zapisany za pomocą 26-literowego alfabetu, w którym dla ułatwienia czytania zostały zachowane odstępy i znaki przestankowe.)