How Shamir Secret Sharing works: algorithm and format

Shamir Secret Sharing

Split a secret into N shares so that any M of them recover it and M − 1 or fewer reveal nothing. It is the threshold scheme Adi Shamir published in 1979, combined here with AES-256-GCM so a wrong result can never pass as the right one.

What it is for

• Seed phrase or master password backups with no single point of failure: losing one share does not lose the secret, and stealing one does not give it away.
• Inheritance and shared custody: for example, 3 of 5 relatives or partners must come together.
• Recovery keys for vaults, servers or admin accounts.

Shamir's idea

A polynomial of degree M − 1 is fixed by M points, and no smaller set of points fixes it. Shamir hides the secret in the constant term:

f(x) = s + a₁·x + a₂·x² + … + a₍M−1₎·x^(M−1)

• s is the secret; a₁ … a₍M−1₎ are drawn at random.
• Share number x is the pair (x, f(x)), for x = 1, 2, …, N. x = 0 is never handed out, because f(0) = s.
• M points rebuild the polynomial, and with it f(0). With M − 1, every possible secret is equally consistent with the known points.

Small example (M = 2, numbers modulo 11)

Secret s = 7, random coefficient a₁ = 3, so f(x) = 7 + 3x (mod 11):

• With shares 1 and 3: the line through (1, 10) and (3, 5) has slope (5 − 10) / (3 − 1) = −5 · 2⁻¹ = −5 · 6 = 3 (mod 11) and crosses the axis at 10 − 3 = 7. The secret is back.
• With share 1 only: for any s from 0 to 10 there is a line through (0, s) and (1, 10). The point alone favours no value, so it leaks no information.

Arithmetic in GF(2⁸)

The tool does not use integers modulo a prime. It works byte by byte in the finite field GF(2⁸), the same one AES uses (FIPS-197):

• the elements are the 256 values of a byte;
• addition and subtraction are XOR;
• multiplication is polynomial multiplication with coefficients in 1, reduced modulo x⁸ + x⁴ + x³ + x + 1 (0x11b);
• every non-zero element has an inverse, computed as a²⁵⁴.

Each key byte gets its own random polynomial, and a share holds all of their values at the same x. That is why the limit is 255 shares: there are 255 non-zero values of x.

To recover, the tool runs Lagrange interpolation at x = 0:

s = Σᵢ yᵢ · Πⱼ≠ᵢ xⱼ / (xⱼ ⊕ xᵢ)

The weights depend only on the share numbers, so they are computed once and applied to every byte.

Encrypt, then split

Splitting the secret itself with Shamir has two problems: every share is as large as the secret, and M wrong shares still produce bytes, with no warning. The tool does this instead:

1. draws a 256-bit key, a 12-byte nonce and a 4-byte set id (crypto.getRandomValues);
2. encrypts the secret with AES-256-GCM. The header (version, M, N, set id) is authenticated data (AAD);
3. splits only the key with Shamir;
4. each share carries its part of the key plus the ciphertext, which is the same in all of them.

So a result is valid only if the 128-bit GCM tag verifies. A damaged share, too few shares or a relabelled header (say, M = 3 changed to M = 2) never turn into a wrong secret: recovery simply fails.

Share format (v3)

Each share is URL-safe base64 text (no =) of these bytes:

The GCM AAD is [0x00][0x03][M][N][set id]. A share is about 75 bytes + the secret's length, roughly 100 characters for a short secret.

What recovery checks

• Per-line checksum: each line is checked as you type. A mistyped share shows as Damaged before any combining.
• Same set: lines from another split show as Other set. Two different lines with the same number show as Conflict. Repeated lines count once.
• GCM tag: the secret is shown only if it authenticates.
• Tampered share: with more than M shares that do not open together, the tool tries groups of M (up to 2,000 combinations) and names the share left out of every group that opened.
• Verify after splitting: before showing the shares, the tool decodes all of them and checks that M open the secret and M − 1 do not.
• Self-test: on open, it runs a round trip and opens a frozen vector of shares. If the arithmetic or the format ever changed, stored shares would become useless, so the tool locks before that happens.

Limits and compatibility

• Secrets up to 16 KB, because every share carries the whole ciphertext. For large files, encrypt the file and split only the key.
• 2 to 255 shares, with 2 ≤ M ≤ N.
• Shares are compatible with offline-tools (format v3), both ways. The old, unauthenticated v2 format is not read here.
• They are not compatible with ssss or SLIP-39: those are different formats.

Good practice

• Keep each share in a different place, or give each one to a different person. M shares together (same drawer, cloud account or photo) are the secret.
• Test recovery right after splitting, with a different set of M shares than the ones you copied first.
• Write down M, N and the set id next to each share. They are already inside the text, but they help whoever puts the pieces together.
• Each share's QR code is handy for paper storage, but any photo of it exposes the share.
• Type the secret on a trusted device without suspicious browser extensions.