Linear Feedback Shift Registers: Primitive Polynomials over F2[x] and Stream Ciphers

The one-sentence version

An LFSR is a row of registers that XORs a few positions together and feeds the result back into the end of the queue, producing a long stream of "random-looking" bits. If the feedback polynomial is a primitive polynomial over $\mathbb{F}_2$ , an $n$ -bit register reaches the maximum period of $2^n - 1$ . But it is linear: after seeing just $2n$ output bits, the Berlekamp–Massey algorithm can solve for the entire register. So an LFSR alone is insecure, and nonlinearity must be added.

This article has three layers:

The intuition: a row of cells passing a message along
Real-world use: GPS, Wi-Fi scrambling, CRC, and the failures of GSM and DVD encryption
The mathematics: linear recurrences, primitive polynomials and maximal period, Berlekamp–Massey and worked examples

Layer 1: The Intuition

1.1 A row of cells passing a message along

Imagine 4 cells in a row, each holding 0 or 1. On each tick:

The leftmost cell "spits out" its digit as output;
All cells shift left by one;
The cell left empty on the right is filled with the XOR of certain cells.

In the diagram above, the new value $= s_0 \oplus s_1$ . The circuit needs only a few flip-flops and one XOR gate, so it is extremely cheap and extremely fast.

1.2 How long before it repeats

4 cells have $2^4 = 16$ states in all. The all-zero state stays at 0 forever, so at most 15 states can take turns. Choose the feedback positions correctly and it visits all 15 nonzero states before repeating; choose badly and the period is much shorter. Which positions are "right" is decided by whether a certain polynomial is primitive.

1.3 Why it is tempting and dangerous for encryption

The one-time pad needs a random key as long as the message. An LFSR offers a temptation: remember just the initial few dozen bits (the key), and you can generate a nearly unlimited "random" keystream to XOR with the plaintext.

The problem is that an LFSR is linear: its output bits satisfy a simple linear equation. An attacker who knows a small piece of plaintext (and therefore a small piece of keystream) can recover the whole register by solving a system of linear equations.

Layer 2: Real-World Use

Non-cryptographic uses (where LFSRs excel)

Use	Explanation
GPS satellite signals	Each satellite's C/A code is generated by combining two 10-bit LFSRs (a Gold code), with period 1023. Different satellites' codes have low cross-correlation, so receivers can tell them apart
Scrambling	Wi-Fi, Ethernet, USB 3.0 and PCIe use LFSR sequences to shuffle data and avoid long runs of 0s or 1s
CRC checks	Essentially polynomial division over $\mathbb{F}_2[x]$ using an LFSR circuit; see "Casting Out Nines and Check Digits"
Chip testing, pseudorandom test data	Cheap and reproducible

Cryptographic uses (more lessons than successes)

System	Outcome
GSM phones, A5/1	3 LFSRs stepped irregularly by "majority vote"; broken in the 2000s, and rainbow tables later allowed real-time cracking on ordinary hardware
CSS on DVDs	Two LFSRs with an effective key of only 40 bits; broken by DeCSS in 1999
Bluetooth E0	4 LFSRs plus a nonlinear combiner; several theoretical attacks exist

Modern stream ciphers (ChaCha20, AES-CTR) no longer center on LFSRs. However, SNOW 3G and ZUC (one of the 4G/5G standards) still wrap strong nonlinear components around an LFSR.

Layer 3: The Mathematics

3.1 Linear recurrences

The output of an $n$ -bit LFSR satisfies

$s_{t+n} = c_0 s_t + c_1 s_{t+1} + \cdots + c_{n-1} s_{t+n-1} \pmod 2,$

and the corresponding characteristic polynomial is $f(x) = x^n + c_{n-1}x^{n-1} + \cdots + c_1 x + c_0 \in \mathbb{F}_2[x]$ .

3.2 An LFSR is "multiplying by $x$ "

Treat the state as an element of the quotient ring $\mathbb{F}_2[x]/(f(x))$ . Then each LFSR step amounts to multiplying by $x$ .

If $f$ is irreducible, this quotient ring is the finite field $\mathbb{F}_{2^n}$ (abstract algebra: $F[x]/(f)$ is a field if and only if $f$ is irreducible);
The period is the order of $x$ in the multiplicative group $\mathbb{F}_{2^n}^\times$ ;
$\mathbb{F}_{2^n}^\times$ is a cyclic group of order $2^n - 1$ . If $x$ happens to be a generator, the period reaches the maximum $2^n - 1$ . Such an $f$ is called a primitive polynomial.

