Linear feedback shift register

A linear feedback shift register (LFSR) is a deterministic bit-sequence generator constructed from a shift register whose input bit is a linear function of its previous state. Despite its simplicity — a handful of XOR gates and flip-flops — an LFSR with properly chosen feedback taps can produce sequences with maximal period and excellent statistical properties, making it the foundational component of many classical stream cipher designs.

The mathematics of LFSRs is governed by polynomials over the finite field GF(2). The feedback polynomial determines the state-transition matrix, and a primitive polynomial yields a maximal-length sequence that cycles through all 2^n − 1 nonzero states before repeating. These sequences exhibit uniform bit distribution, low autocorrelation, and a predictable but long period. From a statistical perspective, they appear random; from a cryptographic perspective, they are catastrophically weak.

The weakness is structural: the LFSR's state is a linear system, and its entire future output can be recovered from a small number of known plaintext-ciphertext pairs via the Berlekamp-Massey algorithm. This makes a raw LFSR unsuitable for cryptographic use. Designers have historically addressed this by combining multiple LFSRs with nonlinear filtering functions, as in the A5/1 GSM cipher, or by using irregular clocking to break the linearity. These modifications increase resistance but do not eliminate the fundamental problem: the linear substrate remains, and algebraic attacks can exploit it when the nonlinear combiner is not sufficiently complex.

The LFSR is best understood not as a cryptographic primitive but as a cautionary example of how statistical randomness and cryptographic unpredictability diverge. It is a perfect random number generator by every classical statistical test, yet it is trivially predictable. This distinction — between passing tests and resisting adversaries — is the boundary that separates non-cryptographic PRNGs from cryptographically secure ones.