71959 Str064 (2)

124    4. Klucze pubUcme

124    4. Klucze pubUcme

" “ (^ 2 ^    ~ \ 2 / * *^,CŚ,i P 1 q 84 b,iskic 8icbic* ^t0 Hcxba

.v« (j> - </)/2 jest mała i wtedy t = (p + tf)/2 jest liczbą niewiele większą niż »taką że liczba t¹ - n jest pełnym kwadratem. Jeśli będziemy badać kolejne liczby / > yjn , to wkrótce natrafimy na taką liczbę, że n — i¹ — s¹ i wtedy wystarczy zauważyć, że p= t + s, q = t — s. (Por. ćwiczenie 3 w podrozdziałach 1.2 oraz 5.3.)

5.    Załóżmy, że dany jest szybki algorytm (algorytm probabilistyczny) roz

wiązujący równanie x² = a (mod p) dla dowolnej liczby pierwszej p i dowolnej reszty kwadratowej a. Testując na przykład liczby losowe i obliczając symbole Lcgendre'a, możemy z dużym prawdopodobieństwem znaleźć nicrcsztę kwadratową modulo p\ wtedy będziemy mogli zastosować algorytm opisany w podrozdziale 2.2. Załóżmy jednak, że nie istnieje żaden dobry algorytm rozwiązujący równanie x² = a (mod n), gdy a jest kwadratem modulo n oraz n = pq jest iloczynem dwóch dużych liczb pierwszych, o ile nie znamy rozkładu n na czynniki (w takim przypadku moglibyśmy znaleźć pierwiastek kwadratowy modulo p i modulo q, a następnie skorzystać z chińskiego twierdzenia o resztach, by znaleźć pierwiastek kwadratów)' modulo ń). Przypuśćmy, że żadna z liczb p i q nie przystaje do 1 modulo 4. Niech K_E = n i niech K_D — {/?, q) będzie rozkładem n na czynniki. Niech 9 — V = (Z/nZ)*/± 1 będzie zbiorem par (*, —x) reszt modulo n liczb względnie pierwszych z n, gdzie liczby przeciwne do siebie występują razem. Niech    będzie przekształceniem x\-*x² mod n.

Wykaż, że w ten sposób otrzymujemy rozwiązanie ćwiczenia 4 z poprzedniego podrozdziału. W ten sposób możemy zaimplementować rzucanie monetą na odległość.

6.    Niech n będzie liczbą bezkwadratową (tzn. iloczynem różnych liczb pierwszych). Niech d i e będą takimi liczbami naturalnymi, że liczba de — 1 jest podzielna przez p — 1 dla każdego dzielnika pierwszego p liczby n. Jest tak na przykład, gdy de = 1 (mod <p(nj). Udowodnij, że wtedy a^de = a (mod n) dla dowolnej liczby całkowitej a (niezależnie od tego, czy ma ona wspólny dzielnik z n).

7.    Udowodnij stwierdzenia sformułowane w punktach (i) i (ii) uwagi 2, dotyczące częstości przystawania liczby a^ml2 do 1 lub — 1 modulo p i q.

Bibliografia

1.    Adleman L.M., Rivest R.L., Shamir A.: A melhod for oblaining digital signatures and pub-lic-key cryplosystems. Communications of the ACM, 1978, 21, s. 120-126.

2.    Rivesl R.L.: RSA chips (pa*t/pre*ent/future). Adoances In Cryptology, Proceedings of Euro-erypt 84, Springer-Verlag 1985, s. 159-165.

3.    Gordon JA.: Strong primes are easy to flnd. Adoances In Cryptology, Proceedings of Eurocrypt 84, Springer-Vcrlag 1985, s. 216-223.

4.3. Logaryim dyskretny

System RSA, opisany w poprzednim podrozdziale, jest oparty na tym, ■_c znalezienie dwóch dużych liczb pierwszych i pomnożenie ich przez siebie po _(0f by otrzymać liczbę n, jest znacznie łatwiejsze niż postępowanie odwrotne (tzn. znalezienie tych dwóch liczb pierwszych, mając daną liczbę n). W teorii ijczb istnieją inne procesy, o fundamentalnym znaczeniu, które również wydają _sję mieć tę własność „progowości lub jednokierunkowości”. Jednym z takich procesów jest podnoszenie do potęgi w dużym ciele skończonym.

Kiedy mamy do czynienia z liczbami rzeczywistymi, podnoszenie do potęgi (czyli obliczanie b^x z dowolną dokładnością) nie jest czynnością istotnie łatwiejszą niż operacja odwrotna (tzn. obliczanie log** z dowolną dokładnością)- Ale teraz przypuśćmy, źe mamy do czynienia z grupą skończoną, taką jak (Z/nZ)* lub FJ (z mnożeniem jako działaniem w grupie). Metoda iterowa-aego podnoszenia do kwadratu (por. podrozdział 1.3) umożliwia obliczenie b^x dla dużych x dość szybko (w czasie wielomianowym względem log*). Ale jeśli mamy dany element y, o którym wiemy, że jest postaci b^x (zakładamy, że nodstawa” b jest ustalona), to w jaki sposób możemy znaleźć wykładnik takiej potęgi ó, która jest równa y, tzn. w jaki sposób możemy obliczyć x = logfrj' (przy czym „log” ma tu znaczenie inne, choć podobne do poprzedniego)? Ten problem jest znany pod nazwą „problemu logarytmu dyskretnego”. Słowo „dyskretny” odróżnia przypadek grup skończonych od klasycznego przypadku (ciągłego).

Definicja. Jeśli G jest grupą skończoną, b elementem tej grupy oraz y jest takim elementem G, który jest potęgą b, to logarytmem dyskretnym dementuj o podstawie b jest taka liczba całkowita x, dla której łf = y.

Przykład 1. Jeśli weźmiemy G = Ff₉ = (Z/19Z)* i jeśli b = 2 będzie generatorem tej grupy (por. przykład 1 z podrozdziału 2.1), to logarytmem dyskretnym z 7 o podstawie 2 będzie liczba 6.

Przykład 2. W grupie FJ, w której a jest pierwiastkiem wielomianu X² - X - l (por. przykład 2 z podrozdziału 2.1), logarytmem dyskretnym z -1 o podstawie a jest liczba 4.

Pod koniec tego podrozdziału omówimy krótko obecny stan wiedzy na temat algorytmów rozwiązujących problem logarytmu dyskretnego w ciałach skończonych. Przedtem jednak opiszemy kilka systemów kryptograficznych z publicznym kluczem oraz kilka specjalnych ustaleń wykorzystujących publiczne klucze, opartych na trudnościach obliczeniowych związanych ze znajdowaniem logarytmów dyskretnych w ciałach skończonych.

System wymiany kluczy Difficgo-Hcllmana. Ponieważ systemy z publicznym kluczem są wolniejsze w porównaniu z systemami klasycznymi (przynaj-