Shamir's Secret Sharing

How it works: hide the secret in a polynomial

You want to split a vault master key so that any 3 of your 5 board members can open it, but no 2 of them — not even if they collude over dinner — can learn a single bit. Adi Shamir's 1979 insight, two years after he co-invented RSA, was that this is just geometry. Two points determine a line. Three points determine a parabola. In general, k points determine a unique degree-(k−1) polynomial, and any fewer leave it completely undetermined.

So encode the secret s as the value the polynomial takes at x = 0 — the constant term. Pick the other k−1 coefficients uniformly at random:

f(x) = s + a₁·x + a₂·x² + … + a_(k−1)·x^(k−1)   (mod p)

Hand participant i the point (i, f(i)) for distinct nonzero x-values i = 1, 2, …, n. That pair is their share. To recover the secret, collect any k shares, fit the one polynomial that passes through all of them — Lagrange interpolation — and evaluate it at x = 0. You never need the full polynomial; the standard trick computes f(0) directly:

s = f(0) = Σⱼ  yⱼ · Πₘ≠ⱼ  (0 − xₘ) / (xⱼ − xₘ)   (mod p)

The magic is on the other side. With only k−1 points, for every candidate secret s' there is exactly one polynomial of degree k−1 passing through your points and hitting s' at x = 0. Every secret is equally consistent with what you hold. That is why the scheme is information-theoretically secure — not "hard to break with current computers," but provably impossible, like a one-time pad.

Why a finite field, not real numbers

If you ran the scheme over ordinary integers, the size of a share would leak information: a huge y-value implies large coefficients, which biases the distribution of likely secrets. The fix is to do all arithmetic in a finite field — most often the integers modulo a prime p larger than both the secret and n, or the byte field GF(2⁸) for software that shares data one byte at a time.

Working mod p buys two things at once. First, uniformity: every share is a uniformly random field element, so it leaks nothing. Second, exact division. Lagrange interpolation divides by (xⱼ − xₘ); in a field, "division" is multiplication by the modular inverse, computed once with the extended Euclidean algorithm or Fermat's little theorem. There is no rounding, so reconstruction is bit-exact every time — a property floating-point interpolation cannot promise.

When to reach for it (and when not to)

• Splitting a root key or recovery seed. HashiCorp Vault unseals with a 3-of-5 Shamir split by default; hardware-wallet seed backups (SLIP-0039) shard a master secret into mnemonic shares across people or locations.
• Threshold custody and dead-man's switches. Release a document only when k trustees agree; no single trustee can act alone, and you survive losing n−k of them.
• Bootstrapping multi-party computation. Shamir shares are the standard input encoding for MPC protocols like BGW, because addition and (with care) multiplication can be done directly on shares.

Reach for something else when you need repeated use of the shares — plain Shamir is one-shot, since reconstruction reveals the secret to whoever assembles it. It also provides no integrity: a wrong or malicious share silently corrupts the result without any error. And it is not encryption — the secret must already be small enough (or pre-encrypted with a symmetric key that you then share). If you only ever need all parties present, additive XOR-splitting is simpler and faster.

Shamir vs. other secret-splitting schemes

	Shamir (threshold)	XOR / additive	Blakley (geometric)	Verifiable SS (Feldman)	Reed-Solomon erasure
Threshold k of n	any k ≤ n	k = n only	any k ≤ n	any k ≤ n	any k ≤ n
Share size vs. secret	1× (ideal)	1×	k× (a hyperplane)	1× + commitments	1×
Security model	information-theoretic	information-theoretic	information-theoretic	computational hiding	none (no secrecy)
Detects bad shares	no	no	no	yes	yes (error correction)
Math	polynomial interpolation	bitwise XOR	intersecting hyperplanes	Shamir + DLog commitments	polynomial over GF(2⁸)
Reconstruct cost	O(k²)	O(n)	O(k³) (linear solve)	O(k²) + verify	O(k²)

