Rozdział 1Wprowadzenie 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ł 2Klasyczna 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 = x1x2 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 = y1 y2 yn
jest przesyłany przez kanał. Gdy Bob otrzymuje y1 y2 yn, odszyfrowuje go przy użyciu funkcji odszyfrowania dK, uzyskując oryginalny ciąg tekstu jawnego, x1 x2 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(x1) = eK(x2),(2.1)
gdzie x1 ? x2, to Bob nie może wiedzieć, czy y trzeba rozszyfrować jako x1, czy jako x2. 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 = q1m + r1, a b = q2m + r2, gdzie 0 ? r1 ? m - 1 i 0 ? r2 ? m - 1. Wtedy nietrudno zauważyć, że a ? b (mod m) wtedy i tylko wtedy, gdy r1 = r2. Użyjemy zapisu a mod m (bez nawiasów), aby oznaczyć resztę z dzielenia a przez m (wartość r1 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 d0, d1 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 × 1026, 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 x1 i x2
ax1? ax2 (mod 26).
Wówczas
a(x1- x2) ? 0 (mod 26),
zatem
26 | a(x1- x2).
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(x1- x2) oraz NWD(a, 26) = 1, musi zatem zachodzić
26 | (x1- x2),
czyli x1? x2 (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 = 22 × 3 × 5 i 98 = 2 × 72).
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 = 22 × 31 × 51,
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 = (k1, k2, ..., 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 × 107. 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 = (x1, x2) oraz element szyfrogramu jako y = (y1, y2). Tutaj y1 będzie liniową kombinacją x1 i x2, podobnie jak y2. 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 = (x1, ..., xm) ? P i K ? K obliczamy y = eK(x) = (y1, ..., 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 = z1z2, i użycie go do szyfrowania strumienia tekstu jawnego x = x1x2 --- 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 z1z2 ? 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 z1z2 --- w następujący sposób:
gdzie K = (k1, ..., km). To generuje strumień klucza
z klucza K = (k1, k2, ..., 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 (k1, ..., 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 c0, ..., 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ąć c0 = 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 k1, ..., km, c0, ..., cm-1. Jeśli
(k1, ..., 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 c0, ..., cm-1 zostaną wybrane w odpowiedni sposób, to inny wektor inicjalizacji (k1, ..., 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 (k1, ..., 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. k1 będzie wybrany jako następny bit strumienia klucza.
2. k2, ..., 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 (x1, ..., xi-1 i/lub y1, ..., 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 z1 = 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 = x1x2 ? 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 f0, f1, . . ., f25 (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 p0, ..., p25. Wówczas możemy się spodziewać, że
ponieważ prawdopodobieństwo, że oba elementy losowe to A wynosi p02, a prawdopodobieństwo, że oba to B wynosi p12 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ść ? pi2 pozostanie niezmieniona.
Załóżmy teraz, że zaczynamy od ciągu szyfrogramu y = y1y2 yn, który został zbudowany przy użyciu szyfru Vigen?re'a. Zdefiniujmy m podciągów y, oznaczonych y1, y2, ..., 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 y1, y2, ..., 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
