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. 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.)
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.
# super secret large numbers
x = 3*10**200
y = 4*10**200
seed = 5*10**300
# Find the next prime congruent to 3 mod 4 following x.
p = sympy.nextprime(x)
while (p % 4 != 3):
p = sympy.nextprime(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.
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.