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.