Randomness plays a dominant role in our daily lives. From the most trivial decision to the most relevant events, all of them seem to be imbued with a layer of unpredictability much of the time. Very often, we want to reduce this component of unpredictability; although, many times, we want just the opposite: Areas such as cryptography depend directly on the adversary’s inability to predict a message exchanged between two parties. In cases like these, unpredictability is an indispensable and often scarce resource.
The scarcity of pure sources of randomness stems from a beautiful coincidence: random phenomena and their study may well be the area of mathematics most closely related to physical phenomena. Without relying on physical systems, it is impossible to generate randomness by purely mathematical processes: we need a source of uncertainty coming from some natural process for, once processed, feeding the mathematical algorithms that make use of it.
However, although it is indeed not possible to generate randomness by mathematical processes, there is a long history of attempts to develop algorithms that, while not random in principle, do try to mimic (and in some cases very convincingly) natural sources of randomness. These algorithms, generally known as “pseudo-random number generators,” try to reproduce some of the characteristics of real random numbers, which are:
Fulfilling this last property is absolutely impossible for a pseudo-generator, given that its results are produced from an algorithmic process that is affected by its previous history and will affect future results. Thus, given a sufficiently long sequence of random numbers from a pseudo-generator, one could, in theory, reverse the random number generation process. Therefore, this would compromise the (apparent) unpredictability of the pseudo-generator.
To avoid using inadequate pseudo-random number generators, these are generally studied from two different perspectives, mainly related to this hypothesis of uncorrelation and independence:
The best existing pseudo-generators, which are a must in cryptographic environments, are those that simultaneously show no statistically notable correlation and whose computational difficulty makes it impractical to attempt to invert the generation algorithm.
In any case, the best guarantee of success in environments requiring unpredictability is to have a high-quality and high-speed source of entropy. In this way, it is the physical processes that come to the rescue of cryptographic applications, providing them with the randomness they need to function correctly.
For generating pseudo-random numbers, an algorithm makes some transformation on a given state of the generator. Both a new state and the pseudo-random number are returned from this transformation.
These PRNGs are used when so much randomness is needed that the entropy sources themselves cannot cope with the demand. They are also widely used in simulation environments.
Many different types of algorithms generate pseudo-random sequences. Still, mainly they can be divided between those which are cryptographically secure (providing the best guarantees to date) and those which aren’t.