Introduction

Suppose a vault holds something so dangerous that no single person should be able to open it — but you also can't require everyone to be present, because people get sick, travel, or quit. You want a rule like: any three of the five trustees, together, can open it; any two, no matter how clever, cannot.

In 1979 the cryptographer Adi Shamir (the "S" in RSA) gave an exact, provably perfect answer to this. His scheme turns a secret into n shares so that any k of them rebuild it instantly — and any k−1 of them reveal literally nothing, not even a hint.

The whole idea rests on one fact you already know from school geometry: two points determine a line, three points determine a parabola, and in general k points pin down exactly one polynomial of degree k−1. Fewer than k points leave infinitely many curves still possible.

Split & Recover

Choose a secret number and a threshold k. The demo builds a random degree-(k−1) polynomial whose constant term is the secret, then hands out shares — points on that curve. Pick which shares to combine and rebuild the secret by Lagrange interpolation.

<p class="hint">Pick a <b>secret</b> and a threshold <b>k</b>. We build a random degree-(k&minus;1) polynomial whose value at x=0 is the secret, then hand out 5 <b>shares</b> (points on it). Tick any shares and recover the secret. With <b>k</b> ticked it always lands; with <b>k&minus;1</b> it can't &mdash; every secret stays possible.</p>
<div class="controls">
  <label>Secret <input id="secret" type="number" min="0" max="96" value="42"></label>
  <label>Threshold k
    <select id="k"><option>2</option><option selected>3</option><option>4</option></select>
  </label>
  <button id="split" type="button">Split into shares</button>
</div>
<div id="shares" class="shares"></div>
<div class="btns">
  <button id="recover" type="button">Recover from ticked shares</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Press "Split into shares" to begin.</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; }
