Konton in Kanji

Appendix: Introduction to Pseudo-Random Number Generators (PRNGs)


[Back to Konton2]

How PRNGs Work

Typically, a PRNG maintains a block of data called the "state data." When called upon to produce the next pseudo-random number, the PRNG performs two functions: its "next-state function" and its "output function." The next-state function puts the state data into its next state. The output function outputs a pseudo-random number which is a function of the state of the state data. Often, the number output is simply part of the state data. This practice raises security issues when the PRNG is used in cryptography.

For more information on how PRNGs work, see Ritter's 1991 article, "The Efficient Generation of Cryptographic Confusion Sequences" available at his website. There are also good discussions in Applied Cryptography (listed in the Books section of the Konton2 page) and the Handbook of Applied Cryptography. Another interesting source of information about PRNGs for simulation use is a news group posting by Prof. Marsaglia (to sci.stat.math and sci.math on Jan. 20, 1999). This posting discusses various generators, including Marsaglia's well-known multiply-with-carry generators. This posting also introduces a class of generators discussed at greater length in "Xorshift RNGs" in the Journal of Statistical Software.

Pseudo-Randomness

A deterministic process (for example, a computer program or a mathematical algorithm) cannot produce really random numbers. It can, however, produce numbers which appear to be random.

"Appear," here, does not involve looking at the numbers either in a list or graphically. Really complex patterns often appear random to the eye. Listening to the numbers as series of sound samples also doesn't work very well. My own experiments have demonstrated this. The problem seems to be that the ear (and microphones) can only hear a limited range of frequencies. Noise which sounds "white" may not be.

It's necessary to use statistical tests to verify "apparent" randomness. See the appendix on Randomness for a discussion of what "randomness" means in this context.

Breaking a PRNG

Designing a PRNG that can't be fairly easily broken is nontrivial. "Broken," here, means "shown to be predictable." A generator can be broken in two ways.

Many generators have terribly simple output functions which make inference of the state of the state data trivial. Linear Feedback Shift Registers (LFSRs) and their cousins Lagged Fibonacci Generators actually output their state data unaltered and in order!

In order to prevent inference of the state of the state data, a cryptographic PRNG must either output a complex, one-way function of the whole state data (as Konton2 does); output parts of the state data in pseudo-random order (as RC4 does); or output the same small part of the state data every time, but use a next-state function based on a so-called "nondeterministic polynomial time" problem in number theory (as the Blum-Blum-Shub generator does).

[Back to Konton2]