Cryptology IV.2 Cryptanalysis of Pseudorandom Generators

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

Contents

1. The general linear generator [PDF]
2. Linear generators over fields [PDF]
3. Cracking an LFSR Stream XOR Encryption [PDF]
4. Linear congruential generators with known module [PDF]
5. Linear congruential generators with unknown module [PDF], and prediction program
6. A general prediction method [PDF]
7. Nonlinear feedback shift registers [PDF]
   Mathematica program for constructing nonlinear FSRs as Mathematica notebook and text
   SageMath code is contained in the PDF file and Appendix.
8. The general congruential generator [PDF]
9. Analysis in the case of truncated output (outline) [PDF]
10. Summary [PDF].

The complete chapter as PDF file

Introduction

We slightly enlarge the black box model of a pseudorandom generator:

The black box hides an inner state that changes with each step by a given algorithm. This algorithm is controlled by parameters some of which are »public«, but some of which are secret and serve as components of the key. The initial state (= start value) is a true random value and likewise secret. With each step the pseudorandom generator outputs a value, depending on its current inner state, until an exterior intervention stops it.

Cryptanalysis of pseudorandom generators assumes a known-plaintext attack. Thus the attacker is supposed to observe (or correctly guess) some elements of the output sequence. Her potential targets are the following data:

• the secret internal parameters,
• the initial state,
• forthcoming elements of the output (»prediction problem«).