Blum Blum Shub
|
|
Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986).
BBS takes the form:
- xn+1 = (xn)2 mod M
where M=pq is the product of two large primes p and q, and the output is the least significant bit of xn, which is the same thing as the parity of xn. Alternatively, the output can be several of the least significant bits of xn.
The two primes, p and q, should both be congruent to 3 mod 4 (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p-1), φ(q-1)) should be small (this makes the cycle length large).
Security
The generator is not appropriate for use in simulations, only for cryptography, because it is not very fast. However, it has an unusually strong security proof, which relates the quality of the generator to the computational difficulty of integer factorization. When the primes are chosen appropriately, and O(log log M) bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random will be at least as difficult as factoring M.
If integer factorization is difficult (as is suspected) then BBS with large M will have an output free from any nonrandom patterns that can be discovered with any reasonable amount of calculation. However, it is theoretically possible that a fast algorithm for factoring will someday be found, so BBS is not yet guaranteed to be secure.
References
- Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
- Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", August 1999. 21 page PDF file (http://crypto.junod.info/bbs.pdf)
- Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF (http://daimi.au.dk/~mg/mamian/random-bits.pdf) and Gzipped Postscript (http://daimi.au.dk/~mg/mamian/random-bits.ps.gz).
External links
- GMPBBS (http://firefly.is-a-geek.org/gmpbbs/) - a GMP-based implementation of Blum Blum Shub.pl:Blum Blum Shub