Shamir's Secret Sharing, in depth: polynomials over finite fields, Lagrange at zero, a worked example, GF(256) byte shares and verifiable sharing

Threshold sharing with a polynomial

A (k, n) threshold scheme splits a secret s into n shares so that any k shares recover s and any k-1 reveal nothing. Shamir's construction picks a random polynomial of degree k-1 whose constant term is the secret: f(x) = s + a1 x + ... + a(k-1) x^(k-1). Share i is the point (i, f(i)). Any k distinct points determine a unique polynomial of degree at most k-1, so k holders can rebuild f and read f(0) = s.

Secrecy is the surprising part, and the argument is short. Fix any k-1 shares and any candidate secret s'. Adding the point (0, s') gives k points, which determine exactly one polynomial of degree at most k-1. So for every candidate secret there is exactly one choice of the random coefficients consistent with what the k-1 holders see, and since the coefficients were uniform, every candidate is equally likely. The k-1 holders learn nothing, not even a hint, whatever their computing power. This is information-theoretic security, not a hardness assumption.

Why a finite field

The secrecy argument needs every value to be equally likely, which is only true in a finite field. Over the integers, shares leak: f(x) grows with x, so its size and parity constrain the coefficients, and combining shares narrows the range of s. Over real numbers you also lose exactness to rounding. Work modulo a prime p larger than any secret and every nonzero element has an inverse, uniform coefficients give uniform outputs, and Lagrange interpolation is exact.

Reconstruction only needs the polynomial's value at zero, so you do not rebuild f at all. Lagrange interpolation evaluated at x = 0 gives s = sum over i of y_i times L_i, where L_i = product over j not equal to i of x_j / (x_j - x_i), all modulo p. Division is multiplication by a modular inverse, which Python computes with pow(d, -1, p); the extended Euclidean algorithm is what runs underneath.

Splitting and combining in Python

The implementation below uses the Mersenne prime 2^521 - 1, large enough to hold a 256-bit key as an integer without wrapping. Coefficients come from the secrets module, never from random, whose Mersenne Twister output is predictable after observing enough of it. Note that the top coefficient may be zero; forcing it nonzero would make the distribution slightly non-uniform for no benefit.

import secrets

P = 2**521 - 1          # a Mersenne prime; the secret must be smaller than P

def eval_poly(coeffs, x, p):
    y = 0
    for a in reversed(coeffs):                   # Horner's rule
        y = (y * x + a) % p
    return y

def split(secret, k, n, p=P):
    if not 0 <= secret < p:
        raise ValueError("secret must lie in [0, p)")
    if not 1 < k <= n < p:
        raise ValueError("need 1 < k <= n < p")
    coeffs = [secret] + [secrets.randbelow(p) for _ in range(k - 1)]
    return [(x, eval_poly(coeffs, x, p)) for x in range(1, n + 1)]

def combine(shares, p=P):
    xs = [x for x, _ in shares]
    if len(set(xs)) != len(xs) or any(x % p == 0 for x in xs):
        raise ValueError("x-coordinates must be distinct and nonzero")
    secret = 0
    for xi, yi in shares:
        num = den = 1
        for xj in xs:
            if xj != xi:
                num = num * xj % p
                den = den * (xj - xi) % p
        secret = (secret + yi * num * pow(den, -1, p)) % p
    return secret

Worked example by hand

Use a small field so you can check every step: p = 2089, secret s = 1234, threshold k = 3, n = 5 shares, and random coefficients a1 = 166, a2 = 94. The polynomial is f(x) = 1234 + 166x + 94x^2 mod 2089, and the five shares are (1, 1494), (2, 1942), (3, 489), (4, 1313), (5, 236). For example f(3) = 1234 + 498 + 846 = 2578, which reduces to 489 modulo 2089.

Now recover s from shares x = 2, 4 and 5. Each Lagrange weight is the product of the other x-values over the product of their differences, reduced with a modular inverse.

The last column sums to 5612288, which is 1234 modulo 2089: the secret. A useful self-check is that the weights themselves sum to 1 modulo p, since interpolating the constant polynomial 1 must return 1.

Change one share by a single unit, say y at x = 4 becomes 1314, and the same computation returns 1229. No error, no warning, a confident wrong answer. Plain Shamir has no integrity at all, which the next sections deal with.

Byte-wise sharing in GF(2^8)

Real secrets are byte strings, and a prime field forces you to encode them as one big number. The common alternative is to share each byte independently in GF(2^8), the field of 256 elements used by AES. Addition is XOR, multiplication is carry-less multiplication reduced by the polynomial 0x11B, and every share is exactly as long as the secret plus a one-byte x-coordinate. Because subtraction is also XOR, the Lagrange weight becomes the product of x_j over the product of (x_j XOR x_i). The field has 255 nonzero elements, so n is at most 255.

def gf_mul(a, b):                    # multiply in GF(2^8), AES polynomial 0x11B
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        if a & 0x100:
            a ^= 0x11B
        b >>= 1
    return r

