**by Neal R. Wagner**

**Copyright © 2002 by Neal R. Wagner. All rights reserved.**

**
NOTE: This site is obsolete. See book draft (in PDF):**

Random numbers are very widely used in simulations, in statistical experiments, in the Monte Carlo methods of numerical analysis, in other randomized algorithms, and especially in cryptography. The connection with cryptography is very close, since any pseudo-random bit stream along with exclusive-or provides a cryptosystem (though not necessarily a strong system), and any good ciphertext should look like a pseudo-random bit stream (perhaps occurring in blocks). This section focuses on random number generators used in simulation and numerical analysis, but for use in cryptography, the recommended random number generators are derived from cryptosystems, both conventional and public key.

From the beginning (where ``beginning'' is the 1940s, the start of the computer age) there was interest in so-called ``true'' random numbers, that is, numbers generated by a random process in the world. Physical events such as the radioactive decay of particles are unpredictable except for their behavior averaged over time, and so could be used as a source of random numbers, but these events have been difficult to utilize and have been disappointing in practice. More promising recently are possibilities from quantum theory, but such matters are completely outside the scope of this discussion.

By far the most common source of random numbers is some
*deterministic* process, such as a software algorithm.
These provide ``random-looking'' numbers, but the numbers are not
*really* random -- there is always an exact algorithm for specifying
them. This is the reason that researchers now describe
such numbers using the word ``pseudo'', which means
``false''. These are not *true* random numbers, but for most
applications they can be just as useful. Sometimes they can be
more useful, as for example when one wants to repeat a simulation
with exactly the same random or pseudo-random numbers.

At first one might think that the best way to get random-looking numbers is to use a ``random'' algorithm -- one that does crazy operations, everything imaginable, in every possible order. Donald Knuth tried out such an algorithm as an example, and showed that its performance was no good at all. In its first run, Knuth's ``random'' algorithm almost immediately converged to a fixed point. Knuth was arguing that one should use science and great care in generating pseudo-random numbers.

An early suggested source of pseudo-random numbers was an equation which was much later to become a part of modern ``chaos'' theory. A later chapter describes a generator derived from this equation.

Another early idea for a source of random numbers was to use the
bits or digits in the exapnsion of a transcendental number such
as ** pi**, the ratio of the circumference of a circle
to its diameter.

It has long been conjectured that this is a very good source of pseudo-random numbers, a conjecture that has still not been proved. In 1852 an English mathematician named William Shanks published 527 digits of3.14159 26535 89793 23846 26433 83279 50288 41972 ... (in decimal) 3.11037 55242 10264 30215 14230 63050 56006 70163 21122 ... (in octal)

Later work focused on a particularly simple approach using a congruence equation.

This approach uses a *linear congruence equation* of the form:

where all terms are integers,x_{n+1}= (k*x_{n}+ a) mod m

This type of generator can produce at most ** m-1**
different numbers before it starts to repeat. To get this
behavior, one can start with a prime number for

The old generator provided by the C standard library uses
** 16**-bit integers, and so has a maximum possible
cycle length of

Knuth in his chapter on conventional random number generators
approves the values ** m = 2^{31} - 1** and

m | k |
---|---|

2^{31}-249 | 40692 |

2^{31}-1 | 48271 |

2^{31}-1 | 62089911 |

2^{32} | 69069 |

2^{48} | 31167285 |

2^{64}-1 | 6364136223846793005 |

Knuth suggests various generators, including one that combines the first two table entries above:

x_{n+1}= 48271*x_{n}mod (2^{31}- 1), y_{n+1}= 40692*y_{n}mod (2^{31}- 249), z_{n}= (x_{n}- y_{n}) mod (2^{31}- 1),

where independent seeds are needed for ** x_{0}** and

x_{n}= (271828183*x_{n-1}- 314159269*x_{n-2}) mod (2^{31}- 1),

which has very good performance and whose period is the square of
** m**. Of course two independent seeds

Knuth has other suggestions for efficient random number generators of high quality, where ``quality'' is measured by a variety of statistical tests that compare the output of the pseudo-random generator with true random numbers. If for a given test the comparison says the two sets of numbers look the same, then one says the generator ``passes'' this particular test. A generator that passes all the popular tests that people can devise is of high quality.

However, even generators of high quality
are mostly not usable in cryptography.
For example, given several successive numbers of a linear
congruence generator, it is possible to compute the modulus and
the multiplier with reasonable efficiency. One could make the
generator more complex in order to resist this attack, but there
would still be no proof or assurance of the difficulty of
``reverse engineering'' the generator. Instead, if generators
are needed in cryptographic applications, one is usually created
using a conventional cipher such as the Advanced Encryption Standard
or using a public key cipher such as RSA or one of its variants.
The AES-based generator will be efficient and will satisfy most
practical requirements, but the RSA-based systems, while extremely
slow compared to the others, have a very strong property of
being *cryptographically secure*, a term that means the
generator will pass all possible efficient statistical tests.
These matters will be defined and discussed in the next chapter.