Ever wondered how machines come up with random numbers? Unlike the real world, where we can roll dice and the number that comes up has an equal chance as any of the other numbers coming up, with a computer it’s not so easy.
Random number generators (RNGs) are what machines use to come up with a number randomly as if we were rolling a die. It’s a process whereby, given a set of numbers (e.g. 1-30), each number has an equal probability of occurring next.
But a machine needs to start somewhere. It needs to be given a function to process. In effect, RNGs only simulate randomness over probability distributions.
There are various types of RNGs that exist, and in today’s piece, we’ll cover some of these in a little more detail – to show just how difficult it is for machines to produce random numbers.
Pseudo Random Number Generators
The most common types of random number generators used in computing are pseudo random number generators.
Pseudo random number generators start with a seed number, then, using a given function, such as x(n+1) = 5 x (n) + 4 (mod 7), generate a sequence of numbers from there, using the result from the initial seed for each “turn”.
However, given the same seed number, the sequence generated thereafter will always be the same. For simple purposes, this seed could be the exact time. This is particularly handy when testing if a pseudo RNG actually works as expected, from the programmatic end.
While this works on the surface and can appear random, if the function to generate the sequence is known, the seed can be determined, and the state (where the sequence is at) can be determined, then a human can determine the outcome of the “dice roll.”
This is just a simple pseudo random number generator (PRNG).
Software libraries have pseudo random number generators that are a lot more complex than this, but still, if a seed is known, as well as a guessed state, a number can be determined.
The concept of entropy in PRNGs
Entropy is a computing term used to describe randomness, collected from some input. This may be from variance in keystrokes over a number of computers, mouse movements, noise collected from the outside of a machine, the level of radiation in the air, etc. If you combine a number of different unrelated entropy sources, this can make it even more random. Sources of entropy that are difficult to manipulate or determine make good seeds for RNGs.
Cryptographic Random Number Generators
Cryptographically secure pseudo random number generators (CSPRNGs) are those which hold up to two different tests:
- Given the first X bits in a series, there is no polynomial-time function that can predict X+1 more than 50% of the time.
- If the state of the function is known, then the previous numbers in the string cannot be recreated.
CSPRNGs are PRNGs with added provisos to make them more secure from outside attackers.
These are important, you guessed it, in the field of cryptography. If we are looking to create a secure hash then it cannot be able to be reverse engineered by an attacker.
This makes CSPRNGs far more secure than PRNGs by their nature.
The trouble with software-based PRNGs
This can make software-defined pseudo random number generators open to misuse, if they’re in the hands of a programmer who might use them for nefarious reasons, or who can easily alter the code without it necessarily being picked up by an untrained eye.
Such is the case of Eddie Tipton, the security man behind the Multi-State Lottery Association’s random number generator code. While the code itself measured a long number of radiation in the air as a seed (which is near impossible to ‘guess’ if you aren’t at the source), then passed the seed through one of the most popular pseudo random number generator algorithms, the Mersenne Twister (used in Excel, C++, Ruby, MATLAB, and more), Eddie had coded in a diversion to the RNG, which helped him determine the outcome of the lottery on various dates, and no one has noticed the code changes.
Hardware Random Number Generators
Another type of random number generator is the hardware random number generator (HRNG). These are also known as true random number generators as they determine a number from hardware instead of a computer algorithm.
They generally measure some physical phenomena in the form of noise (e.g. atmospheric noise) and convert it to an electrical signal, often just 0 or 1. By sampling enough times, a long enough series of random bits is generated to make a number between X and Y.
These types of random number generators are often used in cryptography, as well as in gambling.
Quantum Random Number Generators
A new type of random number generator has emerged recently; the quantum random number generator. Quantum mechanics is a field of physics based on electrons, photons, and atoms, that truly behave randomly.
Thus this type of physics serves as a clever base for random number generation. While un-hackable quantum random number generators are far too expensive to commercialize just at the minute, this will likely be the next step forward in true random number generation.
What else?
This is just the smallest taste of what is available in terms of random number generation, how it is developed, and whether results are both truly random, as well as impossible to exploit by attackers. In a world where cyberattackers are constantly on the lookout for backdoors, exploits, and even brute force methods to hack into cryptographically secure systems, random number generators need to be as true to their name as possible: truly random.
As systems evolve, we will see more secure RNGs rolled out for important purposes, such as the lottery, as well as systems with a promise of being secure. Quantum random number generators look to be the best bet for future applications – so long as they’re fast, secure, and affordable.