Blum Blum Shub
Blum Blum Shub 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
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 and not 1 or 0.
The two primes, p and q, should both be congruent to 3, and should be safe primes with a small gcd/2, .
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly :
where is the Carmichael function..
Security
There is a proof reducing its security to the computational difficulty of factoring. When the primes are chosen appropriately, and O 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.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.
Example
Let, and . 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 for the different bit selection methods used to determine the output.
The following is a Python implementation that does check for primality.
import sympy
def blum_blum_shub -> list:
"""Blum Blum Shub is a pseudorandom number generator."""
assert p1 % 4 3
assert p2 % 4 3
assert sympy.isprime
assert sympy.isprime
n = p1 * p2
numbers =
for _ in range:
seed = % n
if seed in numbers:
return numbers
numbers.append
return numbers
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 are not checked.
"Returns the number of 1-valued bits in the integer-encoded BITS."
))
"Returns the even parity bit of the integer-encoded BITS."
)
"Returns the least significant bit of the integer-encoded BITS."
)
)
"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, and returning three values:
the number x,
the even parity bit of the number,
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."
) ;; x0 = seed
#'
;; x = x^2 mod M
)
;; Compute the random bit based on x.
;; Update the state such that x becomes the new x.
)))))
;; Print the exemplary outputs.
bbs))
)))