Random Numbers 🎲

Back

Recently I wrote about RSA and how to generate prime numbers. The logical next step is asking how random numbers are created. It's a trait I have of keep asking "how does it work" until I can reduce it to the smallest, simplest parts I can understand. One aspect of improvement for me is being able to push this process further and further. This is by no means a review of random number generation in general, just my random remarks about randomness.

When we talk about random number generators (RNG), we actually talk about pseudo-randomness because the output is produced deterministically from an initial seed value and is only an approximation for a random series of numbers. However, it can serve as an advantage, being able to reproduce a series of numbers, given the same seed.

One important family of pseudo RNG (PRNG) is called "Linear Congruential Generator" and is defined by x <= (a * x + b) mod m. For example, take a=2 b=6 m=11 and you get x=0,6,7,9,2,10,4,3,1,8,...

Another algorithm is called Mersenne Twister:

Mersenne Twister

It's very popular and is being used in many languages and frameworks, e.g. it's used by the random module in Python. It has a period of 2^19937 - 1 which means in principle it starts repeating the cycle only after 2^19937-1 queries.

One way of testing the randomness of the output is using the Diehard tests which comprised of small statistical tests where one compares a sample with known analytical results:

Diehard Randomness Tests

Cryptographic PRNG

Cryptographic-secure random number generators (CSPRNG) are a collection of methods to generate random numbers suitable to be used in cryptography. In addition to the randomness of output, they have these two additional properties:

1. The n+1 number should not be deduced easily from the previous n numbers, where easily means polynomial time with higher than 50% probability.

2. If an RNG state is exposed (e.g. a state of a hashing function) it should not be possible to recover previous random numbers using that knowledge. This is an example of forward secrecy, which means a key revealed in the future should not expose past secrets.

In other words, if someone is able to detect some numbers you previously generated, she will not be able to use that to break future secure messages. Additionally, if she is able to get hold of your CSPRNG and examine its state, she can not infer anything about previous generated numbers, thus breaking past secure messages. So both future and past are protected when the CSPRNG or its outputs are exposed.

For example, the previously mentioned Mersenne Twister algorithm is not suitable for cryptography, failing the 1st condition: observing 624 predictions is enough to deduce its state and can be used to predict the next numbers in the series. Which means using the Python random module for cryptography is a bad idea; instead, use the secrets module, designed for this purpose (on Python > 3.5).

Some examples of CSPRNG:

ChaCha20, used in Linux

Fortuna, used in FreeBSD and Apple OSs

The way they work is by using a cypher and acting on an input using a key. The output is converted into random numbers. What is the input? What is the key? Why are the past and future protected? Answers maybe next time.

For comments, questions and complaints please reach me on my @email.