Dane oryginału

Original edition copyright © 2019 by Taylor & Francis Group, LLC. All rights reserved. Title of English-language original: Cryptography: Theory and Practice, 4th Edition by Douglas R. Stinson, Maura B. Paterson, ISBN 978-1-13819-701-5. Polish-language edition © 2021 by Polish Scientific Publishers PWN Wydawnictwo Naukowe PWN Spółka Akcyjna. All Rights reserved.

Authorised translation from the English language edition published by CRC Press, a member of the Taylor & Francis Group LLC.

Przekład Małgorzata Dąbkowska-Kowalik i Witold Sikorski na zlecenie

WITKOM Witold Sikorski

Projekt okładki INT-MEDIA Dawid Mazur na podstawie oryginału

Wydawca Wioleta Szczygielska-Dybciak

Redaktor prowadzący Jolanta Kowalczuk, Monika Zabrocka-Kutera

Redaktor Anna Bogdanienko

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwo Naukowe PWN Michał Latusek

Konsultant merytoryczny Michał Andrzejczak

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Copyright © for the Polish edition by Wydawnictwo Naukowe PWN SA

Warszawa 2021

ISBN 978-83-01-21850-8

eBook został przygotowany na podstawie wydania papierowego z 2021r. (Wydanie IV (I w WN PWN))

Warszawa 2021

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl, reklama@pwn.pl

www.pwn.pl

Bezpłatny fragment

Wstęp

Rozdział 1. Wprowadzenie do kryptografii

1.1. Kryptosystemy i podstawowe narzędzia kryptograficzne

1.1.1. Kryptosystemy z kluczem tajnym

1.1.2. Kryptosystemy klucza publicznego

1.1.3. Szyfry blokowe i strumieniowe

1.1.4. Kryptografia hybrydowa

1.2. Integralność wiadomości

1.2.1. Kody uwierzytelniania wiadomości

1.2.2. Schematy podpisów

1.2.3. Niezaprzeczalność

1.2.4. Certyfikaty

1.2.5. Funkcje skrótu

1.3. Protokoły kryptograficzne

1.4. Bezpieczeństwo

1.5. Uwagi i źródła

Rozdział 2. Klasyczna kryptografia

2.1. Wprowadzenie: niektóre proste kryptosystemy

2.1.1. Szyfr przestawieniowy

2.1.2. Szyfr podstawieniowy

2.1.3. Szyfr afiniczny

2.1.4. Szyfr Vigenère’a

2.1.5. Szyfr Hilla

2.1.6. Szyfr permutacyjny

2.1.7. Szyfry strumieniowe

2.2. Kryptoanaliza

2.2.1. Kryptoanaliza szyfru afinicznego

2.2.2. Kryptoanaliza szyfru podstawieniowego

2.2.3. Kryptoanaliza szyfru Vigenère’a

2.2.4. Kryptoanaliza szyfru Hilla

2.2.5. Kryptoanaliza szyfru strumieniowego z LFSR

2.3. Uwagi i źródła

Ćwiczenia

Rozdział 3. Teoria Shannona, tajność doskonała i szyfr z kluczem jednorazowym

3.1. Wprowadzenie

3.2. Podstawowa teoria prawdopodobieństwa

3.3. Tajność doskonała

3.4. Entropia

3.4.1. Cechy entropii

3.5. Fałszywe klucze i długość krytyczna

3.6. Uwagi i źródła

Ćwiczenia

Rozdział 4. Szyfry blokowe i szyfry strumieniowe

4.1. Wprowadzenie

4.2. Sieci podstawieniowo-permutacyjne

4.3. Kryptoanaliza liniowa

4.3.1. Lemat nawarstwiania

4.3.2. Liniowe aproksymacje S-boksów

4.3.3. Liniowy atak na SPN

4.4. Kryptoanaliza różnicowa

4.5. Data Encryption Standard

4.5.1. Opis DES

4.5.2. Analiza DES

4.6. Advanced Encryption Standard

4.6.1. Opis AES

4.6.2. Analiza AES

4.7. Tryby działania

4.7.1. Atak wyroczni dopełnienia w trybie CBC

4.8. Szyfry strumieniowe

4.8.1. Atak korelacyjny na generator kombinacji

4.8.2. Atak algebraiczny na generator filtrów

4.8.3. Trivium

4.9. Uwagi i źródła

Ćwiczenia

Rozdział 5. Funkcje skrótu i uwierzytelnianie wiadomości

5.1. Funkcje skrótu i integralność danych

5.2. Bezpieczeństwo funkcji skrótu

5.2.1. Model losowej wyroczni

5.2.2. Algorytmy w modelu losowej wyroczni

5.2.3. Porównanie kryteriów bezpieczeństwa

5.3. Iterowane funkcje skrótu

5.3.1. Konstrukcja Merkle’a–Damgårda

5.3.2. Kilka przykładów iterowanych funkcji skrótów

5.4. Konstrukcja gąbki

5.4.1. SHA-3

5.5. Kody uwierzytelniania wiadomości

5.5.1. Zagnieżdżone kody MAC i HMAC

5.5.2. CBC-MAC

5.5.3. Szyfrowanie uwierzytelnione

5.6. Bezwarunkowo bezpieczne kody MAC

5.6.1. Silnie uniwersalne rodziny skrótów

5.6.2. Optymalność prawdopodobieństwa oszustwa

5.7. Uwagi i źródła

Ćwiczenia

Rozdział 6. Kryptosystem RSA i rozkład liczb całkowitych na czynniki

6.1. Wprowadzenie do kryptografii klucza publicznego

6.2. Więcej teorii liczb

6.2.1. Algorytm Euklidesa

6.2.2. Chińskie twierdzenie o resztach

6.2.3. Inne przydatne fakty

6.3. Kryptosystem RSA

6.3.1. Implementowanie RSA

6.4. Testowanie pierwszości

6.4.1. Symbole Legendre’a i Jacobiego

6.4.2. Algorytm Solovaya–Strassena

6.4.3. Algorytm Millera–Rabina

6.5. Pierwiastki kwadratowe modulo n

6.6. Algorytmy rozkładu na czynniki

6.6.1. Algorytm Pollarda p − 1

6.6.2. Algorytm rho Pollarda

6.6.3. Algorytm losowych kwadratów Dixona

6.6.4. Algorytmy rozkładu na czynniki w praktyce

6.7. Inne ataki na RSA

6.7.1. Obliczanie φ(n)

6.7.2. Wykładnik odszyfrowywania

6.7.3. Atak Wienera z małym wykładnikiem odszyfrowywania

6.8. Kryptosystem Rabina

6.8.1. Bezpieczeństwo kryptosystemu Rabina

6.9. Bezpieczeństwo semantyczne RSA

6.9.1. Częściowe informacje dotyczące bitów tekstu jawnego

6.9.2. Uzyskanie bezpieczeństwa semantycznego

6.10. Uwagi i źródła

Ćwiczenia

Rozdział 7. Kryptografia klucza publicznego i logarytmy dyskretne

7.1. Wprowadzenie

7.1.1. Kryptosystem ElGamala

7.2. Algorytmy dla problemu logarytmu dyskretnego

7.2.1. Algorytm Shanksa

7.2.2. Algorytm logarytmu dyskretnego rho Pollarda

7.2.3. Algorytm Pohliga–Hellmana

7.2.4. Metoda rachunku indeksowego

7.3. Dolne granice złożoności algorytmów generycznych

7.4. Ciała skończone

7.4.1. Analiza indeksu Jouxa dla ciał o niewielkich wyróżnikach

7.5. Krzywe eliptyczne

7.5.1. Krzywe eliptyczne na liczbach rzeczywistych

7.5.2. Krzywe eliptyczne modulo liczba pierwsza

7.5.3. Krzywe eliptyczne na ciałach skończonych

7.5.4. Własności krzywych eliptycznych

7.5.5. Parowanie krzywych eliptycznych

7.5.6. Kryptosystem ElGamala na krzywych eliptycznych

7.5.7. Obliczanie wielokrotności punktów na krzywych eliptycznych

7.6. Algorytmy logarytmu dyskretnego w praktyce

7.7. Bezpieczeństwo systemów ElGamala

7.7.1. Bitowe bezpieczeństwo logarytmów dyskretnych

7.7.2. Semantyczne bezpieczeństwo systemów ElGamala

7.7.3. Problemy Diffiego–Hellmana

7.8. Uwagi i źródła

Ćwiczenia

Rozdział 8. Schematy podpisów

8.1. Wprowadzenie

8.1.1. Schemat podpisu RSA

8.2. Wymogi bezpieczeństwa dla schematów podpisu

8.2.1. Podpisy i funkcje skrótu

8.3. Schemat podpisu ElGamala

8.3.1. Bezpieczeństwo schematu podpisu ElGamala

8.4. Warianty schematu podpisu ElGamala

8.4.1. Schemat podpisu Schnorra

8.4.2. Algorytm podpisu cyfrowego

8.4.3. DSA krzywej eliptycznej

8.5. Funkcja skrótu o pełnej dziedzinie

8.6. Certyfikaty

8.7. Podpisywanie i szyfrowanie

8.8. Uwagi i źródła

Ćwiczenia

Rozdział 9. Kryptografia postkwantowa

9.1. Wprowadzenie

9.2. Kryptografia oparta na kratach

9.2.1. NTRU

9.2.2. Kraty i bezpieczeństwo NTRU

9.2.3. LWE

9.3. Kryptografia oparta na kodzie i kryptosystem McEliece’a

9.4. Kryptografia wielu zmiennych

9.4.1. Równania ciała ukrytego

9.4.2. Schemat podpisu oliwa i ocet

9.5. Schematy podpisu oparte na skrócie

9.5.1. Schemat podpisu Lamporta

9.5.2. Schemat podpisu Winternitza

9.5.3. Schemat podpisu Merkle’a

9.6. Uwagi i źródła

Ćwiczenia

Rozdział 10. Schematy identyfikacji i uwierzytelnianie jednostki

10.1. Wprowadzenie

10.1.1. Hasła

10.1.2. Bezpieczne schematy identyfikacji

10.2. Wyzwanie i odpowiedź w kryptografii klucza tajnego

10.2.1. Model ataku i cele przeciwnika

10.2.2. Wzajemne uwierzytelnianie

10.3. Wyzwanie i odpowiedź dla kryptografii klucza publicznego

10.3.1. Schematy identyfikacji klucza publicznego

10.4. Schemat identyfikacji Schnorra

10.4.1. Bezpieczeństwo schematu identyfikacji Schnorra

10.5. Schemat identyfikacji Feige’a–Fiata–Shamira

10.6. Uwagi i źródła

Ćwiczenia

Rozdział 11. Dystrybucja kluczy

11.1. Wprowadzenie

11.1.1. Modele ataku i cele przeciwników

11.2. Wstępna dystrybucja kluczy

11.2.1. Wstępna dystrybucja kluczy Diffiego–Hellmana

11.2.2. Schemat Bloma

11.2.3. Wstępna dystrybucja klucza w sieciach czujnikowych

11.3. Schematy dystrybucji klucza sesji

11.3.1. Schemat Needhama–Schroedera

11.3.2. Atak Denninga–Sacca na schemat NS

11.3.3. Kerberos

11.3.4. Schemat Bellare’a–Rogawaya

11.4. Ponowne tworzenie klucza i logiczna hierarchia kluczy

11.5. Schematy progowe

11.5.1. Schemat Shamira

11.5.2. Uproszczony schemat (t, t)-progowy

11.5.3. Wizualne schematy progowe

11.6. Uwagi i źródła

Ćwiczenia

Rozdział 12. Schematy uzgadniania klucza

12.1. Wprowadzenie

12.1.1. Bezpieczeństwo warstwy transportu (TLS)

12.2. Uzgodnienie klucza Diffiego–Hellmana

12.2.1. Schemat uzgadniania klucza STS (station-to-station)

12.2.2. Bezpieczeństwo STS

12.2.3. Ataki ze znanym kluczem sesji

12.3. Funkcje wyprowadzania klucza

12.4. Schematy MTI uzgadniania klucza

12.4.1. Ataki na MTI/A0 ze znanym kluczem sesji

12.5. Zaprzeczalne schematy uzgadniania klucza

12.6. Aktualizacja kluczy

12.7. Konferencyjne schematy uzgadniania klucza

12.8. Uwagi i źródła

Ćwiczenia

Rozdział 13. Różne tematy

13.1. Kryptografia oparta na tożsamości

13.1.1. Kryptosystem Cocksa oparty na tożsamości

13.1.2. Kryptosystem Boneha–Franklina oparty na tożsamości

13.2. Kryptosystem Pailliera

13.3. Ochrona praw autorskich

13.3.1. Odciski palca

13.3.2. Identyfikowalna własność nadrzędna

13.3.3. Kody 2-IPP

13.3.4. Śledzenie nielegalnej redystrybucji kluczy

13.4. Bitcoin i technologia blockchain

13.5. Uwagi i źródła

Ćwiczenia

Dodatek A. Teoria liczb i algebraiczne koncepcje kryptografii

A.1. Arytmetyka modularna

A.2. Grupy

A.2.1. Rzędy elementów grupy

A.2.2. Grupy cykliczne i elementy pierwotne

A.2.3. Podgrupy i warstwy

A.2.4. Izomorfizmy i homomorfizmy grup

A.2.5. Reszty kwadratowe

A.2.6. Algorytm Euklidesa

A.2.7. Iloczyny proste

A.3. Pierścienie

A.3.1. Chińskie twierdzenie o resztach

A.3.2. Ideały i pierścienie ilorazowe

A.4. Ciała

Dodatek B. Pseudolosowe generowanie bitów dla kryptografii

B.1. Generatory bitów

B.2. Bezpieczeństwo pseudolosowych generatorów bitów

B.3. Uwagi i źródła

Bibliografia

O Autorach

Przypisy

Wstęp

Pierwsze wydanie tej książki ukazało się w 1995 roku. Celem było wówczas opracowanie ogólnego podręcznika, który obejmowałby wszystkie podstawowe dziedziny kryptografii, jak również wybrane bardziej zaawansowane tematy. Ostatnio, w 2002 roku, ukazało się drugie wydanie, a w 2006 roku – trzecie.

Od czasu pierwszego wydania tej książki 23 lata temu dokonano wielu ekscytujących postępów w kryptografii. Jednocześnie wiele z „rdzennych” obszarów kryptografii, które były wtedy ważne, jest nadal aktualnych – zapewnienie silnego oparcia na podstawach pozostaje głównym celem tej pracy. Trzeba było podjąć wiele decyzji co do tego, które ze starszych tematów zachować, a które nowe powinny zostać włączone do książki. W naszych wyborach kierowaliśmy się takimi kryteriami, jak znaczenie dla praktycznych zastosowań kryptografii, a także wpływ nowych podejść i technik na projektowanie oraz analizę protokołów kryptograficznych. W wielu przypadkach wiązało się to z prowadzeniem nowatorskich badań i próbą przedstawienia ich w przystępny sposób, odpowiedni do prezentacji w ramach nauczania.

W tym kontekście podstawowy materiał kryptografii klucza tajnego i publicznego traktowany jest w podobny sposób jak w poprzednich edycjach. Do tego wydania zostało jednak dodanych wiele tematów, z których najważniejsze to:

• Całkiem nowy rozdział na temat ekscytującego, rozwijającego się obszaru kryptografii postkwantowej, który obejmuje najważniejsze kryptosystemy, projektowane w celu zapewnienia bezpieczeństwa przed atakami realizowanymi przez komputery kwantowe (rozdział 9).

• Nowy, wysokopoziomowy, nietechniczny przegląd celów i narzędzi kryptografii (rozdział 1).

• Nowy dodatek matematyczny podsumowujący definicje i główne wyniki teorii liczb i algebry, które są wykorzystywane w całej książce. Daje to możliwość szybkiego odwołania się do wszelkich terminów i twierdzeń matematycznych, które czytelnik mógłby chcieć znaleźć (dodatek A).

• Rozszerzone potraktowanie szyfrów strumieniowych, w tym wspólne techniki projektowania wraz z opisem popularnego szyfru strumieniowego znanego jako Trivium.

• Książka przedstawia teraz dodatkowe, ciekawe ataki na kryptosystemy, w tym:

- atak wyroczni (padding oracle attack),

- ataki korelacyjne i ataki algebraiczne na szyfry strumieniowe,

- atak na generator bitów losowych DUAL-EC, wykorzystujący zapadki.

• Podajemy sposób postępowania z konstrukcją gąbki funkcji skrótu i jej zastosowanie w nowym standardzie funkcji skrótu SHA-3. Jest to znaczące nowe podejście do projektowania funkcji skrótu.

• Opisano metody dystrybucji kluczy w sieciach czujników.

• Jest też dział poświęcony podstawom kryptografii wizualnej. Pozwala to na bezpieczną metodę dzielenia tajnej wiadomości wizualnej na części (udziały), które mogą być później łączone w celu zrekonstruowania tajemnicy.

• Opisane są podstawowe techniki kryptowalut, stosowane w BITCOIN i blockchain.

