How to Build Shamir’s Secret Sharing in Python So Any 3 of 5 People Can Recover a Key

A key that lives in one place has one way to fail. Keep it on a single laptop and one dead disk ends your access. Hand a full copy to five colleagues and any one of them can leak it or misuse it alone. Secret sharing removes that choice. You split the key into shares so that any k of them rebuild it, while fewer than k reveal nothing at all.

Adi Shamir published the standard construction in 1979, in a two-page paper in Communications of the ACM. Its abstract promises to “divide data D into n pieces in such a way that D is easily reconstructable from any k pieces”, and says that knowing fewer pieces “reveals absolutely no information about D”. You will meet the idea in production tools. HashiCorp’s Vault documentation says its default configuration “uses an algorithm known as Shamir’s Secret Sharing to split the key into shares”, and the vault operator init reference lists defaults of 5 key shares and a threshold of 3.

In this tutorial you will build that scheme in Python from the algebra up, so that any 3 of 5 people can recover a key. Along the way you will measure what goes wrong when it is built carelessly: a wrong answer that arrives with no error, a seeded random generator that gives away the whole key from a single share, a forged share that rewrites the secret, and a cheating participant who speaks last. You will finish with an encrypted backup that fails loudly instead of silently when a share is wrong, and with the byte-oriented variant that Vault and the SLIP-39 wallet-backup standard use.

What you need before you start

You need Python 3.10 or newer on Windows, macOS or Linux, and an ordinary user account (no administrator rights). Everything here was run on Python 3.13.14 on Windows 11. You should be comfortable with functions, lists and loops, and remember what a polynomial such as 3x + 2 is. No cryptography background is assumed; each term is defined where it first appears.

Make an empty folder for the lab, create a virtual environment inside it, and install three packages. cryptography provides AES-GCM encryption for Step 7, pytest runs the tests in Step 9, and shamir-mnemonic (the SLIP-39 reference implementation) is used for one cross-check in Step 8.

python -m venv .venv
.venv\Scripts\activate
pip install cryptography pytest shamir-mnemonic

On macOS or Linux the activation line is source .venv/bin/activate. Expected result: pip ends with a line that starts Successfully installed and lists the three packages (this tutorial used cryptography 50.0.2, pytest 9.1.1 and shamir-mnemonic 0.3.0). Save every file below into that one folder, in the order the files appear, and keep the first comment line of each file.

Step 1: Why cutting a secret into pieces is not enough

Before the algebra, it helps to see why the obvious approaches fall short. A good scheme needs two properties at once. Any group of k people (the threshold) can rebuild the secret, and any smaller group learns nothing useful. This is called a k-of-n scheme: n shares exist and k of them are needed.

Idea 1: cut the secret into chunks

Say the secret is an 8-digit passcode, and you give the first four digits to person A and the last four to person B. The first half of the script below shows the problem. The second half previews the next idea.

# step1_naive_splits.py
import secrets

passcode = "48291736"                       # an 8-digit passcode to split between two people
half_a, half_b = passcode[:4], passcode[4:]
print("person A holds:", half_a)
print("person B holds:", half_b)
print("guesses A needs to find the rest:", 10 ** 4, "instead of", 10 ** 8)


def xor_bytes(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))


def xor_split(secret: bytes, n: int) -> list[bytes]:
    pads = [secrets.token_bytes(len(secret)) for _ in range(n - 1)]
    last = secret
    for pad in pads:
        last = xor_bytes(last, pad)
    return pads + [last]


def xor_combine(shares: list[bytes]) -> bytes:
    out = bytes(len(shares[0]))
    for share in shares:
        out = xor_bytes(out, share)
    return out


key = secrets.token_bytes(16)
shares = xor_split(key, 3)
print()
print("all 3 XOR shares rebuild the key:   ", xor_combine(shares) == key)
print("2 of 3 XOR shares rebuild the key:  ", xor_combine(shares[:2]) == key)
print("2 of 3 give a value of the right size:", len(xor_combine(shares[:2])) == len(key))

python step1_naive_splits.py

person A holds: 4829
person B holds: 1736
guesses A needs to find the rest: 10000 instead of 100000000

all 3 XOR shares rebuild the key:    True
2 of 3 XOR shares rebuild the key:   False
2 of 3 give a value of the right size: True

Person A is not shut out of the secret. They hold half of it, and the other half is 10,000 guesses away instead of 100,000,000. Every chunk leaks, so chunking breaks the rule that fewer than k shares must learn nothing. Handing everyone a full copy fails the other way: the first person who is careless, bribed or breached exposes the whole secret alone.

Idea 2: XOR the secret with random pads

XOR (written ^ in Python) combines two byte strings so that XOR-ing the result with either input gives back the other. The function xor_split makes n - 1 random byte strings, called pads, and XORs all of them into the secret to produce the last share. Every share on its own looks like random bytes, and any group smaller than all n learns nothing. That is real secrecy.

The output shows the catch. All three shares rebuild the key, but two of three do not (False). XOR sharing is n-of-n: lose one share and the secret is gone with it. The last line is a preview of a theme that returns in Step 3: two shares still produce a value of the right size, so nothing about the result tells you that it is wrong. We want the secrecy of XOR sharing with the loss tolerance of a threshold, and that is what Shamir’s construction gives.

Step 2: The idea behind Shamir’s scheme, a polynomial that hides the secret

The whole trick fits in one sentence: a polynomial of degree k-1 is pinned down by any k points on its graph, and by no fewer. Two points fix a straight line (degree 1). Three points fix a parabola (degree 2). A single point, or two points for a parabola, leaves many different curves that fit.

Shamir’s recipe has three moves. First, pick a random polynomial of degree k-1 whose value at x = 0 is the secret. Second, give share number i the point (i, f(i)) for i from 1 to n. Third, to recover, take any k points, find the one polynomial that passes through them (Lagrange interpolation), and read its value at 0. The secret is f(0), so x = 0 must never be handed out as a share.

Why every calculation happens modulo a prime

Ordinary arithmetic leaks information, as Step 3 will show. Shamir’s fix is to do all arithmetic modulo a prime number p, which means results wrap around like a clock face: after p-1 comes 0 again. The paper’s instruction is that “we pick a prime p which is bigger than both D and n”. Modulo a prime you can add, subtract, multiply and also divide, because every non-zero number has an inverse. Python computes the inverse with the three-argument pow. The documentation says: “If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.” That is all the number theory this tutorial needs.

The core module

Save this as shamir_core.py. It is deliberately small and deliberately has no input checks, because the next steps show why checks are needed.

# shamir_core.py
import secrets

PRIME_521 = 2**521 - 1   # a Mersenne prime, big enough for secrets up to 65 bytes


