Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00504 008142 10466584 na godz. na dobę w sumie
Kryptografia i bezpieczeństwo sieci komputerowych. Matematyka szyfrów i techniki kryptologii - książka
Kryptografia i bezpieczeństwo sieci komputerowych. Matematyka szyfrów i techniki kryptologii - książka
Autor: Liczba stron: 760
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-2986-2 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> hacking >> kryptografia
Porównaj ceny (książka, ebook, audiobook).

Wykorzystaj fascynujące możliwości kryptografii - zapewniaj bezpieczeństwo informacjom i sieciom komputerowym!

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.

Zagadnienia jakie znajdziesz w I tomie tego podręcznika:


William Stallings - jest autorem 17 książek na zakresu technicznych aspektów bezpieczeństwa informacji i sieci komputerowych. Jest 11-krotnym laureatem nagrody za najlepszą książkę informatyczną roku, przyznawanej przez Text and Academic Authors Association. W trakcie ponad trzydziestoletniej kariery zawodowej zaprojektował i zaimplementował wiele pakietów związanych z protokołami TCP/IP i OSI dla różnych platform. Jako konsultant doradzał m.in. agencjom rządowym, oraz dostawcom sprzętu i oprogramowania.

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

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)

Gdzie kupić całą publikację:

Kryptografia i bezpieczeństwo sieci komputerowych. Matematyka szyfrów i techniki kryptologii
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


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