THE EFFICIENT GENERATION OF CRYPTOGRAPHIC CONFUSION SEQUENCES
Terry Ritter · Cryptologia · 1991
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. An introduction to random sequences is presented, with some speculative consequences suggested by Gödel's incompleteness theorem. Implications of a necessarily deterministic implementation, techniques of external analysis, and ways to complicate such analysis are discussed. A basis for RNG comparison is suggested. Various RNG's are described, including Chaos, Cebysev Mixing, Cellular Automata, x 2 mod N, Linear Congruential, Linear Feedback Shift Register, Non-linear Shift Register, Generalized Feedback Shift Register, and Additive types. Randomizer and isolator mechanisms, one-way functions, the combined sequences from multiple RNG's, random permutations, and methods for finding primitive mod 2 polynomials are also described. An empirical state-trajectory approach to RNG design analysis is given, and experimental results tabulated for several Cellular Automata, x 2 mod N, GFSR and Additive designs.