• Wyjaśniamy podstawy nowych metod kryptograficznych stosowanych w protokołach komunikacyjnych takich jak Signal. Obejmują one takie tematy, jak zaprzeczalność i aktualizacja klucza Diffiego–Hellmana.

Mamy nadzieję, że książka ta może być wykorzystana w różnych kursach. Wstępny kurs na poziomie licencjackim może być oparty na wyborze materiału z pierwszych ośmiu rozdziałów. Należy podkreślić, że w kilku rozdziałach, późniejsze podrozdziały mogą być uważane za bardziej zaawansowane niż wcześniejsze. Mogą one stanowić materiały do kursów dla absolwentów lub do samodzielnej nauki. Materiały z późniejszych rozdziałów mogą być również włączone do kursu wprowadzającego lub uzupełniającego, w zależności od zainteresowań instruktora.

Kryptografia jest szerokim przedmiotem i wymaga znajomości kilku dziedzin matematyki, w tym teorii liczb, grup, pierścieni i ciał, algebry liniowej, prawdopodobieństwa i teorii informacji. Przydatna jest również pewna znajomość złożoności obliczeniowej, algorytmów i teorii zupełności NP. Naszym zdaniem to właśnie szerokość wymaganego tła matematycznego często stwarza trudności osobom studiującym po raz pierwszy kryptografię. Mając to na uwadze, utrzymaliśmy prezentację matematyczną z poprzednich edycji. Jedną z podstawowych zasad jest to, że rozumienie matematyki jest niezbędne do zrozumienia różnych schematów i tematów kryptograficznych. Jednocześnie staramy się unikać niepotrzebnie zaawansowanych technik matematycznych – dostarczamy niezbędne informacje, ale nie przeciążamy czytelnika niepotrzebnymi pojęciami matematycznymi.

Następujące cechy są wspólne dla wszystkich wydań tej książki:

• Tło matematyczne jest podawane na bieżąco tam, gdzie jest potrzebne.

• Nieformalne opisy kryptosystemów są podane wraz z dokładniejszymi opisami pseudokodów.

• Przykłady numeryczne zaprezentowano dla zilustrowania działania większości algorytmów opisanych w tej książce.

• Matematyczne podstawy algorytmów i kryptosystemów zostały wyjaśnione dokładnie i rygorystycznie.

• W książce są też liczne ćwiczenia, a niektóre z nich stanowią spore wyzwanie.

Przygotowując to nowe wydanie, otrzymaliśmy użyteczne opinie od różnych osób na temat treści tej książki. W szczególności chcielibyśmy podziękować Colleen Swanson za wiele pomocnych komentarzy i sugestii. Kilku recenzentów dostarczyło nam przydatne sugestie, a my doceniamy również komentarze Stevena Galbraitha i Jalaja Upadhyaya. Na koniec dziękujemy Roberto De Prisco, który przygotował przykłady udziałów w systemie progów wizualnych zawartych w rozdziale 11.

Douglas R. Stinson

Maura B. Paterson

Rozdział 1

Wprowadzenie do kryptografii

W tym rozdziale przedstawiamy krótki przegląd rodzajów problemów badanych w kryptografii oraz technik ich rozwiązywania. Problemy te oraz narzędzia kryptograficzne, które są stosowane w ich rozwiązywaniu, zostały omówione bardziej szczegółowo i ściśle w dalszej części tej książki. Wprowadzenie to może służyć jako nieformalne, nietechniczne, niematematyczne podsumowanie poruszanych tematów. Jako takie można je uznać za lekturę opcjonalną.

1.1. Kryptosystemy i podstawowe narzędzia kryptograficzne

W tej części omawiamy podstawowe pojęcia związane z szyfrowaniem. Obejmują one kryptografię klucza tajnego i publicznego, szyfry blokowe i strumieniowe oraz kryptografię hybrydową.

1.1.1. Kryptosystemy z kluczem tajnym

Kryptografia jest stosowana od tysięcy lat w celu zapewnienia poufnej komunikacji między wzajemnie zaufanymi stronami. W jej najbardziej podstawowej formie, dwie osoby, często określane jako Alicja i Bob, uzgodniły konkretny tajny klucz. W późniejszym czasie Alicja może chcieć wysłać sekretną wiadomość do Boba (lub Bob może chcieć wysłać wiadomość do Alicji). Klucz jest używany do przekształcenia oryginalnej wiadomości (zazwyczaj nazywanej tekstem jawnym) w zaszyfrowaną formę, która jest niezrozumiała dla każdego, kto nie posiada tego klucza. Proces ten jest nazywany szyfrowaniem, a zaszyfrowana wiadomość jest nazywana tekstem zaszyfrowanym lub szyfrogramem (ciphertext). Gdy Bob odbierze zaszyfrowany tekst, może użyć tego klucza do przekształcenia zaszyfrowanego tekstu z powrotem w oryginalny tekst jawny. Jest to proces odszyfrowywania. Kryptosystem stanowi pełną specyfikację kluczy i sposobu, w jaki są one wykorzystywane do szyfrowania i odszyfrowywania informacji.

Różne typy kryptosystemów o coraz większym stopniu zaawansowania były wykorzystywane do wielu celów w historii. Ważne zastosowania obejmowały poufną komunikację między przywódcami politycznymi i/lub członkami rodziny królewskiej, manewry wojskowe itp. Jednak wraz z rozwojem Internetu i zastosowań takich jak handel elektroniczny pojawiło się wiele nowych, różnorodnych zastosowań. Obejmują one takie scenariusze, jak szyfrowanie haseł, numerów kart kredytowych, poczty elektronicznej, dokumentów, plików i nośników cyfrowych.

Należy także wspomnieć, że techniki kryptograficzne są również szeroko stosowane w celu ochrony przechowywanych danych, oprócz danych przekazywanych przez jedną stronę do drugiej. Na przykład użytkownicy mogą chcieć szyfrować dane przechowywane na laptopach, zewnętrznych twardych dyskach, w chmurze, bazach danych itp. Dodatkowo użyteczna może być możliwość wykonywania obliczeń na zaszyfrowanych danych (bez uprzedniego ich odszyfrowania).

Opracowanie i wdrożenie kryptosystemu musi uwzględniać kwestię bezpieczeństwa. Tradycyjnie zagrożenie kryptograficzne stanowiło zagrożenie ze strony podsłuchującego przeciwnika, który mógłby przechwycić szyfrowany tekst i spróbować go odszyfrować. Jeśli okaże się, że przeciwnik ma klucz, to nic nie da się zrobić. Tak więc główne względy bezpieczeństwa dotyczą przeciwnika, który nie ma klucza, a mimo to nadal próbuje odszyfrować zaszyfrowany tekst. Techniki stosowane przez przeciwnika w celu „złamania” kryptosystemu nazywane są kryptoanalizą. Najbardziej oczywistym rodzajem analizy kryptograficznej jest próba odgadnięcia klucza. Atak, w którym przeciwnik próbuje rozszyfrować zaszyfrowany tekst za pomocą każdego możliwego klucza, nazywany jest wyczerpującym poszukiwaniem klucza. Gdy przeciwnik spróbuje znaleźć właściwy klucz, zostanie znaleziony tekst jawny, ale gdy zostanie użyty jakikolwiek inny klucz, „odszyfrowany”, szyfrogram będzie prawdopodobnie przypadkowym bełkotem. Tak więc oczywistym pierwszym krokiem w projektowaniu bezpiecznego kryptosystemu jest określenie bardzo dużej liczby możliwych kluczy, tak wielu, że przeciwnik nie będzie w stanie przetestować ich wszystkich w rozsądnym czasie.

Opisany powyżej model kryptografii jest zwykle nazywany kryptografią klucza tajnego. Oznacza to, że istnieje jeden tajny klucz, który jest znany zarówno Alicji, jak i Bobowi. To znaczy, że klucz ten jest „tajemnicą”, która jest znana dwóm stronom. Klucz ten jest wykorzystywany zarówno do szyfrowania otwartych tekstów, jak i do odszyfrowywania szyfrogramów. Rzeczywiste funkcje szyfrowania i odszyfrowywania są więc wzajemnie odwrotne. Niektóre podstawowe kryptosystemy klucza tajnego są wprowadzane i analizowane w odniesieniu do różnych pojęć bezpieczeństwa w rozdziałach 2 i 3.

Wadą kryptografii tajnego klucza jest to, że Alicja i Bob muszą jakoś wcześniej uzgodnić tajny klucz (zanim będą chcieli wysyłać do siebie nawzajem jakiekolwiek wiadomości). Może to być proste, jeśli Alicja i Bob są w tym samym miejscu, kiedy wybierają swój tajny klucz. Ale co jeśli Alicja i Bob są daleko od siebie, powiedzmy na różnych kontynentach? Jednym z możliwych rozwiązań jest wykorzystanie przez Alicję i Boba kryptosystemu klucza publicznego.

1.1.2. Kryptosystemy klucza publicznego

Rewolucyjny pomysł kryptografii klucza publicznego został wprowadzony w latach 70. XX wieku przez Diffiego i Hellmana. Ich pomysł polegał na tym, że być może uda się stworzyć kryptografię, w której istnieją dwa odrębne klucze. Klucz publiczny służyłby do szyfrowania tekstu jawnego, a klucz prywatny umożliwiałby odszyfrowanie zaszyfrowanego tekstu. Należy zauważyć, że klucz publiczny może być znany „każdemu”, podczas gdy klucz prywatny jest znany tylko jednej osobie (a mianowicie odbiorcy zaszyfrowanej wiadomości). Tak więc kryptosystem klucza publicznego umożliwiłby każdemu zaszyfrowanie wiadomości, która ma być przesłana, powiedzmy, do Boba, a tylko Bob mógłby ją odszyfrować. Pierwszym i najbardziej znanym przykładem kryptosystemu klucza publicznego jest kryptosystem RSA, który został wynaleziony przez Rivesta, Shamira i Adlemana. Różne typy kryptosystemów klucza publicznego zostały przedstawione w rozdziałach 6, 7 i 9.

Kryptografia klucza publicznego eliminuje konieczność uzgadniania przez dwie strony wcześniej udostępnionego klucza tajnego. Nadal jednak konieczne jest opracowanie metody bezpiecznej dystrybucji kluczy publicznych. Nie jest to wcale trywialny cel do osiągnięcia, a główną kwestią jest poprawność i autentyczność domniemanych kluczy publicznych. Certyfikaty, które omawiamy nieco później, są jedną z powszechnych metod radzenia sobie z tym problemem.

1.1.3. Szyfry blokowe i strumieniowe

Kryptosystemy są zazwyczaj klasyfikowane jako szyfry blokowe lub szyfry strumieniowe. W szyfrze blokowym tekst jawny jest podzielony na fragmenty o stałej wielkości, zwane blokami. Blok jest określony jako ciąg bitów (tzn. ciąg zer i jedynek) o określonej długości (np. 64 lub 128 bitów). Szyfr blokowy szyfruje (lub odszyfrowuje) jeden blok naraz. W przeciwieństwie do tego szyfr strumieniowy najpierw używa klucza do skonstruowania strumienia szyfrującego (keystream), który jest ciągiem bitowym o dokładnie tej samej długości co tekst jawny (tekst jawny jest ciągiem bitowym o dowolnej długości). Operacja szyfrowania konstruuje szyfrogram jako alternatywę wykluczającą tekstu jawnego i strumienia klucza. Odszyfrowywanie uzyskuje się przez obliczenie alternatywy wykluczającej (XOR) szyfrogramu i strumienia szyfrującego. Kryptosystemy klucza publicznego są zawsze szyframi blokowymi, natomiast kryptosystemy klucza tajnego mogą być szyframi blokowymi lub strumieniowymi. Szyfr blokowy jest szczegółowo omówiony w rozdziale 4.

1.1.4. Kryptografia hybrydowa

Jedną z wad kryptosystemów z kluczem publicznym jest to, że są one znacznie wolniejsze niż kryptosystemy z kluczem tajnym. W konsekwencji kryptosystemy klucza publicznego są wykorzystywane głównie do szyfrowania małych ilości danych, np. numeru karty kredytowej. Istnieje jednak ładny sposób na połączenie kryptografii z kluczem tajnym i publicznym, aby wykorzystać zalety obu tych rozwiązań. Technika ta nazywana jest kryptografią hybrydową. Załóżmy, że Alicja chce zaszyfrować „długą” wiadomość i wysłać ją do Boba. Załóżmy, że Alicja i Bob nie mają wcześniej wspólnego tajnego klucza. Alicja może wybrać losowy tajny klucz i zaszyfrować tekst jawny, używając (szybkiego) tajnego klucza kryptograficznego. Następnie Alicja szyfruje ten klucz niejawny przy użyciu klucza publicznego Boba. Alicja wysyła zaszyfrowany tekst i zaszyfrowany klucz do Boba. Bob najpierw używa swojego prywatnego klucza szyfrującego do odszyfrowania tajnego klucza, a następnie używa tego tajnego klucza do odszyfrowania zaszyfrowanego tekstu.

Zauważmy, że „powolny” kryptosystem klucza publicznego jest używany tylko do szyfrowania krótkiego tajnego klucza. Znacznie szybszy kryptosystem klucza tajnego jest używany do szyfrowania dłuższego tekstu jawnego. W ten sposób kryptografia hybrydowa (prawie) osiąga efektywność kryptografii tajnego klucza, ale może być stosowana w sytuacji, gdy Alicja i Bob nie mają wcześniej ustalonego klucza tajnego.

1.2. Integralność wiadomości

W tym podrozdziale omówiono różne narzędzia, które pomagają osiągnąć integralność danych, w tym kody uwierzytelniania wiadomości (MAC), schematy podpisów i funkcje skrótu.

Kryptosystemy zapewniają tajność (inaczej poufność) przed podsłuchującym przeciwnikiem, który jest często nazywany pasywnym przeciwnikiem. Zakłada się, że pasywny przeciwnik jest w stanie uzyskać dostęp do wszelkich informacji przesyłanych przez Alicję do Boba (patrz rysunek 1.1). Istnieje jednak wiele innych zagrożeń, przed którymi chcielibyśmy się chronić, zwłaszcza gdy obecny jest aktywny przeciwnik. Aktywny przeciwnik to taki, który może zmienić informacje przesyłane od Alicji do Boba.

Rysunek 1.2 przedstawia niektóre z możliwych działań aktywnego przeciwnika. Aktywny przeciwnik może

• zmienić informacje, które są wysyłane od Alicji do Boba,

• wysyłać informacje do Boba w taki sposób, aby Bob uważał, że informacje pochodzą od Alicji, lub

• przekierowywać informacje wysłane od Alicji do Boba w taki sposób, aby osoba trzecia (Charlie) otrzymała te informacje zamiast Boba.

Możliwe cele aktywnego przeciwnika mogą obejmować oszukiwanie Boba, aby (powiedzmy) zaakceptował „fałszywe” informacje, lub wprowadzenie Boba w błąd co do tego, kto wysłał mu te informacje.

Należy zauważyć, że samo szyfrowanie nie może chronić przed tego typu aktywnymi atakami. Na przykład szyfr strumieniowy jest podatny na atak przełączania bitów (bit-flipping attack). Jeśli niektóre bity szyfru zostaną „odwrócone” (tzn. zera zostaną zastąpione jedynkami i na odwrót), to efektem jest odwrócenie odpowiadających im bitów zwykłego tekstu. W ten sposób przeciwnik może modyfikować tekst jawny w sposób przewidywalny, nawet jeśli nie wie, jakie są bity jawne.

Istnieją różne rodzaje gwarancji „integralności”, które możemy próbować wykorzystać w celu ochrony przed ewentualnymi działaniami aktywnego przeciwnika. Taki przeciwnik może zmienić informacje, które są przekazywane od Alicji do Boba (i należy pamiętać, że informacje te mogą, ale nie muszą być szyfrowane). Alternatywnie przeciwnik może próbować „podrobić” wiadomość i wysłać ją do Boba, mając nadzieję, że ten pomyśli, iż pochodzi ona od Alicji. Narzędzia kryptograficzne, które chronią przed tymi i podobnymi rodzajami zagrożeń, mogą być konstruowane w ustawieniach zarówno klucza tajnego, jak i publicznego. W systemach klucza tajnego omawiamy krótko pojęcie kodu uwierzytelniania wiadomości (lub MAC – Message Authentication Code). W rozwiązaniach klucza publicznego, narzędziem służącym do mniej więcej podobnego celu jest schemat podpisu cyfrowego.

RYSUNEK 1.1. Przeciwnik pasywny

RYSUNEK 1.2. Przeciwnik aktywny

1.2.1. Kody uwierzytelniania wiadomości

Kod uwierzytelniania wiadomości wymaga, aby Alicja i Bob współdzielili tajny klucz. Gdy Alicja chce wysłać wiadomość do Boba, używa tajnego klucza do utworzenia znacznika, który dołącza do wiadomości (znacznik zależy zarówno od klucza, jak i od wiadomości). Kiedy Bob odbierze wiadomość i znacznik, użyje klucza do ponownego obliczenia znacznika i sprawdzi, czy jest on taki sam jak znacznik, który otrzymał. Jeśli tak, to Bob akceptuje wiadomość jako autentyczną wiadomość od Alicji, a jeśli nie, to Bob odrzuca wiadomość jako niepoprawną. Zwracamy uwagę, że wiadomość może być szyfrowana lub nie. Kody MAC zostały omówione w rozdziale 5.

