44908 Str057 (2)

110    4 Kłucie publłcmc jącv różni się od algorytmu szyfrującego). Będziemy zawsze zakładać, że algorytmy szyfrujący i rozszyfrowujący są powszechnie znane i tylko klucze K_p i K_n mogą być trzymane w tajemnicy.

Przypuśćmy teraz, że ktoś chce używać powyższego afiniczncgo systemu kryptograficznego C = aP + b (mod AO do tajnego porozumiewania się. Wi-dzicliśmy w podrozdziale 3.1, że nietrudno złamać ten system, jeśli jako jednostek tekstu użyto pojedynczych liter pewnego AMiterowego alfabetu. Trochę trudniej złamać ten system, jeśli zostały użyte digramy, które można rozpatrywać jako symbole alfabetu składającego się z N² liter. Jeszcze bezpieczniej byłoby użyć bloków fc-Iitcrowych, mających odpowiedniki liczbowe w Z/N^kZ. Już dla k > 3 nic jest łatwo korzystać z analizy częstości, gdyż liczba wszystkich możliwych bloków fc-litcrowych jest bardzo duża i zauważymy, że wiele z nich może ubiegać się o tytuł najczęściej występującego bloku. Jeśli zechcemy zwiększyć k, to musimy wziąć pod uwagę wzrost czasu potrzebnego do wykonania różnych operacji arytmetycznych (najważniejszym będzie znalezienie a~^l za pomocą algorytmu Euklidesa) związanych z wyborem klucza i wykonaniem potrzebnych obliczeń za każdym razem, gdy wysyłamy wiadomość lub gdy nasz przyjaciel odczytuje naszą wiadomość. Chcemy zatem znać oszacowania, w notacji O, rzędu wielkości czasu (zależnego od wzrostu parametrów, tzn. gdy nasz system kryptograficzny „zwiększa się”) potrzebnego do: szyfrowania (gdy znamy K_E), rozszyfrowywania (gdy znamy K_D) oraz łamania szyfru, tzn. szyfrowania bez znajomości K_E lub rozszyfrowywania bez znajomości K_D.

We wszystkich przykładach w rozdziale 3 - i we wszystkich systemach kryptograficznych znanych w historii aż do około kilkunastu lat temu - nie było konieczne podawanie oddzielnie klucza rozszyfrowującego, gdy znany był klucz szyfrujący (i ogólny algorytm). Nawet jeśli mieliśmy do czynienia z dużymi liczbami - takimi jak N^k z dość dużym k - można było otrzymać klucz rozszyfrowujący z klucza szyfrującego w czasie z grubsza takim samym, jak czas potrzebny do wcielenia w życie algorytmów szyfrujących. Na przykład w przypadku afmicznych przekształceń szyfrujących zbioru Z/N^kZ, jeśli znaliśmy klucz szyfrujący K_E = (a, b), to mogliśmy wyznaczyć klucz rozszyfrowujący K_d = (a^-1 mod N\ —a~ -b mod N^k) za pomocą algorytmu Euklidesa, wykonując O (log³ (AT*)) operacji na bitach.

Zatem w tradycyjnych systemach kryptograficznych każdy, kto wiedział wystarczająco wiele, by móc rozszyfrowywać wiadomości, mógł też bez znacznie większego wysiłku otrzymać klucz szyfrujący. Faktycznie tylko ktoś bardzo naiwny lub nierozsądny mógłby sądzić, że osoba, której udało się złamać szyfr, mogłaby nadal nie znać klucza szyfrującego. Widzimy to w poniższym fragmencie autobiografii znanej postaci historycznej:

Pięć lub sześć tygodni później zapytała mnie ona [Pani d’Urfó], czy rozszyfrowałem już zaszyfrowany manuskrypt. Powiedziałem jej, źe rozszyfrowałem.

-    Bez klucza, Pan mi wybaczy, ale nic wierzę, by było to możliwe.

-    Czy chce Pani, bym wymienił ten klucz, madame?

- Bardzo o to proszę.

Powiedziałem jej wtedy to słowo-klucz, które nie pochodziło z żadnego języka, i zobaczyłem, jak bardzo ją lo /dziwiło Powiedziała mi, że to niemożliwe, gdyż wierzyła, że tylko ona zna to słowo, które przechowywała w pamięci i nawet nigdy go nie zapisała.

Mógłbym powiedzieć jej prawdę — że te same obliczenia, które pozwoliły mi odczytać rękopis, pozwoliły mi także poznać to słowo - ale jakiś kaprys kazał mi powiedzieć jej, że geniusz odkrył je przede mną. To nieprawdziwe wyznanie przywiązało ją do mnie. Tego dnia stałem się panem jej duszy i nadużyłem mojej mocy. Za każdym razem, gdy o tym myślę, trapi mnie to i zawstydza, i czynię dziś pokutę, każąc sobie napisać prawdę w mych wspomnieniach.

Słowa Casajiovy° (1757); cytowane za O. Kaimem: The Codebreakers

Ta sytuacja przetrwała przez następne 220 lat od chwili spotkania pomiędzy Casanovą i Panią d’Urfe: znajomość metod szyfrowania i znajomość metod rozszyfrowywania były uważane za równoważne w każdym systemie kryptograficznym. Jednakże w 1976 roku W. Diffie i M. Hełłman odkryli zupełnie nowy typ systemów kryptograficznych i stworzyli „systemy z publicznym .kluczem**..

Z definicji, system kryptograficzny z publicznym kluczem ma tę własność, że ktoś, kto wie, w jaki sposób szyfrować wiadomości, nie może wykorzystać klucza szyfrującego do tego, by znaleźć klucz rozszyfrowujący bez niezmiernie długich obliczeń. Inaczej mówiąc, wartości przekształcenia szyfrującego/: & —* <8* można łatwo obliczyć, gdy znamy klucz szyfrujący K_E, ale w praktyce jest bardzo trudno obliczać wartości funkcji odwrotnej A więc, z punktu widzenia obliczalności praktycznej, funkcja f nie jest odwracalna (bez dodatkowej informacji — klucza rozszyfrowującego K_D). Taka funkcja f nazywa się funkcją progową lub funkcją jednokierunkową z kluczem (ang. trapdoor function). Zatem funkcja progowa /jest to funkcja, której wartości można łatwo obliczać, ale trudno obliczyć wartości funkcji odwrotnej / ~¹ - bez dodatkowej informacji pomocniczej niepotrzebnej do obliczania wartości f Może natomiast łatwo obliczać wartości funkcji odwrotnej/^-1 ktoś, kto ma te dodatkowe informacje K_D („klucz rozszyfrowujący”).

Blisko związane z funkcjami progowymi są funkcje jednokierunkowe (bez klucza) lub inaczej funkcje jednostronne (ang. one-way function). Są to funkcje f takie, że ich wartości można łatwo obliczać, ale wartości funkcji odwrotnej f ~¹ są trudne do obliczenia i tych obliczeń nie może ułatwić żadna dodatkowa informacja. Podczas gdy pojęcie funkcji progowej pojawiło się po raz pierwszy w 1978 roku wraz z wynalezieniem systemu kryptograficznego RSA z publicznym kluczem, pojęcie funkcji jednokierunkowej jest nieco starsze. Wydaje się, że po raz pierwszy sposób korzystania z funkcji jednokierunkowych w kryptografii został opisany w książce Wilesa dotyczącej systemów podziału czasu (ang. time-sharing systems\ opublikowanej w 1968 roku. Autor opisuje nowy szyfr jednokierunkowy zastosowany przez R. M. Needhama do

W przekładzie tłumacza (przyp. red.)