A

linear feedback shift register is a

feedback shift register. The LFSR, as these are known, is often a key

design component in the

keystream generator of a

stream cipher. There are several reasons for this:

- Well suited for hardware implementation
- They can produce sequences of large period
- They can produce sequences with very good statistical properties
- because of their structure, they can be readliy anallzed with algebraic techniques

Definition

A LFSR of length L consists of L stages (aka delay elements) numbered 0,1,..., L-1, each capable of storing one bit and having both one input and one output; and a clock which controls the movement of data. During each unit of time the following operations are performed:

- the content of stage 0 is output and forms part of the output sequence.
- the content of stage i is moved to stage i-1 for each i, 1<=i<=L-1;
- the new content of stage L-1 is the feedback bit
*s*_{j}, which is calculated by adding together modulo 2 the previous contents of a fixed subset of stages 0, 1, ... , L - 1.

Mathematical Fact:

if the initial state of the LFSR is {*s*_{L-1}, ..., s_{1},s_{0}} than the output sequence s = s_{0}, s_{1}, s_{2}, ... is uniquely determined by the following recursion:

*s*_{j} = ( c_{1}s_{j-1}+c_{2}s_{j-2}+...+c_{L}s_{j-L}) mod 2 for *j* >= *L*