Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00565 008487 10489523 na godz. na dobę w sumie
Podstawy kryptografii. Wydanie II - książka
Podstawy kryptografii. Wydanie II - książka
Autor: Liczba stron: 304
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-1215-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> hacking >> kryptografia
Porównaj ceny (książka, ebook, audiobook).

Poznaj tajniki szyfrowania i zabezpieczania informacji

Większość z nas kojarzy szyfrowanie i kryptografię z filmami czy powieściami poświęconymi tajnym agentom wraz z ich zleceniodawcami. Tymczasem kryptografia -- nauka znana od bardzo dawna i stosowana do przedstawiania określonych danych w formie zrozumiałej tylko dla wybranych osób -- jest powszechnie wykorzystywana nie tylko w armii.

Dziś informacja stała się najcenniejszym towarem, a ochrona danych osobowych -- niezwykle istotnym zagadnieniem. Dlatego efektywne sposoby zabezpieczania informacji mają żywotne znaczenie zarówno dla firm i instytucji, jak i osób prywatnych. Cyfrowe uwierzytelnianie poczty elektronicznej i witryn WWW czy łącza VPN to rozwiązania oparte o niezwykle złożone algorytmy kryptograficzne. Aby sprawnie korzystać z istniejących rozwiązań lub implementować własne, należy zapoznać się z podstawowymi wiadomościami związanymi z szyfrowaniem danych.

Książka 'Podstawy kryptografii. Wydanie II' to doskonały przewodnik po wszelkich zagadnieniach dotyczących szyfrowania danych, uzupełniony o opisy najnowszych osiągnięć w tej dziedzinie. Znajdziesz tu wszystko, co jest niezbędne do zrozumienia i zastosowania zaawansowanych rozwiązań kryptograficznych. Poznasz historię kryptografii, aparat matematyczny leżący u podstaw tej nauki i teorię szyfrowania danych. Dowiesz się, jakie algorytmy szyfrowania stosowane są obecnie i do czego można je wykorzystać. Największy nacisk położono tu na stosowanie kryptografii w praktyce -- czyli na opis protokołów SSL i SSH oraz kwestii związanych z podpisem elektronicznym, algorytmami PGP i implementacją szyfrowania danych w języku PHP.

