Blum Blum Shub
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
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 is co-prime to M (i.e. p and q are not factors of x0) 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 should be safe primes 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 xi value directly (via Euler's theorem):
where is the Carmichael function. (Here we have ).
There is a proof reducing its security to the computational difficulty of factoring. 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 solving the Quadratic residuosity problem modulo M.
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.
|Parity bit||Least significant bit|
|0 1 1 0 1 0||1 1 0 0 1 0|
The following Common Lisp 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) "Counts and returns the number of 1-valued bits in the BITS." (declare (integer bits)) (loop for bit-index from 0 below (integer-length bits) when (logbitp bit-index bits) sum 1)) (defun get-even-parity-bit (number) (declare (integer number)) (mod (get-number-of-1-bits number) 2)) (defun get-least-significant-bit (number) (declare (integer number)) (ldb (byte 1 0) number)) (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 even parity bit of the number, (2) the least significant bit of the number, (3) the number x[n+1]. --- Please note that the parameters P, Q, and S are not checked in accordance to the conditions described in the article." (let ((M (* p q)) ;; M = p * q (x[n] s)) ;; x0 = seed (declare (integer p q M x[n])) #'(lambda () ;; x[n+1] = x[n]^2 mod M (let ((x[n+1] (mod (* x[n] x[n]) M))) (declare (integer x[n+1])) ;; Compute the random bit(s) based on x[n+1]. (let ((even-parity-bit (get-even-parity-bit x[n+1])) (least-significant-bit (get-least-significant-bit x[n+1]))) ;; Update the state such that x[n+1] becomes the new x[n]. (setf x[n] x[n+1]) (values even-parity-bit least-significant-bit x[n+1])))))) ;; Print the exemplary outputs. (let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3))) (format T "~&Keys: E = even parity, ~ L = least significant") (format T "~2%") (format T "~&x[n+1] | E | L") (format T "~&------------------") (loop repeat 6 do (multiple-value-bind (even-parity-bit odd-parity-bit least-significant-bit x[n+1]) (funcall bbs) (format T "~&~6d | ~d | ~d" x[n+1] even-parity-bit least-significant-bit))))
- Blum, Lenore; Blum, Manuel; Shub, Mike (1982). "Comparison of Two Pseudo-Random Number Generators". Advances in Cryptology: Proceedings of CRYPTO '82. Plenum: 61–78. Cite journal requires
- Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (December 2004). "About Random Bits". CiteSeerX 10.1.1.90.3779. Cite journal requires
|journal=(help) available as PDF and gzipped Postscript