What Shamir's scheme is
Shamir's secret sharing (1979) splits a secret into N shares so that any M of them (the threshold) restore it, while any M-1 reveal not a single bit. The idea: exactly one polynomial of degree M-1 passes through M points, but infinitely many pass through M-1 points. The secret is the polynomial's value at zero, and the shares are its values at points 1..N. The other coefficients are random, so given M-1 shares every secret is equally likely.
Why split a key
The classic case is backup. A private key, a master password or a wallet phrase must not sit in one place, yet it must not be lost either. Split it 2 of 3 and give the shares to different people or store them in different places (a safe, the cloud, a relative's house). Losing one share is harmless, and stealing one gives nothing. For an SSH key paste it whole, including the BEGIN and END lines; you can create one in the SSH key generator.
How it differs from cutting a key into pieces
If you cut a key into three parts, each part reveals a third of the secret and all three are needed to restore it. Lose one piece and the key is gone, while two pieces greatly narrow the search for the rest. With Shamir's scheme one share (or any number below the threshold) reveals nothing, and the threshold is flexible: losing N-M shares is safe.
How it works here
The secret is processed byte by byte in the field GF(256) with the AES polynomial 0x11b. For each byte M-1 random coefficients are drawn (crypto.getRandomValues), and share number x gets the polynomial's value at x. Restoring is Lagrange interpolation at zero. Before splitting, 4 checksum bytes (the start of the secret's SHA-256) are appended and shared along with it. So a single share does not leak the secret's hash, and a wrong set of shares is detected on restore: you get a message instead of garbage.
Share format
bl2ss1-M-x-data, where M is the threshold, x is the share number (1..255) and data is the share's values for every byte of the secret plus the checksum, in base64url. Example: bl2ss1-2-1-Qm0x9kT2. The format is our own and is not compatible with ssss, Vault or other programs.
Restoring without the site
So that shares do not depend on this site, here is the complete restore algorithm. Decode base64url into bytes, take M shares and call the function.
def mul(a, b):
r = 0
while b:
if b & 1:
r ^= a
a <<= 1
if a & 0x100:
a ^= 0x11b
b >>= 1
return r
def inv(a):
return next(x for x in range(1, 256) if mul(a, x) == 1)
def restore(points): # points = [(x, y_bytes), ...], any M shares
out = []
for i in range(len(points[0][1])):
s = 0
for xi, yi in points:
num = den = 1
for xj, _ in points:
if xj != xi:
num = mul(num, xj)
den = mul(den, xi ^ xj)
s ^= mul(yi[i], mul(num, inv(den)))
out.append(s)
return bytes(out) # the last 4 bytes are the checksumThe result is the secret followed by 4 bytes. Check that they equal the first 4 bytes of the secret's SHA-256. For a strong password you can use the password generator.