RNG Surveys: A Literature Survey

Research Comments from Ciphers By Ritter

Terry Ritter

There are so many different random number generators (RNG's), and so many claims made for them, that many people have tried to expose the mysteries -- including me!

These are various surveys of pseudo(!)-random number generator schemes from various different points of view.

Contents

• 1983
  • Ripley gives us an early discussion of RNG designs and testing; no particular RNG is proposed. Included are approaches for producing random deviates in various distribution.
• 1989
  • Lewis and Orav present a full chapter on RNG's in their simulation text. They survey various RNG designs and promote graphic testing of the distributions in the resulting designs.
  • L'Ecuyer presents what is apparently another version of L'Ecuyer 1990. This is a survey of the various types of RNG, and no particular implementation is promoted.
• 1990
  • L'Ecuyer discusses generators for simulation use. Very like L'Ecuyer 1989. Again, this is a survey of the various types of RNG, and no particular implementation is promoted.
  • James discusses generators for Monte Carlo use. This is another survey of RNG type, this time with some examples of famous LCG multipliers. Several examples of famous current designs are given in FORTRAN, but not tested here.
  • Lagarias discusses generators with respect to number theory and cryptography. Very theoretical, but touches on one-way functions, unpredictability, and computational complexity issues.
• 1991
  • Zeng, Yang, Wei and Rao discuss bit generators for stream-cipher cryptography. Again, a survey of different types of RNG, but here including approaches intended to make the RNG difficult to analyze from its sequence.
  • Ritter I survey RNG's for use in cryptography, with extensive references.

1983 -- Ripley

Ripley, B. 1983. Computer Generation of Random Variables: A Tutorial. International Statistical Review. 51: 301-319.

"Summary. Users of small and personal computers do not have access to the libraries of generators of random variables provided by experts which have been common on large computer installations. This tutorial provides the background needed by user-programmers to replace the often inadequate pseudorandom number generators supplied with small computers, and to program simple yet efficient methods to generate samples from exponential, normal, gamma, Poisson, ..., distributions for use in simulation studies."

1. Rationale
2. Pseudorandom numbers
3. Testing pseudorandom-number generators
4. Continuous distributions
   1. Inversion
   2. Transformations
   3. Acceptance-rejection
   4. Ratio methods
   5. Composition
5. Conclusions

1989 -- Lewis and Orav

Lewis, P. and E. Orav. 1989. Simulation Methodology for Statisticians, Operations Analysts, and Engineers. Wadsworth and Brooks: Pacific Grove, CA.

In Chapter 4 they introduce the use of "scatter plots" to examine generators.

Chapter 5. Uniform Pseudo-Random Variable Generation.

1. Introduction: Properties of Pseudo-Random Variables
   1. A uniform marginal distribution
   2. Independence of the uniform variate
   3. Repeatability and portability
   4. Computational speed
2. Historical Perspectives
3. Current Algorithms
   1. Congruential Generators
   2. Shift-Register Generators
   3. Fibonacci Generators
   4. Combinations of Generators (Shuffling)
   5. Generators in Packages
4. Recommendations for Generators
5. Computational Considerations
6. The Testing of Pseudo-Random Number Generators
7. Conclusions on Generating and Testing Pseudo-Random Number Generators
   1. "Testing is unnecessary in the sense that very good pseudo-random number generators are available."
   2. "Testing is necessary in the sense that bad pseudo-random number generators exist on many computer systems and are commonly used."
   3. "It is preferable to substitute a good pseudo-random number generator with documented properties for a pseudo-random number generator you known nothing about. And even if you follow [this rule], it is wise to use some of the graphical testing methods given in this book to make sure that the implementation is correct."

1989 -- L'Ecuyer

L'Ecuyer, P. 1989. A Tutorial on Uniform Variate Generation. Proceedings of the 1989 Winter Simulation Conference. 40-49.

"ABSTRACT. In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in the appropriate way. In this tutorial, we examine practical ways of generating such variates on a computer."

[This paper is very similar to the 1990 version in Communications of the ACM, Please refer to that review.]

1990 -- L'Ecuyer

L'Ecuyer, P. 1990. Random Numbers for Simulation. Communications of the ACM. 33(1): 85-97.

"On the mind of the average computer user, the problem of generating uniform variates by computer has been solved long ago. After all, every computer system offers one or more function(s) to do so." "These functions supposedly return numbers that could be used, for all practical purposes, as if they were the values taken by independent random variables, with a uniform distribution between 0 and 1."

"We focus mainly on efficient and recently proposed techniques for generating uniform pseudorandom numbers." "Here, 'uniform pseudorandom' means that the numbers behave from the outside as if they were the values of i.i.d. [individually independently distributed] random variables, uniformly distributed over some finite set of symbols. This set of symbols is often a set of integers of the form {0, ..., m - 1} and the symbols are usually transformed by some function into values between 0 and 1, to approximate the U(0,1) distribution."

• Views of Randomness
  • Classical Definitions
  • A Framework for PRNGs
  • PT-perfect generators
• Matrix Linear Congruential Recurrences
  • Prime Modulus
  • Composite Modulus
  • Jumping Ahead, Splitting, and Vectorization
  • Implementations
  • Multiple Recursive Generators
  • Lattice Structure and Spectral Test
  • Tausworthe, GFSR, Lagged-Fibonacci
  • Other Variants
• Non-Linear Generators
  • A Class of Generators by Inversion
• Combined Generators
• Transforming into U(0,1) Variates
• Statistical Testing
• Discrepancy

1990 -- James

James, F. 1990. A review of pseudorandom number generators. Computer Physics Communications. 60: 329-344. North-Holland.

"This is a brief review of the current situation concerning practical pseudorandom number generation for Monte Carlo calculations. The conclusion is that pseudorandom number generators with the required properties are now available, but the generators actually used are often not good enough. Portable Fortran code is given for three different pseudorandom number generators, all of which have much better properties than any of the traditional generators commonly supplied in most program libraries."

1. General considerations
   1. The motivation and scope of this paper
   2. The three types of generators
      1. Truly random numbers . . . must be produced by a random physical process."
      2. "Pseudorandom numbers . . . are supposed to appear random to someone who doesn't know the algorithm."
      3. "Quasirandom numbers . . . are not designed to appear to be random, but rather to be distributed as uniformly as possible, in order to reduce the errors in Monte Carlo integration."
   3. Desirable properties of a random number generator
      1. Good distribution.
      2. Long period.
      3. Repeatability.
      4. Long disjoint subsequences.
      5. Portability.
      6. Efficiency.
   4. Manufacturer-supplied generators
2. Pseudorandom numbers
   1. Testing good distributions
   2. Pseudorandom generation methods
      1. MLCG [multiplicative linear congruential generator]
      2. Fibonacci
      3. Shift register or tausworthe
   3. Improving simple generators
3. Acceptable pseudorandom generators
   1. The McGill generator super-duper [Marsaglia]
   2. RANECU: the algorithm of l'Ecuyer
   3. RANMAR: the algorithm of Marsaglia, Zaman and Tsang
   4. ACARRY: the algorithm of Marsaglia and Zaman
4. Conclusions

1990 -- Lagarias

Lagarias, J. 1990. Pseudorandom Number Generators in Cryptography and Number Theory. Proceedings of Symposia in Advanced Mathematics. 42: 115-143.

"Abstract. This paper describes the close relations that exist between pseudorandom number generators, one-way functions, and private key cryptosystems. It presents a taxonomy of pseudorandom number generators based on number-theoretic constructions and summarizes results on the cryptanalysis of such generators."

1. Introduction
2. A Taxonomy of Number-theoretic Generators
   1. Multiplicative Congruential Generator
   2. 1/P Generator
   3. Power Generator
   4. Discrete Exponential Generator
   5. Kneading Map
   6. Shift-Register Sequences
   7. Cellular Automata
   8. Hashing
   9. Composition
3. What is a Pseudorandom Number Generator?
4. Unpredictability and Pseudorandomness
5. Pseudorandom Bit Generators and One-way Functions
6. Pseudorandom Bit Generators and Private-key Cryptosystems
7. Secure Number-theoretic Pseudorandom Bit Generators
   • RSA bit generator.
   • Modified Rabin bit generator.
   • Discrete exponential bit generator.
8. Cryptanalysis Problems

1991 -- Zeng, Yang, Wei and Rao

Zeng, K., C. Yang, D. Wei and T. Rao. 1991. Pseudorandom Bit Generators in Stream-Cipher Cryptography. IEEE Computer. February. 8-17.

"The central problem in stream-cipher cryptography . . . is the difficulty of generating a long unpredictable sequence of binary signals from a short and random key."

"The problem is this: On which basis can one draw the conclusion that the output signals of a certain given keystream generator are hard to predict? No universally applicable and practically checkable criteria have been developed to certify the security of bit generators. For that matter, no general theory of cryptanalysis is known to exist except for an ever-expanding arsenal of concrete attack methods elaborated for various practical purposes."

"Many of the publicly proposed keystream generators. We remind the reader that cracking keystream generators amounts to the same thing as conducting known-plaintext attacks on stream ciphers. Secure communication should resist such attacks."

• Background
  • The one-time pad.
  • Secure pseudorandom bit generators.
• Building Blocks
  • Linear congruence generators (LCGs).
  • Feedback shift registers (FSRs).
  • Nonlinear feedback shift registers.
  • Linear feedback shift registers.
  • The linear complexity issue.
• Attacking Keystream Generators
  • The Siegenthaler correlation attack.
  • The linear consistency attack.
  • The linear syndrome attack.
• Some design techniques
  • Nonlinear feed-forward transformation.
  • Step control.
  • Multiclock systems.

1991 -- Ritter

"ABSTRACT: A survey of pseudo-random sequence or random number generators (RNG's) for cryptographic applications, with extensive reference to the literature, and seemingly unresolved issues discussed throughout."

1. Introduction
2. Background
3. Basics and Terminology
   1. Randomness
   2. Randomness and Data Compression
   3. Reasoning about Randomness
   4. Godel and Ciphers?
   5. Characteristics of Computer-Based RNG's
   6. Number of Sequences
   7. Cycles
   8. Some Potential Attacks
   9. Inference Resistance by Exposure Class
   10. Information and Penetration
   11. Inference versus Prediction
   12. Cryptographic RNG Requirements
4. RNG Techniques
   1. Chaos
   2. Cebysev Mixing
   3. Cellular Automata
   4. x² mod N
   5. Linear Congruential
   6. Linear Feedback Shift Register
   7. Non-Linear Shift Register
   8. Clock-Controlled Shift Registers
   9. Generalized Feedback Shift Register
   10. Additive RNG
5. Randomizers and Isolators
   1. One-Way Functions
   2. Checksum Algorithms
   3. CRC's
   4. Randomizers
   5. Isolation Techniques
6. Other Randomness Techniques
   1. "Really Random" Values
   2. Cycle Detection
   3. Polynomial Degree
   4. Sequence Customization and Number of Terms
   5. Finding Primitive Mod 2 Polynomials
   6. Combined RNG's
   7. Random Permutations
7. RNG Exhaustive State Experiments
   1. Exhaustive State Analysis
   2. Results
   3. Discussion
8. Summary
9. Comments

Last updated: 1996-06-26