Str043 (2)

12 J. K rypt ogniła

Przykład 4. lYzypuśćniy, żc mamy dany krypt ogram, o którym wiemy, że został zjuzyfrowany za pomoc'} przekształcenia Klinicznego pojedynczych liter alfnhctu 28-li terowego. składającego się z liter A-Z, odstępu i 7, gdzie liczbowym i odpowiednikami liter A-Z są liczby 0-25, odpowiednikiem odstępu jest 26 i odpowiednikiem ? jest 27. Z analizy częstości występowania liter w ktyplogramic wynika, że dwiema najczęściej występującymi literami są „B” i „?", w tej kolejności Ponieważ najczęściej występującymi literami w języku angielskim, zapisywanym w tym 28-Iitcrowym alfabecie, są „ ** (odstęp) i „E", w tej kolejności, więc przypuszczamy, że „B” szyfruje „ ", a „7" szyfruje „E”. Prowadzi to do dwóch kongruencji: a'+ 6'= 26 (mod 28), 27a' -|- b' = 4 (mod 28). Odjęcie stronami tych dwóch kongruencji daje: la' = 22 (mod 28), co jest równoważne kongruencji o'= 11 (mod 14). To z kolei oznacza, że a' = 11 lub 25 (mod 28) i wtedy odpowiednio 6' s 15 lub 1 (mod 28). Istotne jest to, że oba możliwe afmicznc przekształcenia rozszyfrowujące 11C+ 15 i 25 C -t-1 dają.. ” i „E" jako litery tekstu jawnego odpowiadające literom „B” i „?” kryptogramu. W tym momencie możemy spróbować obu możliwości i zobaczyć, która daje sensowną wiadomość. Albo możemy kontynuować naszą analizę częstości. Przypuśćmy, że stwierdzimy, iż „I” jest trzecią pod względem częstości literą kryptogramu. Wykorzystując to, że trzecią najczęściej występującą literą w języku angielskim (w naszym alfabecie 28-literowym) jest litera „T", otrzymamy trzecią kongruencję: 8a' + b' = 19 (mod 28). Ta dodatkowa informacja wystarczy do stwierdzenia, które przekształcenie afiniczne jest właściwe. Stwierdzimy, że jest nim 11C + 15.

Przekształcenia digramów. Przypuśćmy teraz, że jednostkami naszego tekstu jawnego i kryptogramu są dwuliterowe bloki znaków, nazywane digra-mami. Oznacza to, że tekst jawny jest podzielony na fragmenty dwoili terowe. Jeśli cały tekst jawny składa się z nieparzystej liczby liter, to dopisujemy na końcu dodatkową literę po to, by otrzymać całkowitą liczbę digramów. Wybieramy przy tym literę, która najprawdopodobniej nie utrudni poprawnego odczytania tekstu, taką jak odstęp, jeśli nasz alfabet zawiera odstęp, lub „X" czy „Q”, jeśli używamy alfabetu składającego się tylko z 26 liter.

Każdemu digramowi przypisujemy następnie odpowiednik liczbowy. Najprostszym sposobem jest przyporządkowanie digramowi liczby xN + y, gdzie x jest odpowiednikiem liczbowym pierwszej litery digramu, y jest odpowiednikiem liczbowym drugiej litery digramu, a N jest liczbą liter alfabetu. Równoważnie, traktujemy digramy jako liczby dwucyfrowe zapisane w systemie pozycyjnym o podstawie N. To daje wzajemnie jednoznaczną odpowie-dniość między zbiorem wszystkich digramów ^-literowego alfabetu a zbiorem wszystkich nieujemnych liczb całkowitych mniejszych od N². Ten sposób numerowania digramów był już wcześniej opisany w szczególnym przypadku, gdy N = 27.

Następnie wybieramy przekształcenie szyfrujące, czyli permutację liczb całkowitych zbioru {0, 1, 2,..., N² — 1}. Jednymi z najprostszych przekształ-

ceń szyfrujących są przekształcenia afiniczn* Ten zbiór liczb naturalnych traktujemy jako Z/Al^zZ. a przekształcenie definiujemy tak, by liczba P była zaszyfrowana przez nieujemną liczbę mniejsza od N¹ i spełniającą kongruencję C s a? -I- 6 (mod Al²). Tak jak poprzednio, a nie może mieć wspólnych dzielników z Al (co oznacza, że nie ma też wspólnych dzielników z Al²), po to by istniało przekształcenie odwrotne umożliwiające rozszyfrowywanie: P = a'C + b' (mod Al²), gdzie a' s a"¹ (mod N¹), b' = -a ^!ó (mod Al²). Tłumaczymy teraz liczbę C na blok dwuliterowy, pisząc ją w postaci C = x'AI + y', a następnie wybierając litery, których odpowiednikami liczbowymi są x' i y’.

Przykład 5. Przypuśćmy, że używamy alfabetu 26-literowego i naszym przekształceniem szyfrującym digramy jest Cs 159?+ 580 (mod 676). Wtedy digram „NO" ma odpowiednik liczbowy równy 13 • 26 -+ 14 = 352 i jest zaszyfrowany przez digram 159 • 352 + 580 = 440 (mod 676), czyli „QY". Digram „ON" ma odpowiednik liczbowy równy 377 i jest zaszyfrowany przez 359 = „NV". Zauważmy, że digramy zmieniają się w całości i nie ma żadnego związku między tym, jak został zaszyfrowany jeden digram, a tym, jak został zaszyfrowany inny digram, mający jedną literę wspólną z tym pierwszym digramem, czy nawet składający się z tych samych liter, ale w odwrotnym porządku.

Aby złamać system kryptograficzny oparty na przekształceniu afinicz-nym digramów C = aP 4- b (mod Al²), musimy wiedzieć, w jaki sposób są szyfrowane dwie różne jednostki tekstu jawnego. Ponieważ jednostkami tekstu są digramy, więc analiza częstości polega na zliczaniu bloków dwuliterowych występujących najczęściej w długim kryptogramie (oczywiście zliczamy tylko te bloki, w których pierwsza litera jest pierwszą literą jednostki tekstu, i pomijamy te bloki dwuliterowe, których litery pochodzą z dwóch różnych jednostek tekstu), a następnie na porównaniu z tablicą częstości digramów w tekstach zapisanych w języku angielskim (przy użyciu tego samego alfabetu). Jeśli na przykład używamy alfabetu składającego się z 26 liter, to z analizy statystycznej wynika, że „TH” i „HE" są dwoma najczęściej występującymi digramami, w tej kolejności. Znajomość dwóch odpowiadających sobie digramów w tekście jawnym i kryptogramie najczęściej (choć nie zawsze) wystarczy do wyznaczenia a i b.

Przykład 6. Wiemy, że nasz przeciwnik używa systemu kryptograficznego opartego na alfabecie składającym się z 27 liter, w którym litery A-Z mają odpowiedniki liczbowe równe 0-25, a odstęp ma odpowiednik liczbowy równy 26. Każdy digram odpowiada zatem liczbie całkowitej zawartej między 0 i 728 = 27² - 1, zgodnie z zasadą mówiącą, że jeśli dwie litery digramu mają odpowiedniki liczbowe równe x i y, to odpowiednikiem liczbowym digramu jest 21 x + y, tak jak to już wyjaśnialiśmy wcześniej. Przypuśćmy, że z analizy