Darmowy fragment publikacji:
Idź do
• Spis treści
• Przykładowy rozdział
• Skorowidz
Katalog książek
• Katalog online
• Zamów drukowany
katalog
Twój koszyk
• Dodaj do koszyka
Cennik i informacje
• Zamów informacje
o nowościach
• Zamów cennik
Czytelnia
• Fragmenty książek
online
Kontakt
Helion SA
ul. Kościuszki 1c
44-100 Gliwice
tel. 32 230 98 63
e-mail: helion@helion.pl
© Helion 1991–2011
Kryptografia i bezpieczeństwo
sieci komputerowych.
Matematyka szyfrów
i techniki kryptologii
Autor: William Stallings
Tłumaczenie: Andrzej Grażyński
ISBN: 978-83-246-2986-2
Tytuł oryginału: Cryptography and Network Security:
Principles and Practice (5th Edition) , vol. 1
Format: 170×230, stron: 760
Wykorzystaj fascynujące możliwości kryptografii
– zapewniaj bezpieczeństwo informacjom i sieciom komputerowym!
• Opanuj klasyczne techniki szyfrowania i wstęp do teorii liczb
• Poznaj skuteczne algorytmy ochrony integralności danych
• Stosuj kody uwierzytelniające komunikaty i podpisy cyfrowe
Wirusy, hakerzy, szpiegostwo gospodarcze, elektroniczne podsłuchy i kradzieże – era Internetu
ma także swoją ciemną stronę, która stawia przed nami coraz większe wyzwania w zakresie
bezpieczeństwa informacji. Dla większości przedsiębiorstw i organizacji kwestia ochrony dostępu
do danych przechowywanych w systemach komputerowych i wymienianych między nimi, a także
zachowania tajności wiadomości oraz skuteczne odpieranie ataków sieciowych, stała się
zagadnieniem krytycznym, mogącym przesądzać o ich istnieniu. Bezpieczeństwo sieci ma także
ogromne znaczenie także zwykłych użytkowników Internetu, często przetrzymujących na dyskach
ważne, poufne dokumenty i dokonujących za pomocą Sieci rozmaitych finansowych transakcji.Na
szczęście po ponad 20 latach od upowszechnienia się Internetu mamy już przetestowane w boju,
dojrzałe technologie i narzędzia związane z bezpieczeństwem sieci komputerowych i kryptografią,
które dają dziś naprawdę ogromne możliwości w tym zakresie. Jedyne czego Ci zatem potrzeba to
uzbroić się w wiedzę jak je skutecznie wykorzystać.
Oto pierwszy z dwóch tomów kompletnego przewodnika po praktycznych zastosowaniach
kryptografii i innych mechanizmów bezpieczeństwa w celu ochrony informacji i sieci. Ten
adresowany zarówno do studentów, jak i zawodowców podręcznik podzielono na trzy naszpikowane
wiedzą i ciekawymi przykładami części, wprowadzające kolejno w szyfry symetryczne, szyfry
asymetryczne i kryptograficzne algorytmy ochrony integralności danych. Znajdziesz tu omówienia
rozmaitych technologii związanych z bezpieczeństwem sieciowym, oraz poznasz metody ich
implementacji i zastosowania. Przeczytasz m.in na temat trybów operacyjnych szyfrów blokowych,
przyjrzysz się także standardowi AES i generowaniu liczb pseudolosowych. Otrzymasz obszerną,
porównawczą prezentację algorytmów kryptograficznych i doskonały przewodnik po metodach
uwierzytelniania i tematyce cyfrowego podpisu. Ponadto nauczysz się efektywnie wykorzystywać
system Sage - wieloplatformowe, darmowe narzędzie implementujące użyteczny, elastyczny
i łatwy do opanowania system obliczeń algebraicznych związanych z kryptografią. Znajdziesz
także gotowe dla tego systemu przykłady, ilustrujące praktyczne zastosowania teorii liczb
i algorytmów kryptograficznych.
SPIS TREŚCI
Notacja 11
Przedmowa 13
O autorze 23
Rozdział 0. Przewodnik po treści 25
0.1.
0.2.
0.3.
0.4.
Układ książki 26
Wskazówki dla czytelników i instruktorów 27
Zasoby internetowe 29
Standardy 31
Rozdział 1. Ogólny zarys bezpieczeństwa komputerowego 33
1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
1.7.
1.8.
Koncepcje bezpieczeństwa komputerowego 36
Architektura bezpieczeństwa OSI 42
Ataki na bezpieczeństwo 43
Usługi bezpieczeństwa 45
Mechanizmy bezpieczeństwa 51
Model bezpieczeństwa sieci 51
Zalecane materiały uzupełniające 55
Kluczowe terminy, pytania przeglądowe i problemy 57
CZĘŚĆ I
Rozdział 2. Klasyczne techniki szyfrowania 61
SZYFRY SYMETRYCZNE 61
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
Model szyfrowania symetrycznego 63
Techniki podstawieniowe 70
Techniki przestawieniowe 88
Maszyny wirnikowe 89
Steganografia 91
Zalecane materiały uzupełniające 94
Kluczowe terminy, pytania przeglądowe i problemy 95
Rozdział 3. Szyfry blokowe i standard DES 103
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
Podstawowe cechy szyfru blokowego 105
Standard DES 115
Przykład 124
Siła szyfru DES 127
Kryptoanaliza różnicowa i kryptoanaliza liniowa 129
Zasady projektowania szyfrów blokowych 133
5
6 SPIS TREŚCI
3.7.
3.8.
Zalecane materiały uzupełniające 138
Kluczowe terminy, pytania przeglądowe i problemy 139
Rozdział 4. Podstawy teorii liczb i ciał skończonych 145
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
Podzielność i algorytm dzielenia 147
Algorytm Euklidesa 149
Arytmetyka modularna 152
Grupy, pierścienie i ciała 162
Ciała skończone postaci GF(p) 166
Arytmetyka wielomianowa 170
Ciała skończone postaci GF(2n) 177
Zalecane materiały uzupełniające 189
Kluczowe terminy, pytania przeglądowe i problemy 190
Dodatek 4A. Znaczenie operatora mod 194
Rozdział 5. Standard AES 197
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
5.7.
5.8.
Arytmetyka ciał skończonych 198
Struktura AES 200
Funkcje transformacyjne AES 206
Rozwijanie klucza 218
Przykład zastosowania AES 220
Implementacja AES 224
Zalecane materiały uzupełniające 231
Kluczowe terminy, pytania przeglądowe i problemy 231
Dodatek 5A. Wielomiany o współczynnikach z GF(28) 233
Dodatek 5B. Uproszczony szyfr AES (S-AES) 236
Rozdział 6. Tryby operacyjne szyfrów blokowych 247
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.
6.7.
6.8.
6.9.
Wielokrotne szyfrowanie i potrójny DES 248
Tryb elektronicznej książki kodowej 254
Łańcuchowanie bloków szyfrogramu 257
Sprzężenie zwrotne szyfrogramu 259
Sprzężenie wyjściowe 261
Tryb licznikowy 263
Tryb XTS-AES dla urządzeń blokowych o orientacji sektorowej 266
Polecana strona WWW 271
Kluczowe terminy, pytania przeglądowe i problemy 272
Rozdział 7. Generatory liczb pseudolosowych i szyfry strumieniowe 277
7.1.
7.2.
7.3.
7.4.
7.5.
7.6.
Zasady generowania liczb pseudolosowych 278
Generatory liczb pseudolosowych 286
Generowanie liczb pseudolosowych na bazie szyfrów blokowych 289
Szyfry strumieniowe 293
RC4 295
Generatory liczb prawdziwie losowych 297
SPIS TREŚCI 7
7.7.
7.8.
Zalecane materiały uzupełniające 300
Kluczowe terminy, pytania przeglądowe i problemy 302
CZĘŚĆ II
Rozdział 8. Wstęp do teorii liczb 307
SZYFRY ASYMETRYCZNE 307
8.1.
8.2.
8.3.
8.4.
8.5.
8.6.
8.7.
Liczby pierwsze 309
Twierdzenia Fermata i Eulera 312
Testowanie, czy liczba jest pierwsza 316
Chińskie twierdzenie o resztach 320
Logarytmy dyskretne 322
Zalecane materiały uzupełniające 328
Kluczowe terminy, pytania przeglądowe i problemy 329
Rozdział 9. Kryptografia z kluczami publicznymi i szyfr RSA 333
9.1.
9.2.
9.3.
9.4.
Zasady funkcjonowania kryptosystemów z kluczami publicznymi 336
Algorytm RSA 346
Zalecane materiały uzupełniające 361
Kluczowe terminy, pytania przeglądowe i problemy 363
Dodatek 9A. Dowód poprawności algorytmu RSA 368
Dodatek 9B. Złożoność algorytmów 370
Rozdział 10. Inne systemy kryptografii z kluczami publicznymi 375
10.1.
10.2.
10.3.
10.4.
10.5.
10.6.
10.7.
Algorytm Diffiego-Hellmana wymiany kluczy 377
System kryptograficzny ElGamal 381
Arytmetyka krzywych eliptycznych 384
Kryptografia krzywych eliptycznych 394
Generatory liczb pseudolosowych bazujące na szyfrach asymetrycznych 397
Zalecane materiały uzupełniające 400
Kluczowe terminy, pytania przeglądowe i problemy 401
CZĘŚĆ III KRYPTOGRAFICZNE ALGORYTMY
OCHRONY INTEGRALNOŚCI DANYCH 405
Rozdział 11. Kryptograficzne funkcje haszujące 405
11.1.
11.2.
11.3.
11.4.
11.5.
11.6.
11.7.
11.8.
Zastosowania kryptograficznych funkcji haszujących 407
Dwie proste funkcje haszujące 411
Wymagania stawiane funkcjom haszującym 414
Funkcje haszujące bazujące na łańcuchowaniu szyfrogramów 422
Algorytmy rodziny SHA 423
SHA-3 433
Zalecane materiały uzupełniające 434
Kluczowe terminy, pytania przeglądowe i problemy 435
Dodatek 11A. Matematyczne podstawy paradoksu urodzin 439
8 SPIS TREŚCI
Rozdział 12. Uwierzytelnianie komunikatów 447
12.1.
12.2.
12.3.
12.4.
12.5.
12.6.
12.7.
12.8.
12.9.
12.10.
Wymagania stawiane uwierzytelnianiu komunikatów 449
Funkcje wykorzystywane do uwierzytelniania komunikatów 450
Wymagania stawiane kodom uwierzytelniania komunikatów 458
Bezpieczeństwo kodów uwierzytelniania komunikatów 461
Uwierzytelnianie komunikatów oparte na haszowaniu 463
Uwierzytelnianie komunikatów bazujące na szyfrach blokowych:
DAA i CMAC 468
Uwierzytelniane szyfrowanie: CCM i GCM 472
Generowanie liczb pseudolosowych za pomocą haszowania i kodów MAC 479
Zalecane materiały uzupełniające 482
Kluczowe terminy, pytania przeglądowe i problemy 483
Rozdział 13. Podpisy cyfrowe 487
Podpisy cyfrowe 489
Podpisy cyfrowe ElGamal 493
Schemat Schnorra podpisu cyfrowego 495
Standard DSS 496
Zalecane materiały uzupełniające 499
Kluczowe terminy, pytania przeglądowe i problemy 500
13.1.
13.2.
13.3.
13.4.
13.5.
13.6.
DODATKI 505
Dodatek A Projekty dydaktyczne 505
A.1.
A.2.
A.3.
A.4.
A.5.
A.6.
A.7.
A.8.
A.9.
System algebry komputerowej Sage 506
Projekt hackingu 507
Projekty związane z szyframi blokowymi 508
Ćwiczenia laboratoryjne 508
Projekty poszukiwawcze 509
Zadania programistyczne 509
Praktyczna ocena bezpieczeństwa 510
Wypracowania pisemne 510
Lektura tematu 511
Dodatek B Przykłady dla systemu Sage 513
B.1.
B.2.
B.3.
B.4.
B.5.
B.6.
B.7.
B.8.
B.9.
B.10.
B.11.
Algebra liniowa i operacje na macierzach 514
Rozdział 2. — klasyczne techniki szyfrowania 515
Rozdział 3. — szyfry blokowe i standard DES 518
Rozdział 4. — podstawy teorii liczb i ciał skończonych 521
Rozdział 5. — standard AES 526
Rozdział 7. — generatory liczb pseudolosowych i szyfry strumieniowe 530
Rozdział 8. — teoria liczb 532
Rozdział 9. — kryptografia z kluczami publicznymi i szyfr RSA 536
Rozdział 10. — inne systemy kryptografii z kluczami publicznymi 539
Rozdział 11. — kryptograficzne funkcje haszujące 544
Rozdział 13. — podpisy cyfrowe 545
SPIS TREŚCI 9
Dodatek C Ćwiczenia z systemem Sage 549
C.1.
C.2.
C.3.
C.4.
C.5.
C.6.
C.7.
C.8.
C.9.
C.10.
C.11.
C.12.
Sage — pierwszy kontakt 550
Programowanie w Sage 552
Rozdział 2. — klasyczne techniki szyfrowania 558
Rozdział 3. — szyfry blokowe i standard DES 559
Rozdział 4. — podstawy teorii liczb i ciał skończonych 560
Rozdział 5. — standard AES 562
Rozdział 7. — generatory liczb pseudolosowych i szyfry strumieniowe 565
Rozdział 8. — teoria liczb 566
Rozdział 9. — kryptografia z kluczami publicznymi i szyfr RSA 570
Rozdział 10. — inne systemy kryptografii z kluczami publicznymi 571
Rozdział 11. — kryptograficzne funkcje haszujące 574
Rozdział 13. — podpisy cyfrowe 575
Dodatek D Standardy i organizacje standaryzacyjne 577
D.1.
D.2.
D.3.
Dodatek E
E.1.
E.2.
Znaczenie standardów 578
Standardy internetowe i społeczność internetu 579
Narodowy Instytut Standaryzacji i Technologii (NIST) 583
Podstawowe koncepcje algebry liniowej 585
Operacje na wektorach i macierzach 586
Operacje algebry liniowej w arytmetyce zbioru Zn 590
Dodatek F Miara poufności i bezpieczeństwa kryptosystemów 591
F.1.
F.2.
F.3.
Poufność doskonała 592
Informacja i entropia 597
Entropia a poufność 603
Dodatek G Uproszczony szyfr DES (SDES) 605
G.1.
G.2.
G.3.
G.4.
G.5.
Ogólny schemat 606
Generowanie kluczy 608
Szyfrowanie 609
Analiza S-DES 612
Związek z DES 613
Dodatek H Kryteria ewaluacyjne dla standardu AES 615
H.1.
H.2.
Dodatek I
I.1.
I.2.
Geneza standardu AES 616
Ewaluacja AES 617
Trochę więcej na temat uproszczonego AES 623
Arytmetyka w ciele GF(24) 624
Funkcja MixColumns 624
10 SPIS TREŚCI
Dodatek J
J.1.
J.2.
J.3.
Algorytm plecakowy kryptografii z kluczami publicznymi 627
Problem plecakowy 628
Kryptosystem plecakowy 628
Przykład 632
Dodatek K Dowód poprawności algorytmu DSA 635
Dodatek L
L.1.
L.2.
L.3.
L.4.
L.5.
L.6.
Protokół TCP/IP i architektura OSI 637
Protokoły i architektury protokołów 638
Architektura protokołu TCP/IP 640
Rola protokołu IP 647
Protokół IP w wersji 4 (IPv4) 650
Protokół IP w wersji 6 (IPv6) 651
Architektura protokołów OSI 656
Dodatek M Biblioteki kryptograficzne języka Java 659
Architektura JCA i JCE 660
Klasy JCA 662
Klasy JCE 664
Podsumowanie 665
Publikacje cytowane 665
M.1.
M.2.
M.3.
M.4.
M.5.
Dodatek M.A Przykładowa aplikacja kryptograficzna 666
Dodatek M.B Kod źródłowy aplikacji — ilustracja zastosowania JCA/JCE 670
Dodatek N Whirlpool 701
N.1.
N.2.
Struktura funkcji Whirlpool 703
Szyfr blokowy W 706
Literatura cytowana 713
Dodatek O Algorytm ZIP 715
O.1.
O.2.
Algorytm kompresji 717
Algorytm dekompresji 718
Dodatek P Generowanie liczb losowych w PGP 721
P.1.
P.2.
Generowanie liczb prawdziwie losowych 722
Generowanie liczb pseudolosowych 722
Dodatek Q Międzynarodowy alfabet wzorcowy (IRA) 725
Słownik 731
Bibliografia 741
Skorowidz 749
CZĘŚĆ I SZYFRY SYMETRYCZNE
ROZDZIAŁ2
KLASYCZNE TECHNIKI SZYFROWANIA
2.1. Model szyfrowania symetrycznego
Kryptografia
Kryptoanaliza i atak siłowy
2.2.
Techniki podstawieniowe
Szyfr Cezara
Szyfry monoalfabetyczne
Szyfr Playfaira
Szyfr Hilla
Szyfry polialfabetyczne
Szyfr z kluczami jednorazowymi
Techniki przestawieniowe
2.3.
2.4. Maszyny wirnikowe
2.5.
2.6.
2.7. Kluczowe terminy, pytania przeglądowe i problemy
Steganografia
Zalecane materiały uzupełniające
61
62 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Jestem za pan brat ze wszystkimi formami tajemnego pisma, sam przecież jestem
autorem drobnej monografii na ten temat, w której analizuję 160 różnych szyfrów —
rzekł Holmes.
— The Adventure of the Dancing Men, Arthur Conan Doyle
KLUCZOWE POJĘCIA
Szyfrowanie symetryczne, zwane także szyfrowaniem konwencjonalnym, jest
odmianą kryptosystemu, w którym zarówno szyfrowanie, jak i deszyfracja wyko-
nywane są przy użyciu tego samego klucza.
Szyfrowanie symetryczne transformuje tekst jawny na szyfrogram przy użyciu
tajnego klucza i algorytmu szyfrowania. Stosując do szyfrogramu algorytm
odwrotny z tym samym kluczem, otrzymujemy z powrotem tekst jawny.
Dwa typy ataków, jakie intruzi mogą przypuścić na algorytm szyfrowania, to
kryptoanaliza bazująca na właściwościach tego algorytmu oraz atak siłowy
(brute-force) polegający na wypróbowywaniu wszystkich możliwych kluczy.
Tradycyjne (przedkomputerowe) szyfrowanie opiera się na dwóch technikach:
podstawieniowych i (lub) przestawieniowych. Techniki podstawieniowe doko-
nują odwzorowywania elementów tekstu jawnego (znaków lub bitów) na ele-
menty szyfrogramu, techniki przestawieniowe opierają się na systematycznych
zamianach pozycji elementów tekstu jawnego.
Maszyny wirnikowe to wymyślny sprzęt epoki przedkomputerowej, imple-
mentujący techniki podstawieniowe.
Steganografia to technika ukrywania tajnego komunikatu w obszerniejszym
strumieniu danych w taki sposób, by osoby niepowołane nie mogły nawet
zauważyć samego istnienia ukrytej informacji.
Szyfrowanie symetryczne, zwane również szyfrowaniem konwencjonalnym lub
szyfrowaniem z pojedynczym kluczem, było jedyną metodą szyfrowania do czasu
wynalezienia kryptografii z kluczami publicznymi w latach 70. ubiegłego stulecia,
i pozostaje do dziś dominującą techniką szyfrowania. W pierwszej części książki
omawiamy kilka szyfrów symetrycznych: ten rozdział rozpoczynamy od przed-
stawienia ogólnego modelu tego typu szyfrowania, co może okazać się pomocne
w zrozumieniu kontekstu, w jakim stosowane są symetryczne algorytmy szyfru-
jące. Następnie omawiamy kilka popularnych algorytmów, stosowanych szeroko
w czasach ery przedkomputerowej. Rozdział kończymy omówieniem kilku technik
określanych wspólnym mianem steganografii. W rozdziałach 3. i 5. omówimy
natomiast dwa najbardziej obecnie rozpowszechnione szyfry — DES i AES.
Na początek zdefiniujmy kilka podstawowych terminów. Oryginalny komuni-
kat, podlegający szyfrowaniu, nazywamy tekstem jawnym (plaintext), a wynik jego
zaszyfrowania — szyfrogramem (ciphertext). Proces konwertowania tekstu jaw-
2.1. / MODEL SZYFROWANIA SYMETRYCZNEGO 63
nego na szyfrogram nazywamy szyfrowaniem lub kryptażem (enciphering lub
encryption), zaś proces odwrotny, czyli odzyskiwanie tekstu jawnego na podstawie
szyfrogramu — deszyfracją lub dekryptażem (deciphering lub decryption). Ogół
schematów składających się na szyfrowanie, zwanych (po prostu) szyframi lub
systemami kryptograficznymi tworzy gałąź wiedzy zwaną kryptografią. Tech-
niki wykorzystywane do uzyskania tekstu jawnego bez jakiejkolwiek wiedzy doty-
czącej szczegółów szyfrowania określamy mianem kryptoanalizy — znanej także
jako „łamanie kodu”. Kryptografia i kryptoanaliza składają się na dziedzinę nauki
zwaną kryptologią.
2.1. MODEL SZYFROWANIA SYMETRYCZNEGO
Schemat szyfrowania symetrycznego składa się z pięciu elementów, którymi są
(patrz rysunek 2.1):
x Tekst jawny (plaintext) — oryginalny, czytelny komunikat (lub inne dane),
stanowiący materiał wejściowy dla algorytmu szyfrującego.
x Algorytm szyfrujący (encryption algorithm) — algorytm dokonujący roz-
maitych transformacji podstawieniowych i przestawieniowych na tekście
jawnym.
x Tajny klucz (secret key) — parametr wejściowy określający szczegóły dzia-
łania algorytmu szyfrującego, niezależny od samego algorytmu ani od teksu
jawnego. Zastosowanie różnych kluczy do tego samego tekstu jawnego
w tym samym czasie skutkuje różnymi wynikami — konkretne przestawie-
nia i podstawienia wykonywane przez algorytm zależne są od konkretnego
klucza.
x Szyfrogram (ciphertext) — zakodowany komunikat produkowany przez
algorytm szyfrujący, zależny od tekstu jawnego i użytego klucza. Dla danego
tekstu jawnego użycie dwóch różnych kluczy daje w efekcie różne szyfro-
gramy. Szyfrogram powinien mieć postać chaotycznego ciągu znaków,
sprawiającego złudzenie losowego, co sprawi, że będzie on nieczytelny
w sposób bezpośredni.
x Algorytm deszyfrujący (decryption algorithm) — algorytm odwrotny do
algorytmu szyfrującego, odtwarzający tekst jawny na podstawie szyfro-
gramu i klucza, przy użyciu którego szyfrogram ten został utworzony.
Aby szyfrowanie konwencjonalne mogło zapewnić odpowiedni poziom bez-
pieczeństwa, konieczne jest spełnienie dwóch wymagań:
1. Algorytm szyfrujący musi być na tyle solidny, by znający go intruz, dys-
ponujący dodatkowo zestawem szyfrogramów, nie był w stanie odtworzyć
tekstu jawnego bez znajomości użytego klucza (kluczy). W praktyce wyma-
ganie to formułowane jest w formie bardziej rygorystycznej: intruz nie
64 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Rysunek 2.1. Uproszczony model szyfrowania symetrycznego
powinien mieć możliwości odtworzenia użytego klucza (kluczy) nawet wów-
czas, gdy dysponuje zestawem odpowiadających sobie par „tekst jawny –
– szyfrogram”.
2. Nadawca i odbiorca muszą otrzymać kopie tajnego klucza w sposób bez-
pieczny i zachować je w tajemnicy. Gdy intruz pozna wspomniany klucz,
szyfrowanie przy użyciu tego klucza stanie się bezcelowe.
Transformacja przekształcająca tekst jawny na szyfrogram zależna jest od dwóch
elementów: algorytmu szyfrującego i klucza, a więc w celu zapewnienia jak najwięk-
szego bezpieczeństwa powinniśmy utrzymywać oba te elementy w tajemnicy. Mimo
to ze względów praktycznych rezygnuje się z utajniania algorytmu szyfrującego,
utrzymując w tajemnicy jedynie klucz. Ujawnienie używanego algorytmu szyfrują-
cego umożliwia producentom sprzętu jego implementowanie w seryjnie produko-
wanych (a więc tanich) chipach, które znajdować mogą zastosowanie w szerokiej
gamie produktów. Podstawowym problemem bezpieczeństwa przy szyfrowaniu
symetrycznym pozostaje zatem skuteczne utajnienie używanych kluczy.
Przyjrzyjmy się dokładniej rysunkowi 2.2, na którym zilustrowano schemat
szyfrowania symetrycznego. Generowany przez źródło komunikat, będący tek-
stem jawnym X = [X1, X2, …, XM], składa się z M elementów będących znakami
(literami) pewnego skończonego alfabetu. Tradycyjnie przyjmuje się w tej roli
26-literowy alfabet łaciński, choć większość współczesnych zastosowań opiera
się na alfabecie bitowym (binarnym) {0, 1}. W celu zaszyfrowania tekstu jaw-
nego należy wygenerować klucz K = [K1, K2, …, KJ]. Jeśli klucz generowany jest
w tym samym miejscu, co tekst jawny, pojawia się problem dostarczenia go odbiorcy
za pośrednictwem bezpiecznego kanału komunikacyjnego. Alternatywą jest wyge-
nerowanie klucza przez niezależny zaufany podmiot trzeci i bezpieczne dostar-
czenie go obu uczestnikom transmisji.
Traktując komunikat źródłowy X i klucz K jako informację wejściową dla
algorytmu szyfrującego E, produkującego szyfrogram Y, możemy wyrazić powiąza-
nie tych elementów w postaci wzoru
Y = E(K, X)
2.1. / MODEL SZYFROWANIA SYMETRYCZNEGO 65
Rysunek 2.2. Model szyfrowania symetrycznego
który można także rozumieć następująco: algorytm szyfrujący przekształca tekst
jawny X na szyfrogram Y, a szczegóły tego przekształcenia parametryzowane są
przez klucz K.
Uprawniony odbiorca komunikatu, dysponując kluczem K, potrafi odtworzyć
komunikat X za pomocą algorytmu deszyfrującego D:
X = D(K, Y)
Intruz (kryptoanalityk) dysponujący przechwyconym szyfrogramem Y, nie
znający jednak X ani K, może podjąć próbę odtworzenia X i (lub) K. Zakładamy,
że algorytmy E i D są powszechnie znane (również intruzowi). Jeżeli intruz zainte-
resowany jest odtworzeniem wyłącznie zaszyfrowanego tekstu jawnego X, jego
.
wysiłki koncentrować się będą na konstruowaniu przybliżenia tego tekstu X
Prawdopodobnie jednak intruz zainteresowany będzie także następnymi komuni-
katami, zmierzał więc będzie do konstruowania przybliżenia klucza K
.
Kryptografia
Każdy system kryptograficzny może być scharakteryzowany niezależnie pod
względem każdego z trzech następujących kryteriów:
1. Typu operacji przekształcających tekst jawny na szyfrogram. Wszystkie
algorytmy szyfrowania opierają się na dwojakiego typu operacjach: pod-
stawieniach, w ramach których każdy element tekstu jawnego (bit, litera,
grupa bitów, grupa liter) zastępowany jest przez inny element, oraz przesta-
wieniach (transpozycjach), polegających za zmianie kolejności wspo-
mnianych elementów. Wymaga się, aby operacje te były odwracalne, czyli
66 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
by szyfrowanie nie powodowało utraty informacji. Wiele systemów szyfro-
wania, zwanych systemami produktowymi (product systems) opiera się na
skomplikowanych, wieloetapowych kombinacjach podstawień i przestawień.
2. Liczby używanych kluczy. W sytuacji, gdy nadawca i odbiorca współdzielą
ten sam klucz, mówimy o szyfrowaniu symetrycznym, szyfrowaniu z poje-
dynczym kluczem, szyfrowaniu z kluczem tajnym lub szyfrowaniu kon-
wencjonalnym (są to oczywiście synonimy). Gdy nadawca posługuje się
kluczem innym niż odbiorca, mamy do czynienia z (ponownie synonimy)
szyfrowaniem asymetrycznym, szyfrowaniem z dwoma kluczami lub szyfro-
waniem z kluczami publicznymi.
3. Sposobu przetwarzania tekstu jawnego. Szyfrowanie blokowe polega na nie-
zależnym przekształcaniu poszczególnych bloków tekstu jawnego w odpo-
wiednie bloki szyfrogramu, podczas gdy szyfrowanie strumieniowe jest
sukcesywnym tworzeniem pojedynczego strumienia szyfrogramu drogą
przetwarzania kolejnych elementów tekstu jawnego, traktowanego także
jako pojedynczy strumień1.
Kryptoanaliza i atak siłowy
Zazwyczaj celem ataku na kryptosystem jest rozpoznanie wykorzystywanych klu-
czy, nie zaś rozpoznanie pojedynczego tekstu jawnego czy pojedynczego szyfro-
gramu. W przypadku szyfrowania konwencjonalnego do osiągnięcia tego celu
wykorzystywane są głównie dwie następujące techniki:
x Kryptoanaliza. Technika ta bazuje na znajomości natury algorytmu szyfru-
jącego i ewentualnie na pewnych ogólnych cechach tekstu jawnego bądź
pary „tekst jawny – szyfrogram”, a usiłowania stosującego ją intruza zmie-
rzają w kierunku rozpoznania bądź to stosowanego klucza, bądź jedynie
konkretnego tekstu jawnego.
x Atak siłowy (brute-force). Intruz dokonuje rozszyfrowywania szyfrogramu,
wypróbowując wszystkie możliwe klucze, aż do uzyskania tekstu stwarzają-
cego wrażenie (lub pozory) wiarygodności. W przeciętnym przypadku do
osiągnięcia sukcesu konieczne jest wypróbowanie połowy wszystkich moż-
liwych kluczy.
Gdy w wyniku którejkolwiek z tych technik uda się intruzowi wydedukować
stosowany klucz, będzie on mógł odtwarzać z przechwytywanych szyfrogramów
tekst jawny i całe szyfrowanie okaże się bezcelowe.
Zajmiemy się najpierw kryptoanalizą, po czym omówimy ataki siłowe.
W tabeli 2.1 widoczne jest zestawienie najczęściej stosowanych ataków kryp-
toanalitycznych, różniących się od siebie zestawem informacji, jaka dostępna
jest intruzowi. Najtrudniejsza jest dla niego sytuacja, gdy dysponuje on wyłącznie
1 W przeciwieństwie do szyfrowania blokowego przetwarzanie kolejnego elementu tekstu jaw-
nego uzależnione jest od stanu określonego przez wynik przetwarzania poprzednich elementów —
przyp. tłum.
2.1. / MODEL SZYFROWANIA SYMETRYCZNEGO 67
Tabela 2.1. Rodzaje ataków kryptoanalitycznych
Rodzaj ataku
Informacja dostępna dla kryptoanalityka
Atak z samym szyfrogramem
Atak ze znanym tekstem jawnym
• Algorytm szyfrujący
• Przechwycony szyfrogram
• Algorytm szyfrujący
• Przechwycony szyfrogram
• Jedna lub więcej par „tekst jawny – szyfrogram” utworzonych
przy użyciu tego samego klucza
Atak z wybranym tekstem jawnym • Algorytm szyfrujący
Atak z wybranym szyfrogramem
Atak z wybranym tekstem jawnym
i wybranym szyfrogramem
• Przechwycony szyfrogram
• Utworzony przez kryptoanalityka tekst jawny wraz
z odpowiadającym mu szyfrogramem, utworzonym przy użyciu
tajnego klucza
• Algorytm szyfrujący
• Przechwycony szyfrogram
• Utworzony przez kryptoanalityka szyfrogram wraz
z odpowiadającym mu tekstem jawnym, odtworzonym przy
użyciu tajnego klucza
• Algorytm szyfrujący
• Przechwycony szyfrogram
• Utworzony przez kryptoanalityka tekst jawny wraz
z odpowiadającym mu szyfrogramem, utworzonym przy użyciu
tajnego klucza
• Utworzony przez kryptoanalityka szyfrogram wraz
z odpowiadającym mu tekstem jawnym, odtworzonym przy
użyciu tajnego klucza
szyfrogramem i przypuszczalnie znajomością algorytmu deszyfrującego. Jedną
z możliwości jest wówczas przypuszczenie przez niego ataku siłowego, jednakże
w przypadku dużej liczby potencjalnie możliwych kluczy wypróbowanie ich
wszystkich jest niewykonalne, a przynajmniej niepraktyczne. Alternatywą dla
intruza jest więc wykorzystanie struktury szyfrogramu w drodze jego analizy sta-
tystycznej. Niezwykle pomocna może się wówczas okazać chociażby tylko ogólna
wiedza na temat natury tekstu jawnego, który może być tekstem w języku angiel-
skim czy francuskim, plikiem EXE, kodem programu w języku Java itp.
Najmniejsze szanse ma kryptoanalityk wówczas, gdy dysponuje tylko samym
szyfrogramem — powodzenie ataku jest wówczas najmniej prawdopodobne.
W wielu przypadkach kryptoanalityk dysponuje jednak bogatszą informacją,
między innymi może przechwycić kilka próbek tekstu jawnego wraz z odpowiada-
jącymi tym próbkom szyfrogramami. Użyteczna dla kryptoanalityka może być
również informacja o ogólnych cechach tekstu jawnego: jeśli na przykład wiadomo,
że przesyłany komunikat jest treścią pliku w formacie Postscript, to w ustalonych
miejscach tego komunikatu można spodziewać się obecności pewnych ustalonych
68 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
wzorców i zasada ta pozostaje prawdziwa dla większości formatów danych. Dys-
ponując wieloma egzemplarzami tekstu jawnego i wynikiem ich przekształcenia
na szyfrogramy przy użyciu tego samego klucza, kryptoanalityk może podjąć próbę
wydedukowania tego klucza — tego typu usiłowania określane są wspólnym mia-
nem ataku ze znanym tekstem jawnym.
Pokrewna forma ataku opiera się na występowaniu w tekście jawnym okre-
ślonych słów, dla których znane jest (być może w przybliżeniu) położenie w treści
komunikatu. Nie ma oczywiście takiej regularności zwykły tekst prozatorski, ale
na przykład w dokumencie opracowanym na zamówienie firmy X można spodzie-
wać się informacji o prawach autorskich, obejmującej nazwę tej firmy, a strumień
transmitujący kompletny plik danych księgowych przypuszczalnie zawiera na
początku znany nagłówek.
Jeszcze więcej szczęścia ma analityk dysponujący możliwością „podłożenia”
spreparowanego przez siebie tekstu jawnego na wejście systemu szyfrującego;
obserwując postać szyfrogramów uzyskiwanych na podstawie dowolnie kształ-
towanego (a nie przechwytywanego) tekstu jawnego, kryptoanalityk może dedu-
kować coraz trafniej postać klucza — na tej zasadzie opiera się kryptoanaliza różni-
cowa, o której piszemy w rozdziale 3. Ataki obejmujące możliwość dowolnego
preparowania tekstu jawnego, który następnie poddawany jest szyfrowaniu, nazy-
wane są ogólnie atakami z wybranym tekstem jawnym.
W analogiczny sposób może kryptoanalityk dokonywać deszyfracji dowolnie
preparowanych przez siebie danych, traktowanych jako szyfrogramy (co nosi
nazwę ataków z wybranym szyfrogramem), możliwe jest też połączenie obu spo-
sobów. Tego typu ataki (odpowiadają im dwa ostatnie wiersze tabeli 2.1), choć
stosowane rzadziej, wciąż są jednak możliwe.
Tylko kiepski algorytm szyfrujący daje kryptoanalitykowi duże szanse powo-
dzenia w przypadku ataku ze znanym szyfrogramem (pierwszy wiersz tabeli 2.1).
Generalnie od algorytmów szyfrujących wymaga się zdolności do skutecznego
opierania się atakom ze znanym tekstem jawnym.
Warto w tym miejscu przedstawić dwie definicje związane z jakością algo-
rytmu szyfrującego. Algorytm ten uważany jest za bezwarunkowo bezpieczny,
jeśli generowane przezeń szyfrogramy nie zawierają informacji wystarczającej
do jednoznacznego odtworzenia tekstu jawnego, niezależnie od tego jak obszerna
jest baza tych szyfrogramów. Jak zobaczymy nieco później w tym rozdziale, poza
schematem znanym jako „szyfrowanie z kluczem jednorazowym” nie istnieje algo-
rytm szyfrujący spełniający ten warunek. Bezpieczeństwo teoretyczne musi zatem
ustąpić miejsca podejściu praktycznemu — realne jest wymaganie spełnienia przez
algorytm szyfrujący przynajmniej jednego z poniższych kryteriów:
x koszt złamania szyfru jest większy od wartości zaszyfrowanej informacji;
x czas potrzebny na złamanie szyfru przekracza okres użyteczności zaszyfro-
wanej informacji.
Gdy algorytm szyfrujący spełnia którykolwiek z powyższych kryteriów, nazy-
wamy go obliczeniowo bezpiecznym. Niestety, oszacowanie czasochłonności
i pracochłonności złamania danego szyfru jest zadaniem niezmiernie trudnym.
2.1. / MODEL SZYFROWANIA SYMETRYCZNEGO 69
Wszystkie odmiany kryptoanalizy szyfrów symetrycznych wykorzystują praw-
dopodobieństwo, że pewna regularność tekstu otwartego znajduje swe odbicie
w pewnych charakterystycznych cechach szyfrogramu. Zasada ta stanie się dla
czytelników bardziej zrozumiała po omówieniu kilku przykładów szyfrowania
symetrycznego. Dla odmiany kryptoanaliza ukierunkowana na szyfrowanie z klu-
czami publicznymi opiera się na próbie wydedukowania klucza prywatnego na
podstawie zależności matematycznych wiążących go z kluczem publicznym.
Atak siłowy to mechaniczne wypróbowywanie kolejnych kluczy w nadziei,
że któryś z nich zastosowany do przechwyconego szyfrogramu da w rezultacie tekst
jawny przejawiający cechy autentyczności. W przeciętnym przypadku wymaga to
sprawdzenia połowy wszystkich możliwych kluczy, co przy ich dużej liczbie może
dyskwalifikować całe przedsięwzięcie już na starcie (no, może niekoniecznie,
wytrwałym szczęście sprzyja — teoretycznie możliwe jest, że już pierwszy spraw-
dzony klucz okaże się tym właściwym; zaufajmy jednak statystyce). W tabeli 2.2
widoczny jest rozmiar czasochłonności łamania szyfrów z kluczami różnych roz-
miarów. Klucz 56-bitowy wykorzystywany jest w algorytmie DES (Data Encryption
Standard), z klucza 168-bitowego korzysta natomiast algorytm „potrójnego DES”
(Triple DES). Algorytm AES (Advanced Encryption Standard) opiera się na kluczu
128-bitowym. Uwzględniono także klucz złożony z 26 liter alfabetu w określo-
nym ich uporządkowaniu. Dla każdego klucza podano przybliżony czas realizacji
ataku siłowego, prowadzonego przy wykorzystywaniu dwóch różnych rzędów mocy
obliczeniowych. Przeprowadzenie pojedynczego dekryptażu w czasie 1 mikrose-
kundy (10-6 s) odpowiada w przybliżeniu możliwościom dzisiejszych komputerów;
przy zastosowaniu masowego zrównoleglenia w systemach wieloprocesorowych
można jednak uzyskiwać rezultaty lepsze o kilka rzędów wielkości — w ostatniej
kolumnie tabeli podana jest czasochłonność łamania szyfru dla systemu zdolnego
sprawdzić milion kluczy w ciągu mikrosekundy. I jak łatwo zauważyć, przy tej mocy
obliczeniowej algorytm DES nie może być uważany za obliczeniowo bezpieczny.
Tabela 2.2. Średni czas potrzebny do wyczerpującego przeszukania przestrzeni możliwych kluczy
Liczba
możliwych
kluczy
232 | 4,3 × 109
256 | 7,2 × 1016
2128 | 3,4 × 1038
2168 | 3,7 × 1050
26! | 4 × 1026
Rozmiar klucza
32 bity
56 bitów
128 bitów
168 bitów
26 znaków
(w dowolnym
uporządkowaniu)
Czas potrzebny
w systemie
sprawdzającym jeden
klucz w ciągu Ps
231 Ps | 35,8 minuty
255 Ps | 1142 lata
2127 Ps | 5,4 × 1024 lat
2167 Ps | 5,9 × 1036 lat
2 × 1026 Ps | 6,4 × 1012 lat
Czas potrzebny w systemie
sprawdzającym milion kluczy
w ciągu Ps
2,15 milisekundy
10,01 godziny
5,4 × 1018 lat
5,4 × 1030 lat
6,4 × 106 lat
70 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
2.2. TECHNIKI PODSTAWIENIOWE
W tej i następnej sekcji przedstawimy przykłady kilku technik, które z racji histo-
rycznego znaczenia można uznać za klasyczne techniki szyfrowania. Ich dokładne
przeanalizowanie pozwoli lepiej zrozumieć obecne podejście do szyfrowania
symetrycznego, a także rozpoznać potencjalne typy możliwych ataków, którym
projektanci schematów szyfrowania muszą się a priori przeciwstawić.
Dwoma fundamentami każdej techniki szyfrowania są podstawienia i prze-
stawienia. Prześledzimy je dokładnie w dwóch kolejnych sekcjach, po czym zapre-
zentujmy metodę szyfrowania łączącą przestawienia z podstawieniami.
Podstawianiem (substitution) nazywamy technikę, w ramach której kolejne
litery tekstu jawnego zastępowane są określonymi literami, liczbami i symbolami.
Jeśli tekst jawny rozpatrywany jest jako ciąg bitów, wyodrębniane z niego kolejne
wzorce bitowe zastępowane są wzorcami bitowymi tworzącymi szyfrogram.
W dalszym ciągu książki dla polepszenia czytelności tekst jawny zapisywać
będziemy przy użyciu maïych liter, zaś szyfrogram — przy użyciu DU¿YCH
LITER. Klucze zapisywać będziemy maïymi pochylonymi literami.
Szyfr Cezara
Najstarsze znane, i zarazem najprostsze, zastosowanie techniki podstawieniowej
datuje się z czasów Juliusza Cezara. Szyfrowanie Cezara polega na zastępowaniu
każdej litery tekstu jawnego literą znajdującą się trzy pozycje dalej w alfabecie, co
zapisać można bardzo prosto w następującej postaci:
tekst jawny: 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
szyfrogram: 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 C
Zauważmy, że określenie „trzy pozycje dalej” należy rozumieć w sensie cyklicz-
nym — trzy ostatnie litery alfabetu zastępowane są trzema pierwszymi.
Tak więc przykładowy komunikat zostanie zaszyfrowany następująco:
tekst jawny: meet me after the toga party
szyfrogram: PHHW PH DIWHU WKH WRJD SDUWB
Przyporządkujmy każdej literze odpowiednik liczbowy:
a
0
n
13
b
1
o
14
c
2
p
15
d
3
q
16
e
4
r
17
f
5
s
18
g
6
t
19
h
7
u
20
i
8
v
21
j
9
w
22
k
10
x
23
l
11
y
24
m
12
z
25
Wówczas algorytm realizujący szyfrowanie Cezara będzie można formalnie zapisać
następująco:
2.2. / TECHNIKI PODSTAWIENIOWE 71
każdą literę p tekstu jawnego zastępujemy literą szyfrogramu C
wyznaczoną według formuły2
C = E(3, p) = (p + 3) mod 26
Regułę tę można w oczywisty sposób uogólnić
na dowolną wartość przesunięcia, traktowanego jako klucz:
C = E(k, p) = (p + k) mod 26
(2.1)
gdzie k może przyjmować wartości od 1 do 25. Z formuły (2.1)
wynika formuła algorytmu deszyfrującego:
p = D(k, C) = (C – k) mod 26
(2.2)
Ponieważ k może przyjmować tylko 25 różnych wartości, więc kryptoanalityk
z powodzeniem zastosować może atak siłowy. Potencjalny efekt jego eksperymen-
tów uwidoczniony jest na rysunku 2.3 — jedynie w trzecim wierszu znajduje się
sensowny tekst.
Rysunek 2.3. Złamanie szyfru Cezara metodą
ataku siłowego
2 Zapis a mod b oznacza resztę z dzielenia a przez b, na przykład 11 mod 7 = 4.
72 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Zauważmy, że powodzenie ataku siłowego wynika w tym przypadku z trzech
następujących faktów:
1. Znane są algorytmy szyfrujący i deszyfrujący.
2. Liczba możliwych kluczy jest niewielka.
3. Język, w jakim zapisano tekst jawny, jest znany i łatwo rozpoznawalny.
W większości sytuacji wziętych z codziennej rzeczywistości spełniony jest
warunek 1., o czym pisaliśmy już wcześniej w tym rozdziale. Tym, co generalnie
skazuje na niepowodzenie większość ataków siłowych, jest niespełnienie warunku 2.:
w przypadku szyfru „potrójnego DES” (opisywanego w rozdziale 6.) liczba moż-
liwych kluczy wynosi 2168 | 3,7 × 1050.
Nie bez znaczenia jest także trzecia z wymienionych przesłanek. Jeżeli język
tekstu jawnego nie jest znany, trafienie na właściwy klucz może zostać po prostu
niezauważone. Ponadto sam tekst jawny może zostać przed zaszyfrowaniem pod-
dany kompresji lub innym przekształceniom redukującym, co dodatkowo utrud-
nia jego zrozumienie. Na rysunku 2.4 widoczny jest fragment archiwum .ZIP
w oknie edytora tekstowego. Gdyby zbiór ten został zaszyfrowany zwykłą techniką
podstawieniową, fakt jego rozszyfrowania za pomocą ataku siłowego mógłby
pozostać niezauważony3.
Rysunek 2.4. Fragment (znakowej) zawartości skompresowanego pliku
Szyfry monoalfabetyczne
Z 25-elementową przestrzenią kluczy szyfr Cezara zdecydowanie nie zasługuje
na miano bezpiecznego. Drastyczne zwiększenie liczebności tej przestrzeni można
uzyskać, komplikując reguły podstawiania. Dla danego skończonego zbioru S
3 Ale uwaga: pliki takie jak archiwa cechują się pewnym stopniem redundancji. Aby archiwum
zostało poprawnie obsłużone przez archiwizator, musi m.in. posiadać poprawny nagłówek, poprawne
sumy kontrolne itp. Nieoczekiwanie fakt skompresowania tekstu otwartego archiwizatorem ZIP
może ułatwić zadanie kryptoanalitykowi, daje mu bowiem bardzo wygodne narzędzie weryfiko-
wania trafności wyboru klucza: po deszyfracji należy po prostu uruchomić program PKZIP (oczy-
wiście, o ile wie, że zaszyfrowanym plikiem jest archiwum ZIP) — udane uruchomienie archiwizatora
(kod powrotu 0) oznacza prawdopodobne trafienie we właściwy klucz — przyp. tłum.
2.2. / TECHNIKI PODSTAWIENIOWE 73
definiujemy jego uporządkowanie4 jako dowolny ciąg, w którym każdy element
tego zbioru występuje dokładnie raz. Przykładowo: dla zbioru S = {a, b, c} istnieje
sześć różnych uporządkowań: abc, acb, bac, bca, cab, cba. Ogólnie dla
n-elementowego zbioru istnieje dokładnie n! różnych uporządkowań, ponieważ
pierwszy element ciągu wybrać można na n sposobów, drugi — na (n – 1) spo-
sobów, trzeci — na (n – 2) sposoby itd., wobec czego liczba możliwych wariantów
wyboru wynosi
n × (n – 1) × (n – 2) × … × 2 × 1 = n!
Przywołajmy ponownie szyfr Cezara:
tekst jawny: 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
szyfrogram: 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 C
jeżeli dopuścimy, by wiersz „szyfrogram” zawierał dowolne uporządkowanie
zbioru 26 liter, liczba możliwych kluczy zwiększa się do wartości 26! | 4 × 1026.
Daje to przestrzeń o liczebności 10 rzędów większej niż liczba możliwych kluczy
szyfru DES, co powinno zdecydowanie podziałać zniechęcająco na amatora ataku
siłowego. Ponieważ (dla każdego konkretnego uporządkowania) reguły zastę-
powania są ustalone dla całego komunikatu — nie zmienia się „alfabet kodowy”
w wierszu szyfrogram — ten rodzaj podstawiania nazywamy szyfrowaniem
monoalfabetycznym.
Co prawda 27-cyfrowa liczba możliwych kluczy do sprawdzenia dyskwalifikuje
na starcie próby ataku siłowego, lecz kryptoanalityk dysponuje ponadto innymi,
bardziej obiecującymi metodami. Jeśli mianowicie zna on naturę tekstu jawnego
(na przykład wie, że jest to zwykły tekst w języku angielskim), może wykorzystywać
pewne cechy charakterystyczne dla tegoż języka. Weźmy przykładowy szyfrogram,
zaczerpnięty z książki [SINK66]:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
Dla szyfrogramu tego można wykonać analizę częstości występowania poszcze-
gólnych liter i skonfrontować jej wyniki ze statystyką występowania poszczególnych
liter w zwykłym tekście anglojęzycznym (histogram widoczny na rysunku 2.5
zaczerpnięty został z pracy [LEWA00]). Dla dostatecznie długiego komunikatu
konfrontacja ta może okazać się wystarczająca; w naszym przykładzie komunikat
jest stosunkowo krótki, więc można się wpierw spodziewać jedynie przybliżonego
wyniku. Rozkład (w procentach) częstości występowania poszczególnych liter
w szyfrogramie wygląda tak:
4 W amerykańskim wydaniu tej książki opisane przekształcenie zbioru elementów na ich ciąg
nazywane jest permutacją. Może to być mylące, w algebrze bowiem „permutacja” definiowana jest
jako wzajemnie jednoznaczne przekształcenie danego zbioru na siebie. By uniknąć wynikającej
stąd dwuznaczności, stosowany będzie w zamian termin „uporządkowanie” — przyp. tłum.
74 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Rysunek 2.5. Względna częstotliwość występowania poszczególnych liter w tekstach w języku
angielskim5
P 13,33
Z 11,67
S 8,33
U 8,33
O 7,50
M 6,67
H 5,83
D 5,00
E 5,00
V 4,17
X 4.17
F 3,33
W 3,33
Q 2,50
T 2,50
A 1,67
B 1,67
G 1,67
Y 1,67
I 0,83
J 0,83
C 0,00
K 0,00
L 0,00
N 0,00
R 0,00
Porównanie obu statystyk sugeruje, że litery P i Z, jako występujące w szy-
frogramie najczęściej, odpowiadają literom e i t tekstu jawnego, chociaż nie
wiadomo jeszcze, która jest która. Litery S, U, O, M i H o względnie dużej częstotli-
wości odpowiadają literom ze zbioru [a, h, i, n, o, r, s]. Litery występujące
w szyfrogramie najrzadziej — A, B, G, Y, I, J — mają najprawdopodobniej swe
odpowiedniki w zbiorze [b, j, k, q, v, x, z].
Posiadając tę wiedzę, moglibyśmy metodą prób i błędów dojść do jakiegoś
sensownego „szkieletu” poszukiwanego komunikatu, możliwe jest jednak inne,
bardziej systematyczne podejście, eksploatujące inne regularności typowe dla języka
angielskiego, na przykład duże prawdopodobieństwo obecności określonych słów
w każdym niemal tekście czy też powtarzające się sekwencje liter mające swe
odzwierciedlenie w podobnych powtórzeniach w ramach szyfrogramu.
5 Częstotliwość występowania poszczególnych liter w tekstach w języku polskim można znaleźć na
stronie: http://pl.wikipedia.org/wiki/Alfabet_polski
2.2. / TECHNIKI PODSTAWIENIOWE 75
Powróćmy jednak do statystyki. Wykres podobny do widocznego na rysunku 2.5
można sporządzić również w odniesieniu do dwuznaków (zwanych także digra-
mami) — w języku angielskim najczęściej występującym dwuznakiem jest th.
W naszym szyfrogramie najczęściej powtarzającym się jest dwuznak ZW, który
występuje trzykrotnie. Wnioskujemy stąd, że Z odpowiada literze t, zaś W — lite-
rze h. Wcześniejsze spostrzeżenie dotyczące liter P i Z pozwala nam na stwier-
dzenie, że P odpowiada literze e. Zatem sekwencja ZWP w szyfrogramie odpo-
wiada sekwencji the w tekście jawnym. To najczęściej występujący w języku
angielskim trójznak (trigram), co pozwala nam sądzić, że jesteśmy na dobrej
drodze.
Zwróćmy następnie uwagę na sekwencję ZWSZ w pierwszym wierszu. Nie ma
pewności, że odpowiada ona pełnemu słowu, ale jeśli tak jest, słowo to musi mieć
postać th_t, prawdopodobnie więc odpowiednikiem S jest a.
Reasumując, dotychczas otrzymaliśmy następujący wynik:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
t a e e te a that e e a a t
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
e t ta t ha e ee a e th t a
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
e e e tat e the t
Mimo iż udało nam się odgadnąć tylko cztery litery tekstu jawnego, uzyskaliśmy
już dość znaczną część całego tekstu. Kontynuując dedukcję metodą prób i błędów,
a na końcu wstawiając spacje rozdzielające słowa, otrzymamy ostatecznie test
otwarty:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow
Szyfry monoalfabetyczne poddają się kryptoanalizie o tyle łatwo, że w szyfro-
gramie odzwierciedlona zostaje statystyka wystąpień poszczególnych znaków i ich
sekwencji w tekście jawnym. Tę odpowiedniość można jednak wyraźnie osłabić,
stosując dla określonej litery tekstu jawnego kilka różnych odpowiedników zwa-
nych homofonami, na przykład zastępując literę e jedną z liczb 16, 74, 35 i 21 —
przyporządkowanie kolejnych homofonów danej literze tekstu jawnego może
zmieniać się cyklicznie lub w sposób losowy. Jeżeli liczba homofonów odpowia-
dających danej literze będzie tym większa, im częściej litera ta występuje w tekście
jawnym, to statystyka wystąpień poszczególnych znaków w tekście jawnym zatraci
się prawie kompletnie w szyfrogramie. Pomysłodawca tej zasady, wielki matema-
tyk Carl redrich Gauss wierzył, że wykorzystywanie homofonów uczyni szyfrowa-
nie praktycznie niemożliwym do złamania. Jednak nawet użycie homofonów nie
zmienia faktu, że jeden znak tekstu otwartego odwzorowywany jest na jeden znak
szyfrogramu, i statystyka wystąpień sekwencji znaków (między innymi dwu- i trój-
znaków) zachowywana jest w szyfrogramie.
W celu osłabienia stopnia, w jakim rozmaite statystyki tekstu jawnego odzwier-
ciedlane są w szyfrogramie, zaproponowano dwa podejścia: rozpatrywanie tekstu
76 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
jawnego w podziale nie na pojedyncze litery, a na jednostki wieloliterowe oraz
wykorzystywanie wielu alfabetów szyfrogramu zamiast pojedynczego alfabetu.
Omówimy krótko każde z nich.
Szyfr Playfaira
Najbardziej znanym przykładem rozpatrywania tekstu jawnego w podziale na
sekwencje wieloznakowe jest szyfr Playfaira6, w którym tekst jawny dzielony jest na
dwuznaki.
Podstawą szyfru jest macierz znaków o rozmiarze 5×5. W alfabecie utożsa-
miamy ze sobą litery I oraz J, dzięki czemu liczba liter redukuje się do 25. Ich
określone rozmieszczenie we wspomnianej macierzy jest kluczem szyfru. Roz-
poczynamy od wyboru słowa kluczowego: nie może ono zawierać powtórzeń
liter, a jeżeli powtórzenia jednak występują, należy je wyeliminować — i tak na
przykład słowo jaundicing zredukowane zostanie w wyniku tego zabiegu do
słowa jaundcg (pamiętajmy o utożsamieniu i oraz j). Słowo kluczowe wpisu-
jemy do macierzy, poruszając się po kolejnych wierszach od lewej do prawej, z góry
na dół. Następnie wpisujemy w kolejności alfabetycznej pozostałe litery nieobecne
w słowie kluczowym. Dla słowa kluczowego monarchy macierz Playfaira przyjmie
zatem postać następującą7:
N
Y
G
Q
A
M O
B
C
H
I/J
F
E
P
L
S
V W X
U
R
D
K
T
Z
Szyfrowanie tekstu jawnego odbywa się kolejnymi dwuznakami. Każdy dwu-
znak musi zawierać różne znaki; jeśli postać tekstu jawnego prowadzi do naru-
szenia tej zasady, należy sztucznie rozdzielić bliźniacze znaki jakimś „neutralnym”
znakiem, tak by nie powodowało to zmiany znaczenia tekstu. Dla tekstu jawnego
balloon, używając w tym celu litery x, otrzymujemy podział na dwuznaki ba
lx lo on. Każdy dwuznak tekstu jawnego odwzorowywany jest na dwuznak
szyfrogramu, przy czym w zależności od wzajemnego położenia składników dwu-
znaku w macierzy Playfaira wyróżniamy trzy przypadki:
1. Gdy oba składniki leżą w tym samym wierszu macierzy, zastępujemy każdy
z nich prawostronnym następnikiem; prawostronnym następnikiem dla
ostatniego znaku w wierszu jest pierwszy znak tego wiersza. Formalnie
6 Opisywany szyfr wynaleziony został w 1854 roku przez Charlesa Wheatstone’a, swoją nazwę
zawdzięcza jednak baronowi Lyonowi Playfairowi, szkockiemu naukowcowi i parlamentarzyście,
który w latach 1873 – 1874 pełnił ministerialną funkcję generalnego poczmistrza.
7 Przykład pochodzi z książki Dorothy Sayers Have His Carcase.
2.2. / TECHNIKI PODSTAWIENIOWE 77
zatem rzecz biorąc, dwuznak PijPim (P oznacza macierz Playfaira) odwzoro-
wany zostaje na dwuznak Pi,next(j)Pi,next(m), gdzie next() jest funkcją następnika:
next
i
i
®
1
¯
dla1
dla
i
i
5
5
Zatem na przykład dwuznak ar odwzorowywany jest na dwuznak RM.
2. Analogicznie gdy oba składniki leżą w tej samej kolumnie macierzy, zastę-
pujemy każdy z nich dolnym następnikiem; dla ostatniego wiersza wierszem
następnym jest pierwszy wiersz. Formalnie dwuznak PijPkj odwzorowany
zostaje na dwuznak Pnext(i),jPnext(k),j, na przykład dwuznak mu odwzorowywany
jest na dwuznak CM.
3. W pozostałym przypadku, to znaczy w sytuacji, gdy składniki dwuznaku
leżą w różnych wierszach i różnych kolumnach, stosujemy tzw. uzupeł-
nienie prostokątne: obrazem składnika jest element leżący w tym samym
wierszu i kolumnie partnera. Formalnie dwuznak PijPkm odwzorowany
zostaje na dwuznak PimPkj, na przykład dwuznak bp odwzorowywany jest
na dwuznak IM (albo JM, do wyboru)8.
Szyfr Playfaira ma ogromną przewagę nad prostymi szyframi monoalfabe-
tycznymi między innymi z tego względu, że zamiast 26 znaków mamy 26×26 = 676
dwuznaków, których indywidualna identyfikacja staje się z tego powodu znacz-
nie utrudniona. Ponadto względne częstotliwości występowania poszczególnych
liter wykazują znaczne zróżnicowanie w porównaniu z rozkładem częstotliwości
dwuznaków, co czyni kryptoanalizę jeszcze trudniejszą. Z tego powodu szyfr
Playfaira uważany był przez długi czas za wyjątkowo bezpieczny; wykorzystywany
był w czasie I wojny światowej przez armię brytyjską oraz przez armię USA i alian-
tów podczas II wojny.
Pomimo jednak tak wielkiego zaufania szyfr Playfaira okazuje się niezbyt
trudny do złamania, ponieważ produkowane przy jego użyciu szyfrogramy wciąż
zachowują wiele cech struktury używanego języka; w praktyce kilkaset liter szyfro-
gramu okazuje się wystarczające do odtworzenia tekstu jawnego.
Jeden ze sposobów oceny efektywności szyfru Playfaira i innych szyfrów
opiera się na specyficznej analizie częstotliwości wystąpień poszczególnych liter,
której rezultaty widoczne są na rysunku 2.6, zaczerpniętym z pracy [SIMM93]9.
8 Zobaczmy przy okazji, skąd — w kontekście powyższych reguł — bierze się konieczność
unikania bliźniaczych dwuznaków w tekście jawnym. Gdybyśmy takowe dopuścili (załóżmy dla
ustalenia uwagi, że wejściowym dwuznakiem jest FF), można by dla nich zastosować regułę 1. (dla
FF otrzymalibyśmy wtedy wynik GG) albo regułę 2. (co dla FF dałoby wynik PP). I pojawiłaby się
niejednoznaczność, bo napotykając w szyfrogramie bliźniaczy dwuznak, nie potrafilibyśmy okre-
ślić, na mocy której reguły został on utworzony: PP mogłoby być obrazem zarówno LL (reguła 1.),
jak i FF (reguła 2.). Oczywiście zdefiniowanie dodatkowej reguły mogłoby rozwiązać ten problem,
jednak tak czy inaczej, obrazem bliźniaczego dwuznaku w tekście jawnym musiałby być bliźniaczy
dwuznak szyfrogramie (co okazuje się oczywiste, gdy próbuje się zaprzeczyć temu stwierdzeniu),
a to mogłoby być dla potencjalnego kryptoanalityka znacznym ułatwieniem — przyp. tłum.
9 Dziękuję Gustavusowi Simmonsowi za udostępnienie wykresu i wyjaśnienie metody jego
sporządzenia.
78 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Linia zatytułowana „tekst jawny” odzwierciedla rozkład częstotliwości poszcze-
gólnych liter w tekście liczącym ich ponad 70 000, składających się na artykuł
o kryptografii w Encyclopaedia Britannica. Liczby na osi poziomej reprezentują
poszczególne litery uszeregowane w kolejności malejących częstości występo-
wania — dla każdego z rozważanych szyfrów odpowiedniość między liczbami
a literami jest oczywiście inna. Konkretna postać tej odpowiedniości nie jest
zresztą istotna, bo znacznie ważniejsze jest tu co innego, a mianowicie zróżnicowa-
nie wspomnianej częstotliwości dla poszczególnych szyfrogramów. Szyfrogramy te
utworzono ze wspomnianego tekstu jawnego przy użyciu różnych algorytmów
szyfrujących, a wykresy ilustrujące dystrybucję poszczególnych liter sporządzono,
zliczając ich wystąpienia i dzieląc otrzymane liczniki przez liczbę wystąpień litery e
(jako najczęstszej) w tekście jawnym. Dla tekstu jawnego otrzymujemy więc wskaź-
nik 100 dla litery e, ok. 76 dla litery a itd.
Rysunek 2.6. Względna częstotliwość występowania liter w tekście jawnym i różnych
szyfrogramach
Dzięki opisanej normalizacji wykres widoczny na rysunku 2.6 może stanowić
znakomity przyczynek do dyskusji o tym, w jakim stopniu szyfrowanie jest w sta-
nie zamaskować dystrybucję występowania poszczególnych liter w tekście jaw-
nym. Jeśli dla danego szyfru maskowanie to ma rozmiar totalny, wykres dystrybu-
cji znaków dla tego szyfru powinien być płaską linią — kryptoanaliza jest wtedy
praktycznie niemożliwa. Jak widać, dla szyfru Playfaira wspomniana linia jest
bardziej spłaszczona niż w przypadku tekstu jawnego, mimo to szyfr ten odzwier-
ciedla w znaczącym stopniu oryginalną dystrybucję poszczególnych znaków.
2.2. / TECHNIKI PODSTAWIENIOWE 79
Szyfr Hilla
Inny interesujący szyfr wieloliterowy wynaleziony został w 1929 roku przez
matematyka Lestera Hilla. Szyfr ten bazuje na arytmetyce macierzowej modulo 26,
dlatego na wstępie przypomnimy kilka niezbędnych faktów z zakresu algebry
liniowej; czytelnika zainteresowanego szczegółami mnożenia i odwracania macie-
rzy odsyłamy do dodatku E10.
PODSTAWOWE KONCEPCJE ARYTMETYKI MACIERZOWEJ
Macierzą odwrotną do macierzy kwadratowej M, oznaczaną M–1, jest macierz
spełniająca warunek M(M–1) = M–1M= I, gdzie I jest macierzą jednostkową, czyli
macierzą posiadającą jedynki na głównej przekątnej i zera poza nią. Nie dla każdej
macierzy istnieje macierz odwrotna, ale jeśli istnieje, spełnia wspomniany warunek.
Przykładowo
Dla wyjaśnienia, jak oblicza się macierz odwrotną, zdefiniujemy pojęcie
wyznacznika (ang. determinant). Dla macierzy kwadratowej tworzymy wszelkie
możliwe iloczyny jej elementów, takie że każdy element pochodzi z innego wiersza
i z innej kolumny. Zależnie od wzajemnego układu wierszy i kolumn elementów
tworzących dany iloczyn zmieniamy jego znak lub pozostawiamy znak bez zmiany.
Tak otrzymane n! iloczynów (n jest wymiarem macierzy) dodajemy do siebie —
otrzymana suma jest rzeczonym wyznacznikiem; wyznacznik macierzy M ozna-
czamy det M. Przykładowo dla macierzy o wymiarze 2×2
wyznacznik równy jest k11k22 – k12k21, zaś dla macierzy rozmiaru 3×3 jest on
równy k11k22k33 + k21k32k13 + k31k12k23 – k31k22k13 – k21k12k33 – k11k32k23. Macierz,
której wyznacznik jest zerowy, nazywa się macierzą osobliwą. Niezerowość
wyznacznika, czyli nieosobliwość macierzy jest warunkiem koniecznym i wystar-
czającym istnienia macierzy do niej odwrotnej. Elementy macierzy odwrotnej obli-
czamy z równości
[A–1]ij = (det A)–1(–1)i+j(Dij)
10 Ten szyfr jest być może nieco trudniejszy do zrozumienia niż inne szyfry opisywane w tym
rozdziale, ilustruje jednak pewną istotną kwestię związaną z kryptoanalizą. Przy pierwszym czytaniu
można tę podsekcję pominąć.
80 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
gdzie Dij jest podwyznacznikiem, czyli wyznacznikiem macierzy powstającej
z macierzy A przez usunięcie jej i-tego wiersza i j-tej kolumny. (det A)–1 oznacza
multiplikatywną odwrotność wyznacznika det A modulo 26
(det A)–1 × (det A) mod 26 = 1
Powracając do naszego przykładu
Liczba 3 jest multiplikatywną odwrotnością liczby 9, ponieważ (3×9) mod
26 = 27 mod 26 = 1 (patrz rozdział 4. lub dodatek E). Zatem macierzą odwrotną
modulo 26 do macierzy
jest macierz11
ALGORYTM HILLA
Algorytm szyfrujący Hilla traktuje tekst jawny jako ciąg m-literowych sekwencji
znaków — każda z tych sekwencji przekształcana jest na m-literową sekwencję
szyfrogramu. Przekształcenie to realizowane jest przez m równań liniowych,
w których zarówno litery tekstu jawnego, jak i litery szyfrogramu traktowane są
jako wartości numeryczne (a = 0, b = 1, …, z = 25); każde równanie określa jeden
znak szyfrogramu. Przykładowo dla m = 3 mamy
)
)
)
26
26
26
co w zapisie macierzowym prezentuje się następująco12:
pk
(
1
11
pk
(
1
21
pk
(
1
31
pk
13
3
pk
23
pk
33
mod
mod
mod
pk
12
2
pk
22
pk
32
2
2
3
3
c
1
c
2
c
3
11 Znaki równości oznaczają tu przystawanie modulo 26 — przyp. tłum.
12 W niektórych książkach poświęconych kryptografii zarówno tekst jawny, jak i szyfrogram
reprezentowane są w postaci wektorów kolumnowych, jako takich mnożonych lewostronnie przez
macierz (w przeciwieństwie do wektorów wierszowych mnożonych prawostronnie). Przyjęliśmy
konwencję wektorów wierszowych, taka bowiem stosowana jest w systemie Sage. W rezultacie jednak
zwyczajowe mnożenie
przyjmuje teraz postać
.
2.2. / TECHNIKI PODSTAWIENIOWE 81
lub krócej
C = PK mod 26
gdzie C i P są wektorami wierszowymi o rozmiarze 3, reprezentującymi (odpo-
wiednio) szyfrogram i tekst jawny, zaś K jest macierzą o rozmiarze 3×3 repre-
zentującą klucz szyfru. Jako przykład prześledźmy szyfrowanie tekstu jawnego
paymoremoney za pomocą klucza
Sekwencja trzech pierwszych liter tekstu jawnego reprezentowana jest przez wektor
wierszowy (15 0 24), mamy zatem
(15 0 24)K mod 26 = (303 303 531) mod 26 = (17 17 11) = RRL
Powtarzając to postępowanie, otrzymamy kompletny szyfrogram RRLMWBKA
´SPDH.
Deszyfracja wykonywana jest za pomocą macierzy odwrotnej do macierzy K:
Obliczamy det K = 23, (det K)–1 mod 26 = 17 oraz
P = CK–1
Istotnie
Można łatwo okazać, że zastosowanie macierzy K–1 do szyfrogramu da w rezul-
tacie tekst jawny.
Formalnie rzecz biorąc, szyfrowanie Hilla można zapisać w następującej postaci
C = E(K, P) = PK mod 26
P = D(K, C) = PKK–1 mod 26 = P
Podobnie jak w przypadku szyfru Playfaira bezpieczeństwo szyfru Hilla wynika
stąd, że w szyfrogramie brakuje informacji na temat dystrybucji pojedynczych
znaków w tekście jawnym. Efekt maskujący jest tym lepszy, im większy rozmiar
ma macierz K; użycie macierzy 3×3 maskuje dystrybucję nie tylko pojedynczych
znaków, lecz także dystrybucję dwuznaków.
82 ROZDZIAŁ 2. / KLASYCZNE TECHNIKI SZYFROWANIA
Mimo iż szyfr Hilla potrafi znakomicie przeciwstawić się atakowi ze znanym
szyfrogramem, to może być stosunkowo łatwo załamany za pomocą ataku ze zna-
nym tekstem jawnym. Załóżmy, że macierz kluczowa ma rozmiar m×m i kryp-
toanalityk dysponuje m parami „tekst jawny – szyfrogram”, przy czym w każdej
parze tekst jawny i szyfrogram mają długość po m znaków. Oznaczmy każdą parę
jako ¢Pj, Cj²:
Wówczas
Pj = (pj1 pj2 … pjm)
Cj = (cj1 cj2 … cjm)
Cj = PjK
mj dd1
dla
o rozmiarze m×m, takie że
i pewnej nieznanej macierzy K. Tworzymy dwie macierze, X i Y,
Xij=pij oraz Yij=cij
Prowadzi nas to do równania
Y = XK
Jeśli X jest macierzą odwracalną, wyliczamy
K=X–1Y
Jeśli macierz X okaże się być macierzą osobliwą, musimy postarać się o dodat-
kowe pary „tekst jawny – szyfrogram”.
W charakterze przykładu załóżmy, że zaszyfrowaliśmy tekst jawny hill
´cipher za pomocą macierzy 2×2, otrzymując szyfrogram HCRZSSXNSP.
Mamy więc
i tak dalej. Wykorzystując powyższe dwie pary, otrzymujemy równanie
Odwracając macierz X
obliczamy macierz kluczową
2.2. / TECHNIKI PODSTAWIENIOWE 83
Otrzymany wynik możemy potwierdzić, wykorzystując inne pary „tekst
jawny – szyfrogram”.
Szyfry polialfabetyczne
Inną metodą zwiększenia bezpieczeństwa szyfru monoalfabetycznego jest użycie
wielu podstawień monoalfabetycznych regularnie zmienianych w miarę prze-
twarzania tekstu jawnego. Szyfry opierające się na tej koncepcji nazywane są
ogólnie szyframi polialfabetycznymi. Wszystkie one funkcjonują w oparciu
o dwie poniższe zasady:
1. Wykorzystywany jest zbiór podstawień monoalfabetycznych.
2. Wybór konkretnego podstawienia dla danej transformacji jest określony
przez klucz.
SZYFR VIGENÈRE’A
Najbardziej znanym szyfrem polialfabetycznym — i jednym z najprostszych —
jest szyfr Vigenère’a. Jego istotą jest naprzemienne wykorzystywanie podstawień
typowych dla szyfru Cezara, ze wszystkimi możliwymi przesunięciami od 0 do
25 (patrz wzór 2.1). Każde z tych podstawień identyfikowane jest przez literę
będącą obrazem litery a w tym podstawieniu, przykładowo podstawienie z k = 3
identyfikowane jest przez literę d.
Algorytm szyfrujący Vigenère’a opisać można poglądowo w następujący spo-
sób. Załóżmy, że tekst jawny ma postać P = p0 p1 p2 … pn-1, zaś klucz ma postać
K = k0 k1 k2 … km-1, przy czym na ogół m n. Ciąg kolejnych liter szyfrogramu
C = C0 C1 C2 … Cn-1 = E(K, P) = E((k0 k1 k2 … km-1), (p0 p1 p2 … pn-1)) = (p0 + k0)
mod 26 || (p1 + k1) mod 26 || …|| (pm-1 + km-1) mod 26 || (pm + k0) mod 26 ||
(pm+1 + k1) mod 26 || …|| (p2m-1 + km-1) mod 26 || … — i tak dalej (|| oznacza kon-
katenację ciągów).
Innymi słowy, pierwsza litera tekstu jawnego dodawana jest modulo 26 do
pierwszej litery klucza, druga litera tekstu jawnego dodawana jest modulo 26 do
drugiej litery klucza i tak dalej, aż m-ta litera tekstu jawnego dodana zostanie
modulo 26 do m-tej litery klucza. Dla następnych liter tekstu jawnego klucz wyko-
rzystywany jest cyklicznie od początku. Postępowanie to kontynuowane jest aż do
przetworzenia wszystkich liter tekstu jawnego. Formalnie
Ci = (pi + ki mod m) mod 26
(2.3)
(porównaj to ze wzorem 2.1 dla szyfru Cezara). Tak więc kolejne znaki tekstu
jawnego szyfrowane są przy cyklicznym użyciu kilku szyfrów Cezara, zależnie od
kolejnych zn
Pobierz darmowy fragment (pdf)