def evaluate(coeffs, x, p):
    """coeffs[0] + coeffs[1]*x + coeffs[2]*x**2 + ... (mod p), by Horner's rule."""
    result = 0
    for c in reversed(coeffs):
        result = (result * x + c) % p
    return result


def points_from(coeffs, n, p):
    """The shares: the polynomial's value at x = 1 .. n. Never x = 0, that is the secret."""
    return [(x, evaluate(coeffs, x, p)) for x in range(1, n + 1)]


def split_int(secret, k, n, p, randbelow=secrets.randbelow):
    """Hide secret as f(0) of a random polynomial of degree k - 1; return n points."""
    coeffs = [secret] + [randbelow(p) for _ in range(k - 1)]
    return points_from(coeffs, n, p)


def lagrange_weights(xs, x0, p):
    """Weights w_i such that f(x0) = sum(w_i * y_i) for the polynomial through the points."""
    weights = []
    for i, xi in enumerate(xs):
        num, den = 1, 1
        for j, xj in enumerate(xs):
            if i != j:
                num = (num * (x0 - xj)) % p
                den = (den * (xi - xj)) % p
        weights.append(num * pow(den, -1, p) % p)
    return weights


def interpolate(points, x0, p):
    weights = lagrange_weights([x for x, _ in points], x0, p)
    return sum(w * y for w, (_, y) in zip(weights, points)) % p


def combine_int(points, p):
    """Rebuild the secret: the value at x = 0 of the polynomial through the points."""
    return interpolate(points, 0, p)

evaluate computes the polynomial at a point with Horner’s rule (one multiply and one add per coefficient). points_from turns a coefficient list into shares by evaluating at x = 1 to n. split_int puts the secret in coefficient 0 and fills the other k-1 coefficients from secrets.randbelow. The two interpolation functions work together: lagrange_weights computes numbers w_i that depend only on the x values, and then the polynomial’s value at any x0 is the sum of w_i * y_i. combine_int asks for x0 = 0. The randbelow parameter lets a caller swap the random source, which becomes important in Step 6.

A worked example you can check by hand

Use a tiny prime, 7919, the secret 4242 and a 3-of-5 split. To make the numbers reproducible the script fixes the two random coefficients at 1024 and 777, so the polynomial is f(x) = 4242 + 1024x + 777x^2 modulo 7919. A real split picks those coefficients at random.

# step2_worked_example.py
from shamir_core import points_from, combine_int, lagrange_weights

P = 7919                      # a small prime, so every number can be checked by hand
SECRET = 4242
COEFFS = [SECRET, 1024, 777]  # f(x) = 4242 + 1024x + 777x^2 (mod 7919); degree 2 means 3 points are needed

points = points_from(COEFFS, 5, P)
for x, y in points:
    print(f"share {x}: x={x}, y={y}")

print()
for xs in [(1, 2, 3), (2, 4, 5), (1, 3, 5)]:
    subset = [points[x - 1] for x in xs]
    print("shares", xs, "rebuild", combine_int(subset, P))

print()
weights = lagrange_weights([1, 2, 3], 0, P)
print("weights for x = 1, 2, 3:", weights, f"(that is 3, -3, 1 modulo {P})")
y1, y2, y3 = points[0][1], points[1][1], points[2][1]
total = 3 * y1 - 3 * y2 + y3
print(f"3*{y1} - 3*{y2} + 1*{y3} = {total}, and {total} mod {P} = {total % P}")

python step2_worked_example.py

share 1: x=1, y=6043
share 2: x=2, y=1479
share 3: x=3, y=6388
share 4: x=4, y=4932
share 5: x=5, y=5030

shares (1, 2, 3) rebuild 4242
shares (2, 4, 5) rebuild 4242
shares (1, 3, 5) rebuild 4242

weights for x = 1, 2, 3: [3, 7916, 1] (that is 3, -3, 1 modulo 7919)
3*6043 - 3*1479 + 1*6388 = 20080, and 20080 mod 7919 = 4242

Each share is a point on the curve. Any three of them, in any combination, rebuild 4242. You can check one by hand. For the x values 1, 2 and 3 the weights are 3, -3 and 1 (the output prints -3 as 7916, which is the same number modulo 7919). Multiply each weight by its share’s y value, add, and reduce modulo 7919: 3*6043 - 3*1479 + 1*6388 = 20080, and 20080 - 2*7919 = 4242. The weights never change for a given set of x values. Only the y values, and therefore the answer, depend on the secret.

Step 3: Why exactly k shares, and what happens with fewer

This script makes two points. It shows what happens when you combine too few shares, and it proves on a tiny example that fewer than k shares carry no information.

# step3_threshold_secrecy.py
from shamir_core import points_from, combine_int

P, SECRET, COEFFS = 7919, 4242, [4242, 1024, 777]
points = points_from(COEFFS, 5, P)

print("two shares of a 3-of-5 split give:", combine_int(points[:2], P), "| the real secret is", SECRET)
print("no error was raised, and the wrong answer looks like any other number")

# A tiny field (p = 11) and threshold 2, so the whole experiment fits on screen.
# The share at x = 1 is y = s + a1 (mod 11): s is the secret, a1 is the random coefficient.
p = 11
print()
print("share value y for secret s (rows) over every coefficient a1 = 0..10 (columns):")
table = {s: [(s + a1) % p for a1 in range(p)] for s in range(p)}
for s in (0, 5, 10):
    print(f"  s={s:>2}:", table[s])
print("every secret can produce every share value, exactly once:",
      all(sorted(row) == list(range(p)) for row in table.values()))

# The same experiment with ordinary integers (no modulus) and a1 in 0..10.
print()
print("without the modulus a share leaks:")
for s in (0, 5, 10):
    ys = sorted({s + a1 for a1 in range(11)})
    print(f"  s={s:>2}: possible share values {ys[0]} to {ys[-1]}")
y = 3
still_possible = [s for s in range(11) if any(s + a1 == y for a1 in range(11))]
print(f"seeing y = {y} rules out every secret above {max(still_possible)}:", still_possible)

python step3_threshold_secrecy.py

two shares of a 3-of-5 split give: 2688 | the real secret is 4242
no error was raised, and the wrong answer looks like any other number