Zobacz, jak fascynująca jest kryptografia.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Podstawy kryptografii. Wydanie II Autor: Marcin Karbowski ISBN: 978-83-246-1215-4 Format: B5, stron: 304 Poznaj tajniki szyfrowania i zabezpieczania informacji (cid:149) Opanuj mechanizmy matematyczne rz„dz„ce kryptografi„ (cid:149) Poznaj wsp(cid:243)‡czesne algorytmy szyfrowania (cid:149) Zastosuj w praktyce technologie kryptograficzne WiŒkszo(cid:156)(cid:230) z nas kojarzy szyfrowanie i kryptografiŒ z filmami czy powie(cid:156)ciami po(cid:156)wiŒconymi tajnym agentom wraz z ich zleceniodawcami. Tymczasem kryptografia -- nauka znana od bardzo dawna i stosowana do przedstawiania okre(cid:156)lonych danych w formie zrozumia‡ej tylko dla wybranych os(cid:243)b (cid:150) jest powszechnie wykorzystywana nie tylko w armii. Dzi(cid:156) informacja sta‡a siŒ najcenniejszym towarem, a ochrona danych osobowych (cid:150) niezwykle istotnym zagadnieniem. Dlatego efektywne sposoby zabezpieczania informacji maj„ ¿ywotne znaczenie zar(cid:243)wno dla firm i instytucji, jak i os(cid:243)b prywatnych. Cyfrowe uwierzytelnianie poczty elektronicznej i witryn WWW czy ‡„cza VPN to rozwi„zania oparte o niezwykle z‡o¿one algorytmy kryptograficzne. Aby sprawnie korzysta(cid:230) z istniej„cych rozwi„zaæ lub implementowa(cid:230) w‡asne, nale¿y zapozna(cid:230) siŒ z podstawowymi wiadomo(cid:156)ciami zwi„zanymi z szyfrowaniem danych. Ksi„¿ka (cid:132)Podstawy kryptografii. Wydanie II(cid:148) to doskona‡y przewodnik po wszelkich zagadnieniach dotycz„cych szyfrowania danych, uzupe‡niony o opisy najnowszych osi„gniŒ(cid:230) w tej dziedzinie. Znajdziesz tu wszystko, co jest niezbŒdne do zrozumienia i zastosowania zaawansowanych rozwi„zaæ kryptograficznych. Poznasz historiŒ kryptografii, aparat matematyczny le¿„cy u podstaw tej nauki i teoriŒ szyfrowania danych. Dowiesz siŒ, jakie algorytmy szyfrowania stosowane s„ obecnie i do czego mo¿na je wykorzysta(cid:230). NajwiŒkszy nacisk po‡o¿ono tu na stosowanie kryptografii w praktyce (cid:150) czyli na opis protoko‡(cid:243)w SSL i SSH oraz kwestii zwi„zanych z podpisem elektronicznym, algorytmami PGP i implementacj„ szyfrowania danych w jŒzyku PHP. (cid:149) Historia kryptografii (cid:149) Matematyczne podstawy szyfrowania danych (cid:149) Szyfry strumieniowe, klucze publiczne i steganografia (cid:149) Zabezpieczanie po‡„czeæ internetowych (cid:149) Mechanizm PGP (cid:149) Certyfikaty cyfrowe i podpisy elektroniczne (cid:149) Protoko‡y SSL i SSH (cid:149) NajczŒ(cid:156)ciej stosowane algorytmy szyfruj„ce Zobacz, jak fascynuj„ca jest kryptografia Wydawnictwo Helion ul. Ko(cid:156)ciuszki 1c 44-100 Gliwice tel. 032 230 98 63 e-mail: helion@helion.pl Spis treści Kilka słów wstępu ............................................................................................... 9 Rozdział 1. Historia kryptografii ........................................................................ 13 1.1. Prolog — Painvin ratuje Francję .............................................................................. 13 1.2. Początek… ................................................................................................................ 17 1.2.1. Steganografia ................................................................................................... 17 1.2.2. Kryptografia .................................................................................................... 18 1.2.3. Narodziny kryptoanalizy ................................................................................. 20 1.3. Rozwój kryptografii i kryptoanalizy ......................................................................... 21 1.3.1. Szyfry homofoniczne ...................................................................................... 21 1.3.2. Szyfry polialfabetyczne ................................................................................... 22 1.3.3. Szyfry digraficzne ........................................................................................... 27 1.3.4. Kamienie milowe kryptografii ........................................................................ 28 1.4. Kryptografia II wojny światowej .............................................................................. 29 1.4.1. Enigma i Colossus ........................................................................................... 30 1.5. Era komputerów ....................................................................................................... 35 1.5.1. DES ................................................................................................................. 36 1.5.2. Narodziny kryptografii asymetrycznej ............................................................ 37 1.5.3. RSA ................................................................................................................. 37 1.5.4. PGP .................................................................................................................. 38 1.5.5. Ujawniona tajemnica ....................................................................................... 40 1.5.6. Upowszechnienie kryptografii ........................................................................ 40 Rozdział 2. Matematyczne podstawy kryptografii .............................................. 43 2.1. Podstawowe pojęcia ................................................................................................. 44 2.1.1. Słownik tekstu jawnego .................................................................................. 44 2.1.2. Przestrzeń tekstu .............................................................................................. 44 2.1.3. Iloczyn kartezjański ......................................................................................... 45 2.1.4. System kryptograficzny ................................................................................... 46 2.1.5. Szyfrowanie monoalfabetyczne ...................................................................... 47 2.1.6. Funkcje jednokierunkowe ............................................................................... 47 2.1.7. Arytmetyka modulo ......................................................................................... 48 2.1.8. Dwójkowy system liczbowy ........................................................................... 49 2.1.9. Liczby pierwsze ............................................................................................... 50 2.1.10. Logarytmy ..................................................................................................... 54 2.1.11. Grupy, pierścienie i ciała ............................................................................... 54 2.1.12. Izomorfizmy .................................................................................................. 56 6 Podstawy kryptografii 2.2. Wzory w praktyce ..................................................................................................... 57 2.2.1. Kryptosystem RSA .......................................................................................... 58 2.2.2. Problem faktoryzacji dużych liczb .................................................................. 60 2.2.3. Mocne liczby pierwsze .................................................................................... 61 2.2.4. Generowanie liczb pierwszych ........................................................................ 62 2.2.5. Chińskie twierdzenie o resztach ...................................................................... 64 2.2.6. Logarytm dyskretny ........................................................................................ 65 2.2.7. XOR i AND ..................................................................................................... 66 2.2.8. Testy zgodności ............................................................................................... 67 2.2.9. Złożoność algorytmów .................................................................................... 76 2.2.10. Teoria informacji ........................................................................................... 77 Rozdział 3. Kryptografia w teorii ....................................................................... 83 3.1. Ataki kryptoanalityczne i nie tylko .......................................................................... 83 3.1.1. Metody kryptoanalityczne ............................................................................... 83 3.1.2. Kryptoanaliza liniowa i różnicowa ................................................................. 85 3.1.3. Inne rodzaje ataków ........................................................................................ 87 3.2. Rodzaje i tryby szyfrowania ..................................................................................... 92 3.2.1. Szyfry blokowe ............................................................................................... 92 3.2.2. Szyfry strumieniowe ..................................................................................... 101 3.2.3. Szyfr blokowy czy strumieniowy? ................................................................ 106 3.3. Protokoły kryptograficzne ...................................................................................... 107 3.3.1. Protokoły wymiany kluczy ............................................................................ 107 3.3.2. Podpis cyfrowy .............................................................................................. 111 3.3.3. Dzielenie sekretów ........................................................................................ 114 3.3.4. Inne protokoły ............................................................................................... 116 3.4. Infrastruktura klucza publicznego .......................................................................... 120 3.4.1. PKI w teorii… ............................................................................................... 121 3.4.2. …i w praktyce ............................................................................................... 121 3.5. Kryptografia alternatywna ...................................................................................... 124 3.5.1. Fizyka kwantowa w kryptografii ................................................................... 124 3.5.2. Kryptografia DNA ......................................................................................... 130 3.5.3. Kryptografia wizualna ................................................................................... 134 3.6. Współczesna steganografia ..................................................................................... 136 3.6.1. Znaki wodne .................................................................................................. 136 3.6.2. Oprogramowanie steganograficzne ............................................................... 138 Rozdział 4. Kryptografia w praktyce ............................................................... 141 4.1. Konstrukcja bezpiecznego systemu kryptograficznego ......................................... 141 4.1.1. Wybór i implementacja kryptosystemu ......................................................... 142 4.1.2. Bezpieczny system kryptograficzny .............................................................. 143 4.1.3. Najsłabsze ogniwo ......................................................................................... 144 4.2. Zabezpieczanie połączeń internetowych ................................................................ 148 4.2.1. Protokół SSL ................................................................................................. 148 4.2.2. Protokół SSH ................................................................................................. 156 4.3. PGP ......................................................................................................................... 164 4.3.1. PGPkeys ........................................................................................................ 164 4.3.2. PGPmail ........................................................................................................ 167 4.3.3. PGPdisk ......................................................................................................... 175 4.3.4. Standard PGP/MIME .................................................................................... 182 4.3.5. Web of Trust .................................................................................................. 183 4.3.6. PGP 9.x .......................................................................................................... 186 Spis treści 7 4.4. GnuPG .................................................................................................................... 188 4.4.1. Generowanie klucza prywatnego .................................................................. 188 4.4.2. Obsługa programu ......................................................................................... 189 4.5. TrueCrypt ................................................................................................................ 196 4.5.1. Tworzenie szyfrowanych dysków i partycji .................................................. 197 4.5.2. Obsługa dysków wirtualnych ........................................................................ 199 4.5.3. Ukryte dyski .................................................................................................. 200 4.5.4. Pozostałe opcje i polecenia ........................................................................... 202 4.6. Składanie i weryfikacja podpisów elektronicznych ............................................... 204 4.6.1. Wymagania techniczne ................................................................................. 204 4.6.2. Jak zdobyć certyfikat cyfrowy? ..................................................................... 206 4.6.3. O czym warto pamiętać? ............................................................................... 209 4.6.4. Konfiguracja programu pocztowego ............................................................. 209 4.6.5. Struktura certyfikatu ...................................................................................... 215 4.7. Kryptografia w PHP i MySQL ............................................................................... 217 4.7.1. Funkcje szyfrujące w PHP ............................................................................ 217 4.7.2. Szyfrowanie danych w MySQL .................................................................... 222 4.7.3. Kolejne udoskonalenia .................................................................................. 224 Podsumowanie ................................................................................................ 227 Dodatek A Jednokierunkowe funkcje skrótu ................................................... 229 A.1. MD5 ....................................................................................................................... 229 A.1.1. Przekształcenia początkowe ......................................................................... 229 A.1.2. Pętla główna MD5 ........................................................................................ 230 A.1.3. Obliczenia końcowe ..................................................................................... 232 A.2. SHA-1 .................................................................................................................... 232 A.2.1. Przekształcenia początkowe ......................................................................... 232 A.2.2. Pętla główna algorytmu SHA-1 ................................................................... 233 A.2.3. Operacje w cyklu SHA-1 ............................................................................. 233 A.2.4. Obliczenia końcowe ..................................................................................... 234 A.3. SHA-2 .................................................................................................................... 235 A.3.1. Dodatkowe pojęcia ....................................................................................... 235 A.3.2. Przekształcenia początkowe ......................................................................... 236 A.3.3. Operacje w cyklu SHA-2 ............................................................................. 237 A.3.4. Dodatkowe różnice między algorytmami SHA-2 ........................................ 239 Inne funkcje skrótu ........................................................................................................ 240 Dodatek B Algorytmy szyfrujące .................................................................... 241 B.1. IDEA ...................................................................................................................... 241 B.1.1. Przekształcenia początkowe ......................................................................... 241 B.1.2. Operacje pojedynczego cyklu IDEA ............................................................ 241 B.1.3. Generowanie podkluczy ............................................................................... 243 B.1.4. Przekształcenia MA ...................................................................................... 243 B.1.5. Deszyfrowanie IDEA ................................................................................... 243 B.2. DES ........................................................................................................................ 245 B.2.1. Permutacja początkowa (IP) ......................................................................... 245 B.2.2. Podział tekstu na bloki .................................................................................. 245 B.2.3. Permutacja rozszerzona ................................................................................ 247 B.2.4. S-bloki .......................................................................................................... 248 B.2.5. P-bloki .......................................................................................................... 249 B.2.6. Permutacja końcowa ..................................................................................... 250 B.2.7. Deszyfrowanie DES ..................................................................................... 250 B.2.8. Modyfikacje DES ......................................................................................... 251 8 Podstawy kryptografii B.3. AES ........................................................................................................................ 253 B.3.1. Opis algorytmu ............................................................................................. 253 B.3.2. Generowanie kluczy ..................................................................................... 253 B.3.3. Pojedyncza runda algorytmu ........................................................................ 254 B.3.4. Podsumowanie .............................................................................................. 256 B.4. Twofish .................................................................................................................. 256 B.4.1. Opis algorytmu ............................................................................................. 257 B.4.2. Pojedyncza runda algorytmu ........................................................................ 257 B.4.3. Podsumowanie .............................................................................................. 261 B.5. CAST5 ................................................................................................................... 262 B.5.1. Opis algorytmu ............................................................................................. 262 B.5.2. Rundy CAST5 .............................................................................................. 263 B.6. DSA ........................................................................................................................ 263 B.6.1. Podpisywanie wiadomości ........................................................................... 264 B.6.2. Weryfikacja podpisu ..................................................................................... 264 B.6.3. Inne warianty DSA ....................................................................................... 265 B.7. RSA ........................................................................................................................ 266 B.7.1. Generowanie pary kluczy ............................................................................. 266 B.7.2. Szyfrowanie i deszyfrowanie ........................................................................ 266 B.8. Inne algorytmy szyfrujące ...................................................................................... 267 Dodatek C Kryptografia w służbie historii ....................................................... 269 C.1. Święte rysunki ........................................................................................................ 270 C.1.1. 1000 lat później… ........................................................................................ 271 C.1.2. Szyfr faraonów ............................................................................................. 272 C.1.3. Ziarno przeznaczenia .................................................................................... 273 C.1.4. Je tiens l’affaire! ........................................................................................... 274 C.1.5. Tajemnica hieroglifów .................................................................................. 275 C.2. Język mitów ........................................................................................................... 276 C.2.1. Mit, który okazał się prawdziwy .................................................................. 276 C.2.2. Trojaczki Kober ............................................................................................ 279 C.2.3. Raport z półwiecza ....................................................................................... 280 C.3. Inne języki .............................................................................................................. 283 Bibliografia ..................................................................................................... 285 Skorowidz ....................................................................................................... 287 Rozdział 1. Historia kryptografii Dążenie do odkrywania tajemnic tkwi głęboko w naturze człowieka, a nadzieja dotarcia tam, dokąd inni nie dotarli, pociąga umysły najmniej nawet skłonne do dociekań. Niektórym udaje się znaleźć zajęcie polegające na rozwiązywaniu tajemnic… Ale większość z nas musi zadowolić się rozwiązywaniem zagadek ułożonych dla rozrywki: powieściami kryminalnymi i krzyżówkami. Odczytywaniem tajemniczych szyfrów pasjonują się nieliczne jednostki. John Chadwick Jeszcze nigdy tak wielu nie zawdzięczało tak wiele tak niewielu. Winston Churchill Szyfr Cezara wprowadzono w armii rosyjskiej w roku 1915, kiedy okazało się, że sztabowcom nie można powierzyć niczego bardziej skomplikowanego. Friedrich L. Bauer 1.1. Prolog — Painvin ratuje Francję 21 marca 1918 roku o godzinie 4:30 rozpoczął się największy ostrzał artyleryjski I woj- ny światowej. Przez pięć godzin niemieckie działa pluły ogniem na pozycje połączo- nych sił brytyjskich i francuskich. Następnie 62 dywizje niemieckie zalały front na odcinku 60 kilometrów. Dzień po dniu alianci zmuszani byli do wycofywania się i do- piero tydzień później ofensywa została zatrzymana. Do tego czasu wojska niemieckie wbiły się 60 km poza linię frontu. Sukces ten wynikał w dużej mierze z przewagi li- czebnej, jaką dysponowały — po kapitulacji Rosji przerzucono do Francji dywizje do tej pory związane walką na froncie wschodnim. Rozciągnięta linia frontu zmuszała obrońców do znacznego rozproszenia sił, co skwapliwie wykorzystywał generał Erich von Ludendorf. Jego taktyka opierała się na koncentrowaniu dużych sił w jednym punk- cie i atakowaniu z zaskoczenia. Poznanie planów nieprzyjaciela było kluczowe dla skutecznej obrony. Dzięki temu możliwe stałoby się zgromadzenie większych sił na 14 Podstawy kryptografii zagrożonym odcinku frontu. Prowadzono więc intensywny nasłuch radiowy i prze- chwytywano liczne meldunki przesyłane między niemieckimi centrami dowodzenia, problem polegał jednak na tym, iż w większości wyglądały one mniej więcej tak: XAXXF AGXVF DXGGX FAFFA AGXFD XGAGX AVDFA GAXFX GAXGX AGXVF FGAXA… Był to nowy szyfr stosowany przez niemieckie wojska. Nazwano go ADFGX od stoso- wanych liter alfabetu tajnego. Ich wybór nie był przypadkowy. W alfabecie Morse’a różniły się one w istotny sposób, dzięki czemu ewentualne zniekształcenia komunika- tów radiowych były minimalne. Jedynym sukcesem francuskiego wydziału szyfrów na tym etapie było złamanie inne- go niemieckiego systemu, tzw. Schlusselheft. Był to jednak szyfr stosowany głównie do komunikacji między oddziałami w okopach, natomiast naprawdę istotne informacje chronione były przy użyciu ADFGX. Wprowadzenie tego szyfru praktycznie oślepiło francuskie centrum dowodzenia. Najdobitniej świadczą o tym słowa ówczesnego sze- fa francuskiego wywiadu: „Z racji mego stanowiska jestem najlepiej poinformowanym człowiekiem we Francji, a w tej chwili nie mam pojęcia, gdzie są Niemcy. Jak nas dopadną za godzinę, nawet się nie zdziwię”1. Oczywiście Bureau du Chiffre nie pozostawało bezczynne. Zadanie złamania niemiec- kiego szyfru powierzono najlepszemu z francuskich kryptoanalityków — Georges’owi Painvinowi. Jednak nawet on nie był w stanie przeniknąć spowijającej ów szyfr tajem- nicy. Zdołał jedynie ustalić, iż system oparty jest na szachownicy szyfrującej i że klucze zmienia się codziennie. Te informacje mogłyby się na coś przydać, gdyby przechwy- cono większą liczbę zaszyfrowanych depesz. Ta jednak była zbyt skromna i szyfr na- dal pozostawał zagadką. Sytuacja zmieniła się dopiero na początku kwietnia, kiedy Niemcy zwiększyli liczbę przekazów radiowych. W ręce Painvina wpadła większa ilość materiału do badań, co dało nadzieję na uczynienie pierwszych postępów w łamaniu szyfru. Po wstępnej ana- lizie francuski kryptoanalityk zauważył, iż niektóre wiadomości pochodzące z tego samego dnia mają identyczne początki. Założył więc, że są to te same nagłówki mel- dunków zaszyfrowane kluczem dziennym. Pozwoliło mu to wydobyć pierwsze infor- macje na temat konstruowania tego klucza. Następnie posegregował wiadomości na segmenty o takich samych początkach i przesuwając je względem siebie, próbował znaleźć kolejne prawidłowości. Ogromnie pomocne okazało się przechwycenie 18 wia- domości tego samego dnia. Wszystkie były zaszyfrowane tym samym kluczem, dzięki czemu Painvin był w stanie porównać je ze sobą i wyodrębnić stosowane do szyfrowa- nia pary liter (AA, AD, AF itd.). Następnie policzył częstotliwość występowania po- szczególnych par. Najczęściej pojawiała się kombinacja DG. Nasunęło mu to podej- rzenie, iż odpowiadała ona literze e, najczęściej pojawiającej się w języku niemieckim. Udało mu się również ustalić wygląd stosowanej tablicy (rysunek 1.1). 1 Kahn D., Łamacze kodów — historia kryptologii, Wydawnictwa Naukowo-Techniczne, Warszawa 2004. Rozdział 1. ♦ Historia kryptografii 15 Rysunek 1.1. Tablica podstawień szyfru ADFGX ustalona przez Painvina Na niemieckim systemie szyfrowania pojawiła się pierwsza rysa. Był to jednak dopie- ro początek drogi. Teraz należało ustalić współrzędne pozostałych liter. Rozpoczęły się długie dni mozolnej analizy statystycznej przechwyconych kryptogramów. Painvin porównywał częstotliwość występowania pojedynczych liter w parach i na tej podsta- wie dzielił kryptogramy. Przypisał każdej literze dwie współrzędne — górną i boczną — a następnie próbował je ustalić. Opierał się na każdym, najmniejszym nawet strzęp- ku informacji, jaki udało mu się zdobyć: na częstości występowania czy parzystości lub nieparzystości sumy współrzędnych. Mozolnie, litera po literze, zrekonstruował niemiecką tabelę podstawień i był teraz w stanie rekonstruować dzienne klucze nie- mieckich szyfrantów. Przed końcem maja doszedł do takiej wprawy, iż otrzymane wia- domości był w stanie odczytać już po dwóch dniach. I wtedy stało się to, czego naj- bardziej się obawiał. Niemcy zmienili szyfr. Komunikaty niemieckie przechwycone 1 czerwca zawierały dodatkową literę — V. Oznaczało to zmianę wyglądu tabeli szyfrowania i być może całego systemu. Tymcza- sem niemiecka ofensywa trwała. Decydujący atak był kwestią czasu, a Francuzi stra- cili właśnie możliwość przewidzenia, w którym miejscu nastąpi. Po długiej, bezsennej nocy i kolejnym dniu pracy Painvinowi udało się jednak, poprzez porównywanie sta- rych i nowych kryptogramów, odtworzyć szachownicę szyfrowania (rysunek 1.2). Rysunek 1.2. Tablica szyfru ADFGVX Czym prędzej zabrał się do łamania przechwyconych wiadomości i już tego samego dnia udało mu się wysłać pierwsze cenne informacje do sztabu dowodzenia. Mniej wię- cej w tym samym czasie pierwsze pociski z niemieckich dział dalekosiężnych spadły na Paryż… Czasu było coraz mniej. Linia frontu była zbyt długa, by należycie zabezpieczyć wszel- kie możliwe punkty ataku. Należało więc za wszelką cenę zdobyć informację, gdzie Ludendorf zamierza uderzyć. Francuzi wzmocnili nasłuch radiowy i czekali. 3 czerwca udało się przechwycić depeszę z niewielkiego miasteczka Remaugies, opanowanego 16 Podstawy kryptografii przez wojska niemieckie. Po jej odczytaniu okazało się, iż zawiera ona rozkaz przy- słania dużej ilości amunicji. To mogło być to! Ciężki ostrzał artyleryjski przed rozpo- częciem szturmu był powszechną praktyką. Zwiad lotniczy istotnie zaobserwował w ciągu kolejnych dni dużą liczbę ciężarówek na drogach prowadzących do Remaugies. Hipotezę o ataku potwierdzały również informacje od schwytanych jeńców i dezerte- rów. Prawdopodobną datę ataku wyznaczono na 7 czerwca. Nie pozostawało już nic innego, jak tylko wzmocnić odpowiedni odcinek frontu i cze- kać. Wzmocniono obie linie obrony i poinformowano oficerów o zbliżającym się na- tarciu. Wreszcie nadszedł decydujący dzień. W nerwowym oczekiwaniu żołnierze spoglądali w kierunku niemieckich umocnień. Nic się jednak nie działo. Tak upłynął 7 czerwca, a po nim 8. Napięcie rosło. Oczywiście możliwe było pewne opóźnienie ata- ku, a informacje od jeńców mogły być nieścisłe, a jednak… w serca obrońców wkradł się niepokój. Wreszcie o północy 9 czerwca niemieckie działa otworzyły ogień. Fran- cuskie linie były bombardowane przez 3 godziny z niespotykaną dotąd intensywnością. Chwilę później nastąpił atak. Do przodu ruszyło 15 niemieckich dywizji. Kolejnych pięć dni wypełnionych było ciągłą walką o każde miasteczko i ulicę. Niemcy postępowali naprzód, by kolejnego dnia ustępować przed kontratakiem Francuzów. Jeśli jednak ktokolwiek był zaskoczo- ny przebiegiem bitwy, to jedynie generał von Ludendorf. Po raz pierwszy nie udało mu się skoncentrowanym atakiem przełamać linii oporu wroga. Co więcej, wróg od- ważnie kontratakował. W ciągu następnych tygodni próbował jeszcze kolejnych ata- ków, jednak wkrótce zabrakło mu sił. Paryż został ocalony. A wraz z nim Francja. Wkrótce potem w Europie wylądowały siły amerykańskie. Dzięki ich wsparciu alianci byli w stanie przystąpić do kontrofensywy, zmuszając Niemców do odwrotu i osta- tecznie do poddania się. Niemieccy generałowie podpisali akt kapitulacji 11 paździer- nika w miejscowości Compiegne. I wojna światowa została zakończona. A Painvin? Cóż… Painvin pojechał na zasłużony urlop. Po latach, zapytany o historię złamania szyfru ADFGVX, odpowiedział: „Osiągnięcie to pozostawiło niezmywalny ślad na mej duszy i pozostało jednym z najjaśniejszych i najwspanialszych wspomnień w całym moim życiu”2. I trudno mu się chyba dziwić. Nie każdemu dane jest ocalić własny kraj. Przytoczona tu historia stanowi niewątpliwie znakomity materiał na film. Wiele osób może zadziwić to, jak wielki wpływ na losy wojny może mieć jeden człowiek. Oczy- wiście bez odpowiedniej reakcji ze strony dowództwa, odpowiedniego planowania i wykorzystywania zdobytej przewagi, a przede wszystkim bez odwagi i poświęcenia zwykłych żołnierzy, którzy oddali życie za swój kraj, informacje zdobyte przez Pain- vina zostałyby zmarnowane. Z drugiej jednak strony, gdyby nie on, szanse na ocalenie Paryża byłyby nikłe. Upadek stolicy wpłynąłby zaś nie tylko na losy Francji, ale i na wynik całej wojny. 2 Kahn D., Łamacze kodów — historia kryptologii, op.cit. Rozdział 1. ♦ Historia kryptografii 17 Tymczasem z punktu widzenia historii kryptografii przypadek francuskiego kryptoana- lityka nie jest niczym niezwykłym. Historia ta jest pełna opowieści o jemu podobnych, którzy, łamiąc szyfr, decydowali o losach setek, tysięcy lub nawet milionów ludzi. Jed- nak ich osiągnięcia często wychodziły na jaw dopiero po latach, kiedy tajemnice rzą- dowe mogły zostać bezpiecznie ujawnione. Byli więc szarymi eminencjami historii, wpływali na bieg politycznych negocjacji, gry wywiadów czy wreszcie wojen. Wszyst- ko dzięki znakomitemu opanowaniu sztuki „sekretnego pisma” pozwalającej na od- krywanie cudzych tajemnic i zabezpieczanie swoich. Historia kryptografii to opowieść o tych właśnie ludziach. A zatem posłuchajcie… 1.2. Początek… Na początku było pismo. Wykształcone niezależnie w wielu kulturach stanowiło nie- zbadaną tajemnicę dla tych, którzy nie potrafili czytać. Szybko jednak zrodziła się ko- nieczność ukrycia informacji również przed tymi, którym umiejętność ta nie była ob- ca. Najbardziej oczywistym rozwiązaniem było schowanie tajnej wiadomości przed ludźmi, którzy mogliby ją odczytać. Takie zabiegi wkrótce jednak przestały wystar- czać. Wiadomość mogła zostać odnaleziona podczas wnikliwego przeszukania, a wte- dy tajne informacje dostałyby się w ręce wroga. A gdyby udało się napisać list dzia- łający na zasadzie „drugiego dna”? Z pozoru zawierałby on błahe treści, jednak jeśli adresat wiedziałby, gdzie i jak szukać, mógłby dotrzeć do „mniej niewinnych” infor- macji. Tak narodziła się steganografia. 1.2.1. Steganografia Steganografia to ogół metod ukrywania tajnych przekazów w wiadomościach, które nie są tajne. Jej nazwa wywodzi się od greckich słów: steganos (ukryty) oraz graphein (pisać). W przeszłości stosowano wiele wymyślnych sposobów osiągnięcia tego efektu. Popularny niewidzialny atrament to jeden z najbardziej znanych przykładów stegano- grafii. Pierwsze zapiski na temat stosowania tej sztuki znaleźć można już w księgach z V wieku p.n.e. Przykładem może być opisana przez Herodota historia Demaratosa, Greka, który ostrzegł Spartan przed przygotowywaną przeciw nim ofensywą wojsk perskich. Nie mógł on wysłać oficjalnej wiadomości do króla, zeskrobał więc wosk z tabliczki i wyrył tekst w drewnie. Następnie ponownie pokrył tabliczkę woskiem i wręczył posłańcowi. Czysta tabliczka nie wzbudziła podejrzeń perskich patroli i bez- piecznie dotarła do celu. Tam, co prawda, długo głowiono się nad jej znaczeniem, wkrótce jednak żona spartańskiego wodza Leonidasa wpadła na pomysł zeskrobania wosku, co pozwoliło odkryć tajną wiadomość. W miarę postępu technicznego, a także rozwoju samej steganografii, powstawały co- raz wymyślniejsze metody ukrywania wiadomości. Znana jest na przykład metoda ukrywania wiadomości w formie kropki w tekście drukowanym, stosowana podczas II wojny światowej. Wiadomość była fotografowana, a klisza pomniejszana do rozmia- rów około mm2 i naklejana zamiast kropki na końcu jednego ze zdań w liście. Obecnie 18 Podstawy kryptografii bardzo popularne jest ukrywanie wiadomości w plikach graficznych. Kolejne przy- kłady można mnożyć, jednak nawet najbardziej wymyślne z nich nie gwarantują, iż wiadomość nie zostanie odkryta. Koniecznością stało się zatem wynalezienie takiego sposobu jej zapisywania, który gwarantowałby tajność nawet w przypadku przechwy- cenia przez osoby trzecie. 1.2.2. Kryptografia Nazwa kryptografia również wywodzi się z języka greckiego (od wyrazów kryptos — ukryty i graphein — pisać). Jej celem jest utajnienie znaczenia wiadomości, a nie sa- mego faktu jej istnienia. Podobnie jak w przypadku steganografii, data jej powstania jest trudna do określenia. Najstarsze znane przykłady przekształcenia pisma w formę trudniejszą do odczytania pochodzą ze starożytnego Egiptu, z okresu około 1900 roku p.n.e. Pierwsze tego typu zapisy nie służyły jednak ukrywaniu treści przed osobami postronnymi, a jedynie nadaniu napisom formy bardziej ozdobnej lub zagadkowej. Skrybowie zapisujący na ścianach grobowców historie swych zmarłych panów świa- domie zmieniali niektóre hieroglify, nadając napisom bardziej wzniosłą formę. Często celowo zacierali ich sens, zachęcając czytającego do rozwiązania zagadki. Ten ele- ment tajemnicy był ważny z punktu widzenia religii. Skłaniał on ludzi do odczytywa- nia epitafium i tym samym do przekazania błogosławieństwa zmarłemu. Nie była to kryptografia w ścisłym tego słowa znaczeniu, zawierała jednak dwa podstawowe dla tej nauki elementy — przekształcenie tekstu oraz tajemnicę. Na przestrzeni kolejnych 3000 lat rozwój kryptografii był powolny i dosyć nierówny. Powstawała ona niezależnie w wielu kręgach kulturowych, przybierając różne formy i stopnie zaawansowania. Zapiski na temat stosowania szyfrów znaleziono na pocho- dzących z Mezopotamii tabliczkach z pismem klinowym. Ich powstanie datuje się na 1500 rok p.n.e. W II w. p.n.e. grecki historyk Polibiusz opracował system szyfrowa- nia oparty na tablicy przyporządkowującej każdej literze parę cyfr (rysunek 1.3). Rysunek 1.3. Tablica Polibiusza W późniejszych czasach tablica ta stała się podstawą wielu systemów szyfrowania. Przekształcenie liter w liczby dawało możliwość wykonywania dalszych przekształceń za pomocą prostych obliczeń lub funkcji matematycznych. Metodę Polibiusza uzupeł- nioną kilkoma dodatkowymi utrudnieniami kryptoanalitycznymi zastosowała m.in. nie- miecka armia przy opracowywaniu wspomnianego na wstępie systemu szyfrującego ADFGX oraz jego udoskonalonej wersji ADFGVX. Rozdział 1. ♦ Historia kryptografii 19 Pierwsze wzmianki dotyczące stosowania kryptografii w celach politycznych pochodzą z IV w. p.n.e. z Indii. Wymieniana jest ona jako jeden ze sposobów zdobywania infor- macji przez przebywających za granicą ambasadorów. Sekretne pismo wspomniane jest również w słynnej Kamasutrze — figuruje tam jako jedna z 64 sztuk, które kobie- ta powinna znać. Ogólnie stosowane w starożytności metody kryptografii można podzielić na dwa ro- dzaje — przestawianie i podstawianie. W pierwszym przypadku następowała zamiana szyku liter w zdaniach, czyli, innymi słowy, tworzony był anagram. Przykładem szy- frowania przestawieniowego jest pierwsze znane urządzenie szyfrujące — spartańska scytale z V w. p.n.e. Miała ona kształt pręta o podstawie wielokąta, na który nadawca nawijał skórzany pas. Wiadomość pisana była wzdłuż pręta, po czym odwijano pas, na którym widać było tylko pozornie bezsensowną sekwencję liter. Potem goniec prze- nosił list do adresata, stosując czasem steganograficzne sztuczki, na przykład opasując się nim i ukrywając tekst po wewnętrznej stronie. Odczytanie wiadomości było moż- liwe przy użyciu scytale o takiej samej grubości, jaką miał pręt nadawcy. Druga, bardziej popularna metoda polegała na podstawianiu za litery tekstu jawnego innych liter bądź symboli. Za przykład może tu posłużyć szyfr Cezara, najsłynniejszy algorytm szyfrujący czasów starożytnych (jego twórcą był Juliusz Cezar). Szyfr ten opierał się na zastąpieniu każdej litery inną, położoną o trzy miejsca dalej w alfabecie. W ten sposób na przykład wiadomość o treści Cesar przekształca się w Fhvdu. Adre- sat znający sposób szyfrowania w celu odczytania wiadomości zastępował każdą lite- rę tekstu tajnego literą położoną o trzy miejsca wcześniej w alfabecie (rysunek 1.4). Rysunek 1.4. Szyfr Cezara Szyfry przyporządkowujące każdej literze alfabetu jawnego dokładnie jedną literę, kom- binację cyfr lub symbol nazywamy szyframi monoalfabetycznymi. W przypadku szy- fru Cezara układ alfabetu tajnego zawsze pozostawał ten sam. Znacznie bezpieczniej- szym rozwiązaniem było dokonywanie w nim okresowych zmian tak, aby znajomość metody szyfrowania nie wystarczała do odczytania wiadomości. Stanowiło to jednak utrudnienie również dla adresata. Musiał on dodatkowo posiadać klucz (układ liter lub symboli w alfabecie tajnym). Tak powstał największy problem w historii kryptografii — dystrybucja klucza. Raz przechwycony klucz stawał się bez- użyteczny, gdyż wiadomości szyfrowane za jego pomocą nie były już bezpieczne. O ile w przypadku wymiany wiadomości między dwiema osobami nie była to z reguły du- ża przeszkoda (wystarczyło ustalić nowy klucz), o tyle w przypadku szyfrowania na potrzeby wojskowe rodziło to bardzo wiele problemów. Trzeba było dostarczyć nowy klucz do wszystkich jednostek i to możliwie szybko, gdyż każda przechwycona przez wroga wiadomość stawała się dla niego łatwa do odczytania. 20 Podstawy kryptografii 1.2.3. Narodziny kryptoanalizy Kolebką kryptoanalizy były państwa arabskie, które najlepiej opanowały sztukę lingwi- styki i statystyki, na nich bowiem opierała się technika łamania szyfrów monoalfabe- tycznych. Najwcześniejszy jej opis znajduje się w pracy Al-Kindiego, uczonego z IX wieku, znanego jako „filozof Arabów” (napisał on 29 prac z dziedziny medycyny, astro- nomii, matematyki, lingwistyki i muzyki). Jego największy traktat, O odczytywaniu zaszyfrowanych listów, został odnaleziony w 1987 roku w Archiwum Ottomańskim w Stambule. W pracy tej Al-Kindi zawarł szczegółowe rozważania na temat statystyki fonetyki i składni języka arabskiego oraz opis opracowanej przez siebie techniki po- znawania tajnego pisma. To jeden z pierwszych udokumentowanych przypadków za- stosowania ataku kryptoanalitycznego. Pomysł arabskiego uczonego był następujący: „Jeden sposób na odczytanie zaszyfrowanej wiadomości, gdy wiemy, w jakim języku została napisana, polega na znalezieniu innego tekstu w tym języku, na tyle długiego, by zajął mniej więcej jedna stronę, i obliczeniu, ile razy występuje w nim każda litera. Literę, która występuje najczęściej, będziemy nazywać »pierwszą«, następną pod względem częstości występowania »drugą« i tak dalej, aż wyczerpiemy listę wszystkich liter w próbce jawnego tekstu. Następnie bierzemy tekst zaszyfrowany i również klasyfikujemy użyte w nim symbo- le. Znajdujemy najczęściej występujący symbol i zastępujemy go wszędzie „pierwszą” literą z próbki jawnego tekstu. Drugi najczęściej występujący symbol zastępujemy „drugą” literą, następny „trzecią” i tak dalej, aż wreszcie zastąpimy wszystkie symbo- le w zaszyfrowanej wiadomości, którą chcemy odczytać”3. Opisana powyżej metoda znana jest jako analiza częstości i po dziś dzień stanowi pod- stawową technikę kryptoanalityczną. Każdy język posiada własną charakterystykę wy- stępowania poszczególnych liter w piśmie, zawsze jednak pewne znaki pojawiają się częściej niż inne. Na tej podstawie kryptoanalityk może zidentyfikować te litery w kryp- togramie. To z kolei pozwala odgadnąć niektóre ze znajdujących się w tajnym piśmie wyrazów, dzięki czemu rozszyfrowuje się kolejne litery itd. Wszystko opiera się tutaj w dużej mierze na prawdopodobieństwie, gdyż najczęściej występujący w kryptogra- mie znak wcale nie musi być literą najczęściej występującą w danym języku. Niemniej jednak znajomość tej metody pozwalała znacznie zredukować liczbę możliwych pod- stawień i osiągnąć rozwiązanie metodą prób i błędów. Należy tu podkreślić, że jeśli mamy do czynienia z jedną krótką wiadomością, anali- za częstości występowania znaków może dać fałszywe wyniki (w tych kilku konkret- nych zdaniach najczęściej pojawiającą się literą może być na przykład czternasta pod względem częstości występowania w danym języku) i utrudnić dekryptaż. Stąd też im dłuższy jest zaszyfrowany tekst, tym większa szansa na złamanie szyfru. Dzięki wynalazkowi Al-Kindiego monoalfabetyczne systemy szyfrujące przestały być bezpieczne. Od tej chwili rozpoczął się trwający do dziś wyścig kryptografów z kryp- toanalitykami. 3 Singh S., Księga szyfrów, Albatros, Warszawa 2001, s. 31. Rozdział 1. ♦ Historia kryptografii 21 1.3. Rozwój kryptografii i kryptoanalizy Jeszcze wiele lat po odkryciu Al-Kindiego liczni uczeni negowali możliwość złama- nia szyfru podstawieniowego. Szybko jednak metody kryptoanalityczne rozprzestrze- niły się z Bliskiego Wschodu na Europę. W średniowieczu nie dokonał się większy postęp w europejskiej kryptologii. Szyfry znane były mnichom i skrybom, a i ci nie traktowali ich jako odrębnej nauki, a jedynie jako rodzaj intelektualnej rozrywki. Aż do początków XV wieku używano wyłącznie szyfrów podstawieniowych. Popularne były również tzw. nomenklatory. Było to połączenie szyfru podstawieniowego z ko- dem — oprócz klasycznego alfabetu tajnego nomenklator zawierał listę słów i ich od- powiedników kodowych. Prawdziwy rozkwit technik szyfrowania nastąpił równolegle z rozwojem i umacnianiem stosunków dyplomatycznych między europejskimi pań- stwami. Ambasadorowie, pełniący jednocześnie rolę szpiegów na obcych dworach, po- trzebowali sposobu na bezpieczne przekazywanie tajnych informacji. Z tych samych powodów wzrosło zainteresowanie kryptoanalizą. W związku z dokonanymi w tej dzie- dzinie postępami szyfry monoalfabetyczne nie były już bezpieczne, zaczęto więc opra- cowywać nowe metody szyfrowania. 1.3.1. Szyfry homofoniczne Jedną z najbardziej znanych metod jest szyfrowanie z użyciem homofonów. Miało ono zabezpieczyć szyfr przed atakiem z użyciem analizy częstości. Pierwszy znany przy- kład szyfru homofonicznego pochodzi z roku 1401. W szyfrach takich alfabet tekstu tajnego wzbogacano o pewne dodatkowe symbole, które następnie przypisywano naj- częściej występującym w alfabecie tekstu jawnego literom. I tak, jeśli częstość wystę- powania danej litery wynosiła 7 , przypisywano jej 7 różnych symboli. W ten sposób każdy znak tekstu tajnego pojawiał się w wiadomości z taką samą częstością. Mogło- by się wydawać, że od tej chwili tajne wiadomości pozostaną nieodczytane. Nic bar- dziej mylnego. Częstość występowania liter nie jest jedyną charakterystyką języka. Istnieją również liczne powiązania między literami, takie jak częstość pojawiania się określonych par i trójek. Poszczególne wyrazy w języku również charakteryzują się określoną często- tliwością występowania. Dzięki takim prawidłowościom możliwa jest kryptoanaliza szyfrów homofonicznych poprzez wyszukiwanie tzw. częściowych powtórzeń. Za- łóżmy dla przykładu, iż szyfrowanie opiera się na podstawianiu par cyfr zamiast liter. Literom o większej częstości występowania przypisana jest większa liczba kombina- cji dwucyfrowych. Tak skonstruowany szyfr można złamać przy odpowiedniej ilości materiału do badań. Wystarczy wyszukać w tekście podobne kombinacje znaków, na przykład: 67 55 10 23 i 67 09 10 23. Z dużą dozą prawdopodobieństwa założyć można, iż odpowiadają one tym samym wyrazom. Dzięki temu łatwo zidentyfikować zestawy cyfr odpowiadające tej samej literze (w naszym przykładzie — 55 i 09). Po odtworze- niu odpowiedniej liczby takich powiązań szyfr złamać można tradycyjną metodą ana- lizy częstości. Zaczęto więc udoskonalać szyfry homofoniczne, aby uodpornić je na tego typu kryptoanalizę. 22 Podstawy kryptografii Bardzo wiele usprawnień w szyfrowaniu wprowadziła włoska rodzina Argentich. W XVI i XVII wieku jej członkowie pracowali dla kolejnych papieży, służąc im swoją bogatą wiedzą kryptologiczną. Na początku XVII wieku wprowadzili liczne udoskonalenia w stosowanych wówczas technikach szyfrowania. Przede wszystkim stosowali symbole puste w każdym wierszu kryptogramu. Zlikwi- dowali również rozdzielanie wyrazów i zapisywanie znaków interpunkcyjnych. Na- wet cyfry odpowiadające poszczególnym literom zapisywali razem, mieszając często liczby jedno- i dwucyfrowe. Dzięki tym zabiegom problem pojawiał się już na etapie podziału tekstu tajnego na pojedyncze znaki. Oczywiście, złamanie szyfru nadal było możliwe, jednak zadanie to było znacznie trudniejsze niż w przypadku zwykłego szy- fru homofonicznego. Symbol pusty — znak alfabetu tajnego nieposiadający odpowiednika w alfabecie jawnym. Adresat wiadomości podczas dekryptażu ignoruje takie znaki, natomiast dla kryptoanalityka są one dodatkowym utrudnieniem. 1.3.2. Szyfry polialfabetyczne Szyfry polialfabetyczne opisać można jako połączenie wielu szyfrów monoalfabetycz- nych. Mają wiele alfabetów tajnych, z których każdy szyfruje jeden znak tekstu tajne- go. Używane są cyklicznie, a więc po wyczerpaniu wszystkich powraca się do pierw- szego i kontynuuje szyfrowanie. Prawdopodobnie pierwszym zastosowanym szyfrem polialfabetycznym był szyfr Albertiego, włoskiego architekta z XV wieku. 1.3.2.1. Tarcza Albertiego Urodzony w roku 1404 Leone Battista Alberti był człowiekiem niezwykle wszechstron- nym — komponował, malował, pisał, zajmował się aktorstwem, architekturą, prawem. Kryptografią zainteresował się dosyć późno, bo dopiero w roku 1466, za namową Leo- nardo Dato — ówczesnego papieskiego sekretarza. Alberti napisał obszerną rozprawę o tematyce kryptologicznej. Obejmowała ona za- równo zagadnienia kryptoanalizy, jak i metodologii tworzenia nowych szyfrów. Archi- tekt opisał w niej również swój własny szyfr i stwierdził, iż nikt nie będzie w stanie go złamać. Szyfr ten opierał się na urządzeniu zaprojektowanym przez niego samego. Składało się ono z dwóch okrągłych tarcz (rysunek 1.5). Jedna z nich zawierała się wewnątrz drugiej, na obu zaś, na osobnych polach, wypisa- ne były litery alfabetu. Szyfrowanie polegało na zastępowaniu liter z małej tarczy lite- rami znajdującymi się na odpowiadających im polach dużej. Wszystko to tworzyło- by jedynie prosty szyfr monoalfabetyczny, gdyby nie fakt, iż wewnętrzna tarcza była ruchoma. Obracając ją, szyfrujący zmieniał przypisania wszystkich używanych liter, tym samym wybierając nowy alfabet szyfrowy. Oczywiście osoby prowadzące zaszy- frowaną korespondencję przy użyciu tarczy Albertiego muszą posiadać jej identyczne egzemplarze i ustalić początkową pozycję wewnętrznej tarczy względem zewnętrznej. Rozdział 1. ♦ Historia kryptografii 23 Rysunek 1.5. Tarcza Albertiego Źródło: Kahn D., Łamacze kodów — historia kryptologii, op.cit. Dodatkowo włoski architekt umieścił na zewnętrznej tarczy cyfry od 1 do 4, co umoż- liwiało wstawianie do wiadomości słów kodowych (na przykład nazwy własne mogły być zastępowane kombinacjami cyfr). W połączeniu z wynalezieniem szyfru polialfa- betycznego i dokonaniem pierwszego na Zachodzie opisu kryptoanalizy stanowiło to niebywałe osiągnięcie, zwłaszcza jak na człowieka, który kryptografią zajmował się raptem kilka lat. Osiągnięcia Albertiego zyskały mu miano ojca kryptologii Zachodu. Szyfrowanie z użyciem wielu alfabetów stanowiło wielki przełom, jednak stosowanie w tym celu urządzenia szyfrującego powodowało pewne niedogodności. Pół wieku później zupełnie inny sposób wykorzystania techniki szyfrowania polialfabetycznego zaproponował niemiecki uczony Johannes Trithemius. 1.3.2.2. Tabula recta Trithemius urodził się 2 lutego 1462 roku w Trittenheim w Niemczech. W wieku 17 lat rozpoczął studia na uniwersytecie w Heidelbergu, gdzie szybko zdobył uznanie dzię- ki swemu niebywałemu intelektowi. Mając lat dwadzieścia, przez przypadek trafił do opactwa benedyktynów. Życie mnichów zafascynowało go do tego stopnia, iż posta- nowił rozpocząć nowicjat. Niecałe dwa lata później wybrany został opatem. Oprócz sprawowania swego nowego stanowiska Trithemius zajmował się pisaniem książek. Pierwsza z nich została opublikowana, kiedy miał 24 lata. Pisał opowieści, słowniki, biografie, kroniki oraz kazania. Prowadził też bogatą korespondencję z in- nymi uczonymi. W roku 1499 rozpoczął pisanie książki pt. Steganographia. Opisy- wała ona znane metody szyfrowania. Tak naprawdę jednak w książce tej więcej było okultyzmu i czarnej magii niż kryptografii. Trithemius nie ukrywał swej fascynacji praktykami magicznymi i lubił uchodzić za cudotwórcę. Ze zrozumiałych względów kościelni zwierzchnicy zdecydowanie potępiali postępowanie opata i ostatecznie nie ukończył on swojej książki. 24 Podstawy kryptografii W roku 1508 Trithemius powrócił do tematyki kryptologicznej, tym razem traktując temat bardziej naukowo. Jego kolejna książka — Poligraphia — skupiała się wyłącz- nie na zagadnieniach czysto kryptograficznych. Ukazała się ona dopiero w roku 1518, dwa lata po śmierci uczonego. Była to pierwsza książka na temat kryptologii wydana drukiem. Jej tytuł brzmiał: Sześć ksiąg o poligrafii przez Johannesa Trithemiusa, opa- ta w Wurzburgu, poprzednio w Spanheim, dla cesarza Maksymiliana. Książka zawie- rała głównie kolumny słów używanych przez Trithemiusa w jego systemach krypto- graficznych. W księdze piątej znajdował się jednak opis nowego systemu szyfrowania polialfabetycznego. Opierał się on na specjalnej tabeli nazwanej przez Trithemiusa tabula recta. Przedstawia ją rysunek 1.6. Rysunek 1.6. Tabela Trithemiusa Na samej górze tabeli umieszczono alfabet tekstu tajnego. Kolejne linijki to tajne alfa- bety utworzone przez przenoszenie kolejnych liter z początku alfabetu na jego koniec. W ten sposób Trithemius uzyskał 26 alfabetów szyfrowych. Szyfrowanie tą metodą przebiega następująco: dla pierwszej litery tekstu jawnego uży- wa się pierwszej linijki tabeli, dla drugiej litery — drugiej linijki itd. Pozwala to na zabezpieczenie tekstu przed atakiem przez analizę częstości. Jednak, podobnie jak w przypadku szyfru Cezara, nie chroni to przed odszyfrowaniem w przypadku, gdy kryptoanalityk zna stosowany algorytm. Próbą rozwiązania tego problemu był opubli- kowany w 1586 roku szyfr Vigenere’a. Rozdział 1. ♦ Historia kryptografii 25 1.3.2.3. Le chiffre indechiffrable Blaise de Vigenere urodził się 5 kwietnia 1523 roku we Francji. W wieku 23 lat roz- począł karierę dyplomatyczną na dworze w Wormancji. Podróżował po całej Europie i rok później został przyjęty na służbę u księcia de Nevers. W roku 1549, podczas mi- sji dyplomatycznej w Rzymie, Vigenere po raz pierwszy zetknął się z kryptografią. Ogromnie zafascynowany sztuką „tajnego pisma” oddał się studiowaniu książek naj- większych kryptologów oraz własnym badaniom. Miał również możliwość współpra- cy z najwybitniejszymi ekspertami kurii papieskiej, co pozwoliło mu znacznie pogłę- bić wiedzę. Dzięki niej i bogatemu doświadczeniu został sekretarzem samego króla. W końcu, w wieku 47 lat postanowił opuścić dwór i zająć się pisaniem książek. W roku 1586 Vigenere opublikował Traktat o szyfrach. Podobnie jak w dziele Trithe- miusa, tak i tutaj znajdują się liczne dygresje na tematy zupełnie niezwiązane z krypto- grafią, za to jak najbardziej związane z czarną magią. Autor zachował mimo to nauko- wą solidność w tych fragmentach książki, które w ogóle miały coś z nauką wspólnego. Opisał również własny szyfr polialfabetyczny. System opracowany przez Vigenere’a polegał na szyfrowaniu kolejnych liter wiado- mości za pomocą różnych wierszy tablicy Trithemiusa. Różnica polegała na sposobie wyboru kolejnego wiersza szyfrującego. Dla pierwszej litery mógł to być wiersz 17., dla drugiej — 5., dla trzeciej — 13. itd. W ten sposób znajomość samego systemu prze- stawała wystarczać do odszyfrowania wiadomości. Trzeba było jeszcze znać kombina- cję wierszy zastosowaną w danym przypadku. Nadawca i odbiorca mogli sobie ułatwić zapamiętanie tej kombinacji, ustalając specjalne słowo-klucz. Jego litery stanowiły jednocześnie pierwsze litery kolejno stosowanych wierszy szyfrowania. Dla przykła- du, słowo kluczowe sekret oznaczało, iż do zaszyfrowania pierwszej litery wiadomo- ści zastosowano 19. wiersz tabeli, dla drugiej — 5., dla trzeciej — 11. itd. Znajomość słowa-klucza wystarczała adresatowi do odszyfrowania wiadomości. Odszukiwał on kolejne litery szyfrogramu w odpowiadających im linijkach tabeli, po czym odczyty- wał literę tekstu jawnego z linijki znajdującej się na samej górze. Vigenere stworzył również dwa systemy szyfrowania oparte na koncepcji autoklucza. W pierwszym przypadku kluczem stawał się odszyfrowywany tekst jawny. Konieczna była jedynie znajomość pojedynczej litery, stanowiącej tzw. klucz pierwotny. Dzięki niej adresat odczytywał pierwszą literę tekstu jawnego, którą wykorzystywał do od- czytania drugiej itd. Drugi system z autokluczem również wykorzystywał klucz pierwotny. Tutaj jednak po zaszyfrowaniu pierwszej litery tekstu jawnego jej odpowiednik w kryptogramie stawał się kolejną literą klucza. Obie metody były znacznie bardziej innowacyjne i błyskotli- we niż opracowany przez Vigenere’a szyfr polialfabetyczny, jednak z niewiadomych przyczyn uległy zapomnieniu, a z nazwiskiem francuskiego uczonego kojarzony jest głównie szyfr oparty o tabelę Trithemiusa. Warto również zaznaczyć, iż koncepcja au- toklucza została pierwotnie opisana przez włoskiego matematyka Girolamo Cardano, jednak opracowany przez niego system był pełen niedoskonałości i dopiero udosko- nalenia wprowadzone przez Vigenere’a pozwalały na wykorzystanie tej metody przy szyfrowaniu wiadomości. 26 Podstawy kryptografii Szyfr Vigenere’a przez bardzo długi czas uchodził za niemożliwy do złamania. Zyskał nawet przydomek le chiffre indechiffrable (pol. szyfr nieodszyfrowywalny). Został zła- many dopiero w XIX wieku przez brytyjskiego uczonego Charlesa Babbage’a. 1.3.2.4. Złamanie szyfru „nie do złamania” Charles Babbage urodził się w roku 1792. Pochodził z bogatej rodziny (jego ojciec był bankierem), co pozwoliło mu na rozwijanie różnorodnych zainteresowań, w tym tych dotyczących kryptografii. Już jako dziecko zdradzał wyjątkowy talent w tej dziedzinie, przez co nieraz wpadał w kłopoty — łamał szyfry swoich szkolnych kolegów, a ci w rewanżu spuszczali mu lanie. Wraz z upływem lat rozwijał swoje umiejętności, aż stał się znany w całej Anglii. Często pomagał w przygotowywaniu materiału dowodo- wego w prowadzonych sprawach sądowych poprzez odszyfrowywanie koresponden- cji z nimi związanej. W roku 1854 zainteresował się problemem kryptoanalizy szyfru Vigenere’a. Nie przejmując się opiniami, jakoby szyfr ten był nie do złamania, rozpo- czął poszukiwanie punktu zaczepienia, który pozwoliłby na skuteczną kryptoanalizę. Jeszcze w tym samym roku dokonał przełomowego odkrycia. Babbage zauważył mianowicie, że jeśli pozna się długość użytego słowa-klucza, roz- szyfrowanie tekstu będzie o wiele łatwiejsze, gdyż będzie wtedy wiadomo, które lite- ry zaszyfrowane są przy użyciu takich samych podstawień. Na przykład jeśli słowo kluczowe ma 5 liter, to co piąta litera tekstu jest szyfrowana przy użyciu identycznego alfabetu. Wystarczy zatem podzielić tekst na grupy liter szyfrowane tą samą literą klu- cza i dokonać kryptoanalizy opartej na analizie częstości. Grupy te są bowiem niczym innym, jak prostym szyfrem podstawieniowym. Oczywiście, kryptoanalityk nie zna długości klucza, informację tę można jednak zdo- być podczas badania kryptogramu. Przy dłuższych tekstach często zdarzają się bowiem powtórzenia wyrazów lub ich fragmentów szyfrowane tym samym fragmentem klucza. W takiej sytuacji w kryptogramie wystąpią powtarzające się kombinacje liter. Analizu- jąc odległości między nimi, ustalić można najbardziej prawdopodobną długość klu- cza. Z reguły jest nią jeden ze wspólnych dzielników tych odległości. Jeśli zatem udało nam się wyodrębnić cztery takie przypadki, a odstępy wynoszą 8, 16, 20 i 23 litery, to możemy z dużą dozą prawdopodobieństwa przyjąć, iż długość klucza wynosi cztery. Czasem powtórzenie może być dziełem przypadku, a nie synchronizacji klucza i tek- stu, dlatego też ostatnią wartość (23) można zignorować. Zawsze jednak warto odszu- kać jak najwięcej powtórzeń, gdyż dzięki temu uzyskujemy większą ilość materiału do analizy, a co za tym idzie — większą pewność co do wyznaczonej długości klucza. Technika zastosowana przez Babbage’a została rozwinięta i usystematyzowana przez pruskiego wojskowego, Friedricha W. Kasickiego. W swojej książce Die Geheimschrif- ten und die Dechiffrir-kunst (Tajne pisma i sztuka deszyfracji) szczegółowo opisał on metodykę łamania polialfabetów, począwszy od wyznaczania okresu klucza, a na ana- lizie wyodrębnionych szyfrów monoalfabetycznych skończywszy. Książka stała się znana dopiero po jego śmierci w roku 1881 roku, a opracowaną metodę ochrzczono mianem analizy Kasickiego. Rozdział 1. ♦ Historia kryptografii 27 1.3.3. Szyfry digraficzne Szyfr digraficzny opiera się na szyfrowaniu par znaków. Tekst jawny dzielony jest na pary znaków, a następnie przekształcany w kryptogram według ustalonego wzoru. Każ- dy symbol w kryptogramie jest więc zależny od dwóch liter tekstu jawnego, co utrud- nia złamanie szyfru. Szyfry digraficzne zaliczyć można do szerszej grupy szyfrów wie- loliterowych (operujących na grupach liter). Pierwszy znany szyfr digraficzny pochodzi z dzieła De Furtivis Literarum Notis autor- stwa Giovanniego Battisty Porty — włoskiego uczonego z XVI wieku. Zawierało ono opis znanych ówcześnie szyfrów, lingwistycznych aspektów kryptografii, technik kryp- toanalitycznych oraz autorskie propozycje technik szyfrowania. Autor umieścił w nim również liczne cenne wskazówki dotyczące zarówno szyfrowania, jak i łamania szy- frów. To Porta jako pierwszy wpadł na pomysł kryptoanalizy opartej o prawdopodo- bieństwo występowania słów w tekście. Mówiąc najogólniej, kryptoanalityk znający przeznaczenie danej wiadomości może spróbować odszukać w tekście wyraz często występujący w tekstach o takim charakterze. Na przykład dla meldunku wojskowego mogą to być wyrazy atak, wróg, dowódca itp. Co ciekawe, Porta nie podzielał powszechnej opinii, jakoby szyfry polialfabetyczne były nie do złamania. Przypuścił wiele ataków na znane wówczas polialfabety i był bardzo blisko sukcesu. W jednym przypadku udało mu się na podstawie występują- cych powtórzeń określić długość klucza, jednak nie zrobił z tej informacji żadnego użytku. W rezultacie szyfry polialfabetyczne uznawane były za bezpieczne przez ko- lejnych 300 lat. Pierwszym w historii literowym szyfrem digraficznym był szyfr Playfaira, nazwany tak od nazwiska angielskiego uczonego epoki wiktoriańskiej. Nazwa ta przylgnęła do tego szyfru, mimo iż tak naprawdę jego autorem był inny uczony, Charles Wheatstone. Obaj panowie byli jednak do siebie łudząco podobni, przez co notorycznie ich ze sobą m
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Podstawy kryptografii. Wydanie II
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: