Berlekamp–Massey

Imagine a spy transmitting a secret message encrypted with a stream cipher. The cipher XORs the plaintext with a keystream — a long pseudorandom sequence of bits generated by a tiny piece of hardware called a linear feedback shift register (LFSR). The register holds $L$ bits of secret state. Each clock tick it shifts right, XORing chosen positions together to fill the left cell. The result looks random but is entirely deterministic — and therein lies the fatal flaw.

In 1965, Elwyn Berlekamp invented an algorithm to reconstruct the shortest LFSR consistent with a sequence of symbols observed from a Reed-Solomon decoder. In 1969, James Massey recast it as a shift-register synthesis problem and proved a stunning theorem: $2L$ output bits are always enough to uniquely determine an LFSR of length $L$ — and his algorithm finds it in $O(n^2)$ time.

The theorem is exact and proven. Give Berlekamp–Massey $2L$ bits of keystream and it hands you back the secret internal state — the key — in quadratic time. Stream ciphers built on a single LFSR are completely broken.

Below is a stream of bits produced by a hidden LFSR. Click Run Berlekamp–Massey to watch the algorithm consume the bits one by one and build up the shortest shift register that could have produced them. The linear complexity $L$ of the sequence equals the length of that register.

<p class="hint">{{hint_intro}}</p>
<div class="stream-row" id="stream-display"></div>
<div class="info-row">
  <span class="label">{{label_lc}}</span>
  <span id="lc-value" class="value">–</span>
  <span class="label" style="margin-left:1.2rem;">{{label_poly}}</span>
  <span id="poly-value" class="value">–</span>
</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_new_stream}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stream-row { display: flex; flex-wrap: wrap; gap: 5px; margin-bottom: .6rem; }
.bit { width: 30px; height: 30px; display: flex; align-items: center; justify-content: center;
       font: 700 14px ui-monospace, monospace; border-radius: 6px;
       background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557;
       transition: background .2s; }
.bit.consumed { background: #d0ebff; border-color: #74b9e7; }
.bit.dissonant { background: #ffe0e0; border-color: #e07070; }
.info-row { display: flex; align-items: center; flex-wrap: wrap; gap: .4rem; font-size: .9rem;
            margin-bottom: .5rem; }
.label { color: #555; }
.value { font: 700 14px ui-monospace, monospace; color: #1d3557; }
.log { font-size: .82rem; font-family: ui-monospace, monospace; color: #333;
       background: #f4f6f8; border: 1px solid #dde3ea; border-radius: 8px;
       padding: .5rem .7rem; max-height: 140px; overflow-y: auto; margin-bottom: .6rem; }
.log p { margin: .15rem 0; }
.log .dis { color: #c0392b; }
.log .ok  { color: #1a7d2c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice the asymmetry. Generating the stream takes one XOR per clock tick — trivial. Finding the register from scratch by brute force would require trying all $2^L$ possible feedback polynomials. But Berlekamp–Massey does it in $O(n^2)$ steps with pure linear algebra over $\mathbb{F}_2$, the field with just two elements: 0 and 1.

How hard is the shift-register synthesis problem?

• Generating a sequence from an LFSR of length $L$ costs $O(L)$ per bit — one XOR of chosen taps.
• Brute force over all feedback polynomials of degree $\leq L$ means trying $2^L$ candidates — hopeless for even $L = 50$.
• Berlekamp–Massey solves it in $O(n^2)$. Given $n$ output bits it maintains a current candidate polynomial and updates it whenever the sequence diverges from prediction. The key insight is that each discrepancy (called a dissonance) can be corrected with a single rank-1 update over $\mathbb{F}_2$.
• The linear complexity theorem (Massey, 1969) is the decisive result: the shortest LFSR that generates a sequence of length $n$ has length exactly $L(n)$, and $L(n) \leq n/2$. Furthermore $2L(n)$ bits are both necessary and sufficient — no algorithm, however clever, can do better with fewer bits.
• Optimality is proven. The algorithm is not merely fast; it extracts the maximum possible information from each bit. There is no room for improvement.

This is the algorithm's beautiful character: it sits at the intersection of coding theory and cryptanalysis, and its complexity bound is tight on both sides. Compare it to the discrete logarithm problem — another one-way function — where no efficient algorithm is known. LFSR synthesis is easy precisely because the structure is linear.

The algorithm surfaces wherever a sequence must be explained by the shortest linear recurrence:

• Cryptanalysis of stream ciphers: any cipher whose keystream is generated by a single LFSR is broken by $2L$ known plaintext bits. This is why modern stream ciphers — ChaCha20, for instance — are built from non-linear components.
• Decoding Reed-Solomon and BCH codes: the original Berlekamp algorithm was invented for this purpose. Finding the error-locator polynomial over a finite field is mathematically identical to LFSR synthesis, and Berlekamp–Massey is the standard decoder in CDs, QR codes, and storage controllers.
• Testing pseudorandom number generators: a good PRNG should have high linear complexity. If Berlekamp–Massey finds a short LFSR, the generator is dangerously predictable.
• Sequence analysis in algebraic coding: the algorithm computes the linear complexity profile of a sequence, a key metric in stream cipher design.

The duality — the same algorithm both breaks ciphers and fixes corrupted data — makes Berlekamp–Massey one of the most elegant results connecting pattern matching in strings to the algebra of finite fields.

Berlekamp–Massey carries a lesson about linearity: linear structure is beautiful but fragile. An LFSR produces a sequence that looks random — yet $2L$ bits of it hand you the entire future of the stream. The algorithm needs only $O(n^2)$ steps, the bound is tight, and the proof is clean.

The consequence for cryptography is clear: stream ciphers must introduce non-linearity, or they fall to a first-year linear algebra student armed with this algorithm. And in coding theory, the same mathematics that breaks ciphers also rescues corrupted data from scratched CDs and noisy storage channels.

Elegant mathematics does double duty — and knowing which side of the equation you're on is the whole game.