Historia kryptologii - część trzecia

Opublikowany: 29-03-2011 22:21 przez Krystian

Po dwóch wcześniejszych częściach udało nam się dojść początku XX wieku. Nie będę ukrywał, że wiek XX obfitował w tak wiele ważnych dla kryptologii odkryć, że w najlepszym wypadku poruszymy jedynie sam wierzchołek całej tej szyfrowej góry i to w kilku kolejnych artykułach.


Przejdźmy od razu do rzeczy i zajmijmy się osobą wywodzącą się jeszcze z XIX wieku. Chodzi mi mianowicie o Félixa Delastelle, który mimo tego, że był kryptografem amatorem wymyślił kilka niegłupich szyfrów.


Pierwszym z nich jest "szyfr bifid". Oparty o "kwadrat Polybiusa" i przestawienia. Czyli dwie bardzo stare techniki, które pojawiły się w części pierwszej. Do tego Delastelle dodał podział elementów. Brzmi to mgliście, więc przeanalizujmy przykład.


Zaczniemy od wymieszanego "kwadratu Polybiusa" (usuńmy q i oddzielmy i od j), który będzie naszym kluczem.



Wiadomością, którą zaszyfrujemy znowu będzie "hunowie nas atakuja". Stwórzmy tabelkę, w której pod kolejnymi literami pojawią się "współrzędne" litery na naszym kwadracie. W drugim rzędzie numer rzędu w trzecim rzędzie numer kolumny.



Teraz zapiszmy cyfry rzędami i łączymy w pary, które będą nowymi koordynatami na naszym "kwadracie", otrzymujemy:

11 32 51 43 42 41 42 12 44 33 15 51 34 24 14 53 44


Pierwsza zmienna oznaczać będzie rząd, a druga kolumnę w "kwadracie". Efektem tego przekształcenia jest:

Tyzgrerbanizfjhxa


"Test Kasiskiego" tutaj nie pomoże, ponieważ nie ma tutaj pojęcia długość klucza. Doszło do "rozproszenia" wartości za pomocą przestawień koordynatów przypisanych do znaków. Przy dłuższych wiadomościach pojawia się za to wielkość bloku, na które wiadomości mogą zostać podzielone dla wygody szyfrującego. Teoretycznie znając wielkość takiego bloku bylibyśmy krok bliżej rozszyfrowania. Tyle tylko, że problemem nadal pozostaje nieznajomość wymieszanego "kwadratu Polybiusa" (teoretyzując dalej możliwe jest przecież użycie dwóch różnych kwadratów, co jeszcze bardziej utrudni zadanie).


Delastelle udoskonalił "szyfr bifid" przenosząc go z dwóch wymiarów do trzech ("szyfr trifid"). Tak jak w "szyfr bifid" mieliśmy dwie wartości dla litery, tak w "szyfr trifid" mamy trzy wartości.


