Delta
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Delta > Matematyka - spis artykułów >  SZYFRY KLASYCZNE  
  Jesteś tutaj
Wybór artykułów z miesięcznika "Delta"
"Delta" to miesięcznik popularyzujący matematykę, fizykę i astronomię na bardzo wysokim poziomie, wydawany od 1974 roku.
Wirtualny Wszechświat prezentuje wybór tekstów publikowanych w "Delcie" od pierwszego numeru po początek XXI wieku.
  Szukacz
Delta 01/1997
Wojciech GUZICKI
SZYFRY KLASYCZNE

W tym artykule zajmiemy się najprostszymi sposobami szyfrowania, znanymi od wielu stuleci i nie mającymi już większego znaczenia praktycznego. Zostaną one pokazane po to, by wyjaśnić, co nazywamy "klasycznym systemem kryptograficznym". W kolejnym artykule ("Delta" nr 3/1997) opiszemy znacznie nowsze i lepsze sposoby szyfrowania, tzw. szyfry z publicznym kluczem.

Jeden z najstarszych sposobów szyfrowania pochodzi od Juliusza Cezara, który szyfrował swoją korespondencję z Cyceronem. Sposób ten polegał na tym, że zamiast każdej litery pisało się literę występującą w alfabecie trzy miejsca dalej. Tak więc, jeśli użyjemy dzisiejszego alfabetu łacińskiego

ABCDEFGHIJKLMNOPQRSTUVWXYZ,

to zamiast A będziemy pisać D, zamiast K piszemy N, zamiast Y piszemy B. Widzimy więc, że alfabet traktujemy "cyklicznie", tzn. po ostatniej literze Z następuje znów pierwsza A itd.

Słynne słowa Cezara ALEA IACTA EST zaszyfrowalibyśmy więc jako DOHD LDFWD HVW. Na tym przykładzie objaśnimy dwa ważne pojęcia kryptografii (czyli nauki o szyfrowaniu): systemu kryptograficznego i klucza. System kryptograficzny to, mówiąc nieprecyzyjnie, ogólny sposób szyfrowania. W naszym przykładzie polega on na tym, że zamiast danej litery alfabetu piszemy literę występującą w tym samym alfabecie ileś miejsc dalej. Cezar zdecydował się akurat na trzy miejsca dalej, ale równie dobrze mógłby pisać literę występującą siedem miejsc dalej. Sposób szyfrowania (tzn. system kryptograficzny) byłby w zasadzie ten sam, różniłby się tylko wyborem klucza, czyli liczby wskazującej, o ile miejsc dalej w alfabecie stoi litera, którą mam napisać. Można powiedzieć, że system kryptograficzny polega tu na pisaniu litery stojącej k miejsc dalej, a liczba k jest kluczem. Podsumujmy: szyfrowanie polega na wyborze ogólnego sposobu, algorytmu szyfrowania, zwanego systemem kryptograficznym i pewnych parametrów, od których ten algorytm jest zależny, nazywanych kluczem szyfrowania.

Każdą zaszyfrowaną wiadomość trzeba kiedyś rozszyfrować. W szyfrze Cezara znajdujemy literę stojącą w alfabecie trzy miejsca bliżej, czyli w istocie stosujemy ten sam algorytm szyfrowania z innym kluczem. Do szyfrowania używamy klucza +3, a do rozszyfrowywania klucza -3. Gdy znamy klucz szyfrowania, to znamy też klucz rozszyfrowywania. Tak naprawdę jest to ten sam klucz, jeśli pominiemy jego znak.

Szyfr Cezara bardzo łatwo jest opisać w sposób matematyczny. Kolejnym literom alfabetu łacińskiego przyporządkujemy liczby od 0 do 25. Przyjmijmy oznaczenie: a mod b oznacza (zawsze nieujemną!) resztę z dzielenia liczby całkowitej a przez dodatnią liczbę całkowitą b. System kryptograficzny Cezara może teraz być zdefiniowany wzorem

C = (P + k) mod 26,

gdzie k jest kluczem szyfrowania, P jest numerem litery, którą szyfrujemy, a C jest numerem litery po zaszyfrowaniu. Rozszyfrowywanie odbywa się według wzoru

P = (C - k) mod 26.

Jeśli ktoś zadaje sobie tyle trudu, by szyfrować wiadomości wysyłane do kogoś innego, to pewnie dlatego, że nie chce, by inne, niepowołane do tego osoby, mogły te wiadomości odczytać. I pewnie znajdą się te inne osoby, które chcą koniecznie przeczytać to, co zostało zaszyfrowane. Jeśli nie znają one sposobu szyfrowania, to muszą ten szyfr "złamać". W jaki sposób można tego dokonać?

Po pierwsze, będziemy zakładać, że osoba łamiąca szyfr zna system kryptograficzny i nie zna tylko klucza. Dlaczego przyjmujemy takie założenie? Wśród wielu powodów można wymienić ten, że system kryptograficzny na ogół trudniej zmienić niż klucz. Używa się więc tego samego systemu na tyle długo, że osoby niepowołane mogą wykraść informacje o samym systemie. Bezpieczeństwo szyfrowania będzie zapewnione dzięki częstym zmianom kluczy. Innym powodem jest ten, że często tego samego systemu używa bardzo wiele osób i sam system jest dobrze wszystkim znany.

