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

${\displaystyle 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):

${\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {\lambda }}(M)}\right){\bmod {M}}}$,

where ${\displaystyle \lambda }$ is the Carmichael function. (Here we have ${\displaystyle \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 ${\displaystyle p=11}$, ${\displaystyle q=23}$ and ${\displaystyle s=3}$ (where ${\displaystyle s}$ is the seed). We can expect to get a large cycle length for those small numbers, because ${\displaystyle {\rm {gcd}}((p-3)/2,(q-3)/2)=2}$. The generator starts to evaluate ${\displaystyle x_{0}}$ by using ${\displaystyle x_{-1}=s}$ and creates the sequence ${\displaystyle x_{0}}$, ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle \ldots }$${\displaystyle 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.

importsympydefblum_blum_shub(p1,p2,seed,iterations):assertp1%4==3assertp2%4==3assertsympy.isprime(p1//2)assertsympy.isprime(p2//2)n=p1*p2numbers=[]for_inrange(iterations):seed=(seed**2)%nifseedinnumbers:print(f"The RNG has fallen into a loop at {len(numbers)} steps")returnnumbersnumbers.append(seed)returnnumbersprint(blum_blum_shub(11,23,3,100))

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.

(defunget-number-of-1-bits(bits)"Returns the number of 1-valued bits in the integer-encoded BITS."(declare(type(integer0*)bits))(the(integer0*)(logcountbits)))(defunget-even-parity-bit(bits)"Returns the even parity bit of the integer-encoded BITS."(declare(type(integer0*)bits))(thebit(mod(get-number-of-1-bitsbits)2)))(defunget-least-significant-bit(bits)"Returns the least significant bit of the integer-encoded BITS."(declare(type(integer0*)bits))(thebit(ldb(byte10)bits)))(defunmake-blum-blum-shub(&key(p11)(q23)(s3))"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(integer0*)pqs))(let((M(*pq));; M  = p * q(x[n]s));; x0 = seed(declare(type(integer0*)Mx[n]))#'(lambda();; x[n+1] = x[n]^2 mod M(let((x[n+1](mod(*x[n]x[n])M)))(declare(type(integer0*)x[n+1]));; Compute the random bit(s) based on x[n+1].(let((even-parity-bit(get-even-parity-bitx[n+1]))(least-significant-bit(get-least-significant-bitx[n+1])))(declare(typebiteven-parity-bit))(declare(typebitleast-significant-bit));; Update the state such that x[n+1] becomes the new x[n].(setfx[n]x[n+1])(valuesx[n+1]even-parity-bitleast-significant-bit))))));; Print the exemplary outputs.(let((bbs(make-blum-blum-shub:p11:q23:s3)))(declare(type(function()(values(integer0*)bitbit))bbs))(formatT"~&Keys: E = even parity, L = least significant")(formatT"~2%")(formatT"~&x[n+1] | E | L")(formatT"~&--------------")(looprepeat6do(multiple-value-bind(x[n+1]even-parity-bitleast-significant-bit)(funcallbbs)(declare(type(integer0*)x[n+1]))(declare(typebiteven-parity-bit))(declare(typebitleast-significant-bit))(formatT"~&~6d | ~d | ~d"x[n+1]even-parity-bitleast-significant-bit))))

References

Citations

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. Lecture Notes in Computer Science. Vol. 3796. pp. 355–375. doi:10.1007/11586821_24. ISBN   978-3-540-30276-6.

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

• GMPBBS, a C-language implementation by Mark Rossmiller
• BlumBlumShub, a Java-language implementation by Mark Rossmiller
• An implementation in Java
• Randomness tests