Str058 (2)

112    4. Klucre publiczni*

tego. by komputer mógł sprawdzać hasła, nie przechowując jednocześnie infor. macji. które mogłyby być wykorzystane przez intruza do podszycia się uprawnionego użytkownika.

W systemie Needhuma, gdy użytkownik po raz pierwszy ustala swoje hasło lub gdy je kiedykolwiek zmienia, jest ono natychmiast poddane procesowi szyfrowania i przechowywana jest tylko jego zaszyfrowana postać. Za każdym razem, gdy na żądanie wprowadzane jest hasło po to, by sprawdzić tożsamość użytkowniku, jest ono znów szyfrowane i otrzymany wynik jest porównywany i wersją przechowywaną w pamięci. Zdobycie przez włamywacza listy zaszyfrowanych haseł nie przyniesie mu pożytku, gdyż nie będzie umiał ich rozszyfrować przed użyciem. Do tego musiałby mieć dostęp do komputera, ale nawet gdyby zdobył wszystkie szczegóły dotyczące algorytmu szyfrowania, proces rozszyfrowywania trwałby bardzo długo.

W 1974 roku G. Purdy opublikował pierwszy szczegółowy opis takiej funkcji jednokierunkowej. Oryginalne hasła i ich zaszyfrowane postaci są traktowane jak reszty z dzielenia przez dużą liczbę pierwszą /?, a funkcja jednokierunkowa F_p -» F_p jest określona za pomocą wielomianu /(*), którego wartości mogą być łatwo obliczone za pomocą komputera, ale dla którego obliczanie wartości funkcji odwrotnej trwałoby stanowczo zbyt długo. Purdy wziął liczbę p = 2⁶* ~ 59 oraz f {x) = x*^u+il + a₁jc^2W+3 + a₂ć +    +

+ a₄x + a₅, gdzie współczynniki a_t były dowolnymi liczbami całkowitymi 19-cyfrowymi.

Powyższa definicja systemów z publicznym kluczem i funkcji progowych lub jednokierunkowych nie jest wystarczająco precyzyjna z matematycznego punktu widzenia. Pojęcie „praktycznej obliczalności” odgrywa w niej kluczową rolę. Ale jest to pojęcie czysto empiryczne i jego znaczenie zależy od postępów technologii komputerowej (np. procesorów wykonujących obliczenia równoległe) oraz odkryć nowych algorytmów, które przyspieszają wykonywanie zadań arytmetycznych (czasami nawet wielokrotnie). Można sobie zatem wyobrazić, że przekształcenie szyfrujące uważane za progowe lub jednokierunkowe w roku 1988 przestanie być uważane za takie w roku 1998 lub 2998.

Można sobie wyobrazić, że udowodnimy, iż jakieś przekształcenie jest progowe. To znaczy, udowodnimy twierdzenie dające nietrywialne ograniczenie dolne liczby operacji na bitach potrzebnych (w „średnim” przypadku, tzn. dla losowych wartości parametrów) do wykonania algorytmu rozszyfrowującego bez użycia klucza rozszyfrowującego. Musimy w takim przypadku dopuścić możliwość badania dużej liczby odpowiadających sobie tekstów otwartych i kryptogramów (podobnie jak w analizie częstości prostych systemów w rozdziale 3), gdyż definicja systemów z publicznym kluczem zakłada, że dowolny użytkownik może wygenerować dowolną liczbę par: tekst otwarty-krypto-gram. Będziemy musieli dopuścić również stosowanie metod „probabilistycznych”, które wprawdzie nie gwarantują złamania szyfru od razu, ale prawdopodobnie pozwolą złamać szyfr po wielokrotnym powtórzeniu. (Przykłady algorytmów probabilistycznych będą podane w następnym rozdziale). Nieste-

iy, żadne tego typu twierdzenie nie zostało udowodnione dla żadnej funkcji używanej w systemach kryptograficznych. Zatem, pomimo że znamy już wiele systemów kryptograficznych, które zgodnie z naszym doświadczeniem zasługują na miano „systemów z publicznym kluczem”, nic znamy jednak systemu, o którym dowiedziono by, źe jest takim systemem.

Uzasadnieniem nazwy „publiczny klucz” jat to, źe informacja potrzebna do wysyłania zaszyfrowanych wiadomości - klucz szyfrujący K_t - może być ogłoszona publicznie i każdy ma do niej dostęp bez konieczności czytania tajnych dokumentów. Przypuśćmy, źe mamy daną pewną populację użytkowników systemu kryptograficznego, z których każdy chce otrzymywać od innych poufne wiadomości w taki sposób, by inne osoby (użytkownicy systemu lub osoby spoza systemu) nic mogły odczytać przesyłanych informacji. Pewna instytucja centralna może zebrać od wszystkich użytkowników A ich klucze szyfrujące K_{E A} i opublikować je w postaci „książki telefonicznej” mającej postać

AAA Banking Company .... (9974398087453939,2975290017591012)

Aardvark, Aaron................(8870004228331,7234752637937)

Ktoś, kto chce wysłać zaszyfrowaną wiadomość, wyszukuje w tej „książce telefonicznej” odpowiedni klucz szyfrujący, a następnie wykonuje ogólny algorytm szyfrowania z kluczem-parametrem właściwym dla adresata. Tylko wybrany adresat posiada odpowiedni klucz rozszyfrowujący potrzebny do odszyfrowania wiadomości. 2/1 -&/-    ■-*>. /,. a

I W dawnych czasach stosowanie podobnych systemów kryptograficznych nie dawałoby spektakularnych korzyści. Tradycyjnie kryptografia była stosowana głównie do celów wojskowych i w korespondencji dyplomatycznej. Zazwyczaj niewielka, dobrze określona grupa użytkowników miała dostęp do wszystkich kluczy i nowe klucze mogły być regularnie rozsyłane (za pośrednictwem kurierów) tak, by przeciwnik ciągle musiał ich poszukiwać na nowo.

Jednakże w ostatnich latach aktualne i potencjalne zastosowania kryptografii rozciągnęły się na wiele nowych dziedzin, w których systemy komunikacji odgrywają podstawową rolę - zbieranie i przechowywanie poufnych danych, elektronicznie zlecane transakcje finansowe itp. Wielokrotnie mamy do czynienia z dużymi sieciami użytkowników, z których każdy może chcieć przestać do innego wiadomość, której treść chce ukryć przed innymi użytkownikami sieci i innymi osobami. Dwaj użytkownicy mogą chcieć skorzystać z okazji przesiania poufnej wiadomości tylko raz, a niedługo potem jeden z nich może chcieć wymienić tajną korespondencję z innym użytkownikiem sieci. Powstające zatem „układy” - tzn. kto z kim wymienia utajnioną korespondencję - mogą się stale zmieniać. Stała wymiana kluczy pomiędzy wszystkimi możliwymi korespondentami byłaby bardzo niepraktyczna.

Zauważmy, że w systemie z publicznym kluczem dwaj partnerzy mogą rozpocząć tajną korespondencję bez uprzedniego bezpośredniego kontaktu ze