The Blum–Micali algorithm is a
cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely kno ...
. The algorithm gets its security from the difficulty of computing
discrete logarithms
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...
.
[Bruce Schneier, ''Applied Cryptography: Protocols, Algorithms, and Source Code in C'', pages 416-417, Wiley; 2nd edition (October 18, 1996), ]
Let
be an odd prime, and let
be a
primitive root modulo
. Let
be a seed, and let
.
The
th output of the algorithm is 1 if
.
Otherwise the output is 0. This is equivalent to using one bit of
as your random number. It has been shown that
bits of
can be used if solving the discrete log problem is infeasible even for exponents with as few as
bits.
In order for this generator to be secure, the prime number
needs to be large enough so that computing discrete logarithms modulo
is infeasible.
To be more precise, any method that predicts the numbers generated will lead to an algorithm that solves the discrete logarithm problem for that prime.
There is a paper discussing possible examples of the quantum permanent compromise attack to the Blum–Micali construction. This attacks illustrate how a previous attack to the Blum–Micali generator can be extended to the whole Blum–Micali construction, including the
Blum Blum Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ...
and
Kaliski
__NOTOC__
Kalisz County ( pl, powiat kaliski) is a unit of territorial administration and local government (powiat) in Greater Poland Voivodeship, west-central Poland. It came into being on January 1, 1999, as a result of the Polish local governme ...
generators.
References
External links
* https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml
Cryptographically secure pseudorandom number generators
{{crypto-stub