Blum Blum Shub

From Wikipedia, the free encyclopedia

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub.^[1]

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

The generator is very slow. However, there is a proof reducing its security to the computational difficulty of the computing modular square roots, a problem whose difficulty is equivalent to factoring. 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.

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

↑ Blum, Lenore; Blum, Manuel; Shub, Mike (1 May 1986). "A Simple Unpredictable Pseudo-Random Number Generator". SIAM Journal on Computing 15 (2): 364–383. doi:10.1137/0215025. Cite uses deprecated parameters (help)

General

Blum, Lenore; Blum, Manuel; Shub, Mike (1982). Comparison of Two Pseudo-Random Number Generators. Advances in Cryptology: Proceedings of CRYPTO '82. Plenum. pp. 61––78. Cite uses deprecated parameters (help)
Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (December 2004). About Random Bits. Cite uses deprecated parameters (help) 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
Randomness tests

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.