View source for 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.

[[Category:Cryptography]]
[[Category:Mathematics]]
[[Category:Technology]]