A random number generator can have excellent statistical properties and yet not be suited for use in cryptography. I’ve written a few posts to demonstrate this. For example, this post shows how to discover the seed of an LCG random number generator.
This is not possible with a secure random number generator (CSPRNG). Or more precisely, it is not practical. It may be theoretically possible, but doing so requires solving a problem currently believed to be extremely time-consuming. (Lots of weasel words here. That’s the nature of cryptography. Security often depends on the assumption that a problem is as hard to solve as experts generally believe it is.)
Blum Blum Shub algorithm
The Blum Blum Shub algorithm for generating random bits rests on the assumption that a certain number theory problem, the quadratic residuosity problem, is hard to solve. The algorithm is simple. Let M = pq where p and q are large primes, both congruent to 3 mod 4. Pick a seed x0 between 1 and M and relatively prime to M. Now for n > 0, set
xn+1 = xn² mod M
and return the least significant bit of xn+1.
Yes, that’s a lot of work for just one bit. If you don’t need cryptographic security, there are much faster random number generators. In fact, even if you do need cryptographic quality, there are much faster generators. BBS was one of the first CSPRNGs, and so it was initially a proof of concept rather than something meant to be pushed into production. Even so, BBS is practical if you don’t need much output, e.g. if you’re using it to generate a 256-bit key.
Here’s some Python code to illustrate using the generator. The code is intended to be clear, not efficient.
Given two large (not necessarily prime) numbers
y, the code below finds primes
q for the algorithm and checks that the seed is OK to use.
import sympy # super secret large numbers x = 3*10**200 y = 4*10**200 seed = 5*10**300 def next_usable_prime(x): # Find the next prime congruent to 3 mod 4 following x. p = sympy.nextprime(x) while (p % 4 != 3): p = sympy.nextprime(p) return p p = next_usable_prime(x) q = next_usable_prime(y) M = p*q assert(1 < seed < M) assert(seed % p != 0) assert(seed % q != 0)
There’s a little bit of a chicken-and-egg problem here: how do you pick
seed? Well, you could use a cryptographically secure random number generator ….
Now let’s generate a long string of bits:
# Number of random numbers to generate N = 100000 x = seed bit_string = "" for _ in range(N): x = x*x % M b = x % 2 bit_string += str(b)
I did not test the output thoroughly; I didn’t use anything like DIEHARDER or PractRand as in previous posts, but just ran a couple simple tests described here. Other people have, and it passes as expected.
First I look at the balance of 0’s and 1’s.
Number of 1's: 50171 Expected: 49683.7 to 50316.2
Then the longest run. (See this post for a discussion of expected run length.)
Run length: 16 Expected: 12.7 to 18.5
Nothing unusual here.
The first two authors of Blum Blum Shub are Lenore and Manuel Blum. The third author is Michael Shub.
I had a chance to meet the Blums at the Heidelberg Laureate Forum in 2014. Manuel Blum gave a talk that year on mental cryptography that I blogged about here and followed up here. He and his wife Lenore were very pleasant to talk with.