Introduction

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 LL 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: 2L2L output bits are always enough to uniquely determine an LFSR of length LL — and his algorithm finds it in O(n2)O(n^2) time.

The theorem is exact and proven. Give Berlekamp–Massey 2L2L 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.

Crack a Stream

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 LL of the sequence equals the length of that register.

<p class="hint">A hidden LFSR produced this bit stream. Click <b>Run Berlekamp–Massey</b> to find the shortest shift register that generates it. Each step shows how the algorithm updates its candidate polynomial when a discrepancy appears.</p>
<div class="stream-row" id="stream-display"></div>
<div class="info-row">
  <span class="label">Linear complexity <i>L</i>:</span>
  <span id="lc-value" class="value">–</span>
  <span class="label" style="margin-left:1.2rem;">Feedback polynomial:</span>
  <span id="poly-value" class="value">–</span>
</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="btn-run" type="button">Run Berlekamp–Massey</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Berlekamp–Massey algorithm over GF(2).
// Given a binary sequence s[0..n-1], finds the shortest LFSR (length L, feedback polynomial C) such that C * s = 0 over GF(2).
// Reference: Massey, J.L. (1969) "Shift-register synthesis and BCH decoding."
//
// State: C = current polynomial (array of 0/1, C[0]=1 always)
//        L = current length
//        B = previous polynomial before last length change
//        b = discrepancy at that last change
//        x = how many steps since last length change
// Each step, compute discrepancy d = sum_{i=1}^{L} C[i]*s[n-i] (mod 2).
// If d=0: no change, x++.
// If d=1: T = C; C = C XOR (d/b)*x-shift(B); if 2L<=n: L=n+1-L; B=T; b=d; x=1; else x++.
// Over GF(2): d/b = d*b^{-1} = 1 (since b is always 1 in GF(2)).

function berlekampMassey(s) {
  const n = s.length;
  let C = [1], B = [1], L = 0, x = 1;
  const steps = [];
  for (let i = 0; i < n; i++) {
    // Compute discrepancy
    let d = s[i];
    for (let j = 1; j <= L; j++) d ^= (C[j] || 0) & s[i - j];
    d &= 1;
    if (d === 0) {
      steps.push({ i, d, L, C: C.slice(), changed: false });
      x++;
    } else {
      const T = C.slice();
      // C = C XOR x-shift(B)  (multiply B by z^x then XOR into C)
      const newLen = Math.max(C.length, B.length + x);
      while (C.length < newLen) C.push(0);
      for (let j = 0; j < B.length; j++) C[j + x] ^= B[j];
      const changed = (2 * L <= i);
      if (changed) { L = i + 1 - L; B = T; x = 1; }
      else x++;
      steps.push({ i, d, L, C: C.slice(), changed });
    }
  }
  return { L, C, steps };
}

// Generate a stream from an LFSR with given taps (1-indexed positions, GF(2) feedback)
function genLFSR(seed, taps, len) {
  const s = [];
  const reg = seed.slice();
  const L = reg.length;
  for (let i = 0; i < len; i++) {
    s.push(reg[L - 1]);
    let fb = 0;
    taps.forEach(t => { fb ^= reg[L - t]; });
    reg.pop();
    reg.unshift(fb);
  }
  return s;
}

// Predefined interesting streams (with non-trivial but short LFSRs)
const STREAMS = [
  { bits: genLFSR([1,0,1,1], [1,4], 16),   desc: 'LFSR seed=1011, taps={1,4}, L=4' },
  { bits: genLFSR([1,1,0,1,0], [2,5], 20),  desc: 'LFSR seed=11010, taps={2,5}, L=5' },
  { bits: genLFSR([1,0,0,1,1,0], [1,6], 18),desc: 'LFSR seed=100110, taps={1,6}, L=6' },
];
let streamIdx = 0;
let stream = [];
let bmResult = null;
let stepIdx = 0;
let running = false;

function polyStr(C) {
  // C[0]=1 always; C[k] = coefficient of z^k
  let parts = ['1'];
  for (let k = 1; k < C.length; k++) if (C[k]) parts.push('z^' + k);
  return parts.join(' + ');
}

