How do computers generate random numbers?

To my thinking, what is more important is that you don’t fool yourself about the amount of entropy from one source, or among sources. Two entropy sources that are dependent variables may be good separately but not together. Like the timings of keystrokes and network packets may be affected by the scheduler, or the fact that you are typing into a remote editor session which is bouncing ACKs back, or auto saving every time you hit enter or change focus.

There is important terminology in the world of all this stuff though, particularly "not all random numbers are the same" can confuse someone who then begins learning more about it.

Artistic license is good.

My last paragraph basically amounts to if any of the axioms used for constructing any crypto are false then all cryptography based on them is breakable and this is not specific to any implementation. If they're not false, proper implementation works, and implementation details are more important. In principle, just using a provably random TRNG to generate a seed and then using a properly implemented CSPRNG to generate numbers from the seed, as long as the seed is provably destroyed the numbers are indistinguishable from random numbers. This is not true of "randomness" generated by the human brain. "You'd rather not bet on that being true" is exactly right, theoretically a human could produce a truly random number, but the likelihood is very low that no predictable external influence went into that process compared to using noise generated by the chaotic universe.

You can not. Randomness is a property of the procedure used to generate it, not the number.

There are other comments in this thread that get into some nitty gritty details of this that I don't pretend to be an expert on.

Sure, asking whether or not any single number is random does not really make sense (although I suppose if we have enough digits to look at then something similar to Benford's law might apply to their distribution). But the point being made was about humans as random number generators and the distribution of numbers they produce. It's like comparing individual molecules to statistical physics.

It can't disprove it either. It can only say if it is "likely to be random" or "appears to be random".

A perfectly random source could generate a string of 1M zeros, and most statistical tests would fail it. But that is not proof that it isn't random. A second test would likely not generate all zeros and would likely pass.

Yeah, "Cryptographically secure" just means "according to currently published literature, no one has yet found a correlation between bits that leads to a faster than a 2^128 attack on the key"

Tomorrow, it might be broken. But AES has been around for a while, so its unlikely to break tomorrow. IIRC, the furthest anyone has gotten is like breaking 4-rounds of AES (out of 8).

Yes, that's somewhat important for "smaller" 64-bit or 128-bit states.

But at 512-bit states, the "average loop" is 2^256 (birthday paradox), so no one really cares at that point. We can see that Mersenne Twister is overprovisioned: 19937 bits of state and all 2^19937 visited in some order.

But in practice, 64-bits worth of cycles (18-quintrillion) is sufficient for single-threaded simulations, and 128-bits is sufficient for multithreaded simulations.

> In light of the above, is it possible to prove this (through some property of AES)?

Yeah. AES is a block cipher that maps 128 bit blocks into "encrypted" 128-bit blocks. The reverse-AES (I'll call it unAES in this post) provides us the 1-to-1 unmapping as well.

Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key) == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all possible 2^128 blocks)

By the pidgeon-hole principle, we have 2^128 blocks associated with AES-encrypted blocks (named AES(0, key), AES(1, key)... AES(2^128-1, key)), and 2^128 blocks associated with our plaintexts (0, 1, 2, 3... 2^128-1). The only way all 2^128 map to each other is through a 1-to-1 bijection.

Or in another way: AES(X, key) == AES(Y, key) if-and-only-if X == Y. This is because deAES(AES(X, key), key) == deAES(AES(Y, key), key) if-and-only if X == Y.

Done. We know the AES-crypto method therefore only "loops" after 2^128, exploring the entire state-space. 2^128 possible inputs, 2^128 possible outputs, pigeonhole principle. QED, done.

I think they would take a series of 0's and 1's..

0010001110100100011

...and map that into 0's and 1's based on the changes, not the numbers themselves. Maybe like 00 or 11 mapped to 0 and 10 or 01 mapped to 1? I can't recall.

It gives you a continuously-varying output voltage. To get random numbers, you have to sample the output (presumably using a clock of some kind), and compare the sample with some reference (e.g. using a comparator).

How often you can sample depends on the bandwidth of the analogue noise-source. You still need to debias, and probably whiten as well. That's digital circuitry, and it's hard to make analogue and digital circuitry play nicely together on the same circuit board; the digital part tends to influence the analogue part through the power lines.

maybe you know the word I need to search for, it was something like using every two or three bits and anding or xoring them or whatever to magically erase any bias present in the shot noise, yielding a perfectly uniform distribution of 1s and 0s.

I'd like to turn this into a circuit-building curriculum if I can find all the pieces again.

If the CPU is going to detect and subvert your soft PRNG, it can do that whether you use RDRAND or not.

Well, the output from AES is by definition indistinguishable from randomness, unless you have the key. So to test a TRNG, you need access to the input to the whitener. Intel doeesn't provide that access. So the hardware might be producing a continuous stream of zeroes, and you'd never know from examining the output of the whitener.

I believe Intel chips with RDRAND have been inspected using electron microscopes, and no flaw has been found in the hardware (I think it's two free-running oscillators whose outputs are sampled and XORed).