Shamir's Secret Sharing

Shamir’s Secret Sharing

Introduction

Some secrets are too important to keep in one place, and too dangerous to give to everyone. A master key can be lost with the one person who holds it. If five people each hold a full copy, any one of them can leak it. Shamir’s secret sharing solves both problems. It splits a secret into n pieces, called shares, so that any k of them rebuild the secret, and any k - 1 of them tell you nothing about it.

The scheme is called a threshold scheme, and k is the threshold. With k = 3 and n = 5, any three of five people can open the vault together. Two people, even if they cheat, learn exactly as much as a stranger. This is not a computational promise. It holds even for an attacker with unlimited computing power, as the section on perfect secrecy shows.

The idea behind it fits in one sentence: a polynomial of degree k - 1 is fixed by k points, and not by fewer. The secret is the value of such a polynomial at zero, and the shares are other points on it. This guide builds the scheme from scratch, first with ordinary numbers modulo a prime and then with bytes in the field GF(256), which is what real tools use.

Table of Contents

• History and Use Today
• The Idea: A Secret Hidden in a Polynomial
• Splitting the Secret
• Rebuilding the Secret
• Why Fewer Shares Reveal Nothing
• Working with Bytes: GF(256)
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History and Use Today

Adi Shamir described the scheme in 1979, in a two-page paper titled “How to Share a Secret” in Communications of the ACM. Wikipedia lists the same year as the date of its first formulation. The paper is short because the idea is short. The mathematics it uses is Lagrange interpolation, which finds a polynomial from points on it.

Shamir’s secret sharing is used to share the keys that protect other secrets. Wikipedia names several uses. One is sharing a key that decrypts the root key of a password manager. Others are recovering a user key for encrypted email, sharing a passphrase that recreates the master secret of a cryptocurrency wallet, and recovering the combination of a physical safe.

Two real systems show the two common ways to build it:

• HashiCorp Vault. Its Go package shamir works on bytes in GF(2^8). Every byte of the secret gets its own random polynomial, and the coefficients come from the random source of the Go standard library, crypto/rand. A share is the list of polynomial values for one x coordinate, followed by one extra byte that holds that x. The x values are a random selection from 1 to 255. The code refuses a threshold below 2 and a share count or threshold above 255.
• SLIP-39. This specification of SatoshiLabs describes how to back up a wallet seed as a set of word lists. It also uses GF(256), with the field defined by the same polynomial as in AES. It stores the secret at x = 255 and a digest of the secret at x = 254, and it never uses x = 0 for a share. The reason is a real attack, described in the section on limitations.

The Idea: A Secret Hidden in a Polynomial

Two points define a line. Three points define a parabola, and four points define a cubic curve. In general, k points with different x values define exactly one polynomial of degree at most k - 1. Give a parabola only two of its points, and infinitely many parabolas still pass through them.

Shamir turns this fact into a secret-keeping device. To share a secret s with threshold k, pick a random polynomial of degree k - 1 whose value at zero is the secret:

f(x) = s + a1*x + a2*x^2 + ... + a(k-1)*x^(k-1)

The numbers a1 to a(k-1) are chosen at random. The secret s is the constant term, which is also f(0). The shares are the points (1, f(1)), (2, f(2)), up to (n, f(n)). Anyone with k of these points can find the polynomial, and with it f(0). Anyone with fewer points is left with an enormous family of polynomials, and every possible secret is among them.

The arithmetic is done in a finite field, not with ordinary real numbers. In the original scheme, this is the integers modulo a prime p, where p must be larger than the secret and larger than the number of shares. Working in a finite field matters for secrecy. With ordinary integers there is no way to choose the coefficients uniformly, so a few shares would leak information about the size of the secret. Modulo a prime, the coefficients can be uniform, and every residue stays equally likely.

Splitting the Secret

Take the example that Wikipedia uses. The prime is p = 1613, the secret is 1234, the threshold is k = 3, and the number of shares is n = 6. A polynomial of degree 2 needs two random coefficients. The example uses 166 and 94:

f(x) = 1234 + 166*x + 94*x^2 (mod 1613)

Each share is one evaluation. For x = 3, the calculation is 1234 + 166*3 + 94*9 = 1234 + 498 + 846 = 2578, and then 2578 - 1613 = 965, because the result is taken modulo 1613. The six shares are:

(1, 1494), (2, 329), (3, 965), (4, 176), (5, 1188), (6, 775)

Each of six people receives one point. The polynomial itself is destroyed after the split. Nobody has to remember it, and nobody can be forced to reveal it, because nobody keeps it.

Rebuilding the Secret

To rebuild the secret, collect k shares and find f(0). You do not need the whole polynomial. Lagrange interpolation gives the value at zero directly:

f(0) = sum over the chosen shares i of  y_i * w_i
w_i  = product over the other chosen shares j of  x_j / (x_j - x_i)

The weight w_i depends only on the x coordinates of the chosen shares, not on their values. It is a fraction, so in the finite field it needs a modular inverse. The weight is the value at zero of a helper polynomial that equals 1 at x_i and 0 at every other chosen x_j. That is why the weighted sum reproduces the polynomial at zero.

Take the shares at x = 2, x = 4, and x = 5. The three weights are as follows:

• For x = 2: w = (4*5) / ((4-2)*(5-2)) = 20 / 6, which is 541 modulo 1613.
• For x = 4: w = (2*5) / ((2-4)*(5-4)) = 10 / (-2), which is 1608 modulo 1613.
• For x = 5: w = (2*4) / ((2-5)*(4-5)) = 8 / 3, which is 1078 modulo 1613.

Multiplying each weight by its share value gives the terms 559, 733, and 1555. Their sum is 2847, and modulo 1613 this is 1234. That is the secret. Any other group of three shares gives the same result, because they all lie on the same polynomial.

Why Fewer Shares Reveal Nothing

Suppose an attacker has only two shares of a threshold-3 scheme. The attacker can try any guess g for the secret. The two shares and the point (0, g) are three points with different x values, so exactly one polynomial of degree at most 2 passes through all of them. That polynomial is a perfectly valid candidate. It is just as likely to be the real one as the polynomial for any other guess.

So every value in the field survives, and each one is consistent with exactly one polynomial. Because the real coefficients were chosen uniformly at random, the possible secrets are all equally likely. The two shares carry no information at all. Wikipedia calls this perfect secrecy, and also information-theoretic security. It adds that the one-time pad can be viewed as the case with two shares in total and a threshold of two.

The visualizer shows the effect. If you combine fewer shares than the threshold, it still computes the interpolation, but it reports that the result is only one of p equally possible secrets. In the example, shares 1 and 3 interpolate to 952, which is not the secret and means nothing.

Two practical properties follow from the construction, and Wikipedia lists both. The scheme is minimal, because each share is no larger than the secret. It is also flexible. Different people can receive different numbers of shares, so a president with three shares can open the safe alone, while three secretaries with one share each must work together.

Working with Bytes: GF(256)

Real secrets are bytes, not numbers below a small prime. A convenient field for bytes is GF(256), the field with 256 elements. Each element is a byte, read as a polynomial of degree at most 7 with coefficients of 0 or 1.

• Addition in GF(256) is XOR. Subtraction is the same operation, so a - b = a xor b.
• Multiplication multiplies the two polynomials and then reduces the result modulo x^8 + x^4 + x^3 + x + 1. This is the polynomial of AES. In bytes it is 0x11B, so the reduction step XORs with 0x11B whenever the product reaches 9 bits.
• Division multiplies by the inverse. Every nonzero byte a satisfies a^255 = 1, so its inverse is a^254.

For example, 57 * 83 = c1, and the inverse of 53 is ca.

To share a byte string, give every byte its own random polynomial of degree k - 1. The share for x = 1 is the list of values f_j(1) for every byte j, so a share is exactly as long as the secret. Reconstruction uses the same Lagrange weights as before, computed once and applied to every byte.

Both Vault and SLIP-39 use this field. The SLIP-39 specification explains the choice. The arithmetic is easy to implement in any programming language, many implementations already exist because AES uses the same field, and the field is byte-oriented. The cost is that a scheme over GF(256) allows at most 255 shares, because each share needs its own nonzero x value.

Interactive Visualizer

The visualizer above runs this exact algorithm. The first variant uses a prime field with small numbers, so that every value fits on the screen. Enter the secret, the random coefficients, the number of shares, the prime, and the list of shares to combine. The number of coefficients sets the threshold, which is one more than their count. The log shows the polynomial, each share with its calculation, and the Lagrange weight and term for every chosen share.

The second variant works on text in GF(256). The coefficients come from a small repeatable generator with a seed, so that the example gives the same shares every time. This generator is for demonstration only. Real code must take its coefficients from a secure random source. Choose fewer shares than the threshold to see what happens: the log then shows that every secret remains possible.

A Worked Example

The default of the second variant shares the word HELLO, which is the bytes 48 45 4c 4c 4f. The threshold is 3, and there are 5 shares. The generator with seed 2026 gives the ten random bytes 1f 97 6f ee ce 53 be 66 09 77. The first two belong to the first byte, so its polynomial is 48 1f 97, in hexadecimal. That means f(x) = 48 + 1f*x + 97*x^2 in GF(256).

The five shares are:

x = 1: c0c4d19431
x = 2: 1c0e9ca89a
x = 3: 948f0170e4
x = 4: 87801eb85a
x = 5: 0f01836024

To rebuild, take the shares for x = 2, x = 4, and x = 5. The weights in GF(256) are d0, 03, and d2. For the first byte, the terms are d0 * 1c = 18 xor 03 * 87 = 92 xor d2 * 0f = c2, and the XOR of these three values is 48, the letter H. The same weights give the other four bytes. With only the shares for x = 1 and x = 2, the interpolation gives the bytes 7d 82 ea 80 a1, which are not the word, and every other five-byte string would be equally likely.

Python Implementation

This is a complete Shamir secret sharing, in both versions. The prime-field part follows the formulas above. The GF(256) part uses shifts and XOR for the multiplication, and the inverse is a^254.

# shamir.py
# Shamir's secret sharing (Adi Shamir, 1979), in two versions:
#   1. over a prime field Z_p, the original scheme for one number
#   2. over GF(256), the version used by real tools, one polynomial for each byte
# Teaching code. The "random" coefficients come from a tiny generator so that
# the examples can be repeated. Real code must take them from a secure source.


# ---------- version 1: a prime field ----------

def evaluate(coefficients, x, p):
    """f(x) = c0 + c1*x + c2*x^2 + ... (mod p), by Horner's rule."""
    result = 0
    for c in reversed(coefficients):
        result = (result * x + c) % p
    return result


def split_prime(secret, extra, n, p):
    """Shares (1, f(1)) ... (n, f(n)) of f(x) = secret + extra[0]*x + extra[1]*x^2 + ..."""
    coefficients = [secret] + list(extra)
    return [(x, evaluate(coefficients, x, p)) for x in range(1, n + 1)]


def lagrange_at_zero(xs, i, p):
    """The weight of share i when f(0) is rebuilt: product of x_j / (x_j - x_i) over j != i."""
    num, den = 1, 1
    for j, xj in enumerate(xs):
        if j != i:
            num = num * xj % p
            den = den * (xj - xs[i]) % p
    return num * pow(den, -1, p) % p


def combine_prime(shares, p):
    """f(0) from the given shares, by Lagrange interpolation."""
    xs = [x for x, _ in shares]
    return sum(y * lagrange_at_zero(xs, i, p) for i, (_, y) in enumerate(shares)) % p


# ---------- version 2: GF(256) ----------

def gf_mul(a, b):
    """Multiply two bytes as polynomials, modulo x^8 + x^4 + x^3 + x + 1 (the AES polynomial)."""
    result = 0
    while b:
        if b & 1:
            result ^= a
        a <<= 1
        if a & 0x100:
            a ^= 0x11B
        b >>= 1
    return result


def gf_inv(a):
    """The inverse of a nonzero byte is a^254, because a^255 = 1."""
    result = 1
    for _ in range(254):
        result = gf_mul(result, a)
    return result


def gf_evaluate(coefficients, x):
    result = 0
    for c in reversed(coefficients):
        result = gf_mul(result, x) ^ c  # addition in GF(256) is XOR
    return result


def demo_random_bytes(seed, count):
    """A small xorshift generator. Repeatable, and NOT secure."""
    state = seed & 0xFFFFFFFF or 1
    out = []
    for _ in range(count):
        state ^= (state << 13) & 0xFFFFFFFF
        state ^= state >> 17
        state ^= (state << 5) & 0xFFFFFFFF
        out.append(state >> 24)
    return out