Jeśli nie ma potrzeby zachowania poufności, wiadomość może być wysłana jako tekst jawny. Jeśli jednak pożądana jest poufność, to tekst jawny zostanie zaszyfrowany, a następnie znacznik zostanie obliczony na podstawie szyfru. Bob najpierw zweryfikuje poprawność znacznika. Jeśli znacznik jest poprawny, Bob odszyfrowałby wówczas tekst szyfrujący. Proces ten jest często określany jako szyfruj-potem-MAC (bardziej szczegółowe omówienie tego tematu znajduje się w punkcie 5.5.3).

Aby MAC został uznany za bezpieczny, przeciwnik nie powinien mieć możliwości obliczenia prawidłowego znacznika dla żadnej wiadomości, dla której nie widział jeszcze prawidłowego znacznika. Załóżmy, że bezpieczny MAC jest wykorzystywany przez Alicję i Boba (i załóżmy, że przeciwnik nie zna tajnego klucza, którego używają). Wtedy, jeśli Bob otrzyma wiadomość i ważny znacznik, może być pewien, że Alicja utworzyła znacznik na danej wiadomości (pod warunkiem, że Bob nie utworzył go sam) i że ani wiadomość, ani znacznik nie zostały zmienione przez przeciwnika. Podobny wniosek może wyciągnąć Bob, gdy otrzyma wiadomość od Alicji wraz z poprawnym znacznikiem.

1.2.2. Schematy podpisów

W systemach klucza publicznego schemat podpisu zapewnia podobną funkcjonalność co MAC. W schemacie podpisu klucz prywatny określa algorytm podpisywania, którego Alicja może użyć do podpisania wiadomości. Podobnie jak w przypadku MAC, algorytm podpisywania zwraca wynik, który w tym przypadku nazywany jest podpisem, zależny od podpisywanej wiadomości i klucza. Podpis jest następnie dołączany do wiadomości. Zauważmy, że algorytm podpisywania jest znany tylko Alicji. Z drugiej strony, istnieje algorytm weryfikacyjny, który jest kluczem publicznym (znanym wszystkim). Algorytm weryfikacyjny przyjmuje na wejściu wiadomość i podpis, a na wyjściu wskazuje wartość true lub false, zależnie od tego, czy podpis ma być zaakceptowany jako ważny, czy nie. Jedną z ładnych cech schematu podpisu jest to, że każdy może zweryfikować podpisy Alicji na wiadomościach, pod warunkiem, że ma autentyczną kopię klucza weryfikacyjnego Alicji. Natomiast w ustawieniu MAC tylko Bob może weryfikować znaczniki utworzone przez Alicję (gdy Alicja i Bob mają wspólny tajny klucz). Schematy podpisów są analizowane w rozdziale 8.

Wymogi bezpieczeństwa dotyczące schematów podpisu są podobne do tych dla MAC-ów. Przeciwnik nie powinien mieć możliwości złożenia ważnego podpisu na żadnej wiadomości, która nie została wcześniej podpisana przez Alicję. Dlatego też, jeżeli Bob (lub ktokolwiek inny) otrzyma wiadomość i ważny znacznik (tzn. taki, który może być zweryfikowany przy użyciu algorytmu publicznej weryfikacji Alicji), odbiorca może być pewien, że podpis został utworzony przez Alicję i ani wiadomość, ani podpis nie zostały zmodyfikowane przez przeciwnika.

Jednym z powszechnych zastosowań podpisów jest ułatwianie bezpiecznych aktualizacji oprogramowania. Gdy użytkownik kupuje oprogramowanie na stronie internetowej, zazwyczaj zawiera ono algorytm weryfikacji schematu podpisu. Później, gdy pobierana jest zaktualizowana wersja oprogramowania, zawiera ona podpis (na zaktualizowanym oprogramowaniu). Podpis ten można zweryfikować za pomocą algorytmu weryfikacyjnego, który został pobrany podczas zakupu oryginalnej wersji oprogramowania. Dzięki temu komputer użytkownika może zweryfikować, czy aktualizacja pochodzi z tego samego źródła co oryginalna wersja programu.

Systemy podpisu mogą być łączone z systemami szyfrowania klucza publicznego w celu zapewnienia poufności wraz z gwarancjami integralności systemu podpisu. Załóżmy, że Alicja chce wysłać podpisaną, zaszyfrowaną (krótką) wiadomość do Boba. W tej sytuacji najpowszechniej stosowaną techniką jest dla Alicji najpierw utworzenie podpisu na zwykłym tekście przy użyciu jej prywatnego algorytmu podpisywania, a następnie zaszyfrowanie zwykłego tekstu i podpisu przy użyciu publicznego klucza szyfrującego Boba. Gdy Bob otrzymuje wiadomość, najpierw ją odszyfrowuje, a następnie sprawdza ważność podpisu. Proces ten nazywa się podpisz-potem-szyfruj (sign-then-encrypt). Należy pamiętać, że jest to w pewnym sensie odwrotna część procedury „szyfruj-potem-MAC” (encrypt-then-MAC), która jest używana w systemach klucza tajnego.

1.2.3. Niezaprzeczalność

Istnieje subtelna różnica między MAC a schematami podpisów. W schemacie podpisu algorytm weryfikacji jest jawny. Oznacza to, że podpis może być zweryfikowany przez każdego. Jeśli więc Bob otrzyma od Alicji wiadomość zawierającą jej ważny podpis, może on pokazać wiadomość i podpis każdemu i mieć pewność, że osoba trzecia również zaakceptuje podpis jako ważny. W związku z tym Alicja nie może podpisać wiadomości, a następnie próbować twierdzić, że nie podpisała wiadomości, co jest właściwością określaną mianem niezaprzeczalności. Jest to przydatne przy zawieraniu umów, w których nie chcemy, aby ktoś mógł odmówić wykonania podpisanej umowy, twierdząc (nieprawdziwie), że jego podpis został „sfałszowany”.

Jednak w przypadku MAC nie ma możliwości weryfikacji przez osoby trzecie, ponieważ tajny klucz jest wymagany do weryfikacji poprawności znacznika, a klucz jest znany tylko Alicji i Bobowi. Nawet jeśli tajny klucz zostanie ujawniony stronie trzeciej (np. w wyniku nakazu sądowego), nie ma możliwości ustalenia, czy znacznik został utworzony przez Alicję, czy przez Boba, ponieważ wszystko, co może zrobić Bob, może zrobić również Alicja i na odwrót. Tak więc MAC nie zapewnia niezaprzeczalności i z tego powodu MAC jest czasami określany jako „zaprzeczalny”. Interesujące jest jednak to, że istnieją sytuacje, w których zaprzeczenie jest pożądane. Może to mieć miejsce w przypadku komunikacji w czasie rzeczywistym, gdzie Alicja i Bob chcą mieć pewność co do autentyczności ich komunikacji w trakcie jej trwania, ale nie chcą, aby istniał trwały, możliwy do sprawdzenia zapis tej komunikacji. Taka komunikacja jest analogiczna do rozmowy „poza protokołem”, np. między dziennikarzem a anonimowym źródłem. MAC jest przydatny w kontekście tego typu rozmów, zwłaszcza jeśli po ich zakończeniu zadbamy o skasowanie tajnych kluczy, które były używane podczas komunikacji.

1.2.4. Certyfikaty

Wspomnieliśmy, że ważne jest sprawdzanie autentyczności kluczy publicznych, zanim zostaną one użyte. Certyfikat jest wspólnym narzędziem, które pomaga w osiągnięciu tego celu. Certyfikat będzie zawierał informacje o konkretnym użytkowniku lub, co bardziej powszechne, o stronie internetowej, w tym o jej kluczach publicznych. Te klucze publiczne będą podpisywane przez zaufany organ. Zakłada się, że każdy ma publiczny klucz weryfikacyjny zaufanego organu, dzięki czemu każdy może zweryfikować podpis zaufanego organu na certyfikacie. Więcej informacji na temat certyfikatów znajduje się w podrozdziale 8.6.

Technika ta jest stosowana w Internecie w protokole bezpieczeństwa warstwy transportu (Transport Layer Security), powszechnie nazywanym TLS. Gdy użytkownik łączy się z bezpieczną stroną internetową, na przykład należącą do firmy zajmującej się handlem elektronicznym, strona internetowa firmy prześle użytkownikowi certyfikat, aby mógł on zweryfikować autentyczność kluczy publicznych strony. Te klucze publiczne będą następnie wykorzystywane do ustanowienia bezpiecznego kanału między użytkownikiem a stroną internetową, w którym wszystkie informacje są szyfrowane. Należy zauważyć, że klucz publiczny zaufanego organu, który jest używany do weryfikacji klucza publicznego strony internetowej, jest zazwyczaj zakodowany w przeglądarce internetowej.

1.2.5. Funkcje skrótu

Systemy podpisywania są zwykle znacznie mniej wydajne niż MAC. Dlatego też nie jest wskazane, aby używać schematu podpisu do podpisywania „długich” wiadomości. (Właściwie większość schematów podpisu jest zaprojektowana do podpisywania tylko krótkich wiadomości o stałej długości). W praktyce wiadomości są „mieszane” przed ich podpisaniem. Kryptograficzna funkcja skrótu jest używana do kompresji wiadomości o dowolnej długości na krótki, losowo wyglądający skrót o stałej długości (message digest). Zauważmy, że funkcja skrótu jest funkcją publiczną i zakłada się, że jest znana wszystkim. Co więcej, funkcja skrótu nie ma żadnego klucza. Funkcje skrótu są omówione w rozdziale 5.

Po tym, jak Alicja zmiesza wiadomość, podpisuje jej skrót, używając swojego prywatnego algorytmu podpisywania. Oryginalna wiadomość, wraz z podpisem, jest następnie przekazywana powiedzmy do Boba. Proces ten nazywany jest skróć-potem-podpisz (hash-then-sign). W celu weryfikacji podpisu Bob oblicza skrót wiadomości przez zastosowanie funkcji skrótu. Następnie używa publicznego algorytmu weryfikacji do sprawdzenia ważności podpisu na skrócie wiadomości. Gdy podpis jest używany wraz z szyfrowaniem klucza publicznego, proces ten jest nazywany skróć-potem-podpisz-potem-szyfruj (hash-then-sign-then-encrypt). Oznacza to, że wiadomość jest mieszana, skrót wiadomości jest następnie podpisywany, a na koniec wiadomość i podpis są szyfrowane.

Kryptograficzna funkcja skrótu bardzo się różni od funkcji skrótu, która jest używana na przykład do konstruowania tabeli skrótów. W kontekście tabel skrótu, funkcja skrótu jest zazwyczaj wymagana tylko do uzyskania kolizji[1] z wystarczająco małym prawdopodobieństwem. Z drugiej strony, jeżeli używana jest kryptograficzna funkcja skrótu, powinno być obliczeniowo niemożliwe znalezienie kolizji, choć muszą one istnieć. Kryptograficzne funkcje skrótu są zazwyczaj wymagane w celu spełnienia dodatkowych właściwości bezpieczeństwa, jak to omówiono w podrozdziale 5.2.

Kryptograficzne funkcje skrótu mają również inne zastosowania, na przykład do wyprowadzania kluczy (key derivation). W przypadku gdy funkcja skrótu zostanie użyta do wyprowadzenia klucza, będzie stosowana do długiego ciągu losowego w celu utworzenia krótkiego klucza losowego.

Na koniec należy podkreślić, że funkcje skrótu nie mogą być wykorzystywane do szyfrowania z dwóch podstawowych powodów. Pierwszym z nich jest fakt, że funkcje skrótu nie mają klucza. Drugim jest to, że funkcje skrótu nie mogą być odwracane (nie są to funkcje różnowartościowe), więc nie można „odszyfrować” skrótu wiadomości, aby uzyskać jednoznaczny tekst jawny.

1.3. Protokoły kryptograficzne

Narzędzia kryptograficzne, takie jak kryptosystemy, schematy podpisów, funkcje skrótu itp., mogą być wykorzystywane samodzielnie w celu osiągnięcia określonych celów bezpieczeństwa. Narzędzia te są jednak również używane jako komponenty w bardziej skomplikowanych protokołach. (Oczywiście protokoły mogą być również projektowane „od zera”, bez korzystania z wcześniejszych wersji pierwotnych).

Ogólnie rzecz biorąc, protokół (lub protokół interaktywny) odnosi się do określonej sekwencji komunikatów wymienianych między dwiema (lub ewentualnie więcej) stronami. Sesja protokołu, powiedzmy między Alicją a Bobem, będzie się składać z jednego lub więcej przepływów, gdzie każdy przepływ składa się z wiadomości wysłanej od Alicji do Boba lub odwrotnie. Pod koniec sesji zaangażowane strony mogą ustalić pewną wspólną informację lub potwierdzić posiadanie pewnych współdzielonych wcześniej informacji.

Jednym z ważnych typów protokołów jest schemat identyfikacji, w którym jedna strona „udowadnia” swoją tożsamość drugiej stronie, na przykład przez wykazanie posiadania hasła. Bardziej zaawansowane protokoły identyfikacyjne będą zamiast tego składać się z dwóch (lub więcej) przepływów, na przykład wyzwanie, po którym następuje odpowiedź, przy czym odpowiedź jest obliczana z wyzwania przy użyciu pewnego tajnego lub prywatnego klucza. Schematy identyfikacji są tematem rozdziału 10.

Istnieje wiele rodzajów protokołów związanych z różnymi aspektami wyboru kluczy lub przekazywania kluczy od jednej strony do drugiej. W schemacie dystrybucji kluczy klucze mogą być wybierane przez podmiot zaufany i przekazywane jednemu lub kilku członkom danej sieci. Inne podejście, które nie wymaga udziału aktywnego, zaufanego organu, nazywane jest uzgadnianiem klucza. W systemie uzgadniania klucza Alicja i Bob (powiedzmy) są w stanie ostatecznie ustalić wspólny, tajny klucz, który nie powinien być znany przeciwnikowi. Te i związane z nimi tematy są omówione w rozdziałach 11 i 12.

Schemat dzielenia się tajną informacją polega na tym, że zaufany organ rozprowadza „części” informacji (zwane „udziałami”) w taki sposób, że niektóre podzbiory udziałów mogą być odpowiednio łączone w celu odtworzenia pewnej wcześniej określonej tajemnicy. Jednym z powszechnych rodzajów schematu tajnego udostępniania informacji jest schemat progowy. W schemacie (k, n)-progowym występuje n udziałów, a każde k udziałów pozwala na odtworzenie tajemnicy. Z drugiej strony, k – 1 lub mniej udziałów nie daje żadnej informacji o wartości tajemnicy. Schematy tajnego udostępniania są analizowane w rozdziale 11.

1.4. Bezpieczeństwo

Podstawowym celem kryptosystemu, schematu podpisu itp. jest jego „bezpieczeństwo”. Ale co to znaczy być bezpiecznym i jak możemy zyskać pewność, że coś jest rzeczywiście bezpieczne? Prawdę mówiąc, chcielibyśmy powiedzieć, że przeciwnik nie może na przykład „złamać” kryptosystemu, ale musimy sprecyzować to pojęcie. Bezpieczeństwo w kryptografii wymaga uwzględnienia trzech różnych aspektów: modelu ataku, celu przeciwnika i poziomu bezpieczeństwa. Omówmy każdy z nich po kolei.

Model ataku określa informacje, które są dostępne dla przeciwnika. Zawsze zakładamy, że przeciwnik zna schemat lub protokół, który jest używany (nazywa się to zasadą Kerckhoffa). Zakłada się również, że przeciwnik zna klucz publiczny (jeśli system jest systemem klucza publicznego). Z drugiej strony, zakłada się, że przeciwnik nie zna używanego tajnego lub prywatnego klucza. Ewentualne dodatkowe informacje przekazywane przeciwnikowi powinny być określone w modelu ataku.

Cel przeciwnika określa dokładnie, co to znaczy „złamać” kryptosystem. Co przeciwnik próbuje zrobić i jakie informacje próbuje określić? Zatem cel przeciwnika definiuje „udany atak”.

Poziom bezpieczeństwa próbuje oszacować wysiłek wymagany do złamania kryptosystemu. Inaczej mówiąc, do jakich zasobów obliczeniowych przeciwnik ma dostęp i ile czasu zajęłoby przeprowadzenie ataku z wykorzystaniem tych zasobów?

Oświadczenie o bezpieczeństwie dla schematu kryptograficznego będzie stwierdzeniem, że przy określonych zasobach obliczeniowych nie można osiągnąć konkretnego celu przeciwnika w określonym modelu ataku.

