Cryptographically secure pseudorandom number generator

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also referred to as a cryptographic random number generator (CRNG).

Most cryptographic applications require random numbers, for example:

The "quality" of the randomness required for these applications varies. For example, creating a nonce in some protocols needs only uniqueness. On the other hand, the generation of a master key requires a higher quality, such as more entropy. And in the case of one-time pads, the information-theoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy, and thus just any kind of pseudorandom number generator is insufficient.

Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high-quality source, generally the operating system's randomness API. However, unexpected correlations have been found in several such ostensibly independent processes. From an information-theoretic point of view, the amount of randomness, the entropy that can be generated, is equal to the entropy provided by the system. But sometimes, in practical situations, numbers are needed with more randomness than the available entropy can provide. Also, the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can "stretch" the available entropy over more bits.

The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups:

Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts:

In the asymptotic setting, a family of deterministic polynomial time computable functions ${\displaystyle G_{k}\colon \{{\texttt {0}},{\texttt {1}}\}^{k}\to \{{\texttt {0}},{\texttt {1}}\}^{p(k)}}$ for some polynomial p, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input (${\displaystyle p(k)>k}$ for any k), and if its output is computationally indistinguishable from true randomness, i.e. for any probabilistic polynomial time algorithm A, which outputs 1 or 0 as a distinguisher,

for some negligible function ${\displaystyle \mu }$. (The notation ${\displaystyle x\gets X}$ means that x is chosen uniformly at random from the set X.)