Cryptology IV.1 Classic Pseudorandom Generators: Congruential Generators and Feedback Shift Registers

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

1. General discussion of bitstream ciphers [PDF]
2. Methods for generating a key stream [PDF]
3. Linear congruential generators [PDF]
4. The maximum period [PDF]
5. The maximum period of a multiplicative generator [PDF]
6. Feedback shift registers (FSR and LFSR) [PDF]
   Mathematica program for constructing linear FSRs as Mathematica notebook and text
   SageMath code is in the Appendix.
7. Multistep generators [PDF]
8. General linear generators [PDF]
9. Matrix generators over finite fields [PDF]
10. Statistical properties of LFSRs [PDF]

The complete chapter as PDF file

Introduction

[See also the section on XOR in Part I.]

»Classic« (pseudo-) random generators are algorithms that generate »pseudorandom« numbers or bits for use in statistical applications or simulations instead of »true« random numbers or bits. For this kind of applications their statistical properties are excellent. The standard references are

Solomon W. Golomb, Shift Register Sequences. Revised Edition: Aegean Park Press, Laguna Hills 1982.
Donald E. Knuth, The Art of Computer Programming, Vol.2, Seminumerical Algorithms. Addison-Wesley, Reading Mass. 1969, 1981.

However the requirements of cryptology are much stronger. The methods of cryptanalysis mercilessly reveal the weaknesses of classic pseudorandom generators, and make them useless for naive direct cryptographic application.

This chapter introduces the best known classic pseudorandom generators and derives their most important properties.

The following figure describes a simple model for pseudorandom generation. The state is an element of a set M, changing after each step according to the state transition algorithm M → M. The output (of each step) is an element of an output alphabet Σ.