Szyfrowanie zaczynamy od losowego podzielenia naszego 26 znakowego alfabetu na trzy części po 9 liter, ponieważ brakuje nam jednego znaku dodajemy kropkę (-:


Nasze trzy kwadraciki wyglądają tak:


Trzema wartościami każdej litery są: numer kwadratu, rząd i kolumna. Nasze litery przyjmą więc takie wartości:


Kolejne kroki są identyczne do tych w "szyfrze bifit". Zamiast liter naszego komunikatu jawnego zapisujemy odpowiednie koordynaty:


Teraz zapisujemy kolejne trzy rzędy, aby wymieszać wartości i od razu grupujemy je po trzy cyfry:

212 123 321 211 121 313 312 311 112 121 233 112 222 132 111 113 221


I przerabiamy na litery z kwadratów:

nfrvtecidtzdbuaps


Dlaczego uznałem "szyfr trifid" za istotny i warty pokazania? Gdybyśmy przeszli dwa wymiary wyżej, a zamiast wartości dziesiętnych używali wartości binarnych moglibyśmy dojść do kodu Baudot-Murray używanego w telegrafach, a stąd już niedaleka droga do powszechnie stosowanej we współczesnej kryptografii manipulacji zerami i jedynkami.


Zarówno bifid jak i trifid były odporne na ówczesne metody kryptoanalizy (dzięki dyfuzji, czyli rozproszeniu). Przestawiania przeprowadzane na koordynatach wszystkich znaków skutecznie eliminowały wszelkie sposoby znalezienia jakiegoś punktu zaczepienia, który skróciłby ilość obliczeń niezbędnych do złamania szyfru. Oczywiście w erze komputerów atak pełnego przeglądu nie miałby większych trudności z pokonaniem obu szyfrów.


Delastelle nie zakończył na trifidzie romansu z kryptografią. W zanadrzu miał jeszcze udoskonalenie "podwójnego szyfru Playfaira" zwane "szyfrem czterokwadratowym". W rozwiązaniu tym zamiast dwóch kwadratów Polybiusa zbudowanych w oparciu o dwa klucze mieliśmy jeszcze dodatkowo dwa zwykłe kwadraty Polybiusa. Tworzyły razem siatkę dwa na dwa kwadraty. Przy czym kwadraty stworzone z kluczy były w prawym górnym i lewym dolnym rogu. Podczas szyfrowania digrafów pierwszy digraf był zaznaczany na górnym lewym kwadracie, który był zwykłym Polybiusem, zaś drugi na prawym dolnym Polybiusie. Wartości szyfrowane brane więc były z pozostałych dwóch kwadratów utworzonych na naszych kluczach. Całość była więc takim "przerośniętym Playfairem", z tym, że wyeliminowano problem z sytuacją, gdy dwa znaki są w tej samej kolumnie lub rzędzie.


No dobrze, krótki przykład:


Nasze dwa klucze: "mysecretkey" oraz "otherkey".


Tworzymy dwa kwadraty tak jak to robiliśmy przy "szyfrze Playfair":


Teraz połączymy je w jeden "nadkwadrat" zgodnie z wcześniej podaną zasadą.


W oparciu o powyższy kwadrat szyfrujemy naszą wiadomość kolejnymi digrafami. Dla przypomnienia, pierwszy znak - lewy górny kwadrat, drugi prawy dolny, zaś do szyfrogramu trafiają litery z dwóch pozostałych rogów "prostokąta":


wiadomość: hu no wi en as at ak uj ax


szyfrogram: bn ii xy ej sl el md pc su


"Szyfr czterokwadratowy" jest oczywiście silniejszy od zwykłego i podwójnego "Playfaira", jednak sam proces tworzenia kwadratów jest znacznie dłuższy. Jeśli chodzi o kryptoanalizę czterokwadratowca to podstawą jest to, czy mamy dwa zwykłe kwadraty Polybiusa i dwa oparte o klucz, czy cztery kwadraty oparte o klucz (możliwa w końcu jest również taka wersja). Pierwszy wariant jest prostszy, a kryptoanaliza oparta może być o wzorce. W końcu identyczne digrafy tekstu jawnego (w tym wypadku jednak ważna jest kolejność liter w digrafie!) generują te same digrafy szyfrogramu (chociażby wyraz "kukurydza"). Przydatna staje się lista wzorców rzeczywistych słów. Do tego występują powtórzenia pojedynczych liter jeśli dwa digrafy są "podobne". Na ile podobne? Przykładowo podobne jak w wyrazie porosty (grupa podgatunków grzybów). Mamy digrafy po ro st yx (x dopełnieniem). Szyfrowane przez powyższy kwadrat na: pd pf on wx. Powtarzają się pierwsze litery w dwóch pierwszych zaszyfrowanych digrafach. Podobieństwo polega więc na tym, że jedna litera jest dokładnie ta sama w obu digrafach, zaś drugie litery pochodzą z dokładnie tej samej kolumny/rzędu (oczywiście i tutaj ważna jest ich kolejność). Ta przypadłość również pozwala zastosować pewien wzorzec oparty o rzeczywiste słowa.


Delastelle jest też autorem książki pod tytułem "Traité Élémentaire de Cryptographie" ("Traktat o podstawach kryptografii"), prace nad nią zakończył kilka miesięcy przed śmiercią, zaś pierwsze wydanie pojawiło się dopiero po jego zgonie.


Kolejnym kryptologiem, o którym chciałem wspomnieć jest kolejny Francuz (ale ich się narobiło) Étienne Bazeries. Pojawił się w części pierwszej w związku z "dyskiem Jeffersona" i jego późniejszą, lepszą wersją zwaną "Cylindrami Bazeriesa" (przypominam o tym, że Bazeries nie znał odkrycia Jeffersona).


Étienne Bazeries przez wiele lat służył w armii Francuskiej (podczas wojny Francusko-Pruskiej trafił nawet do niewoli). Kryptologią zainteresował się stosunkowo późno, bo dopiero około czterdziestego roku życia. Pierwszym jego osiągnięciem było pokonanie w 1890 roku używanego we Francuskiej armii szyfru przestawieniowego. W efekcie doprowadziło to do zmian, które poprawiły bezpieczeństwo narodowe. W 1891 roku rozpoczął pracę w biurze szyfrów działającym przy ministerstwie spraw zagranicznych. Aż do końca pierwszej wojny światowej współpracował z armią Francuską jako ekspert pomagając jej rozpracowywać Niemieckie szyfry wojskowe.


Wróćmy jednak do najważniejszego wynalazku Bazeriesa, którym były oczywiście "cylindry Bazeriesa". Zasadę ich działania omówiłem dokładniej w części pierwszej. Dla przypomnienia - mamy 36 albo 25 (czy ile tam nam się wymarzy) dysków (tarczy czy jak to tam nazwiemy, chociaż możemy też mieć znaki ustawione po prostu w linii), na każdym dysku 26 znaków, w pewnym losowym ustawieniu (nadawca i odbiorca muszą mieć rzecz jasna takie same zestawy dysków do dyspozycji). Kolejność dysków staje się naszym kluczem. ¯eby zaszyfrować tekst jawny ustawiamy w odpowiedni sposób dyski, tak by znaki naszego tekstu jawnego były obok siebie na kolejnych dyskach tworząc "linię". Naszym szyfrogramem jest dowolna inna "linia" spośród 25 pozostałych.


"Cylindry Bazeriesa" stały się podstawą urządzenia szyfrującego M-94 używanego przez armię Stanów Zjednoczonych. Z koncepcją użycia "cylindrów" wyszedł pułkownik Parker Hitt, który eksperymentował z "cylindrami Bazeriesa" od roku 1914. W 1917 major Joseph Mauborgne rozwinął projekt, który ostatecznie w 1922 roku pojawił się jako urządzenie szyfrujące model M-94 (w marynarce USA znane pod nazwą CSP 488). M-94 było stosowane w armii USA do roku 1945 (chociaż z biegiem czasu coraz rzadziej i do coraz mniej kluczowych kanałów komunikacji), kiedy zastąpiono je w pełni rozwiązaniem elektromechanicznym M-209, o którym powiemy sobie, w którejś z kolejnych części.


M-94 używało 25 aluminiowych dysków do tworzenia szyfrogramów i odszyfrowywania wiadomości. Kilka lat później powstała wersja skrywająca się pod nazwą M-138-A. Ta z kolei opierała się nie o dyski, a o paski, których było, aż 100, zaś do komunikacji wybierano 30 z nich. Ta odmiana wykorzystywana była przez Departament Stanu USA oraz Marynarkę Wojenną USA. M-138-A była oczywiście bezpieczniejsza, za to znacznie mniej poręczna. Obie wersje możecie zobaczyć na obrazku obok, M-94 i jego aluminiowe dyski to niewielki metalowy cylinder, który mieścił się do kieszeni, dzięki czemu można było z niego wygodnie korzystać na linii frontu. M-138-A wymagał więcej miejsca.


Przejdźmy do kryptoanalizy M-94 i cylindrów Bazeriesa. W poprzednim artykule wprowadziliśmy (nie na darmo!) zasadę Kerckhoffsa, mówiącą, że "System kryptograficzny powinien być bezpieczny nawet wtedy, gdy wszystkie szczegóły jego działania (za wyjątkiem klucza) są znane". Wprowadzimy teraz dwa proste pojęcia. "Atak na szyfrogram" oraz "atak na znany tekst jawny". Atakiem na szyfrogram były wszystkie wcześniej rozważane kryptoanalizy. Za każdym razem mieliśmy dostęp jedynie do wiadomości zaszyfrowanej. Skoro jednak Kerckhoffs opublikował swoje reguły to sprawdzimy czy M-94 jest odporny na atak ze znanym tekstem jawnym.


W tym przypadku będziemy mieć do dyspozycji szyfrogram oraz odpowiadający mu tekst jawny (zwany slangowo "ściagawką", czyli "crib’em"), zaś naszym celem nie będzie poznanie wiadomości, a złamanie klucza, który zgodnie z zasadą Kerckhoffsa jest teraz najważniejszą częścią system kryptograficznego.


Nie ma co zwlekać, trzeba brać się do roboty. W celach prezentacji koncepcji kryptoanalizy nasz testowy zestaw będzie miał mniej dysków niż M-94, mianowicie jedynie 15. Szyfrować będziemy krótszą niż zwykle wiadomość "hunowieatakuja", na dyskach o następującym układzie znaków:

1. GIKXWEMUVQSRNDPZTLOYJFCHBA
2. FDSTRYPCNEGZIBXOLUJVQKMHAW
3. QRSTINYHCOWLJFAKMUXZBVDPEG
4. HSGWYKLQMFIOZBJTEXCDPAVRUN
5. OXSWACVZJTELGRMUFPHNKQDIBY
6. JQVSDNFYTGRZEIUMAXKLBWOCPH
7. IDXVRBASCOTLPFEYJGZHWKUMNQ
8. ZWSOTYJUARVCGMHXNLFQEBKPID
9. NSZOMXLWETJYKCAFBVRPIUHQDG
10.JOQBMYGCKNISHAFERXDVPUWZTL
11.NCRYQHXEBDJSWGAVMZKLPIOUFT
12.BYENUSWKCOLPVHTGRAZFIXQJDM
13.SDWCTLJNQKXFIBAOZYHRMPGUVE
14.EYTJOFIKBQSDLPGUNAZXCMRHVW
15.KJAFVUYIRODCTXZNLBWPGMSEHQ


Dyski wygenerowałem sobie za pomocą kawałka kodu w C. Generator ciągów o różnej długości i zawartości przyda nam się z pewnością jeszcze wiele razy. Pamiętajcie, to nie są linie, tylko dyski, nie mają końca i początku, przed pierwszym znakiem jest ostatni, a po ostatnim pierwszy, można nimi dowoli obracać (-:


Na boku zaszyfrowałem sobie naszą wiadomość. Dla zmyłki dysków jest więcej o jeden niż znaków w wiadomości. Jest to tak naprawdę nie istotne, chociaż najlepiej gdyby nasz szyfrogram oraz ściągawka z nim powiązana miały długość równą ilości dysków. Klucza oraz przesunięcia nie zdradzę, otrzymamy go w procesie kryptoanalizy, którą przeprowadzimy za pomocą metody de Viarisa (-:


Szyfrogram, który otrzymałem, po zaszyfrowaniu wiadomości "hunowieatakuja", na powyższych dyskach, bazując na kluczu X oraz przesunięciu w prawo (gdybyśmy nie ustalili kierunku nasz przykład skomplikowałby się zbyt mocno, bo mielibyśmy dwie wartości w każdym polu) o Y linii brzmi:

FQSMDYNUQVEDAX


Kryptoanalizę rozpoczniemy od połączenia w pary liter wiadomości z odpowiadającymi im literami szyfrogramu. Pary mamy następujące:

h - F; u - Q; n - S; o - M; w - D; i - Y; e - N; a - U; t - Q; a - V; k - E; u - D; j - A; a - X


Głównym orężem w tej metodzie kryptoanalizy będzie tabelka wypełniona przesunięciami dla wszystkich par, które przed chwilą utworzyliśmy (kolumny) na wszystkich dyskach (rzędy). Obliczeń jest więc dość dużo, ale w końcu mamy komputery, więc to nie jest problem (-:


Teraz musimy znaleźć zestawy wartości, które pojawiają się we wszystkich rzędach (a przynajmniej te, które występują w największej ilości rzędów).


Brawo, naszym przesunięciem użytym w szyfrze jest liczba 7, wiemy też, że dysk numer 13 nie uczestniczy w szyfrowaniu. Teraz musimy przesunąć rzędy, tak aby nasza wartość pojawiła się na głównej przekątnej. Oczywiście możliwa jest sytuacja, kiedy więcej niż jedna wartość wystąpi na każdym dysku, wtedy do dalszej analizy mielibyśmy więcej materiałów i rzecz jasna więcej roboty do wykonania. Na szczęście w naszym przypadku istnieje tylko jedna wartość, którą jest "7".


Przykładowy układ (i tak na dobrą sprawę to jedyny, w którym na głównej przekątnej mamy siódemki) może wyglądać tak:


Jak najwygodniej przejść z wcześniejszej tabelki do tej powyższej? Wystarczy zamieniać miejscami rząd, który najlepiej pasuje z rzędem zajmującym rozpatrywaną pozycję. Przykład:


Zaczynamy od pierwszej kolumny, translacji h na F. Ponieważ tylko dysk 6. spełnia nasze oczekiwanie zamieniamy miejscami 1. z 6. Przechodzimy do translacji u na Q. Pasują dyski 10. i 11. Dysk 11. Ma tylko jedną siódemkę, więc to on powinien zająć kolejne miejsce. Zamieniamy 11. z 2. Przechodzimy do translacji n na S. Tym razem tylko dysk 15. pasuje. Zamieniamy 15. z 3. I przechodzimy do translacji o - M. Tutaj pasują dyski 2. i 3. skoro 2. ma tylko jedną siódemkę to właśnie ją zamieniamy z dyskiem 4. Do w - D pasuje tylko dysk 7. Przy i - Y ponownie mamy dwa, więc wybieramy ten z mniejszą ilością siódemek.


Z kolejnymi translacjami robimy tak samo. W efekcie otrzymujemy tabelę z dyskami ustawionymi w pewnej kolejności. Nie musi to być w pełni poprawne rozwiązanie. Jeśli jednak wybraliśmy właściwy offset, czyli przesunięcie, to powinniśmy po testowym ponownym zaszyfrowaniu otrzymać szyfrogram bardzo podobny do tego pierwotnego. Podobieństwa będą występować zawsze tam gdzie pasuje tylko jeden dysk (taki szkielet, na którym można oprzeć resztę). Teraz pozostaje poprzestawiać pozostałe dyski, tak, aby ostatecznie otrzymać prawidłowy klucz, którym jak widać jest ustawienie dysków: 6-11-15-2-7-12-1-9-14-3-10-5-4-8 (-:


Nasz przypadek jest bardzo wygodny. Wśród pasujących przesunięć mieliśmy tylko jedną wartość. Jak wcześniej wspomniałem takich wartości mogłoby być więcej, wtedy dla każdego przypadku musielibyśmy dokonywać oddzielnych przestawień dysków i sprawdzać poprawność poprzez testowe szyfrowanie. Wygodnie również występowały same siódemki. Gdyby były liczniejsze, ułożenie dysków byłoby trudniejsze (kilka wariantów do rozpatrzenia).


Tak to wygląda w przypadku naszej hipotetycznej wersji urządzenia opartego o 15 dysków. W rzeczywistości dysków było więcej, jednak sam atak na klucz wyglądałby identycznie. Oczywiście moglibyśmy mieć szyfrogram i "ściągawkę" znacznie krótsze niż ilość dysków, to jednak nie wykluczyłoby powodzenia , a jedynie utrudniłoby pracę.


Skoro problemem i jednocześnie najsłabszym ogniwem całego systemu szyfrującego jest klucz czas przejść do kolejnego tematu, który przedstawi zupełnie inne podejście do kluczy.


Mam na myśli szyfr Vernama oraz szyfr z kluczem jednorazowym (one-time pad). Jest to symetryczne szyfrowanie strumieniowe. Symetryczne, ponieważ ten sam klucz przeprowadza szyfrowanie i deszyfrowanie, zaś strumieniowy, ponieważ zarówno wiadomość jawna jak i szyfrogram są ciągiem (strumieniem).


Gilbert Vernam był inżynierem pracującym w AT&T Bell Laboratories. Wynalazł szyfr strumieniowy oraz przedstawił koncepcję dalekopisu opartego właśnie o szyfr strumieniowy. Jest to bardzo ważne ponieważ dalekopis nie przesyłał znaków tylko oczywiście impulsy. Czyli komunikacja opierała się o "zera" i "jedynki" (ustalmy, że tak było, bez niepotrzebnego zagłębiania się w historię) niezależnie za pomocą czego były one przedstawiane. Z tego względu potrzebne było kodowanie. W dalekopisie Vernama użyto kodowania Baudot-Murray, które wygląda tak:


Za jego pomocą kodujemy naszą wiadomość: “hunowie nas atakuja" do postaci:

11111 00010 00101 11100 00110 00011 11001 01100 10000 00100 00110 11000 10100 00100 11000 00001 11000 11110 11100 11010 11000 01000


Jest to nasz strumień wiadomości jawnej. Teraz potrzebujemy ciąg losowych (względnie pseudolosowych) wartości "keystream", czyli strumień klucza. Musi być nie krótszy niż wiadomość. Przyjmijmy, że będzie to:

10101 00110 01001 11011 10111 01011 01101 11011 00010 11010 10101 11010 10110 10101 11000 10110 10100 10001 01011 11011 01101 01011


Teraz na kolejnych parach zer i jedynek wziętych ze strumienia wiadomości i ze strumienia klucza przeprowadzamy operację XOR, która dla przypomnienia osiąga takie wartości:


W efekcie otrzymujemy nasz szyfrogram:

01010 00100 01100 00111 10001 01000 10100 10111 10010 11110 10011 00010 00010 10001 00000 10111 01100 01111 10111 00001 10101 00011


W tej postaci może trafić on na drugi koniec kabla (czy też dowolnego innego medium, które przenosi nam dane), gdzie poddany zostanie ponownie operacji XOR z użyciem znanego strumienia klucza, co w efekcie pozwoli odczytać nasz tekst jawny.


Inna nazwa tego szyfru to szyfr idealny. Pod jakim względem jest idealny? Pod względem odporności na kryptoanalizę opartą o sam szyfrogram. To oczywiste, ponieważ ten system nie pozwala wywnioskować absolutnie niczego w oparciu o sam szyfrogram. Kolejne bity są zerami i jedynkami. Pełna losowość, bez żadnego punktu zaczepienia. W końcu nasz znany szyfrogram S jest wynikiem operacji XOR na dwóch nieznanych wartościach wiadomości jawnej W i strumienia klucza K

W xor K = S - Jedno równanie i dwie niewiadome.


Nie ma róży bez kolców rzecz jasna. Problemem jest klucz, który musi być równie długi, lub dłuższy niż szyfrowana wiadomość. Musi pozostać też tajny, inaczej komunikacja zostanie zagrożona.


W tym momencie z pomocą przychodzi nam koncepcja zaproponowana przez Josepha Mauborgne’a (który dodatkowo był również autorem pierwszej oficjalnie uznanej metody rozwiązania szyfru Playfair), zwana po prostu "szyfrem z kluczem jednorazowym". Klucz, w dowolnej postaci (czy to karty perforowane czy to strumień zer i jedynek) używany jest tylko raz. Natychmiast po użyciu zostaje zniszczony. Szyfr Vernama razem z kluczem jednorazowym uznawany jest za jedno z kluczowych odkryć w dziedzinie kryptologii. Trudno się z tym stanowiskiem nie zgodzić w końcu rozwiązanie to jest pod wieloma względami rzeczywiście idealne. Oczywiście nie jest pozbawione wad, przez co znajdowało zastosowanie wyłącznie przy zabezpieczaniu najważniejszych informacji, przesyłanych na najważniejszych odcinkach, którym można było zapewnić tajność kluczy jednorazowych (czy to używając dobrze pilnowanych kurierów, czy innej metody wymiany). Z przyczyn w tym miejscu aż nadto oczywistych pominąłem kryptoanalizę z wykorzystaniem tekstu jawnego i odpowiadającemu mu szyfrogramowi. Wyciągnięty w ten sposób klucz byłby oczywiście bezużyteczny, ponieważ już nigdy nie zostałby użyty.


Mam nadzieję, że szyfry oraz kryptoanalizy przedstawione w tej części były interesujące. Podobnie jak kwestie związane z zagadnieniem klucza. W kolejnej części skupimy się przede wszystkim na pierwszej wojnie światowej (chociaż oczywiście nie tylko na tym). Tymczasem, niech duch Vernama będzie z wami!


bro
Brak komentarzy