73916 Str069

134    4. KIuck publiczne

(słowo ..niezależne” oznacza tu, że wyznacznik macierzy współczynników ja_eł) jest względnie pierwszy z q - I ), będziemy mogli rozwiązać ten układ modulo q I i wyznaczymy wartości niewiadomych. (Por. omówienie metod algebry liniowej modulo N = (/ - I w podrozdziale 3.2). W ten sposób kończymy pierwszą fazę naszego algorytmu. Obliczenie wstępne dało nam dużą „bazę danych”, mianowicie iogarytmy dyskretne wszystkich wielomianów tf(,V)e /?, które umożliwią nam obliczanie dowolnych interesujących nas loga-rytmów dyskretnych.

Zanim przejdziemy do opisu drugiej fazy algorytmu, zajmiemy się problemem wyboru liczby m, której nie wybraliśmy wyraźnie wtedy, kiedy określaliśmy zbiór B c F_p[A'] jako zbiór wszystkich unormowanych wielomianów nierozkładalnych stopnia nie większego niż m. Wielkość h zbioru B rośnie gwałtownie wraz ze wzrostem m. Jeśli na przykład liczba m jest pierwsza, to widzieliśmy już (wniosek do twierdzenia 2.1.8), że istnieje (p^m — p)/m unormowanych wielomianów' nierozkładalnych stopnia m. Ponieważ musimy znaleźć co najmniej h różnych wielomianów c(X), które dadzą nam układ h niezależnych równań liniowych z h niewiadomymi ind (a(X))_t a następnie musimy ten układ rozwiązać, więc liczba h nie powinna być zbyt duża, a zatem liczba m też nie powinna być zbyt duża. Z drugiej strony, jeśli liczba m jest mała, to mała jest szansa na to, by „typowy” wielomian unormowany có^xc(A0 stopnia nie większego niż n — 1 rozkładał się na iloczyn wielomianów a{X) stopnia nie większego niż m\ bardziej prawdopodobne jest to, że będzie on miał co najmniej jeden czynnik nierozkładalny stopnia większego niż m. Zatem, jeśli liczba m jest mała, to znalezienie choć jednej liczby losowej t takiej, że wielomian c(X) = b{X)¹ (mod f{X)) ma wymagany rozkład na czynniki, zajmie nam nadmiernie wiele czasu. A więc liczba m nie może być zbyt mała, ale musi być sporo mniejsza od rt. Optymalny wybór m - zależny oczywiście od p i n- wymaga długiej analizy prawdopodobieństw i oszacowań czasu, wykraczających poza zakres tej książki. Na przykład dla p = 2 i n = 127 najlepszym wyborem okazuje się być m— 17 (w tym przypadku h — 16510). Wartość q = 2¹²⁷ jest bardzo popularna, gdyż |F*in| = 2¹²⁷ — 1 jest liczbą pierwszą Mersenne’a.

Powrócimy teraz do naszego algorytmu i opiszemy końcową fazę obliczeń. Założymy, że y(X)e1t* jest elementem, którego logarytm dyskretny chcemy obliczyć oraz że pierwsza faza algorytmu dała nam wartości ind(a(K)) dla wszystkich a{X)eB. Znów wybieramy liczbę losową t zawartą między 1 i ą - 2, a następnie obliczamy y_t = yb\ tzn. wyznaczamy jedyny wielomian yi(.Y)eF_p[A'], stopnia mniejszego niż n, spełniający kongruencję JiW = yiX)b{X)¹ (mod f{X)). Podobnie jak w pierwszej fazie algorytmu, najpierw sprawdzamy, czy y₁ (X) rozkłada się na iloczyn pewnej stałej y₀ i potęg wielomianów a(X) należących do B. Jeśli wielomian y nie rozkłada się na taki iloczyn, to szukamy innej liczby losowej t tak długo, aż w końcu znajdziemy liczbę t taką, źe y_t(X) = y₀J] _a(X)*\ Wtedy mamy już wszystko, co jest

oefl

nam potrzebne, gdyż ind(y) = indfyj - /, z definicji y_v\ ponadto ind^) =

s: ind(y₀) + ind(fl(Jf))» przy czym wszystkie wartości po prawej stronie są 7jianc. To kończy opis algorytmu.

Należy wspomnieć o tym, że w przypadku p = 2 poprawiona metoda autorstwa D. Coppersmitha spowodowała znaczne przyspieszenie procesu znajdowania logarytmu dyskretnego. Z tego powodu system kryptograficzny oparty na problemie logarytmu dyskretnego w grupie FJ, nie może być uważany za bezpieczny, chyba że liczba n jest rzędu 1000. Pomimo to ciała F₂* pozostają popularne, gdyż użycie ich jest związane z efektywnymi algorytmami. Dobry przegląd tych metod (w którym omówiono wyniki znane do roku 1985) znajdzie czytelnik w artykule A. Odlyzki (zob. bibliografię na końcu tego podrozdziału).

Jeśli q = f jest potęgą nieparzystej liczby pierwszej, mającą k cyfr dwójkowych, to okazuje się, że czas potrzebny do rozwiązania problemu loga-rytmu dyskretnego w FJ jest, z grubsza rzecz biorąc, porównywalny z czasem potrzebnym do rozkładu fc-bitowęj liczby na czynniki pierwsze. To znaczy, że z doświadczalnego punktu widzenia, problem logarytmu dyskretnego wydaje się być tak samo trudny jak problem faktoryzacji (chociaż nikt nie udowodnił żadnego twierdzenia na ten temat). W rzeczywistości, kiedy będziemy w następnym rozdziale omawiać metody faktoryzacji i oszacowania czasu tych metod, zobaczymy, że jedna z podstawowych metod rozkładania dużych liczb na czynniki wykazuje uderzające podobieństwo do algorytmu znajdowania logarytmu dyskretnego opartego na obliczaniu indeksu.

W obecnej chwili jest więc za wcześnie, by powiedzieć, czy w przyszłości zostanie udowodnione, że systemy kryptograficzne z publicznym kluczem, takie jak RSA (oparte na trudnościach związanych z rozkładem na czynniki), lub systemy oparte na problemie logarytmu dyskretnego są bezpieczne.

Ćwiczenia

Uwaga: Możesz próbować rozwiązywać ćwiczenia 4, 6, 7(c) i 8 tylko wtedy, kiedy masz dostęp do komputera z programami arytmetyki wysokiej precyzji. (Naprawdę potrzebny jest program obliczający a^b mod m dla bardzo dużych liczb całkowitych a, b i m; pamiętajmy, że a^-1 mod p może być obliczone jako a^p“².) ¹

1

Jeśli często wykonujesz dużo działań arytmetycznych w pewnym ustalonym, niezbyt dużym, ciele skończonym F_f, to oszczędzisz sporo czasu, tworząc „tablicę logarytmów” dla tego ciała. Inaczej mówiąc, wybierz generator g grupy FJ i sporządź tablicę, której pierwsze dwie kolumny będą zawierały wszystkie pary n, g" dla n od 1 do q - 1. W trzeciej i czwartej kolumnie wypisz wszystkie pary a, log, a. To znaczy, w trzeciej kolumnie wypisz wszystkie elementy FJ w pewnym dogodnym porządku, a następnie przejrzyj pierwsze dwie kolumny i dopisz każdą liczbę n w czwartej kolumnie przy odpowiadającym jej elemencie a, równym g". Jeśli na przykład dla