Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00360 008375 11063048 na godz. na dobę w sumie
Sekrety kryptografii - książka
Sekrety kryptografii - książka
Autor: Liczba stron: 544
Wydawca: Helion Język publikacji: polski
ISBN: 83-7197-960-6 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> hacking >> kryptografia
Porównaj ceny (książka, ebook, audiobook).
Kryptologia, przez tysiąclecia nazywana 'nauką tajemną', gwałtownie nabiera praktycznego znaczenia w systemach zabezpieczeń kanałów komunikacyjnych, baz danych i oprogramowania. Pełni ona ważną rolę w skomputeryzowanych systemach informacyjnych (systemy kluczy publicznych). W systemach komputerowych oraz sieciowych pojawia się coraz więcej możliwych zastosowań kryptologii związanych z prawami dostępu i ochroną plików źródłowych.

Pierwsza część niniejszej książki dotyczy kryptografii czyli tajnych kodów oraz sposobów ich wykorzystania. Część druga poświęcona jest kryptoanalizie, czyli procesowi deszyfrowania tajnych kodów; zawiera także porady dotyczące metod dostępu (assessing methods). Od czytelnika wymagana jest jedynie podstawowa wiedza z zakresu matematyki. Książka zawiera wiele ciekawych, zabawnych, a czasem osobistych opowieści z historii kryptologii, które sprawią, że zainteresuje ona także osoby nie zajmujące się kryptologią profesjonalnie.

'Sekrety kryptografii' to klasyka z dziedziny kryptologii. Niniejsze trzecie wydanie zostało poprawione i uzupełnione o wiele technicznych i bibliograficznych szczegółów.

'Najlepsza obecnie pozycja na temat kryptologii.'
- David Kahn, Cryptologia

