Analysis and Design of Stream Ciphers

It is now a decade since the appearance of W. Diffie and M. E. Hellmann's startling paper, "New Directions in Cryptography". This paper not only established the new field of public-key cryptography but also awakened scientific interest in secret-key cryptography, a field that had been the almost exclusive domain of secret agencies and mathematical hobbyist. A number of ex cellent books on the science of cryptography have appeared since 1976. In the main, these books thoroughly treat both public-key systems and block ciphers (i. e. secret-key ciphers with no memo ry in the enciphering transformation) but give short shrift to stream ciphers (i. e. , secret-key ciphers wi th memory in the enciphering transformation). Yet, stream ciphers, such as those . implemented by rotor machines, have played a dominant role in past cryptographic practice, and, as far as I can determine, re main still the workhorses of commercial, military and diplomatic secrecy systems. My own research interest in stream ciphers found a natural re sonance in one of my doctoral students at the Swiss Federal Institute of Technology in Zurich, Rainer A. Rueppe1. As Rainer was completing his dissertation in late 1984, the question arose as to where he should publish the many new results on stream ciphers that had sprung from his research.

Inhalt

1. Introduction.- 2. Stream Ciphers.- 2.1. Theoretical versus Practical Security.- 2.2. The Key Stream Generator.- 2.3. The Synchronization (Problem) of Stream Ciphers.- 3. Algebraic Tools.- 3.1. Finite Fields and Polynomials.- 3.2. Linear Feedback Shift Registers (LFSRs) and Sequences.- 3.3. Minimal Polynomial and Traces.- 4. Random Sequences and Linear Complexity.- 5. Nonlinear Theory of Periodic Sequences.- 5.1. Nonlinear Operations on Phases of a Sequence with Irreducible Minimal Polynomial.- 5.2. Nonlinear Operations on Sequences with Distinct Minimal Polynomials.- 5.3. Correlation-Immunity of Memoryless Combining Functions.- 5.4. Summary and Conclusions.- 6. Multiple Speed: An Additional Parameter in Secure Sequence Generation.- 6.1. The Simulated Linear Feedback Shift Register.- 6.2. A Random Number Generator Suggested by a Linear Cipher Problem.- 7. The Knapsack as a Nonlinear Function.- 7.1. The Significance of the Knapsack for Secrecy Systems.- 7.2. Addition is a Cryptographically Useful Function.- 7.3. The Knapsack in GF(2)-Arithmetic.- 8. The Hard Knapsack Stream Cipher.- 8.1. System Description.- 8.2. Analysis of the Knapsack Stream Cipher.- 8.3. Conclusions and Design Considerations.- 8.4. Simulation Results of Small Scale Knapsack Stream Ciphers.- 9. Nonlinear Combining Functions with Memory.- 9.1. Correlation Immunity.- 9.2. The Summation Principle.- 9.3. Summary and Conclusions.- Literature References.