Shamir’s Secret Sharing

History

Adi Shamir published “How to Share a Secret” in Communications of the ACM in November 1979: data divided into n pieces so that any k make it easily computable and k − 1 leave it completely undetermined. He opened with C. L. Liu’s eleven scientists and a cabinet only six together may open, which by locks and keys takes 462 locks and 252 keys each. SatoshiLabs’ SLIP-0039 (2017, now final), the scheme of Trezor’s wallets, writes the shares as words, with groups and a passphrase.

How it works

Split encrypts the secret with the passphrase, empty if none, in four Feistel rounds of PBKDF2-HMAC-SHA256. Each byte of the result then lies on a polynomial of degree k − 1 over GF(256), the field of bytes AES uses: the secret at x = 255, a digest at 254 (four bytes of HMAC-SHA256 of the secret, keyed by random bytes, then those bytes), and k − 2 random points. The shares are its values at x = 0, 1, 2 …, written as ten-bit words and closed by a three-word checksum. Combine reverses it step by step, and groups repeat it. The 1979 tab works Shamir’s own form, modulo a prime, on a number.

How it was checked

All 45 of SLIP-0039’s test vectors are read: the 15 valid sets give their master secrets and the 30 others are refused, each for its own fault. Shares made here, with groups, passphrases, both settings of the extendable flag and iteration exponents 0 to 2, come back from the fewest and from all; every three of five agree, a wrong passphrase gives another secret, and a share from another split is named. FIPS 197’s products check the field, and every one-word error in a share is caught. In the 1979 tab Liu’s 462 and 252 come out, and every value of D fits two pieces of three, each by one polynomial.

Limits

The shares are as random as the browser’s generator, and the secret passes through the page’s memory: a wallet’s real master secret is safer split on an offline device. A text is padded with zero bytes to SLIP-0039’s sixteen at least, an even number, and Combine drops them, so a text ending in zero bytes loses them. Combine runs iteration exponents up to 11. The 1979 tab is a worked example, seeded so that a link shows it again, and not for a real secret.