# Blum Blum Shub

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.

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 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):

$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

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.

## Example

Let $p=11$ , $q=23$ and $s=3$ (where $s$ is the seed). We can expect to get a large cycle length for those small numbers, because ${\rm {gcd}}((p-3)/2,(q-3)/2)=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, 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))))