Shamir's Secret Sharing in Go: Splitting a Key So No Single Person Holds It
Somewhere in most organisations there's a key that unlocks something you really don't want unlocked by one disgruntled employee, one phishing email, or one border agent with a laptop clamp. A root CA key. A disk encryption passphrase for the backup vault. The master key that decrypts everyone else's keys. The usual answer is "give it to someone you trust", which is a policy, not a control. Shamir's Secret Sharing is the control: split the key into pieces so that no single piece, or even a group of pieces below some threshold, tells you anything about the original at all.
It dates from 1979 (Adi Shamir, the S in RSA), and it still holds up because the security argument doesn't rely on any assumption about computational hardness. It's information-theoretic: with fewer than the threshold number of shares, an attacker with infinite compute learns precisely nothing about the secret. That's a much stronger claim than "would take longer than the age of the universe to brute-force", and it's worth understanding why it's true before writing any Go.
Why you can't just XOR it into pieces
The obvious naive scheme is to XOR the secret with a pile of random pads: generate n-1 random byte strings the same length as the secret, XOR them all together with the secret to produce the nth share, then hand out all n. Reconstruction is XOR-ing everything back together. This is genuinely secure in the sense that any n-1 shares reveal nothing at all, but it has a fatal practical flaw: you need every single share back to reconstruct anything. Lose one, or have one director go on holiday with theirs, and the secret is gone forever along with whatever it protected.
What you actually want is a "k of n" threshold: split the secret into n shares such that any k of them reconstruct it, but any k-1 reveal nothing. Five shares held by five directors, any three of whom can act together. That isn't a small tweak to the XOR scheme, it needs different maths entirely.
The polynomial trick
Shamir's insight is that a straight line is uniquely defined by two points, a parabola by three, and in general a polynomial of degree k-1 is uniquely defined by k points on it, and left completely undetermined by any k-1 of them, since infinitely many degree k-1 polynomials pass through k-1 given points. So to split a secret s into n shares with threshold k:
- Build a random polynomial of degree k-1 whose constant term is the secret: f(x) = s + a1*x + a2*x^2 + ... + a(k-1)*x^(k-1), with the coefficients a1 through a(k-1) chosen uniformly at random.
- Hand out n points on that polynomial: (1, f(1)), (2, f(2)), and so on up to (n, f(n)). Each pair is one share.
- To reconstruct, take any k shares and use Lagrange interpolation to recover f(0), which equals the secret by construction.
With fewer than k points, the constant term stays unconstrained: for every possible value of the secret there's some polynomial of degree k-1 that fits the points you already hold, so you've learned nothing. That's the information-theoretic part, it isn't "hard to guess", it's genuinely undetermined by the maths.
Why a finite field, and why GF(256) specifically
Do this arithmetic over the real numbers or the rationals and two problems show up. First, coefficients and shares grow without bound as you evaluate a polynomial at larger x, which is awkward when you want a share to stay the same size as the secret. Second, floating-point maths isn't exact, and Lagrange interpolation over floats won't reliably reconstruct anything.
The fix used by essentially every real implementation, including the scheme behind HashiCorp Vault's unseal keys, is to do the arithmetic in GF(256), the finite field with 256 elements, the same field AES uses for its S-box and MixColumns step. Every byte of the secret is treated as a field element. Addition is XOR, so there's no carrying and no growth. Multiplication and division are defined modulo the irreducible polynomial x^8 + x^4 + x^3 + x + 1, which is 0x11b, and that keeps every result inside a single byte. It's the same closed, byte-sized field structure Reed-Solomon codes use, for the same reason: bounded size and exact arithmetic.
The scheme then runs per byte: split each byte of the secret independently, with a fresh random polynomial for each byte position but the same set of x-coordinates reused across all of them.
Implementing it in Go
Field arithmetic comes first. Multiplication and division are done with precomputed log/exp tables built once at package init, which turns GF(256) multiplication into an addition and a table lookup:
package shamir
import (
"crypto/rand"
"fmt"
)
var expTable [512]byte
var logTable [256]byte
func init() {
x := byte(1)
for i := 0; i < 255; i++ {
expTable[i] = x
logTable[x] = byte(i)
x = gfMulSlow(x, 3) // 3 is a generator of GF(256)*
}
for i := 255; i < 512; i++ {
expTable[i] = expTable[i-255]
}
}
// gfMulSlow multiplies without the tables, used only to build them.
func gfMulSlow(a, b byte) byte {
var p byte
for i := 0; i < 8 && a != 0 && b != 0; i++ {
if b&1 != 0 {
p ^= a
}
hiBit := a & 0x80
a <<= 1
if hiBit != 0 {
a ^= 0x1b // x^8 + x^4 + x^3 + x + 1, reduced
}
b >>= 1
}
return p
}
func gfMul(a, b byte) byte {
if a == 0 || b == 0 {
return 0
}
return expTable[int(logTable[a])+int(logTable[b])]
}
func gfDiv(a, b byte) byte {
if a == 0 {
return 0
}
if b == 0 {
panic("shamir: division by zero in GF(256)")
}
diff := int(logTable[a]) - int(logTable[b])
if diff < 0 {
diff += 255
}
return expTable[diff]
}
Splitting evaluates a random polynomial per byte at x = 1 through n, using Horner's method:
// Split divides secret into the given number of shares, any threshold
// of which can reconstruct it. Shares are keyed by their x-coordinate.
func Split(secret []byte, shares, threshold int) (map[byte][]byte, error) {
if threshold < 2 || threshold > shares {
return nil, fmt.Errorf("shamir: threshold must be between 2 and %d", shares)
}
if shares < 1 || shares > 255 {
return nil, fmt.Errorf("shamir: shares must be between 1 and 255")
}
if len(secret) == 0 {
return nil, fmt.Errorf("shamir: secret must not be empty")
}
result := make(map[byte][]byte, shares)
for i := 1; i <= shares; i++ {
result[byte(i)] = make([]byte, len(secret))
}
coeffs := make([]byte, threshold)
for byteIdx, b := range secret {
coeffs[0] = b
if _, err := rand.Read(coeffs[1:]); err != nil {
return nil, fmt.Errorf("shamir: generating coefficients: %w", err)
}
for x := 1; x <= shares; x++ {
result[byte(x)][byteIdx] = evalPoly(coeffs, byte(x))
}
}
return result, nil
}
func evalPoly(coeffs []byte, x byte) byte {
result := byte(0)
for i := len(coeffs) - 1; i >= 0; i-- {
result = gfMul(result, x) ^ coeffs[i]
}
return result
}
Reconstruction is Lagrange interpolation evaluated at x = 0, which simplifies nicely in GF(256) because subtraction is the same operation as addition, both are XOR:
// Combine reconstructs the secret from a set of shares at least as
// large as the original threshold. Fewer shares silently produce
// garbage rather than an error, since Combine has no way to tell.
func Combine(shares map[byte][]byte) ([]byte, error) {
if len(shares) < 2 {
return nil, fmt.Errorf("shamir: need at least two shares")
}
length := -1
xs := make([]byte, 0, len(shares))
for x, ys := range shares {
if length == -1 {
length = len(ys)
} else if len(ys) != length {
return nil, fmt.Errorf("shamir: mismatched share lengths")
}
xs = append(xs, x)
}
secret := make([]byte, length)
for byteIdx := 0; byteIdx < length; byteIdx++ {
var acc byte
for _, xi := range xs {
yi := shares[xi][byteIdx]
num, den := byte(1), byte(1)
for _, xj := range xs {
if xj == xi {
continue
}
num = gfMul(num, xj) // (0 - xj) == xj in GF(2^8)
den = gfMul(den, xi^xj) // (xi - xj) == xi XOR xj
}
acc ^= gfMul(yi, gfDiv(num, den))
}
secret[byteIdx] = acc
}
return secret, nil
}
That's the whole scheme in under a hundred lines. Split a 32-byte key five ways with a threshold of three, and any three of the resulting shares reconstruct it:
secret := []byte("a 32-byte example master key!!!")
shares, err := Split(secret, 5, 3)
if err != nil {
log.Fatal(err)
}
subset := map[byte][]byte{
1: shares[1],
3: shares[3],
5: shares[5],
}
recovered, err := Combine(subset)
if err != nil {
log.Fatal(err)
}
fmt.Println(bytes.Equal(secret, recovered)) // true
Where this stops helping you
A few things this scheme deliberately doesn't do, and they're worth being explicit about before building anything on top of it.
It isn't authenticated. If one of the k shares handed to Combine is wrong, whether through corruption or a malicious holder, you get back confident-looking garbage with no error at all. Reed-Solomon-style secret sharing schemes exist that add redundant shares so a bad one can be detected and corrected, and verifiable secret sharing (Feldman's and Pedersen's schemes build commitments on top of the same polynomial idea) lets participants check their share is consistent with the others before anyone attempts reconstruction. Plain Shamir has none of that, so if shares are going to parties you don't fully trust to type them in correctly, check the reconstructed secret against something independent, such as a hash published alongside the shares, rather than assuming a successful Combine call means the result is right.
It also isn't a substitute for threshold signatures or multi-party computation. Reconstructing the secret means it briefly exists in full, in memory, on whatever machine ran Combine. If the whole point of splitting a signing key was to ensure it never sits in one place, gathering it back together to sign defeats that, if only for a moment. Threshold signature schemes such as FROST for Schnorr, or threshold ECDSA, avoid this by letting parties jointly produce a valid signature without ever reconstructing the private key anywhere. Shamir's scheme is the right tool when a secret needs reconstructing occasionally, deliberately, and under supervision, like a disaster recovery key, not when the goal is for the whole secret to never exist anywhere at all.
And it says nothing about who's allowed to bring shares together, or where those shares live in the meantime. Splitting a key five ways and putting all five pieces in the same filing cabinet has roughly the same threat model as not splitting it. The maths solves the mathematical problem of information leakage below the threshold; separating the shares geographically and organisationally is still entirely on you.