Shamir's Secret Sharing

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.

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">{{hint}}</p>
<div class="controls">
  <label>{{lbl_secret}} <input id="secret" type="number" min="0" max="96" value="42"></label>
  <label>{{lbl_threshold}}
    <select id="k"><option>2</option><option selected>3</option><option>4</option></select>
  </label>
  <button id="split" type="button">{{btn_split}}</button>
</div>
<div id="shares" class="shares"></div>
<div class="btns">
  <button id="recover" type="button">{{btn_recover}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{press_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; }

// Code not found

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.

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 $k^{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.

"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.

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.