Historia kryptologii - część pierwsza

Opublikowany: 12-03-2011 22:33 przez Krystian

Jakiś czas temu w mojej głowie zrodził się pomysł powołania do życia swojej strony, na której będę dzielił się tym co wiem (albo przynajmniej tym co wydaje mi się, że wiem). Tematyka będzie różnorodna, chociaż oczywiście (mniej lub bardziej) luźno powiązana z takimi tematami jak sieci komputerowe, programowanie, systemy operacyjne, kryptologia i co mi tam jeszcze innego wyda się ciekawe i godne podzielenia się z bliźnimi. Nie jestem ekspertem, ani nie uważam się za eksperta (cóż za wygodna wymówka w razie ewentualnych błędów merytorycznych), więc nie zawsze mogę mieć rację. Dlatego może lepiej nie bierzcie wszystkiego co tu znajdziecie za pewnik.


Oczywiście pomysł na stronę pojawił się razem z pomysłem na zawartość strony. Konkretnie razem z pomysłem na kilka początkowych artykułów. Jednym z pierwszych chciałem uczynić tekst o kryptologii. Pomysł spodobał mi się z dwóch powodów. Po pierwsze krypto to ciekawa sprawa, chociaż dla wielu osób dość skomplikowana (nie będę ukrywał, że dla mnie również, zwłaszcza kiedy do głosu dochodzą obszary matematyki, na których nie czuję się zbyt pewnie), po drugie od dwóch miesięcy w zasadzie codziennie pisałem ten lub inny program w takim lub innym języku, więc mały odpoczynek od kodu dobrze mi zrobi na umysł.


Po wybraniu kryptologii za temat pierwszego artykułu stwierdziłem, że artykuł to stanowczo za mało na tak obszerny temat. Powstanie więc cykl artykułów o kryptologii. Na pierwszy ogień, pójdzie jej historia , potem jakieś małe wprowadzenie do kryptologii nowożytnej, dalej może jakieś zagłębienie się w kilka algorytmów i na koniec oczywiście małe "fiku-miku", czyli wykorzystanie krypto w praktyce z kilkoma (setkami?) linii kodu. W końcu kryptologia to nie martwe słowa, ale coś nad wyraz użytecznego.


No dobrze, ale czy kryptologia jest ciekawa? Z pewnością zależy to od punktu widzenia, ale jeśli coś wiąże się z najpilniej strzeżonymi tajemnicami, wielkimi pieniędzmi i władzą to raczej nie jest mdłe i nudne. W końcu krypto używane jest i było (no i będzie) przez szpiegów, wojsko, władze, instytucje finansowe, rewolucjonistów, powstańców i tych wszystkich, dla których utajnienie pewnych informacji stanowi coś wyjątkowo ważnego, czasem decydującego o życiu i śmierci (i to nie tylko pojedynczej osoby), a nawet wpływającego na bieg historii (tutaj pewnie każdemu na myśl zupełnie słusznie przyjdzie do głowy Enigma, chociaż przykładów będzie znacznie więcej).


Przejdźmy jednak do konkretów. Czyli jak wcześniej wspomniałem do historii kryptologii, a w zasadzie do historii kryptologii do końca wieku XVIII. Czyli części pierwszej z trzech. Kolejna zajmie się historią do początku pierwszej wojny światowej, zaś trzecia wszystkim co było podczas obu wielkich wojen oraz w okresie między nimi, aby w końcu płynnie przejść do wprowadzenia do współczesnej kryptologii. Dla ścisłości muszę dodać, że wiele informacji może się tutaj nie pojawić (zwłaszcza tych informacji, które są bardziej powszechne), za to możecie oczekiwać paru "rarytasów" wyszperanych z wyjątkowo rzadkich i dziwnych źródeł. Powinno więc być ciekawie, chociaż nie mam ambicji zrobienia kompletnego przeglądu całej historii kryptologii, jako, że jest to materiał na bardzo obszerną książkę.


"Historia kryptologii część pierwsza"


Kryptologia i kryptologia, a gdzie tu kryptografia, czyli wyraz z którym część z was częściej się spotyka niż z kryptologią. Albo kryptoanaliza. Jak to się wszystko łączy? Powalczmy może na samym początku z językami i tłumaczeniami, to powinno nieco wyjaśnić.


Sam wyraz kryptologia pochodzi oczywiście z greki i jest połączeniem wyrazów "kryptos" i "logos". Pewnie weźmiecie mnie za wariata, ale przeprowadziłem małe śledztwo w paru słownikach starożytnej greki i jakoś oficjalne tłumaczenie "kryptos" jako "ukryty", które pojawia się w wielu publikacjach na temat kryptologii nie przemawia zbytnio do mnie. W tym kontekście bardziej pasuje tłumaczenie jako "sekretny" lub "tajny".


"Ukryty" jest dla mnie sensowniejszy jako swobodne tłumaczenie wyrazu "steganos" (które z kolei jest raczej tłumaczone dosłownie jako "ślad na wodzie", "znak wodny", "coś mętnego"), który razem z "graphein" czyli "zapis", tworzy Steganografię, czyli naukę o ukrytym zapisie, czyli w skrócie o ukryciu poufnych informacji (przykładowo w zupełnie błahych danych udających zwykłą komunikację, lub dawniej, w Grecji zapisując wiadomość na skórze głowy niewolnika i wysłanie go w trasę kiedy włoski mu odrosną).


