Pseudorandomness
A Socratic walk-through of pseudorandomness — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How can a machine following completely fixed rules produce numbers nobody can predict?
A computer is a machine for doing exactly what it is told, in exactly the same way, every time. Give it the same input twice and it must give you the same output twice, or it is broken. Yet the same machine will happily deal you a shuffled hand of cards or run a Monte Carlo simulation over millions of "random" draws. Those two descriptions seem to contradict each other. Which one is wrong?
Reasoning it through
REASONING #Neither, as it turns out — but only because "random" is doing two different jobs in the sentence, and separating them is the whole exercise.
Consider what we actually want from random numbers in a simulation. Do we want them to be uncaused? Ask what test you could run to find out. You could check that each digit appears about equally often, that pairs and triples are evenly spread, that runs have the right length distribution, that the sequence does not correlate with a shifted copy of itself. Every one of those is a test on the output. None looks at the cause.
That gap is the opening. If the tests only see the sequence, then a deterministic rule producing a sequence that passes all of them is, for those purposes, as good as randomness. This is what a pseudorandom number generator is: a fixed function applied over and over to an internal state, emitting a number each time. The Mersenne Twister, still the default in many languages, keeps a state of 624 words and shuffles it by fixed bit operations; its sequence repeats only after 2^19937 - 1 steps and passes a great many statistical batteries.
Now notice what determinism buys you rather than costs you. Since the whole sequence follows from the starting state — the seed — the same seed always gives the same stream. Is that a defect? For a scientific simulation it is essential: it is the difference between a result someone else can reproduce and an anecdote. Debugging a stochastic program without a fixed seed is close to impossible, because the bug moves each time you look at it.
But now ask the adversarial question. Statistical tests are run by someone who wants to know if the output looks random. What if the person examining the output wants to predict it, and is allowed to think? The Mersenne Twister has no secrets: observe 624 consecutive outputs, undo the final scrambling step on each, and you have reconstructed the entire internal state, from which every future output follows. Nothing was broken. It was never designed to resist that.
So there are two different bars, and this is where the real distinction lies. A statistical generator must produce output that passes tests. A cryptographically secure generator must, in addition, satisfy something much stronger: given every bit it has ever output, it must remain infeasible to predict the next bit better than by guessing — and ideally, given its current state, infeasible to reconstruct what it output before. Generators built for that are typically block ciphers or stream ciphers run forward, and they are what /dev/urandom and the getrandom system call provide.
That leaves one thing unaccounted for. If everything follows from the seed, where does the seed come from? Not from the algorithm, which is why this is the point of failure in practice. A seed must come from outside computation: thermal noise in a circuit, jitter between independent oscillators, interrupt timings, a dedicated hardware instruction. If the seed is guessable, the strongest generator in the world is a fixed sequence.
The documented failures make the point. In 2008 a patch to Debian's OpenSSL removed the code feeding uninitialised memory into the entropy pool, leaving process ID as effectively the only variable input — around 32,767 possibilities. Every key generated on those systems for nearly two years could be reproduced by simply generating all of them. The algorithm was fine.
The analogy
THE ANALOGY #Think of a very long book of digits, printed once and identical in every copy. Tell someone which page and line to start reading from, and the digits they read out will pass any test for randomness you care to apply — but if a second person knows which page you started on, they can read ahead of you. The book is the algorithm, the page number is the seed, and secrecy lives entirely in the page number.
With a real book, a reader who sees a few of your digits still has to search the whole book to find your place, whereas an ordinary statistical generator hands its position away outright once you have seen enough output — a cryptographic generator is the one built so that finding the page from the digits is infeasible.
Clarifying the model
THE MODEL #Three clarifications connect the steps.
Passing statistical tests and resisting an adversary are genuinely different properties, and the first does not imply the second. This is the single most common confusion here: a generator can sail through the NIST and TestU01 batteries and still be trivially predictable, because those suites ask whether the output looks patternless, not whether an analyst who knows the algorithm can invert it.
Second, "unpredictable" is always relative to an adversary's resources. Cryptographic security here is computational, not absolute — the sequence is fully determined, and someone who could search the seed space exhaustively would recover it. The claim is that doing so is infeasible, which is a claim about cost, and one that a large enough advance in hardware or cryptanalysis could weaken.
Third, true randomness is a physical claim, not a mathematical one. Hardware generators sample thermal noise, oscillator jitter, or quantum events like photon paths through a beam splitter. In practice these are rarely used raw — their raw output is usually biased and needs conditioning — so modern systems mix physical entropy into a cryptographic generator and take the output from there, getting physical unpredictability with the speed and uniformity of an algorithm.
A picture of it
THE PICTURE #How to readRead downward as time. The top three messages are the honest path — physical noise seeds the state, and the state emits values while advancing itself by a rule with no randomness in it, which is why the same seed replays identically. The bottom four are the attack, and note the two distinct routes: the dashed arrow from observed outputs works whenever the generator is merely statistical, while the arrow back to the seed works whenever the entropy source was too thin, regardless of how strong the generator is. Both end in the same place.
What became clearer
WHAT CLEARED #A pseudorandom generator is a deterministic machine whose output passes tests for randomness — and determinism is a feature, not an embarrassment, because reproducibility is what makes a simulation checkable. The distinction that matters is which bar the generator was built for: statistical generators like the Mersenne Twister are predictable to anyone who watches long enough, while cryptographic ones are designed so that watching the output tells you nothing about the next bit. And under both sits the same dependence: everything follows from the seed, so a guessable seed is a total failure no algorithm can repair, which is why the seed must come from a physical source outside computation.
Where to go next
ONWARD #- How operating systems collect, estimate and mix entropy before a system has any user activity to draw on.
- Why a virtual machine restored from a snapshot can reissue the same "random" values twice.
Key terms
TERMS #| Term | What it means |
|---|---|
| Seed | the starting internal state from which a generator's entire sequence follows. |
| Period | the number of values a generator emits before its sequence repeats. |
| Mersenne Twister | a widely used statistical generator with period 2^19937 - 1, whose state can be recovered from 624 consecutive outputs. |
| CSPRNG | a cryptographically secure pseudorandom number generator, built so past output does not reveal future output. |
| Entropy source | a physical process, such as thermal noise or oscillator jitter, supplying unpredictability that an algorithm cannot manufacture. |
Every term the collection defines is gathered in the glossary.