Blum–Micali algorithm

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

Principle

The generator is based on a generic construction of Blum and Micali, a Einwegpermutation and a hardcore predicate for needed. A hardcore predicate is a function with the property that it is virtually impossible to calculate from the bit. From a random start value is a result first derived by the rule. The sequence of random bits is then the result.

Construction

In the concrete construction is used as Einwegpermutation the discrete exponentiation. When parameters a prime number is first selected, which defines a cyclic group. Of the multiplicative group of a random element is chosen, which is a generator at the same time ( because the probability that 1 is selected, is negligibly small ). The function is now the discrete exponentiation. She is a permutation, lie there as well as in and a generator.

Starting from a random will now be described by means of a sequence as defined above. The required hardcore predicate for the function that returns 1 if, and 0 otherwise The pseudo- random bit sequence generated by the generator is so.

Security

The method is provably secure under the assumption that it is difficult to compute discrete logarithms. If an algorithm a bit this episode with probability better than can predict, so it can be constructed an algorithm that can compute the group in probabilistic polynomial time discrete logarithms.