Shamir and Reed-Solomon are the same polynomial machine seen from two ends: Reed-Solomon evaluates a data-bearing polynomial to add redundancy you can decode through errors; Shamir evaluates a secret-bearing polynomial whose extra coefficients are pure noise. Blakley's scheme reaches the same threshold property with intersecting hyperplanes, but its shares are k times larger, which is why Shamir won in practice.

What the numbers actually say

• Share size is ideal. Each share is the same size as the secret (plus a tiny x-index). A 3-of-5 split of a 256-bit key over GF(2⁸) produces five 33-byte shares — 32 secret bytes + 1 index byte — regardless of the threshold. There is no n× blow-up.
• Reconstruction is cheap. Lagrange interpolation at x = 0 is O(k²) field multiplications. For a 3-of-5 scheme that is roughly 9 multiplies and 3 inversions per byte — microseconds, even byte-by-byte over a 32-byte key.
• The threshold is exact, not fuzzy. k−1 shares give you literally zero bits of advantage; the k-th share takes you from a 1/q guess to certainty. There is no gradual leakage as you accumulate shares — a property unique to information-theoretic schemes.
• Field choice bounds n. Over GF(2⁸) you have 255 usable nonzero x-values, so n ≤ 255. Need more participants? Move to GF(2¹⁶) (n ≤ 65 535) or a large prime field.

JavaScript implementation

This version works in a prime field — readable, and correct for secrets and indices smaller than the prime. (Production byte-wise code uses GF(2⁸) log tables; see the variants section.)

// 13th Mersenne prime — fits any secret < 2^521.
const P = (2n ** 521n) - 1n;

const mod = (a, m) => ((a % m) + m) % m;

