Blum Blum Shub

related topics
{math, number, function}
{system, computer, user}

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:

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

The seed x0 should be an integer that's not 1 or divisible by M.

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 xi value directly (via Euler's Theorem):

where λ is the Carmichael function.

Contents

Security

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 xn 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 x0 by using x − 1 = s and creates the sequence x0, x1, x2, \ldots x5 = 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.

Full article ▸

related documents
Contraction mapping
LALR parser
Normal morphism
Axiom of union
Nearest neighbour algorithm
Complete measure
Best-first search
Sophie Germain prime
Lyapunov fractal
Baire category theorem
Mutual recursion
Characteristic subgroup
Group homomorphism
Composite number
Partition of unity
Linear congruence theorem
Up to
Hamiltonian path problem
Multiple inheritance
Complete category
Category of sets
Permutation group
Sed
Tree structure
AVL tree
Elias delta coding
Zhu Shijie
Identifier
Brun's constant
Product of rings