Str061 (2)

I IR 4. Klucyc pubHcme

o tym samym obrazie, jeśli znamy oba klucze K_F i K_p (mianowicie możemy znaleźć oba przcciwobrazy /'(/?,)); ale zakładamy, że znajomość tylko K» nic daje praktycznych możliwości obliczenia elementu p₂, stowarzyszone* go z p_t, dla żadnego /),.

Przypuśćmy, żc gracz A (Anita) i gracz B (Bartek) chcą użyć takiego systemu do rzucenia monetą. Anita generuje dwa klucze K_E i K_D i Wysyła Bankowi klucz K_F (ale nie wysyła klucza K_D). Opisz procedurę, która daje każdemu graczowi szansę 50% na „wygranie” (przy odpowiednio dobranej definicji „wygranej”) oraz ma odpowiednie zabezpieczenia przed oszukiwaniem.

Bibliografia

I. Biuro M.: Coin-flippmg by tclephonc - a protocol for solving impossiblc problcms. IEEE Proc., Spring Compcon., 1982, s. 133*137.

1 Chaum D.: Achieving ciec Ironie privacy. Scientijic American, 1992, 267, s. 96-101.

3.    Difllc W., Hellman M.E.: New directions in ayptography. IEEE Transactions on Information Theory IT-22, 1976, s. 644-654.

4.    Ooldwasser S.: The search for provably secure eryptosystems. Cryptology and Computational Number Theory. Proc. Symp. Appl. Math., 1990, 42, s. 89-113.

5.    Hellman M.E.: The roathemalics of public-key cryptography. Scientific American, 1979, 241, s. 146-157.

6.    Kranakis E.: Primality and Cryptography. John Wiley & Sons 1986.

7.    Rjveśt R.: Cryptography. Handbook of Theoretical Computer Science. Vol. A, Elsevier 1990, | 717-755.

8.    Ruggiu G.: Cryptology' and complexity theories. Adoances in Cryptology, Proceedlngs of Euro-orypi 84, Springer-Yerlag 1985, s. 3-9.

4.2. System RSA

Przy poszukiwaniu funkcji progowej f którą mamy zastosować w systemie z publicznym kluczem, chcemy, z jednej strony, użyć pomysłu względnie prostego pojęciowo i prowadzącego do łatwej implementacji. Z drugiej strony, potrzebujemy silnych dowodów empirycznych - opartych na długiej historii prób znalezienia algorytmu obliczającego wartości /^-1 - na to, że rozszyfrowywanie nie może być łatwo dokonane bez znajomości tajnego klucza rozszyfrowującego. Z tego powodu naturalne jest przyjrzenie się dawnemu problemowi z teorii liczb: problemowi znalezienia rozkładu dużej liczby złożonej na czynniki pierwsze, których nie znaliśmy wcześniej. Tak zwany system „RSA” (nazwa pochodzi od nazwisk trzech twórców: Rivesta, Shamira i Adlemana), który jest jednym z najstarszych (ma ponad 15 lat) i jednym z najpopularniejszych systemów z publicznym kluczem, swoje powodzenie zawdzięcza niezwykłym trudnościom związanym z rozkładem liczb na czynniki.

Opiszemy teraz, jak działa system RSA. Każdy użytkownik najpierw wybiera dwie niezwykle duże liczby pierwsze p i q (np. mające po około

100 cyfr) i mnoży jc przez siebie: n ~ pq. /nająć rozkład liczby n na czynniki pierwsze, łatwo obliczyć <p{ń)=(p --- I )(ę - I) * n -f I ~ p ~ q. Następnie użytkownik wybiera losowo liczbę i między I i tp(n), względnie pierwszą i <p(n).

Uwaga. Gdy mówimy o liczbie „losowej”, mamy na myśli liczbę wybraną za pomocą pewnego generatora liczb losowych (czy też generatora liczb „pseudo* losowych”), tj. programu komputerowego generującego ciąg cyfr w taki sposób, by nikt nic mógł ich przewidzieć czy powtórzyć oraz by ten ciąg mógł mieć wszystkie statystyczne własności prawdziwego ciągu losowego. Wiele napisano na temat doboru efektywnych i bezpiecznych metod generowania liczb losowych i nic będziemy się tą kwestią tutaj zajmować. W systemie RSA potrzebujemy generatora liczb losowych nie tylko do wyboru liczby e, ale także do wyboru dużych liczb pierwszych p i q (tak, by nikt nie mógł odgadnąć naszego wyboru, zaglądając do tablic liczb pierwszych szczególnych typów, np. liczb pierwszych Mersenne’a czy dzielników pierwszych liczb postaci t/± 1 dla małych b i względnie małych k). Co oznacza „wygenerowana losowo” liczba pierwsza? Otóż, po pierwsze wygenerujmy dużą losową liczbę m. Jeśli m jest liczbą parzystą, to zastąpmy ją przez m + 1. Następnie zastosujmy odpowiednie testy pierw szóści, by przekonać się, czy nieparzysta liczba m jest liczbą pierwszą (testy pierwszości będą omawiane systematycznie w następnym rozdziale). Jeśli liczba m nic jest liczbą pierwszą, to zastąpmy m przez m + 2, następnie przez m + 4 itd., aż napotkamy najmniejszą liczbę pierwszą nie mniejszą niż m, którą uznamy za naszą „losową” liczbę pierwszą. Zgodnie z twierdzeniem o liczbach pierwszych (zob. sformułowanie tego twierdzenia w ćwiczeniu 11 z podrozdziału 1.1) częstość występowania liczb pierwszych w pobliżu liczby m wynosi około 1/logm, a więc możemy spodziewać się, że przetestujemy O(logm) liczb, zanim natrafimy na najmniejszą liczbę pierwszą nie mniejszą niż m.

Podobnie, „losową” liczbę e względnie pierwszą z <p(n) możemy wybrać, generując najpierw losową liczbę (nieparzystą) o odpowiedniej liczbie cyfr, a następnie zwiększając ją sukcesywnie tak długo, aż napotkamy liczbę e taką, że NWD(e, <p(n)) = 1. (Inaczej, możemy przeprowadzać testy pierwszości dopóty, dopóki nie znajdziemy liczby pierwszej e zawartej między np. max(p, q) i tp(n); taka liczba pierwsza musi być względnie pierwsza z ę{n).)

A więc każdy użytkownik A wybiera dwie liczby pierwsze p_A i q_A oraz losową liczbę e_A nie mającą wspólnych dzielników z (p_A - 1 )(q_A - 1). Następnie A oblicza n_A = p_Aq_A, <p(n_A) = n_A + \ - p_A- q_A oraz znajduje liczbę odwrotną do e_A modulo (p(n_A): d_A = e_A^l mod ę{n_A). Klucz szyfrujący K_EA = = (n_A, e_A) podaje do publicznej wiadomości, natomiast klucz rozszyfrowujący K_DiA = (n_A, d_A) zachowuje w tajemnicy. Przekształceniem szyfrującym jest funkcja ze zbioru Z/n_AZ w ten sam zbiór, dana wzorem f(P) s P'* (mod n_A).