.controls { display: flex; gap: .8rem; flex-wrap: wrap; align-items: flex-end; margin-bottom: .6rem; }
label { font-size: .85rem; font-weight: 600; display: flex; flex-direction: column; gap: .25rem; }
input, select { font: 600 14px system-ui, sans-serif; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; }
input { width: 90px; }
.shares { display: grid; grid-template-columns: repeat(auto-fit, minmax(110px, 1fr)); gap: .5rem; margin: .5rem 0; }
.share { display: flex; align-items: center; gap: .5rem; background: #e8eef3; border: 1px solid #cdd9e3;
         border-radius: 8px; padding: .5rem .6rem; font: 700 14px ui-monospace, monospace; color: #1d3557; cursor: pointer; user-select: none; }
.share input { width: auto; }
.share.on { background: #d2e7d8; border-color: #0a7d33; }
.status { font-size: .98rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shamir secret sharing over the prime field GF(P). The secret is the constant
// term a0 of a random degree-(k-1) polynomial. A share is a point (x, f(x) mod P).
// Any k shares recover a0 by Lagrange interpolation at x=0; any k-1 shares leave
// every secret equally possible (information-theoretic / perfect secrecy).
const P = 97;            // prime field; secret must be < P
const N = 5;             // number of shares handed out
let coeffs = [], shares = [], K = 3, SECRET = 42;

const mod = x => ((x % P) + P) % P;
function inv(a){ // modular inverse via Fermat: a^(P-2) mod P
  a = mod(a); let r = 1, e = P - 2;
  while(e > 0){ if(e & 1) r = mod(r * a); a = mod(a * a); e >>= 1; }
  return r;
}
function evalPoly(c, x){ let y = 0; for(let i = c.length - 1; i >= 0; i--) y = mod(y * x + c[i]); return y; }

// Lagrange interpolation evaluated at x=0 over the given points.
function recoverAtZero(pts){
  let secret = 0;
  for(let i = 0; i < pts.length; i++){
    let num = 1, den = 1;
    for(let j = 0; j < pts.length; j++){ if(i === j) continue;
      num = mod(num * (0 - pts[j].x));      // (0 - xj)
      den = mod(den * (pts[i].x - pts[j].x)); // (xi - xj)
    }
    secret = mod(secret + pts[i].y * mod(num * inv(den)));
  }
  return secret;
}

function split(){
  SECRET = Math.max(0, Math.min(P - 1, parseInt(document.getElementById('secret').value || '0', 10)));
  document.getElementById('secret').value = SECRET;
  K = parseInt(document.getElementById('k').value, 10);
  coeffs = [SECRET];
  for(let i = 1; i < K; i++) coeffs.push(Math.floor(Math.random() * P)); // random a1..a(k-1)
  shares = [];
  for(let x = 1; x <= N; x++) shares.push({ x, y: evalPoly(coeffs, x) });
  renderShares();
  setStatus(fmt('Built a degree-%v% polynomial. Tick shares and recover. (k = %K%)', { v: K - 1, K: K }), '');
}

function renderShares(){
  const box = document.getElementById('shares'); box.innerHTML = '';
  shares.forEach((s, idx) => {
    const d = document.createElement('label'); d.className = 'share';
    const cb = document.createElement('input'); cb.type = 'checkbox'; cb.dataset.i = idx;
    cb.addEventListener('change', () => { d.classList.toggle('on', cb.checked); });
    const span = document.createElement('span'); span.textContent = 'P' + s.x + ' = (' + s.x + ', ' + s.y + ')';
    d.appendChild(cb); d.appendChild(span); box.appendChild(d);
  });
}

function selected(){
  return [...document.querySelectorAll('#shares input:checked')].map(cb => shares[+cb.dataset.i]);
}

function recover(){
  if(shares.length === 0){ setStatus('Split a secret first.', 'bad'); return; }
  const pts = selected();
  if(pts.length === 0){ setStatus('Tick some shares to combine.', 'bad'); return; }
  const guess = recoverAtZero(pts);
  if(pts.length >= K){
    setStatus(fmt('Recovered with %length% shares (k = %K%): secret = %guess%%v%', { length: pts.length, K: K, guess: guess, v: guess === SECRET ? '  ✓ correct!' : '' }), 'ok');
  } else {
    // With fewer than k points, count how many of the P secrets are still consistent.
    setStatus(fmt('Only %length% of %K% shares. These points fit a curve through every one of the %P% possible secrets — they reveal nothing. (This combo would interpolate to %guess%, but that is meaningless: any secret is equally possible.)', { length: pts.length, K: K, P: P, guess: guess }), 'bad');
  }
}

document.getElementById('split').addEventListener('click', split);
document.getElementById('recover').addEventListener('click', recover);
document.getElementById('reset').addEventListener('click', () => {
  shares = []; coeffs = []; document.getElementById('shares').innerHTML = '';
  setStatus('Press "Split into shares" to begin.', '');
});
function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }
split();
Result
Console

Notice the sharp threshold. With any k shares, interpolation lands on the exact secret every time. With k−1 shares, every possible secret remains equally consistent with what you hold — the demo shows that fewer than k points fit infinitely many curves, so the leftover share leaks nothing. All arithmetic is done modulo a prime so the security is exact, not approximate.

The Real Complexity

What makes Shamir's construction special is how secure it is.

  • Rebuilding is easy. Given any k shares, Lagrange interpolation reconstructs the degree-(k−1) polynomial — and hence the secret at x=0 — in about k2k^{2} steps. Fast and exact.
  • Breaking it is impossible — not merely hard. With k−1 shares, for every candidate secret there is exactly one polynomial of degree k−1 that passes through your points and hits that secret at x=0. All secrets stay equally likely. This is information-theoretic security: no computer, however powerful, and no future algorithm can do better than a blind guess.
  • It does not rely on hardness assumptions. Unlike RSA factoring or the discrete logarithm, Shamir's secrecy is unconditional — it would survive even a working quantum computer, because there is simply no information to extract.
  • The threshold is razor-sharp. k shares give everything; k−1 give nothing. There is no gradual leak in between.

Shamir published this in How to Share a Secret (1979), and it remains one of the cleanest results in cryptography: a problem solved completely, with a proof of perfection rather than a bet on intractability.

Where It Matters

"No single point of failure, no single point of betrayal" is exactly what custody of critical keys demands, and Shamir's scheme is the standard tool:

  • Cryptocurrency custody: hardware wallets and exchanges split a master key into shares held in separate vaults; a quorum is needed to sign, so one stolen share is worthless.
  • Root certificate authorities: the keys that anchor internet trust are ceremonially split among officers, so no individual can mint rogue certificates.
  • Hardware security modules and DNSSEC: the DNS root signing key is famously guarded by a group of trusted "key holders," any sufficient subset of whom can act.
  • Secure multi-party computation: Shamir shares are the building block that lets parties jointly compute on data none of them can see alone.

Understand this scheme and you've met the core idea of threshold cryptography, which builds on the same number theory as the discrete logarithm and RSA factoring.

Conclusion

Shamir's secret sharing is a rare thing in security: a problem with a complete, provably perfect answer. The same fact that two points fix a line and three fix a parabola becomes a way to split trust so that any k people can act and any k−1 are powerless — and the powerlessness is total, guaranteed by mathematics rather than by the cost of cracking it.

So the next time you hear that a vault key is "split five ways, three to open," you'll know it isn't a metaphor. It's a polynomial, a handful of points, and a 1979 proof that fewer than the threshold reveals nothing at all — a guarantee even RSA factoring and the discrete logarithm can only dream of.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/shamir-secret-sharing/Content licensed under CC BY-NC 4.0.