Shamir Secret Sharing in Python from Scratch: GF(256), Vault Compatibility, and Where MPC Wallets Go Further
What We Will Build
- Shamir secret sharing over a prime field (about 40 lines).
- A byte-wise version over GF(256), the same field AES uses.
- A demonstration that t-1 shares reveal nothing, compared with naive key chunking.
- The “before” bug: a dealer that uses random instead of secrets, and an attack that recovers the key from a single share.
- An interop test suite against HashiCorp Vault’s shamir package, with property-based tests in Hypothesis.
- The honest boundary: why reconstructing a key is different from threshold signing.
Shamir secret sharing is one of those algorithms that fits on a napkin and still runs in production systems. HashiCorp Vault uses it by default to split the key that unseals a Vault server: vault operator init creates 5 key shares and requires 3 of them to unseal.
Crypto custody products talk about “key shares” too, and that is where people start mixing up two different ideas: splitting a key so it can be rebuilt later, and never having the key in one place at all.
In this post we build a Shamir secret sharing scheme in Python from first principles, break it on purpose, and then check it byte for byte against Vault’s own Go implementation. At the end we draw the line between Shamir secret sharing and what an MPC wallet does with threshold signatures.
Stack: Python 3.13, pytest 9.2.0, Hypothesis 6.170.14, Go 1.24.7 for the Vault cross-check. Every output block below is copied from a real run.
Educational code, not for production. The code below is written to be read, not deployed. It is not constant-time, has no share authentication, and has not been audited. For real keys use a maintained, reviewed library or a KMS/HSM, and if you need threshold signing, an audited MPC/TSS library.
How Shamir Secret Sharing Works
Adi Shamir described the scheme in “How to Share a Secret” (Communications of the ACM, November 1979). The goal is a (k, n) threshold scheme: split data D into n pieces so that any k pieces make D easy to compute, and k-1 or fewer leave D “completely undetermined.”
The trick is polynomial interpolation. Two points define a line, three points define a parabola, and in general k points define exactly one polynomial of degree k-1. So the dealer does this:
Two panels. Left: a parabola through five share points with the secret at x = 0; any three points fix the curve. Right: only two share points, with three dashed parabolas passing through them and crossing the y-axis at three different values, labelled as all equally possible.
The picture uses real numbers to build intuition. The code uses a finite field, and that is not cosmetic: over the reals, a share’s magnitude leaks information about the secret, and division introduces rounding. In a finite field every nonzero element has an exact inverse and every value is equally likely.
Step 1. Shamir Secret Sharing Over a Prime Field
The first version uses integers modulo p = 2^127 - 1, a Mersenne prime. Python’s built-in pow(den, -1, P) (available since 3.8) gives the modular inverse, so Lagrange interpolation is a few lines.
"""Shamir secret sharing over a prime field. EDUCATIONAL CODE, NOT FOR PRODUCTION."""
import secrets
P = 2 ** 127 - 1 # a Mersenne prime; every secret must be smaller than P
def _eval(coeffs: list[int], x: int) -> int:
"""Evaluate a0 + a1*x + a2*x^2 + ... mod P with Horner's method."""
acc = 0
for c in reversed(coeffs):
acc = (acc * x + c) % P
return acc
def split(secret: int, n: int, t: int) -> list[tuple[int, int]]:
"""Return n shares (x, y); any t of them recover the secret."""
if not 0 <= secret < P:
raise ValueError("secret must be in [0, P)")
if not 2 <= t <= n < P:
raise ValueError("need 2 <= t <= n")
# a0 is the secret, a1..a(t-1) are uniformly random field elements
coeffs = [secret] + [secrets.randbelow(P) for _ in range(t - 1)]
return [(x, _eval(coeffs, x)) for x in range(1, n + 1)]
def combine(shares: list[tuple[int, int]]) -> int:
"""Lagrange interpolation at x = 0."""
xs = [x for x, _ in shares]
if len(set(xs)) != len(xs):
raise ValueError("duplicate share x-coordinate")
secret = 0
for i, (xi, yi) in enumerate(shares):
num, den = 1, 1
for j, xj in enumerate(xs):
if i != j:
num = num * (-xj) % P # (0 - xj)
den = den * (xi - xj) % P # (xi - xj)
secret = (secret + yi * num * pow(den, -1, P)) % P
return secret
Two details matter more than they look. The random coefficients come from secrets.randbelow, not from random. And combine rejects duplicate x-coordinates: two shares with the same x would make a denominator zero.
from itertools import combinations
from sss.prime import split, combine
secret = int.from_bytes(b"correct horse", "big")
shares = split(secret, n=5, t=3)
for x, y in shares:
print(f"share x={x}: y={y:#034x}")
ok = all(combine(list(c)) == secret for c in combinations(shares, 3))
print("all 10 three-share subsets recover the secret:", ok)
two = combine(shares[:2])
print("two shares interpolate to:", two.to_bytes(16, "big"))
share x=1: y=0x76f14d46392488daea23121ae0faf646
share x=2: y=0x472c2dd395464e19f1e42c925dd3e63a
share x=3: y=0x70b0a20b83d7c2227ab76fcee5fd433f
share x=4: y=0x737ea9ee04d8e4f4849cdbd079770d56
share x=5: y=0x4f96457b1849b6900f9470971841447f
all 10 three-share subsets recover the secret: True
two shares interpolate to: b'&\xb6l\xb8\xdd\x02\xc3\x9b\xe2a\xf7\xa3d"\x06S'
All ten 3-of-5 subsets give the original value back. Two shares also produce a number, just a wrong one. Lagrange interpolation always returns something, which is the first gotcha we will come back to. (The share values differ on every run because the coefficients are fresh random numbers.)
Step 2. Byte-Wise Sharing Over GF(256)
A prime field is easy to reason about but awkward for real secrets: you have to map bytes to an integer below p, and share sizes depend on p. Most practical implementations, including Vault’s and the SLIP-39 standard for wallet backups, work in GF(2^8) instead. Each byte of the secret gets its own random polynomial, and each share is exactly one byte longer than the secret.
GF(256) arithmetic is not ordinary byte math:
- Addition and subtraction are both XOR.
- Multiplication is carry-less multiplication reduced modulo x^8 + x^4 + x^3 + x + 1 (0x11B), the polynomial defined for AES in FIPS 197.
- The inverse of a nonzero a is a^254, because a^255 = 1 for every nonzero element.
"""Byte-wise Shamir secret sharing over GF(2^8). EDUCATIONAL CODE, NOT FOR PRODUCTION.
Field: GF(2^8) with the AES polynomial x^8 + x^4 + x^3 + x + 1 (0x11B).
Share format matches HashiCorp Vault's shamir package: y_1 .. y_len || x.
Not constant-time: table-free but branchy Python. Do not use on real keys.
"""
import secrets
def add(a: int, b: int) -> int:
return a ^ b # addition and subtraction are both XOR
def mul(a: int, b: int) -> int:
r = 0
while b:
if b & 1:
r ^= a
a <<= 1
if a & 0x100:
a ^= 0x11B # reduce modulo x^8 + x^4 + x^3 + x + 1
b >>= 1
return r
def inv(a: int) -> int:
if a == 0:
raise ZeroDivisionError("0 has no inverse in GF(256)")
r, e = 1, 254 # a^254 == a^-1 because a^255 == 1 for every nonzero a
while e: # square-and-multiply
if e & 1:
r = mul(r, a)
a = mul(a, a)
e >>= 1
return r
def _eval(coeffs: list[int], x: int) -> int:
acc = 0
for c in reversed(coeffs):
acc = add(mul(acc, x), c)
return acc
def interpolate(points: list[tuple[int, int]], x: int = 0) -> int:
result = 0
for i, (xi, yi) in enumerate(points):
basis = 1
for j, (xj, _) in enumerate(points):
if i != j:
basis = mul(basis, mul(add(x, xj), inv(add(xi, xj))))
result = add(result, mul(yi, basis))
return result
def split(secret: bytes, n: int, t: int) -> list[bytes]:
if not secret:
raise ValueError("cannot split an empty secret")
if not 2 <= t <= n <= 255:
raise ValueError("need 2 <= t <= n <= 255")
xs = list(range(1, n + 1)) # x-coordinates are public; never use x = 0
shares = [bytearray() for _ in xs]
for byte in secret: # one fresh polynomial per secret byte
coeffs = [byte] + list(secrets.token_bytes(t - 1))
for share, x in zip(shares, xs):
share.append(_eval(coeffs, x))
return [bytes(s) + bytes([x]) for s, x in zip(shares, xs)]
def combine(shares: list[bytes]) -> bytes:
if len(shares) < 2:
raise ValueError("need at least two shares")
if len({len(s) for s in shares}) != 1 or len(shares[0]) < 2:
raise ValueError("shares must have equal length >= 2")
xs = [s[-1] for s in shares]
if len(set(xs)) != len(xs) or 0 in xs:
raise ValueError("duplicate or zero x-coordinate")
return bytes(interpolate([(x, s[i]) for x, s in zip(xs, shares)], 0) for i in range(len(shares[0]) - 1))
The share layout (y bytes || x) is deliberately the same one Vault uses, so we can test against it later. Vault’s source comments it as {y1, y2, .., yN, x}.
Before trusting the field code, pin it to known answers. FIPS 197, Section 4.2, gives {57}·{02} = {ae} and {57}·{13} = {fe}, and Vault’s own unit tests check mult(3, 7) == 9 and div(6, 3) == 2. Those go straight into the test suite (Step 5).
Step 3. Why t-1 Shares Reveal Nothing
“Perfect secrecy” is easy to state and easy to doubt, so let’s count. Take one secret byte, a 3-of-3 split, and give the attacker two shares. For every candidate secret a0 and every a1, the first known point forces a unique a2; then we check whether that polynomial also hits the second point. This covers all 256^3 degree-2 polynomials.
"""What does an attacker learn from t-1 shares? Exhaustive check for one byte, t = 3."""
from collections import Counter
from sss.gf256 import add, inv, mul, split
secret = b"K"
shares = split(secret, n=3, t=3)
known = [(s[-1], s[0]) for s in shares[:2]] # attacker holds 2 of 3 shares
# For every candidate secret a0 and every a1, the first known point fixes a2
# uniquely; then check the second point. That covers all 256^3 polynomials.
(x1, y1), (x2, y2) = known
inv_x1sq = inv(mul(x1, x1))
consistent = Counter()
for a0 in range(256):
for a1 in range(256):
a2 = mul(add(add(y1, a0), mul(a1, x1)), inv_x1sq)
if add(add(a0, mul(a1, x2)), mul(a2, mul(x2, x2))) == y2:
consistent[a0] += 1
print("candidate secrets consistent with 2 shares:", len(consistent))
print("polynomials per candidate:", sorted(set(consistent.values())))
print("is the real secret special?", consistent[secret[0]], "polynomial(s), like every other value")
# Contrast: naive "cut the key into 3 chunks" leaks the chunks you hold
key = bytes(range(32))
chunks = [key[0:11], key[11:22], key[22:32]]
print("naive chunking, 2 of 3 chunks reveal", len(chunks[0]) + len(chunks[1]), "of 32 key bytes")
candidate secrets consistent with 2 shares: 256
polynomials per candidate: [1]
is the real secret special? 1 polynomial(s), like every other value
naive chunking, 2 of 3 chunks reveal 22 of 32 key bytes
Every one of the 256 possible bytes is consistent with exactly one polynomial. From the attacker’s point of view the real secret looks like every other value, so two shares carry zero information about it. Byte-wise sharing applies the same argument to each byte independently, because each byte has its own independent random coefficients.
Compare that with the tempting shortcut of cutting a 32-byte key into three pieces: anyone holding two of them already knows 22 bytes, which leaves 10 bytes (80 bits) to brute force instead of 256. Chunking is a way to lose a key slowly; Shamir sharing is not.
Step 4. The “Before” Bug: Random Instead of Secrets
The proof in Step 3 assumes the coefficients are uniformly random and unpredictable. Here is a dealer that looks fine in code review but is not:
"""The 'before' bug: a dealer that uses `random` seeded with the clock."""
import random
import time
from sss.gf256 import _eval
def bad_split(n: int, t: int, seed: int) -> tuple[bytes, list[bytes]]:
rng = random.Random(seed) # BUG: deterministic PRNG, guessable seed
secret = bytes(rng.randrange(256) for _ in range(32)) # BUG: key from `random`
shares = [bytearray() for _ in range(n)]
for byte in secret:
coeffs = [byte] + [rng.randrange(256) for _ in range(t - 1)]
for x, share in enumerate(shares, start=1):
share.append(_eval(coeffs, x))
return secret, [bytes(s) + bytes([x]) for x, s in enumerate(shares, start=1)]
deal_time = 1_793_000_000 # fixed timestamp so the run is reproducible
secret, shares = bad_split(n=5, t=3, seed=deal_time)
stolen = shares[0] # ONE share, below the threshold of 3
# Attacker knows the deal happened "some time on that day": try 86,400 seeds
start = time.perf_counter()
for guess in range(deal_time - 50_000, deal_time + 36_400):
rng = random.Random(guess)
cand = bytes(rng.randrange(256) for _ in range(32))
coeffs0 = [cand[0]] + [rng.randrange(256) for _ in range(2)]
if _eval(coeffs0, stolen[-1]) != stolen[0]: # cheap filter on byte 0
continue
_, replay = bad_split(5, 3, guess)
if replay[0] == stolen:
elapsed = time.perf_counter() - start
print(f"seed found: {guess} after {guess - (deal_time - 50_000) + 1:,} guesses")
print(f"recovered key == real key: {cand == secret} ({elapsed:.1f}s, 1 of 3 shares)")
break
seed found: 1793000000 after 50,001 guesses
recovered key == real key: True (4.7s, 1 of 3 shares)
The attacker holds one share out of a 3-of-5 split, well below the threshold, and still recovers the full 32-byte key in a few seconds of pure Python. The math
Comments
No comments yet. Start the discussion.