LINEAR FEEDBACK SHIFT REGISTER shift, XOR the taps in, and a long pseudorandom run falls out
An LFSR is a row of bits that shifts each tick, with the new bit set to the XOR of a few chosen positions (the taps). From a single seed it cycles through a long pseudorandom-looking sequence; if the taps correspond to a primitive polynomial, an n-bit register hits every nonzero state before repeating — the maximal period 2ⁿ−1. Cheap in hardware, the classic keystream generator — and, alone, fatally weak.
THE TECHNIQUE new bit = XOR of taps; maximal period 2^n - 1
An 8-bit LFSR with taps for a primitive polynomial cycles through all 255 nonzero states before returning to its seed. Watch it shift, and count the period: live demo
HISTORY & CREDIT Golomb 1967; Tausworthe 1965
“A long-period LFSR keystream is secure.” — no, catastrophically not. It is linear: Berlekamp-Massey recovers the entire register and taps from just 2n output bits. LFSRs are keystream ingredients (combined nonlinearly, clocked irregularly), never a stream cipher on their own. cited
1965–67 · Tausworthe (1965) and Solomon Golomb — “Shift Register Sequences” (1967): the theory of maximal-length (m-)sequences and their randomness properties. 1969 · Berlekamp / Massey — the algorithm that breaks a pure LFSR from 2n bits (linear complexity). use · A5/1 (GSM), E0 (Bluetooth), CRC (dart 075!) — the same shift-and-XOR register, tapped differently, everywhere in hardware.
The maximal period needs a primitive tap polynomial — the same algebraic condition (a generator of the multiplicative group of GF(2ⁿ)) that makes a full-cycle exist; the wrong taps give a short, useless cycle. Golomb 1967
RECOMMEND FOR I-13 the maximal period, computed
On the canonical compiler the 8-bit LFSR cycles through all 255 nonzero states — pure shift and XOR:
$ i13 run lfsr.i13 # new bit = (s>>7) xor (s>>5) xor (s>>4) xor (s>>3), then shift
seed = 1 -> 2 -> 4 -> ...
period = 255 -- maximal (2^8 - 1): every nonzero state visited once before repeating
Recommend: the LFSR is LIT and pure I-13 bitwise — verified an 8-bit register reaches the maximal period 255 from its seed, the new bit being the XOR of four tapped positions (>> and & only). It is the cheapest keystream/PRNG primitive and the literal cousin of the corpus’s CRC keeper (dart 075) — the same shift-and-XOR register, tapped for a different job. The honest warning ships with it: alone it is broken by Berlekamp-Massey in 2n bits, so it is an ingredient (nonlinear combiner, irregular clock), never a cipher by itself.