[JoGu]

Cryptology

Part IV. Bitstream Ciphers

a7Hzq .#5r<
k\as TK$
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
Appendices:

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.

[XOR encryption]

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:


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