function renderStream(highlightIdx, dissonantIdx) {
  const el = document.getElementById('stream-display');
  el.innerHTML = '';
  stream.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = 'bit' + (i <= highlightIdx ? ' consumed' : '') +
                  (i === dissonantIdx ? ' dissonant' : '');
    d.textContent = b;
    el.appendChild(d);
  });
}

function appendLog(html, cls) {
  const el = document.getElementById('log');
  const p = document.createElement('p');
  if (cls) p.className = cls;
  p.innerHTML = html;
  el.appendChild(p);
  el.scrollTop = el.scrollHeight;
}

function updateInfo(L, C) {
  document.getElementById('lc-value').textContent = L;
  document.getElementById('poly-value').textContent = polyStr(C);
}

function resetDisplay() {
  stream = STREAMS[streamIdx % STREAMS.length].bits;
  streamIdx++;
  bmResult = berlekampMassey(stream);
  stepIdx = 0;
  running = false;
  renderStream(-1, -1);
  document.getElementById('log').innerHTML = '';
  updateInfo('–', [1]);
  document.getElementById('lc-value').textContent = '–';
  document.getElementById('poly-value').textContent = '–';
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
}

function applyStep(idx) {
  const st = bmResult.steps[idx];
  renderStream(st.i, st.d ? st.i : -1);
  updateInfo(st.L, st.C);
  if (st.d === 0) {
    appendLog(fmt('Bit %i% = %v%: prediction correct, no change.', { i: st.i, v: stream[st.i] }), 'ok');
  } else {
    const msg = fmt('Bit %i% = %v%: <b>dissonance!</b> Update polynomial%v2%.', { i: st.i, v: stream[st.i], v2: st.changed ? ', ' + fmt('increase L to %L%', { L: st.L }) : '' });
    appendLog(msg, 'dis');
  }
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (!bmResult || stepIdx >= bmResult.steps.length) return;
  applyStep(stepIdx++);
  if (stepIdx >= bmResult.steps.length) {
    appendLog(fmt('Done. Linear complexity L = %L%.', { L: bmResult.L }), 'ok');
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
  }
});

document.getElementById('btn-run').addEventListener('click', () => {
  if (!bmResult) return;
  // Run all remaining steps quickly
  while (stepIdx < bmResult.steps.length) { applyStep(stepIdx++); }
  appendLog(fmt('Done. Linear complexity L = %L%.', { L: bmResult.L }), 'ok');
  document.getElementById('btn-step').disabled = true;
  document.getElementById('btn-run').disabled = true;
});

document.getElementById('btn-reset').addEventListener('click', resetDisplay);

resetDisplay();
// Log the true LFSR description for transparency
const trueDesc = STREAMS[(streamIdx - 1) % STREAMS.length].desc;
appendLog(fmt('Stream generated by: %trueDesc%', { trueDesc: trueDesc }), '');
Result
Console

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 2L2^L possible feedback polynomials. But Berlekamp–Massey does it in O(n2)O(n^2) steps with pure linear algebra over F2\mathbb{F}_2, the field with just two elements: 0 and 1.

The Real Complexity

How hard is the shift-register synthesis problem?

  • Generating a sequence from an LFSR of length LL costs O(L)O(L) per bit — one XOR of chosen taps.
  • Brute force over all feedback polynomials of degree ≤L\leq L means trying 2L2^L candidates — hopeless for even L=50L = 50.
  • Berlekamp–Massey solves it in O(n2)O(n^2). Given nn 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 F2\mathbb{F}_2.
  • The linear complexity theorem (Massey, 1969) is the decisive result: the shortest LFSR that generates a sequence of length nn has length exactly L(n)L(n), and L(n)≤n/2L(n) \leq n/2. Furthermore 2L(n)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.

Where It Matters

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 2L2L 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.

Conclusion

Berlekamp–Massey carries a lesson about linearity: linear structure is beautiful but fragile. An LFSR produces a sequence that looks random — yet 2L2L bits of it hand you the entire future of the stream. The algorithm needs only O(n2)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/berlekamp-massey/Content licensed under CC BY-NC 4.0.