Linear Feedback Shift Register

A LFSR is set of rules to alter a set of bits. They are useful to psudeo random number generators, and as key generators for stream ciphers.

All LFSRs are cyclical in nature, and after a set amount of time will repeat back into themselves. The initial state of the bits in the LFSR is called the seed.

The maximum period for a n bit shift register is

2^n - 1

An LFSR can be generalized as a recurrence relationship where

A tap is where a bit is read and fed back into itself.

Reverse Engineering

An LFSR generates values based on a linear expression modulous 2, therefore we can reverse engineer the state of the LFSR based on a sequence we are given. This can be done using the Berlekamp-Massey algorithm.

So first we will start with a simpler version. If we have a sequence and we know the number of bits in the LSFR, we can create a matrix of the values. If S_{i} is the i th value out of an LSFR, we can solve the following

Sa = x

Where S is a matrix of the outputted values formatted below

A has the coefficents of the LFSR

and x has values of the bit string, as formatted below.

Assume 4 bits
--           ----  --   --  --
| s0 s1 s2 s3 || a0 |   | s4 |
| s1 s2 s3 s4 || a1 | = | s5 |
| s2 s3 s4 s5 || a2 |   | s6 |
| s3 s4 s5 s6 || a3 |   | s7 |
--           ----  --   --  --

Note that

Given this, we can find the coefficents by solving

a = S^-1 * x

Once we do this, it will give us all of the coefficents! Everywhere there is a 1 a tap will be located there and all of these values are XORed and placed onto the back of the register.

To make this the Berlekamp-Massey algorithm, we first start and assume the number of bits n is 1, check if it makes the right seuqnece, and if not we increase n and try again. That all there is to it!