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
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.
Latest Answers