Shamir's Secret Sharing

Shamir's Secret Sharing (SSS) is a cryptographic algorithm that splits a secret into n unique shares. The secret can only be recovered when at least k shares (the threshold) are combined. Fewer than k shares reveal absolutely no information about the secret. It was invented by Adi Shamir in 1979 and is based on polynomial interpolation over a finite field.

The threshold k is the minimum number of shares required to reconstruct the secret. For example, with n=5 and k=3, you generate 5 shares but only need any 3 of them to recover the secret. Even if an attacker obtains 2 shares, they cannot learn anything about the secret. This provides both redundancy (losing some shares is okay) and security (partial compromise reveals nothing).

This demo uses the Mersenne prime 2¹²⁷ − 1 (170141183460469231731687303715884105727) as the finite field modulus. This 127-bit prime is large enough for demonstration purposes and allows encoding secrets of up to ~15 ASCII characters. All arithmetic operations (addition, multiplication, division) are performed modulo this prime using BigInt arithmetic, ensuring information-theoretic security.

Shamir's Secret Sharing provides information-theoretic security. With fewer than k shares, every possible secret value is equally likely — the system has perfect secrecy. Each coefficient of the polynomial is chosen uniformly at random, meaning partial shares give zero mathematical advantage in guessing the secret, regardless of computing power.

SSS is used in: cryptocurrency wallet recovery (splitting seed phrases), secure key management (distributing master keys across multiple custodians), multi-party computation, digital inheritance (distributing access among heirs), nuclear launch codes (requiring multiple officials), and cloud storage security (distributing encryption keys across data centers).

Each share is formatted as x:hex_y, where x is the share index (1 through n) and hex_y is the hexadecimal representation of the polynomial evaluation at x. For example: 3:a1b2c3d4e5f6. The hex string represents a BigInt value modulo the prime. When recovering, paste one share per line in this same format.

A prime modulus ensures that the finite field GF(p) has no zero divisors — every non-zero element has a multiplicative inverse. This is essential for Lagrange interpolation, which requires division. Without a prime modulus, the recovery algorithm would fail for certain share combinations. The prime guarantees that the polynomial is uniquely determined by any k distinct points.