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 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