36499 Str041 (2)

78    3. KryptoftrtlU

Pierwszym krokiem przy tworzeniu systemu kryptograficznego jest „ponumerowanie” wszystkich możliwych jednostek tekstu jawnego i wszystkich możliwych jednostek tekstu zaszyfrowanego za pomocą obiektów matematycznych, które mogą być argumentami i wartościami łatwo konstruowal-nycli funkcji. Zazwyczaj tymi obiektami są liczby całkowite z pewnego przedziału. Jeśli na przykład naszymi jednostkami tekstu jawnego i tekstu zaszyfrowanego są pojedyncze litery 26-litcrowego alfabetu A-Z, to możemy ponumerować je liczbami naturalnymi 0, 1, 2,    25, które nazywamy ich „od

powiednikami liczbowymi”. Zatem w miejsce litery A piszemy 0, w miejsce litery S piszemy 18, w miejsce litery X piszemy 23 itd. Jako inny przykład weźmy digramy w 27-litcrowym alfabecie składającym się z liter A-Z i odstępu między wyrazami. Najpierw przypiszmy odstępowi liczbę 26 (następną po Z), a potem nadajmy digramowi złożonemu z liter o numerach x, j'e{0, 1, 2,

26} numer będący liczbą

27* + ye{0,1,..., 728}.

Zatem pojedyncze litery traktujemy jako cyfry w systemie pozycyjnym o podstawie 27, a digramy jako liczby dwucyfrowe w tym systemie. Na przykład digram „NO” odpowiada liczbie 27 • 13 + 14 = 365. Podobnie, jeśli będziemy używać trigramów jako jednostek tekstu, to ponumerujemy je liczbami 729* + lly + ze{0, 1,..., 19682}. Ogólnie, bloki k-literowe w alfabecie składającym się z N liter możemy ponumerować liczbami od 0 do N^k — 1 i traktować każdy taki blok jako k-cyfrową liczbę w systemie pozycyjnym o podstawie N.

W pewnych sytuacjach możemy chcieć ponumerować jednostki tekstu innymi obiektami matematycznymi, np. wektorami czy punktami pewnej krzywej. Jednak w tym rozdziale będziemy używać liczb całkowitych.

Przykłady. Zaczniemy od przypadku, w którym jednostką tekstu (jawnego i zaszyfrowanego) będzie pojedyncza litera pewnego AMiterowego alfabetu, ponumerowanego liczbami 0,1,2,..., N — 1. Wtedy, zgodnie z definicją, przekształcenie szyfrujące jest pewną permutacją tych N liczb.

W celu ułatwienia szybkiego szyfrowania i rozszyfrowywania wygodnie mieć względnie prostą regułę umożliwiającą dokonanie takiej permutacji. Jedna metoda polega na tym, by myśleć o liczbach 0, 1,2,..., N — 1 jako o elementach ZjNZ i skorzystać z działań dodawania i mnożenia modulo N.

Przykład 1. Przypuśćmy, że używamy 26-literowego alfabetu A-Z z jego liczbowymi odpowiednikami 0-25. Niech litera Pe {0,1,..., 25} oznacza jednostkę tekstu jawnego. Zdefiniujmy funkcję /ze zbioru {0,1,..., 25} w ten sam zbiór za pomocą wzoru

f P + 3, dla * < 23,

/(?) = \

1 P - 23, dla x > 23.

inaczej mówiąc,/po prostu dodaje 3 modulo 26: f(P)* P + 3 (mod 26). Tę definicję łatwiej zapisać za pomocą arytmetyki modulo N i łatwiej jej wtedy używać. Teraz, w tym systemie kryptograficznym, aby zaszyfrować słowo „YES”, najpierw przekształcamy je na liczby: 24 4 18, potem dodajemy 3 modulo 26:1 7 21, a na końcu z powrotem przekształcamy na litery: „BH V”. Aby rozszyfrować wiadomość, odejmujemy 3 modulo 26. Na przykład kryptogram „ZKB” rozszyfrowuje się do tekstu jawnego „WH Y”. Ten system kryptograficzny był w rzeczywistości stosowany w starożytnym Rzymie przez Juliusza Cezara, który podobno sam go wymyślił.

Przykład 1 może być uogólniony w następujący sposób. Przypuśćmy, że używamy AMiterowego alfabetu z liczbowymi odpowiednikami 0,1,..., N - 1. Niech b będzie ustaloną liczbą całkowitą. Przesunięciem będziemy nazywać przekształcenie szyfrujące /zdefiniowane za pomocą wzoru C=f(P) = P + b (mod N). W systemie kryptograficznym Juliusza Cezara mieliśmy N = 26, b- 3. Aby rozszyfrować jednostkę tekstu zaszyfrowanego Ce{0, 1, ..., N- 1}, po prostu obliczamy P = f~^l(Q = C-b(mod N).

Załóżmy teraz, że nie zostaliśmy wtajemniczeni w metody szyfrowania i rozszyfrowywania, ale pomimo to chcielibyśmy umieć czytać zaszyfrowane wiadomości. Nazywa się to łamaniem szyfru, a nauka zajmująca się łamaniem szyfrów nazywa się kryptoanalizą.

Aby złamać system kryptograficzny, potrzebujemy dwóch rodzajów informacji. Pierwsza dotyczy ogólnej postaci (struktury) systemu. Przypuśćmy na przykład, że wiemy, iż w systemie kryptograficznym używa się przesunięcia pojedynczych liter 26-literowego alfabetu A-Z z liczbowymi odpowiednikami 0-25. Drugi rodzaj informacji dotyczy znajomości wartości pewnych parametrów związanych z systemem. W naszym przykładzie tym drugim rodzajem informacji jest znajomość parametru przesunięcia b. Z chwilą gdy zdobędziemy tę informację, będziemy mogli szyfrować i rozszyfrowywać za pomocą wzorów C s P + b (mod N)iP = C - b (mod N).

Będziemy zawsze zakładać, że ogólna struktura systemu jest znana. W praktyce użytkownicy kryptografii często mają odpowiednie urządzenia do szyfrowania i rozszyfrowywania, których konstrukcja umożliwia zastosowanie tylko jednego rodzaju systemu kryptograficznego. Po pewnym czasie informacja o tym, jakiego systemu oni używają, może wydostać się na zewnątrz. Zatem, aby zwiększyć bezpieczeństwo tego systemu, często zmienia się wykorzystywane w nim parametry. Przypuśćmy na przykład, że dwaj użytkownicy systemu opartego na przesunięciu mogą spotkać się tylko raz w roku. Wtedy uzgadniają oni listę 52 wyborów parametru b, po jednym na każdy tydzień następnego roku.

Ten parametr b (bardziej skomplikowane systemy kryptograficzne zazwyczaj mają wiele parametrów) nazywamy kluczem bądź - bardziej precyzyjnie - kluczem szyfrowania (lub kluczem szyfrującym).