share value y for secret s (rows) over every coefficient a1 = 0..10 (columns):
  s= 0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  s= 5: [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
  s=10: [10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
every secret can produce every share value, exactly once: True

without the modulus a share leaks:
  s= 0: possible share values 0 to 10
  s= 5: possible share values 5 to 15
  s=10: possible share values 10 to 20
seeing y = 3 rules out every secret above 3: [0, 1, 2, 3]

Two shares of a 3-of-5 split give a wrong answer, silently

The first line of output is the important one. Two points define a straight line, and the code happily reads that line’s value at 0: 2688, a number between 0 and 7918 like any other. Nothing raised an error, because nothing inside a share records how many other shares are needed. Keep this in mind. A plain Shamir implementation has this property, and Step 7 is the fix.

Why fewer than k shares reveal nothing: an exhaustive check

For a field small enough to enumerate, use p = 11 and a threshold of 2. A share at x = 1 is y = s + a1 modulo 11, where s is the secret and a1 is the random coefficient. Each printed row lists the share value you get for one secret as a1 runs from 0 to 10. Every row is a shuffled copy of 0 to 10. So for any secret, each share value appears exactly once, and because a1 is chosen uniformly at random, a share value is equally likely whatever the secret is. Seeing it tells you nothing. Shamir states the same goal in his paper: knowing fewer pieces “leaves D completely undetermined (in the sense that all its possible values are equally likely)”. Cryptographers call this information-theoretic security. It holds against an attacker with unlimited computing power, because there is nothing to compute.

Why the modulus matters: integer arithmetic leaks

The last part of the output repeats the experiment with ordinary integers and no modulus. Now y = s + a1 can never be smaller than s, so seeing y = 3 rules out every secret above 3. With large numbers the same effect still shrinks the range an attacker must search. Wikipedia’s article on the scheme walks through the same leak with integers before it switches to a finite field. The modulus is not decoration.

Step 4: From integers to bytes, a prime you can trust, and shares you can paste into an email

Real secrets are bytes, such as a 32-byte AES key. Python converts bytes to an integer with int.from_bytes, and the prime must be larger than the largest secret. This tutorial uses p = 2**521 - 1, a Mersenne prime (a prime of the form 2**n - 1). Every number of 520 bits or fewer is below it, so secrets of up to 65 bytes fit.

Do not take a prime on trust; test it. The Lucas-Lehmer test says that for an odd prime exponent p, the number M = 2**p - 1 is prime if and only if the sequence s, which starts at 4 and repeats s = s*s - 2 (mod M), reaches 0 after p-2 steps. The script below runs it.

Now the module that turns the integer math into something you can hand to people. Save this as keyshare.py.

# keyshare.py
import secrets
from collections import namedtuple

from shamir_core import PRIME_521, split_int, combine_int

PRIME = PRIME_521
HEX_WIDTH = 132            # a 521-bit value needs 66 bytes, which is 132 hex digits
MAX_SECRET_BYTES = 65      # every 65-byte value is below the prime

Share = namedtuple("Share", "batch k x length y")


class ShareError(ValueError):
    """The shares are malformed, from different splits, repeated or too few."""


class WrongShares(ShareError):
    """The shares are well formed but do not rebuild a possible secret."""


def split_key(secret: bytes, k: int, n: int) -> list[str]:
    if not 1 <= len(secret) <= MAX_SECRET_BYTES:
        raise ShareError(f"secret must be 1 to {MAX_SECRET_BYTES} bytes, got {len(secret)}")
    if not 2 <= k <= n <= 255:
        raise ShareError("need 2 <= k <= n <= 255")
    batch = secrets.token_hex(2)          # tags the shares of one split, like the id in SLIP-39
    points = split_int(int.from_bytes(secret, "big"), k, n, PRIME)
    return [f"ks1-{batch}-{k}-{x}-{len(secret)}-{y:0{HEX_WIDTH}x}" for x, y in points]


def parse_share(text: str) -> Share:
    parts = text.strip().split("-")
    if len(parts) != 6 or parts[0] != "ks1" or len(parts[5]) != HEX_WIDTH:
        raise ShareError("not a ks1 share")
    try:
        share = Share(parts[1], int(parts[2]), int(parts[3]), int(parts[4]), int(parts[5], 16))
    except ValueError:
        raise ShareError("share fields are not numbers") from None
    if not 1 <= share.x <= 255:
        raise ShareError(f"share index must be 1 to 255, got {share.x}")
    if share.k < 2 or not 1 <= share.length <= MAX_SECRET_BYTES or share.y >= PRIME:
        raise ShareError("share values out of range")
    return share


def recover_key(texts: list[str]) -> bytes:
    shares = [parse_share(t) for t in texts]
    if not shares:
        raise ShareError("no shares given")
    if len({(s.batch, s.k, s.length) for s in shares}) != 1:
        raise ShareError("these shares come from different splits")
    if len({s.x for s in shares}) != len(shares):
        raise ShareError("two shares have the same index")
    k, length = shares[0].k, shares[0].length
    if len(shares) < k:
        raise ShareError(f"need {k} shares, got {len(shares)}")
    value = combine_int([(s.x, s.y) for s in shares[:k]], PRIME)
    if value >> (8 * length):
        raise WrongShares(f"the shares do not rebuild a {length}-byte value")
    return value.to_bytes(length, "big")

A share is a text string of the form ks1-BATCH-K-X-LENGTH-Y, where Y is the y value as 132 hex digits (a 521-bit number needs 66 bytes). Each field has a job. BATCH is four random hex digits shared by all the shares of one split, like the identifier that SLIP-39 puts at the start of its shares so that “the user can immediately tell whether the correct shares are being combined”. K travels inside the share so that recover_key can refuse when fewer than K shares are supplied. LENGTH restores leading zero bytes. parse_share rejects indexes outside 1 to 255 and values that are not field elements, and recover_key ends with a size check that Step 5 puts to the test.

# step4_bytes_roundtrip.py
import itertools
import secrets

from keyshare import MAX_SECRET_BYTES, PRIME, ShareError, recover_key, split_key


def lucas_lehmer(exponent: int) -> bool:
    """For an odd prime exponent, 2**exponent - 1 is prime exactly when s ends at 0."""
    m = 2 ** exponent - 1
    s = 4
    for _ in range(exponent - 2):
        s = (s * s - 2) % m
    return s == 0


print("2**13-1 prime:", lucas_lehmer(13), "| 2**11-1 prime:", lucas_lehmer(11), "| 2**521-1 prime:", lucas_lehmer(521))
print("the prime has", PRIME.bit_length(), "bits, so secrets up to", MAX_SECRET_BYTES, "bytes fit")

key = secrets.token_bytes(32)
shares = split_key(key, 3, 5)
print()
print("share header (batch id hidden):", [shares[0].split("-")[0]] + shares[0].split("-")[2:5])
print("share length:", len(shares[0]), "characters")
print("all 10 three-share subsets rebuild the key:",
      all(recover_key(list(c)) == key for c in itertools.combinations(shares, 3)))

print()
secret = b"\x00\x00hello"
as_int = int.from_bytes(secret, "big")
print("naive int round trip: ", as_int.to_bytes((as_int.bit_length() + 7) // 8, "big"))
print("keyshare round trip:  ", recover_key(split_key(secret, 2, 3)[:2]))

try:
    split_key(b"x" * 66, 2, 3)
except ShareError as err:
    print("66-byte secret:", err)

python step4_bytes_roundtrip.py

2**13-1 prime: True | 2**11-1 prime: False | 2**521-1 prime: True
the prime has 521 bits, so secrets up to 65 bytes fit

share header (batch id hidden): ['ks1', '3', '1', '32']
share length: 148 characters
all 10 three-share subsets rebuild the key: True

naive int round trip:  b'hello'
keyshare round trip:   b'\x00\x00hello'
66-byte secret: secret must be 1 to 65 bytes, got 66

Read the output from the top. The Lucas-Lehmer function says that 2**13-1 is prime (it is: 8191), that 2**11-1 is not (2047 is 23 times 89), and that 2**521-1 is, which is the answer we needed. A 32-byte key splits into shares of 148 characters, and the header shows the threshold 3, the index 1 and the length 32. All ten possible groups of three shares rebuild the key.

The last three lines show two gotchas. A naive round trip through int loses the two leading zero bytes of b"\x00\x00hello", because an integer does not remember how many zeros preceded it, and the stored LENGTH fixes that. And a 66-byte secret is refused with a clear message instead of silently wrapping around the prime. Step 7 shows the standard answer for larger data: split a small key, not the data.

Step 5: Mistakes that do not raise errors

This script has three parts. The first shows what the bare math does with bad input, the second shows what keyshare refuses, and the third measures what a single mistyped character does.

# step5_silent_failures.py
import random
import secrets

from keyshare import ShareError, WrongShares, recover_key, split_key
from shamir_core import combine_int, points_from

P, COEFFS = 7919, [4242, 1024, 777]
points = points_from(COEFFS, 5, P)

print("=== the raw math layer")
try:
    combine_int([points[0], points[0], points[1]], P)
except ValueError as err:
    print("same share twice:", err)
off_by_one = [points[0], (2, points[1][1] + 1), points[2]]
print("one share off by 1:", combine_int(off_by_one, P), "(the real secret is 4242, and no error was raised)")

print()

python step5_silent_failures.py

=== the raw math layer
same share twice: base is not invertible for the given modulus
one share off by 1: 4239 (the real secret is 4242, and no error was raised)

Two real failure shapes appear. Giving the same share twice produces ValueError: base is not invertible for the given modulus, which comes from pow, not from your code: two points with the same x give a zero denominator, and zero has no inverse. That is at least loud. A share that is off by one is silent. The answer moves from 4242 to 4239 with no error. The reason is in Step 2: share 2 carries the weight -3, so a change of +1 in its y value moves the result by exactly -3.

# step5_silent_failures.py (continued)
print("=== the keyshare layer")
key = secrets.token_bytes(32)
shares = split_key(key, 3, 5)
other_split = split_key(key, 3, 5)
for label, attempt in [
    ("two shares", shares[:2]),
    ("the same share twice", [shares[0], shares[0], shares[1]]),
    ("shares from two different splits", [shares[0], shares[1], other_split[2]]),
]:
    try:
        recover_key(attempt)
    except ShareError as err:
        print(f"{label}: {type(err).__name__}: {err}")

print()

=== the keyshare layer
two shares: ShareError: need 3 shares, got 2
the same share twice: ShareError: two shares have the same index
shares from two different splits: ShareError: these shares come from different splits

The keyshare layer turns three common slips into clear errors: too few shares, the same share entered twice, and shares from two different splits (the batch field catches that last one). Now the harder case, a single mistyped hex digit.

# step5_silent_failures.py (continued)
print("=== one mistyped hex digit in one share, 1000 tries")
rng = random.Random(7)                       # only chooses which digit to damage
outcome = {"rejected as not a field element": 0, "caught by the size check": 0, "wrong key, no error": 0}
for _ in range(1000):
    key = secrets.token_bytes(32)
    shares = split_key(key, 3, 5)
    y_start = shares[1].rindex("-") + 1
    pos = rng.randrange(y_start, len(shares[1]))
    digit = rng.choice([c for c in "0123456789abcdef" if c != shares[1][pos]])
    typo = shares[1][:pos] + digit + shares[1][pos + 1:]
    try:
        rebuilt = recover_key([shares[0], typo, shares[2]])
    except WrongShares:
        outcome["caught by the size check"] += 1
    except ShareError:
        outcome["rejected as not a field element"] += 1
    else:
        assert rebuilt != key                # a typo never rebuilds the right key
        outcome["wrong key, no error"] += 1
for label, count in outcome.items():
    print(f"{label}: {count} of 1000")
print("every try is accounted for:", sum(outcome.values()) == 1000)

=== one mistyped hex digit in one share, 1000 tries
rejected as not a field element: 17 of 1000
caught by the size check: 517 of 1000
wrong key, no error: 466 of 1000
every try is accounted for: True

The experiment damages one random hex digit of one share, a thousand times, and sorts the outcomes. In this run 17 tries were rejected because the typo made the value at least as large as the prime, 517 were caught by the size check at the end of recover_key, and 466 returned a wrong key with no error at all. Your numbers will differ slightly from these, because the keys are random.

The size check works like this. A wrong rebuilt value is a random-looking number up to 521 bits long, and the check rejects it when it does not fit in 32 bytes. That catches typos in the high digits. A typo in a low digit moves the answer by a small multiple of the change (the weights are small numbers such as 3 and -3), so the result stays under 2²⁵⁶ and passes. Treat the size check as a seat belt for accidents, not as an integrity check. It cannot stop deliberate tampering, as the next step shows, and a 65-byte secret leaves no headroom at all, because about half of all field elements fit in 65 bytes.

Step 6: Three attacks on naive implementations

Each attack below is short, and each is a mistake a first implementation can easily make.

Attack 1: a seeded random generator hands one share the whole key

Python’s random module is deterministic: the same seed always produces the same numbers. Its documentation warns that “The pseudo-random generators of this module should not be used for security purposes. For security or cryptographic uses, see the secrets module.” Suppose a dealer seeds the generator with the clock, a tempting shortcut. An attacker who steals one share, and who knows roughly when the split ran, can replay every possible seed.

# step6a_weak_prng.py
import hashlib
import random
import time

from shamir_core import PRIME_521, split_int

P = PRIME_521


def weak_split(secret, k, n, seed):
    rng = random.Random(seed)                        # seeded from the clock: the mistake
    return split_int(secret, k, n, P, randbelow=rng.randrange)


secret = int.from_bytes(bytes.fromhex("00112233445566778899aabbccddeeff"), "big")   # a fixed 16-byte key
fingerprint = hashlib.sha256(secret.to_bytes(16, "big")).hexdigest()               # stored "to detect typos"

day_start = 1_790_000_000                           # a Unix time in September 2026
dealer_seed = day_start + 4_321                     # the dealer used int(time.time()) when splitting
shares = weak_split(secret, 3, 5, dealer_seed)
x, y = shares[0]                                    # the attacker steals ONE share of a 3-of-5 split
print("shares stolen: 1 of 5, threshold 3")

started = time.perf_counter()
fits_in_16_bytes = []
for tried, seed in enumerate(range(day_start, day_start + 86_400), start=1):
    rng = random.Random(seed)
    a1, a2 = rng.randrange(P), rng.randrange(P)     # replay the dealer's two random coefficients
    candidate = (y - a1 * x - a2 * x * x) % P
    if candidate < 2 ** 128:                        # a wrong seed gives a 521-bit number
        fits_in_16_bytes.append((seed, candidate))
elapsed = time.perf_counter() - started

print("seeds tried:", tried)
print("candidates that fit in 16 bytes:", len(fits_in_16_bytes))
seed_found, recovered = fits_in_16_bytes[0]
print("seed found at offset", seed_found - day_start, "| key recovered:", recovered == secret)
print("matches the stored fingerprint:",
      hashlib.sha256(recovered.to_bytes(16, "big")).hexdigest() == fingerprint)
print(f"elapsed: {elapsed:.1f} s")

python step6a_weak_prng.py

shares stolen: 1 of 5, threshold 3
seeds tried: 86400
candidates that fit in 16 bytes: 1
seed found at offset 4321 | key recovered: True
matches the stored fingerprint: True
elapsed: 0.5 s

The dealer seeded the generator with a Unix time in September 2026 (1,790,000,000 is 21 September 2026). The attacker holds one share of a 3-of-5 split and tries all 86,400 seconds of that day. For each seed the attacker regenerates the two random coefficients, solves for the secret, and keeps candidates that fit in 16 bytes. A wrong seed produces a number of around 521 bits, so only the right seed survives the filter, and the output shows exactly one candidate: the key. The whole search takes about half a second here. The fingerprint, a SHA-256 hash stored beside the shares to detect typos, was not even needed. (For a random 16-byte key such a hash is harmless. For a guessable secret it would be an offline guessing oracle, so do not store one.)

The fix is to take secret coefficients from the secrets module, which the documentation describes as “used for generating cryptographically strong random numbers suitable for managing data such as passwords, account authentication, security tokens, and related secrets”. That is the default in split_int. The randbelow parameter exists so tests can be deterministic, and production code must never pass a seeded generator into it. Vault’s source draws its polynomial coefficients from Go’s crypto/rand. It uses a clock-seeded math/rand only to shuffle the x coordinates, which is fine because those travel with the shares and are not secret.

Attack 2: a share whose index is 0

The secret is the polynomial’s value at x = 0. If an implementation accepts a share with x = 0, that share is the secret, and whoever can edit one stored share can choose the answer.

# step6b_x_zero.py
from keyshare import ShareError, recover_key, split_key
from shamir_core import combine_int, points_from

P, COEFFS = 7919, [4242, 1024, 777]
points = points_from(COEFFS, 5, P)

tampered = [points[0], points[1], (0, 5555)]        # someone rewrote share 3 as the point (0, 5555)
print("honest shares rebuild:      ", combine_int(points[:3], P))
print("with the (0, 5555) share:   ", combine_int(tampered, P), "(whatever the other two shares say)")

shares = split_key(bytes(32), 3, 5)
parts = shares[2].split("-")
parts[3] = "0"                                      # the same trick on a keyshare string
evil = "-".join(parts)
try:
    recover_key([shares[0], shares[1], evil])
except ShareError as err:
    print("keyshare says:", err)

python step6b_x_zero.py

honest shares rebuild:       4242
with the (0, 5555) share:    5555 (whatever the other two shares say)
keyshare says: share index must be 1 to 255, got 0

With the rewritten share the raw math returns 5555, whatever the other two shares say. The SLIP-39 specification describes this exact attack: if an implementation does not check that the index is non-zero, an attacker with write access to one share can change its point from (x, y) to (0, y), and “the resulting shared secret will always be equal to y regardless of the values of the other shares”. SLIP-39 sidesteps the problem by storing its secret at index 255 instead of 0. Our fix is simpler: parse_share rejects any index outside 1 to 255, and the last line of output shows the refusal.

Attack 3: the last person to speak can force the answer

Shares are sometimes read out in a meeting or typed into a shared screen one after another. In a 3-of-5 split, the third person to reveal a share has already seen the first two. That person can compute the real secret, and can also compute a fake share that makes everyone else’s calculation produce a value of their choosing.

# step6c_cheater.py
from shamir_core import combine_int, interpolate, points_from

P, COEFFS = 7919, [4242, 1024, 777]
points = points_from(COEFFS, 5, P)
alice, bob, mallory = points[0], points[1], points[4]      # x = 1, 2 and 5; threshold is 3

# Alice and Bob read their shares out first. Mallory speaks last.
real = combine_int([alice, bob, mallory], P)
wanted = 1337
forged_y = interpolate([(0, wanted), alice, bob], mallory[0], P)

print("Mallory's real share:           ", mallory)
print("secret from the 3 real shares:  ", real)
print("Mallory announces y =", forged_y, "instead of", mallory[1])
print("what Alice and Bob now compute: ", combine_int([alice, bob, (mallory[0], forged_y)], P))
print("what Mallory knows:             ", real)

python step6c_cheater.py

Mallory's real share:            (5, 5030)
secret from the 3 real shares:   4242
Mallory announces y = 3438 instead of 5030
what Alice and Bob now compute:  1337
what Mallory knows:              4242

Mallory holds the share at x = 5. Alice and Bob reveal theirs first. Mallory builds the polynomial through three points: the secret he wants (1337 at x = 0) and Alice’s and Bob’s shares. He evaluates it at x = 5 and announces 3438 instead of his real 5030. Alice and Bob now compute 1337, while Mallory, who used his real share privately, knows that the secret is 4242. As Wikipedia’s article puts it, the scheme has no verifiable secret sharing: it “does not provide a way to verify the correctness of each share being used”. Without a check on the result, the honest parties never learn that anything went wrong.

The defence has two parts. Do not reveal shares in the open: feed them to a combiner that collects all of them before showing anything, so nobody sees the others’ values before committing to their own. And check the rebuilt secret against something the cheater cannot forge, which is the next step. Related reading on the cheating problem is Tompa and Woll’s paper “How to share a secret with cheaters” (Journal of Cryptology, volume 1, issue 3).

Step 7: Put the integrity check in the key, seal a backup with AES-GCM

Shamir’s paper points to the pattern: “In order to protect data we can encrypt it, but in order to protect the encryption key we need a different method”. So split the key, not the data. Encrypt your real material (a credentials file, a database dump, a wallet seed) under a fresh random 32-byte key, and split that key with the code from Step 4. This also removes the 65-byte limit, because the key is 32 bytes however large the data is.

The cipher mode matters. AES-GCM is authenticated encryption: decryption checks an authentication tag and refuses to return anything if the tag does not validate. The cryptography documentation says InvalidTag is raised when the ciphertext has been changed but “will also occur when the key, nonce, or associated data are wrong”. A wrong rebuilt key therefore stops with an exception instead of returning garbage. The same library rules give the nonce rule: “NEVER REUSE A NONCE with a key”. Each call to seal makes a brand-new key that encrypts exactly one message, so a random 12-byte nonce is safe here. The hybrid post-quantum key exchange tutorial uses the same AES-GCM API to prove a derived key works.

Save this as sealed.py.

# sealed.py
import secrets
from itertools import combinations

from cryptography.exceptions import InvalidTag
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

from keyshare import ShareError, WrongShares, recover_key, split_key

AAD = b"sealed-v1"


def seal(plaintext: bytes, k: int, n: int):
    """Encrypt under a fresh random key and split that key. Returns (shares, blob)."""
    key = secrets.token_bytes(32)
    nonce = secrets.token_bytes(12)           # safe: this key encrypts exactly one message
    blob = nonce + AESGCM(key).encrypt(nonce, plaintext, AAD)
    return split_key(key, k, n), blob


def unseal(shares: list[str], blob: bytes) -> bytes:
    key = recover_key(shares)
    try:
        return AESGCM(key).decrypt(blob[:12], blob[12:], AAD)
    except InvalidTag:
        raise WrongShares("authentication failed: wrong or tampered shares") from None


def unseal_any(shares: list[str], blob: bytes, k: int):
    """Try every k-subset. Returns (plaintext, working_subsets, suspect_positions)."""
    working = []
    plaintext = None
    for combo in combinations(range(len(shares)), k):
        try:
            plaintext = unseal([shares[i] for i in combo], blob)
            working.append(combo)
        except ShareError:
            pass
    if plaintext is None:
        raise WrongShares("no subset of these shares opens the blob")
    cleared = {i for combo in working for i in combo}
    suspects = [i for i in range(len(shares)) if i not in cleared]
    return plaintext, len(working), suspects

seal returns the shares and one encrypted blob (nonce first, then ciphertext and tag). unseal rebuilds the key and decrypts, turning an InvalidTag into WrongShares. unseal_any goes one step further: it tries every group of k shares, and a share that appears in no working group is suspect. For 5 shares and a threshold of 3 that is 10 groups. It does not scale to large groups (20 shares with a threshold of 10 is 184,756 groups), so use it for small custodian sets.

# step7_sealed_backup.py
import itertools

from keyshare import HEX_WIDTH, PRIME, ShareError, WrongShares, parse_share
from sealed import seal, unseal, unseal_any
from shamir_core import interpolate

plaintext = b'{"db_password": "correct horse battery staple", "api_key": "sk-demo-0000"}'
shares, blob = seal(plaintext, 3, 5)
print("blob:", len(blob), "bytes | shares:", len(shares))
print("all 10 three-share subsets open it:",
      all(unseal(list(c), blob) == plaintext for c in itertools.combinations(shares, 3)))

try:
    unseal(shares[:2], blob)
except ShareError as err:
    print("two shares:", err)


def typo_at(share: str, from_end: int) -> str:
    i = len(share) - 1 - from_end
    return share[:i] + ("0" if share[i] != "0" else "1") + share[i + 1:]


print()
for label, from_end in [("typo in the last digit", 0), ("typo in a high digit", 120)]:
    try:
        unseal([shares[0], typo_at(shares[1], from_end), shares[2]], blob)
    except WrongShares as err:
        print(f"{label}: {err}")

# Mallory holds share 5, speaks last, and forces the key to 32 bytes of 0x07.
alice, bob, mallory = parse_share(shares[0]), parse_share(shares[1]), parse_share(shares[4])
wanted_key = bytes([7]) * 32
forged_y = interpolate(
    [(0, int.from_bytes(wanted_key, "big")), (alice.x, alice.y), (bob.x, bob.y)], mallory.x, PRIME)
forged = shares[4][:-HEX_WIDTH] + f"{forged_y:0{HEX_WIDTH}x}"
try:
    unseal([shares[0], shares[1], forged], blob)
except WrongShares as err:
    print("forged share:", err)

print()
back, working, suspects = unseal_any(shares[:4] + [forged], blob, 3)
print("opened despite the forgery:", back == plaintext)
print(f"working subsets: {working} of 10 | share numbers in no working subset: {[i + 1 for i in suspects]}")

python step7_sealed_backup.py

blob: 102 bytes | shares: 5
all 10 three-share subsets open it: True
two shares: need 3 shares, got 2

typo in the last digit: authentication failed: wrong or tampered shares
typo in a high digit: the shares do not rebuild a 32-byte value
forged share: authentication failed: wrong or tampered shares

opened despite the forgery: True
working subsets: 4 of 10 | share numbers in no working subset: [5]

The blob is 102 bytes: 12 for the nonce, 74 for the message and 16 for the authentication tag. All ten groups of three shares open it, and two shares are refused with a clear message. The two typo lines show both layers at work. A typo in a high digit trips the size check from Step 5, while a typo in the last digit slips past it and is caught by the authentication tag. The forged share from Attack 3, built here in the real share format so that it passes the size check by design, is also rejected by the tag. Last, unseal_any opens the blob even though one share is forged, because 4 of the 10 groups avoid share 5, and it names share 5 as the one that appears in no working group.

What the envelope does not fix

Authenticated encryption detects a bad share but cannot prevent Mallory from learning the key first. If he sees k-1 honest shares in the open, he holds k real shares and can decrypt the blob on his own. It also cannot stop a holder from simply refusing to take part. That is why the advice from Attack 3 still stands: collect shares privately, and keep a few spare shares beyond the threshold so that unseal_any has a working group to find.

Step 8: The byte-oriented variant that Vault and SLIP-39 use

Python has built-in big integers, so a prime field is the easiest way to teach and to code Shamir’s scheme. Several widely used tools, including Vault and SLIP-39, choose a different field, GF(2⁸), where every element is a single byte. SLIP-39’s rationale says it chose GF(256) because “the field arithmetic is easy to implement in any programming language”, and notes that a prime field would need multi-precision arithmetic. You should understand this variant because it is what you will find when you read Vault’s source.

In GF(256), a byte is read as a polynomial whose coefficients are its eight bits. Addition is XOR, because coefficients are added modulo 2. Multiplication multiplies the polynomials and reduces the result modulo x^8 + x^4 + x^3 + x + 1 (the byte 0x11B), the same polynomial AES uses. FIPS 197, the AES standard, works through an example in section 4.2: 0x57 times 0x13 is 0xfe, built from repeated doubling steps (0xae, 0x47, 0x8e, and so on). Each secret byte gets its own polynomial, and each share is the y bytes plus one byte for x. Save this as gf256.py.

# gf256.py
import secrets


def mul(a: int, b: int) -> int:
    """Multiply two bytes in GF(2^8), reducing by x^8 + x^4 + x^3 + x + 1 (0x11B)."""
    product = 0
    while b:
        if b & 1:
            product ^= a
        a <<= 1
        if a & 0x100:
            a ^= 0x11B
        b >>= 1
    return product


def inverse(a: int) -> int:
    if a == 0:
        raise ZeroDivisionError("0 has no inverse")
    result = 1
    for _ in range(254):          # a**255 == 1 for every nonzero a, so a**254 is 1/a
        result = mul(result, a)
    return result


def evaluate(coeffs: list[int], x: int) -> int:
    result = 0
    for c in reversed(coeffs):
        result = mul(result, x) ^ c
    return result


def split(secret: bytes, k: int, n: int) -> list[bytes]:
    """One polynomial per secret byte; each share is its y bytes plus one x byte."""
    if not secret or not 2 <= k <= n <= 255:
        raise ValueError("need a non-empty secret and 2 <= k <= n <= 255")
    rows = [bytearray() for _ in range(n)]
    for byte in secret:
        coeffs = [byte] + list(secrets.token_bytes(k - 1))
        for x in range(1, n + 1):
            rows[x - 1].append(evaluate(coeffs, x))
    return [bytes(row) + bytes([x]) for x, row in enumerate(rows, start=1)]


def combine(shares: list[bytes]) -> bytes:
    xs = [s[-1] for s in shares]
    if 0 in xs or len(set(xs)) != len(xs):
        raise ValueError("share index 0 or a repeated share index")
    weights = []
    for i, xi in enumerate(xs):          # addition and subtraction are both XOR here
        num = den = 1
        for j, xj in enumerate(xs):
            if i != j:
                num = mul(num, xj)
                den = mul(den, xi ^ xj)
        weights.append(mul(num, inverse(den)))
    out = bytearray()
    for pos in range(len(shares[0]) - 1):
        value = 0
        for w, share in zip(weights, shares):
            value ^= mul(w, share[pos])
        out.append(value)
    return bytes(out)

mul is the shift-and-XOR loop: it adds a shifted copy of a for each set bit of b, and XORs in 0x11B whenever a shift overflows eight bits. inverse uses the fact that the 255 non-zero bytes form a group, so a**255 is 1 and a**254 is the inverse. combine is the same Lagrange calculation as before, with subtraction replaced by XOR. The script below checks the arithmetic three ways: against the FIPS 197 values, by multiplying every byte by its inverse, and against the multiplication tables of the SLIP-39 reference implementation for all 65,536 input pairs.

# step8_gf256.py
import itertools
import secrets

from gf256 import combine, inverse, mul, split
from keyshare import HEX_WIDTH

print("FIPS 197: {57} * {13} =", hex(mul(0x57, 0x13)))
print("{57} * {02}, {04}, {08} =", [hex(mul(0x57, b)) for b in (0x02, 0x04, 0x08)])
print("every nonzero byte times its inverse is 1:", all(mul(a, inverse(a)) == 1 for a in range(1, 256)))

# Cross-check against the multiplication tables of the SLIP-39 reference implementation.
from shamir_mnemonic.shamir import EXP_TABLE, LOG_TABLE


def mul_reference(a: int, b: int) -> int:
    return 0 if a == 0 or b == 0 else EXP_TABLE[(LOG_TABLE[a] + LOG_TABLE[b]) % 255]


print("agrees with the SLIP-39 tables on all 65536 products:",
      all(mul(a, b) == mul_reference(a, b) for a in range(256) for b in range(256)))

key = secrets.token_bytes(32)
shares = split(key, 3, 5)
print()
print("GF(256) share size:", len(shares[0]), "bytes for a", len(key), "byte secret")
print("prime-field share size:", HEX_WIDTH // 2, "bytes for the same secret")
print("all 10 three-share subsets rebuild the key:",
      all(combine(list(c)) == key for c in itertools.combinations(shares, 3)))
print("two shares rebuild the key:", combine(shares[:2]) == key)

python step8_gf256.py

FIPS 197: {57} * {13} = 0xfe
{57} * {02}, {04}, {08} = ['0xae', '0x47', '0x8e']
every nonzero byte times its inverse is 1: True
agrees with the SLIP-39 tables on all 65536 products: True

GF(256) share size: 33 bytes for a 32 byte secret
prime-field share size: 66 bytes for the same secret
all 10 three-share subsets rebuild the key: True
two shares rebuild the key: False

The FIPS 197 values match, every non-zero byte has its inverse, and our mul agrees with the reference tables on all 65,536 products. The size comparison is the practical difference: a 32-byte secret gives 33-byte shares here and 66-byte shares in the prime-field version. The last line repeats the lesson of Step 3. Two shares of a 3-of-5 split rebuild something that is not the key, and the code says nothing.

What Vault’s source does

Vault’s shamir.go is short enough to read in one sitting, and it matches the design above. It works in GF(2⁸) with a per-byte polynomial and reduces with the constant 0x1B. A comment explains the share layout: “The returned shares are each one byte longer than the secret as they attach a tag used to reconstruct the secret.” The tag is the x coordinate, stored as the last byte. Combine returns an error for fewer than two parts, for parts of different lengths and for a duplicate part (“duplicate part detected”), but it has no idea what the threshold was, so it accepts any number of valid-looking parts from two upward.

The safety net sits one layer up. Vault’s documentation says that “Vault encrypts the root key using the unseal key”, which means a wrongly rebuilt unseal key cannot decrypt the root key. That is the same idea as Step 7. The documentation does not describe the failure message, so treat this as my reading of the design, not documented behavior. SLIP-39 solves the same problem inside the polynomial itself: it computes a digest of the secret and stores it as a second polynomial point, and the specification says that “Encoding the digest makes it possible to verify that the shared secret has been correctly recovered”.

Step 9: Run the test suite and confirm the whole thing works

The tests cover the main behaviors from the steps: every group of three shares rebuilds the secret, too few shares give a wrong value at the raw layer and are refused at the byte layer, the zero-index and forged-share tricks work on the raw math and are rejected or detected by the checked code, a seeded generator makes shares reproducible, the sealed backup names a forged share, and the GF(256) arithmetic and round trip hold. Save this as test_shamir.py.

# test_shamir.py
import itertools
import random

import pytest

import gf256
from keyshare import HEX_WIDTH, PRIME, ShareError, WrongShares, parse_share, recover_key, split_key
from sealed import seal, unseal, unseal_any
from shamir_core import PRIME_521, combine_int, interpolate, points_from, split_int

P = 7919
COEFFS = [4242, 1024, 777]


def test_every_three_share_subset_rebuilds_the_secret():
    points = points_from(COEFFS, 5, P)
    for subset in itertools.combinations(points, 3):
        assert combine_int(list(subset), P) == 4242


def test_two_shares_of_a_three_share_threshold_give_a_wrong_value():
    points = points_from(COEFFS, 5, P)
    assert combine_int(points[:2], P) == 2688


def test_large_prime_round_trip_with_more_than_k_shares():
    secret = random.Random(5).getrandbits(256)
    points = split_int(secret, 4, 7, PRIME_521)
    assert combine_int(points[1:6], PRIME_521) == secret      # five shares, threshold four


def test_duplicate_x_makes_the_raw_layer_raise_valueerror():
    points = points_from(COEFFS, 5, P)
    with pytest.raises(ValueError):
        combine_int([points[0], points[0], points[1]], P)


def test_keyshare_round_trip_keeps_leading_zero_bytes():
    secret = bytes(2) + b"hello"
    shares = split_key(secret, 2, 3)
    assert recover_key(shares[1:]) == secret


def test_keyshare_refuses_too_few_duplicate_mixed_and_x_zero():
    shares = split_key(bytes(32), 3, 5)
    other = split_key(bytes(32), 3, 5)
    with pytest.raises(ShareError, match="need 3 shares"):
        recover_key(shares[:2])
    with pytest.raises(ShareError, match="same index"):
        recover_key([shares[0], shares[0], shares[1]])
    with pytest.raises(ShareError, match="different splits"):
        recover_key([shares[0], shares[1], other[2]])
    parts = shares[2].split("-")
    parts[3] = "0"
    with pytest.raises(ShareError, match="1 to 255"):
        recover_key([shares[0], shares[1], "-".join(parts)])


def test_secret_length_limits():
    with pytest.raises(ShareError):
        split_key(b"", 2, 3)
    with pytest.raises(ShareError):
        split_key(b"x" * 66, 2, 3)
    assert recover_key(split_key(b"y" * 65, 2, 3)[:2]) == b"y" * 65


def test_a_seeded_generator_makes_shares_reproducible():
    a = split_int(123, 3, 5, PRIME_521, randbelow=random.Random(99).randrange)
    b = split_int(123, 3, 5, PRIME_521, randbelow=random.Random(99).randrange)
    assert a == b


def test_forged_share_rebuilds_the_attackers_value():
    points = points_from(COEFFS, 5, P)
    alice, bob, mallory = points[0], points[1], points[4]
    forged = interpolate([(0, 1337), alice, bob], mallory[0], P)
    assert combine_int([alice, bob, (mallory[0], forged)], P) == 1337


def test_x_zero_point_overrides_the_secret_in_the_raw_layer():
    points = points_from(COEFFS, 5, P)
    assert combine_int([points[0], points[1], (0, 5555)], P) == 5555


def test_sealed_round_trip_every_subset():
    shares, blob = seal(b"break glass", 3, 5)
    for subset in itertools.combinations(shares, 3):
        assert unseal(list(subset), blob) == b"break glass"


def test_sealed_rejects_a_tampered_blob():
    shares, blob = seal(b"break glass", 3, 5)
    tampered = blob[:-1] + bytes([blob[-1] ^ 1])
    with pytest.raises(WrongShares):
        unseal(shares[:3], tampered)


def test_unseal_any_names_the_forged_share():
    shares, blob = seal(b"break glass", 3, 5)
    a, b, m = parse_share(shares[0]), parse_share(shares[1]), parse_share(shares[4])
    forged_y = interpolate([(0, 7), (a.x, a.y), (b.x, b.y)], m.x, PRIME)
    forged = shares[4][:-HEX_WIDTH] + f"{forged_y:0{HEX_WIDTH}x}"
    with pytest.raises(WrongShares):
        unseal([shares[0], shares[1], forged], blob)
    assert unseal_any(shares[:4] + [forged], blob, 3) == (b"break glass", 4, [4])


def test_gf256_known_products_and_inverses():
    assert gf256.mul(0x57, 0x13) == 0xFE
    assert gf256.mul(0x57, 0x02) == 0xAE
    assert all(gf256.mul(a, gf256.inverse(a)) == 1 for a in range(1, 256))


def test_gf256_round_trip_and_guards():
    secret = bytes(range(32))
    shares = gf256.split(secret, 3, 5)
    assert {len(s) for s in shares} == {33}
    for subset in itertools.combinations(shares, 3):
        assert gf256.combine(list(subset)) == secret
    with pytest.raises(ValueError):
        gf256.combine([shares[0], shares[0], shares[1]])
    with pytest.raises(ValueError):
        gf256.combine([shares[0], shares[1], shares[2][:-1] + bytes([0])])

python -m pytest -q

15 passed in 0.07s

You should see 15 passed, with a time of a fraction of a second. If a test fails, read its name: each one maps to a step above. To confirm that the whole thing works end to end, run python step2_worked_example.py and look for 4242 three times, run python step7_sealed_backup.py and look for share 5 in the last line, and run the tests.

Mistakes to avoid when you use this for real

• Trusting the output of a combine call. Fewer than k shares, a typo and a forged share all return a plausible number. Always check the result with authenticated encryption (Step 7) or a digest like SLIP-39’s.
• Using a seeded random generator. Only secrets (or your operating system’s randomness) may produce secret coefficients (Attack 1).
• Accepting an index of 0. Validate every share’s x value before interpolating (Attack 2).
• Revealing shares in the open. The last speaker can see the others’ shares, and that is enough to learn the secret or force a wrong one (Attack 3).
• Mixing shares from two splits. Without a batch identifier the mix rebuilds garbage. Keep one, as keyshare does.
• Reusing a nonce with the same key. Make a fresh key for every sealed blob, as seal does.
• Storing a checksum of a guessable secret. A plain hash stored beside the shares lets anyone test guesses offline. Wrap the secret in authenticated encryption under a random key (Step 7). And if what you need is to check user passwords at login, you do not want to recover them at all; hash them, as in the password hashing tutorial.

Where to go next

The cheating problem in Attack 3 is what verifiable secret sharing addresses; the Wikipedia article describes it as aiming “to verify that shareholders are honest and not submitting fake shares”, and Tompa and Woll’s paper is a place to start. Shamir’s own paper also shows how to refresh shares without changing the secret: “all we need is a new polynomial q(x) with the same free term”, so that shares stolen at different times cannot be combined. It also shows how to give people unequal weight by handing some of them several points, which SLIP-39 handles with groups of shares. If you want a ready-made, reviewed implementation of the byte-oriented variant with checksums and word lists, the shamir-mnemonic package is the SLIP-39 reference.

Two limits are worth remembering. Recovery assembles the secret in one process, so if the key must never exist in one place at all, Shamir alone is the wrong tool. And shares are still secrets: never commit them to a repository. The Gitleaks pre-commit tutorial shows how to catch that mistake before it reaches GitHub.