'Książka niniejsza to niezbędna pozycja dla tych, którzy zajmują się kryptologią. Natomiast amatorom może posłużyć jako ważny leksykon, który w wielu przypadkach pokaże im, jak uczynić szyfry bezpieczniejszymi.'
- Arne Fransén, International Intelligence History Study Group

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

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI Sekrety kryptografii KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Autor: John Paul Mueller T³umaczenie: Bart³omiej Garbacz Tomasz Wasilewski ISBN: 83-7197-960-6 Tytu³ orygina³u: Decrypted Secrets Format: B5, stron: 536 Kryptologia, przez tysi¹clecia nazywana „nauk¹ tajemn¹”, gwa³townie nabiera praktycznego znaczenia w systemach zabezpieczeñ kana³ów komunikacyjnych, baz danych i oprogramowania. Pe³ni ona wa¿n¹ rolê w skomputeryzowanych systemach informacyjnych (systemy kluczy publicznych). W systemach komputerowych oraz sieciowych pojawia siê coraz wiêcej mo¿liwych zastosowañ kryptologii zwi¹zanych z prawami dostêpu i ochron¹ plików ĥród³owych. Pierwsza czêġæ niniejszej ksi¹¿ki dotyczy kryptografii czyli tajnych kodów oraz sposobów ich. Czêġæ druga poġwiêcona jest kryptoanalizie, czyli procesowi deszyfrowania tajnych kodów; zawiera tak¿e porady dotycz¹ce metod dostêpu (assessing methods). Od czytelnika wymagana jest jedynie podstawowa wiedza z zakresu matematyki. Ksi¹¿ka zawiera wiele ciekawych, zabawnych, a czasem osobistych opowieġci z historii kryptologii, które sprawi¹, ¿e zainteresuje ona tak¿e osoby nie zajmuj¹ce siê kryptologi¹ profesjonalnie. „Sekrety kryptografii” to klasyka z dziedziny kryptologii. Niniejsze trzecie wydanie zosta³o poprawione i uzupe³nione o wiele technicznych i bibliograficznych szczegó³ów. „Najlepsza obecnie pozycja na temat kryptologii.” David Kahn, Cryptologia „Ksi¹¿ka niniejsza to niezbêdna pozycja dla tych, którzy zajmuj¹ siê kryptologi¹. Natomiast amatorom mo¿e pos³u¿yæ jako wa¿ny leksykon, który w wielu przypadkach poka¿e im, jak uczyniæ szyfry bezpieczniejszymi.” Arne Fransén, International Intelligence History Study Group Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Spis tre·sci Cz(cid:8)e·s·c I . Kryptogra(cid:2)a . . . . 1. 1.1. 1.2. 1.3. 1.4. Wskaz(cid:243)wki . . . . 1.5. 1.6. 1.7. Streszczenie wst(cid:8)epne Kryptogra(cid:2)a i steganogra(cid:2)a . . Semagramy . . . . . . . Kod jawny: maskowanie . . . . . . . . . . . . . . . . . . . . . . . . Kod jawny: woalowanie za pomoc (cid:8)a warto·sci zerowych . Kod jawny: woalowanie za pomoc (cid:8)a kratki . . . . . . . . . Klasy(cid:2)kacja metod kryptogra(cid:2)cznych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cele i metody kryptogra(cid:2)i 2. 2.1. Natura kryptogra(cid:2)i . . . 2.2. . . . . 2.3. 2.4. 2.5. 2.6. . . . . Szyfrowanie . . . . . . . Systemy kryptogra(cid:2)czne (kryptosystemy) . . . . . Polifonia . . . . . . . . . Zbiory znak(cid:243)w . Klucze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. 3.1. 3.2. 3.3. 3.4. Kroki szyfrowania: podstawienie proste Przypadek V (1) (cid:0)(cid:0)! W (jednodzielne podstawienia proste) . . . . . . . . Przypadek szczeg(cid:243)lny V (cid:0)(cid:0)(cid:0)! V (permutacje) . . . . . . Przypadek V (1) (cid:0)(cid:0)! Wm (wielodzielne podstawienia proste) . . . . Przypadek og(cid:243)lny V (1) (cid:0)(cid:0)! W(m) (rozstawianie) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 23 . . 23 . . 24 . . 28 . . 31 . . 33 . . 38 . . 39 41 . . 41 . . 47 . . 49 . . 52 . . 54 . . 56 59 . . 59 . . 61 . . 68 . . 71 8 Spis tre´sci . . . . 4. 4.1. 4.2. 4.3. 4.4. Kroki szyfrowania: podstawienie i kodowanie poligra(cid:2)czne Przypadek V 2 (cid:0)(cid:0)! W(m) (podstawienie dwuznakowe) . . . . . . . Przypadek szczeg(cid:243)lny Playfaira i Delastelle’a: metody tomogra(cid:2)czne . . . . Przypadek V 3 (cid:0)(cid:0)! W(m) (podstawienie tr(cid:243)jznakowe) . . . . . . . . . . . . . Przypadek og(cid:243)lny V (n) (cid:0)(cid:0)! W(m): kody . Kroki szyfrowania: podstawienie liniowe 5. Samoodwrotne podstawienia liniowe . . . 5.1. . . . . Jednorodne podstawienia liniowe . . 5.2. . . . . . . . 5.3. Binarne podstawienia liniowe . 5.4. Og(cid:243)lne podstawienia liniowe . . . . . . . . . . . . Roz(cid:7)o(cid:1)zone podstawienia liniowe . . 5.5. 5.6. Alfabety dziesi (cid:8)atkowane . . . . . . . . . . . 5.7. . . . . . . . . . . . . . . . . . . . . . . . . Podstawienia liniowe dla liczb dziesi(cid:8)etnych i binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kroki szyfrowania: transpozycja 6. 6.1. Najprostsze metody . . . 6.2. 6.3. Anagramy . . . . . . . . Transpozycja kolumnowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Szyfrowanie polialfabetyczne: rodziny alfabet(cid:243)w . . . . Podstawienia iterowane . . . . . . . . . . . . 7. 7.1. . . . 7.2. Alfabety przesuni(cid:8)ete i obr(cid:243)cone . . . 7.3. . . . 7.4. 7.5. Alfabety niezale(cid:1)zne . . . . . . . . . . . . . . . Rotorowe maszyny szyfruj (cid:8)ace . Przesuni(cid:8)ete alfabety standardowe: VigenŁre i Beaufort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Szyfrowanie polialfabetyczne: klucze . . . . Klucz podw(cid:243)jny . . . . . . . . . Szyfrowanie Vernama . . Klucze pseudonieokresowe . . 8. . . . . 8.1. Wczesne metody z kluczami okresowymi . . . . 8.2. . . . . 8.3. 8.4. . . . . 8.5. Maszyny generuj (cid:8)ace w(cid:7)asny ci (cid:8)ag znak(cid:243)w klucza . 8.6. Zewn(cid:8)etrzne tworzenie ci (cid:8)ag(cid:243)w znak(cid:243)w klucza . . . . . . Klucze nieokresowe . . . 8.7. 8.8. Klucze jednorazowe . . . . . . . 8.9. Negocjowanie kluczy i zarz (cid:8)adzanie kluczami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 . . 75 . . 81 . . 85 . . 85 99 . . 101 . . 102 . . 106 . . 106 . . 107 . . 110 . . 110 113 . . 113 . . 117 . . 121 125 . . 125 . . 126 . . 130 . . 138 . . 141 151 . . 151 . . 153 . . 154 . . 156 . . 158 . . 168 . . 170 . . 173 . . 176 Spis tre´sci . . . . . . . . . . . . Sk(cid:7)adanie klas metod . . . . . . . . . . . Przeszyfrowywanie . . . . . . . . . . Podobie·nstwo metod szyfrowania . . . . . (cid:132)Przekszta(cid:7)cenie piekarza(cid:148) Shannona . . . 9. . . . . 9.1. Grupy . . . . . . . 9.2. . . . . 9.3. 9.4. . . . . 9.5. Mieszanie i rozpraszanie za pomoc (cid:8)a operacji arytmetycznych . . . . 9.6. DES i IDEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Systemy z jawnym kluczem szyfruj (cid:8)acym 10. 10.1. Symetryczne i asymetryczne metody szyfrowania . . . . . . . 10.2. Funkcje jednokierunkowe . . . . . . . . . . . 10.3. Metoda RSA . . . . . . . . . . 10.4. Kryptoanalityczny atak na RSA . . . . . . . 10.5. Poufno·s·c a uwierzytelnianie . . . . . . . . . 10.6. Bezpiecze·nstwo system(cid:243)w z kluczem publicznym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bezpiecze ·nstwo szyfrowania 11. . . . 11.1. B(cid:7)(cid:8)edy kryptogra(cid:2)czne . . . . 11.2. Zasady kryptologii . . . 11.3. Kryteria Shannona . . . . . . 11.4. Kryptologia a prawa cz(cid:7)owieka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cz(cid:8)e·s·c II . Kryptoanaliza 12. 12.1. Monoalfabetyczne podstawienie proste . . . . . . 12.2. Monoalfabetyczne szyfrowanie poligra(cid:2)czne . . . 12.3. Szyfrowania polialfabetyczne . . . . . 12.4. Og(cid:243)lne uwagi na temat z(cid:7)o(cid:1)zono·sci kombinatorycznej 12.5. Kryptoanaliza przez atak wyczerpuj (cid:8)acy . . . . . . 12.6. D(cid:7)ugo·s·c krytyczna . . . . . . . . . . . 12.7. Praktyczne stosowanie ataku wyczerpuj (cid:8)acego . . 12.8. Mechanizacja ataku wyczerpuj (cid:8)acego . . . . . . . . Z(cid:7)o(cid:1)zono·s·c kombinatoryczna przeszukiwania wyczerpuj (cid:8)acego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anatomia j(cid:8)ezyka: wzorce 13. 13.1. Niezmienniczo·s·c wzorc(cid:243)w . . . . . . 13.2. Wykluczanie metod szyfrowania . . 13.3. Wyszukiwanie wzorca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 181 . . 181 . . 184 . . 186 . . 186 . . 192 . . 196 205 . . 206 . . 208 . . 215 . . 217 . . 221 . . 222 225 . . 225 . . 233 . . 238 . . 239 245 251 . . 252 . . 253 . . 255 . . 257 . . 258 . . 259 . . 262 . . 265 267 . . 267 . . 270 . . 270 10 Spis tre´sci . . . . 13.4. Wyszukiwanie wzorc(cid:243)w poligra(cid:2)cznych . 13.5. Metoda s(cid:7)(cid:243)w prawdopodobnych . . . . . . . . . . 13.6. Automatyczne wyczerpywanie realizacji wzorca . 13.7. Pangramy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Przypadek polialfabetyczny: s(cid:7)owa prawdopodobne 14. 14.1. Wyczerpywanie pozycji negatywnego wzorca s(cid:7)owa prawdopodobnego . . 14.2. Wyczerpywanie pozycji binarnego negatywnego wzorca s(cid:7)owa . . . . . . . . . . 14.3. Atak de Viarisa . . . . . 14.4. Wyczerpywanie pozycji s(cid:7)owa prawdopodobnego metod (cid:8)a zygzakow (cid:8)a . . . . . . . 14.5. Metoda izomorf(cid:243)w . . . . . . . 14.6. Ukryta kompromitacja tekst jawny(cid:150)kryptogram . . . . . prawdopodobnego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anatomia j(cid:8)ezyka: cz(cid:8)esto·sci 15. . . . . 15.1. Wykluczanie metod szyfrowania . . . . . . . . . 15.2. Niezmienniczo·s·c partycji . . . . . . . . 15.3. Metoda intuicyjna: pro(cid:2)l cz(cid:8)esto·sci . . . . . . . . 15.4. Szeregowanie cz(cid:8)esto·sci . . . . . . . . . . . . 15.5. Kliki i dopasowanie partycji . . . . . . 15.6. Dopasowanie optymalne . . . . . . . . . . . 15.7. Cz(cid:8)esto·sci wieloznak(cid:243)w . . . . . . . . 15.8. Mieszana metoda dopasowania cz(cid:8)esto·sci . . . . 15.9. Dopasowanie wzorca w przypadku podstawie·n poligra(cid:2)cznych . . . . . . . 15.10. Styl dowolny . . . . . . . 15.11. Dodatkowe informacje o d(cid:7)ugo·sci krytycznej . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kappa i Chi 16. 16.1. De(cid:2)nicja i niezmienniczo·s·c parametru Kappa . . . . . . . 16.2. De(cid:2)nicja i niezmienniczo·s·c parametru Chi 16.3. Twierdzenie Kappa(cid:150)Chi . . . . . . . . . . . . 16.4. Twierdzenie Kappa(cid:150)Phi . . . . 16.5. Symetryczne funkcje cz(cid:8)esto·sci znak(cid:243)w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Badanie okresowo·sci 17. 17.1. Test Kappa Friedmana . . . . . 17.2. Test Kappa dla wieloznak(cid:243)w . 17.3. Kryptoanaliza maszynowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 . . 274 . . 279 . . 281 283 . . 283 . . 286 . . 288 . . 295 . . 297 . . 302 305 . . 305 . . 307 . . 308 . . 310 . . 313 . . 318 . . 320 . . 328 . . 332 . . 334 . . 337 339 . . 339 . . 342 . . 345 . . 346 . . 348 351 . . 352 . . 353 . . 354 Spis tre´sci 11 17.4. Metoda Kasiskiego . . . . . . 17.5. Nawarstwianie i test Phi Kullbacka . 17.6. Szacowanie d(cid:7)ugo·sci okresu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 . . 365 . . 368 . . . . . . . . . . . . . . . Ustawianie alfabet(cid:243)w towarzysz (cid:8)acych 18. . . . 18.1. Dopasowanie pro(cid:2)lu . . . . . . 18.2. Ustawianie wzgl(cid:8)edem znanego alfabetu . . . . . 18.3. Test Chi: wzajemne ustawianie alfabet(cid:243)w towarzysz (cid:8)acych . . . . . . . . . 18.4. Rekonstrukcja alfabetu podstawowego . . . . . . 18.5. Symetria pozycji Kerckhoffsa . . . . . . . . . 18.6. Usuwanie przeszyfrowania: metoda r(cid:243)(cid:1)znicowa . . . . . . . . . . . . 18.7. Deszyfrowanie kodu . . 18.8. Rekonstrukcja has(cid:7)a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kompromitacje 19. . . . . 19.1. Nak(cid:7)adanie Kerckhoffsa . . . . . . . . . . . . . . . 19.2. Nak(cid:7)adanie metod szyfrowania posiadaj (cid:8)acych grup(cid:8)e kluczy . . . . . . . . . 19.3. Zgodne fazowo nak(cid:7)adanie kodu przeszyfrowanego . . . . . . . . . . . . . . . . . . . . . 19.4. Kompromitacje kryptogram(cid:150)kryptogram . . . . . 19.5. Metoda Sinkova . . . . . . . . . . . . . . . . . . . . 19.6. Kompromitacja kryptogram(cid:150)kryptogram: dublowanie wska·znika . . . . . . 19.7. Kompromitacja tekst jawny(cid:150)kryptogram: cykl sprz(cid:8)e(cid:1)zenia zwrotnego . . . . . . . . . . . . . . . . . . . . . . . . . . . Kryptoanaliza liniowa 20. 20.1. Redukcja liniowych podstawie·n poligra(cid:2)cznych . 20.2. Rekonstrukcja klucza . . . . . . 20.3. Rekonstrukcja liniowego rejestru przesuwnego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21. Anagramowanie 21.1. Transpozycja . . . . . . . 21.2. Podw(cid:243)jna transpozycja kolumnowa . . . . . . . . 21.3. Anagramowanie wielokrotne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uwagi ko ·ncowe 22. . . . . 22.1. Sukces w z(cid:7)amaniu szyfru . . . 22.2. Spos(cid:243)b dzia(cid:7)ania niepowo(cid:7)anego deszyfranta . . . . . . . 22.3. U(cid:7)uda bezpiecze·nstwa . 22.4. Znaczenie kryptologii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 . . 371 . . 375 . . 379 . . 383 . . 386 . . 391 . . 393 . . 394 397 . . 397 . . 399 . . 415 . . 418 . . 422 . . 429 . . 444 455 . . 455 . . 456 . . 457 461 . . 461 . . 464 . . 465 469 . . 470 . . 475 . . 480 . . 481 12 Spis tre´sci Aksjomatyczna teoria informacji A.1 Aksjomaty aksjomatycznej teorii informacji . . . . A.2 Aksjomatyczna teoria informacji kryptosystem(cid:243)w . . . . A.3 Kryptosystemy zupe(cid:7)ne i z kluczem niezale(cid:1)znym . . . . . . . . A.4 G(cid:7)(cid:243)wne twierdzenie Shannona . . . . . . . . . . . . . . A.5 D(cid:7)ugo·s·c krytyczna . . . . . . . A.6 Kompresja kodowa . . . . . . . . . . . . . . . . . . A.7 Niemo(cid:1)zno·s·c totalnego nieuporz (cid:8)adkowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliogra(cid:2)a Skorowidz ·Zr(cid:243)d(cid:7)a fotogra(cid:2)i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 . . 487 . . 489 . . 491 . . 493 . . 494 . . 496 . . 496 499 503 535 Rozdzia(cid:7) 3. Kroki szyfrowania: podstawienie proste W·sr(cid:243)d krok(cid:243)w szyfrowania wyr(cid:243)(cid:1)zni·c mo(cid:1)zna dwie du(cid:1)ze klasy: podstawienia (substitutions) oraz transpozycje (transpositions). S (cid:8)a one szczeg(cid:243)lnymi przypadkami og(cid:243)lnego kroku szy- frowania V (n) (cid:0)(cid:0)! W(m). Rozpoczniemy od om(cid:243)wienia rodzaj(cid:243)w podstawie·n, by na- st(cid:8)epnie w rozdziale 6. zaj (cid:8)a·c si(cid:8)e transpozycjami. Podstawienie proste (ang. simple substitution, niem. Tauschverfahren lub Ersatzverfahren) to podstawienie o monogra(cid:2)cznych krokach szyfrowania (cid:31)i 2 M: (cid:31)i : V (1) (cid:0)(cid:0)! W(mi). W przypadku monoalfabetycznym ustala si(cid:8)e dowolny (cid:31)s 2 M i szyfrowanie przebiega wed(cid:7)ug schematu X = [(cid:31)s, (cid:31)s, (cid:31)s, . . .]. Zbi(cid:243)r M mo(cid:1)ze wtedy by·c nawet jednoelementowy. Zaczniemy od przypadku, w kt(cid:243)rym mi = 1 dla wszystkich i. 3.1. Przypadek V (1) (cid:0)(cid:0)! W (jednodzielne podstawienia proste) Przypadek V (1) (cid:0)(cid:0)! W zwi (cid:8)azany jest z jednodzielnym podstawieniem prostym, zwanym w skr(cid:243)cie podstawieniem prostym (ang. unipartite simple substitution, franc. substitution sim- ple ordinaire). 3.1.1. V (cid:0)(cid:0)! W, heterogeniczne szyfrowanie bez homofon(cid:243)w i warto·sci zerowych. Mamy tu do czynienia z przypadkiem podstawowym. Jako W cz(cid:8)esto s(cid:7)u(cid:1)zy alfabet dziw- nie wygl (cid:8)adaj (cid:8)acych, niezwyk(cid:7)ych grafem(cid:243)w; przyk(cid:7)ad(cid:243)w mo(cid:1)zna szuka·c w Tajlandii, Per- sji, Etiopii koptyjskiej i innych miejscach. Znak(cid:243)w takich u(cid:1)zywa(cid:7) Giovanni Battista Porta (Giambattista Della Porta, 1535(cid:150)1615) na swoim dysku szyfruj (cid:8)acym (rysunek 23., patrz tak- (cid:1)ze rysunek 30.). Tak(cid:1)ze Karol Wielki u(cid:1)zywa(cid:7) znak(cid:243)w tego typu (rysunek 24.), podobnie jak uczona i mistyczka Hildegarda von Bingen (1098(cid:150)1179). W tym miejscu trzeba wspomnie·c 60 Rozdział 3. Kroki szyfrowania: podstawienie proste Rysunek 23. Dysk szyfruj (cid:8)acy Giovanniego Battisty Porty (1563) Rysunek 24. Tajemne znaki Karola Wielkiego o szyfrze wolnomularzy (Freemasons’ cipher). Jego ·zr(cid:243)de(cid:7) szuka·c nale(cid:1)zy w staro(cid:1)zytnym szy- frze pigpen. Wsp(cid:243)(cid:7)cze·snie przyjmuje on nast(cid:8)epuj (cid:8)ac (cid:8)a posta·c: Szyfr ten mo(cid:1)zna (cid:7)atwo opanowa·c dzi(cid:8)eki diagramom: s (bez kropki) (z kropk (cid:8)a) a b d e g h c f i j m p k l n o q r (bez kropki) t u x v (z kropk (cid:8)a) y w z Po z(cid:7)amaniu tego szyfru przez angielski wydzia(cid:7) deszyfrowania w 1728 roku, car Piotr Wielki zacz (cid:8)a(cid:7) u(cid:1)zywa·c (opr(cid:243)cz nomenklator(cid:243)w) heterogenicznego podstawienia V (cid:0)(cid:0)(cid:0)(cid:0)! W o dziwacznym alfabecie tekstu zaszyfrowanego. Znany pisarz Edgar Allan Poe wykorzysta(cid:7) w swoim opowiadaniu Z(cid:7)oty (cid:1)zuk banalny al- fabet zwyk(cid:7)ych czcionek drukarskich (podrozdzia(cid:7) 15.10.1.). Do klasy tej nale(cid:1)zy tak(cid:1)ze szyfr ksi(cid:8)egarski przeznaczony do szyfrowania cen i dat, stanowi (cid:8)a- cy r(cid:243)(cid:1)znowarto·sciowe odwzorowanie Z10 (cid:0)(cid:0)(cid:0)(cid:0)! Z26, tworzone na podstawie has(cid:7)a (szyfr z fraz (cid:8)a kluczow (cid:8)a, key-phrase cipher). Jako przyk(cid:7)ad niech pos(cid:7)u(cid:1)zy krok szyfrowania z ha- s(cid:7)em MILCHPROBE [‘pr(cid:243)bka mleka’], 3 5 L C H 1 2 M I 9 8 O B 6 7 P R 4 0 E , 3.2. Przypadek szczególny V (cid:0)(cid:0)(cid:0)! V (permutacje) 61 przez wiele lat u(cid:1)zywany w Niemczech do znakowania daty pakowania mas(cid:7)a. Podobnie w marynarce brytyjskiej, przy odczycie kod(cid:243)w ENIGMY, liczby by(cid:7)y czasem reprezento- wane za pomoc (cid:8)a liter: 1 2 Q W 4 3 5 E R T 6 7 Z U 9 8 I O 0 P . 3.1.2. V (1) (cid:0)(cid:0)! W, heterogeniczne szyfrowanie z homofonami i warto·sciami zerowymi. Homofony znale·z·c mo(cid:1)zna w ·zr(cid:243)d(cid:7)ach muzu(cid:7)ma·nskich, np. al-Qalqashandi z roku 1412, a tak(cid:1)ze w szyfrze u(cid:1)zywanym przez Ksi(cid:8)estwo Mantui w 1401 roku w korespondencji z Si- meonem de Crema. Samog(cid:7)oski (cid:151) zazwyczaj wyst(cid:8)epuj (cid:8)ace najcz(cid:8)e·sciej (cid:151) opatrywano ho- mofonami, co stanowi(cid:7)o pierwszy przejaw przywi (cid:8)azywania wagi do cz(cid:8)esto·sci wyst(cid:8)epo- wania znak(cid:243)w. Dodatkowo zbi(cid:243)r W rozszerzano o cyfry. Wprowadzenie homofon(cid:243)w prak- tycznie wymusza dodanie warto·sci zerowych; w przeciwnym wypadku homofony mo(cid:1)zna z (cid:7)atwo·sci (cid:8)a rozpozna·c na podstawie sta(cid:7)ego wzorca liter, otaczaj (cid:8)acych je w cz(cid:8)esto wyst(cid:8)e- puj (cid:8)acych wyrazach. Metoda korzystaj (cid:8)aca z homofon(cid:243)w, u(cid:1)zywana po dzie·n dzisiejszy, to tak zwany szyfr ksi (cid:8)a(cid:1)z- kowy: z pewnej niewinnie wygl (cid:8)adaj (cid:8)acej ksi (cid:8)a(cid:1)zki, kt(cid:243)rej identyczne egzemplarze posiadaj (cid:8)a zar(cid:243)wno nadawca, jak i odbiorca wiadomo·sci, wybiera si(cid:8)e kolejne litery tekstu jawnego; odpowiednie adresy postaci (strona x, wiersz y, znak z) tworz (cid:8)a grup(cid:8)e szyfru (x-y-z). Wybieraj (cid:8)ac za ksi (cid:8)a(cid:1)zk(cid:8)e niniejszy egzemplarz, s(cid:7)owo (cid:132)ssak(cid:148) mo(cid:1)zna zaszyfrowa·c jako: 25-6-3, 33-12-30, 30-1-9, 22-21-6. 3.2. Przypadek szczeg(cid:243)lny V (cid:0)(cid:0)(cid:0)! V (permutacje) W przypadku wzajemnie jednoznacznego odwzorowania V (cid:0)(cid:0)(cid:0)! W, jak w przyk(cid:7)a- dach z podrozdzia(cid:7)u 3.1.1., W jest nazywany N-znakowym alfabetem nieuporz (cid:8)adkowanym tekstu zaszyfrowanego (ang. mixed alphabet; franc. alphabet dØsordonnØ, alphabet incohØrent; niem. umgeordnetes Geheimtextalphabet), kt(cid:243)ry odpowiada alfabetowi standardowemu tekstu jawnego (ang. standard alphabet; franc. alphabet ordonnØ; niem. Standard-Klartextalphabet) V, r(cid:243)wnie(cid:1)z sk(cid:7)adaj (cid:8)acemu si(cid:8)e z N znak(cid:243)w. W celu zde(cid:2)niowania podstawienia wystarczy utworzy·c w pewien spos(cid:243)b list(cid:8)e odpowia- daj (cid:8)acych sobie par znak(cid:243)w tekstu jawnego i kryptogramu, np. dla V (cid:1)(cid:17) W = Z26 (zasady u(cid:1)zycia w notacji ma(cid:7)ych liter oraz wersalik(cid:243)w opisano w podrozdziale 2.5.4.): u d c b m a v g k s t n w z e i h f q l j r o p x y H E W A S R I G T O U D C L N M F Y V B P K J Q Z X Podczas szyfrowania du(cid:1)zo wygodniej jest oczywi·scie mie·c znaki tekstu jawnego uporz (cid:8)ad- kowane w alfabet standardowy (tekstu jawnego); daje to alfabet nieuporz (cid:8)adkowany tekstu zaszyfrowanego: a b c d e f g h i j k l m n o p q r s t u v w x y z R A W E N Y G F M P T B S D J Q V K O U H I C Z X L W matematyce zwyczajowo stosuj(cid:8)e si(cid:8)e tak (cid:8)a notacj(cid:8)e podstawie·n. Jednak podczas deszy- frowania lepiej mie·c znaki tekstu zaszyfrowanego uporz (cid:8)adkowane w alfabet standardowy (tekstu zaszyfrowanego), co daje nieuporz (cid:8)adkowany alfabet tekstu jawnego: 62 Rozdział 3. Kroki szyfrowania: podstawienie proste b l w n d h g u v o r z i e s j p a m k t q c y f x A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z now (cid:8)a sytuacj (cid:8)a mamy do czynienia w endomor(cid:2)cznym przypadku V (cid:1)(cid:17) W. W szczeg(cid:243)l- no·sci wzajemnie jednoznaczne odwzorowanie V (cid:0)(cid:0)(cid:0)! V jest w(cid:243)wczas permutacj (cid:8)a V. Per- mutacj(cid:8)e V (cid:0)(cid:0)(cid:0)! V mo(cid:1)zna zrealizowa·c w modelu elektrycznym poprzez wymian(cid:8)e (ang. in- terchange; niem. Umstecken) N przewod(cid:243)w w wi (cid:8)azce. Do zapisu permutacji matematycy u(cid:1)zywaj (cid:8)a, opr(cid:243)cz notacji podstawie·n, tak(cid:1)ze notacji cy- klicznej: (a r k t u h f y x z l b) (c w) (d e n) (g) (i m s o j p q v), w kt(cid:243)rej trzeba zrezygnowa·c z rozr(cid:243)(cid:1)znienia pomi(cid:8)edzy ma(cid:7)ymi literami a wersalikami. Pod- czas szyfrowania przechodzimy cyklicznie od znalezionego znaku tekstu jawnego do na- st(cid:8)epnego znaku; podczas deszyfrowania (cid:151) cyklicznie do poprzedniego znaku. Cykle d(cid:7)u- go·sci 1 (1-cykle) s (cid:8)a cz(cid:8)esto pomijane (cid:151) my nie b(cid:8)edziemy si(cid:8)e do tego stosowa·c. 3.2.1. Permutacje samoodwrotne. Najstarsze ·zr(cid:243)d(cid:7)a (pomijaj (cid:8)ac Egipt, do kt(cid:243)rego powr(cid:243)- cimy przy omawianiu kod(cid:243)w) opisuj (cid:8)a samoodwrotn (cid:8)a (inwolutywn (cid:8)a) permutacj(cid:8)e V: in- dyjska Kflama-sflutra, napisana przez Vflatsyflayan(cid:8)e, zawiera opis tajnego pisma traktowanego jako jedna z sze·s·cdziesi(cid:8)eciu czterech sztuk; M fluladevfl(cid:17)ya oznacza proces szyfrowania i de- szyfrowania, kt(cid:243)ry stanowi odbicie (inwolucj(cid:8)e): V 2 (cid:0)(cid:0)(cid:0)! V :l a kh gh c t ñ n r l y k g n t. p n. m s. s ´s . Pozosta(cid:7)e znaki nie s (cid:8)a zmieniane, wi(cid:8)ec permutacja nie jest ·sci·sle samoodwrotna, permutacja (properly self-reciprocal). O alfabetach tekstu jawnego i tekstu zaszyfrowanego permutacji samoodwrotnej m(cid:243)wi si(cid:8)e, (cid:1)ze s (cid:8)a wzgl(cid:8)edem siebie wzajemnie odwrotne. W hebrajskim Starym Testamencie u(cid:1)zyto podstawienia bustrofedonicznego (boustrophedo- nic substitution) zwanego Athbash (cid:151) aczkolwiek nie w celu szyfrowania (cid:151) kt(cid:243)re w (cid:7)aci·n- skim alfabecie V = Z20 mo(cid:1)zna odczyta·c jako V 2 (cid:0)(cid:0)(cid:0)! V :l a b c d e f g h i l z v t s r q p o n m . Takie podstawienie korzysta z alfabetu odwr(cid:243)conego (inwersyjnego). W przypadku inwo- lucji V 2 (cid:0)(cid:0)(cid:0)! V :l a b c d e f g h i l m a z v t s r q p o n m Charles Eyraud m(cid:243)wi o alfabecie dope(cid:7)niaj (cid:8)acym (ang. complementary alphabet; franc. alphabet complØmentaire) (cid:151) patrz podrozdzia(cid:7) 5.6. Permutacja ta nie jest jednak ·sci·sle samoodwrotna: /a/ i /m/ pozostaj (cid:8)a niezmienione. Oczywista jest tak(cid:1)ze samoodwrotno·s·c alfabetu przesuni(cid:8)etego, na przyk(cid:7)ad hebrajskiego Albam, u(cid:1)zytego w 1589 roku przez Argentich, gdzie V = Z20: a b c d e f g h i l m n o p q r s t v z , (cid:0)(cid:0)(cid:0)! V :l 2 V 3.2. Przypadek szczególny V (cid:0)(cid:0)(cid:0)! V (permutacje) 63 czy te(cid:1)z alfabetu Giovanniego Battisty Porty z 1563 roku (patrz rysunek 53.) przy V = Z22: V 2 (cid:0)(cid:0)(cid:0)! V :l a b c d e f g h i l m n o p q r s t v x y z . Poni(cid:1)zszy przyk(cid:7)ad przedstawia najog(cid:243)lniejszy przypadek bustrofedoniczy z u(cid:1)zyciem ha- s(cid:7)a (V = Z26): V 2 (cid:0)(cid:0)(cid:0)! V :l a n g e r s b c d f h i j z y x w v u t q p o m l k . Opr(cid:243)cz zalety zwi(cid:8)ez(cid:7)ej notacji inwolucje posiadaj (cid:8)a cech(cid:8)e, kt(cid:243)r (cid:8)a niekt(cid:243)rzy uwa(cid:1)zaj (cid:8)a za ogro- mnie wa(cid:1)zn (cid:8)a (cid:151) pokrywanie si(cid:8)e krok(cid:243)w szyfrowania i deszyfrowania. Przy wykorzystaniu notacji cyklicznej, pi(cid:8)e·c ostatnich przyk(cid:7)ad(cid:243)w permutacji mo(cid:1)zna zapi- sa·c jako: (a z) (b v) (c t) (d s) (e r) (f q) (g p) (h o) (i n) (l m), (a) (b z) (c v) (d t) (e s) (f r) (g q) (h p) (i o) (l n) (m), (a m) (b n) (c o) (d p) (e q) (f r) (g s) (h t) (i v) (l z), (a n) (b o) (c p) (d q) (e r) (f s) (g t) (h v) (i x) (l y) (m z), (a z) (b t) (c q) (d p) (e w) (f o) (g x) (h m) (i l) (j k) (n y) (r v) (s u). (Cykle uporz (cid:8)adkowano w kolejno·sci alfabetycznej ich pierwszych element(cid:243)w). ·Sci·sle samoodwrotne permutacje nie posiadaj (cid:8)a 1-cykli, co oznacza wyst(cid:8)epowanie w nich wy(cid:7) (cid:8)acznie 2-cykli (zamiany, swaps). Stanowi (cid:8)a one cel atak(cid:243)w kryptoanalitycznych (pod- rozdzia(cid:7) 14.1.), kt(cid:243)re okazuj (cid:8)a si(cid:8)e nieskuteczne, je·sli niekt(cid:243)re z cykli s (cid:8)a 1-cyklami (cykle female). W przypadku alfabetu binarnego V = Z2 jedyn (cid:8)a nietrywialn (cid:8)a permutacj (cid:8)a jest zamiana: V 2 (cid:0)(cid:0)(cid:0)! V :l O L . 3.2.2. Komutator. W implementacjach elektrycznych inwolucje mo(cid:1)zna zrealizowa·c przez zamian(cid:8)e par przewod(cid:243)w, (cid:7)atw (cid:8)a do wykonania przy zastosowaniu dwustronnych wtyk(cid:243)w (rysunek 25.). W ten spos(cid:243)b zrealizowano inwolucje w centralce (ang. plugboard; niem. Stec- kerbrett) maszyny ENIGMA. a rm rh a b rm rh b c rm rh c d rm rh d e rm rh e f rm rh f g rm rh g h rm rh h i rm rh i j rm rh j k rm rh k l rm rh l m rm rh m . . . Rysunek 25. Permutacja samoodwrotna zrealizowana przy u(cid:1)zyciu komutatora z(cid:7)o(cid:1)zonego z par dwustronnych wtyk(cid:243)w, przerywaj (cid:8)acych bezpo·srednie po(cid:7) (cid:8)aczenia 64 Rozdział 3. Kroki szyfrowania: podstawienie proste Liczba inwolucji d(k, N) zale(cid:1)zy od N oraz od liczby k u(cid:1)zytych koncentrycznych z(cid:7) (cid:8)acz wty- kowych (cinch plugs): N! d(k, N) = (2k)! 2kk! (2k - 1)!! = (2k - 1) (cid:1) (2k - 3) (cid:1) (cid:1)(cid:1)(cid:1) (cid:1) 5 (cid:1) 3 (cid:1) 1 = 2k (cid:1) (N - 2k)! (cid:1) k! =(cid:18) N 2k(cid:19) (cid:1) =(cid:18) N 2k(cid:19) (cid:1) (2k - 1)!!, (2k)! 2kk! . gdzie Permutacje ·sci·sle samoodwrotne ((cid:132)prawdziwe(cid:148) inwolucje) istniej (cid:8)a tylko dla parzystych N = 2(cid:23). Liczba d(cid:0) N 2 , N(cid:1) wszystkich permutacji ·sci·sle samoodwrotnych wynosi (przy b(cid:7)(cid:8)e- dzie wzgl(cid:8)ednym mniejszym ni(cid:1)z 10-3 dla N 6) d(cid:16) n 2 , N(cid:17) = (N - 1)!! = (N - 1) (cid:1) (N - 3) (cid:1) (cid:1)(cid:1)(cid:1) (cid:1) 5 (cid:1) 3 (cid:1) 1 = (2(cid:23))! (cid:23)!2(cid:23) (cid:25) p(2(cid:23))! 4q(cid:25) (cid:1) ((cid:23) + 1 4 ) . Przybli(cid:1)zenie to nale(cid:1)zy traktowa·c jako dobre g(cid:243)rne oszacowanie warto·sci (N - 1)!!. Dla ustalonego N, warto·s·c d(k, N) osi (cid:8)aga maksimum przy k =l(cid:23) -p((cid:23) + 1)=2m: d(5, 26) (cid:25) 5,02 (cid:1) 109, d(8, 26) (cid:25) 1,08 (cid:1) 1013, d(11, 26) (cid:25) 2,06 (cid:1) 1014, za·s d(3, 10) = 3 150, d(6, 26) (cid:25) 1,00 (cid:1) 1011, d(9, 26) (cid:25) 5,38 (cid:1) 1013, d(12, 26) (cid:25) 1,03 (cid:1) 1014, d(4, 10) = 4 725, d(7, 26) (cid:25) 1,31 (cid:1) 1012, d(10, 26) (cid:25) 1,51 (cid:1) 1014, d(13, 26) (cid:25) 7,91 (cid:1) 1012, d(5, 10) = 945. log2P13 (cid:1)ze log2 d(10, 26) (cid:25) 47,10 [bit], log2 d(11, 26) (cid:25) 47,55 [bit], log2 d(12, 26) (cid:25) Zauwa(cid:1)zmy, i=1 d(k, 26) (cid:25) log2 5,33 (cid:1) 1014 (cid:16) 48,92 [bit]. 46,55 [bit], za·s dla wszystkich inwolucji W ENIGMIE I Reichswehry z 1930 roku do po(cid:7) (cid:8)aczenia komutatora realizowano pocz (cid:8)atko- wo za pomoc (cid:8)a sze·sci dwustronnych wtyk(cid:243)w dwuprzewodowych, za·s w ENIGMIE Wehr- machtu od pocz (cid:8)atku, czyli od 1 pa·zdziernika 1936 roku (cid:151) za pomoc (cid:8)a od pi(cid:8)eciu do o·smiu wtyk(cid:243)w; od 1 stycznia 1939 roku (cid:151) od siedmiu do dziesi(cid:8)eciu wtyk(cid:243)w, za·s od 19 sierpnia 1939 roku (cid:151) za pomoc (cid:8)a dziesi(cid:8)eciu wtyk(cid:243)w. 3.2.3. Permutacje monocykliczne. Zwi(cid:8)ez(cid:7)a notacja mo(cid:1)ze tak(cid:1)ze s(cid:7)u(cid:1)zy·c do opisu permutacji monocyklicznej, kt(cid:243)rej rz (cid:8)ad wynosi N. Oto na przyk(cid:7)ad, dla N = 20, cykl standardowego alfabetu Z20: V N (cid:0)(cid:0)(cid:0)! V : (a b c d e f g h i l m n o p q r s t v x) i jego trzeciej pot(cid:8)egi V N (cid:0)(cid:0)(cid:0)! V : (a d g l o r v b e h m p s x c f i n q t). W notacji podstawie·n przyjm (cid:8)a one posta·c: oraz V N (cid:0)(cid:0)(cid:0)! V : a b c d e f g h i l m n o p q r s t v x B C D E F G H I L M N O P Q R S T V X A V N (cid:0)(cid:0)(cid:0)! V : a b c d e f g h i l m n o p q r s t v x D E F G H I L M N O P Q R S T V X A B C . 3.2. Przypadek szczególny V (cid:0)(cid:0)(cid:0)! V (permutacje) 65 Z tego drugiego kroku szyfrowania korzysta(cid:7) wed(cid:7)ug Swetoniusza Juliusz Cezar, kt(cid:243)ry szukaj (cid:8)ac potrzebnej litery przesuwa(cid:7) si(cid:8)e po prostu w alfabecie o trzy pozycje do przodu. Jego nast(cid:8)epca August, pod wieloma wzgl(cid:8)edami podrz(cid:8)edny w stosunku do Cezara, u(cid:1)zywa(cid:7) pierwszego z podanych krok(cid:243)w szyfrowania (by·c mo(cid:1)ze dlatego, (cid:1)ze niekoniecznie umia(cid:7) liczy·c do trzech); Swetoniusz twierdzi(cid:7) tak(cid:1)ze, (cid:1)ze zast(cid:8)epowa(cid:7) on /x/ przez AA. Ka(cid:1)zda pot(cid:8)ega cyklu alfabetu standardowego daje w wyniku alfabet CAESAR. Powr(cid:243)cimy do tej kwestii w rozdziale 5. (dodawanie CAESAR). Nale(cid:1)zy jednak zauwa(cid:1)zy·c, (cid:1)ze cho·c oba powy(cid:1)zsze kroki szyfrowania s (cid:8)a rz(cid:8)edu dwadzie·scia, to ich drugie pot(cid:8)egi s (cid:8)a ju(cid:1)z tylko rz(cid:8)edu dziesi(cid:8)e·c, a pot(cid:8)egi dziesi (cid:8)ate (cid:151) rz(cid:8)edu dwa (s (cid:8)a to wi(cid:8)ec opisane wcze·sniej inwolucje). (N-1)-ta pot(cid:8)ega jest odwrotno·sci (cid:8)a pot(cid:8)egi pierwszej i stanowi krok deszyfrowania. Monoalfabetyczne podstawienie kroku szyfrowania CAESAR wprowadzono w 1915 roku w armii rosyjskiej po tym, jak okaza(cid:7)o si(cid:8)e nierealne oczekiwanie, (cid:1)ze sztaby b(cid:8)ed (cid:8)a w stanie u(cid:1)zywa·c czego·s bardziej skomplikowanego. Dla szef(cid:243)w s(cid:7)u(cid:1)zb kryptoanalitycznych, pru- skiego (Ludwig Deubner) i austriackiego (Hermann Pokorny), mile prost (cid:8)a spraw (cid:8)a by(cid:7)o deszyfrowanie tych wiadomo·sci. Ze swej natury ·scie(cid:1)zka na dysku, obr(cid:8)ecz p(cid:7)uczki lub pasek materia(cid:7)u zamkni(cid:8)ety w kszta(cid:7)t pier·scienia mog (cid:8)a s(cid:7)u(cid:1)zy·c jako reprezentacja pe(cid:7)nego cyklu. Narz(cid:8)edzia takie by(cid:7)y szeroko stosowane. W spos(cid:243)b szczeg(cid:243)lny wykorzystali je (podrozdzia(cid:7) 7.5.3.) Thomas Jefferson i (cid:201)tienne Bazeries. q-t (cid:8)a pot(cid:8)eg(cid:8)e permutacji monocyklicznej otrzymuje si(cid:8)e przez cykliczne liczenie krokami co q znak(cid:243)w. 3.2.4. Alfabety nieuporz (cid:8)adkowane. Do przedstawiania niesamoodwrotnych i niecyklicz- nych permutacji V (cid:0)(cid:0)(cid:0)! V w najog(cid:243)lniejszym przypadku alfabetu nieuporz (cid:8)adkowanego (ang. mixed alphabet; franc. alphabet dØsordonnØ; niem. permutieres Alphabet) zazwyczaj stosuje si(cid:8)e notacj(cid:8)e podstawie·n: V (cid:0)(cid:0)(cid:0)! V : a b c d e f g h i j k l m n o p q r s t u v w x y z S E C U R I T Y A B D F G H J K L M N O P Q V W X Z . Zwi(cid:8)ez(cid:7)a notacja cykliczna tak(cid:1)ze jest przydatna. Ukazuje ona rozk(cid:7)ad powy(cid:1)zszej permutacji V (cid:0)(cid:0)(cid:0)! V : (a s n h y x w v q l f i) (b e r m g t o j) (c) (d u p k) (z) na jeden 12-cykl, jeden 8-cykl, jeden 4-cykl oraz dwa 1-cykle (podzia(cid:7) cykliczny 12 + 8 + 4 + 1 + 1). 3.2.4.1. Dodatkowe alfabety nieuporz (cid:8)adkowane otrzymuje si(cid:8)e przez cykliczne przesuni(cid:8)e- cie jednego z dw(cid:243)ch wierszy w notacji podstawie·n (przesuni(cid:8)ety alfabet nieuporz (cid:8)adkowa- ny; ang. shifted mixed alphabet; franc. alphabet dØsordonnØ parallØle; niem. verschobenes permu- tieres Alphabet): V (cid:0)(cid:0)(cid:0)! V : V (cid:0)(cid:0)(cid:0)! V : a b c d e f g h i j k l m n o p q r s t u v w x y z E C U R I T Y A B D F G H J K L M N O P Q V W X Z S , a b c d e f g h i j k l m n o p q r s t u v w x y z C U R I T Y A B D F G H J K L M N O P Q V W X Z S E . W notacji cyklicznej maj (cid:8)a one posta·c: (a e i b c u q m h) (d r n j) (f t p l g y z s o k) (v) (w) (x), (a c r o l h b u v w x z e t q n k g) (f y s p m j) (d i). 66 Rozdział 3. Kroki szyfrowania: podstawienie proste 3.2.4.2. Iterowanie podstawie·n, zwane tak(cid:1)ze podnoszeniem do wy(cid:1)zszej pot(cid:8)egi, tworzy po- t(cid:8)egi alfabetu nieuporz (cid:8)adkowanego, np. druga pot(cid:8)ega przedstawionego wy(cid:1)zej podstawie- nia SECURITY... daje podstawienie (a n y w q f) (b r g o) (c) (d p) (e m t j) (h x v l i s) (k u) (z) o wszystkich cyklach d(cid:7)ugo·sci parzystej rozdzielonych na p(cid:243)(cid:7); w notacji podstawie·n: V (cid:0)(cid:0)(cid:0)! V : a b c d e f g h i j k l m n o p q r s t u v w x y z N R C P M A O X S E U I T Y B D F G H J K L Q V W Z . Przesuwanie z jednej strony, a podnoszenie do pot(cid:8)egi z drugiej, w og(cid:243)lnym przypadku nie daj (cid:8)a tego samego rezultatu; s (cid:8)a to dwie kra·ncowo r(cid:243)(cid:1)zne metody tworzenia rodziny co najwy(cid:1)zej N (a czasem mniejszej liczby) alfabet(cid:243)w towarzysz (cid:8)acych (rozdzia(cid:7) 7.). 3.2.5. Alfabety uzyskiwane z hase(cid:7). Przedstawione wy(cid:1)zej przyk(cid:7)ady ukaza(cid:7)y ju(cid:1)z spos(cid:243)b konstruowania (endomor(cid:2)cznego) podstawienia prostego V (cid:0)(cid:0)(cid:0)! V za pomoc (cid:8)a has(cid:7)a (ang. password; franc. mot-clef ; niem. Kennwort, Losung): zazwyczaj mnemonicznego klu- cza lub wyra(cid:1)zenia kluczowego. W klasycznej metodzie u(cid:1)zywa si(cid:8)e s(cid:7)owa z V, zapisuje si(cid:8)e jego znaki bez powt(cid:243)rze·n i uzupe(cid:7)nia w kolejno·sci alfabetycznej znakami niewyst(cid:8)epuj (cid:8)acy- mi w ha·sle. Metod(cid:8)e t(cid:8)e datuje si(cid:8)e na okolice roku 1580, kiedy to u(cid:1)zy(cid:7) jej Giovanni Battista Argenti. By(cid:7) to standard kryptologiczny jeszcze w XX wieku1. Jednak(cid:1)ze konstrukcja taka nie jest bezpieczna: prost (cid:8)a spraw (cid:8)a mo(cid:1)ze okaza·c si(cid:8)e odgadni(cid:8)ecie brakuj (cid:8)acego fragmentu has(cid:7)a (wszak(cid:1)ze najcz(cid:8)e·sciej wyst(cid:8)epuj (cid:8)ace samog(cid:7)oski /e/ oraz /a/ s (cid:8)a zawsze zast(cid:8)epowane literami z has(cid:7)a, je·sli ma ono d(cid:7)ugo·s·c 5 lub wi(cid:8)ecej znak(cid:243)w). Ma(cid:7)ym pocieszeniem jest fakt, (cid:1)ze has(cid:7)o nie b(cid:8)edzie wymaga·c istotnego uzupe(cid:7)nienia. Z tego wzgl(cid:8)edu bardziej wymy·slne metody korzystaj (cid:8)a z przestawienia has(cid:7)a, na przyk(cid:7)ad przez zapisanie go w wierszach i odczytywanie w kolumnach (metoda Charlesa Wheatsto- ne’a z 1854 roku, transpozycja opisana szczeg(cid:243)(cid:7)owo w podrozdziale 6.2.): x y z l o m p n q r u s v t w U R F G O P I T H J Q V Y K W S A L X E C B D M N Z a e i b f j c g k d h Otrzymany tym sposobem alfabet a b c d e f g h i j k l m n o p q r s t u v w x y z S A L X E B M Z C D N U F O R G P I H Q T J V Y K W w notacji cyklicznej przedstawia si(cid:8)e jako (a s h z w v j d x y k n o r i c l u t q p g m f b) (e) z 1-cyklem (e). W kolejnej metodzie tak(cid:1)ze kolumny po stronie tekstu jawnego wype(cid:7)niane s (cid:8)a w alfabetycz- nej kolejno·sci liter has(cid:7)a; w bie(cid:1)z (cid:8)acym przyk(cid:7)adzie jest to kolejno·s·c: 1 Dopuszczenie powt(cid:243)rze·n jest rzecz (cid:8)a z(cid:7) (cid:8)a, gdy(cid:1)z prowadzi do polifon(cid:243)w, jak np. w szyfrze z fraz (cid:8)a kluczow (cid:8)a a b c d e f g h i j l m n o p q r s t u v x y z L E G O U V E R N E M E N T P R O V I S O I R E oraz zmniejsza liczb(cid:8)e element(cid:243)w zbioru znak(cid:243)w tekstu zaszyfrowanego (w naszym przypadku do 13 zna- k(cid:243)w; np. fb, g, j, m, zg 7(cid:0)! E). 3.2. Przypadek szczególny V (cid:0)(cid:0)(cid:0)! V (permutacje) 67 trzecia, druga, sz(cid:243)sta, pi (cid:8)ata, pierwsza, si(cid:243)dma, czwarta, (cid:243)sma kolumna, co daje w rezultacie: S A L X E C B D M N Z U R F G O P I T H J Q V Y K W n d a o e b p f c q g u k v l w m h r i s j t x y z Ostatecznie otrzymujemy alfabet: a b c d e f g h i j k l m n o p q r s t u v w x y z C D N E B M Z I H Q R G P S A L X T J V U F O Y K W kt(cid:243)ry w notacji cyklicznej b(cid:8)edzie mia(cid:7) posta·c (a c n s j q x y k r t v f m p l g z w o) (b d e) (h i) (u). Metoda ta mo(cid:1)ze by·c tak(cid:1)ze wykorzystana do konstruowania cykli. Zdanie (cid:132)Øvitez les co- urants d’air(cid:148) [(cid:132)unikaj przeci (cid:8)ag(cid:243)w(cid:148)] (Bazeries, podrozdzia(cid:7) 7.5.3.) tworzy cykl: V N (cid:0)(cid:0)(cid:0)! V : (e v i t e z l s c o u r a n d b f g h j k m p q x y). 3.2.6. Liczba odwzorowa ·n. Poni(cid:1)zsza tabela przedstawia liczb(cid:8)e Z(N) mo(cid:1)zliwych alfabet(cid:243)w V (cid:0)(cid:0)(cid:0)! V dla N = 26, N = 10 i N = 2: Liczba permutacji razem monocykliczne inwolucje razem ·scis(cid:7)e inwolucje uzyskane z sensownych hase(cid:7) (wyrazy mnemoniczne) Z(N) N! (N - 1)! (cid:25) N (cid:1) (N!) (cid:25) (N!) 1 2 1 2 Z(10) Z(2) 3 628 800 362 880 9 496 945 2 1 2 1 Z(26) 4,03 (cid:1) 1026 1,55 (cid:1) 1025 5,33 (cid:1) 1014 7,91 (cid:1) 1012 104 . . . 106 3.2.7. Dyski szyfruj (cid:8)ace i paski szyfruj (cid:8)ace. Przy mechanizacji procesu podstawiania, usta- lony zwi (cid:8)azek znak(cid:243)w tekstu jawnego i znak(cid:243)w tekstu zaszyfrowanego, podobnie jak w no- tacji podstawie·n, mo(cid:1)zna osi (cid:8)agn (cid:8)a·c dzi(cid:8)eki u(cid:1)zyciu cylindra lub paska materia(cid:7)u. Dwa okienka pozwalaj (cid:8)a w danej chwili widzie·c tylko dwa odpowiadaj (cid:8)ace sobie znaki. Okienka mo(cid:1)zna ustawi·c tak, (cid:1)ze g(cid:7)(cid:243)wny szyfrant widzi jedynie tekst jawny, za·s operator (cid:151) tylko okienko z bie(cid:1)z (cid:8)acym znakiem kryptogramu, przy czym nie mo(cid:1)ze zrozumie·c tre·sci szyfrowanego komunikatu (podrozdzia(cid:7) 7.5.2., maszyna Gripenstierny, rysunek 54.). Wyboru jednego z N przesuni(cid:8)etych alfabet(cid:243)w towarzysz (cid:8)acych dokona·c mo(cid:1)zna, je·sli jedno z okienek jest ruchome. Inna mo(cid:1)zliwo·s·c to przesuwanie alfabetu tekstu jawnego wzgl(cid:8)e- dem alfabetu tekstu zaszyfrowanego. Prowadzi to do u(cid:1)zycia dw(cid:243)ch dysk(cid:243)w (rysunek 26.) lub dw(cid:243)ch pask(cid:243)w (rysunek 27.). W tym drugim przypadku konieczne jest powt(cid:243)rzenie jednego z alfabet(cid:243)w (duplikacja). Dyski szyfruj (cid:8)ace (ang. cipher disk; franc. cadran; niem. Chiffrierscheibe), mechaniczne urz (cid:8)a- dzenia s(cid:7)u(cid:1)z (cid:8)ace do og(cid:243)lnego podstawiania przy u(cid:1)zyciu przesuni(cid:8)etych alfabet(cid:243)w nieupo- rz (cid:8)adkowanych, zosta(cid:7)y opisane ju(cid:1)z w 1466 roku przez Leona Battist(cid:8)e Albertiego2 (patrz rycina B). Suwaki szyfruj (cid:8)ace (ang. cipher slide; franc. reglette; niem. Chiffrierschieber) by(cid:7)y 2 Na ilustracji Albertiego, w odr(cid:243)(cid:1)znieniu od wsp(cid:243)(cid:7)czesnej konwencji, wielkie litery oznaczaj (cid:8)a tekst jawny, za·s 68 Rozdział 3. Kroki szyfrowania: podstawienie proste Rysunek 26. Dysk szyfruj (cid:8)acy Leona Battisty Albertiego (wed(cid:7)ug Langego i Soudarta, 1935) u(cid:1)zywane w Anglii czas(cid:243)w el(cid:1)zbieta·nskich oko(cid:7)o roku 1600. W wieku XIX nazywano je su- wakami Saint-Cyr (od nazwy s(cid:7)ynnej francuskiej akademii wojskowej). Takie samo prze- znaczenie maj (cid:8)a pr(cid:8)ety szyfruj (cid:8)ace (ang. cipher rods; franc. b(cid:226)tons; niem. Chiffrierst(cid:228)bchen). a b c d e f g h i j k l m n o p q r s t u v w x y z a b d c e f g h i j k l m . . . S E C U R I T Y A B D F G H J K L M N O P Q V W X Z Rysunek 27. Suwak szyfruj (cid:8)acy z podwojonym alfabetem tekstu jawnego 3.2.8. Realizacja cykli za pomoc (cid:8)a okienek. Mechanizacja permutacji monocyklicznej mo- (cid:1)ze bazowa·c tak(cid:1)ze na notacji cyklicznej. Cykl znak(cid:243)w umieszcza si(cid:8)e na cylindrze lub su- waku (w tym drugim przypadku pierwszy znak trzeba powt(cid:243)rzy·c na ko·ncu). S (cid:8)asiaduj (cid:8)ace okienka pozwalaj (cid:8)a widzie·c w danej chwili tylko dwa znaki, z kt(cid:243)rych lewy jest znakiem tekstu jawnego, za·s prawy odpowiednim znakiem kryptogramu. Wyboru spo·sr(cid:243)d (maksymalnie N) towarzysz (cid:8)acych pot(cid:8)eg alfabetu nieuporz (cid:8)adkowanego mo(cid:1)zna dokonywa·c, o ile odleg(cid:7)o·s·c mi(cid:8)edzy okienkami da si(cid:8)e zmienia·c. W przypadku suwa- ka konieczne jest powt(cid:243)rzenie ca(cid:7)ego cyklu. q-t (cid:8)a pot(cid:8)eg(cid:8)e permutacji monocyklicznej otrzy- muje si(cid:8)e, kiedy okienka dzieli odleg(cid:7)o·s·c q znak(cid:243)w (rysunek 28. dla q = 14). # 14 S E C U R I T Y A B D F G H J K L M N O P Q V W X Z S E C U R I T Y A B D F G . . . Rysunek 28. Suwak szyfruj (cid:8)acy z okienkami do generowania pot(cid:8)eg alfabetu 3.3. Przypadek V (1) (cid:0)(cid:0)! Wm (wielodzielne podstawienia proste) 3.3.1. m = 2, dwudzielne podstawienie proste V (1) (cid:0)(cid:0)! W2. Podstawienia korzysta- j (cid:8)ace z bigram(cid:243)w (bigram substitutions, podstawienia dwudzielne) by(cid:7)y znane ju(cid:1)z w staro- (cid:1)zytno·sci. Polibiusz opisa(cid:7) pi (cid:8)atkowe (jWj = 5) podstawienie dwudzielne dla liter greckich. We wsp(cid:243)(cid:7)czesnej formie dwudzielnego podstawienia prostego alfabet Z25 wpisuje si(cid:8)e w ta- bel(cid:8)e o wymiarach 5 (cid:2) 5: ma(cid:7)e litery (cid:151) kryptogram. Znak /et/ najprawdopodobniej oznacza symbol . Pocz (cid:8)atkow (cid:8)a pozycj(cid:8)e dysku wyznacza si(cid:8)e ustawiaj (cid:8)ac obok siebie liter(cid:8)e klucza, na przyk(cid:7)ad D i znak tekstu jawnego, na przyk(cid:7)ad /a/. 3.3. Przypadek V (1) (cid:0)(cid:0)! Wm (wielodzielne podstawienia proste) 69 1 2 a b f g l m q r v w 3 4 c d h i n o s t x y 5 e k p u z 1 2 3 4 5 lub 1 a b c d e 3 2 4 f l q g m r h n s i o t k p u 5 v w x y z 1 2 3 4 5 Odszyfrowanie semagramu tekstowego 3 3 5 1 5 1 4 1 2 3 4 3 3 3 5 1 4 5 1 2 4 3 2 4 1 1 3 4 3 4 1 1 3 4 3 4 4 2 3 3 1 1 4 4 4 2 4 3 3 3 z podrozdzia(cid:7)u 1.2., rysunek 3., przeprowadzone za pomoc (cid:8)a prawego kwadratu Polibiu- sza, prowadzi do nast(cid:8)epuj (cid:8)acego tekstu jawnego: n e e d m o n e y f o r a s s a s s i n a t i o n [potrzebne pieni (cid:8)adze na zab(cid:243)jstwo]. Cho·c Polibiusz opisa(cid:7) spos(cid:243)b reprezentowania liczb 1(cid:150)5 za pomoc (cid:8)a pochodni, to w bardziej wsp(cid:243)(cid:7)czesnych czasach u(cid:1)zywano sygna(cid:7)(cid:243)w stukania. szczeg(cid:243)lny szyfr Z25 (cid:0)(cid:0)(cid:0)(cid:0)! Z5 (cid:2) Z5 przedstawiony powy(cid:1)zej jest powszechnie znanym, prawdziwie mi(cid:8)edzynarodowym szy- frem stukania, u(cid:1)zywanym w wi(cid:8)ezieniach od Alcatraz po Ploetzensee zar(cid:243)wno przez prze- st(cid:8)epc(cid:243)w, jak i wi(cid:8)e·zni(cid:243)w politycznych. Zwyk(cid:7)a szybko·s·c transmisji wynosi od 8 do 15 s(cid:7)(cid:243)w na minut(cid:8)e. W carskiej Rosji taki szyfr stukania (z rosyjskim alfabetem wpisanym w kwadrat 6 (cid:2) 6) r(cid:243)wnie(cid:1)z by(cid:7) powszechnie znany i wraz z anarchistami rosyjskimi przyw(cid:8)edrowa(cid:7) do Euro- py Zachodniej jako cz(cid:8)e·s·c szyfru nihilist(cid:243)w (podrozdzia(cid:7) 9.4.5.); u(cid:1)zywano go tak(cid:1)ze w sensie steganogra(cid:2)cznym (podrozdzia(cid:7) 1.2.). Arthur Koestler w Sonnen(cid:2)nsternis, a tak(cid:1)ze Alek- sander So(cid:7)(cid:1)zenicyn w ArchipelaguGu(cid:7)ag, opisali jego u(cid:1)zycie w Zwi (cid:8)azku Sowieckim. Konstrukcja alfabetu zazwyczaj korzysta z has(cid:7)a, kt(cid:243)re zostaje wpisane wiersz po wierszu, a ca(cid:7)o·s·c uzupe(cid:7)nia si(cid:8)e pozosta(cid:7)ymi znakami. Hrabia HonorØ de Mirabeau, francuski rewo- lucjonista z XVIII wieku, u(cid:1)zywa(cid:7) tej metody w swojej korespondencji z markiz (cid:8)a Sophie de Monnier (cid:151) u(cid:1)zywa(cid:7) jej r(cid:243)wnie(cid:1)z steganogra(cid:2)cznie, dodaj (cid:8)ac jako warto·sci zerowe znaki: 6, 7, 8, 9, 0. System ADFGVX, opracowany przez Fritza Nebela (1891(cid:150)1967) i stosowany w 1918 ro- ku w transmisji radiowej na niemieckim froncie zachodnim dowodzonym przez genera(cid:7)a kwatermistrza Ericha Ludendorffa, pracowa(cid:7) przy jWj = 6 (alfabet tekstu zaszyfrowanego Z6 (cid:151) patrz podrozdzia(cid:7) 2.5.2.), w oparciu o tabel(cid:8)e A D c o m k n w 5 s p 1 e q F G V 8 x f 3 a z l 0 j i y h v b 6 7 t 2 X 4 9 d u r g A D F G V X Korzysta si(cid:8)e tak(cid:1)ze z tabel prostok (cid:8)atnych. Giovanni Battista Argenti oko(cid:7)o roku 1580 zasto- sowa(cid:7) nast(cid:8)epuj (cid:8)acy schemat (przy W = Z10): 70 Rozdział 3. Kroki szyfrowania: podstawienie proste 1 2 4 5 r o m n w kt(cid:243)rym po raz pierwszy u(cid:1)zyte zosta(cid:7)o has(cid:7)o. Podstawienie dwudzielne pozostawia na og(cid:243)(cid:7) du(cid:1)zo miejsca dla homofon(cid:243)w: 6 8 a b c q s u 9 d z 0 1 p i f g 2 3 e t h l 7 9, 6, 3 8, 5, 2 7, 4, 1 1 2 a b j k s t 3 4 c d l m u v 5 6 e f n o w x 8 7 9 g h i p q r y z W przyk(cid:7)adzie tym znak /0/ mo(cid:1)ze s(cid:7)u(cid:1)zy·c jako warto·s·c null. Znak zera, pocz (cid:8)atkowo nazy- wany nulla ziffra, wci (cid:8)a(cid:1)z nie wsz(cid:8)edzie jest powa(cid:1)znie brany pod uwag(cid:8)e. Najlepiej jest, kiedy homofony wyr(cid:243)wnuj (cid:8)a cz(cid:8)esto·s·c wyst(cid:8)epowania znak(cid:243)w w kryptogra- mie. Skoro w j(cid:8)ezyku angielskim litery /e/, /t/, /a/, /o/, /n/, /i/, /r/, /s/, /h/ wy- st(cid:8)epuj (cid:8)a z (cid:7) (cid:8)aczn (cid:8)a cz(cid:8)esto·sci (cid:8)a oko(cid:7)o 70 , r(cid:243)wnomierny rozk(cid:7)ad osi (cid:8)aga si(cid:8)e przy 4, 5, 6, 7, 8, 9, 0 2, 3 1 2 1 e t b c p q 4 3 a o d f u v 6 5 n i g j w x 8 9 7 r s h k l m y z 71,09 19,46 9,45 . W innej metodzie u(cid:1)zywa si(cid:8)e 4-literowego has(cid:7)a, kt(cid:243)re decyduje o pocz (cid:8)atkach cykli: (00. . . 24), (25. . . 49), (50. . . 74), (75. . . 99) przy de(cid:2)niowaniu szyfru homofonicznego (dla V = Z25 i W = Z2 10), np. z has(cid:7)em KILO: a b c d e f g h i k l m n o p q r s t u v w x y z K 16 17 18 19 20 21 22 23 24 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 I 42 43 44 45 46 47 48 49 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 L 65 66 67 68 69 70 71 72 73 74 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 O 87 88 89 90 91 92 93 94 95 96 97 98 99 75 76 77 78 79 80 81 82 83 84 85 86 Dziesi(cid:8)etny (jWj = 10) szyfr dwudzielny nie musi posiada·c homofon(cid:243)w: podstawienie mo(cid:1)ze nie by·c surjektywne, a cz(cid:8)e·sci par mo(cid:1)zna nie wykorzysta·c. Szyfru takiego u(cid:1)zywa(cid:7) szwedzki baronet Fridric Gripenstierna (cid:151) prawdopodobnie w oparciu o propozycj(cid:8)e Chri- stophera Polheima. Zabawnej formy dwudzielnego szyfru z homofonami w czasie prac nad bomb (cid:8)a atomow (cid:8)a w Los Alamos u(cid:1)zywali: genera(cid:7) brygady Leslie R. Groves oraz pod- pu(cid:7)kownik Peer da Silva (rysunek 29.) podczas rozm(cid:243)w telefonicznych w celu ukrycia spe- cjalnych nazw i miejsc. Chodzi o to, (cid:1)ze odszukanie w diagramie potrzebnej litery zabiera nieco czasu, homofony s (cid:8)a wi(cid:8)ec wybierane z wi(cid:8)eksz (cid:8)a losowo·sci (cid:8)a ni(cid:1)z w normalnej sytuacji, kiedy szyfrant jest w pewien spos(cid:243)b stronniczy. 3.3.2. m = 3, tr(cid:243)jdzielne podstawienie proste V (1) (cid:0)(cid:0)! W3. Podstawianie za pomoc (cid:8)a tr(cid:243)jznak(cid:243)w (tripartite substitution, podstawienie tr(cid:243)jdzielne) zaproponowa(cid:7) w swoim dziele Polygraphi(cid:230) Trithemius, przy jWj = 3 (warto zauwa(cid:1)zy·c, (cid:1)ze 33 = 27 26) dla cel(cid:243)w steganogra(cid:2)cznych. W innych sytuacjach podobne tr(cid:243)jdzielne podstawienia spotyka si(cid:8)e rzadko. 3.3.3. m = 5, pi(cid:8)eciodzielne podstawienie proste V (1) (cid:0)(cid:0)! W5. Podstawienie grupami po pi(cid:8)e·c znak(cid:243)w kryptogramu (podstawienie pi(cid:8)eciodzielne) przy jWj = 2 zosta(cid:7)o u(cid:1)zy- te przez Francisa Bacona razem z technikami steganogra(cid:2)cznymi (warto zauwa(cid:1)zy·c, (cid:1)ze 3.4. Przypadek ogólny V (1) (cid:0)(cid:0)! W(m) (rozstawianie) 71 1 i w e t s n i m l 2 p e u a v a c c v s 3 i u g z t o b w t r 4 t n m j l a y e 5 o e b d n f r h t 6 u k t e s r u p d 7 o n i u s a d e 8 l o y g m i a 9 p o s e o i x h 0 n t h e r n q e 1 2 3 4 5 6 7 8 9 0 Rysunek 29. Szyfr dwudzielny u(cid:1)zywany w Los Alamos w 1944 roku podczas rozm(cid:243)w telefonicznych 25 = 32 26). Pi(cid:8)eciodzielne szyfrowanie binarne zosta(cid:7)o wskrzeszone w maszynie szyfru- j (cid:8)acej Vernama w 1918 roku (podrozdzia(cid:7) 8.3.2.), a podczas drugiej wojny ·swiatowej w szy- fruj (cid:8)acych maszynach dalekopisowych Siemens T 52 (Geheimschreiber) oraz Lorenz SZ 40/42 (Schl(cid:252)sselzusatz), patrz podrozdzia(cid:7)y: 9.1.3. oraz 9.1.4. 3.3.4. m = 8 o·smiodzielne podstawienie proste V (1) (cid:0)(cid:0)! W8. Dla jWj = 2 (kod 8-bi- towy, binarny kod EBCDIC, kod ASCII z bitem parzysto·sci) o·smiodzielne podstawienie proste pokrywa si(cid:8)e z jednodzielnym podstawieniem bajt(cid:243)w (Z256) znanym ze wsp(cid:243)(cid:7)cze- snych komputer(cid:243)w. 3.4. Przypadek og(cid:243)lny V (1) (cid:0)(cid:0)! W(m) (rozstawianie) W przypadku og(cid:243)lnym V (1) (cid:0)(cid:0)! W(m) mog (cid:8)a wyst (cid:8)api·c warto·sci zerowe i homofony. Simeone de Crema z Mantui (1401) korzysta(cid:7) z samych homofon(cid:243)w (przy m = 1). Przy m = 2 opr(cid:243)cz homofon(cid:243)w i warto·sci zerowych pojawia si(cid:8)e nowe wa(cid:1)zne poj(cid:8)ecie: rozstawia- nie (ang. straddling; niem. Spreizen) alfabetu, b(cid:8)ed (cid:8)ace odwzorowaniem V na W 1 [ W2. Szyfr u(cid:1)zywany na dworze papieskim, opracowany przez Matteo Argentiego po 1590 roku wy- korzystuje homofony, warto·sci zerowe oraz rozstawianie. Dla alfabetu Z24 rozszerzonego o /et/, /con/, /non/, /che/, oraz 5 i 7 s(cid:7)u(cid:1)z (cid:8)ace jako warto·sci zerowe, krok szyfrowania Z(1) 10 [ Z2 24 (cid:0)(cid:0)! Z1 10 wygl (cid:8)ada nast(cid:8)epuj (cid:8)aco: h b c a o m n f g i l 1 86 02 20 22 06 60 3 24 26 84 9 d e 62 82 72 Rozdział 3. Kroki szyfrowania: podstawienie proste p 66 q 68 r 28 s 42 t 80 40 v 04 z 88 et con non che (cid:15) 5 7 00 44 08 64 3.4.1. Zastrze(cid:1)zenia. Kroki szyfrowania z rozstawianiem podlegaj (cid:8)a ograniczeniu nakazu- j (cid:8)acemu, by indukowane przez nie szyfrowanie by(cid:7)o lewostronnie jednoznaczne (left-uni- que) (cid:151) to znaczy, (cid:1)ze granice (hiatusy) mi(cid:8)edzy elementami szyfru jedno- i dwuliterowego, a przez to odpowiednie dekompozycje, s (cid:8)a dobrze okre·slone. Jak stwierdzono w podroz- dziale 2.4., Giovanni Battista oraz Matteo Argenti byli ·swiadomi tego faktu. Ich szyfry spe(cid:7)niaj (cid:8)a nast(cid:8)epuj (cid:8)acy warunek: W dzieli si(cid:8)e na znaki u(cid:1)zywane jako elementy szyfru jed- noznakowego, W 0 = f1, 3, 5, 7, 9g oraz szyfru dwuznakowego, W 00 = f0, 2, 4, 6, 8g. Argenti pope(cid:7)nili b(cid:7) (cid:8)ad przyjmuj (cid:8)ac, (cid:1)ze tak(cid:1)ze drugi znak szyfru musi by·c elementem W 00, co prowa- dzi do rozstawiania. Udzielili oni tak(cid:1)ze bardziej praktycznych porad: nale(cid:1)zy pomija·c /u/ wyst(cid:8)epuj (cid:8)ace po /q/ oraz pomija·c podwojone litery. Tak zwane szyfry szpiegowskie, u(cid:1)zywane przez sowiecki NKWD i jego kontynuator(cid:243)w, to szyfry z rozstawianiem. Zosta(cid:7)y one ujawnione przez schwytanych szpieg(cid:243)w. Przez analo- gi(cid:8)e z kwadratem Polibiusza mo(cid:1)zna je opisa·c za pomoc (cid:8)a tablicy prostok (cid:8)atnej, np.: ((cid:3)) 0 s c . 1 2 i o x u w f 3 4 e r d j l / 6 5 7 a t n p z b g m y 8 9 k q h v 8 9 kt(cid:243)rej pierwszy wiersz zawiera jednoliterowe elementy szyfru. Przy W = Z10 otrzyma·c mo(cid:1)zna 28 element(cid:243)w szyfru, co wystarczy dla Z26 i dw(cid:243)ch znak(cid:243)w specjalnych: . znacz (cid:8)acego ‘stop’ oraz /, s(cid:7)u(cid:1)z (cid:8)acego do zmiany trybu litera(cid:150)liczba. Z uwa- gi na fakt, (cid:1)ze szyfr ten podlega(cid:7) dalszemu szyfrowaniu (szyfrowanie zamykaj (cid:8)ace, closing, podrozdzia(cid:7) 9.2.1.), by(cid:7) przydatny do szyfrowania liczb (po przes(cid:7)aniu znaku przej·scia litera(cid:150)liczba umo(cid:1)zliwia(cid:7) powt(cid:243)rn (cid:8)a transmisj(cid:8)e liczby), b(cid:8)ed (cid:8)ac (cid:8)a dodatkowym zabezpiecze- niem przed b(cid:7)(cid:8)edami transmisji. Przy konstrukcji tej tablicy tak(cid:1)ze korzystano z has(cid:7)a. Dr Per Meurling, szwedzki podr(cid:243)(cid:1)znik, zrobi(cid:7) to w 1937 roku w spos(cid:243)b nast(cid:8)epuj (cid:8)acy: zapisa(cid:7) 8-literowe has(cid:7)o (M. Delvayo by(cid:7) hisz- pa·nskim komunist (cid:8)a), a pod nim pozosta(cid:7) (cid:8)a cz(cid:8)e·s·c alfabetu; kolumny zosta(cid:7)y ponumerowane od ko·nca: 0 m b q 9 8 d e c f r s 7 6 l v g h t u 4 5 3 a y o i j k w x z 2 1 n p . / 1 2 Procedura taka ma t(cid:8)e wad(cid:8)e, (cid:1)ze nie wszystkie najcz(cid:8)e·sciej wyst(cid:8)epuj (cid:8)ace litery otrzymuj (cid:8)a jed- nocyfrowe kody. Wad (cid:8)a t (cid:8)a charakteryzowa(cid:7)a si(cid:8)e tak(cid:1)ze metoda szwedzkiego szpiega Bertila Erikssona, kt(cid:243)rej u(cid:1)zywa(cid:7) w 1941 roku: ponumerowa(cid:7) on kolumny zgodnie z alfabetyczn (cid:8)a kolejno·sci (cid:8)a liter znajduj (cid:8)acych si(cid:8)e w ha·sle (podrozdzia(cid:7) 3.2.5.): 3 9 6 p b r 0 8 a u c d t w 7 5 s o f g x y 9 4 1 m v e h i l z 2 3 j k n q 3.4. Przypadek ogólny V (1) (cid:0)(cid:0)! W(m) (rozstawianie) 73 Has(cid:7)o pochodzi(cid:7)o ze szwedzkiego t(cid:7)umaczenia powie·sci Jaroslava Ha(cid:154)ka Paus, som Svejk sj(cid:228)lv avbr(cid:246)t. . . . Z uwagi na fakt, (cid:1)ze szyfrowanie najcz(cid:8)e·sciej wyst(cid:8)epuj (cid:8)acych liter za pomoc (cid:8)a kod(cid:243)w jednocyfrowych, nie za·s wielocyfrowych, skraca r(cid:243)wnie(cid:1)z czas transmisji telegra- (cid:2)cznej, w 1940 roku NKWD opracowa(cid:7) metod(cid:8)e, kt(cid:243)ra bra(cid:7)a to pod uwag(cid:8)e. Max Clausen, radiooperator rosyjskiego szpiega w Tokio dra Richarda Sorge, musia(cid:7) zapa- mi(cid:8)eta·c zdanie: (cid:132)a sin to err(cid:148) (to bardzo dobra rada dla ka(cid:1)zdego szpiega), zawieraj (cid:8)ace osiem najcz(cid:8)e·sciej wyst(cid:8)epuj (cid:8)acych liter w j(cid:8)ezyku angielskim, w sumie w 65,2 przypadk(cid:243)w. Do ta- blicy wstawiono has(cid:7)o subway i uzupe(cid:7)niono je pozosta(cid:7)ymi literami. Nast(cid:8)epnie, przecho- dz (cid:8)ac kolumny od strony lewej do prawej, najpierw literom ze zbioru fa, s, i, n, t, o, e, rg przypisano liczby od 0 do 7; potem, pozosta(cid:7)ym literom przypisano liczby od 80 do 99: s 0 c 80 i 1 o 2 x 81 u 82 d 83 j 84 p 85 z 86 b 87 e 3 k 88 q 89 . 90 w 91 f 92 l 93 r 4 / 94 a 5 g 95 m 96 t 6 y 97 h 98 n 7 v 99 W ten spos(cid:243)b kwadrat Polibiusza oznaczony na stronie 72 znakiem ((cid:3)) otrzymano w bar- dziej zwi(cid:8)ez(cid:7)ej notacji. W przypadku cyrylicy odpowiedni jest podzia(cid:7) na siedem kod(cid:243)w jednocyfrowych oraz trzydzie·sci kod(cid:243)w dwucyfrowych, co w sumie daje 37 kod(cid:243)w i pozwala na u(cid:1)zycie 5 zna- k(cid:243)w specjalnych. W metodzie, kt(cid:243)r (cid:8)a zdradzi(cid:7) agent Reino Hayhanen, pomocnik wysoko postawionego szpiega rosyjskiego Rudolfa Abla, korzystano z rosyjskiego s(cid:7)owa (cid:132)sne- gopad(cid:148) [‘opady ·sniegu’], kt(cid:243)rego pierwszych siedem liter wyst(cid:8)epuje z (cid:7) (cid:8)aczn (cid:8)a cz(cid:8)esto·sci (cid:8)a 44,3 . Tablic(cid:8)e utworzon (cid:8)a jak zwykle: s n b v r t y ~ g e o d (cid:25) z u f h (cid:11) (cid:24) (cid:31) p i c . . k . . a j l m q x w (cid:127) . . . . przekszta(cid:7)cano za pomoc (cid:8)a klucza, kt(cid:243)ry by(cid:7) zmieniany od komunikatu do komunikatu, a kt(cid:243)ry mo(cid:1)zna by(cid:7)o znale·z·c w z g(cid:243)ry ustalonym miejscu zaszyfrowanej wiadomo·sci. Osta- tecznie dokonywano szyfrowania zamykaj (cid:8)acego (closing encryption (cid:151) podrozdzia(cid:7) 9.2.1.). 3.4.2. Rosyjskie (cid:7) (cid:8)aczenie. Przy tej okazji trzeba wyja·sni·c u(cid:1)zywan (cid:8)a przez Rosjan metod(cid:8)e, zwan (cid:8)a (cid:132)rosyjskim (cid:7) (cid:8)aczeniem(cid:148): wiadomo·s·c dzieli si(cid:8)e w niej na dwie cz(cid:8)e·sci mniej wi(cid:8)ecej tej samej d(cid:7)ugo·sci, po czym (cid:7) (cid:8)aczy si(cid:8)e je w odwrotnej kolejno·sci, ukrywaj (cid:8)ac w ten spos(cid:243)b gdzie·s po·srodku rzucaj (cid:8)ace si(cid:8)e w oczy wyra(cid:1)zenia, standardowo wyst(cid:8)epuj (cid:8)ace na pocz (cid:8)atku i na ko·ncu wiadomo·sci. Winston Churchill nazwa(cid:7) Rosj(cid:8)e (cid:132)a riddle wrapped in a mystery inside an enigma(cid:148) [(cid:132)zagadka otoczona tajemnic (cid:8)a niewiadomego(cid:148)]. To samo powiedzie·c mo(cid:1)zna o rosyjskiej kryptologii.
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Sekrety kryptografii
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ą: