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 that is derived from Michael O. Rabin's oblivious transfer mapping.

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 is co-prime to M (i.e. p and q are not factors of x₀) and not 1 or 0.

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 $\lambda$ is the Carmichael function. (Here we have $\lambda(M) = \lambda(p\cdot q) = \operatorname{lcm}(p-1, q-1)$).

Security

There is a proof reducing its security to the computational difficulty of solving the Quadratic residuosity problem. 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 solving the Quadratic residuosity problem modulo M.

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 ${\rm gcd}(\varphi(p-1), \varphi(q-1))=2$. The generator starts to evaluate $x_0$ by using $x_{-1}=s$ and creates the sequence $x_0$, $x_1$, $x_2$, $\ldots$ $x_5$ = 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

General

• available as PDF and Gzipped Postscript

External links

• GMPBBS , a GPL'ed GMP-based implementation of Blum Blum Shub in C by Maria Morisot with implementation in Java also.
• An implementation in Java
• Randomness tests