CONNOTECH Experts-conseils Inc.

Pseudo-Random Generators, a High-Level Survey-in-Progress

by Thierry Moreau

March 1997

© 1997 CONNOTECH Experts-conseils Inc.


Contents

Introduction
Basic definitions
Uses of pseudo-random generators
The paradoxical aspect of pseudo-random number generators.
Fields of science that deal with pseudo-random number generation.
Algorithmic classification
Testing of pseudo-random generators
Warning for cryptographic application designers
Conclusion
References

Introduction

This internet document contains miscellaneous thoughts on pseudo-random number generation. It is a "survey-in-progress" of the field. Indeed, there isn't a single field of science attached to pseudo-random generators, and this document originality might be to shed light on this topic from various angles in a single communication.

For genuine survey articles, see [6] and [15], which are respectively from the computer simulation field and cryptography. Interesting Internet resources on this topic includes the PLab project, a server on the theory and practice of random number generation, maintained by a team of mathematicians and computer scientists from the University of Salzburg.

Basic definitions

A pseudo-random generator is an algorithm with some state information that is the sole input. The generator is exercised by steps, and two things occur concurrently during each step: there is a transformation of the state information, and the generator outputs a fixed size bit string. The generator seed is simply the initial state information. With any pseudo-random generator, after a sufficient number of steps, the generator comes back to some sequence of states that was already visited. Then, the period of the generator is the number of steps required to do one full cycle through the visited states.

For our purpose, there are three types of random number generation methods:

  1. The toy generators that are provided by most programming languages, and many software packages. If you read this document, you are already aware that these generators should be considered suspicious for most serious applications ([3]). For instance, the rand() function of the C programming language usually falls in this category.

  2. The serious generators, that is generators with internal state information using at least 64 bits and with empirical and/or theoretical justifications.

  3. The truly random generators: electronic circuits that employ measurements of a natural phenomenon to provide totally unpredictable draws, contrary to pseudo-random number generators with their deterministic output sequence ([13]). In practice, truly random number generators are combined with serious generators.

Uses of pseudo-random generators

Here are a few examples of usage of pseudo-random generators:

The paradoxical aspect of pseudo-random number generators.

From a strict mathematical point of view, the very definition of a pseudo-random sequence seems to be impossible to set: a pseudo-random sequence is one which can not be distinguished from a truly random one, but what is a truly random sequence? If you take a random 32 bit integer, 0 is as likely to occur as 0x75F19AB0. Who can venture into listing all 32 bits integers that are "less random" than 0x75F19AB0? This paradoxical aspect of pseudo-random generators can lead to endless discussions.

Fields of science that deal with pseudo-random number generation.

Mathematics
Be prepared to deal with mathematics if you intend to do anything serious in the field of pseudo-random generator.
Computer science
Pseudo-random generators are more or less useful based on system architecture. Will you trust a smart card to generate a random cryptographic key that will lock your bank account? If you sell a massively parallel computer to research laboratories, which pseudo-random generator will you put in your parallel FORTRAN compiler?
Physics
Being users of simulation tools, many researchers in physics and a few in finance became experts in the field of pseudo-random generators.
Cryptography
Any cipher system is supposed to turn meaningful text into scrambled bits, and thus should be somehow analogue to a pseudo-random generator. Cryptographic hash functions are similarly related to randomness. Conversely, to be used as a stream cipher, a pseudo-random generator must meet criteria that are specific to the field of cryptography.

Algorithmic classification

Here is an attempt to classify pseudo-random generator algorithms. This is a very rough classification at the draft stage.

Analyzable algorithms from the field of simulation are those for which many properties can be ascertained by the discipline of mathematics. Among those, we could attempt to distinguish the LFSR-equivalent class (LFSR stands for Linear Feedback Shift Registers, [14], [12]), predominantly using shifts and exclusive-or operations, from the small-modulus class, predominantly using multiplications, additions, and modulus (remainder) operations. In the latter class, the serious generators almost invariably use muduli that are not exact powers of two. In either classes, mathematicians came up with creative combinations of small generators (those that fit in 32 bit computer words) to make huge generators with interesting statistical properties while remaining efficient ([7], [4]).

The heuristic combination of small generators from dissimilar designs usually produce generators for which mathematicians can not formally assert properties. This type of generator should be avoided.

Cryptographically-supported heuristics are generators build from secret key ciphers and secure hash functions. In this class, the generator characteristics are basically unknown, but if any statistical defect was found, it would turn into a cryptanalytic weakness. The fact that years of cryptanalysis attempts leave a cryptographic algorithm intact is a strong argument supporting a generator that is derived from this algorithm. Although rarely used in the field of simulation, generators from this class of generators can be considered serious. A stream cipher falls in this class; it can be used directly as a pseudo-random generator.

