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*_{0} between 1 and *M* and relatively prime to *M*. Now for *n* > 0, set

*x*_{n+1} = *x*_{n}² 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 generate
N = 100000
x = seed
bit_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.