Ilustrujemy teraz niektóre z powyższych koncepcji w odniesieniu do kryptosystemu. Istnieją cztery powszechnie uznawane modele ataków. W ataku ze znanym szyfrogramem przeciwnik ma dostęp do pewnej ilości szyfrogramów, które są tym samym nieznanym kluczem. W ataku ze znanym jawnym tekstem przeciwnik uzyskuje dostęp do pewnej ilości tekstu jawnego, a także do odpowiadającego mu szyfru (wszystkie są zaszyfrowane tym samym kluczem). W ataku z wybranym tekstem jawnym przeciwnik ma możliwość wybrania tekstu jawnego, a następnie otrzymuje odpowiadający mu szyfrogram. W końcu, w ataku z wybranym szyfrogramem przeciwnik wybiera jakiś szyfrogram, a następnie otrzymuje odpowiadający mu tekst jawny.

Zdecydowanie to atak z wybranym tekstem jawnym lub wybranym szyfrogramem dostarcza przeciwnikowi więcej informacji niż atak ze znanym szyfrogramem. Dlatego są one uważane za silniejsze modele ataku niż atak ze znanym szyfrogramem, ponieważ potencjalnie ułatwiają pracę przeciwnikowi.

Następnym aspektem, który należy zbadać, jest cel przeciwnika. Przy całkowitym złamaniu kryptosystemu przeciwnik określa klucz prywatny (lub tajny). Istnieją jednak inne, słabsze cele, które przeciwnik mógłby potencjalnie osiągnąć, nawet jeśli całkowite złamanie nie jest możliwe. Na przykład przeciwnik może być w stanie odszyfrować nieznany mu wcześniej szyfrogram z określonym niezerowym prawdopodobieństwem, nawet jeśli nie był w stanie określić klucza. Albo przeciwnik może być w stanie określić pewne częściowe informacje o tekście jawnym z pewnym określonym niezerowym prawdopodobieństwem. „Informacje częściowe” mogą zawierać wartości niektórych bitów tekstu jawnego. W końcu, jako przykład słabego celu, przeciwnik może być w stanie rozróżnić szyfrogramy dwóch podanych tekstów jawnych[2].

Inne podstawowe elementy kryptograficzne będą miały różne modele ataku i cele przeciwnika. W schemacie podpisu model ataku określałby, do jakiego rodzaju (ważnych) podpisów przeciwnik ma dostęp. Być może przeciwnik widzi tylko niektóre z wcześniej podpisanych wiadomości, a może poprosić sygnatariusza o podpisanie kilku konkretnych wiadomości, które wybrał. Celem przeciwnika jest zazwyczaj podpisanie jakiejś „nowej” wiadomości (tzn. takiej, dla której przeciwnik nie zna już ważnego podpisu). Być może przeciwnik może znaleźć ważny podpis jakiejś konkretnej wiadomości, którą wybierze, lub może znajdzie ważny podpis dla dowolnej wiadomości. Stanowiłyby one odpowiednio słabe i silne cele przeciwnika.

Często badane są trzy poziomy bezpieczeństwa, które nazywane są bezpieczeństwem obliczeniowym, bezpieczeństwem możliwym do udowodnienia i bezpieczeństwem bezwarunkowym.

Bezpieczeństwo obliczeniowe oznacza, że określony algorytm łamania systemu jest niewykonalny obliczeniowo, tzn. nie może być wykonany w rozsądnym czasie przy użyciu aktualnie dostępnych zasobów obliczeniowych. Oczywiście system, który jest dziś bezpieczny obliczeniowo, może nie być bezpieczny obliczeniowo w nieskończoność. Na przykład mogą zostać odkryte nowe algorytmy, komputery mogą stać się szybsze, a podstawowe nowe paradygmaty obliczeniowe, takie jak obliczenia kwantowe, mogą stać się wykonalne. Obliczenia kwantowe, jeśli staną się dostępne w praktyce, mogą mieć ogromny wpływ na bezpieczeństwo wielu rodzajów kryptografii klucza publicznego. Kwestia ta jest omawiana bardziej szczegółowo w podrozdziale 9.1.

W rzeczywistości bardzo trudno jest przewidzieć, jak długo coś, co dziś uznawane jest za bezpieczne, pozostanie bezpieczne. Istnieje wiele przykładów, w których wiele schematów kryptograficznych nie przetrwało tak długo, jak pierwotnie oczekiwano, ze względu na wspomniane wyżej powody. Doprowadziło to do dość częstych przypadków zastępowania standardów przez ulepszone standardy. Na przykład dla funkcji skrótu pojawiła się seria proponowanych i/lub zatwierdzonych standardów, oznaczonych jako SHA-0, SHA-1, SHA-2 i SHA-3, ponieważ znaleziono nowe ataki i stare standardy stały się niepewne.

Ciekawym przykładem dotyczącym błędnych prognoz jest kryptosystem RSA z kluczem publicznym. W wydaniu Scientific American z sierpnia 1977 roku wybitny badacz matematyczny Martin Gardner napisał artykuł na temat nowo opracowanego kryptosystemu RSA z kluczem publicznym, zatytułowany „Nowy rodzaj szyfru, którego złamanie zajęłoby miliony lat”. W artykule znalazł się szyfrogram stanowiący wyzwanie – tekst zaszyfrowany przy użyciu klucza 512-bitowego. Wyzwanie to zostało jednak rozwiązane 17 lat później, 26 kwietnia 1994 roku, przez rozkład podanego klucza publicznego na czynniki (tekst jawny brzmiał: „the magic words are squeamish ossifrage”, czyli „magiczne słowa to piskliwy rybołów”). Stwierdzenie, że złamanie szyfru zajmie miliony lat, odnosiło się prawdopodobnie do tego, ile czasu zajmie uruchomienie najlepszego algorytmu rozkładu znanego w 1977 roku na najszybszym dostępnym komputerze. Jednak między rokiem 1977 a 1994 nastąpiło kilka zmian, w tym następujące:

• komputery stały się o wiele szybsze,

• znaleziono ulepszone algorytmy oraz

• rozwój Internetu ułatwił prowadzenie rozproszonych obliczeń na dużą skalę.

Oczywiście w zasadzie nie da się przewidzieć, kiedy zostaną odkryte nowe algorytmy. Również trzeci z wymienionych powyżej punktów może być uważany za „zmianę paradygmatu”, o którym prawdopodobnie nikt nawet nie myślał w 1977 roku.

Kolejnym „poziomem” bezpieczeństwa, którym się zajmujemy, jest bezpieczeństwo dające się udowodnić (zwane również bezpieczeństwem redukcjonistycznym) odnoszące się do sytuacji, w której złamanie kryptosystemu (tj. osiągnięcie celu przez przeciwnika) może zostać zredukowane w sensie teoretycznej złożoności do rozwiązania jakiegoś podstawowego (z założenia trudnego) problemu matematycznego. Pokazałoby to, że złamanie kryptosystemu jest co najmniej tak samo trudne jak rozwiązanie danego trudnego problemu. Bezpieczeństwo możliwe do udowodnienia często wiąże się z ograniczeniem problemu rozkładu na czynniki lub problemu logarytmów dyskretnych (problemy te zostały omówione odpowiednio w podrozdziałach 6.6 i 7.2).

Wreszcie, bezwarunkowe bezpieczeństwo oznacza, że kryptosystemu nie da się złamać (tzn. cel przeciwnika nie jest osiągalny) nawet przy nieograniczonych zasobach obliczeniowych, ponieważ przeciwnik nie ma wystarczającej ilości dostępnych informacji (jak określono w modelu ataku), aby mógł to zrobić. Najsłynniejszym przykładem bezwarunkowo bezpiecznego kryptosystemu jest szyfr z kluczem jednorazowym (one-time pad). W tym kryptosystemie kluczem jest losowy ciąg bitów o tej samej długości co tekst jawny. Szyfr jest tworzony jako alternatywa wykluczająca (XOR) tekstu jawnego i klucza. W przypadku one-time pad można matematycznie udowodnić, że przeciwnik nie może uzyskać żadnych częściowych informacji o tekście jawnym (poza jego długością), biorąc pod uwagę tekst jawny, pod warunkiem, że klucz jest używany do szyfrowania tylko jednego ciągu tekstu jawnego i ma taką samą długość jak tekst jawny. Szyfr z kluczem jednorazowym jest omówiony w rozdziale 3.

Celem naszej analizy schematu kryptograficznego jest wykazanie, że przeciwnik nie może osiągnąć słabego celu w silnym modelu ataku, biorąc pod uwagę znaczne zasoby obliczeniowe.

Wcześniejsza dyskusja na temat bezpieczeństwa dotyczyła głównie sytuacji kryptograficznego elementu pierwotnego, jakim jest kryptosystem. Kryptograficzne elementy pierwotne są jednak na ogół łączone w skomplikowany sposób podczas definiowania i ostatecznego wdrażania protokołów. Nawet pozornie proste decyzje implementacyjne mogą prowadzić do nieoczekiwanych luk w zabezpieczeniach. Na przykład, gdy dane są szyfrowane przy użyciu szyfru blokowego, najpierw należy je podzielić na kawałki o stałej długości, np. bloki 128-bitowe. Jeśli dane nie wypełniają dokładnie całkowitej liczby bloków, należy wprowadzić pewne wypełnienia. Okazuje się, że standardowa technika uzupełniania, stosowana w popularnym trybie pracy CBC, jest podatna na atak znany jako atak wyroczni dopełnienia (padding oracle attack), który został odkryty przez Vaudenaya w 2002 roku (opis tego ataku znajduje się w punkcie 4.7.1).

Istnieją również różne rodzaje ataków na fizyczne implementacje kryptografii, które są znane jako ataki bocznym kanałem (side channel attacks). Przykładem mogą być ataki czasowe (timing attacs), ataki analizy błędów (fault analysis attacks), ataki z analizą zużycia mocy (power analysis attacks) oraz ataki typu cache. Chodzi o to, że informacja o tajnym lub prywatnym kluczu może wyciec przez obserwację lub fizyczną manipulację urządzeniem (np. kartą inteligentną), na którym zaimplementowano konkretny schemat kryptograficzny. Jednym z przykładów może być obserwowanie czasu, jaki zajmuje urządzeniu wykonanie pewnych obliczeń (tzw. atak czasowy). Ten wyciek informacji może nastąpić nawet wtedy, gdy schemat jest „bezpieczny”.

1.5. Uwagi i źródła

Istnieje wiele monografii i podręczników na temat kryptografii. Wymienimy tu kilka ogólnych pozycji, które mogą być przydatne dla czytelników.

W celu uzyskania dostępnego, niematematycznego podejścia, polecamy:

• Everyday Cryptography: Fundamental Principles and Applications, wyd. 2, K. Martin [127].

Dla bardziej matematycznego punktu widzenia pomocne są następujące najnowsze teksty:

• An Introduction to Mathematical Cryptography, J. Hoffstein, J. Pipher, J. Silverman [96].

• Introduction to Modern Cryptography, wyd. 2, J. Katz, Y. Lindell [104].

• Understanding Cryptography: A Textbook for Students and Practitioners, C. Paar, J. Pelzl [157].

• Cryptography Made Simple, Nigel Smart [185].

• A Classical Introduction to Cryptography: Applications for Communications Security, S. Vaudenay [196].

Jeśli chodzi o podstawy matematyczne, zwłaszcza w kryptografii klucza publicznego, polecamy

• Mathematics of Public Key Cryptography, S. Galbraith [84].

Na koniec warto wspomnieć o poniższej pozycji, mimo że jest dość nieaktualna:

• Handbook of Applied Cryptography, A.J. Menezes, P.C. Van Oorschot i S.A. Vanstone [134].

Rozdział 2

Klasyczna kryptografia

W tym rozdziale przedstawiamy ogólne wprowadzenie do kryptografii i kryptoanalizy. Prezentujemy kilka prostych systemów i opisujemy, jak można je „złamać”. Po drodze omawiamy różne techniki matematyczne, które będą stosowane w całej książce.

2.1. Wprowadzenie: niektóre proste kryptosystemy

Podstawowym celem kryptografii jest umożliwienie dwóm osobom, zwanym zazwyczaj Alicją i Bobem, komunikowania się przez niepewny kanał w taki sposób, aby przeciwnik, Oskar, nie mógł zrozumieć, o czym jest mowa. Kanałem tym może być na przykład linia telefoniczna lub sieć komputerowa. Informacja, którą Alicja chce wysłać do Boba, nazywana „tekstem jawnym”, może być angielskim (lub polskim) tekstem, danymi liczbowymi lub czymś innym – jej struktura jest całkowicie dowolna. Alicja szyfruje tekst jawny, używając uprzednio ustalonego klucza, i wysyła otrzymany w ten sposób szyfrogram przez kanał. Oscar, widząc dzięki podsłuchowi zaszyfrowany tekst w kanale, nie może określić, czym był tekst jawny, ale Bob, który zna klucz szyfrujący, może ten tekst odszyfrować i odtworzyć.

Pomysły te są formalnie opisane za pomocą następującego zapisu matematycznego.

DEFINICJA 2.1. Kryptosystem jest krotką pięcioelementową (P, C, K, E, D), która spełnia następujące warunki:

1. P jest skończonym zbiorem możliwych tekstów jawnych.

2. C jest skończonym zbiorem możliwych szyfrogramów.

3. K, przestrzeń kluczy, jest skończonym zbiorem możliwych kluczy.

4. Dla każdego K ∈ K istnieje reguła szyfrowania eK ∈ E i odpowiadająca jej reguła odszyfrowania dK ∈ D. Każda eK : P → C i dK : C → P są funkcjami takimi, że dK(eK(x)) = x dla każdego elementu tekstu jawnego x ∈ P.

Najważniejszą właściwością jest właściwość 4. Mówi ona, że jeśli test jawny x został zaszyfrowany przy użyciu eK, a otrzymany szyfrogram zostanie następnie odszyfrowany przy użyciu dK, wynikiem będzie oryginalny tekst jawny x.

RYSUNEK 2.1. Kanał komunikacyjny

Alicja i Bob użyją następującego protokołu, aby wykorzystać konkretny kryptosystem. Najpierw wybierają losowy klucz K ∈ K. Jest to wykonywane, gdy znajdują się w tym samym miejscu i nie są obserwowani przez Oskara, lub, alternatywnie, gdy mają dostęp do bezpiecznego kanału, w którym to przypadku mogą znajdować się w różnych miejscach. Przypuśćmy, że później Alicja chce przekazać wiadomość do Boba przez niepewny kanał. Przyjmujemy, że ta wiadomość jest ciągiem znaków

x = x_1x_2 xn

dla pewnej liczby całkowitej n ≥ 1, gdzie każdy symbol tekstu jawnego xi ∈ P, 1 ≤ i ≤ n. Każdy xi został zaszyfrowany przy użyciu zasady szyfrowania eK określonej przez z góry ustalony klucz K. W ten sposób Alicja oblicza yi = eK(xi), 1 ≤ i ≤ n, a otrzymany ciąg szyfrogramu

y = y_1 y_2 yn

jest przesyłany przez kanał. Gdy Bob otrzymuje y_1 y_2  yn, odszyfrowuje go przy użyciu funkcji odszyfrowania dK, uzyskując oryginalny ciąg tekstu jawnego, x_1 x_2  xn; patrz rysunek 2.1 ilustrujący kanał komunikacyjny.

Oczywiście musi być spełniony warunek, że każda funkcja szyfrująca eK jest funkcją różnowartościową (tzn. jeden do jednego).W przeciwnym razie nie można by było przeprowadzić odszyfrowania w sposób jednoznaczny. Na przykład, jeżeli

y = eK(x_1) = eK(x_2),(2.1)

gdzie x_1 ≠ x_2, to Bob nie może wiedzieć, czy y trzeba rozszyfrować jako x_1, czy jako x_2. Zwróćmy uwagę, że jeśli P = C, wynika z tego, że każda funkcja szyfrująca jest permutacją. Oznacza to, że jeśli zbiór tekstów jawnych i szyfrogramów jest identyczny, to każda funkcja szyfrująca po prostu przestawia (lub permutuje) elementy tego zbioru.

2.1.1. Szyfr przestawieniowy

W tym punkcie opiszemy szyfr przestawieniowy, który jest oparty na arytmetyce modularnej. Ale najpierw przypomnimy kilka podstawowych definicji arytmetyki modularnej.

DEFINICJA 2.2. Załóżmy, że a i b są liczbami całkowitymi, a m jest liczbą całkowitą dodatnią. Wówczas piszemy a ≡ b (mod m), jeśli m jest dzielnikiem b – a. Wyrażenie a ≡ b (mod m) nazywamy kongruencją (przystawaniem) modulo m i czytamy „a jest przystające do b modulo m”. Liczbę całkowitą m nazywamy modułem.

Załóżmy, że dzielimy a i b przez m, otrzymując całkowite ilorazy i reszty, gdzie reszty są między 0 a m – 1. Czyli a = q_1m + r_1, a b = q_2m + r_2, gdzie 0 ≤ r_1 ≤ m – 1 i 0 ≤ r_2 ≤ m – 1. Wtedy nietrudno zauważyć, że a ≡ b (mod m) wtedy i tylko wtedy, gdy r_1 = r2. Użyjemy zapisu a mod m (bez nawiasów), aby oznaczyć resztę z dzielenia a przez m (wartość r_1 powyżej). Zatem a ≡ b (mod m) wtedy i tylko wtedy, gdy a mod m = b mod m. Jeśli zastąpimy a przez a mod m, mówimy, że a jest zredukowana modulo m.

