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:
  1. Well suited for hardware implementation
  2. They can produce sequences of large period
  3. They can produce sequences with very good statistical properties
  4. because of their structure, they can be readliy anallzed with algebraic techniques

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:

  1. the content of stage 0 is output and forms part of the output sequence.
  2. the content of stage i is moved to stage i-1 for each i, 1<=i<=L-1;
  3. the new content of stage L-1 is the feedback bit sj, 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 {sL-1, ..., s1,s0} than the output sequence s = s0, s1, s2, ... is uniquely determined by the following recursion:
sj = ( c1sj-1+c2sj-2+...+cLsj-L) mod 2 for j >= L