A jak w takim razie zdobyć klucz, jeśli dysponuje się tylko tekstem zaszyfrowanym? Czasami nie jest to trudne. Np. szyfr Cezara można złamać bardzo łatwo. Przecież ma on tylko 26 kluczy. Wystarczy spróbować wszystkich, by przekonać się, że tylko jedna wiadomość brzmi sensownie, a pozostałe stanowią niezrozumiały bełkot. Klucz użyty w tym rozszyfrowywaniu jest właściwym kluczem. Widzimy więc, że system kryptograficzny dopuszczający niewiele kluczy nie jest bezpieczny i łatwo taki szyfr złamać. Kiedyś myślano, że bezpieczeństwo szyfru zależy po prostu od liczby kluczy. Girolamo Cardano, wybitny uczony XVI wieku, pisał, że niemożliwy do złamania jest nieco inny szyfr, polegający na tym, że zamiast każdej litery alfabetu piszemy ustaloną inną literę. Wyjaśni to najlepiej przykład. Przyjmijmy, że zamiast litery A piszemy Q, zamiast B piszemy W itd. według następującego schematu:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

QWERTYUIOPASDFGHJKLZXCVBNM

(zamiast litery stojącej w górnym wierszu piszemy literę znajdująca się pod nią w dolnym wierszu). Zdanie ALEA IACTA EST zostanie teraz zaszyfrowane jako QSTQ OQEZQ TLZ. System kryptograficzny polega tu na zastępowaniu każdej litery inną, a kluczem jest stojąca w dolnym wierszu permutacja liter alfabetu. Kluczem rozszyfrowywania jest oczywiście permutacja odwrotna, którą nietrudno wypisać:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

KXVMCNOPHQRSZYIJADLEGWBUFT

Liczba kluczy jest ogromna. Jest ich 26! - czyli 403291461126605635584000000. Oczywiście, przeszukanie wszystkich możliwych kluczy nie jest wykonalne, trwałoby zbyt długo. Jak więc można złamać ten szyfr? Sięgamy do metod statystycznych. Okazuje się, że w tekstach napisanych w danym języku poszczególne litery nie występują z tą samą częstotliwością. I tak, na przykład, w języku angielskim najczęściej występuje litera E (około 13% wszystkich liter odpowiednio długiego tekstu). Drugą z kolei jest litera T (około 9%), następnymi są A, O, N, I, R. W języku polskim nie ma litery bardzo wyróżniającej się od innych i dlatego łamanie zaszyfrowanego tekstu napisanego po polsku będzie nieco trudniejsze. Najczęściej występują litery A oraz I (po około 9%), a po nich E i O (po około 7,5%).

Taki sposób łamania szyfru opisał w opowiadaniu "Tańczące sylwetki" Artur Conan Doyle. Czytelnik-koneser może sprawdzić, czy Sherlock Holmes korzystał z odpowiednich rozkładów częstości.

Przypuśćmy teraz, że mamy dany tekst zaszyfrowany za pomocą opisanego wyżej systemu. Musimy, oczywiście, wiedzieć, w jakim języku napisano zaszyfrowaną wiadomość i znać rozkład częstości występowania liter alfabetu w tekstach napisanych w tym języku. Jeśli nasz tekst jest wystarczająco długi (wystarczy już kilkaset liter), to rozkład częstości jego liter powinien być podobny. Najczęściej występujące litery w tekście zaszyfrowanym powinny odpowiadać najczęstszym literom danego języka (choć niekoniecznie w tej samej kolejności). Próbujemy przypisać te litery sobie; po kilku próbach okaże się, że dość łatwo możemy domyślić się znaczenia następnych liter, potem jeszcze następnych, aż wreszcie domyślamy się znaczenia wszystkich liter klucza i odczytujemy cały tekst. Duża liczba kluczy nie jest więc warunkiem wystarczającym bezpieczeństwa szyfru.