Oto kilka przykładów. Aby obliczyć 101 mod 7, piszemy 101 = 7 × 14 + 3. Ponieważ 0 ≤ 3 ≤ 6, wynika z tego, że 101 mod 7 = 3. W innym przykładzie załóżmy, że chcemy obliczyć (−101) mod 7. W tym wypadku piszemy −101 = 7 × (−15) + 4. Ponieważ 0 ≤ 4 ≤ 6, zatem (−101) mod 7 = 4.

UWAGA. Wiele języków programowania definiuje a mod m jako resztę w zakresie –m + 1, …, m – 1 mającą taki sam znak jak a. Na przykład (–101) mod 7 będzie równe –3, a nie 4, jak zdefiniowano powyżej. Ale do innych celów wygodniej jest zdefiniować a mod m jako wartość zawsze nieujemną.

■

Teraz zdefiniujemy arytmetyczne modulo m: ℤm jest zbiorem {0, …, m – 1}, na którym można wykonywać dwa działania + i ×. Dodawanie i mnożenie w ℤm działa dokładnie tak jak dodawanie i mnożenie liczb rzeczywistych, z wyjątkiem tego, że wyniki są redukowane modulo m.

Przypuśćmy, że mamy obliczyć 11 × 13 w ℤ_16. Ponieważ są to liczby całkowite, 11 × 13 = 143. Następnie redukujemy 143 modulo 16, jak opisano powyżej: 143 = 8 × 16 + 15, więc 143 mod 16 = 15, a zatem 11 × 13 = 15 w ℤ_16.

Te definicje dodawania i mnożenia w ℤ_16 spełniają większość znanych reguł matematycznych. Wymienimy je tutaj bez dowodu:

1. Dodawanie jest domknięte, czyli dla dowolnych a, b ∈ ℤm, a + b ∈ ℤm.

2. Dodawanie jest przemienne, czyli dla dowolnych a, b ∈ ℤm, a + b = b + a.

3. Dodawanie jest łączne, czyli dla dowolnych a, b, c ∈ ℤm, (a + b) + c = a + (b + c).

4. 0 jest elementem neutralnym, czyli dla dowolnego a ∈ ℤm, a + 0 = 0 + a = a.

5. Liczbą przeciwną do dowolnego a ∈ ℤm jest m − a, czyli a + (m − a) = (m − a) + a = 0 dla dowolnego a ∈ ℤm.

KRYPTOSYSTEM 2.1. Szyfr przestawieniowy

Niech P = C = K = ℤ_26. Dla 0 ≤ K ≤ 25 zdefiniowano

eK(x) = (x + K) mod 26

oraz

dK(y) = (y − K) mod 26

(x, y ∈ ℤ_26).

6. Mnożenie jest domknięte, czyli dla każdego a, b ∈ ℤm, ab ∈ ℤm.

7. Mnożenie jest przemienne, czyli dla każdego a, b ∈ ℤm, ab = ba.

8. Mnożenie jest łączne, czyli dla każdego a, b, c ∈ ℤm, (ab)c = a(bc).

9. 1 jest elementem neutralnym mnożenia, czyli dla każdego a ∈ ℤm, a × 1 = 1 × a = a.

10. Spełniona jest właściwość rozdzielności względem dodawania, czyli dla dowolnych a, b, c ∈ ℤm, (a + b)c = (ac) + (bc) i a(b + c) = (ab) + (ac).

Właściwości 1, 3–5 mówią, że ℤm tworzy strukturę algebraiczną nazywaną grupą ze względu na działanie dodawania. Ponieważ ma również właściwość 2, grupa ta jest określana jako grupa przemienna (abelowa).

Właściwości 1–10 ustalają, że ℤm jest w rzeczywistości pierścieniem. W tej książce zobaczymy wiele innych przykładów grup i pierścieni. Niektóre znane przykłady pierścieni to liczby całkowite ℤ, liczby rzeczywiste ℝ oraz liczby zespolone ℂ. Są to jednak wszystko pierścienie nieskończone, a nasza uwaga będzie się ograniczała prawie wyłącznie do pierścieni skończonych.

Ponieważ w ℤm istnieją liczby przeciwne, w ℤm możemy również odejmować elementy. Definiujemy a – b w ℤm jako (a – b) mod m. To oznacza, że obliczamy liczbę całkowitą a – b, a następnie redukujemy ją modulo m. Na przykład, aby obliczyć 11 – 18 w ℤ_31, najpierw odejmujemy 18 od 11, otrzymując –7, a następnie obliczamy (–7) mod 31 = 24.

Przedstawiliśmy szyfr przestawieniowy jako kryptosystem 2.1. Jest on zdefiniowany na ℤ_26, ponieważ obejmuje 26 liter alfabetu łacińskiego, mimo że mógłby być zdefiniowany na ℤm dla dowolnego modulo m. Łatwo zauważyć, że szyfr przestawieniowy tworzy kryptosystem zgodnie z podaną powyżej definicją, czyli dK(eK(x)) = x dla każdego x ∈ ℤ_26.

UWAGA. Dla konkretnego klucza K = 3 kryptosystem jest często nazywany szyfrem Cezara, gdyż rzekomo korzystał z niego Juliusz Cezar.

■

Do szyfrowania zwykłego tekstu angielskiego użylibyśmy szyfru przestawieniowego (z modułem 26), ustawiając powiązanie między znakami alfabetycznymi i resztami modulo 26 w następujący sposób: A ↔ 0, B ↔ 1, …, Z ↔ 25. Ponieważ będziemy używać tego powiązania w kilku przykładach, zarejestrujmy je do wykorzystania w przyszłości:

A

B

C

D

E

F

G

H

I

J

K

L

M

0

1

2

3

4

5

6

7

8

9

10

11

12

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

13

14

15

16

17

18

19

20

21

22

23

24

25

Zilustruje to mały przykład.

Przykład 2.1. Załóżmy, że kluczem szyfru przestawieniowego jest K = 11, a tekstem jawnym jest

wewillmeetatmidnight.

Najpierw przekształcamy tekst jawny na ciąg liczb całkowitych, korzystając z określonych powiazań, i otrzymujemy:

22

4

22

8

11

11

12

4

4

19

0

19

12

8

3

13

8

6

7

19

Następnie dodajemy 11 do każdej wartości, redukując każdą sumę modulo 26:

7

15

7

19

22

22

23

15

15

4

11

4

23

19

14

24

19

17

18

4

Na koniec przekształcamy ciąg liczb całkowitych na litery alfabetu (znaki), otrzymując szyfrogram:

HPHTWWXPPELEXTOYTRSE.

Aby odszyfrować zaszyfrowany tekst, Bob najpierw zamieni go na ciąg liczb całkowitych, następnie odejmie 11 od każdej wartości (redukując modulo 26), a na koniec zamieni ciąg liczb całkowitych na znaki alfabetyczne.

☐

UWAGA. W powyższym przykładzie używamy wielkich liter dla szyfrogramu i małych liter dla tekstu jawnego, aby poprawić czytelność. Zrobimy to również w innych miejscach.

■

Jeśli kryptosystem ma mieć praktyczne zastosowanie, powinien spełniać określone właściwości. Informacyjnie wymieniamy teraz dwie z tych właściwości.

1. Każda funkcja szyfrująca eK i każda funkcja odszyfrowująca dK powinny być możliwe do obliczenia.

2. Przeciwnik, widząc ciąg szyfrogramu y, nie powinien być w stanie ustalić klucza K, który został użyty, ani ciągu tekstu jawnego x.

Druga właściwość definiuje dość ogólnikowo pojęcie „bezpieczeństwa”. Próba obliczenia klucza K, gdy dany jest ciąg szyfrogramów y, nazywana jest kryptoanalizą. Zauważmy, że jeśli Oskar potrafi określić klucz K, to może odszyfrować y tak jak Bob, używając dK. Dlatego określenie K jest co najmniej tak trudne, jak określenie ciągu tekstu jawnego x, biorąc pod uwagę ciąg szyfrogramu y.

Zauważmy, że szyfr przestawieniowy (modulo 26) nie jest bezpieczny, ponieważ może być szyfrowany – analizowany oczywistą metodą wyczerpującego wyszukiwania kluczy. Ponieważ istnieje tylko 26 możliwych kluczy, łatwo jest wypróbować każdą możliwą regułę odszyfrowywania dK, aż do uzyskania ciągu „sensownego” testu jawnego. Zostało to zilustrowane w poniższym przykładzie.

Przykład 2.2. Mając ciąg szyfrogramu

JBCRCLQRWCRVNBJENBWRWN,

kolejno wypróbowujemy klucze odszyfrowujące d_0, d_1 itd. Otrzymujemy:

jbcrclqrwcrvnbjenbwrwn

iabqbkpqvbqumaidmavqvm

hzapajopuaptlzhclzupul

gyzozinotzoskygbkytotk

fxynyhmnsynrjxfajxsnsj

ewxmxglmrxmqiweziwrmri

dvwlwfklqwlphvdyhvqlqh

cuvkvejkpvkogucxgupkpg

btujudijoujnftbwftojof

astitchintimesavesnine

W tym momencie ustaliśmy, że jawnym tekstem jest fraza „a stitch in time saves nine” i możemy skończyć. Kluczem jest K = 9.

☐

Tekst jawny zostanie obliczony tą metodą średnio po wypróbowaniu 26/2 = 13 wartości klucza odszyfrowania.

Jak wskazuje powyższy przykład, warunkiem koniecznym dla bezpieczeństwa kryptosystemu jest to, aby wyczerpujące wyszukiwanie kluczy było niemożliwe, tzn. aby przestrzeń kluczy była bardzo duża. Jak można się jednak spodziewać, duża przestrzeń kluczy nie jest wystarczająca, aby zagwarantować bezpieczeństwo.

2.1.2. Szyfr podstawieniowy

Innym dobrze znanym szyfrem jest szyfr podstawieniowy, który tutaj zdefiniujemy. Ten kryptosystem jest stosowany od setek lat. Zagadkowe „kryptogramy” w gazetach są przykładami szyfrów podstawieniowych. Ten szyfr jest zdefiniowany jako kryptosystem 2.2.

Faktycznie w przypadku szyfru podstawieniowego możemy przyjąć, że zarówno P, jak i C są 26-literowym angielskim alfabetem. W szyfrze przestawieniowym użyliśmy ℤ26, ponieważ i szyfrowanie, i odszyfrowanie są działaniami algebraicznymi. Natomiast w szyfrze podstawieniowym wygodniej traktować szyfrowanie i odszyfrowywanie jako permutacje znaków alfabetu.

KRYPTOSYSTEM 2.2. Szyfr podstawieniowy

Niech P = C = ℤ26. K składa się ze wszystkich możliwych permutacji 26 symboli 0, 1,…, 25. Dla każdej permutacji π ∈ K, zdefiniowano

eπ(x) = π(x)

i zdefiniowano

dπ(y) = π−1(y),

gdzie π−1 jest permutacją odwrotną do π.

Jest to przykład „losowej” permutacji π, która może zawierać funkcję szyfrowania. (Tak jak poprzednio, tekst jawny piszemy małymi literami, a szyfrogram wielkimi literami).

a

b

c

d

e

f

g

h

i

j

k

l

m

X

N

Y

A

H

P

O

G

Z

Q

W

B

T

n

o

p

q

r

s

t

u

v

w

x

y

z

S

F

L

R

C

V

M

U

E

K

J

D

I

Zatem eπ(a) = X, eπ(b) = N itd. Funkcja odszyfrowująca jest odwrotną permutacją. Tworzy się ją przez zapisanie najpierw drugich wierszy, a następnie ich posortowanie w porządku alfabetycznym. Otrzymuje się:

A

B

C

D

E

F

G

H

I

J

K

L

M

d

l

r

y

v

o

h

e

z

x

w

p

t

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

b

g

f

j

q

n

m

u

s

k

a

c

i

Stąd dπ(A) = d, dπ(B) = l itd.

W ramach ćwiczenia czytelnik może rozszyfrować następujący szyfrogram, korzystając z następującej funkcji odszyfrowującej:

MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA.

Klucz szyfru podstawieniowego składa się z permutacji 26 znaków alfabetu. Liczba możliwych permutacji wynosi 26!, czyli więcej niż 4,0 × 10^26, co jest bardzo dużą liczbą. Wyczerpujące wyszukiwanie kluczy jest więc niemożliwe, nawet dla komputera. Zobaczymy jednak później, że szyfr podstawieniowy można łatwo zaszyfrować innymi metodami.

2.1.3. Szyfr afiniczny

Szyfr przestawieniowy jest specjalnym przypadkiem szyfru podstawieniowego, który obejmuje tylko 26 z 26! możliwych permutacji 26 elementów. Innym specjalnym przypadkiem szyfru podstawieniowego jest szyfr afiniczny, który teraz opiszemy. W szyfrze afinicznym ograniczamy funkcje szyfrowania do funkcji w postaci

e(x) = (ax + b) mod 26,

gdzie a, b ∈ ℤ_26. Taką funkcję nazywamy funkcją afiniczną, stąd nazwa szyfr afiniczny. (Zauważmy, że dla a = 1 otrzymujemy szyfr przestawieniowy). Zbadajmy, czy funkcja afiniczna jest różnowartościowa. Innymi słowy, dla każdego y ∈ ℤ_26 chcemy, aby kongruencja

ax + b ≡ y (mod 26)

miała jednoznaczne rozwiązania dla x. Ta kongruencja jest odpowiednikiem

ax ≡ y − b (mod 26).

Teraz, ponieważ y zmienia się w ℤ_26, więc również y – b zmienia się w ℤ_26. Zatem wystarczy zbadać kongruencję ax ≡ y (mod 26) (y ∈ ℤ_26).

Twierdzimy, że ta kongruencja ma jedyne rozwiązanie dla każdego y wtedy i tylko wtedy, gdy NWD(a, 26) = 1 (gdzie funkcja NWD oznacza największy wspólny dzielnik jej argumentów). Najpierw załóżmy, że NWD(a, 26) = d > 1. Wówczas kongruencja ax ≡ 0 (mod 26) ma (przynajmniej) dwa różne rozwiązania w ℤ_26, a mianowicie x = 0 i x = 26/d. W tym przypadku e(x) = (ax + b) mod 26 nie jest funkcją różnowartościową, a zatem nie jest poprawną funkcją szyfrowania.

Na przykład, ponieważ NWD(4, 26) = 2, wynika z tego, że 4x + 7 nie jest poprawną funkcją szyfrowania: x i x + 13 zostaną zaszyfrowane do tej samej wartości dla każdego x ∈ ℤ_26.

Niech NWD(a, 26) = 1. Załóżmy, że dla pewnych x_1 i x_2

ax_1≡ ax_2 (mod 26).

Wówczas

a(x_1− x_2) ≡ 0 (mod 26),

zatem

26 | a(x_1− x_2).

Teraz wykorzystamy podstawową właściwość dzielenia liczb całkowitych: jeśli NWD(a, b) = 1 oraz a | bc, to a | c. Ponieważ 26 | a(x_1− x_2) oraz NWD(a, 26) = 1, musi zatem zachodzić

26 | (x_1− x_2),

czyli x_1≡ x_2 (mod 26).

Pokazaliśmy tutaj, że jeśli NWD(a, 26) = 1, to kongruencja w postaci ax ≡ y (mod 26) ma co najwyżej jedno rozwiązanie w ℤ_26. Zatem, jeśli pozwolimy x zmieniać się w ℤ_26, to ax mod 26 przyjmuje 26 różnych wartości modulo 26. To znaczy, że przyjmuje każdą wartość dokładnie raz. Wynika z tego, że dla każdego y ∈ ℤ_26 kongruencja ax ≡ y (mod 26) ma jedno rozwiązanie dla x.

Nie ma niczego szczególnego w liczbie 26 użytej jako argument. Poniższy wynik można udowodnić w analogiczny sposób.

TWIERDZENIE 2.1. Kongruencja ax ≡ b (mod m) ma jedno rozwiązanie x ∈ ℤm dla każdego b ∈ ℤm wtedy i tylko wtedy, gdy NWD(a, m) = 1.

Ponieważ 26 = 2 ×13, wartościami a ∈ ℤ_26, takimi że NWD(a, 26) = 1, są a = 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 i 25. Parametr b może być dowolnym elementem z ℤ26. Zatem szyfr afiniczny ma 12 × 26 = 312 możliwych kluczy. (Oczywiście jest to zbyt mało, aby było to bezpieczne).

Rozważmy teraz ogólne ustawienie, w którym modułem jest m. Potrzebujemy innej definicji z teorii liczb.

DEFINICJA 2.3. Załóżmy, że a ≥ 1 i m ≥ 2 są liczbami całkowitymi. Jeśli NWD(a, m) = 1, to mówimy, że a i m są względnie pierwsze. Liczba liczb całkowitych w ℤm, które są względnie pierwsze z m, jest często oznaczana jako φ(m) (ta funkcja nosi nazwę funkcji φ Eulera[3]).

