Why is it that true random number generation is virtually impossible for current computers to achieve? I build and fix computer hardware as part of my living, but I still don’t understand this. Please explain?
In: 3
Let’s say you want to argue that current computers *can* achieve random numbers. You take a practical engineering approach: You sit down at a standard desktop or laptop PC and write a program in your favorite programming language.
– Your program has a subroutine that activates whenever the mouse moves a single pixel.
– In the subroutine, you record how many microseconds have passed since the system was booted.
– You wait until the user’s been moving the mouse for a while and you have enough measurements [1], let’s say 1000.
– You combine the measurements with a [cryptographic hash function](https://en.wikipedia.org/wiki/Cryptographic_hash_function) that the best mathematicians and security experts all agree effectively mashes up all the information into a fixed-size chunk of 256 bits.
“That’s a very nice program,” I say, “But true random number generation can’t be done on a computer.”
“What do you mean?” you exclaim. “This is an excellent engineering solution for any practical application that needs random numbers!”
“It is,” I say, “But you haven’t shown that random number generation can be done on a computer.”
“The numbers pass all the statistical tests for randomness!” you say.
“They do,” I say, “But you haven’t shown the random number generation can be done on a computer.”
“I consulted several cryptography textbooks, Wikipedia articles, and so on!” you say. “This is well-regarded as a standard method for generating random numbers!”
“Those are fine textbooks,” I say, “The authors do know what they’re talking about. But you haven’t shown the random number generation can be done on a computer.”
You further protest: “For the past five years I’ve had $100 million dollars in Bitcoin secured by random numbers picked by this code! Any hacker who could guess the random numbers could anonymously steal all those Bitcoins — And no one has, for five whole years!”
“Yes,” I say, “Your code definitely produces random numbers that are effectively impossible for a hacker to guess, but you still haven’t shown that random number generation can be done on a computer.”
Finally, exasperated, you throw up your hands. “What do you want of me?” you ask.
“Well,” I say, “For starters, you didn’t use a computer.”
“WHAT!?” you shout. “I wrote my program in a popular, widely used programming language, running on a standard, off-the-shelf PC!”
“A computer,” I kindly explain, “is a device that takes input, runs some code on it, and produces output –”
“I know that,” you mutter.
” — and it always produces the *same* output, every time you run the same code on the same input,” I continue.
“But my program doesn’t do that!” you say. “It’s different every time! That’s basically the *whole point* of a random number generating program!”
“Yes,” I say, encouragingly. “What makes it different every time?”
You think for a moment, then highlight a couple lines in your program’s code. “It’s right here,” you say, “The program reads the timer and the mouse movements.”
“And are those part of the input?” I ask, grinning demonically, as I’ve now sprung my trap and you can’t escape.
– If you say “No, they’re not part of the input,” I say “Well then, your PC technically isn’t a computer, because you run the same code on the same input multiple times and it gives you different output each time.”
– If you say “Yes, they’re part of the input,” I say “Well then, your program technically didn’t generate random numbers, your program just manipulated numbers that came from somewhere else — the mouse and timer. And the numbers technically aren’t ‘truly random’ at all, they’re measurements that could be replicated if the user moved the mouse the exact same way.”
Basically, in order for me to defend the claim “true random number generation is virtually impossible for current computers to achieve,” I have to play tricky games with language, where I very narrowly define what is meant by “true random number” and “computer” in such a way as to disqualify your program on a technicality — Even though, for all practical engineering purposes, your program does in fact generate random numbers on a computer.
[1] How much is “enough” is its own rabbit hole and I don’t want to get into it here. But here’s a [somewhat related video](https://www.youtube.com/watch?v=v68zYyaEmEA).
Latest Answers