Blum-Micali algorithm

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

The Blum-Micali algorithm is used as a pseudo random generator in cryptography. The algorithm gets its security from the difficulty of computing discrete logarithms.^[1]

$\mathbf{Let\ } g \mathbf{\ be\ prime}$
$\mathbf{Let\ } p \ \mathbf{be\ an\ odd\ prime}$

$X_{i+1} = g^{x_j}\mbox{ } mod\mbox{ } p$

It can be used to set bits since the output of the generator is either 0 or 1.

$\mbox{If } X_i < \frac{p-1}{2} \mbox{ is true, then return } 1 \mbox{ otherwise } 0$

In order for this generator to be secure, the prime number p needs to be large enough so that computing discrete logarithms $m o d p$ is infeasible.^[1]

[edit] References

^ ^a ^b Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 416-417, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099