Number-theoretic generators are built from the same mathematical functions as public key cryptography primitives ([1], [10], [8]). They might be related to the small-modulus analyzable algorithms because 1) they are indeed analyzable to a great extent, and 2) they use modular arithmetic operations, but this time with large moduli (e.g. 180, 256, or even 1024 bits). As in the case of public key cryptography primitives, the theoretical support for this class of generators stems from complexity theory, but uses "unproven assumptions," (e.g. it is computationally difficult to find the factors of large integers).

Testing of pseudo-random generators

Statistical testing of pseudo-random generators appears effective only to reject generators with statistical defects, and maybe to verify a precise statistical defect suspected from formal analysis. This testing can not prove that a generator is good ([5]).

Warning for cryptographic application designers

The random key source can be the achile's heel of a security system. In most cases, the generator state should be kept secret ([11]). Also, be realistic about "unpredictable" seeds: how useful is a key size of 38 digits if it is generated from a seed derived from the current time to the nearest second (there are less than 1,000,000,000 seconds in the expected life-cycle of a secure application design).

Conclusion

There is no such a thing as an ideal pseudo-random generator, but there are less and less excuses to use any generator based on an ad-hoc or obscure design.

References

[1] Blum, Leonore, Blum, Manuel, and Shub, M., A Simple Unpredictable Pseudo-random Number Generator, SIAM Journal of Computing, vol. 15, no. 2, May 1986, pp 364-383

[2] Brotherton-Ratcliffe, Rupert, Using Quasi-Random Sequences in Monte-Carlo Valuation of Path-Dependent Options, Risk Magazine, December 1994, and also in Canadian Treasurer, vol 11, number 2, April 1995, pp 36-38

[2] Brotherton-Ratcliffe, Rupert, Using Quasi-Random Sequences in Monte-Carlo Valuation of Path-Dependent Options, Risk Magazine, December 1994, and also in Canadian Treasurer, vol 11, number 2, April 1995, pp 36-38

[3] Ferrenberg, Alan M., Landau, D.P., and Wong, Y. Joanna, Monte Carlo Simulations: Hidden Errors from "Good" Random Number Generators, Physical Review Letters, Vol. 69, Number 23, 7 December 1992, pp. 3382-3384

[4] L'Écuyer, Pierre, Combined Multiple Recursive Random Number Generators, Les cahiers du GERAD, G-95-15, March 1995

[5] L'Écuyer, Pierre, Testing Random Number Generators, Proceedings of the 1992 Winter Simulation Conference, IEEE press, pp 305-313

[6] L'Écuyer, Pierre, Uniform Random Number Generation, Annals of Operations Research, vol. 53 (1994), pp 77-120

[7] Matsumoto, Makoto, and Kurita, Yoshiharu, Twisted GFSR Generators II, ACM Transactions on Modeling and Computer Simulations, Vol. 4, No. 3, July 1994, pp 254-266

[8] Micali, Sylvio, and Schnorr, Claus P., Efficient, Perfect Polynomial Random Number Generators, Journal of Cryptology, Vol 3 (1991), pp 157-172

[9] Moore, Lynn, $600,000 put aside for keno winner, The Gazette, Montreal, April 23, 1994, page A6

[10] Moreau, Thierry, A practical 'perfect' pseudo-random number generator, article submitted to Computers in physics, 1996

[11] Moreau, Thierry, A Probabilistic Flaw in PGP Design?, Computers & Security, Vol. 15 No. 1 (1996), pp 39-43

[12] Mullen, G.L., and Niederreiter, Harald, Optimal Characteristic Polynomials for Digital Multistep Pseudorandom Number, Computing, vol. 39, 1987, pp 155-163

[13] Newbridge Microsystems, RBG1210 Random Bit Generator, data sheet published in Newbridge Microsystems' 3rd issue of CMOS Products data book, Newbridge Microsystems, Kanata, Ontario, Canada, 1992

[14] Tausworthe, R.C., Random numbers generated by linear recurrence modulo two, Mathematics of Computation, Vol 19 (1965), pp 201-209

[15] Ritter, Terry, The Efficient Generation of Cryptographic Confusion Sequences, Cryptologia, Vol XV, number 2, April 1991, pp 81-139

[16] Vattulainen, I., Ala-Nissila, T., and Kankaala, K., Physical Tests for Random Numbers in Simulation, Physical Review Letters, Vol. 73, Number 19, 7 November 1994, pp. 2513-2516


security scheme designalternative to PKIpatent publicationsSAKEMscholarly web contentsconsulting services ]
[ CONNOTECH home page: http://www.connotech.com/about us | e-mail to: info@connotech.com ]

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900