Cryptography Part 4: Random numbers

Executive summary: There are no random numbers; only random number generators.

If that sentence made perfect sense to you, feel free to skip this installment. Otherwise, read on.

In the previous post, we saw a cryptosystem whose security was entirely based on a coin toss. But why use a coin? Why not just get together and agree that when I say one thing I will mean another?

Well, two reasons. First, humans are notoriously predictable; our minds are just not very good at being random. Second, ad-hoc cryptosystems are impossible to analyze mathematically, and mathematical certainty is our goal (even if we will not quite get there).

Randomness lies at the heart of all cryptography, both in theory and in practice. So we want to be able to think about it clearly.

But wait a minute. What is a “random number”, exactly? A single number is just itself, so what does it even mean to call it “random”? After a coin lands, it is either heads or tails, neither of which seems particularly “random” on its own. And so on.

The solution to the dilemma is this: “Random” refers not to values, but to means of generating them. It is not the outcome of the coin toss that is random, but the process of flipping it.

So, when you see the phrase “random number generator”, do not read it as “random-number generator” (i.e., a generator of random numbers). Read it as “random number-generator” (i.e., a random generator of numbers). The randomness is in the generator, not in the numbers.

Even experts often speak loosely here, using phrases like “source of random bits” when what they really mean is “random source of bits”. Don’t let them confuse you. Or themselves.

Aside: If you show this post to a mathematician and they mumble something about “Martin-Löf randomness” or “Kolmogorov complexity”, do me a favor and smack them upside the head. This is cryptography, which means computers, which means our world consists only of integers like God intended.

Aside #2: If you show this post to a physicist and they mumble something about “Schrödinger”, or to an engineer and they mumble something about “thermal noise” or “reverse-biased diodes”, do me a favor and smack them upside the head twice. Actually, make it three times for the engineer. To win against someone who can outsmart us, we need very precise reasoning, which means totally separating the math from the real world. We have to bring them back together eventually, of course, but leaving them connected during the process will only make our thinking fuzzy and our proofs non-existent. (This is the problem with the Linux /dev/random design, by the way… But that is a topic for another time.)

The mathematical language of randomness is called probability theory. In that language, my summary statement would read: There are no random events; only random distributions. In basic cryptography, the formal proofs tend to be tedious but straightforward, relying only on very elementary probability theory. We shall see how far I can get in this series without it.

More next time.