68327 Str067

1.10    4. Kłuci* publiczne

podrozdział 4.1), otrzymując liczbę h z przedziału 0 < h < q. Następnie wybiera losową liczbę k z tego samego przedziału, oblicza g^k modulo p i jako r bierze resztę z dzielenia wyniku przez q (a więc najpierw oblicza g^k modulo />, a następnie wynik dzieli przez mniejszą liczbę pierwszą q i bierze resztę). Wreszcie Alicja znajduje liczbę całkowitą .v taką. że sk = h + xr (mod q). Jej podpisem jest wtedy para (r, s) liczb całkowitych wziętych modulo q.

Aby stwierdzić autentyczność podpisu, adresat (niech np. będzie nim Bolek) oblicza u_{ =s~^lh mod q i u₂ = s~^lr mod q. Następnie oblicza g^Uiy^t* (mod p). Jeśli wynik przystaje do r modulo q, uznaje autentyczność podpisu. (Zauważmy, że g"¹/"³ =    = g^k (mod p).)

Ten schemat podpisu ma tę zaletę, że podpisy są względnie krótkie, składają się z dwóch liczb 160-bitowych (mają taki rząd wielkości jak q). Jednakże bezpieczeństwo systemu wydaje się zależeć od trudności obliczeniowych związanych z problemem logarytmu dyskretnego w grupie multyplikatywnej dość dużego ciała F_p. Chociaż do złamania systemu wystarczyłoby znaleźć logarytmy dyskretne w mniejszej podgrupie generowanej przez g, jednak w praktyce nic wydaje się to być łatwiejsze niż znalezienie logarytmów dyskretnych w F*. Zatem wydaje się, że DSS osiągnął zupełnie wysoki poziom bezpieczeństwa, nie rezygnując z małej pamięci potrzebnej do przechowywania podpisu i szybkiego czasu działania.

Algorytmy znajdujące logarytm dyskretny w ciałach skończonych. Najpierw założymy, że wszystkie dzielniki pierwsze liczby ^ — 1 są małe. Przy tym założeniu istnieje szybki algorytm znajdujący logarytm dyskretny elementu yeFJ o podstawie b. Dla uproszczenia przyjmijmy, źe b jest generatorem grupy FJ. Teraz opiszemy ten algorytm, opracowany przez Silvera, Pohliga i Hcllmana.

Najpierw dla każdego dzielnika pierwszego p liczby q — 1 obliczamy pierwiastki stopnia p z jedności dane wzorem r_{p l} —    dla j = 0, 1, ...,

p — 1. (Jak zwykle korzystamy z algorytmu iterowanego podnoszenia do kwadratu, by podnieść b do dużej potęgi). Mając już tablicę {r_p j}, możemy przystąpić do obliczania logarytmu dyskretnego dowolnego yeFJ. (Zauważmy, że jeśli podstawa b jest ustalona, to obliczenie wstępne musi być przeprowadzone tylko jeden raz, potem ta sama tablica będzie używana dla dowolnego y)

Naszym zadaniem jest znalezienie liczby *, 0 < * < q — 1, takiej, że b* — y. Jeśli q — 1 = f] p^a jest rozkładem liczby q — 1 na czynniki pierwsze, to

p

wystarczy znaleźć x mod p^a dla każdego dzielnika pierwszego p liczby q — 1; wtedy liczba x jest wyznaczona jednoznacznie przez algorytm z dowodu chińskiego twierdzenia o resztach (twierdzenie 1.3.3). Zatem ustalamy teraz dzielnik pierwszy p liczby q — 1 i pokażemy, jak obliczyć x mod p^a.