Przyjrzymy się jeszcze jednemu systemowi kryptograficznemu. Od poprzedniego systemu będzie się on różnić tym, że ta sama litera może być zaszyfrowana w różny sposób, w zależności od tego, w którym miejscu tekstu występuje. Weźmy ciąg kilku liczb mniejszych od 26, na przykład (3, 7, 1, 11, 2). Sposób szyfrowania polega teraz na tym, że zamiast pierwszej litery tekstu piszemy literę znajdującą się w alfabecie 3 miejsca dalej, zamiast drugiej litery tekstu piszemy literę znajdującą się w alfabecie 7 miejsc dalej, zamiast trzeciej literę znajdującą się 1 miejsce dalej, potem literę znajdującą się 11 miejsc dalej, potem 2 miejsca i zaczynamy od początku: 3 miejsca, 7 miejsc, 1 miejsce itd. A więc zdanie ALEA IACTA EST po zaszyfrowaniu będzie brzmiało DSFL KDJUL GVA. Zauważmy, że litery A w pierwszym słowie zostały zaszyfrowane inaczej. Natomiast pierwsza litera A i druga w drugim słowie zostały zaszyfrowane tak samo - dlatego, że druga z nich występuje w tekście pięć miejsc dalej i klucz ma pięć liczb. Ten system kryptograficzny, nazywany szyfrem Vigenre'a, jest więc jakby kombinacją wielu systemów Cezara, a kluczem szyfrowania jest odpowiedni ciąg liczb. Klucze, oczywiście, mogą być dowolnej długości. Często zapamiętujemy klucz w postaci słowa. Na przykład słowo CEZAR odpowiada ciągowi (3, 5, 26, 1, 18): litera C jest trzecią literą alfabetu, litera E piątą itd. Liczba kluczy w tym systemie jest naprawdę olbrzymia. Kluczy długości 26, a więc takiej długości jak permutacje w poprzednim systemie, jest 2626; ta liczba jest znacznie większa niż 26! A jednak ten szyfr też można łatwo złamać.

Łamanie polega na tym, by najpierw odgadnąć długość klucza. Następnie łatwo już odgadnąć liczbę stojącą w kluczu na każdym miejscu. Na przykład, odgadliśmy, że klucz ma długość 5. Zliczamy litery stojące na co piątym miejscu: na pierwszym, szóstym, jedenastym itd. Rozkład częstości tych liter powinien być przesuniętym o kilka miejsc rozkładem częstości występowania liter danego alfabetu. Te dwa rozkłady można bardzo łatwo do siebie "dopasować" i w ten sposób odnajdujemy liczbę stojącą w kluczu na pierwszym miejscu. Potem tak samo odnajdujemy liczbę stojącą na drugim miejscu, na trzecim itd.

A jak odgadnąć długość klucza? Można po prostu próbować po kolei: najpierw przypuścić, że klucz ma długość 2 i spróbować dopasować odpowiednie rozkłady. Jeśli się nie uda, to próbujemy długości 3, potem 4 i tak dalej, dotąd, aż znajdziemy właściwą długość. Istnieją zresztą metody statystyczne, dzięki którym można tę długość wyznaczyć z dość dobrym przybliżeniem. Tak więc ten system kryptograficzny też nie jest bezpieczny.

Przyjrzyjmy się sposobom łamania tych dwóch szyfrów. W obu przypadkach próbowaliśmy znaleźć klucz szyfrowania. Wydaje się, że ten sposób postępowania jest najbardziej naturalny. Jeśli znajdziemy klucz szyfrowania, to łatwo odzyskamy z niego klucz rozszyfrowywania i odczytamy zaszyfrowaną wiadomość. Ale czy jest to jedyny sposób łamania szyfru? Czy odczytanie zaszyfrowanej wiadomości musi być równoważne znalezieniu klucza? Dla tych dwóch systemów kryptograficznych jest to równoważne. Przypuśćmy bowiem, że otrzymaliśmy jednocześnie tekst jawny (tzn. tekst oryginalny, przed zaszyfrowaniem) i tekst zaszyfrowany. Bez trudu w obu przypadkach wyznaczymy klucz, a właściwie oba klucze: szyfrowania i rozszyfrowywania. Wystarczy przyjrzeć się, jakie litery w tekście zaszyfrowanym odpowiadają kolejnym literom tekstu jawnego. Czy jednak tak będzie dla wszystkich innych systemów kryptograficznych? Spróbujmy sformułować wyraźnie pytania, które się narzucają.

Po pierwsze, jeśli poznamy klucz szyfrowania, to czy łatwo możemy odtworzyć z niego klucz rozszyfrowywania? We wszystkich powyższych przykładach było to oczywiste, ale nie zawsze musi tak być. Po drugie, jeśli mamy jednocześnie tekst jawny i tekst zaszyfrowany, to czy umiemy odtworzyć klucz szyfrowania (lub rozszyfrowywania)? Znów okaże się, że nie zawsze będziemy umieli to zrobić.

Klasyczne systemy kryptograficzne to właśnie takie systemy, których złamanie polega w istocie na znalezieniu klucza szyfrowania i tym samym klucza rozszyfrowywania. W następnym artykule poznamy tzw. szyfry z publicznym kluczem. Polegają one na tym, że klucz szyfrowania może być powszechnie znany i każdy będzie mógł go użyć do zaszyfrowania dowolnej wiadomości. Klucz rozszyfrowywania będzie jednak tajny i tylko jego "właściciel" będzie mógł z niego skorzystać. W tych systemach kryptograficznych znajomość klucza szyfrowania nie wystarczy do rozszyfrowania tekstu zaszyfrowanego. Potrzebna jest jeszcze pewna dodatkowa informacja, której nie udostępnia się publicznie i której w praktyce nie można uzyskać, jeśli zna się tylko klucz szyfrowania. Do skonstruowania takich szyfrów wykorzystano subtelne metody teorii liczb, algebry, geometrii algebraicznej i kombinatoryki.




[góra strony]
Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach