Symmetric-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 156

LFSR Operation

0. Input the seed, and set j =1.

1. The bit, k (0 ,j − 1) , in register 0 is output as the next bit in the keystream.
In other words, k (0 ,j − 1) is tapped as the next keystream bit, and becomes
part of the output sequence, and we store it with the label K j − 1 .

2. The bit in register i , for i =0 , 1 ,..., 2, is shifted one register to the

right, namely, the contents of register i becomes k ( i − 1 ,j − 1) .

−

3. Register − 1 is given as the following input,

k ( − 1 ,j ) = c 1 k ( − 1 ,j − 1) ⊕ c 2 k ( − 2 ,j − 1) ⊕···⊕ c k (0 ,j − 1) . (3.6)

This step is called the linear feedback .

4. If s 0 = s i , set i = i +1 and go to step 1. Otherwise, set i = L , and terminate

the algorithm, with output keystream given by

k =( K L − 1 K L − 2 ...K 0 ) ,

which is said to have period length L .

Diagram 3.8 shows the result of the first bit iteration.

Diagram 3.8 A Linear Feedback Shift Register

⊕ ←−−−− ⊕←···←−⊕←⊕
k − 1 , 1

c − 1

···

c 1 c 2 c

✄
✂ ✁

→ ✄
✂ ✁

···→ ✄
✂ ✁

→ ✄
✂ ✁

→ k k k 1 , 0 k 0 , 0 output: K 0

− 1 , 0 − 2 , 0

Thus, the state after the completion of the first bit-iteration given in Diagram
3.8 is

s 1 = k ( − 1 , 1) ,k ( − 2 , 1) ,k ( − 3 , 1) ,...,k (0 , 1) =
k ( − 1 , 1) ,k ( − 1 , 0) ,k ( − 2 , 0) ,...,k (1 , 0) ,

where,

c k (0 , 0) .
A very simple illustrating instance of the LFSR is given in the following.

k ( − 1 , 1) = c 1 k ( − 1 , 0) ⊕ c 2 k ( − 2 , 0) ⊕···⊕