First, a primer

The LFSRs (Linear Feedback Shift Registers) represent a family of very low-level, simple to implement, and darn quick ways of generating seemingly random sequences of bits. It is no surprise then that they are often used as PRNGs (pseudo-random number generators).

In spite of their many aforementioned practical qualities they are, however, definitely not well known for their cryptographic strength.

But let’s take things one at a time. So, how do they work?

A bird’s-eye view of an LFSR’s functionality

[b1][b2][b3][b4][b5]...[bn]

Imagine for a second that the above is a sequence of $n$ bits. We call this initial sequence the seed of the LFSR.

To obtain a new $n$-bit sequence, we apply the following recurrence rule:

[b1][b2][b3][b4][b5]...[bn]
  \   \   \   \   \   \
    \   \   \   \   \   \
[x0][b1][b2][b3][b4]...[bn-1]

where $x_0 = \bigoplus_{k=1}^n t_kb_k$ is the sole new bit, for some $t_k \in \{0, 1\}$. $b_n$ is discarded, and all other bits are shifted one position to the right.

In general, $k$ is called a tap of the LFSR $\iff$ $t_k = 1$.

Conceptually, taps can be thought of as positions which contribute towards the birth of a new bit.

Note that this sequence of $n$-bit sequences (let’s call this $(L_n)$) has an order of sorts. Since every state is entirely dependent on the state before it and there exist only $2^n$ distinct sequences of bits, this order can be at the very most $2^n$. Hence,

$$\forall L : \exists\,\text{ord}(L) \in (0, 2^n] : L_{\text{ord}(L)} = L_{0}.$$

[To be continued.]