Pseudorandom Generators

True randomness is surprisingly hard to come by. Computers are deterministic machines — feed them the same input and they always give the same output. Yet almost everything secure, from your encrypted messages to the lottery, needs a steady supply of unpredictable bits.

The fix is a pseudorandom generator (PRG): a small, deterministic program that takes a short truly-random seed — say 128 coin flips — and stretches it into a much longer stream of bits. The stream isn't really random; it's completely determined by the seed. And yet, to anyone who doesn't know the seed, it looks perfectly random.

That's the whole trick, and it's the foundation of every stream cipher: keep one short secret, and you can generate a keystream as long as the message you want to hide.

Pick a short seed below and press Expand. A tiny deterministic generator stretches your few starting bits into a long stream, and three simple randomness tests check whether the output looks like fair coin flips: roughly half ones, no obvious short-run bias, and no easy correlation between neighboring bits.

<p class="hint">{{hint}}</p>
<div class="row">
  <label for="seed">{{seed_label}}</label>
  <input id="seed" type="text" value="42" maxlength="12" inputmode="numeric">
  <button id="flip" type="button" class="ghost">{{flip_btn}}</button>
</div>
<div class="btns">
  <button id="expand" type="button">{{expand_btn}}</button>
  <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div class="stream" id="stream">{{stream_initial}}</div>
<div class="tests" id="tests"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .9rem; font-weight: 600; color: #1d3557; }
input { font: 600 14px ui-monospace, monospace; padding: .4rem .6rem; width: 9rem;
        border: 1px solid #cdd9e3; border-radius: 8px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stream { font: 600 13px ui-monospace, monospace; line-height: 1.7; letter-spacing: 1px;
          background: #f4f7fa; border: 1px solid #e1e8ef; border-radius: 8px; padding: .7rem;
          word-break: break-all; color: #1d3557; min-height: 3.5em; }
.stream b { color: #e63946; }
.tests { margin-top: .7rem; display: grid; gap: .4rem; }
.test { display: flex; align-items: center; gap: .5rem; font-size: .9rem; }
.badge { font: 700 12px system-ui, sans-serif; padding: .15rem .5rem; border-radius: 999px; min-width: 4.2rem; text-align: center; }
.badge.pass { background: #d7f0df; color: #0a7d33; }
.badge.fail { background: #fcdcdf; color: #c92f3c; }

// Code not found

Two things to notice. First, the same seed always produces the same stream — that's what lets two people who share a seed generate the identical keystream to encrypt and decrypt. Second, flip a single bit of the seed and the entire stream changes unrecognizably, yet it still passes the tests. The output is fully determined, but it behaves like randomness — and that is exactly what "pseudorandom" means.

The simple tests in the demo are easy to pass — and easy to fool. The real definition of a secure PRG is far stronger and far subtler.

• The bar is "no efficient test". A generator is cryptographically secure if no efficient algorithm (running in polynomial time) can tell its output apart from a truly random string with better than negligible advantage. This is called computational indistinguishability: the stream may be perfectly predictable in principle, but no feasible computation can exploit that.
• It rests on hardness, not magic. Such generators are built from one-way functions — operations easy to compute but believed hard to invert. The landmark result of Håstad, Impagliazzo, Levin and Luby (1999) proved that a secure PRG exists if and only if a one-way function exists.
• Status: conjectured, not proven. We have strong candidates (built on factoring, discrete logarithms, or hardened block ciphers like AES), but no one has proven that any secure PRG truly exists. Such a proof would settle that one-way functions exist — which would immediately imply P ≠ NP, one of the great open problems.
• The cost of distinguishing. Breaking a good PRG means either learning the seed or finding a statistical edge — and for the best designs, the only known attack is brute force over all possible seeds, which is astronomically expensive.

So a pseudorandom generator lives in a fascinating place: provably useful the moment any one-way function exists, yet its unconditional existence is tangled up with the deepest unsolved question in computer science.

Once you can manufacture convincing randomness from a tiny seed, it shows up nearly everywhere:

• Stream ciphers: the canonical use. XOR your message with a PRG-generated keystream and you have encryption; the receiver, sharing the seed (the key), regenerates the same keystream to decrypt.
• Keys, nonces and salts: the cryptographically secure RNGs in your operating system and browser are PRGs, periodically reseeded from real entropy, that feed every key and session token.
• Simulation and sampling: Monte Carlo methods, randomized algorithms and games all need fast, reproducible pseudorandom streams — and reproducibility (same seed → same run) is a feature, not a bug.
• Derandomization: in theory, strong PRGs let us replace true randomness in algorithms with cheap pseudorandomness, a central idea linking randomness and computational hardness.

The same hardness that makes a generator secure is studied directly in factoring and discrete logarithms — the very problems many PRGs are built upon.

A pseudorandom generator does something almost paradoxical: it takes a handful of genuinely random bits and produces an endless stream that acts random to anyone without the seed, even though it's fully determined. That single capability is what turns a short key into a long keystream and makes practical encryption possible.

But peel back the construction and you reach bedrock uncertainty. We can build a secure generator the instant one-way functions exist — yet proving they exist would crack P vs NP wide open. Until then, the randomness protecting your messages is a brilliant, well-tested bet against the limits of computation.