Blum–Micali Algorithm

The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.Bruce Schneier, ''Applied Cryptography: Protocols, Algorithms, and Source Code in C'', pages 416-417, Wiley; 2nd edition (October 18, 1996),

Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a seed, and let

$x_ = g^\ \bmod$.

The $i$th output of the algorithm is 1 if
$x_i \leq \frac$.
Otherwise the output is 0. This is equivalent to using one bit of $x_i$ as your random number. It has been shown that $n - c - 1$ bits of $x_i$ can be used if solving the discrete log problem is infeasible even for exponents with as few as $c$ bits.

In order for this generator to be secure, the prime number $p$ needs to be large enough so that computing discrete logarithms modulo $p$ 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 and Kaliski 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