9346692686

i (p — 1) (q — 1) były względnie pierwsze. Można to sprawdzić szukając największego wspólnego dzielnika. Jeśli jest on różny niż 1 to wybór należy powtórzyć. Kolejną czynnością jest znalezienie takiego d, by

e • d = 1 mod (p — 1) (q — 1)

Teraz następuje dosyć niespodziewany krok. Obliczamy iloczyn n = p • q i pozbywamy się liczb p i q tak, by nie pozostał po nich ślad i by nie wpadły one w ręce adwersarzom. Para liczb [e, n] jest kluczem publicznym, a [d, n] kluczem prywatnym. Tak przygotowanymi kluczami szyfrowane mogą być liczby m < n. Tekst jawny w postaci ciągu bitów, traktowany jako zapis binarny liczby m, nie może więc być zbyt długi, aby spełniony był powyższy warunek. Szyfrowanie odbywa się zgodnie z fomułą

c = i?[e,n] (^m) = mod n

a odszyfrowanie

m = D[d,n\ (^c) ⁼ c^d mod n

Obliczenia prowadzące do uzyskania klucza prywatnego możnaby odtworzyć, gdyby udało się dokonać rozkładu liczby n na czynniki. Zadanie to należy do klasy problemów NP, lecz nie wiadomo, czy jest to problem NP-zupełny. Pomimo tego znane obecnie algorytmy rozkładu na czynniki pierwsze wymagają dość długich czasów obliczeń. Niemniej jednak w 1996 roku udało się dokonać rozkładu losowo wygenerowanej liczby o długości 512 bitów.

4 Generatory kryptograficznie bezpieczne

Dobrą metodą generowania sekwencji bitów pseudolosowych jest zastosowanie do tego celu algorytmów szyfrujących. Widzieliśmy takie potępowanie w generatorze ANSI X9.17, który używa schematu DES E-D-E. Poniżej przedstawiamy generatory najwyższej jakości dla kryptografii — generatory kryptograficznie bezpieczne opisywane wcześniej. Poniższe algorytmy opierają się na pomysłach wprowadzonych w szyfrowaniu RS A.

4.1 Generator RS A

Generator ten służy do tworzenia ciągu zi, Z2,... bitów pseudolosowych o długości l. Aby przygotować się do działania powinniśmy, podobnie jak w RSA, wybrać dwie duże liczby pseudolosowe. Dalej obliczamy iloczyn n = p ■ q i losujemy e tak, by e i (p — l)(ę — 1) były względnie pierwsze. Jako zarodek dla naszego generatora wybieramy xq z przedziału [l,n — 1]. Natępnie w pętli od 1 do l obliczamy

Xi — mod n

Najmniej znaczący bit rozwinięcia binarnego liczby Xi jest i-tym bitem generowanego ciągu.