Blum Blum Shub

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Blum Blum Shubgenerator liczb pseudolosowych (PRNG) postaci:

x_{n+1} = (x_n)^2 \,\operatorname{mod}\, M

gdzie x_n to kolejne stany, a M to iloczyn dwóch dużych liczb pierwszych p i q dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały \operatorname{NWD}(\phi(p-1),\phi(q-1)), a \phi jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów x_n.

Generator ten jest dość powolny, za to bardzo bezpieczny. Przy odpowiednich założeniach, odróżnienie jego wyników od szumu jest równie trudne jak faktoryzacja M, tak więc jest stosowany głównie w kryptografii. Może się zdarzyć, że znaleziony zostanie szybki algorytm faktoryzacji i Blum Blum Shub przestanie być bezpieczny.

Algorytm został po raz pierwszy opisany w pracy:

L. Blum, M. Blum, and M. Shub.
A Simple Unpredictable Pseudo-Random Number Generator.
SIAM Journal on Computing, vol. 15, p. 364-383, May 1986

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]