Dobrze znana zależność z teorii liczb wiąże wartość φ(m) z rozkładem m na potęgi liczb pierwszych. (Liczba całkowita p > 1 jest liczbą pierwszą, jeśli nie ma żadnych dodatnich dzielników liczb pierwszych poza 1 i p. Każdą liczbę całkowitą m > 1 można w sposób jednoznaczny rozłożyć na czynniki będące potęgami liczb pierwszych. Na przykład 60 = 2^2 × 3 × 5 i 98 = 2 × 7^2).

Zapisujemy wzór na φ(m) w poniższym twierdzeniu.

TWIERDZENIE 2.2. Niech

gdzie pi są różnymi liczbami pierwszymi oraz ei > 0, 1 ≤ i ≤ n. Wówczas

Wynika z tego, że liczba kluczy szyfru afinicznego w ℤm wynosi mφ(m), gdzie φ(m) jest podane powyższym wzorem. (Liczba wyborów dla b wynosi m, a liczba wyborów dla a wynosi φ(m), gdzie funkcją szyfrowania jest e(x) = ax + b). Załóżmy dla przykładu, że m = 60. Mamy

60 = 2^2 × 3^1 × 5^1,

a zatem

φ(60) = (4 − 2) × (3 − 1) × (5 − 1) = 2 × 2 × 4 = 16

Liczba kluczy w szyfrze afinicznym wynosi 60 × 16 = 960.

Rozważmy operację odszyfrowania szyfru afinicznego z modułem m = 26. Załóżmy, że NWD(a, 26) = 1. Do odszyfrowania musimy rozwiązać kongruencję y ≡ ax + b (mod 26) dla x. W powyższym omówieniu ustalono, że kongruencja będzie mieć jedno rozwiązanie w ℤ_26, lecz nie daje nam to efektywnej metody jej znajdowania. Jest nam do tego potrzebny skuteczny algorytm. Na szczęście kilka dalszych narzędzi z arytmetyki modularnej dostarczy nam skutecznego algorytmu odszyfrowywania, którego szukamy.

Jest nam potrzebne pojęcie liczby odwrotnej.

DEFINICJA 2.4. Załóżmy, że a ∈ ℤm. Liczbą odwrotną (odwrotnością multiplikatywną) do a modulo m, oznaczaną jako a−1 mod m, jest element a′ ∈ ℤm, taki że aa′ ≡ a′a ≡ 1 (mod m). Jeśli m jest ustalone, piszemy czasami a−1 zamiast a−1 mod m.

Za pomocą argumentów podobnych do przedstawionych powyżej można pokazać, że a ma odwrotność modulo m wtedy i tylko wtedy, gdy NWD(a, m) = 1. Jeśli istnieje liczba odwrotna, jest ona jednoznaczna modulo m. Zauważmy również, że jeśli b = a−1, to a = b−1. Jeśli p jest liczbą pierwszą, to każdy element niezerowy ℤm ma odwrotność. Pierścień, w którym jest to prawda, nosi nazwę ciała.

W punkcie 6.2.1 opisujemy efektywny algorytm obliczania odwrotności w ℤm dla wielu m. Jednak w ℤ_26 metoda prób i błędów wystarczy, aby znaleźć odwrotności elementów względnie pierwszych do 26:

1–1 = 1,

3–1 = 9,

5–1 = 21,

7–1 = 15,

11–1 = 19,

17–1 = 23 oraz

25–1 = 25.

(To wszystko można łatwo sprawdzić. Na przykład 7 × 15 = 105 ≡ 1 (mod 26), więc 7−1 = 15 i 15−1 = 7).

Weźmy pod uwagę naszą kongruencję y ≡ ax + b (mod 26). Jest to równoważne

ax ≡ y − b (mod 26).

Ponieważ NWD(a, 26) = 1, a ma odwrotność modulo 26. Mnożąc obie strony kongruencji przez a−1, otrzymujemy

a−1(ax) ≡ a−1(y − b) (mod 26).

Na podstawie łączności mnożenia modulo 26 mamy

a−1(ax) ≡ (a−1 a)x ≡ 1x ≡ x (mod 26).

KRYPTOSYSTEM 2.3. Szyfr afiniczny

Niech P = C = ℤ_26 i niech

K = {(a, b) ∈ ℤ_26 × ℤ_26 : NWD(a, 26) = 1}.

Dla K = (a, b) ∈ K definiujemy

eK(x) = (ax + b) mod 26

i

dK(y) = a−1(y − b) mod 26

(x, y ∈ ℤ_26).

W rezultacie x = a–1(y – b) mod 26. Jest to bezpośredni wzór na x, czyli funkcją odszyfrowującą jest

dK(y) = a−1(y − b) mod 26.

Pełny opis szyfru afinicznego podano jako kryptosystem 2.3.

Rozpatrzmy mały przykład.

Przykład 2.3. Załóżmy, że K = (7, 3). Jak wspomniano powyżej, 7−1 mod 26 = 15. Funkcją szyfrującą jest

eK(x) = 7x + 3,

a odpowiednią funkcją odszyfrowującą jest

dK(y) = 15(y − 3) = 15y − 19,

gdzie wszystkie działania są wykonywane w ℤ_26. Dobrze jest sprawdzić, że dK(eK(x)) = x dla wszystkich x ∈ ℤ_26. Obliczając w ℤ_26, otrzymujemy

dK(eK(x)) = dK(7x + 3) = 15(7x + 3) – 19 = x + 45 – 19 = x.

Aby to zilustrować, zaszyfrujmy tekst jawny hot. Najpierw przekształcamy h, o, t na reszty modulo 26. Wynoszą one odpowiednio 7, 14 i 19. Teraz szyfrujemy:

(7 × 7 + 3) mod 26 = 52 mod 26 = 0

(7 × 14 + 3) mod 26 = 101 mod 26 = 23

(7 × 19 + 3) mod 26 = 136 mod 26 = 6.

Tak więc trzema znakami szyfrogramu są 0, 23 i 6, co odpowiada ciągowi alfabetycznemu AXG. Odszyfrowanie pozostawiamy jako ćwiczenie dla czytelnika.

☐

KRYPTOSYSTEM 2.4. Szyfr Vigenère’a

Niech m jest liczbą całkowitą dodatnią. Zdefiniujemy P = C = K = (ℤ 26)m. Dla klucza K = (k_1, k_2, …, km) definiujemy

i

Przy czym wszystkie działania są wykonywane w ℤ_26.

2.1.4. Szyfr Vigenère’a

Zarówno w szyfrze przestawieniowym, jak i podstawieniowym, gdy zostanie wybrany klucz, każdy znak alfabetyczny jest odwzorowywany na niepowtarzalny znak alfabetu. Z tego powodu te kryptosystemy są nazywane kryptosystemami monoalfabetycznymi. Przedstawiamy teraz kryptosystem, który nie jest monoalfabetyczny, dobrze znany szyfr Vigenère’a, jako kryptosystem 2.4. Nazwa tego szyfru pochodzi od nazwiska Blaise’a de Vigenère’a, który żył w XVI wieku.

Korzystając z opisanej wcześniej zależności A ↔ 0, B ↔ 1, …, Z ↔ 25, możemy powiązać każdy klucz K z ciągiem alfabetycznym o długości m, nazywanym słowem kluczowym. Szyfr Vigenère’a szyfruje m znaków alfabetu naraz: każdy element tekstu jawnego odpowiada m znakom alfabetu.

Rozpatrzmy niewielki przykład.

Przykład 2.4. Załóżmy, że m = 6, a słowem kluczowym jest CIPHER. Jego liczbowym odpowiednikiem jest K = (2, 8, 15, 7, 4, 17). Załóżmy, że tekstem jest ciąg

thiscryptosystemisnotsecure.

Przekształcamy elementy tekstu jawnego na reszty modulo 26, zapisujemy je w grupach po sześć, a następnie „dodajemy” słowo kluczowe modulo 26, jak poniżej:

19

7

8

18

2

17

24

15

19

14

18

24

2

8

15

7

4

17

2

8

15

7

4

17

21

15

23

25

6

8

0

23

8

21

22

15

18

19

4

12

8

18

13

14

19

18

4

2

2

8

15

7

4

17

2

8

15

7

4

17

20

1

19

19

12

9

15

22

8

25

8

19

20

17

4

2

8

15

22

25

19

Alfabetycznym odpowiednikiem ciągu szyfru będzie zatem:

VPXZGIAXIVWPUBTTMJPWIZITWZT.

Aby to odszyfrować, możemy użyć tego samego słowa kluczowego, ale zamiast dodawać, odejmiemy je modulo 26 od szyfrogramu.

☐

Zwróćmy uwagę, że liczba możliwych kluczy o długości m w szyfrze Vigenère’a wynosi 26m, więc nawet dla stosunkowo niewielkich wartości m wyczerpujące wyszukiwanie klucza będzie wymagać dużo czasu. Na przykład, jeśli weźmiemy m = 5, to przestrzeń klucza ma rozmiar przekraczający 1,1 × 10^7. To już wystarczy, aby uniemożliwić wyczerpujące ręczne (ale nie komputerowe) wyszukiwanie kluczy.

W szyfrze Vigenère’a, mając klucz o długości m, można odwzorować znak alfabetyczny na jeden z m możliwych znaków alfabetu (zakładając, że słowo kluczowe zawiera m różnych znaków).Taki system jest nazywany kryptosystemem polialfabetycznym. Ogólnie kryptoanaliza jest trudniejsza dla kryptosystemów polialfabetycznych niż dla monoalfabetycznych.

2.1.5. Szyfr Hilla

W tym punkcie opisujemy inny kryptosystem polialfabetyczny nazywany szyfrem Hilla. Szyfr ten został wynaleziony w 1929 roku przez Lestera S. Hilla. Niech m będzie liczbą całkowitą dodatnią i zdefiniujmy P = C = (ℤ_26)m. Idea jest taka, aby wziąć m liniowych kombinacji m znaków alfabetu w elemencie tekstu jawnego, w ten sposób tworząc m znaków alfabetu w elemencie szyfrogramu.

Na przykład, jeśli m = 2, możemy zapisać element tekstu jawnego jako x = (x_1, x_2) oraz element szyfrogramu jako y = (y_1, y_2). Tutaj y_1 będzie liniową kombinacją x_1 i x_2, podobnie jak y_2. Możemy przyjąć

Oczywiście można to zapisać bardziej zwięźle w zapisie macierzowym w następujący sposób:

gdzie wszystkie działania są wykonywane w ℤ26. Ogólnie przyjmiemy za nasz klucz macierz K o wymiarze m × m. Jeśli elementem w wierszu i oraz kolumnie j macierzy jest ki,j, to piszemy K = (ki,j). Dla x = (x_1, …, xm) ∈ P i K ∈ K obliczamy y = eK(x) = (y_1, …, ym):

Innymi słowy, używając zapisu macierzowego, y = xK.

Mówimy, że szyfrogram jest uzyskiwany z tekstu jawnego za pomocą transformacji liniowej. Musimy się zastanowić, jak będzie działać odszyfrowanie, czyli jak można obliczyć x na podstawie y. Czytelnicy zaznajomieni z algebrą liniową zdadzą sobie sprawę, że do rozszyfrowania użyjemy macierzy odwrotnej K –1. Szyfrogram jest odszyfrowywany przy użyciu równania macierzowego x = yK –1.

Oto definicje niezbędnych pojęć z algebry liniowej. Jeśli A = (ai,j) jest macierzą ℓ × m i B = (bj,k) jest macierzą m× n, to definiujemy iloczyn macierzy AB = (ci,k) według wzoru

dla 1 ≤ i ≤ ℓ oraz 1 ≤ k ≤ n. To znaczy, że wynik w wierszu i oraz kolumnie k macierzy AB jest tworzony przez pomnożenie przez siebie odpowiednich elementów i-tego wiersza A i k-tej kolumny macierzy B i ich zsumowanie. Zwróćmy uwagę, że AB jest macierzą ℓ × n.

Mnożenie macierzy jest łączne (czyli (AB)C = A(BC)), lecz nie jest ogólnie przemienne (nie zawsze AB = BA, nawet dla macierzy kwadratowych A i B).

Macierz jednostkowa (tożsamościowa) m × m, oznaczona jako Im, jest macierzą m × m z jedynkami na głównej przekątnej i zerami na wszystkich pozostałych pozycjach. Wówczas macierzą jednostkową 2 × 2 jest

Im jest nazywana macierzą jednostkową, ponieważ AIm = A dla każdej macierzy A o wymiarze ℓ × m i ImB = B dla każdej macierzy B o wymiarze m × n. Natomiast macierzą odwrotną do macierzy A o wymiarze m × m (jeśli istnieje) jest macierz A–1 taka, że AA–1 = A–1A = Im. Nie wszystkie macierze mają odwrotności, ale jeśli istnieje macierz odwrotna, to jest niepowtarzalna.

Dysponując tą wiedzą, łatwo jest wyprowadzić podany powyżej wzór szyfrowania, zakładając, że K ma macierz odwrotną K−1. Ponieważ y = xK, możemy pomnożyć obie strony wzoru przez K−1, otrzymując

(Zwróćmy uwagę na wykorzystanie cechy łączności).

Możemy sprawdzić, że zdefiniowany powyżej przykład macierzy szyfrowania ma odwrotność w ℤ_26:

ponieważ

(Pamiętajmy, że wszystkie działania arytmetyczne są wykonywane modulo 26).

Rozpatrzmy teraz przykład, aby zilustrować szyfrowanie i odszyfrowanie w szyfrze Hilla.

Przykład 2.5. Załóżmy, że kluczem jest

Z powyższego obliczenia mamy

Załóżmy, że chcemy zaszyfrować jawny test july. Mamy dwa elementy tekstu jawnego do zaszyfrowania: (9, 20) (odpowiadający ju) oraz (11, 24) (odpowiadający ly). Liczymy w następujący sposób:

oraz

Zatem szyfrogramem july jest DELW. Aby to odszyfrować, Bob obliczyłby:

i

Stąd otrzymuje się tekst jawny.

☐

W tym momencie pokazaliśmy, że odszyfrowanie jest możliwe, jeśli K ma odwrotność. W rzeczywistości, aby odszyfrowanie było możliwe, K musi mieć odwrotność. (Wynika to w łatwy sposób z elementarnej algebry liniowej, ale nie podamy tu żadnego dowodu). Interesują nas więc dokładnie te macierze K, które są odwracalne.

Odwracalność macierzy (kwadratowej) zależy od wartości jej wyznacznika, którą teraz zdefiniujemy.

DEFINICJA 2.5. Załóżmy, że A = (ai,j) jest macierzą m × m. Dla 1 ≤ i ≤ m, 1 ≤ j ≤ m zdefiniujmy Aij jako macierz otrzymaną z A przez usunięcie wiersza i oraz kolumny j. Wyznacznikiem A, oznaczonym jako det A, jest wartość a1,1, jeśli m = 1. Jeśli m >1, to det A jest obliczany rekurencyjnie ze wzoru

gdzie i jest dowolną stałą liczbą całkowitą między 1 a m.

Nie jest wcale oczywiste, że wartość det A jest niezależna od wyboru i we wzorze podanym powyżej, ale można udowodnić, że tak rzeczywiście jest. Przydatne będzie wypisanie wzorów dla wyznaczników macierzy 2 × 2 i 3 × 3. Jeśli A = (ai,j) jest macierzą 2 × 2, to

Jeśli A = (ai,j) jest macierzą 3 × 3, to

Dla dużych m wykorzystanie wzoru rekurencyjnego podanego w powyższej definicji nie jest zazwyczaj bardzo efektywną metodą obliczania wyznacznika m × m macierzy kwadratowej. Preferowaną metodą jest obliczanie wyznacznika za pomocą tzw. działań elementarnych na wierszach (patrz dowolny tekst na temat algebry liniowej).

Dwiema ważnymi cechami wyznaczników, z których będziemy korzystać, są det Im= 1 oraz reguła mnożenia det(AB) = det A × det B.

Macierz rzeczywista K ma odwrotność wtedy i tylko wtedy, gdy jej wyznacznik jest niezerowy. Ważne jest jednak, aby pamiętać, że korzystamy z ℤ_26. Istotnym wynikiem dla naszych celów jest to, że macierz K ma odwrotność modulo 26 wtedy i tylko wtedy, gdy NWD(det K, 26) = 1. Aby zobaczyć, że ten warunek jest konieczny, załóżmy, że macierz K ma odwrotność, oznaczoną K–1. Zgodnie z regułą mnożenia wyznaczników mamy:

Zatem det K jest odwrotnością w ℤ_26, co jest prawdziwe wtedy i tylko wtedy, gdy NWD(det K, 26) = 1.

Wystarczalność tego stanu można ustalić na kilka sposobów. Podamy wzór na odwrotność macierzy K. Zdefiniujmy macierz K* jako macierz zawierającą wartości elementów (i, j) obliczone jako wartość (–1)i+j det Kji. (Przypomnijmy, że Kji jest uzyskane z K przez usunięcie j-ego wiersza i i-tej kolumny). K* jest nazywana macierzą sprzężoną K. Podajemy bez dowodu następujące twierdzenie dotyczące odwrotności macierzy w ℤn.