Skoro już ustaliliśmy, że "kryptos" znaczy w naszym kontekście "sekretny" to pozostaje nam jeszcze drugi wyraz. "Logos" albo "logy", czy też "log". "Logos" oznacza "słowo", zaś "logy/log" to sufiks (końcóweczka) pochodzący ze starożytnej greki, który na potrzeby tego tekstu przetłumaczmy konkretnie (pomińmy pozostałe tłumaczenia) jako "nauka/dział wiedzy". Sam sufiks pojawia się chyba we wszystkich europejskich językach i znaczy dokładnie to samo. Stąd mamy przecież teologię, kosmologię i tak dalej.


Tak więc mamy kryptologię, czyli "sekretne słowo", albo "naukę o sekretach". Stąd prosta droga do kryptografii (połączenie "kryptos" i wspomnianego wcześniej "graphein" czyli "zapis",), czyli "sekretnego zapisu". Jest jeszcze kryptoanaliza, która łączy wyraz "kryptos" z wyrazem "analyein", który wśród wielu swoich dziwnych znaczeń ma sformułowania: "łamanie" (w sensie fizycznym), "rozsupływanie" (w kontekście węzła chociażby), "od wejścia do wyjścia", czy "osłabianie". W najsensowniejszym tłumaczeniu niech będzie kryptoanaliza jako "rozwiązywanie sekretu".


Tak więc kryptografia zajmuje się tworzeniem szyfrów, kryptoanaliza, atakowaniem i rozwiązywaniem ich. Zaś oba te wyrazy łączy kryptologia, która jest nauką o szyfrach.


Skoro nomenklatura trzech podstawowych wyrazów jest już w miarę jasna możemy spokojnie przejść do zasadniczej historii kryptologii. Kto stworzył pierwszą zaszyfrowaną wiadomość? Kto jako pierwszy złamał zaszyfrowaną wiadomość?


W wielu publikacjach znalazłem stwierdzenie, że pierwszym zaszyfrowanym tekstem były pewne hieroglify, które pod wieloma względami odbiegały od innych hieroglifów. Nie znam się na hieroglifach, więc nie jestem pewien czy to właściwa odpowiedź. Mam jednak nieco odmienną teorię na ten temat. Punktem wyjścia jest problem czy sam nieznany innym alfabet nie jest pewnego rodzaju szyfrem. Czy pierwszy człowiek, który pomyślał "ten szlaczek oznacza drzewo, tamta kreska górę" nie stworzył też jednocześnie pierwszego szyfru? W końcu nie miał świadomości samego problemu "zaszyfrowania". Może dobrym podejściem jest uznanie, że pierwszy szyfr wymaga z jednej strony powszechności alfabetu, w którym wiadomość jest zapisana, zaś z drugiej świadomości dokonania samego procesu zaszyfrowania. To w pewnym sensie wyklucza hieroglify, ponieważ symbole do dzisiaj pozostają nie do końca wyjaśnione, ponadto czy szyfrem może być jedynie bariera analfabetyzmu większości osób? W dodatku mamy kwestię pewnej nieużyteczności. Hieroglify jako ośrodek do przenoszenia zaszyfrowanych wiadomości są ciut nie mobilne. Bardziej na miano pierwszych szyfrów zasługują zapiski pisma klinowego na glinianych tabliczkach z Mezopotamii, stawiane przez większość jako drugi po hieroglifach szyfr.


