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

Contents
 Classic pseudorandom generators:
Congruential generators and feedback shift registers
 Cryptanalysis of pseudorandom generators
 Feedback shift registers and linear complexity
 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 F_{2} = {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, 1997Apr09;
last change: 2021Apr17