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)