The number of primitive polynomials is $\varphi(2^n - 1)/n$ (where $\varphi$ is Euler's function), so they always exist, and there are plenty of them.

A worked example: $f(x) = x^4 + x + 1$ (primitive)

The recurrence is $s_{t+4} = s_t + s_{t+1}$ , with initial state $0001$ .

$\underbrace{0\,0\,0\,1\ 0\,0\,1\,1\ 0\,1\,0\,1\ 1\,1\,1}_{15\ \text{bits}}\ 0\,0\,0\,1\ \cdots$

It repeats from bit 16, with period $15 = 2^4 - 1$ . These 15 bits contain 8 ones and 7 zeros, and a window of length 4 passes through each of the 15 nonzero 4-bit strings exactly once. These are typical properties of an "m-sequence".

By contrast: $f(x) = x^4 + x^3 + x^2 + x + 1$ is irreducible but not primitive (it divides $x^5 - 1$ , so $x$ has order only $5$ ), and starting from $0001$ the period is only $5$ . (Both checked with Python.)

3.3 Berlekamp–Massey: $2n$ bits are enough

Suppose an attacker knows the register length $n$ and sees $2n$ consecutive output bits. Then they can write down $n$ linear equations in $c_0, \dots, c_{n-1}$ and solve them over $\mathbb{F}_2$ .

Recovering a 4-bit LFSR from 8 bits

Intercept the first 8 bits: $s_0 \dots s_7 = 0\,0\,0\,1\,0\,0\,1\,1$ . Let $s_{t+4} = c_0 s_t + c_1 s_{t+1} + c_2 s_{t+2} + c_3 s_{t+3}$ :

$t$	Equation	Result
0	$s_4 = c_0 \cdot 0 + c_1 \cdot 0 + c_2 \cdot 0 + c_3 \cdot 1$ , i.e. $0 = c_3$	$c_3 = 0$
1	$s_5 = c_2 \cdot 1 + c_3 \cdot 0$ , i.e. $0 = c_2$	$c_2 = 0$
2	$s_6 = c_1 \cdot 1 + c_2 s_4 + c_3 s_5$ , i.e. $1 = c_1$	$c_1 = 1$
3	$s_7 = c_0 \cdot 1 + c_1 s_4 + c_2 s_5 + c_3 s_6$ , i.e. $1 = c_0$	$c_0 = 1$

This gives $s_{t+4} = s_t + s_{t+1}$ , that is $f(x) = x^4 + x + 1$ . The attacker can now predict all future keystream.

The Berlekamp–Massey algorithm goes further: without knowing $n$ in advance, it finds the shortest LFSR generating a given sequence in $O(N^2)$ time. This shortest length is called the sequence's linear complexity. An LFSR with a 128-bit key has linear complexity at most 128, and is seen through with just 256 bits of known plaintext.

Interestingly, this algorithm was originally invented for decoding Reed–Solomon and BCH codes.

3.4 How to fix it: add nonlinearity

Nonlinear combination: merge the outputs of several LFSRs through a nonlinear Boolean function (such as the Geffe generator, though a poor design falls to correlation attacks);
Nonlinear filtering: take values from several positions of one LFSR and feed them into a nonlinear function;
Irregular stepping: use one LFSR to control whether another advances (the approach of A5/1).

The goal in every case is to push the linear complexity close to the sequence length, while avoiding statistical correlation between the output and any single LFSR.

Summary

Layer	Key points
Intuition	Cells shift left and XOR feeds back; a few gates generate a long sequence
Algebra	Each step $=$ multiplying by $x$ in $\mathbb{F}_2[x]/(f)$ ; a primitive polynomial gives the maximum period $2^n - 1$
Weakness	Linear: $2n$ bits solve the entire register (Berlekamp–Massey)
Reality	Excellent for GPS, scrambling and CRC; encryption must add nonlinearity, with A5/1 and CSS as cautionary tales

Linear Feedback Shift Registers: Primitive Polynomials over F2[x]\mathbb{F}_2[x]F2​[x] and Stream Ciphers