Cryptography/Random number generation

The generation of random numbers is essential to cryptography. One of the most difficult aspect of cryptographic algorithms is in depending on or generating, true random information. This is problematic, since there is no known way to produce true random data, and most especially no way to do so on a finite state machine such as a computer.

There are generally two kinds of random number generators: non-deterministic random number generators, sometimes called "true random number generators" (TRNG), and deterministic random number generators, also called pseudorandom number generators (PRNG).

Many high-quality cryptosystems use both -- a hardware random-number generator to periodically re-seed a deterministic random number generator.

Quantum mechanical theory suggests that some physical processes are inherently random (though collecting and using such data presents problems), but deterministic mechanisms, such as computers, cannot be. Any stochastic process (generation of random numbers) simulated on a computer, however, is not truly random, but only pseudorandom.

Within the limitations of pseudorandom generators, any quality pseudorandom number generator must:

• have a uniform distribution of values, in all dimensions
• have no detectable pattern, ie generate numbers with no correlations between successive numbers
• have a very long cycle length
• have no, or easily avoidable, weak initial conditions which produce patterns or short cycles

Methods of Pseudorandom Number Generation

Keeping in mind that we are dealing with pseudorandom number generation (i.e. numbers generated from a finite state machine, as a computer), there are various ways to randomly generate numbers.

In C and C++ the function rand() returns a pseudo-random integer between zero and RAND_MAX (internally defined constant), defined with the srand() function; otherwise it will use the default seed and consistently return the same numbers when the program is restarted. Most such libraries have short cycle lengths and are not usable for cryptographic purposes.

"Numerical Recipes in C" reviews several random number generators and recommends a modified version of the DES cypher as their highest quality recommended random number generator. "Practical Cryptography" (Ferguson and Schneier) recommend a design they have named Fortuna; it supersedes their earlier design called Yarrow.

Methods of nondeterministic number generation

As of 2004, the best random number generators have 3 parts: an unpredictable nondeterministic mechanism, entropy assessment, and conditioner. The nondeterministic mechanism (also called the entropy source) generates blocks of raw biased bits. The entropy assessment part produces a conservative estimate of the min-entropy of some block of raw biased bits. The conditioner (also called a whitener, an unbiasing algorithm, or a randomness extractor) distills the block of raw bits into a much smaller block of conditioned output bits -- an output block of bits half the size of the estimated entropy (in bits) of the raw biased bits -- eliminating any systematic bias. If the estimate is good, the conditioned output bits are unbiased full-entropy bits even if the nondeterministic mechanism degrades over time. In practice, the entropy assessment is the difficult part.

Further Reading

• Cryptography/Random Quality
• RFC 4086 "Randomness Requirements for Security"
• Random Number—from MathWorld
• Statistics/Numerical Methods/Random Number Generation
• Algorithms/Randomization
• Random number generation standards development bodies