Przypuśćmy, że x = x₀ + x_vp + ... + x_a__ip*~ⁱ (mod p“), przy czym 0 < x_{ < p. Aby znaleźć x₀, obliczamy y^{(,_ 1)/p}. Otrzymujemy pierwiastek stopnia p z jedności, gdyż y^,_1 = 1. Ponieważ y ~ b*, więc    — £*(«-i)/p —

5- ffM~^l),p =* r_{Pi Xfl}. Zatem porównujemy /* z \r_f j}<,_<j<p i jako x₀ bierzemy tę wartośćdla której y^lą~^l)lf = r_py

Następnie, aby znaleźć zastępujemy y przez y, = y/ó*\ Wtedy loga-_rytin dyskretny y,, równy x - x₀, przystaje do x_tp + ... + x_f_₁p*~¹ modulo «*. Ponieważ y_i jest p-tą potęgą, więc = a zatem    =

*    ₌ ffk- uiP * znów porównujemy

y«"^1)/pl _z {r^j} i jako x, bierzemy tę wartośćJ, dla której y^"¹^ = r_pj.

Teraz już powinno być jasne, w jaki sposób indukcyjnie znajdujemy wszystkie współczynniki x₀, *„    x_a_,. Mianowicie dla każdego i- 1,2,...,

a -1 bierzemy

y, = y/ó*®‘^fx,,+ ”'⁺**'^,p,*^,f

którego logarytm dyskretny przystaje do x,p^ł +... + x_a__ł/'¹ modulo />“. ponieważ y, jest p-tą potęgą, więc yj*^_1,/p‘ = 1 i    =

= ó^(x,+*^,+,p+'"^)(,“^1)/p = b^x,lq~^i)lp = r_pX|. Znów jako x, bierzemy tę wartośćy, dla której yj*^-1^’ = r_pj.

Po zakończeniu tego postępowania znamy x mod p* i po powtórzeniu tego dla wszystkich p\q - 1 korzystamy z chińskiego twierdzenia o resztach, by znaleźć x.

Ten algorytm działa dobrze, gdy wszystkie dzielniki pierwsze liczby q- 1 są małe. Ale jasne jest, że wyznaczenie tablicy {r_{p j}} i porównywanie yj^ł'¹)/^p,+l z elementami tej tablicy zabierze bardzo dużo czasu, gdy ę -1 jest podzielna przez dużą liczbę pierwszą. (Przez „dużą” rozumiemy liczbę mającą co najmniej 20 cyfr dziesiętnych. Jeśli liczba p\q - 1 jest mniejsza niż lO²⁰, to można połączyć algorytm Silvera-Pohliga-Hellmana z metodą wielkich i małych kroków (ang. giant step - baby step) Shanksa; por. strony 9, 575-576 drugiego tomu książki Knutha.)

Przykład 4. Znajdźmy logarytm dyskretny z 28 o podstawie 2 w F|₇ za pomocą algorytmu Silvera-Pohliga-Hellmana. (2 jest generatorem grupy F*₇.)

Rozwiązanie. Mamy rozkład 37 - 1 = 2² • 3². Obliczamy 2¹⁹ = -1 (mod 37), skąd otrzymujemy r₂ 0 = 1, r_{2 t} = -1. (Dla p = 2 zawsze (r_{2 /}} = {±1}). Następnie 2^36/3 = 26, 2²*^36/3 = 10 (mod 37), skąd {r_3J} = {1,26,10}. Teraz niech 28 = 2* (mod 37). Najpierw bierzemy p- 2 i znajdujemy x mod 4, które zapisujemy jako x₀ + 2x_v Obliczamy 28^36/2 = 1 (mod 37) i stąd otrzymujemy x„ = 0. Następnie obliczamy 28^36/4 s -1 (mod 37) i stąd x_l = 1, czyli x = 2 (mod 4). Teraz bierzemy p = 3 i znajdujemy x mod 9, które zapisujemy jako x₀ + 3x_r (Oczywiście dla każdego p współczynniki x, są zdefiniowane inaczej). Aby znaleźć x₀ obliczamy 28^36/3 s 26 (mod 37), skąd otrzymujemy x₀ = 1. Następnie obliczamy (28/2)^36/9 = 14⁴ s 10 (mod 37); zatem x_t = 2, czyli x = 1 + 2 • 3 = 7 (mod 9). Pozostaje znaleźć jedyne x mod 36 takie, że x = 2 (mod 4) i x s 7 (mod 9). Jest nim x = 34. Zatem 28 = 2³⁴ w F}₇.