def split_bytes(secret, k, n, seed):
    """Share a byte string. Every byte gets its own polynomial of degree k-1."""
    random = demo_random_bytes(seed, len(secret) * (k - 1))
    polynomials = []
    for j, byte in enumerate(secret):
        polynomials.append([byte] + random[j * (k - 1):(j + 1) * (k - 1)])
    shares = []
    for x in range(1, n + 1):
        shares.append((x, bytes(gf_evaluate(poly, x) for poly in polynomials)))
    return shares, polynomials


def gf_lagrange_at_zero(xs, i):
    num, den = 1, 1
    for j, xj in enumerate(xs):
        if j != i:
            num = gf_mul(num, xj)
            den = gf_mul(den, xj ^ xs[i])  # subtraction is XOR too
    return gf_mul(num, gf_inv(den))


def combine_bytes(shares):
    """Rebuild the secret from shares [(x, bytes), ...]."""
    xs = [x for x, _ in shares]
    weights = [gf_lagrange_at_zero(xs, i) for i in range(len(xs))]
    secret = bytearray()
    for j in range(len(shares[0][1])):
        value = 0
        for weight, (_, y) in zip(weights, shares):
            value ^= gf_mul(weight, y[j])
        secret.append(value)
    return bytes(secret)


if __name__ == "__main__":
    # The textbook example: p = 1613, secret 1234, f(x) = 1234 + 166x + 94x^2, six shares, any three rebuild it
    p = 1613
    shares = split_prime(1234, [166, 94], 6, p)
    print("shares:", shares)
    print("rebuilt from shares 2, 4, 5:", combine_prime([shares[1], shares[3], shares[4]], p))
    print("rebuilt from shares 1, 3:   ", combine_prime([shares[0], shares[2]], p), "(two shares are not enough)")

    # The same idea, one byte at a time
    shares, polynomials = split_bytes(b"HELLO", 3, 5, 2026)
    print("polynomial for the first byte:", polynomials[0])
    for x, y in shares:
        print("share", x, y.hex())
    print("rebuilt from shares 2, 4, 5:", combine_bytes([shares[1], shares[3], shares[4]]))
    print("rebuilt from shares 1, 2:   ", combine_bytes([shares[0], shares[1]]), "(two shares are not enough)")

Running it produces this output:

shares: [(1, 1494), (2, 329), (3, 965), (4, 176), (5, 1188), (6, 775)]
rebuilt from shares 2, 4, 5: 1234
rebuilt from shares 1, 3:    952 (two shares are not enough)
polynomial for the first byte: [72, 31, 151]
share 1 c0c4d19431
share 2 1c0e9ca89a
share 3 948f0170e4
share 4 87801eb85a
share 5 0f01836024
rebuilt from shares 2, 4, 5: b'HELLO'
rebuilt from shares 1, 2:    b'}\x82\xea\x80\xa1' (two shares are not enough)

I checked this code in several independent ways before writing it up. The six shares of the textbook example equal the points printed in the Wikipedia article, and each of the 20 groups of three shares rebuilds 1234. On 400 random settings, the Lagrange formula gives the same result as solving the linear system with Gaussian elimination. With a prime of 101 and two shares of a threshold-3 scheme, all 101 candidate secrets fit one polynomial each.

For GF(256), the multiplication equals the six multiplication tables published in the Wikipedia article on Rijndael MixColumns, for the factors 2, 3, 9, 11, 13, and 14, in all 256 entries each. It equals the mult function of HashiCorp Vault, ported line by line, for all 65,536 pairs of bytes, and the inverse equals Vault’s inverse for all 255 nonzero bytes. A table of powers of 3 gives the same products, and the AES example column db 13 53 45 becomes 8e 4d a1 bc. On 300 random settings, every group of k shares rebuilds the secret. With two shares of a threshold-3 scheme, all 256 values of a byte fit exactly one polynomial each. The visualizer code matches 607 test vectors computed by this Python code, and I ran its page in a simulated browser. I did not test the demonstration generator for statistical quality, because it is not meant to be secure.

Limitations

This is a faithful teaching version of the scheme, not a production one:

