9346692687

Generator RS A działa dosyć powoli: utworzenie jednego bitu wymaga jednego podnoszenia do potęgi modulo n. Jeśli n jest wystarczająco dużą liczbą, można zwiększyć jego wydajność w każdym kroku ekstrachując nie jeden, a j bitów Xi, gdzie j = c • log log n, a c jest stałą.

Rozwiązaniem o większej wydajności opartym właściwie na tej samej zasadzie jest algorytm Micaliego - Schnorra. Podobnie jak w generatorze RSA wybieramy p i q oraz obliczamy n = pq. Niech N będzie ilością bitów w rozwinięciu binarnym n. Tak jak w RSA wybiermy e nakładąjc jednak dodatkowy warunek, by 80e < N. Dalej, niech k będzie największą liczbą całkowitą nie większą niż N (1 — 2/e) i r = N — k. Wybieramy losowy zarodek xq o rozwinięciu długości r. Aby wygenerować pseudolosowy ciąg o długości Z • k powtarzamy w pętli od 1 do Z powtarzamy następujące operacje:

—    Hi — mod n;

—    do X{ wstawiamy r najbardziej znaczących bitów yi\

—    za Zi podstawiamy k najmniej znaczących bitów Xi.

Wyjściowa sekwencja powstaje ze sklejenia z\ || 22    • || ^zi-

Algorytm ten jest kryptograficznie bezpieczny pod warunkiem, że rozkład x^e mod n dla r-bitowych sekwencji jest nierozróżnialny od jednorodnego rozkładu liczb całkowitych na przedziale [0,n — 1] przez algorytmy o złożoności wielomianowej. Niestety jest to założenie mocniejsze niż praktyczna nierozwią-zywalność problemu RSA.

4.2 Generator BBS

Dalszą modyfikacją generatora RSA w celu zwiększenia jego efektywności jest generator Blum-Blum-Shub (BBS). Jest to pewne uproszczenie, w którym podnoszenie do potęgi e zastępujemy podnoszeniem do kwadratu, co zajmuje o wiele mniej czasu. I tak kompletny algorytm wygląda następująco:

—    Wybieramy duże, tajne liczby pierwsze p, q, z których każda przystaje do 3 modulo 4 (p,q = 3 mod 4). Obliczamy n — pq.

—    Wybieramy losowy zarodek s z przedziału [l,n — 1] taki, by NWD(s,n)= 1 i obliczamy xq = s² mod n.

—    W pętli obliczamy Xi — xf__l mod n.

Wynikiem jest ciąg najmniej znaczących bitów Podobnie jak w przypadku generatora RSA można jeszcze zwiększyć wydajność ekstrachując więcej niż jeden mniej znaczący bit.

5 Podsumowanie

Zastosowanie kryptografii w życiu codziennym począwszy od sieci bankomatów i telefonii komórkowej na kodach startowych rakiet balistycznych kończąc, może uzmysłowić nam konieczność poznania bliżej metod szyfrowania. Biorąc