Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. ... Lenore Blum received her Ph. ... Manuel Blum (born 26 April 1938 in Caracas, Venezuela) is a computer scientist who received the Turing Award in 1995 In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking. // Biography Blum attended MIT, where he received his bachelors...

BBS takes the form:

x_n+1 = (x_n)² mod 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; the output is commonly either the bit parity of x_n or one or more of the least significant bits of x_n. Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, a prime number (or a prime) is a positive integer that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... A parity bit is a binary digit that indicates whether the number of bits with value of one in a given set of bits is even or odd. ...

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). In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ... In mathematics, a number q is called a quadratic residue modulo p if there exists an integer x such that: Otherwise, q is called a quadratic non-residue. ... In mathematics, a square root of a number x is a number r such that , or in words, a number r whose square (the result of multiplying the number by itself) is x. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... The first thousand values of φ(n) In number theory, the totient (n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...

An interesting characteristic of the BBS generator is the possibility to calculate any x_i value directly:

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) 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. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ... Above is the graph plots of Logarithms to various bases: is to base e, is to base 10, and is to base 1. ...

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. This makes it as secure as other encryption technologies tied to the factorization problem, such as RSA encryption. In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In cryptology, RSA is an algorithm for public-key encryption. ...

Example

Let p=11, q=19 and s=3. 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₂, ... x₅= 9, 81, 82, 36, 42, 92. If the bit parity is used to determine the output, then the output bits are 0 1 1 0 1 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 - a GMP-based implementation of Blum Blum Shub.
• An implementation in Java
• Randomness tests