Blum-Micali generator

The Blum-Micali generator is a cryptographically secure random number generator developed by Manuel Blum and Silvio Micali .

principle

The generator is based on a generic construction by Blum and Micali, which requires a one-way permutation and a hardcore predicate for . A hardcore predicate is a function with the property that it is practically impossible to calculate from the bit . A sequence is first derived from a random starting value by the rule . The sequence of the random bits is then the sequence . ${\displaystyle f\colon M\to M}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle B\colon M\to \{0,1\}}$ ${\displaystyle f(x)}$ ${\displaystyle B(x)}$ ${\displaystyle x_{0}\in M}$ ${\displaystyle x_{i+1}=f(x_{i})}$ ${\displaystyle B(x_{i})}$

construction

In the concrete construction, the discrete exponentiation is used as a one-way permutation. First a prime number is selected as a parameter , which defines a cyclic group . A random element is selected from this multiplicative group , which is also a generator at the same time (since the probability that the 1 is chosen is negligibly small). The function is now the discrete exponentiation . It is a permutation since both and in lie and is a generator. ${\displaystyle p}$ ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle f(x)=g^{x}\ {\bmod {\ p}}}$ ${\displaystyle x}$ ${\displaystyle g^{x}}$ ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle g}$

Starting from a random one, a sequence is now defined by means of, as described above . The required hardcore predicate for is the function that outputs 1, if , and 0 otherwise. The pseudo-random bit sequence generated by the generator is therefore . ${\displaystyle x_{0}}$ ${\displaystyle f}$ ${\displaystyle x_{i+1}=f(x_{i})=g^{x_{i}}\ {\bmod {\ p}}}$ ${\displaystyle f}$ ${\displaystyle B(x)}$ ${\displaystyle x<{\frac {p-1}{2}}}$ ${\displaystyle B(x_{i})}$

safety

The procedure is provably safe under the assumption that it is difficult to compute discrete logarithms . If an algorithm can with probability better than predict a bit of this sequence , then an algorithm can be constructed from this that can calculate discrete logarithms in the group in probabilistic polynomial time. ${\displaystyle B(x_{i})}$ ${\displaystyle 1/2}$ ${\displaystyle \mathbb {Z} _{p}^{*}}$

Individual evidence

1. ↑ Manuel Blum and Silvio Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits . In: SIAM Journal on Computing . tape 13 , no. 4 , 1984, pp. 850–864 ( with.edu [PDF]).

Web links

• https://crypto.stanford.edu/pbc/notes/crypto/blummicali.html