Rozważamy zagadnienie kryptograficzne polegające na przesłaniu wiadomości, od nadawcy do obiorcy, w taki sposób, by żadna trzecia (przypadkowa) osoba nie była w stanie jej odczytać.
Tekst jawny to ciąg symboli (znaków) w pewnym języku (np. w polskim). Wiadomość zakodowana, czyli szyfrogram, to także ciąg symboli. Podczas naszych rozważań zakładamy, iż szyfrogram jest ciągiem nad tym samym alfabetem co tekst jawny. Przed zakodowaniem nadawca dzieli tekst jawny na tzw. jednostki. Jednostką tekstu jawnego może być pojedynczy symbol, dwójka symboli, itp.. Dopiero jednostkę tekstu jawnego poddaje się procesowi kodowania otrzymując jednostkę szyfrogramu. Kolejne jednostki szyfrogramu mogą być niezależnie wysyłane od nadawcy do odbiorcy. Odbiorca poddaje otrzymany szyfrogram procesowi dekodowania dostając jednostkę tekstu jawnego.
Funkcja kodująca \( f \) to permutacja
\( f:\mathcal{J}\longrightarrow\mathcal{J}, \)
gdzie \( \mathcal{J} \) to zbiór wszystkich, możliwych jednostek tekstu jawnego i szyfrogramu (w skrócie jednostki wiadomości).
Funkcja dekodująca jest permutacją odwrotną do funkcji kodującej. Oznaczamy ją przez \( f^{-1} \), gdzie \( f \) jest odpowiednią funkcją kodującą.
Funkcja kodująca/dekodująca zależy zazwyczaj od parametrów, zwanych kluczami. Przyjmuje się, iż funkcja kodująca (jej wzór, bądź algorytm ją realizujący) jest ogólnie dostępna. Zachowane w tajemnicy są jedynie klucze.
Kryptosystem to para \( (\mathcal{J},f) \), czyli zbiór jednostek wiadomości \( \mathcal{J} \) i funkcja kodująca \( f \).
Pierwszym krokiem do określenia kryptosystemu jest poetykietowanie jednostek wiadomości pewnymi obiektami matematycznymi, na których będzie można określić funkcję kodującą (permutację). W naszych rozważaniach zawsze będą to kolejne liczby naturalne, jednak w ogólności rozważa się w tym miejscu także wektory bądź np. krzywe eliptyczne czy obecnie nawet już hipereliptyczne.
Przykład
Rozważmy alfabet jako zbiór cyfr, polskich liter oraz dodatkowych kilku znaków interpunkcyjnych.
Poetykietujmy symbole alfabetu kolejnymi liczbami naturalnymi.
\( \begin{array} {rrrrrrrrrrrrrrrr} A & Ą & B & C & Ć & D & E & Ę & F & G & H & I & J & K & L & Ł \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline M & N & Ń & O & Ó & P & R & S & Ś & T & U & W & Y & Z & Ż & Ź \\ 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ \hline & . & ? & ! & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \end{array} \)
Niech jednostki wiadomości zawierają tylko jeden symbol. Wtedy zbiór jednostek wiadomości to \( \mathbb{Z}_{46}={\{ {0,\ldots,45} \} } \). Podzielmy tekst 'MATEMATYKA DYSKRETNA 2' na jednostki wiadomości. Na podstawie tabeli powyżej kolejne jednostki to:
\( 16,0,25,6,16,0,25,28,13,0,32,5,28,23,13,22,6,25,17,0,32,38. \)
Rozważmy teraz jednostki wiadomości zawierające dwie litery. Wtedy łatwo policzyć, że mamy \( 46\cdot46=2116 \) możliwych jednostek. Ponumerujmy je w sposób naturalny: jednostka \( xy \) otrzymuje numer
\( 46x+y\in{\{ {0,\ldots,2115} \} }. \)
Zatem zbiór jednostek wiadomości to \( \mathbb{Z}_{2116}={\{ {0,\ldots,2115} \} } \). Jak teraz wyglądają jednostki wiadomości 'MATEMATYKA DYSKRETNA 2'?
\( \begin{align*} \textrm{MA} & \equiv & 16\cdot46+0=736, \\ \textrm{TE} & \equiv & 25\cdot46+6=1156, \\ & \ldots & \end{align*} \)
To przykład bardzo prostego systemu kryptograficznego. Są poszlaki świadczące o tym, że Juliusz Cezar używał tej metody do porozumiewania się ze swoimi generałami.
Funkcja kodująca jest tu oparta na dodawaniu modulo rozmiar \( \vert\mathcal{J}\vert \) zbioru jednostek wiadomości:
\( f(P)=(P+b) {\sf mod} \vert \mathcal{J}\vert . \)
Parametr \( b\in{\{ {0,\ldots,\vert\mathcal{J}\vert-1} \} } \) (choć wartość \( 0 \) jest niepraktyczna :)) jest kluczem, który powinien pozostać tajny. Odbiorca otrzymując szyfrogram \( C \) dekoduje go następująco:
\( f^{-1}(C)=(C-b) \ {\sf mod} \vert \mathcal{J}\vert . \)
Zauważmy, że ten sam parametr \( b \) jest kluczem funkcji dekodującej.
Przykład
Zakodujmy w kryptosystemie Cezara wiadomość: `FARSALOS'. Przyjmijmy, iż jednostki wiadomości zawierają jeden symbol. Wtedy, zgodnie z tabelą, numeryczny odpowiednik naszej wiadomości to:
\( 8,0,22,23,0,14,19,23. \)
Jeśli klucz funkcji (de)kodującej to \( b=33 \), to szyfrogram składa się z następujących jednostek:
\( 41,33,9,10,33,1,6,10, \)
czyli `5.GH.EA' jest treścią szyfrogramu.
Wyobraźmy sobie, iż nie jesteśmy nadawcą ani odbiorcą wiadomości, lecz osobą trzecią, bardzo zainteresowaną treścią przesyłanej wiadomości. Jak już wcześniej wspomnieliśmy zakładamy, iż wiadomo jaki kryptosystem jest użyty (w szczególności jaki jest zbiór jednostek wiadomości). Nieznane są jedynie klucze funkcji (de)kodującej.
Kryptoanaliza to dział kryptografii badający możliwość dekodowania wiadomości bez znajomości kluczy użytego kryptosystemu. W ogólności badane są tu też możliwości zamiany wiadomości, fałszowania podpisów, itp..
Załóżmy, iż przechwyciliśmy wiadomość zakodowaną w poprzednim przykładzie. Ponieważ istnieje tylko \( 46 \) możliwych wartości klucza, możemy szybko sprawdzić każdą ewentualność i prawie na pewno tylko w jednym przypadku zdekodowana wiadomość będzie miała sens. Widzimy więc, iż złamanie tego szyfru jest dziecinnie proste.
Jak poprawić bezpieczeństwo kryptosystemu Cezara? Można powiększyć zbiór jednostek wiadomości poprzez zwiększenie liczby symboli alfabetu w jednej jednostce. Wtedy automatycznie będzie więcej możliwych wartości klucza i trudniej będzie je wszystkie przeglądnąć.
Rozwiązanie to jest jednak podatne na tzw. analizę częstotliwości. Wróćmy na chwilę do jednostek wiadomości zawierających jeden symbol. W każdym języku naturalnym pewne symbole występują częściej, np. w języku polskim najczęściej używamy liter: A, E, I, itp. Gdy w przechwyconej wiadomości pewien symbol powtarza się częściej, możemy podejrzewać, iż reprezentuje on jedną z wymienionych liter. W przypadku gdy jednostki wiadomości zawierają więcej symboli analizujemy częstotliwość występowania odpowiednio długich zbitek liter. Jest to skuteczna metoda o ile mamy wystarczająco dużą próbkę zakodowanego tekstu.
Przykład
Przyjmijmy, iż przechwyciliśmy zakodowaną wiadomość: '5.GH.EA' (z poprzedniego przykładu). Wiedząc, iż zakodowana jest ona w kryptosytemie Cezara z jednostką informacji zawierającą pojedynczy symbol dokonując analizy częstotliwości symboli możemy zgadywać, iż symbol '.' (wartość \( 33 \)) reprezentuje symbol o dużej częstotliowści. Zgadując, iż jest to 'A' (wartość \( 0 \)) mamy
\( f('A')='5',\ \textrm{czyli}\ f(0)=0+b {\sf mod} 45 =33,\ \textrm{czyli}\ b=33. \)
Zatem bez sprawdzania wszystkich możliwych wartości udało nam się poznać wartość klucza, a co za tym idzie treść wiadomości
To nieznaczne udoskonalenie kryptosystemu Cezara. Funkcja kodująca jest tym razem, tzw. funkcją afiniczną na zbiorze \( \mathbb{Z}_{\vert J \vert} \), czyli
\( f(P)=a\cdot P+b {\sf mod} \vert\mathcal{J}\vert , \)
gdzie \( a,b\in\mathbb{Z}_{\vert\mathcal{J}\vert} \) są kluczami \( f \) i co bardzo ważne \( a\perp\vert\mathcal{J}\vert \) (dlaczego?). Sprawdźmy, iż po zakodowaniu i zdekodowaniu wrócimy do tego samego elementu
\( \begin{align*} f^{-1}(f(P)) & =f^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert ) \\ & =a^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert )+a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =a^{-1}(a\cdot P+b)-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P+a^{-1}b-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P {\sf mod} \vert\mathcal{J}\vert . \end{align*} \)
Pozostawiamy czytelnikowi wypracowanie szybkiego sposobu"złamania" tego kryptosystemu.