Blum Blum Shub

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al., 1986).

Blum Blum Shub takes the form:

$x_{n+1} = x_n^2 \bmod M$

where M=pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from x_n+1; the output is commonly either the bit parity of x_n+1 or one or more of the least significant bits of x_n+1.

The seed x₀ should be an integer that's not 1 or co-prime to M (i.e. p and q are not factors of x₀).

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).

An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any x_i value directly (via Euler's Theorem):

$x_i = \left( x_0^{2^i \bmod \lambda(M)} \right) \bmod M$

where λ is the Carmichael function. (Here we have $\lambda(M) = \lambda(p\cdot q) = \operatorname{lcm}(p-1, q-1)$).

Security

The generator is not appropriate for use in simulations, only for cryptography, because it is very slow. However, there is a proof reducing its security to the computational difficulty of the Quadratic residuosity problem. Since the only known way to solve that problem requires factoring the modulus, the difficulty of Integer factorization is generally regarded as providing security. When the primes are chosen appropriately, and O(log log M) lower-order bits of each x_n are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as factoring M.

If integer factorization is difficult (as is suspected) then B.B.S. with large M should have an output free from any nonrandom patterns that can be discovered with any reasonable amount of calculation. Thus it appears to be as secure as other encryption technologies tied to the factorization problem, such as RSA encryption.

Example

Let p = 11, q = 19 and s = 3 (where s is the seed.) We can expect to get a large cycle length for those small numbers, because gcd(φ(p − 1),φ(q − 1)) = 2. The generator starts to evaluate x₀ by using x _{− 1} = s and creates the sequence x₀, x₁, x₂, $\ldots$ x₅ = 9, 81, 82, 36, 42, 92. The following table shows the output (in bits) for the different bit selection methods used to determine the output.

Even parity bit	Odd parity bit	Least significant bit
0 1 1 0 1 0	1 0 0 1 0 1	1 1 0 0 0 0

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.
• Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. Available as PDF.
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF and Gzipped Postscript.

External links

• GMPBBS (archived 2009-05-24 at the Wayback Machine), a GPL'ed GMP-based implementation of Blum Blum Shub by Mark Rossmiller. Retrieved 2011-09-05.
• An implementation in Java (Note: this is not a correct implementation because it does not enforce p and q as being prime; it just enforces p congruent to 3 (mod 4).)
• Randomness tests