TWIERDZENIE 2.3. Załóżmy, że K = (ki,j) jest macierzą m × m w ℤn, taką że det K jest odwracalna w ℤn. Wówczas K −1 = (det K)−1K*, gdzie K* jest macierzą sprzężoną K.

UWAGA. Powyższy wzór na K –1 nie jest zbyt efektywny obliczeniowo, z wyjątkiem małych wartości m (np. m = 2, 3). Dla większych m preferowaną metodą obliczania macierzy odwrotnych jest wykonywanie elementarnych operacji na wierszach macierzy K.

■

W przypadku 2 × 2 mamy następujący wzór, który jest bezpośrednim wnioskiem z twierdzenia 2.3.

WNIOSEK 2.4. Załóżmy, że

jest macierzą, która ma elementy w ℤn, a det K = k1,1k2,2 − k1,2k2,1 jest odwracalna w ℤn. Wówczas

Popatrzmy ponownie na rozważany wcześniej przykład. Najpierw mamy

Teraz 1−1 mod 26 = 1, więc macierzą odwrotną jest

jak wcześniej sprawdziliśmy.

Oto inny przykład z macierzą 3 × 3.

Przykład 2.6. Załóżmy, że

gdzie wszystkie elementy są w ℤ_26. Czytelnik może sprawdzić, że det K = 7. W ℤ_26 mamy 7−1 mod 26 = 15. Macierzą sprzężoną jest

Ostatecznie macierzą odwrotną jest

☐

Jak wspomniano powyżej, szyfrowanie za pomocą szyfru Hilla odbywa się przez pomnożenie tekstu jawnego przez macierz K, natomiast odszyfrowanie mnoży szyfrogram przez macierz odwrotną K–1. Podajemy dokładny opis matematyczny szyfru Hilla w ℤ_26 jako kryptosystem 2.5.

KRYPTOSYSTEM 2.5. Szyfr Hilla

Niech m ≥ 2 będzie liczbą całkowitą. Niech P = C = (ℤ_26)m i niech

K = {macierze odwracalne m × m w ℤ_26}.

Dla klucza K definiujemy

eK(x) = xK

oraz

dK(y) = yK−1,

gdzie wszystkie działania są wykonywane w ℤ_26.

2.1.6. Szyfr permutacyjny

Wszystkie kryptosystemy, o których była mowa do tej pory, wymagają zastępowania: znaki jawne są zastępowane różnymi znakami szyfrującymi. Ideą szyfrów permutacyjnych jest zachowanie niezmienionych znaków alfabetu zwykłego, lecz zmiana ich pozycji przez zmianę ich układu za pomocą permutacji.

Permutacja zbioru skończonego X jest funkcją wzajemnie jednoznaczną π : X → X. Innymi słowy, funkcja π jest funkcją różnowartościową oraz „na” (surjektywna). Wynika z tego, że dla każdego x ∈ X, istnieje niepowtarzalny element x′ ∈ X, taki że π(x′) = x. To powala nam zdefiniować permutację odwrotną π−1 : X → X zgodnie z regułą

π−1(x) = x′ wtedy i tylko wtedy, gdy π(x′) = x.

Wówczas π−1 jest również permutacją X.

Szyfr permutacyjny (znany także jako szyfr transpozycyjny) jest formalnie zdefiniowany jako kryptosystem 2.6. Ten kryptosystem był stosowany przez setki lat. Rozróżnienie między szyfrem permutacyjnym a szyfrem podstawieniowym zostało wskazane w 1563 roku przez Giovanniego Portę.

Podobnie jak w przypadku szyfrów podstawieniowych, wygodniejsze jest używanie znaków alfabetycznych w przeciwieństwie do reszt modulo 26, ponieważ w szyfrowaniu i odszyfrowywaniu nie są wykonywane żadne działania algebraiczne.

Oto przykład, który to ilustruje:

Przykład 2.7. Załóżmy, że m = 6 i kluczem jest następująca permutacja π:

x

1

2

3

4

5

6

π(x)

3

5

1

6

4

2

Zwróćmy uwagę, że pierwszy wiersz w powyżej tabeli zawiera wartości x, 1 ≤ x ≤ 6, a drugi wiersz zawiera odpowiednie wartości π(x). Wówczas permutacją odwrotną π−1 można utworzyć, zamieniając dwa wiersze i porządkując kolumny tak, że pierwszy wiersz jest uporządkowany rosnąco. Przeprowadzając te działania, widzimy, że permutacja π–1 jest następująca:

x

1

2

3

4

5

6

π−1 (x)

3

6

1

5

2

4

KRYPTOSYSTEM 2.6. Szyfr permutacyjny

Niech m będzie liczbą całkowitą dodatnią. Niech P = C = (ℤ_26)m i niech K składa się ze wszystkich permutacji {1, …, m}. Dla klucza (czyli permutacji) π definiujemy

oraz

gdzie π−1 jest odwrotną permutacją π.

Teraz załóżmy, że mamy test jawny

shesellsseashellsbytheseashore.

Najpierw podzielimy tekst jawny na grupy złożone z sześciu liter:

shesel|lsseas|hellsb|ythese|ashore

Teraz każda grupa sześciu liter zostaje uporządkowana według permutacji π, co daje następujące wyniki:

EESLSH|SALSES|LSHBLE|HSYEET|HRAEOS

Zatem szyfrogramem jest:

EESLSHSALSESLSHBLEHSYEETHRAEOS.

Szyfrogram można odszyfrować w podobny sposób, korzystając z odwrotnej permutacji π−1.

☐

Pokażemy teraz, że szyfr permutacyjny jest specjalnym przypadkiem szyfru Hilla. Mając permutację π zbioru {1, …, m}, możemy zdefiniować powiązaną macierz permutacji m × m Kπ = (ki,j) zgodnie ze wzorem

(Macierz permutacji jest macierzą, w której każdy wiersz i kolumna zawierają dokładnie jedną „1”, a wszystkie pozostałe wartości są równe „0”. Macierz permutacji można otrzymać z macierzy jednostkowej, przestawiając wiersze i kolumny).

Nietrudno zauważyć, że szyfrowanie Hilla przy użyciu macierzy Kπ jest w rzeczywistości równoważne szyfrowaniu permutacyjnemu przy użyciu permutacji π. Ponadto Kπ−1 = Kπ−1, czyli odwrotna macierz do Kπ jest macierzą permutacyjną zdefiniowaną przez permutację π−1. Tak więc odszyfrowanie Hilla jest równoważne z rozszyfrowaniem permutacyjnym.

Dla permutacji π użytej w powyższym przykładzie związane z nią macierze permutacyjne są następujące:

oraz

Czytelnik może sprawdzić, że iloczyn tych dwóch macierzy jest macierzą jednostkową.

2.1.7. Szyfry strumieniowe

W kryptosystemach, których uczyliśmy się do tej pory, kolejne elementy zwykłego tekstu są szyfrowane przy użyciu tego samego klucza K. Oznacza to, że ciąg szyfrujący y jest otrzymywany w następujący sposób:

Kryptosystemy tego typu są często nazywane szyframi blokowymi.

Alternatywnym podejściem jest stosowanie tzw. szyfrów strumieniowych. Podstawową ideą jest wygenerowanie strumienia kluczy z = z_1z_2, i użycie go do szyfrowania strumienia tekstu jawnego x = x_1x_2 ·∙∙ według wzoru

Najprostszym typem szyfru strumieniowego jest taki, w którym strumień klucza jest skonstruowany z klucza, niezależnie od ciągu tekstu jawnego, przy użyciu określonego algorytmu. Ten typ szyfru strumieniowego jest nazywany „synchronicznym” i może być formalnie zdefiniowany w następujący sposób:

DEFINICJA 2.6. Synchroniczny szyfr strumieniowy jest krotką (P, C, K, , E, D ) wraz z funkcją g, taką że spełnione są następujące warunki:

1. P jest skończonym zbiorem możliwych tekstów jawnych.

2. C jest skończonym zbiorem możliwych szyfrogramów.

3. K, przestrzeń klucza, jest skończonym zbiorem możliwych kluczy.

4.  jest skończonym zbiorem o nazwie alfabet strumienia klucza.

5. g jest generatorem strumienia klucza. g przyjmuje klucz K jako wejście i generuje ciąg nieskończony z_1z_2 ⋯ o nazwie strumień klucza, gdzie zi ∈ , dla wszystkich dla i ≥ 1.

6. Dla każdego z ∈ istnieje reguła szyfrowania ez ∈ E i odpowiednia reguła odszyfrowania dz ∈ D. ez : P → C i dz : C → P są funkcjami takimi, że dz(ez(x)) = x dla każdego elementu testu jawnego x ∈ P.

Aby zilustrować tę definicję, pokazujemy, jak szyfr Vigenère’a może być zdefiniowany jako synchroniczny szyfr strumieniowy. Załóżmy, że m jest długością słowa kluczowego szyfru Vigenère’a. Zdefiniujmy K = (ℤ_26)m i P = C =  = ℤ_26 oraz zdefiniujmy ez(x) = (x + z) mod 26 i dz(y) = (y – z) mod 26. Na koniec zdefiniujmy strumień kluczy z_1z_2 ∙∙∙ w następujący sposób:

gdzie K = (k_1, …, km). To generuje strumień klucza

z klucza K = (k_1, k_2, …, km).

UWAGA. Szyfr blokowy można traktować jako specjalny przypadek szyfru strumieniowego, w którym strumień klucza jest stałą: zi = K dla każdego i ≥ 1.

■

Szyfr strumieniowy jest okresowym szyfrem strumieniowym z okresem d, jeśli zi+d = zi dla wszystkich i ≥ 1. Szyfr Vigenère’a z długością klucza m, jak opisano powyżej, może być uważany za okresowy szyfr strumieniowy z okresem m.

Szyfry strumieniowe są często opisywane w kategoriach alfabetów binarnych, czyli P = C =  = ℤ_2. W takiej sytuacji działania szyfrowania i odszyfrowania są tylko dodawaniem modulo 2:

oraz

Jeśli myślimy o „0” jako reprezentującym wartość boolowską „false” i „1” jako reprezentującym „true”, to dodanie modulo 2 odpowiada alternatywie wykluczającej (exclusive-or). Dlatego też szyfrowanie (i odszyfrowywanie) może być bardzo efektywnie zaimplementowane w sprzęcie.

Przyjrzyjmy się innej metodzie generowania (synchronicznego) strumienia klucza. Będziemy korzystać z alfabetów binarnych. Załóżmy, że zaczynamy od binarnej krotki m-elementowej (k_1, …, km) i niech zi = ki, 1 ≤ i ≤ m (jak poprzednio). Teraz generujemy strumień klucza, korzystając z liniowej rekurencji rzędu m:

dla wszystkich i ≥ 1, gdzie c_0, …, cm−1 ∈ ℤ_2 są określonymi stałymi.

UWAGA. Mówi się, że rekurencja jest rzędu m, ponieważ każdy składnik zależy od poprzednich m składników. Jest to rekurencja liniowa, ponieważ zi+m jest funkcją liniową poprzednich składników. Zauważ, że możemy przyjąć c_0 = 1 bez utraty ogólności, ponieważ w przeciwnym razie rekurencja będzie miała stopień (najwyżej) m – 1.

■

Tutaj klucz K składa się z 2m wartości k_1, …, km, c_0, …, cm−1. Jeśli

(k_1, …, km) = (0, …, 0),

to strumień klucza składa się w zer. Oczywiście należy tego unikać, ponieważ szyfrogram będzie wtedy taki sam jak tekst jawny. Jeśli jednak stałe c_0, …, cm–1 zostaną wybrane w odpowiedni sposób, to inny wektor inicjalizacji (k_1, …, km) utworzy okresowy strumień klucza o okresie 2m – 1. Zatem „krótki” klucz może dać strumień klucza mający bardzo długi okres. Jest to z pewnością pożądana właściwość: w dalszej części rozdziału zobaczymy, jak szyfr Vigenère’a można poddawać kryptoanalizie, wykorzystując fakt, że strumień klucza ma krótki okres.

Oto przykład dla ilustracji.

Przykład 2.8. Załóżmy, że m = 4, a strumień klucza jest generowany przy użyciu rekurencji liniowej

i ≥ 1. Jeśli strumień klucza jest inicjowany za pomocą wektora innego niż (0, 0, 0, 0), to otrzymujemy strumień klucza o okresie 15. Na przykład, zaczynając od (1, 0, 0, 0), strumieniem klucza jest

1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 ⋯ .

Każdy inny niezerowy wektor inicjalizacji wytworzy permutację cykliczną tego samego strumienia klucza.

☐

Innym aspektem tej metody generowania strumienia klucza jest to, że strumień klucza może być wytwarzany efektywnie metodą sprzętową za pomocą rejestru przesuwającego z liniowym sprzężeniem zwrotnym (LFSR). Użyjemy wtedy rejestru przesuwającego z m rundami. Wektor (k_1, …, km) zostanie użyty do inicjacji rejestru przesuwającego. W każdej jednostce czasu będą wykonywane równolegle następujące działania:

1. k_1 będzie wybrany jako następny bit strumienia klucza.

2. k_2, …, km będą przesunięte o jeden w lewo.

3. „Nowa” wartość km będzie obliczona jako

(to jest „liniowe sprzężenie zwrotne”).

W danym momencie rejestr przesuwający zawiera m kolejnych elementów strumieni, powiedzmy zi, …, zi+m−1. Po jednostce czasu rejestr przesuwający zawiera zi+1, …, zi+m.

Zwróćmy uwagę, że liniowe sprzężenie zwrotne jest realizowane przez wybranie pewnych kroków rejestru (określonych przez stałe cj mające wartość „1”) i obliczenie sumy modulo 2 (która jest alternatywą wykluczającą). Jest to zilustrowane na rysunku 2.2, gdzie przedstawiono LFSR, który generuje strumień klucza z przykładu 2.8.

RYSUNEK 2.2. Rejestr przesuwający z liniowym sprzężeniem zwrotnym

Niesynchroniczny szyfr strumieniowy to szyfr strumieniowy, w którym każdy element strumienia klucza zi zależy od poprzedniego tekstu jawnego lub elementów szyfrogramu (x_1, …, xi−1 i/lub y_1, …, yi–1), także klucza K. Prosty typ niesynchronicznego szyfru strumieniowego, znany jako szyfr automatyczny, jest przedstawiony jako kryptosystem 2.7. Powodem użycia słowa „automatyczny” jest to, że tekst jawny jest użyty do utworzenia strumienia klucza (poza początkowym „znakiem klucza” K). Oczywiście klucz automatyczny nie jest bezpieczny, ponieważ jest tylko 26 możliwych takich kluczy.

Oto przykład, który to ilustruje:

Przykład 2.9. Przypuśćmy, że klucz jest równy K = 8, a jawnym tekstem jest

rendezvous.

Najpierw przekształcamy tekst jawny na ciąg liczb całkowitych:

17

4

13

3

4

25

21

14

20

18

Strumień klucza jest następujący:

8

17

4

13

3

4

25

21

14

20

KRYPTOSYSTEM 2.7. Szyfr automatyczny

Niech P = C = K =  = ℤ_26. Niech z_1 = K i zdefiniujmy zi = xi−1 dla każdego i ≥ 2. Dla 0 ≤ z ≤ 25 zdefiniujmy

ez(x) = (x + z) mod 26

oraz

dz(y) = (y − z) mod 26

(x, y ∈ ℤ_26).

Teraz dodajemy odpowiednie elementy, redukując je modulo 26:

25

21

17

16

7

3

20

9

8

12

Szyfrogramem w postaci alfabetycznej jest:

ZVRQHDUJIM.

Spójrzmy teraz, jak szyfrogram zostałby odszyfrowany. Najpierw przekształcamy ciąg alfabetyczny na ciąg liczbowy

25

21

17

16

7

3

20

9

8

12

Następnie obliczamy

Potem

i tak dalej. Za każdym razem, gdy otrzymujemy kolejny znak tekstu jawnego, używamy go również jako kolejnego elementu strumienia klucza.

☐

W następnym podrozdziale omawiamy metody, które mogą być użyte do kryptoanalizy różnych prezentowanych przez nas kryptosystemów.

2.2. Kryptoanaliza

W tej części omawiamy kilka technik kryptoanalizy. Ogólnym założeniem, które zwykle się przyjmuje, jest to, że przeciwnik, Oskar, zna używany kryptosystem. Zwykle określa się to mianem zasady Kerckhoffa. Oczywiście, jeśli Oskar nie zna używanego kryptosystemu, będzie to utrudniać jego zadanie. Nie chcemy jednak opierać bezpieczeństwa kryptosystemu na (być może chwiejnej) przesłance, że Oskar nie wie, jaki system jest wykorzystywany. Dlatego też naszym celem przy projektowaniu kryptosystemu będzie uzyskanie bezpieczeństwa przy założeniu, że zasada Kerckhoffa obowiązuje.