def gf_inv(a):                       # a^254 = a^-1 for nonzero a
    if a == 0:
        raise ZeroDivisionError("0 has no inverse")
    r = 1
    for _ in range(254):
        r = gf_mul(r, a)
    return r

def split_bytes(secret: bytes, k, n):
    if not 1 < k <= n <= 255:
        raise ValueError("need 1 < k <= n <= 255")
    out = {x: bytearray() for x in range(1, n + 1)}
    for byte in secret:
        coeffs = [byte] + list(secrets.token_bytes(k - 1))
        for x in out:
            y = 0
            for a in reversed(coeffs):
                y = gf_mul(y, x) ^ a     # addition is XOR
            out[x].append(y)
    return {x: bytes(v) for x, v in out.items()}

def combine_bytes(shares: dict):
    xs = list(shares)
    length = len(shares[xs[0]])
    result = bytearray()
    for pos in range(length):
        s = 0
        for xi in xs:
            num = den = 1
            for xj in xs:
                if xj != xi:
                    num = gf_mul(num, xj)
                    den = gf_mul(den, xj ^ xi)   # subtraction is XOR too
            s ^= gf_mul(shares[xi][pos], gf_mul(num, gf_inv(den)))
        result.append(s)
    return bytes(result)

Both implementations above are checked when this page is built: round trips through different subsets of shares, and every nonzero GF(2^8) element times its inverse equals one. They are teaching code. gf_mul branches on secret data, which leaks timing; production code uses constant-time table-free multiplication or bit-sliced arithmetic. For the modular arithmetic underneath, see modular exponentiation.

Integrity and verifiable sharing

Plain Shamir trusts two parties it should not: the dealer, who could hand out inconsistent shares, and the holders, who could submit wrong ones at recovery. Two standard fixes exist.

• Integrity tag. Store a hash or MAC of the secret alongside the shares, or share an authenticated encryption key and keep the ciphertext. After reconstruction, check the tag; with more than k shares available, try subsets until one verifies, which also identifies the bad share.
• Feldman verifiable secret sharing. In a group of prime order q with generator g, the dealer publishes commitments C_j = g^(a_j) for each coefficient. Holder i checks g^(y_i) = product over j of C_j^(i^j). A bad share fails the check before recovery. The cost is that C_0 = g^s reveals s to anyone who can solve discrete logarithms, so secrecy becomes computational.
• Pedersen verifiable secret sharing. Uses a second generator and a blinding polynomial so that commitments reveal nothing about s even to an unbounded adversary, at the price of a binding property that rests on discrete-log hardness instead.

Refresh, labelling and operations

Shares are linear: if every holder adds their shares of s1 and s2 at the same x, they hold valid shares of s1 + s2. That property powers proactive refresh. Periodically, deal a fresh random polynomial with constant term zero and have each holder add its value to their share. The secret is unchanged, old shares become useless when combined with new ones, and an attacker must now steal k shares within one refresh period. Changing k or n, by contrast, needs a re-split or a resharing protocol.

Operationally, label every share with a scheme identifier, the threshold, its x-coordinate and a version, so mismatched shares are rejected rather than silently combined. Store shares on independent media and with independent people. Remember that recovery puts the whole secret in one memory space; if that is unacceptable, use threshold signatures or multi-party computation, where the key is used without ever being reassembled.

Failure modes

• Using random for coefficients. Predictable coefficients let an attacker with fewer than k shares solve for the secret.
• Giving out x = 0. That share is the secret itself. Also reject duplicate x values.
• Secret larger than the field. It wraps modulo p and recovers as a different number.
• Integer arithmetic. Shares computed without a modulus leak the secret's size and residues.
• Re-using the polynomial for a new secret. Two sharings with the same coefficients let holders subtract shares and learn the difference of the secrets.
• No integrity check. One wrong share yields a wrong secret with no error, as the worked example showed.

Trade-offs and alternatives

For n-of-n, XOR splitting is simpler: n-1 random strings and their XOR with the secret. Shamir earns its complexity when you need a threshold below n. Share size equals secret size, so sharing a large file is wasteful; Krawczyk's 1993 construction encrypts the data, shares only the key with Shamir and spreads the ciphertext with an erasure code, giving computational security with much smaller shares. Interpolation costs O(k^2) field operations per secret, which is nothing for keys; batching many secrets shares the weight computation across all of them. Related polynomial tools are covered in fast polynomial multiplication and polynomial hashing.

What to do next

1. Implement the prime-field version above and reproduce the worked example by hand.
2. Test that every k-subset of shares recovers the secret and every (k-1)-subset does not constrain it.
3. Switch to a byte-wise GF(2^8) implementation for real keys, using a constant-time library.
4. Add an integrity tag or Feldman commitments before anyone relies on recovery.
5. Label shares with scheme, threshold, x and version, and reject mismatches.
6. Plan proactive refresh and a recovery drill with the actual share holders.
7. If the key must never be reassembled, evaluate threshold signatures instead.