// Modular inverse via Fermat: a^(p-2) mod p  (p prime).
function inv(a, m) {
  let result = 1n, base = mod(a, m), e = m - 2n;
  while (e > 0n) {
    if (e & 1n) result = (result * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return result;
}

// Split secret into n shares; any k reconstruct.
function split(secret, k, n) {
  const coeffs = [BigInt(secret)];           // a0 = secret
  for (let i = 1; i < k; i++)                 // a1..a_{k-1} random
    coeffs.push(mod(randomBig(), P));
  const shares = [];
  for (let x = 1n; x <= BigInt(n); x++) {     // x = 0 is the secret — never give it out
    let y = 0n, pow = 1n;
    for (const c of coeffs) { y = mod(y + c * pow, P); pow = mod(pow * x, P); }
    shares.push([x, y]);
  }
  return shares;                              // [[x1,y1], ...]
}

// Lagrange-interpolate the shares back to f(0).
function combine(shares) {
  let secret = 0n;
  for (let j = 0; j < shares.length; j++) {
    const [xj, yj] = shares[j];
    let num = 1n, den = 1n;
    for (let m = 0; m < shares.length; m++) {
      if (m === j) continue;
      const xm = shares[m][0];
      num = mod(num * (0n - xm), P);          // (0 - x_m)
      den = mod(den * (xj - xm), P);          // (x_j - x_m)
    }
    secret = mod(secret + yj * num % P * inv(den, P), P);
  }
  return secret;
}

function randomBig() {                         // 64 random bytes -> BigInt
  const b = crypto.getRandomValues(new Uint8Array(64));
  return b.reduce((acc, x) => (acc << 8n) | BigInt(x), 0n);
}

Two details that bite newcomers. First, the random coefficients must come from a CSPRNG (crypto.getRandomValues, not Math.random) — predictable coefficients let an attacker with one share fit the polynomial. Second, never issue a share at x = 0: its y-value is the secret.

Python implementation

import secrets
from functools import reduce

P = 2**521 - 1  # large prime field

def split(secret, k, n):
    """Split `secret` into n shares; any k reconstruct it."""
    coeffs = [secret] + [secrets.randbelow(P) for _ in range(k - 1)]
    def f(x):
        return sum(c * pow(x, i, P) for i, c in enumerate(coeffs)) % P
    return [(x, f(x)) for x in range(1, n + 1)]  # x = 0 withheld (it's the secret)

def combine(shares):
    """Lagrange-interpolate f(0) from any k shares."""
    secret = 0
    for j, (xj, yj) in enumerate(shares):
        num, den = 1, 1
        for m, (xm, _) in enumerate(shares):
            if m == j:
                continue
            num = (num * (0 - xm)) % P     # numerator:   prod (0 - x_m)
            den = (den * (xj - xm)) % P     # denominator: prod (x_j - x_m)
        # division in a field = multiply by modular inverse (Python 3.8+)
        secret = (secret + yj * num * pow(den, -1, P)) % P
    return secret

# --- round trip ---
shares = split(0xC0FFEE, k=3, n=5)
assert combine(shares[:3])      == 0xC0FFEE   # any 3 work
assert combine([shares[0], shares[2], shares[4]]) == 0xC0FFEE
assert combine(shares[:2])      != 0xC0FFEE   # 2 shares -> garbage, by design

Note pow(den, -1, P) — Python 3.8 gained native modular inverse, so you no longer hand-roll the extended Euclidean algorithm. The final assertion is the whole point: two shares produce a uniformly random field element with no relationship to the real secret.

Variants worth knowing

GF(2⁸) byte sharing. Real libraries don't use one giant prime; they share each byte independently in the byte field, using precomputed log/antilog tables so multiplication is two lookups and an add. A share is then the same length as the secret plus one index byte — this is what sss, Vault, and most wallet tools ship.

Verifiable Secret Sharing (Feldman, Pedersen). Plain Shamir trusts the dealer and the share-holders. Feldman publishes commitments g^aᵢ to the polynomial coefficients so everyone can check their share without learning others'; Pedersen's variant keeps the secret information-theoretically hidden too. The price is computational hiding and extra group operations.

Proactive secret sharing. Periodically re-randomize all shares (re-share the zero polynomial and add it in) so an attacker who slowly compromises holders over months never assembles k shares from the same epoch. Vital for long-lived keys.

Hierarchical / weighted thresholds. Give a CEO 3 shares and each VP 1, so "the CEO plus one VP" or "any four VPs" both reach a threshold of 4. Implemented by handing some holders multiple distinct x-points, or with Tassa's disjunctive hierarchical scheme.

SLIP-0039. The standard for sharding cryptocurrency mnemonic seeds: a two-level Shamir split (groups, then members within groups) with checksums and a passphrase, designed so humans can transcribe shares on paper without silent corruption.

Common bugs and edge cases

• Using a weak RNG for coefficients. Math.random() / random.random() are predictable; an attacker who guesses the coefficients recovers the secret from a single share. Always use a CSPRNG.
• Issuing a share at x = 0. f(0) is the secret itself. Index participants from 1, and store the x-value with the share — interpolation needs to know which x each y belongs to.
• Duplicate x-coordinates. Two shares at the same x make Lagrange divide by zero, and two holders with the same x are effectively one participant toward the threshold.
• Secret larger than the field. If the secret exceeds the prime (or 255 in GF(2⁸)), it wraps and reconstruction returns the wrong value silently. Pick the field to bound the secret, or share byte-by-byte.
• Floating-point interpolation. Doing Lagrange over doubles instead of a field accumulates rounding error and occasionally reconstructs the wrong secret. All arithmetic must be exact, modular integer math.
• Trusting reconstruction without integrity. A single corrupted or malicious share silently produces a different value with no error flag. If holders may be adversarial, layer on verifiable sharing or attach a MAC of the secret.
• Forgetting it's one-shot. Once k shares are combined, that party knows the secret forever. Reconstruct inside a secure enclave, or rotate to a fresh secret afterward.