Blum Blum Shub (B.B.S.) is a
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
proposed in 1986 by
Lenore Blum
Lenore Carol Blum (née Epstein, born December 18, 1942) is an American computer scientist and mathematician who has made pioneering contributions to the theories of real number computation, cryptography, and pseudorandom number generation. She ...
,
Manuel Blum
Manuel Blum (born 26 April 1938) is a Venezuelan-American 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 ...
and
Michael Shub
Michael Ira Shub (born August 17, 1943) is an American mathematician who has done research into dynamical systems and the complexity of real number algorithms.
Biography
Shub obtained his Ph.D. degree at the University of California, Berkele ...
that is derived from
Michael O. Rabin
Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award.
Biography Early life and education
Rabin was born in 1931 in ...
's one-way function.
__TOC__
Blum Blum Shub takes the form
:
,
where ''M'' = ''pq'' is the product of two large
primes
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''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
A seed is an embryonic plant enclosed in a protective outer covering, along with a food reserve. The formation of the seed is a part of the process of reproduction in seed plants, the spermatophytes, including the gymnosperm and angiospe ...
''x''
0 should be an integer that is co-prime to ''M'' (i.e. ''p'' and ''q'' are not factors of ''x''
0) and not 1 or 0.
The two primes, ''p'' and ''q'', should both be
congruent
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
to 3 (mod 4) (this guarantees that each
quadratic residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic no ...
has one
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
which is also a quadratic residue), and should be
safe prime
In number theory, a prime number ''p'' is a if 2''p'' + 1 is also prime. The number 2''p'' + 1 associated with a Sophie Germain prime is called a . For example, 11 is a Sophie Germain prime and 2 × 11 +  ...
s with a small
gcd((''p-3'')''/2'', (''q-3'')''/2'') (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
In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if and are coprime positive integers, and \varphi(n) is Euler's totient function, then raised to the power \varphi(n) is congru ...
):
:
,
where
is the
Carmichael function
In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that
:a^m \equiv 1 \pmod
holds for every integer coprime to . In algebraic terms, is the exponent of the multip ...
. (Here we have
).
Security
There is a proof reducing its security to the
computational difficulty of factoring. When the primes are chosen appropriately, and
''O''(
log
Log most often refers to:
* Trunk (botany), the stem and main wooden axis of a tree, called logs when cut
** Logging, cutting down trees for logs
** Firewood, logs used for fuel
** Lumber or timber, converted from wood logs
* Logarithm, in mathe ...
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 The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
modulo ''M''.
Example
Let
,
and
(where
is the seed). We can expect to get a large cycle length for those small numbers, because
.
The generator starts to evaluate
by using
and creates the sequence
,
,
,
= 9, 81, 236, 36, 31, 202. The following table shows the output (in bits) for the different bit selection methods used to determine the output.
The following
Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fro ...
implementation provides a simple demonstration of the generator, in particular regarding the three bit selection methods. It is important to note that the requirements imposed upon the parameters ''p'', ''q'' and ''s'' (seed) are not checked.
(defun get-number-of-1-bits (bits)
"Returns the number of 1-valued bits in the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the (integer 0 *) (logcount bits)))
(defun get-even-parity-bit (bits)
"Returns the even parity bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (mod (get-number-of-1-bits bits) 2)))
(defun get-least-significant-bit (bits)
"Returns the least significant bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (ldb (byte 1 0) bits)))
(defun make-blum-blum-shub (&key (p 11) (q 23) (s 3))
"Returns a function of no arguments which represents a simple
Blum-Blum-Shub pseudorandom number generator, configured to use the
generator parameters P, Q, and S (seed), and returning three values:
(1) the number x +1
(2) the even parity bit of the number,
(3) the least significant bit of the number.
---
Please note that the parameters P, Q, and S are not checked in
accordance to the conditions described in the article."
(declare (type (integer 0 *) p q s))
(let ((M (* p q)) ;; M = p * q
(x s)) ;; x0 = seed
(declare (type (integer 0 *) M x )
#'(lambda ()
;; x +1= x 2 mod M
(let ((x +1(mod (* x x M)))
(declare (type (integer 0 *) x +1)
;; Compute the random bit(s) based on x +1
(let ((even-parity-bit (get-even-parity-bit x +1)
(least-significant-bit (get-least-significant-bit x +1))
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
;; Update the state such that x +1becomes the new x
(setf x x +1
(values x +1 even-parity-bit
least-significant-bit))))))
;; Print the exemplary outputs.
(let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3)))
(declare (type (function () (values (integer 0 *) bit bit)) bbs))
(format T "~&Keys: E = even parity, L = least significant")
(format T "~2%")
(format T "~&x +1, E , L")
(format T "~&--------------")
(loop repeat 6 do
(multiple-value-bind (x +1even-parity-bit least-significant-bit)
(funcall bbs)
(declare (type (integer 0 *) x +1)
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
(format T "~&~6d , ~d , ~d"
x +1even-parity-bit least-significant-bit))))
References
Citations
Sources
*
*
*
{{refend
External links
GMPBBS, a C-language implementation by Mark RossmillerBlumBlumShub, a Java-language implementation by Mark RossmillerAn implementation in JavaRandomness tests
Pseudorandom number generators
Cryptographically secure pseudorandom number generators