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
Patterns will always appear no matter how many starting points you have. Always fractal as in nature, there’s a code behind it all, whether it be an algorithm on a computer or a tree.
Think of it this way: Computers just follow the instructions given. The same software, given the same input, will always have the same output.
So whatever a computer will produce will have order to it. This is fundamentally why it’s not possible for a computer to generate truly random data.
Computers work off input and output. For any given input the output should be reproducible and predictable. The problem is that predictable and reproducible are sort of the opposite of random. This means its often time easier to use an unpredictable input and utilize that to give the the appearance of randomness.
Your standard PC has no source of entropy (randomness) built-in. Which for most common usages is o.k. [Here is a simple true-random generator](http://holdenc.altervista.org/avalanche/) if you’re interested in playing with a ‘true’ random generator. You should ensure the circuit is shielded really well so the white noise generator doesn’t pick up stray RF.
Hardware like this would only add a few dollars to the price of a PC. But, for most uses, including games, cryptography, and statistics, having a deterministic and repeatable pseudorandom generator is actually more desirable than a true random generator.
Computers generate random numbers by choosing a seed, and then generating a pseudorandom sequence based on that seed. Pseudorandom sequences have the property that, up to some (very large) threshold, an adversary can observe any amount of the sequence and will not be able to predict the next bit better than random without an inordinate amount of computational work. Cryptographers like these numbers to be something like 2^60 – 2^100 bits until you can start making predictions, and if you try predicting with less data than that it’ll take a similar amount of CPU cycles to make an accurate prediction.
The choice of seed is crucial – if the adversary can predict the seed, they can calculate the stream of random numbers right along with you. The best seeds come from hardware random number generators, which often directly or indirectly make use of quantum noise. Such a seed is unpredictable in principle according to current laws of quantum mechanics (though they can still be biased, so you need to take care that you’re not generating a value which is truly random but has a 90% chance of being within some small range).
More common is to collect a bunch of data from the environment – the timing of network traffic, perhipheral actions, disk actions, etc. These generate data which does have extremely unpredictable components (e.g. which millisecond you click your mouse), but are even more heavily biased, so you need to be careful to keep track of how much randomness you collect before you start doing important cryptographic operations.
Edit: I think for most modern computers it is common to have a hardware random number generator, so the environmental randomness collection is just a legacy ability for older computers.
# Part 1 – Nothing is “truly random”
Well, what does “true random” even mean?
If I flip a coin, is that truly random? If you knew what speed I flipped it at, how high it will go, and at what height it would be caught, you could technically calculate how many times it would flip in the air, and then predict whether it will land heads or tails.
So, in that sense, coin flips aren’t even “truly random”.
But they are “random enough”, because humans basically can’t calculate those things fast enough in order to make a prediction before the coin lands.
And this is true of basically any “random” process. Shuffling cards? If you had a high-speed camera and recorded the shuffle, you could technically figure out the order of the cards. Rolling dice? If you knew the speed of the throw and the rotation, it might be possible to simulate how the dice will tumble and what numbers will show up in the end.
Taken to the extreme, if you were an all-knowing-god and knew how every molecule, atom, and electron was going to move according to the laws of physics, then you could predict anything that would happen. Everything moves according to rules.
So, in some ways, there is no such thing as “random”. And in this sense, true random number generation is impossible.
# Part 2 – How “un-random” are computers?
How computers generate random numbers is called “pseudo-random number generation”. It just uses a math formula: take a number, divide it by a really big number, do all sorts of weird calculations things to it, until the answer is completely unrelated to the original number. That way, we can feed it in a predictable number, and then it gives us a completely unrelated number.
Unless you know what math formula the computer is using. Then you can predict it easily.
And again, sometimes that’s “random enough”, but sometimes it isn’t (especially when there’s a lot of money on the line, like gambling). So can we get any *more* random than that?
Well, yes and no. Computers can only follow instructions — all they can do is take an input, do a fixed set of instructions using the input, then give an output. So, since instructions are fixed and cannot be random, it would seem that computers can’t *really* produce random numbers.
The closest we can get is “randomizing” the input we give it.
One way of doing this is using the internal clock as an input. Computers keep time to a very accurate degree, usually down to the millisecond. If a human pressed a “generate random number” button on the computer, the computer could use the current millisecond that the button was pressed, then the input would, more or less, be completely random, since no one can predict exactly what millisecond the button will be pressed.
The are other ways of providing “random enough” input as well, even without human input. One computer security company [points webcams at lava lamps](https://www.youtube.com/watch?v=1cUUfMeOijg), and uses what the camera sees as input for their computers’ pseudo-random number generators. Some companies [put radioactive materials in their computers](https://www.youtube.com/watch?v=SxP30euw3-0) and use as input the count of the exact amount of radiation emitted at any given time, which is also highly unpredictable.
So while it’s technically true that computers can never produce “truly random” numbers, we’ve already reached the point where they can produce numbers that are basically unpredictable, unless you are an all-knowing god.
True random number generation is a fancy term with little real world use. It has to do with a new event having nothing to do with a previous events. This fundamentally clashes with the ability to control it; if the new event ignores everything you’ve done to set it up, how could you expect it to happen in a way you could detect it?
The power of computers is their predictability. A 3 GHz processor has something like 3 billion calculations happening each second. If even .0001% of those were wrong, that’s 3 thousand wrong numbers every second. Modern computers are expensive because of the effort to eliminate these errors as much as possible.
These combine into computers to being bad at true random number generation, even if it is only a little worse than the rest of our reality (a coin flip is dependent of the physics of the coin launching, traveling through the air, and landing as an example of not being true random). However, us humans are even worse than computers. We perceive a pattern, and we expect it to repeat. This is why true random number generation has so little real world use; even if humans saw true random numbers, we wouldn’t know it to see it. So the “pseudo random numbers” that computer programmers have figured out are good enough for most of us.
Computers use a function that generates numbers random based on an input (a seed). This function is very good, nearly indistinguishable from true randomness for most purposes. The only problem is that seed. Computers seed these generators with junk data from interference detected in devices or in rarer cases a dedicated piece of hardware which specifically collects “noise” which is random in nature through one of various means.
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).
It’s certainly not “virtually impossible”. Most computers have a number of devices that generate essentially random data, such as mice, keyboards, and temperature sensors, and many operating systems have a program that collects this data and uses it to generate “true” random numbers. For example this is what /dev/random generally does on unix-like operating systems. You can also get peripheral devices that use physical processes such as radioactive decay to generate “true” random numbers, and there are even web services that allow you to download “true” random numbers produced by somebody else. However, these options have several big downsides:
* they are extremely slow compared to typical pseudo-random number generators (PRNGs), so aren’t suitable if you need a large number of random values
* because the way these systems operate is quite complicated and unpredictable, it can be quite hard to ensure that they really do what they’re supposed to – in contrast we know exactly how PRNGs such as Mersenne Twister behave and we can be sure that their output consistently satisfies a battery of tests demonstrating that they are random “enough” for many purposes
* “true” random number generators can be affected by subtle hardware failures, for example if a temperature sensor stops working it might degrade the quality of output from /dev/random and you might not even notice
What people often do with scientific simulations is use a PRNG like Mersenne Twister, and use a “true” random source such as /dev/random or the current time to seed it (set its initial value) so it doesn’t produce exactly the same sequence of random numbers every single time.
If you need random numbers for cryptographic purposes such as generating random passwords, that approach isn’t good enough. Instead you need to use a specially designed CSPRNG (cryptographically secure pseudo random number generator) such as Blum Blum Shub – these are slower than normal PRNGs but make it very difficult for someone who has seen several outputs to predict what the next one will be. And you need to be careful how you seed it – using the current time isn’t good enough because people may be able to infer what time the program was run.
Latest Answers