A cryptographically secure random number generator

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 x₀ between 1 and M and relatively prime to M. Now for n > 0, set

x_n+1 = x_n^2 mod M

and return the least significant bit of x_n+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.)

Python implementation

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 x and y, the code below finds primes p and 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 x, y, and 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 generateN = 100000 x = seedbit_string = ""for _ in range(N): x = x*x % M b = x % 2 bit_string += str(b)

Testing

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 Blums

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.