Randomness

In information theory, the

word entropy is used to judge how much randomness a string contains

When random numbers are needed for security and cryptography purposes,

then randomness must be unpredictable

Uniformly random means

that all possible values are equally likely.

Non-uniformly random means

that all possible values are not equally likely

One example of True random number generators is to make use of external unpredictable physical phenomena like thermal noise to extract randomness

Extracting randomness from noise is a process that can be slow. For some applications that might need lots of random numbers quickly, it can become a bottleneck

Due to True Random Number Generators (TRNGs) slow nature

OSs often optimize their production of random numbers by using pseudorandom number generators (PRNGs)

Pseudo Random

Too many unknown variables to predict

True Random

Infinite unknown variables

A PRNG needs an initial secret, usually called a seed, that we can obtain

from mixing different entropy sources together and can then produce lots of random numbers quickly

A psuedorandom number generator (PRNG) generates a sequence of random numbers based on a seed. Using the same seed makes the PRNG produce the same sequence of random numbers.

It should be impossible to recover the state using knowledge of the random outputs (the function next is one way). It follows that it should also be impossible from observing the produced random numbers alone to predict future random numbers or to recover previously generated random numbers.

Cryptographically secure PRNGs usually tend to exhibit the following properties:

Deterministic - Using the same seed twice produces the same sequence of random numbers. If you know a seed used by a PRNG, the PRNG should be completely predictable. This is why the construction is called pseudorandom, and this what allows a PRNG to be extremely fast

Indistinguishable from random - In practice, you should not be able to distinguish between a PRNG outputting a random number from a set of possible numbers. Consequently, observing the random numbers generated alone shouldn’t allow anyone to recover the internal state of the PRNG.

A PRNG has forward secrecy if

compromise of a state does not allow recovering previously generated random numbers

A PRNG has backward secrecy if

compromise of a state does not allow predicting future random numbers generated by the PRNG. This is true only once new entropy is produced and injected in the update function after the compromise