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

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."


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
  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."


1991 -- Ritter

Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia. 15(2): 81-139.

"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. x2 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


Terry Ritter, his current address, and his top page.

Last updated: 1996-06-26