Stream Ciphers - Understanding Cryptography - page 42

A Mathematical Description of LFSRs

The general form of an LFSR of degree m is shown in Fig. 2.7. It shows m flip-flops
and m possible feedback locations, all combined by the XOR operation. Whether a
feedback path is active or not, is defined by the feedback coefficient p 0 , p 1 ,..., p m − 1 :
If p i = 1 (closed switch), the feedback is active.
If p i = 0 (open switch), the corresponding flip-flop output is not used for the
feedback.

With this notation, we obtain an elegant mathematical description for the feedback
path. If we multiply the output of flip-flop i by its coefficient p i , the result is either
the output value if p i = 1, which corresponds to a closed switch, or the value zero if
p i = 0, which corresponds to an open switch. The values of the feedback coefficients
are crucial for the output sequence produced by the LFSR.

Fig. 2.7 General LFSR with feedback coefficients p i and initial values s m − 1 ,..., s 0

Let's assume the LFSR is initially loaded with the values s 0 ,..., s m − 1 . The next
output bit of the LFSR s m , which is also the input to the leftmost flip-flop, can be
computed by the XOR-sum of the products of flip-flop outputs and corresponding
feedback coefficient:

s m ≡ s m − 1 p m − 1 + ··· + s 1 p 1 + s 0 p 0 mod 2

The next LFSR output can be computed as:

s m +1 ≡ s m p m − 1 + ··· + s 2 p 1 + s 1 p 0 mod 2

In general, the output sequence can be described as:

m 1

j =0 p j · s i + j mod 2;

−

s i + m ≡ s i , p j ∈{ 0 , 1 } ; i = 0 , 1 , 2 ,... (2.1)

Clearly, the output values are given through a combination of some previous output
values. LFSRs are sometimes referred to as linear recurrences .