Cryptology Part IV. Bitstream Ciphers

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

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

• 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.

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).