| Pseudorandom Number Generator |
Article Index for Pseudorandom |
Website Links For Pseudorandom |
Information AboutPseudorandom Number Generator |
| CATEGORIES ABOUT PSEUDORANDOM NUMBER GENERATOR | |
| pseudorandom number generators | |
|
Most pseudo-random generator algorithms produce sequences which are Uniformly Distributed by any of several tests. Common classes of these algorithms are Linear Congruential Generator s, Lagged Fibonacci Generator s, Linear Feedback Shift Register s and generalised feedback shift registers. Recent instances of pseudo-random algorithms include Blum Blum Shub , Fortuna , and the Mersenne Twister . Careful mathematical analysis is required to have any confidence a PRNG generates numbers that are sufficiently "random" to suit the intended use. Robert R. Coveyou of Oak Ridge National Laboratory once titled an article, "The generation of random numbers is too important to be left to chance."Peterson, Ivars. ''The Jungles of Randomness: A Mathematical Safari.'' Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6 As John Von Neumann joked, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951). PERIODICITY
If a PRNG's internal state contains ''n'' bits, its period can be no longer than 2n results. For some PRNGs the period length be calculated without walking through the whole period. LFSR s are usually chosen to have periods of exactly 2n-1. Linear Congruential Generators have periods that can be calculated by factoring. Mixes (no restrictions) have periods of about 2n/2 on average, usually after walking through a nonrepeating starting sequence. Mixes that are reversible ( Permutations ) have periods of about 2n-1 on average, and the period will always include the original internal state. Although PRNGs will repeat their results after they reach the end of their period, a repeated result does not imply that the end of the period has been reached. It is an open question, and one central to the theory and practice of Cryptography , whether there is any way to distinguish the output of a high-quality PRNG from a truly random sequence without knowing the algorithm(s) used and the state with which it was initialized. The security of most cryptographic algorithms and protocols using PRNGs is based on the assumption that it is infeasible to distinguish use of a suitable PRNG from a random sequence. The simplest examples of this dependency are Stream Cipher s, which (most often) work by Exclusive Or ing the Plaintext of a message with the output of a PRNG, producing Ciphertext . The design of cryptographically adequate PRNGs is extremely difficult. PROBLEMS WITH DETERMINISTIC GENERATORS In practice, the output from many common PRNGs exhibit Artifact s which cause them to fail statistical pattern detection tests. These include, but are certainly not limited to
Defects exhibited by flawed PRNGs range from unnoticeable to absurdly obvious. The RANDU random number algorithm used for decades on Mainframe Computer s was seriously flawed, and much research work of that period is less reliable than it might have been, as a result. EARLY APPROACHES An early computer-based PRNG, suggested by John Von Neumann in 1946 , is known as the Middle-square Method . It is very simple: take any number, square it, remove the middle digits of the resulting number as your "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which can be written as "01234321", an 8-digit number being the square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on. Von Neumann used 10 digit numbers, but the process was the same. A problem with the "middle square" method is that all sequences eventually repeat themselves, some very quickly, such as "0000". Von Neumann was aware of this, but he found the approach sufficient for his purposes, and was worried that mathematical "fixes" would simply hide errors rather than remove them. Von Neumann judged hardware random number generators unsuitable, for, if they did not record the output generated, they could not later be tested for errors. If they did record their output, they would exhaust the limited computer memories available then, and so the computer's ability to read and write numbers. If the numbers were written to cards, they would take very much longer to write and read. On the ENIAC computer he was using, the "middle square" method generated numbers at a rate some two hundred times faster than reading numbers in from Punch Card s. The middle-square method has been supplanted by more elaborate generators. MERSENNE TWISTER The 1997 invention of the Mersenne Twister algorithm, by Makoto Matsumoto and Takuji Nishimura, avoids many of the problems with earlier generators. It has the colossal period of 219937-1 iterations (likely far more than the number of computations which can be performed within the entire future existence of the universe), is proven to be Equidistributed in (up to) 623 dimensions (for 32-bit values), and runs faster than other statistically reasonable generators. It is now increasingly becoming the "random number generator of choice" for statistical simulations and generative modeling. Although suitable for other purposes, the Mersenne twister is not considered suitable for use in Cryptography . A variant has been proposed as a cryptographic cipher. {Link without Title} CRYPTOGRAPHICALLY SECURE PSEUDORANDOM NUMBER GENERATORS Main article: Cryptographically Secure Pseudorandom Number Generator A PRNG suitable for Cryptographic applications is called a ''cryptographically secure PRNG'' (CSPRNG). The difference between a PRNG and a CSPRNG is not simple: a CSPRNG must meet certain design principles and be resistant to known attacks. Years of review are required before such an algorithm can be certified and it is still possible attacks will be discovered in the future. Some classes of CSPRNGs include the following:
BSI EVALUATION CRITERIA The German Federal Office For Information Security (BSI) has established a four-part criteria for quality of deterministic random number generators. They are summarized here:
For cryptographic applications, only generators meeting the K4 standard are really acceptable. NON-UNIFORM GENERATORS Non-uniform probability distributions can be simulated with a uniform distribution PRNG and a non-linear function. For example the inverse of cumulative gaussian distribution with an ideal uniform PRNG with range (0, 1) as input produces a sequence with a gaussian distribution. Likewise for other distributions. A simple approximation is to use the Tan(x) as the inverse cumulative gaussian and a uniform distribution from -pi to pi non-inclusive. The density at a point is inversely proportional to the slope of the non-linear function at that point. A very steep slope will spread out numbers over a vast area, where as a very shallow slope will concentrate them over a small region. SEE ALSO
NOTES REFERENCES
EXTERNAL LINKS
|
|
|