“Blum–Micali algorithm”的意思、由来-开放百科全书

词条

Blum–Micali algorithm

释义

References
External links

The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.^[1]

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.^[2]

In order for this generator to be secure, the prime number needs to be large enough so that computing discrete logarithms modulo is infeasible.^[1] 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.^[3]

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.^[4]

References

1. ^¹Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 416-417, Wiley; 2nd edition (October 18, 1996), {{ISBN|0471117099}}
2. ^An improved pseudo-random generator based on the discrete logarithm problemR Gennaro - Journal of Cryptology, 2005 - Springer
3. ^Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864. online (pdf)
4. ^Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr, Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction https://arxiv.org/abs/1012.1776

External links

http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml

1 : Cryptographically secure pseudorandom number generators

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。