 ## Cryptology

### Part IV. Bitstream Ciphers

 a7Hzq .#5r

#### Contents

1. Classic pseudorandom generators: Congruential generators and feedback shift registers
2. Cryptanalysis of pseudorandom generators
3. Feedback shift registers and linear complexity
4. Perfect pseudorandom generators
Appendices:
• Statistical distinguishers [PDF]
• Recursive and periodic sequences: How to find the shortest feedback shift register that generates a given finite sequence [PDF]
• SageMath Code for bitstream ciphers [PDF]
• SageMath modules: FSR, bmAlg, Periods

The complete Part IV as PDF file.

#### Introduction

A bitstream cipher sequentially encrypts each single bit of a bitstring by an individual rule. The two possibilities are: leave the bit unchanged, or negate it. Leaving the bit unchanged is equivalent with (binary) adding 0, negating the bit is equivalent with adding 1. Thus every bitstream cipher may be interpreted as an XOR encryption, the key being the »difference« between ciphertext and plaintext. We distinguish between

synchronous bitstream ciphers
where the key stream is generated independently of the plaintext,
asynchronous bitstream ciphers
where the key stream depends on the plaintext or other context parameters.
In this part of the lecture notes we treat synchronous bitstream ciphers in a systematic way. We disregard asynchronous bitstream ciphers, and also stream ciphers over other alphabets than F2 = {0, 1}.

Key streams are usually provided by random generators, more exactly in most cases by pseudorandom generators, the main basic techniques being:

• feedback shift registers and combinations of them (as application of Boolean algebra),
• number theoretic pseudorandom generators (as application of number theory).

Author: Klaus Pommerening, 1997-Apr-09; last change: 2021-Apr-17