• Randomness. The coefficients must come from a cryptographically secure generator. The repeatable generator in the code is for examples only.
• No verification of shares. Wikipedia lists this as a weakness. During reassembly the scheme cannot tell whether a share is correct. A shareholder who submits a wrong share makes the result wrong, and nobody learns who cheated. Verifiable secret sharing schemes exist to detect this, but they are a different scheme.
• A single point of failure remains. The secret exists in one place when it is split, and again in one place when it is rebuilt. Anyone who observes either moment sees the whole secret. Wikipedia names multisignature schemes as one way to avoid that.
• Index zero is forbidden. Nobody may receive a share with x = 0, because f(0) is the secret itself. SLIP-39 explains the attack when an implementation forgets this check. If a program does not check that x is nonzero, an attacker who can change a stored share can replace (x, y) with (0, y). The interpolation then always returns y, whatever the other shares are. This is why that specification stores the secret at index 255 instead.
• Size limits. GF(256) allows at most 255 shares. The prime-field version needs a prime larger than the secret, so long secrets need either a large prime or a split into blocks.
• Constant-time arithmetic. The code here branches on the data it multiplies. The mult function in Vault has no such branches.

Security Status

Shamir’s scheme is not an encryption algorithm that an attacker could break with enough effort. Its secrecy for fewer than k shares is perfect, as shown above, so no future advance in computing or mathematics changes it. That also means that quantum computers do not change it.

The weaknesses are all around the scheme. The dealer must be trusted. The secret must be handled safely when it is split and when it is rebuilt. Shares must be stored separately, and enough of them must survive: with k of n needed, losing n - k + 1 shares loses the secret forever. And the shares carry no authentication, so a damaged or forged share goes unnoticed.

For a real system, use a reviewed implementation, such as the one in a mature secrets manager, or a specification such as SLIP-39, which adds identifiers, checksums, and a digest of the secret to the bare scheme.

FAQ

Is Shamir’s secret sharing the same as encrypting the secret?

No, they are different things. Encryption hides a secret behind a key that someone must then protect. Secret sharing has no key. It spreads the secret itself over several holders, so that no single holder, and no small group, has anything useful. A common design combines both: encrypt the data with a key, and share the key.

Why does the scheme need a prime or a field?

Because the arithmetic must be exact, and every value must be equally likely. In a finite field, every nonzero element has an inverse, so the Lagrange weights exist, and the coefficients can be chosen uniformly. With plain integers, no uniform choice exists, and the shares would leak information about the size of the secret.

What happens if I lose some shares?

As long as k shares remain, nothing is lost. If fewer than k remain, the secret cannot be rebuilt by anyone, including the original holder of the secret. This is why the threshold balances two risks: a low k is easier to attack, and a high k is easier to lose.

Can a share be larger than the secret?

In the standard scheme it cannot. Wikipedia lists minimality as a property: the size of each share does not exceed the size of the secret. Real formats add a few bytes for the share index, as Vault does with one extra byte, or for identifiers and checksums, as SLIP-39 does.

Can I add more shares later?

Yes, for the same polynomial. Any new point on it is a valid share, as long as its x value is new and nonzero. If you want to change the threshold, you must make a new polynomial and issue new shares.

Is the generator in the visualizer secure?

No, it is not secure. It is a small repeatable generator, so that the examples give the same numbers every time. A real implementation must use the random source of the operating system.

References

1. Shamir, Adi. “How to Share a Secret.” Communications of the ACM, volume 22, number 11, November 1979, pages 612 to 613.

2. Wikipedia. “Shamir’s secret sharing.” Available at: https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing

3. HashiCorp Vault, Go package shamir, file shamir.go. Available at: https://github.com/hashicorp/vault/blob/main/shamir/shamir.go

4. SatoshiLabs. “SLIP-0039: Shamir’s Secret-Sharing for Mnemonic Codes.” Available at: https://github.com/satoshilabs/slips/blob/master/slip-0039.md

5. National Institute of Standards and Technology. “Advanced Encryption Standard (AES).” FIPS 197, defines the field GF(2^8) and the polynomial x^8 + x^4 + x^3 + x + 1. Available at: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf

6. Wikipedia. “Rijndael MixColumns.” Published multiplication tables for GF(2^8). Available at: https://en.wikipedia.org/wiki/Rijndael_MixColumns