Random Number Generator (BBS-Generator)

Hi folks,

the BBS-Generator can be downloaded in the publications section now.

Blum Blum Shub (B.B.S.) is a pseudo random number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub in 1986. The algorithm uses a product n which is the product of two large primes p and q. At each step of the algorithm, some output is derived from x_n. Commonly, the output is either the bit parity of x_n or one or more of the least significant bits of x_n.

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

The generator is not appropriate for use in simulations, only for cryptography, because it is very slow. 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) lower-order bits of each x_n 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 B.B.S. with large M will have an output free from any nonrandom patterns that can be discovered with any reasonable amount of calculation. This makes it as secure as other encryption technologies tied to the factorization problem, such as RSA encryption.