Hieroglify nie pasują trochę do zastosowań kryptografii tamtych czasów, czyli do przenoszenia wiadomości między dowództwem, a oddziałami, między szpiegami, a ich zwierzchnikami, między kochankami (o czym wspomina Kamasutra, co oczywiście pojawia się również we wszystkich publikacjach o krypto (-: ), wyznawcami jakiejś religii (podobno Chrześcijanie wykorzystywali kryptografię w okresie prześladowań) czy innymi osobami chcącymi zachować tajemnicę konwersacji. No dobrze, ale jak to wyglądało przed pierwszymi szyframi? Początkowo wymiana ograniczała się do zwykłych ustnych komunikatów. Niestety posłańcy byli mało odporni na "kryptoanalizę łamania kolan" (jedna z popularniejszych i co ciekawe skuteczniejszych metod ataku brute-force, również w dzisiejszych czasach) i dość szybko (najpóźniej między pierwszym, a drugim kolanem) zdradzali treść wiadomości temu kto ich złapał. Wymyślono wtedy pierwsze proste szyfry. Posłaniec nie znał metody przekształcającej zwykłą wiadomość do postaci poufnej, więc jedyne co mógł wyjawić przeciwnikowi, to niezrozumiały bełkot. Oczywiście nie poprawiało to specjalnie sytuacji życiowej samych posłańców (-: jednak strony tajnej komunikacji były zadowolone, z tego, że ich wiadomości nie są łatwo dostępne.


Może przejdźmy na chwilę do konkretnych szyfrów z tamtych czasów, które podzielimy na przestawieniowe i podstawieniowe.


Prostym przykładem przestawieniowego szyfru może być przerobienie wiadomości "hunowie nas atakuja" na "uhoniwe ans takajua", czyli przestawienie sąsiadujących ze sobą liter w obrębie wyrazu. Banalne? Oczywiście, ale jeśli wymyślimy kilka przestawień, następujących po sobie, to już nie jest to takie banalne do rozwiązania. Poprawmy więc "nasz szyfr". Usuńmy przerwy między wyrazami. Następnie przestawmy sąsiadujące litery, potem przestawmy parami co trzecie litery (1 z 3, 2 z 4, 5 z 7, 6 z 8 itd.), potem co czwartą (1 z 4, 2 z 5, 3 z 6, 7 z 10, 8 z 11, 9 z 12, 13 z 16, 14 z 17), a na koniec jeszcze sąsiadujące tyle, że od końca (16 z 17, 14 z 15, 12 z 13 itd) aktualnego szyfrogramu. W efekcie mamy hennoauaswiatkauj (o ile algorytm się nie pomylił (-: ). Nie jest już to tak oczywiste jak wcześniejsza wersja, chociaż oczywiście zdeterminowany przeciwnik zaatakuje nasz szyfr różnymi przestawieniami i może odnaleźć pierwotną wiadomość. Kluczem jest oczywiście przestawienie liter w odwrotnej kolejności niż robiono to podczas szyfrowania.


Zajmujmy się teraz sposobem krytoanalizy naszej wiadomości. Metodę statystyczną możemy sobie odpuścić - opiera się ona o rozkład częstotliwości występowania danych liter w tekście, ponieważ dokonaliśmy jedynie przestawień liter metoda statystyczna nie ma tutaj racji bytu (za to przyda nam się później do czegoś zupełnie innego). Niezłym sposobem będzie atak metodą słów prawdopodobnych, która polega na dopasowaniu fragmentu znanego tekstu (lub odszyfrowanej wiadomości) do szyfrogramu w celu znalezienia przesunięć. Skoro Hunowie przechwycili wiadomość i są w stanie wojny ze swoim przeciwnikiem, to takim słowem prawdopodobnym będzie Hun, Hunowie, czy też typowo wojenne wyrazy ("oblegać", "atak", "wojsko", "obrona") itd. (pomińmy może fakt, że metoda słów prawdopodobnych została wymyślona po upadku Hunów (-: nie bądźmy jednak tacy drobiazgowi, w końcu to tylko przykład teoretyczny). W zależności od złożoności przekształcenia metoda siłowa (na wiadomości, a nie na posłańcu) również może być skuteczna (tyle, że bez komputerowej, czy tez jakiejkolwiek innej automatyzacji metoda siłowa była trochę niewygodna).


Jeśli chodzi o historyczny przykład szyfru przestawieniowego to mamy chociażby skytale. Czym były rzeczone skytale? To po prostu kij pewnej grubości, na który nawijano pasek pergaminu i na którym pisano poziomo wiadomość, tylko posiadacz identycznej grubości kija był w stanie szybko przeczytać wiadomość. Problemem kryptoanalizy było w tym przypadku znalezienie kija o odpowiednim przekroju. Niezbyt trudne, dlatego dodawano elementy steganografii. Posłaniec ukrywał (chociażby obwiązując się nim) przenoszony pasek pergaminu literami do wewnątrz.


Drugim wspomnianym sposobem szyfrowania było szyfrowanie podstawieniowe. W najpopularniejszym historycznym przykładzie jest to tak zwany szyfr Cezara (tak, tak Juliusz Cezar go używał). Czyli monoalfabetyczna wersja szyfru podstawieniowego o 3 znaki. Jak to działa? Mamy alfabet, powiedzmy 26 znaków. Za "a" mamy "d", za "b" mamy "e" za "c" mamy "f" itd. "Przesuwamy" litery o trzy w prawo. Nasza wiadomość "hunowie nas atakuja" ma postać "kxqrzlh qdv dwdnxmd". Wygląda dziwnie? To prawda. Zresztą dopasowanie podstawienia w wersji monograficznej nie jest zbyt trudne. Skoro jednak Cezar go używał to znaczy, że mu wystarczał.


Innym przykładem szyfru podstawieniowego z tamtych czasów jest Atbash. Atbash używany był przez starozakonnych (czy jak kto woli przez ¯ydów) na alfabecie hebrajskim. Zasada podstawienia była prosta. Pierwsza litera była zastępowana z ostatnią, druga z przedostatnią, trzecia z trzecią od końca. Dla alfabetu łacińskiego będzie to wyglądać tak: "a" zamieniamy z "z", "b" z "y", "c" z "x" i tak dalej. Alfabet jest więc zapisany w odwrotnej kolejności i tyle, żadna filozofia. Nasz komunikat "hunowie nas atakuja" brzmieć będzie po zaszyfrowaniu tak "sfmldrv mzh zgzpfqz".


Wysoką skuteczność zarówno Atbasha jak i dla szyfru Cezara (oraz dla innych prostych szyfrów podstawieniowych) ma tutaj wspomniana wcześniej metoda statystyczna. Widzimy na pierwszy rzut oka, że brakuje w naszej zaszyfrowanej wiadomości popularnych liter (chociażby samogłosek). Atak może przebiegać w dość prosty sposób. Wystarczy przeanalizować kilka stron tekstu w danym języku. Zrobić rozkład statystyczny występowania poszczególnych liter, potem zrobić analizę szyfrogramu i zastanowić się co za co zostało podstawione. Oczywiście Juliusz Cezar nie przejmował się specjalnie ową metodą statystyczną, ponieważ powstała ona jakieś 900 lat po tym jak powiedział "Et tu, Brute, contra me?" i wyzionął ducha.


Udoskonaleniem szyfru podstawieniowego jest zastąpienie wersji monoalfabetycznej (gdzie jeden znak odpowiada dokładnie jednemu innemu znakowi) szyfrem homofonicznym (pojawił się znacznie później, ale o tym dalej). Powiedzmy, że zamiast na litery chcemy odwzorować na dwucyfrowe liczby (to właśnie nasze "homofony"). Przykładowo zamiast "a" będziemy mieć "11" "37" "48" i "62", zamiast "b" "19" "76" i "95" i tak dalej. Przed doborem kombinacji możemy przeanalizować rozkład statystyczny i dobrać tak podstawienie, żeby zamiast częściej występujących liter było przykładowo siedem homofonów, a zamiast rzadko występujących liter po dwa homofony. To nas trochę uodporni na kryptoanalizę metodą statystyczną.


Obie metody (przestawieniowa i podstawieniowa) pochodzą z antyku. Nie są zbyt trudne do zrozumienia. Obie dawały niezłą skuteczność jak na owe czasy, w końcu nie było wtedy komputerów ułatwiających ataki siłowe. Naturalnie połączenie obu metod skutkowałoby dalszą poprawą.


Inna metoda szyfrowania jaka pojawiła się w antyku to wymyślony przez greka Polybiusa "kwadrat" szyfrujący, zwany na jego cześć "kwadratem Polybiusa". Jak owy kwadrat wyglądał? Tak:



Proste odwzorowanie liter (i razem z j, żeby wszystko zmieściło się w kwadrat 5 na 5), w zasadzie bliżej mu do kodowania niż szyfru, ale bez znajomości "kwadratu" odszyfrowanie nie jest takie oczywiste.


Kryptografia to domena nie tylko cywilizacji basenu morza śródziemnego. Kryptografia rozwijała się również w innych starożytnych państwach, w Chinach, Indiach oraz Japonii, chociaż są to zagadnienia często pomijane w kontekście historii kryptografii (przynajmniej ja trafiłem na kilka dłuższych tekstów zupełnie ten rejon świata pomijających).


Zacznijmy może od Chin. W VI wieku przed naszą erą powstało dzieło autorstwa Sun Wu (czy jak kto woli Sun Tzu, pojawia się też wersja Sun Zi, tyle, że Zi to przydomek i znaczy "mistrz") pod tytułem "Sztuka wojny", w którym oprócz wielu ciekawych przemyśleń na temat prowadzenia wojny znajdziemy (w rozdziale "wywiad") taki fragment:


"Wyróżniamy pięć rodzajów szpiegów: miejscowi, wtajemniczeni, nawróceni, martwi oraz żywi. Kiedy wszyscy oni działają jednocześnie, nikt sie niczego nie domyśla - oto boski plan, skarb każdego władcy. Szpiedzy miejscowi rekrutują się spośród autochtonów. Szpiedzy wtajemniczeni wywodzą sie spośród urzędników wroga. Szpiedzy nawróceni, to tacy, którzy służyli wrogowi, a teraz służą nam. Martwi zaś mają za zadanie przekazywać fałszywe informacje, aby nasi szpiedzy zdemaskowali ich w obozie wroga. ¯ywi szpiedzy to ci, którzy wracają z informacjami o wrogu."


Wielce ubolewam nad tym, że nie pojawia się wzmianka o szyfrach z tamtych czasów, można jednak przypuszczać, że istnieć musiały w takiej lub innej formie, ponieważ "szpiedzy wtajemniczeni" musieli jakoś dostarczać informacje bez wzbudzania podejrzeń (zapewne wykorzystywano zaufanych posłańców i steganografie, jednak śmiem uważać, że coś w rodzaju szyfrów musiało się wtedy pojawić).


Dlaczego "coś w rodzaju szyfrów"? śpieszę z wyjaśnieniami. Problem leży u samej podstawy konstrukcji języka. We wcześniejszych przykładach mieliśmy 26 znaków, które były podstawiane, lub przestawiane. W piśmie chińskim mamy około 50000 znaków (współcześnie, w codziennym życiu używane jest około 15% z nich), które nie są pojedynczymi literami, a sylabami, stąd o piśmie chińskim mówi się też jako o monosylabowym (logosylabowym, czyli znakosylabowym, jako, że za sylabę mamy znak). W dodatku gramatyka języka chińskiego jest diametralnie odmienna od naszej. Rzeczowniki są niepoliczalne (nie wiadomo, czy chodzi o jeden przedmiot, dwa, czy czterdzieści), nie istnieje też czas gramatyczny. Sformułowania są wyjątkowo ulotne i trudne do jednoznacznego tłumaczenia. Dlatego właśnie pierwotną barierą, którą można określić jako quasikryptologiczną (wybaczcie mi słowotwórstwo (-: ), był sam język. Tłumaczenie pojedynczych znaków, czyli sylab jest różne w zależności od kontekstu chociażby. To dawało fantastyczne możliwości ukrywania wiadomości w innych wiadomościach o ile obie strony dogadały się wcześniej co do zasad konwersacji.


Widać, że w takich warunkach nie można było wprowadzić ani szyfrów przestawieniowych, ani podstawieniowych. Bazowano więc właśnie na tym co dawał język, czyli na jego złożoności i wieloznaczności. Ponadto znaki były ideogramami można było więc używać podobieństw między nimi, w celu ukrycia prawdziwego znaczenia.


Ciekawostką może być Nu Shu, to sekretny język wymyślony w Chinach przez kobiety, aby komunikować się między sobą bez wiedzy mężczyzn. Nu Shu został odkryty dopiero w połowie XX wieku.


Kryptografia była rozpowszechniona również w Indiach. Władcy korzystali z szyfrów często i chętnie, aby utrzymać swoje sieci szpiegów w dobrej kondycji. W przeciwieństwie do rozwiązań śródziemnomorskich w Indiach powszechne były metody podstawieniowe, jednak nie na samym tekście pisanym tylko pomiędzy tekstem pisanym, a jego fonetyczną wersją. Czyli powiedzmy pisali "kup kilo ziemniaków", a czytali "Hunowie nas atakuja" (-:


W Japonii również nie próżnowano. Popularna była technika bliźniaczo podobna do "kwadratu Polybiusa". W Japonii było to umieszczenie 48 literowego alfabetu w kwadrat siedem na siedem pól (tak tak, tym razem jedno pole zostaje puste). Zapisane za pomocą liczb znaki można było oczywiście dalej przekształcać, w celu osiągnięcia finalnej wersji szyfrogramu.



Japonię zostawmy może na później. Powróci jeszcze i to w bardzo ciekawym kontekście związanym z Polską w kolejnych częściach. Wróćmy na pewien czas w bliższe nam rejony świata.


Pojawiło się wcześniej to i owo na temat kryptoanalizy. Przyznam się, że były to dywagacje teoretyczne. Dlaczego? Samo słowo Kryptoanaliza zostało ukute dopiero w XX wieku. Zaś pierwsze uporządkowane metody działania zasługujące na nazwę kryptoanalizy pojawiły się stosunkowo późno, bo dopiero IX wieku naszej ery. Na miano pierwszego kryptoanalityka zasługuje z pewnością arabski uczony Al-Kindi. Cóż takiego odkrył? Wspomnianą wcześniej kryptoanalizę statystyczną. Był to wynalazek na tyle skuteczny, że szyfry (kwadrat Polybiusa, podstawienie monoalfabetyczne i wszystkie pochodne metody) pozostawały bezbronne wobec kryptoanalizy przez kolejne pięć wieków. Wszystko zostało opisane w jego książce "Risalah fi Istikhraj al-Mu'amma" ("Manuskrypt o rozszyfrowywaniu zaszyfrowanych wiadomości").


Kolejnym arabskim uczonym wartym odnotowania w kontekście krypto jest Ahmad al-Qalqashandi. Autor "Subh al-a 'sha" - czternastoczęściowej encyklopedii arabskiej, w której pojawiły się liczne informacje na temat kryptografii. Między innymi o szyfrach podstawieniowych, przestawieniowych, wielokrotnych podstawieniach (chociaż nie były to jeszcze szyfry polialfabetyczne) oraz przykłady kryptoanalizy - chociażby użycie tablicy częstotliwości występowania liter, oraz zestawy liter, które nie pojawiają się razem w wyrazie (bardzo pomocne).


Dopiero w roku 1467 Leon Battista Alberti udoskonalił szyfrowanie przez podstawienie szyfrem polialfabetycznym, warto zapamiętać sobie tego Pana, ponieważ często nazywany jest "ojcem zachodniej kryptologii". Uodpornienie na kryptoanalizę statystyczną polegało na ukryciu rozkładu częstości występowania poszczególnych znaków poprzez wiele podstawień. Różne części wiadomości mogły być szyfrowane w inny sposób. Przedstawił też urządzenie uznawane za pierwszą maszynę szyfrującą. Skonstruował dysk szyfrowy, składający się z dwóch kół. Na zewnętrznym znajdowały się litery alfabetu jawnego (24 znaki), na wewnętrznym ruchomym znajdowały się litery alfabetu szyfrowego. Dzięki temu dysk ten definiuje 24 możliwe podstawienia (zamiana tekstu jawnego na litery kryptogramu z koła wewnętrznego), które możemy zmienić co pewien okres przez obrót koła.


W 1518 Johannes Trithemius w swojej pracy pod tytułem "Poligraphia" ukuł pojęcie "tabula recta" pod którym krył się "silnik" szyfru polialfabetycznego Albertiego. Nieco później Blaise de Vigenere przedstawił system do praktycznego zastosowania tego rodzaju szyfrowania, które zostało nazwane "Szyfrem Vigenere’a".


Tablica Vigenere’a, czy jak kto woli "tabula recta", to obiekt poniżej:



Sposób działania szyfru polialfabetycznego oczywiście najlepiej przedstawić na przykładzie. Szyfrowanym tekstem znowu będzie "hunowie nas atakuja" (co prawda w czasach Albertiego i Vigenere byli zamierzchłą przeszłością), do tego potrzebować będziemy klucza szyfrującego. Niech naszym kluczem będzie "mysecretkey".


Tworzymy sobie taką tabelkę:



Literka z rzędu "wiadomość" wybiera nam odpowiednią kolumnę pionową, zaś literka z rzędu "klucz" wybiera nam poziomy rząd. W punkcie przecięcia mamy literkę, która trafia do "szyfrogram". Ponieważ nie ma pojedynczego podstawienia tak jak chociażby w szyfrze Cezara nie można tego zaatakować metodą rozkładu statystycznego. W zasadzie szyfrowanie można tutaj potraktować jako n podstawień dla n znakowej wiadomości, w końcu jak możecie zauważyć literka "u" z oryginalnej wiadomości raz pojawia się w szyfrogramie jako "l", raz jako "s", zaś "a" dwa razy jako "e", raz jako "y" i raz jako "t". Podchodząc do sprawy z drugiej strony "l" w szyfrogramie w oryginalnej wiadomości raz jest literą "u" zaś raz "t". Nie ma więc jednego prostego odwzorowania. Całość opiera się na sile klucza, konkretnie jego długości (tutaj jest krótszy od wiadomości, dlatego został zwielokrotniony, ale oczywiście nic nie stoi na przeszkodzie, żeby był równej długości, lub dłuższy niż szyfrowana wiadomość) i tajności (kiedy klucz wpadnie w ręce wroga, cały system przestaje spełniać swoje zadanie). Pomyślcie chwile o kluczu. Jeśli jego długość wynosiłaby 1 to byłoby to podstawienie monoalfabetyczne. Krótki klucz, powiedzmy o długości 7 znaków zabezpieczający długą wiadomość to nie byłoby mądre rozwiązanie, ponieważ mielibyśmy wielokrotne zastosowanie powtórzenia klucza. Wystarczyłoby zaatakować fragment wiadomości, żeby wydobyć klucz, który pozwoli odczytać całość. Jest coś pomocnego przy ataku? Owszem. Zwróćcie uwagę, że litera "a" w wiadomości powoduje przepisanie szyfrującego ją znaku z klucza prosto do szyfrogramu, ponieważ "a" występuje dość często w tekstach pisanych w alfabecie łacińskim pewien procent szyfrogramu będzie fragmentami klucza. Jeśli dodamy do tego fakt, iż klucz zazwyczaj był (i jest) jakimś tekstem, a nie zlepkiem przypadkowych znaków trudnych do zapamiętania, atak na klucz nie jest pozbawiony szans.


No dobrze, to może weźmiemy na warsztat coś z życia wziętego, chociaż nieco wychodzącego po za informacje do tej pory przedstawione, oraz wychodzącego z ram czasowych części pierwszej.


Druga wojna światowa, Afryka północna rok 1942. Niemcy (konkretnie Abwehra) wysyłają Johannesa Epplera z misją szpiegowską do Kairu. Eppler pojawiał się pod wieloma nieprawdziwymi nazwiskami, znany był szerzej pod pseudonimem "Kondor" i jest oczywiście postacią autentyczną (zachęcam do własnych poszukiwań). Owy agent używał książki "Rebecca" jako podstawy do tworzenia swoich tajnych szyfrogramów, a robił to tak:


"Praca nad utajnieniem tekstu rozpoczynała się od dodawania do przyznanego agentowi numeru osobistego, np. 46, numeru miesiąca i dnia miesiąca. I tak, wysyłając szyfrogram 4 czerwca, musieli do 46 dodać 4 (dzień) i 6 (miesiąc) otrzymując w ten sposób sumę 56. Ta liczba wskazywała stronicę książki, która była kluczem do szyfru. Eppler zaczynał szyfrować, wybierając pierwsze litery z pierwszej linii tekstu ze strony 56. Brzmiały one: "He would like…" Teraz literom tym musiał przyporządkować cyfry od 1 do 9:

Szyfrogram rozpoczynał się od słów:

Co oznaczało: 4 (dzień miesiąca) 6 (czerwca) 15:45 (godzina nadania szyfrogramu) 367 (numer agenta (coś innego niż numer osobisty, który pojawia się na początku /przypis mój)) 128 (słów w depeszy). Pozostałe litery oznaczały zera i były dobierane z liter nie występujących w pierwszych słowach pierwszej linii wybranej stronnicy. Po tym rozpoczynał się właściwy tekst depeszy, składający się ze 128 słów. "Kondor" szyfrował je, używając tablicy tworzonej z pierwszych liter 21 wierszy ze stronnicy 56, z pominięciem akapitów. Każdą tak wybraną literę zastępował odpowiednią cyfrą z tabeli."

(B. Wołoszański "Sensacje XX wieku" - "Pojedynek na pustyni")


Jak widać droga do uzyskania szyfrogramu była dość zawiła. Złamanie systemu bez kilku kluczowych wiadomości było niemożliwe. Obie strony komunikacji, czyli Eppler oraz centrala Abwehry znały aktualny klucz, który zmieniał się codziennie. Wywiad Brytyjski (wszak Kair wtedy był oczywiście zajęty przez Brytyjczyków) bez świadomości, że klucz pochodzi z książki "Rebecca", był bez szans. Jednak historia jest dobrą nauczycielką. Najsłabszym elementem niemieckiej układanki był sam Eppler, konkretniej jego nieostrożność, oraz… chuć (-:


Kelnerka, z którą się przespał zauważyła podejrzanie gruby zwitek banknotów w jego portfelu, do tego kilka dostarczonych policji przez okolicznych handlarzy fałszywych funtów (wskazujących sposobem podrobienia na państwową wytwórnie Rzeszy) oraz nieoczekiwane sukcesy Marszałka Erwina Rommla na froncie, przekonały MI-5 (wywiad Brytyjski), że coś jest nie tak.


Koniec końców "Kondor" został złapany. Początkowo nie chciał współpracować, jednak złamała go obietnica Churchilla o uniewinnieniu w zamian za współpracę. "Kondor" przez resztę wojny pozostał podwójnym agentem, wysyłającym do rzeszy depesze dyktowane przez Brytyjski wywiad. Fałszywymi informacjami walnie przyczynił się do klęski wojsk Osi podczas ofensywy na Egipt (fałszywe informacje sprowokowały główny atak Niemców na wyjątkowo silnie broniony rejon umocnień), co razem z problemami z zaopatrzeniem spowodowało, że wojska Osi w zasadzie przestały się liczyć w Afryce północnej, a Alianci musieli już tylko posprzątać resztki dawnej machiny wojennej Rommla, zwanego przecież do tego czasu "Lisem pustyni".


Jak więc widać kryptologia i gra wywiadów, niezwykle mocno wpłynęła na przebieg wojny i losy świata. Wszak nie wiadomo, co by było, gdyby Rommel dobrał się do Egiptu i świeżych zapasów ropy.



Wróćmy jednak do czasów nieco wcześniejszych. Do XVI wieku, na którym się zatrzymaliśmy. Szyfry polialfabetyczne upowszechniły się w Europie. Były powszechnie używane w zmaganiach militarnych, politycznych, religijnych. Używali ich wojskowi, królowie, papieże oraz zwykli obywatele. Wszak były to czasy wielu przemian, wojen i innych "rozrywek", więc wiele osób chciało przekazać ważne informacje, lub coś zwyczajnie ukryć. Szyfry pojawiały się w kontekstach dworskich intryg i politycznych machinacji. Szyfry opierały się głównie o odkrycie Albertiego, chociaż część z nich nie była specjalnie odporna na ataki.


Nie można obojętnie przejść obok rodu Rossignol, francuskich kryptografów i krypto analityków (wiele pokoleń Rossignolów służyło francuskim monarchom jako kryptolodzy). Antoine Rossignol, złamał szyfr Huguenotów wykorzystywanego podczas oblężenia Réalmont do wysyłania wiadomości do sojuszników z oblężonego miasta. Twierdza została zdobyta, gdy parlamentariusze pokazali dowódcy twierdzy rozszyfrowaną wiadomość, którą wcześniej wysłał po za mury miasta (chodziło konkretnie o problemy z zaopatrzeniem).


Antoinem Rossignolem zainteresował się słynny Kardynał Richelieu ("Kardynała Richelieu sekret wam dziś zdradzę "Od przyjaciół Boże strzeż, z wrogami sobie poradzę"" (-: ), który wykorzystał jego wiedzę, do poprawy szyfrów używanych przez rząd Francji, na czele, którego stał.


Nieco później, za czasów Ludwika XIV Antoine Rossignol wraz z synem opracował na zlecenie właśnie Ludwika XIV "Grand Chiffre" zwany też "Great Cipher", czyli po naszemi "Wielki/wspaniały szyfr". "Grand Chiffre" był wariacją szyfru homofonicznego zwaną nomenklatorem. Łączył książkę kodów ze sporą tablicą podstawień homofonicznych. Podstawienia homofonów dotyczyły zarówno liter jak i całych wyrazów, lub sylab. Popularne wyrazy takie jak nazwiska znanych osób czy obiekty geograficzne (państwa, miasta, rzeki itd.) miały własne podstawienia homofoniczne (kodowanie). Do tego zastosowano pewne pułapki, jak chociażby "zerowe homofony", które niczego nie kodowały (po prostu pusty znak), a miały jedynie przeszkadzać w kryptoanalizie. Inna pułapka to homofony, których wystąpienie "usuwało" pewien poprzedzający je rozszyfrowany fragment (coś jakby backspace (-: ). Wspomniałem przy okazji "szyfru Cezara" o wielu homofonach dla częściej występujących liter, jako skutecznej obronie przez kryptoanalizą metodą statystyczną. Właśnie tutaj znalazło to zastosowanie. Najpopularniejsza w języku Francuskim litera "e" miała, aż 131 homofonów ( z łącznej puli 711 homofonów, jakie pojawiają się w "Grand Chiffre").


O skuteczności "wielkiego szyfru" niech świadczy fakt, że nawet po tym jak wyszedł z użycia (po śmierci trzeciego Rossignola, najmłodszego z rodu Rossignol Antoine-Bonaventure) wiadomości nim zaszyfrowane pozostały niezłamane. Wiadomości dyplomatyczne leżały więc sobie grzecznie w archiwum Francji przez prawie trzysta lat i czekały na rozszyfrowanie. Dopiero inny wybitny Francuski kryptolog Étienne Bazeries (o nim w kolejnej części cyklu) pod koniec XIX wieku złamał "wielki szyfr" Rossignolów. Kolejne wersje (czy też modyfikacje, jak kto woli) "wielkiego szyfru" używane były, aż do początku XIX wieku.


Z "Grand Chiffre" wiąże się też ciekawostka dotycząca persony zwanej jako "człowiek w żelaznej masce". "Grand Chiffre" został użyty do zaszyfrowania listu między Ludwikiem XIV, a Nicolasem de Catinatem, który przez wielu badaczy uważany jest za klucz do rozszyfrowania tożsamości człowieka w żelaznej masce. Niestety w liście nie pojawia się słowo maska i tym podobne, jednoznacznie wskazujące na tę sprawę, za to jest pewien fragment, który nie został rozszyfrowany. Czy ten fragment coś by wniósł do poszukiwań? Kto wie.


Ostatnia sprawa dotycząca rodu Rossignolów, jaką chciałem jeszcze poruszyć dotyczy kwestii stricte formalnych. Za czasów ich pracy dla Ludwika XIV minister wojny (czy jak kto woli, sekretarz królewski do spraw wojny) François Michel Le Tellier powołał do życia "Francuską Czarną Komnatę" ("French Black Chamber") ich miejsce pracy. Później sformułowanie "czarna komnata" stało się międzynarodowym synonimem wszystkich biur szyfrów.


Zajmijmy się może kolejnym interesującym wynalazkiem w dziedzinie krypto, który wyprzedził swoją epokę i czekał ponad sto lat na użycie na szerszą skalę. Mowa o Dysku Jeffersona, czyli tak zwanym "szyfrze tarczowym", znanym później również pod nazwą "Cylindrów Bazeriesa".


Autorem pierwotnej koncepcji był trzeci prezydent USA - Thomas Jefferson. Szyfr opracował w 1795 roku. Nie upowszechnił się jednak. Dla kryptografii odkrył go na nowo wspomniany wcześniej pogromca "Grand Chiffre" Étienne Bazeries. Nie podprowadził koncepcji Jeffersona, po prostu odkrył to ponownie, nie wiedząc nic o istnieniu "szyfru tarczowego". Co ciekawe, sam szyfr powrócił do USA i był wykorzystywany przez US Army w urządzeniu krypto M-94 (używanym w latach 1922-1945).


No dobra, tyle historii. Jak działał sam "szyfr tarczowy"?


Zerknijcie na zdjęcie obok. Jak widać mamy tam dwa wsporniki, oś, oraz 36 tarcz (kółek, czy jak to tam inaczej nazwać). Na każdej tarczy mamy 26 liter alfabetu. Litery nie są umieszczone w określonej kolejności, tylko losowo (chociaż oczywiście każdy zestaw ma identyczne tarcze do dyspozycji). Oś jest ruchoma, więc tarcze mogą być ułożone w dowolnej kolejności.


Samo szyfrowanie i deszyfrowanie przebiega w następujący sposób:


Nadawca ustala sobie kolejność w jakiej tarcze są ułożone na osi. Ich kolejność staje się naszym kluczem. Nadawca obraca tarcze, aby otrzymać w jednej linii wiadomość jaką chce zaszyfrować. Niech będzie "hunowie nas atakuja" (nie martwcie się, Hunowie będą nam towarzyszyć, aż do współczesnej kryptologii, w końcu kto wie, czy kiedyś nie powrócą!). Teraz do wyboru mamy aż 25 wersji szyfrogramu, ponieważ szyfrogramem jest dowolna linia inna niż ta z oryginalną wiadomością. Powiedzmy, że wybieramy linię położoną dziewięć linii pod naszą wiadomością (9 to będzie nasz offset, czyli przesunięcie). Niestety nie mam przy sobie "szyfratora tarczowego" (pewnie został w innych spodniach (-: ), więc dajmy na to nasz szyfrogram brzmi "etapihr szr ybeukol" (tak tak, w żadnym wypadku litera z szyfrogramu nie może odpowiadać literce z oryginału, ponieważ każda litera występuje tylko jeden raz na tarczy). Mamy więc trzy rzeczy - klucz (układ tarcz), przesunięcie (ile linii dzieli szyfrogram od wiadomości) oraz szyfrogram. Przesunięcie nie jest wyjątkowo ważne, może zostać pominięte.


Podczas odszyfrowywania zaczynamy od ułożenia tarcz w odpowiedniej kolejności, czyli od zastosowania klucza. Teraz pozostaje nam ułożenie tarcz, tak aby w jednej linii znalazły się litery naszego szyfrogramu. Jeśli znamy przesunięcie, to patrzymy na odpowiednią linię, aby odczytać treść wiadomości, jeśli przesunięcia nie znamy, analizujemy pozostałe 25 linii, w poszukiwaniu czegoś co ma sens.


Odszyfrowanie nie jest możliwe jeśli nie znamy klucza, lub jeśli nasze tarcze mają zupełnie inny układ niż w urządzeniu szyfrującym. Zupełnie mamy przegwizdane jeśli nie znamy ani klucza, ani układu na tarczach. Zresztą wystarczy sobie wyliczyć "oporność matematyczną". Zacznijmy od problemu braku klucza. Mamy 36 tarcz, ale nie znamy kolejności. Ile jest sposobów ułożenia 36 tarcz? To zwykła permutacja bez powtórzeń (o ile się nie mylę (-: , czyli wariacji bez powtórzeń dla której n=k), czyli jedynie 36! (silnia, a nie 36 i wykrzyknik, chociaż jak tu ktoś dotarł to pewnie wie co to silnia (-: ). 36! równa się 3.719 razy 10 do 41 potęgi - całkiem sporo. Jeśli przypadkiem poznaliśmy klucz, ale nie znamy wyglądu tarcz to i tak jesteśmy w "ciemnej srace", bo każda tarcza może mieć 4.032 razy 10 do 26 potęgi wariantów, do tego nie wiemy, która z nich to nasza tarcz numer jeden, dwa, trzy itd., z poznanego klucza. Może darujmy sobie wersję najgorszą, czyli bez klucza i tarcz, bo w końcu wybranie odpowiednich 36 tarcz z 26! różnych wersji i ułożenie ich na jeden z 36! sposobów to nic miłego.


Tak dobrnęliśmy do końca wieku XVIII zarysowując kilka najistotniejszych problemów kryptologii. Przeszliśmy od stosunkowo prostego "szyfru Cezara" do tak opornych wynalazków jak "szyfr tarczowy" czy "Grand Chiffre". Poznaliśmy też metodę statystyczną, przodka kryptoanalizy. Kolejne epoki historyczne i kolejne ważne postacie kryptologii pojawią się w dalszych częściach. Część druga jeśli nie zostanę zaskoczony przez bogactwo moich źródeł powinna objąć cały wiek XIX.


bro
Ilość komentarzy: 1
Luzak A (11-04-2013 20:17)
Szkoda, ze nie można się jakoś z Tobą skontaktować. Napisz może do mnie. 092C 8437 00B4 09C3 8606 6314 23A3 557E 94CC A0E7 Polecam fajne wideo na akademickiej telewizji. Pokazywal realne transmisje i różne inne ciekawostki.