Po pierwsze, chcemy rozróżnić różne modele ataku na kryptosystemy. Model ataku określa informacje dostępne przeciwnikowi w momencie przeprowadzania ataku. Najczęstsze typy modeli ataków są wymienione poniżej.

Atak z samym szyfrogramem

Przeciwnik dysponuje ciągiem szyfrogramu y.

Atak ze znanym tekstem jawnym

Przeciwnik dysponuje ciągiem tekstu jawnego x oraz odpowiadającym mu szyfrogramem y.

Atak z wybranym tekstem jawnym

Przeciwnik uzyskał tymczasowy dostęp do maszyny szyfrującej. Może więc wybrać ciąg tekstu x i skonstruować odpowiadający mu ciąg szyfrogramu y.

Atak z wybranym szyfrogramem

Przeciwnik uzyskał tymczasowy dostęp do maszyny odszyfrowującej. Może więc wybrać ciąg szyfrogramu y i skonstruować odpowiadający mu ciąg tekstu jawnego x.

W każdym przypadku celem przeciwnika jest znalezienie użytego klucza. Pozwoliłoby to przeciwnikowi na odszyfrowanie określonego „docelowego” szyfrogramu, a następnie na odszyfrowanie wszelkich dodatkowych szyfrogramów zaszyfrowanych przy użyciu tego samego klucza.

Na pierwszy rzut oka atak z wybranym szyfrogramem może wydawać się nieco sztuczny. Jeśli bowiem istnieje tylko jeden szyfrogram interesujący przeciwnika, to przeciwnik może oczywiście go odszyfrować, jeśli wybrany model ataku jest dozwolony. Sugerujemy jednak, że celem przeciwnika jest zazwyczaj określenie klucza, który jest używany przez Alicję i Boba, tak aby inne szyfrogramy mogły zostać odszyfrowane (być może w późniejszym czasie). Atak z wybranym szyfrogramem ma w tym kontekście sens.

W pierwszej kolejności rozważamy najsłabszy rodzaj ataku, czyli atak z samym szyfrogramem (czasami nazywany jest to atakiem ze znanym szyfrogramem). Zakładamy również, że ciąg tekstu jawnego to zwykły tekst angielski, bez interpunkcji i „spacji”. (To sprawia, że kryptoanaliza jest trudniejsza niż w przypadku szyfrowania interpunkcji i spacji).

Wiele technik kryptoanalizy wykorzystuje właściwości statystyczne języka angielskiego. Różne osoby oszacowały względną częstość występowania 26 liter, zestawiając statystyki z licznych powieści, czasopism i gazet. Szacunki z tabeli 2.1 zostały pozyskane przez Bekera i Pipera. Na podstawie tych prawdopodobieństw Beker i Piper podzielili 26 liter na pięć grup w następujący sposób:

1. E z prawdopodobieństwem około 0,120,

2. T, A, O, I, N, S, H, R, każde z prawdopodobieństwem między 0,06 a 0,09,

3. D, L, każde z prawdopodobieństwem około 0,04,

4. C, U, M, W, F, G, Y, P, B, każde z prawdopodobieństwem między 0,015 a 0,028,

5. V, K, J, X, Q, Z, każde z prawdopodobieństwem mniejszym niż 0,01.

TABELA 2.1. Prawdopodobieństwo wystąpienia 26 liter

Przydatne jest również rozważenie ciągów dwóch lub trzech kolejnych liter, zwanych odpowiednio digramami i trigramami. Oto 30 najczęściej spotykanych digramów (w kolejności malejącej):

TH, HE, IN, ER, AN, RE, ED, ON, ES, ST,

EN, AT, TO, NT, HA, ND, OU, EA, NG, AS,

OR, TI, IS, ET, IT, AR, TE, SE, HI, OF.

Dwanaście najczęstszych trigramów to:

THE, ING, AND, HER, ERE, ENT,

THA, NTH, WAS, ETH, FOR, DTH.

2.2.1. Kryptoanaliza szyfru afinicznego

Jako prostą ilustrację tego, jak można przeprowadzić kryptoanalizę z wykorzystaniem danych statystycznych, spójrzmy najpierw na szyfr afiniczny. Załóżmy, że Oskar przechwycił szyfrogram przedstawiony w poniższym przykładzie:

TABELA 2.2. Częstość występowania 26 liter szyfrogramu

Przykład 2.10. Szyfrogram otrzymany z szyfru afinicznego

FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK

APRKDLYEVLRHHRH

Analizę częstości podano w tabeli 2.2.

Jest tylko 57 znaków szyfrogramu, lecz jest to zwykle wystarczające, aby dokonać kryptoanalizy szyfru afinicznego. Najczęstszymi znakami szyfrogramu są: R (8 wystąpień), D (7 wystąpień), E, H, K (5 wystąpień każde) oraz F, S, V (4 wystąpienia każde). Jako pierwszą można postawić hipotezę, że R jest szyfrem e, a D jest szyfrem t, ponieważ e i t są (odpowiednio) dwiema najczęstszymi literami. Wyrażone liczbowo mają postać eK(4) = 17 i eK(19) = 3. Przypomnijmy, że eK(x) = ax + b, gdzie a i b są niewiadomymi. Otrzymujemy więc dwa równania liniowe z dwiema niewiadomymi:

Ten układ ma jedno rozwiązanie a = 6, b = 19 (w ℤ_26). Ale ten klucz jest niedopuszczalny, gdyż NWD(a, 26) = 2 > 1. Więc nasza hipoteza musi być błędna.

Nasza następna próba może być taka, że R jest szyfrem e, a E jest szyfrem t. Postępując tak jak powyżej, otrzymujemy a = 13, co znów jest niedopuszczalne. Więc próbujemy kolejnego a = 8, znów niemożliwe. Kontynuując, przypuszczamy, że R jest szyfrem e, a K jest szyfrem t. To daje a = 3, b = 5, co jest przynajmniej potencjalnie poprawnym kluczem. Pozostaje do obliczenia funkcja odszyfrowywania odpowiadająca K = (3, 5), a następnie odszyfrowanie szyfrogramu, aby sprawdzić, czy otrzymamy ciąg znaków w języku angielskim, czy też nonsens. To potwierdzi ważność (3, 5).

TABELA 2.3. Częstość występowania 26 liter szyfrogramu

Jeśli wykonamy te działania, otrzymamy dK(y) = 9y – 19 i dany szyfrogram odszyfruje się, aby dać:

algorithmsarequitegeneraldefinitionsofarit

hmeticprocesses

Stwierdzamy, że ustaliliśmy właściwy klucz.

☐

2.2.2. Kryptoanaliza szyfru podstawieniowego

Tutaj patrzymy na bardziej skomplikowaną sytuację, szyfr podstawieniowy. Rozważmy szyfrogram w poniższym przykładzie.

Przykład 2.11. Szyfrogram otrzymany z szyfru podstawieniowego

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Analiza częstotliwości występowania dla tego szyfru została przedstawiona w tabeli 2.3.

Ponieważ Z występuje znacznie częściej niż jakikolwiek inny znak szyfrogramu, możemy przypuszczać, że dK(Z) = e. Pozostałe znaki szyfrogramu, które występują co najmniej dziesięć razy (każdy) to C, D, F, J, M, R, Y. Możemy się spodziewać, że litery te są szyfrogramami (podzbioru) t, a, o, i, n, s, h, r, ale częstotliwości naprawdę nie różnią się na tyle, aby powiedzieć nam, jaka może być kolejność.

Na tym etapie możemy przyjrzeć się digramom, zwłaszcza tym w postaci –Z lub Z–, ponieważ przypuszczamy, że Z odszyfrowuje się na e. Najczęściej spotykane digramy tego typu to DZ i ZW (cztery razy każdy); NZ i ZU (trzy razy każdy); oraz RZ, HZ, XZ, FZ, ZR, ZV, ZC, ZD i ZJ (dwa razy każdy). Ponieważ ZW występuje cztery razy, a WZ w ogóle, a W występuje rzadziej niż wiele innych znaków, moglibyśmy przypuszczać, że dK(W) = d. Ponieważ DZ występuje cztery razy, a ZD dwa razy, moglibyśmy przypuszczać, że dK(D) ∈ {r, s, t}, ale nie jest jasne, która z tych trzech możliwości jest właściwa.

Jeśli przyjmiemy założenie, że dK(Z) = e i dK(W) = d, możemy wrócić do szyfrogramu i zauważyć, że mamy ZRW występujące w pobliżu początku szyfrogramu, a RW pojawia się ponownie później. Ponieważ R pojawia się często w szyfrogramie, a nd jest częstym digramem, możemy wypróbować dK(R) = n jako najbardziej prawdopodobną możliwość.

W tym momencie mamy następującą sytuację:

------end---------e----ned---e------------

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

--------e----e---------n--d---en----e----e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

-e---n------n------ed---e---e--ne-nd-e-e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

-ed-----n-----------e----ed-------d---e--n

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Naszym następnym krokiem może być wypróbowanie dK(N) = h, ponieważ NZ jest częstym digramem, a ZN nie. Jeżeli jest to poprawne, to segment tekstu jawnego ne – ndhe sugeruje, że dK(C) = a. Biorąc pod uwagę te domysły, mamy:

------end-----a---e-a--nedh--e------a-----

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

h-------ea---e-a---a---nhad-a-en--a-e-h--e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

he-a-n------n------ed---e---e--neandhe-e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

-ed-a---nh---ha---a-e----ed-----a-d--he--n

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Teraz możemy wziąć pod uwagę M, drugi co do częstości występowania znak szyfrogramu. Segment szyfrogramu RNM, który naszym zdaniem odszyfrowuje się na nh–, sugeruje, że dla h– rozpoczyna się słowo, więc M prawdopodobnie reprezentuje samogłoskę. Ponieważ zajmowaliśmy się już a i e, więc oczekujemy, że dK(M) = i lub o. Ponieważ ai jest dużo bardziej prawdopodobnym digramem niż ao, digram szyfrogramu CM sugeruje, że najpierw spróbujemy dK(M) = i. Wówczas mamy:

-----iend-----a-i-e-a-inedhi-e------a---i-

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

h-----i-ea-i-e-a---a-i-nhad-a-en--a-e-hi-e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

he-a-n-----in-i----ed---e---e-ineandhe-e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

-ed-a--inhi--hai--a-e-i--ed-----a-d--he--n

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Następnie moglibyśmy spróbować określić, która litera jest szyfrogramem o. Ponieważ o jest częstym znakiem w tekście jawnym, przypuszczamy, że odpowiadający mu znak szyfrujący jest jednym z D, F, J, Y. Y wydaje się być najbardziej prawdopodobną możliwością; w przeciwnym razie otrzymalibyśmy długie ciągi samogłosek, aoi z CFM lub CJM. Załóżmy więc, że dK(Y) = o.

Trzy najczęstsze pozostałe litery szyfrogramu to D, F, J, które, jak przypuszczamy, mogą być odszyfrowane na r, s, t w jakiejś kolejności. Dwa wystąpienia trigramu NMD przekonują, że dK(D) = s, dając trigram his w tekście jawnym (jest to zgodne z naszą wcześniejszą hipotezą, że dK(D)∈ {r, s, t}). Segment HNCMF mógłby być szyfrem słowa chair, co dawałoby dK(F) = r (i dK(H) = c), więc mielibyśmy dK(J) = t przez proces eliminacji. Teraz mamy:

o-r-riend-ro--arise-a-inedhise--t---ass-it

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

hs-r-riseasi-e-a-orationhadta-en--ace-hi-e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

he-asnt-oo-in-i-o-redso-e-ore-ineandhesett

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

-ed-ac-inhischair-aceti-ted--to-ardsthes-n

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Teraz bardzo łatwo jest ustalić tekst jawny i klucz dla przykładu 2.11. Pełne odszyfrowanie jest następujące:

Our friend from Paris examined his empty glass with surprise, as if evaporation had taken place while he wasn’t looking. I poured some more wine and he settled back in his chair, face tilted up towards the sun[4].

☐

2.2.3. Kryptoanaliza szyfru Vigenère’a

W tej części opisujemy kilka metod kryptoanalizy szyfru Vigenère’a. Pierwszym krokiem jest określenie długości słowa kluczowego (klucza), które oznaczamy przez m. Można zastosować jedną z kilku technik. Pierwszą z nich jest tzw. test Kasiskiego, a druga wykorzystuje indeks koincydencji.

Test Kasiskiego został opisany przez Fryderyka Kasiskiego w 1863 roku, jednak podobno wcześniej, około 1854 roku, odkrył go Charles Babbage. Opiera się on na obserwacji, że dwa identyczne segmenty tekstu jawnego będą zaszyfrowane tak samo, gdy ich występowanie w tekście jawnym będzie oddalone od siebie o δ pozycji, gdzie δ ≡ 0 (mod m). I odwrotnie, jeżeli obserwujemy dwa identyczne segmenty tekstu zaszyfrowanego, z których każdy ma długość co najmniej trzy, to istnieje duże prawdopodobieństwo, że odpowiadają one identycznym segmentom tekstu jawnego.

Test Kasiskiego działa w następujący sposób. Przeszukujemy szyfrogram w poszukiwaniu par identycznych odcinków o długości co najmniej trzech znaków i zapisujemy odległość między pozycjami wyjściowymi dwóch segmentów. Jeśli otrzymamy kilka takich odległości, powiedzmy δ_1, δ_2, …, to przypuszczamy, że m dzieli wszystkie δi, a więc m dzieli największy wspólny dzielnik δi.

Dalsze wskazówki dotyczące wartości m można uzyskać za pomocą indeksu koincydencji. Pojęcie to zostało zdefiniowane przez Williama Friedmana w 1920 roku w następujący sposób.

DEFINICJA 2.7. Załóżmy, że x = x_1x_2 ⋯ xn jest ciągiem n znaków alfabetu. Indeks koincydencji x, oznaczony jako Ic(x), jest zdefiniowany jako prawdopodobieństwo, że dwa losowe elementy x są identyczne.

Załóżmy, że oznaczymy częstotliwości A, B, C, …, Z w x przez f_0, f_1, . . ., f_25 (odpowiednio). Możemy wybrać dwa elementy x na sposoby[5]. Dla każdego i, 0 ≤ i ≤ 25, istnieją + sposoby wyboru obu elementów, które mają być i. Stąd mamy wzór

Załóżmy, że x jest ciągiem tekstowym w języku angielskim. Oznaczmy oczekiwane prawdopodobieństwa wystąpienia liter A, B, …, Z z tabeli 2.1 odpowiednio przez p_0, …, p_25. Wówczas możemy się spodziewać, że

ponieważ prawdopodobieństwo, że oba elementy losowe to A wynosi p_0^2, a prawdopodobieństwo, że oba to B wynosi p_1^2 itd. To samo rozumowanie ma zastosowanie, jeżeli x jest ciągiem szyfrogramu otrzymanym przy użyciu dowolnego szyfru monoalfabetycznego. W tym przypadku poszczególne prawdopodobieństwa będą podlegać permutacji, ale wielkość ∑ pi^2 pozostanie niezmieniona.

Załóżmy teraz, że zaczynamy od ciągu szyfrogramu y = y_1y_2 yn, który został zbudowany przy użyciu szyfru Vigenère’a. Zdefiniujmy m podciągów y, oznaczonych y_1, y_2, …, ym przez przepisanie szyfrogramu w kolumnach w prostokątnej macierzy o wymiarach m × (n/m). Wiersze tej macierzy są podciągami yi, 1 ≤ i ≤ m. Innymi słowy, mamy

Jeśli y_1, y_2, …, ym są skonstruowane w ten sposób, a m jest faktycznie długością słowa kluczowego, to każda wartość Ic(yi) powinna być w przybliżeniu równa 0,065. Z drugiej strony, jeśli m nie jest długością słowa kluczowego, to podciągi yi będą wyglądały o wiele bardziej losowo, ponieważ zostaną uzyskane przez szyfrowanie przesuwające z różnymi kluczami. Zauważmy, że całkowicie losowy ciąg znaków będzie miał

Dwie wartości 0,065 i 0,038 są na tyle odległe od siebie, że często będziemy w stanie tą metodą określić prawidłową długość słowa kluczowego (lub potwierdzić odgadniecie, które zostało już dokonane za pomocą testu Kasiskiego).

Zilustrujmy te dwie techniki na przykładzie.

Przykład 2.12. Szyfrogram uzyskany z szyfru Vigenère’a

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW

RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK

LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX

VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR

ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT

AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI

PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP

WQAIIWXNRMGWOIIFKEE

Przypisy

[1] Kolizja dla funkcji h zachodzi wtedy, gdy h(x) = h(y) dla jakiegoś x ≠ y.

[2] Inną kwestią jest oczywiście to, czy tego rodzaju ograniczone informacje mogą być wykorzystane przez przeciwnika w złośliwy sposób, czy też nie.

[3] Inna nazwa tej funkcji to tocjent (przyp. tłum.).

[4] P. Mayle, A Year in Provence, A. Knopf, Inc., 1989 (Rok w Prowansji, Prószyński, Warszawa 2010).

[5] Symbol Newtona  = n!/(k!(n – k)!) wyznacza liczbę sposobów wybrania podzbioru k obiektów ze zbioru n obiektów.