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^[1] 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 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 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 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

There is a proof reducing its security to the computational difficulty of factoring.^[1] 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 solving the quadratic residuosity problem modulo M.

The performance of the BBS random-number generator depends on the size of the modulus M and the number of bits per iteration j. While lowering M or increasing j makes the algorithm faster, doing so also reduces the security. A 2005 paper gives concrete, as opposed to asymptotic, security proof of BBS, for a given M and j. The result can also be used to guide choices of the two numbers by balancing expected security against computational cost.^[2]

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 is a Python implementation that does check for primality.

<syntaxhighlight lang="python3"> import sympy def blum_blum_shub(p1, p2, seed, iterations):

 assert p1 % 4 == 3
 assert p2 % 4 == 3
 assert sympy.isprime(p1//2)
 assert sympy.isprime(p2//2)
 n = p1 * p2
 numbers = []
 for _ in range(iterations):
   seed = (seed ** 2) % n
   if seed in numbers:
     print(f"The RNG has fallen into a loop at {len(numbers)} steps")
     return numbers
   numbers.append(seed)
 return numbers

print(blum_blum_shub(11, 23, 3, 100)) </syntaxhighlight>

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.

<syntaxhighlight lang="lisp"> (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[n+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[n] s))            ;; x0 = seed
   (declare (type (integer 0 *) M x[n]))
   #'(lambda ()
       ;; x[n+1] = x[n]^2 mod M
       (let ((x[n+1] (mod (* x[n] x[n]) M)))
         (declare (type (integer 0 *) 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])))
           (declare (type bit even-parity-bit))
           (declare (type bit least-significant-bit))
           ;; Update the state such that x[n+1] becomes the new x[n].
           (setf x[n] x[n+1])
           (values x[n+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[n+1] | E | L")
 (format T "~&--------------")
 (loop repeat 6 do
   (multiple-value-bind (x[n+1] even-parity-bit least-significant-bit)
       (funcall bbs)
     (declare (type (integer 0 *) x[n+1]))
     (declare (type bit           even-parity-bit))
     (declare (type bit           least-significant-bit))
     (format T "~&~6d | ~d | ~d"
               x[n+1] even-parity-bit least-significant-bit))))

</syntaxhighlight>

References

Citations

^ ^1.0 ^1.1 Blum, Blum & Shub 1986, pp. 364–383.
^ Sidorenko, Andrey; Schoenmakers, Berry (2005). "Concrete Security of the Blum-Blum-Shub Pseudorandom Generator". Cryptography and Coding. 3796: 355–375. doi:10.1007/11586821_24.

Sources

Blum, Lenore; Blum, Manuel; Shub, Michael (1983). "Comparison of Two Pseudo-Random Number Generators". Advances in Cryptology. Boston, MA: Springer US. pp. 61–78. doi:10.1007/978-1-4757-0602-4_6. ISBN 978-1-4757-0604-8.
Blum, L.; Blum, M.; Shub, M. (1986). "A Simple Unpredictable Pseudo-Random Number Generator" (PDF). SIAM Journal on Computing. 15 (2). Society for Industrial & Applied Mathematics (SIAM): 364–383. doi:10.1137/0215025. ISSN 0097-5397. Archived (PDF) from the original on 2021-08-14.
Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (December 2004), About Random Bits (PDF), CiteSeerX 10.1.1.90.3779, archived (PDF) from the original on 2016-03-31

External links

[FOOTNOTEBlumBlumShub1986364–383-1] 1.0 ^1.1 Blum, Blum & Shub 1986, pp. 364–383.

[2] Sidorenko, Andrey; Schoenmakers, Berry (2005). "Concrete Security of the Blum-Blum-Shub Pseudorandom Generator". Cryptography and Coding. 3796: 355–375. doi:10.1007/11586821_24.

[1]

[2]