How to Share a Secret

A friend recently asked me to help with a reference implementation, in Rust, of a research project for a NIST Multi-Party Threshold Cryptography (MPTC) call. It's been a while since I've written any crypto code so this seemed like a good opportunity to refresh my skills and roll-my-own-crypto.

Instead of diving straight in, I wanted to start with something simpler and work my way up to it. So I implemented Shamir's secret sharing (SSS) -- which is a fundamental building block of MPTC. SSS is information theoretically secure, like a one-time pad, but it alone is missing some desirable properties for use in the real world. For example, you have to trust the secret dealer to give you a correct secret, and you have to trust the other parties to give you their share. There are other schemes that solve these verifiability problems, known as Verifiable Secret Sharing (VSS) schemes, such as Feldman's Scheme, which ensures there is a well-defined secret even if the dealer is malicious. But I'll save those for another day.

In this post I'll be documenting the basic math and implementation details that I found interesting while implementing SSS.

You can find the code here.

We all have secrets, sometimes we want to share them, sometimes you have $$n$$ friends and you want to split up your secret into pieces so that if any $$k$$ of your friends get together they can reconstruct your secret. If only $$k - 1$$ friends get together, nothing is revealed. This is called a $$(k, n)$$ threshold scheme.

The SSS algorithm leverages the fact that polynomials of degree $$k-1$$ are uniquely determined by $$k$$ points. So to share a secret just give every person a random point on the polynomial. Then when $$k$$ people combine their points, they can recreate the polynomial and use it to calculate the secret, which is $$f(0)$$ .

For example, consider a polynomial of degree 1 -- a line. A line is uniquely defined by 2 points. Likewise a degree 2 polynomial, a quadratic, is determined by 3 points, and so on.

In SSS we define our secret $$s$$ to be the value of the polynomial at $$x = 0$$ or $$f(0) = s$$ . And we use the $$k$$ above as our threshold value: the number of shares needed to reveal the secret.

We can continue with our "line" example where $$k = 2$$ , and use this info to share a secret. To keep things easy we'll have $$n = 3$$ shares, or 3 people. Alice, Bob, Carol.

Let's say the secret is $$s = 9$$ , we'd split it up like this:

Pick random coefficients for our polynomial. Here there is only one coefficient to pick in $$y = mx + b$$ , and it's $$m$$ . Let's choose 5. Also recall our secret $$s$$ is $$f(0) = s$$ , which is $$b$$ , the y-intercept in our example. So $$m = 5$$ , and $$b = s = 9$$ , making our polynomial $$y = 5x + 9$$ .
For each person, pick a distinct $$x$$ and evaluate the polynomial there, so each person gets the point $$(x, f(x))$$ . Picking some values and evaluating, we distribute: Alice $$(1, 14)$$ , Bob $$(4, 29)$$ , Carol $$(7, 44)$$ .

Now everyone has their shares. No one knows the secret. Suppose Carol and Alice want to reconstruct it. They would get together and do "Lagrange Interpolation". In the general case we're given $$k$$ points $(x_1, y_1), \ldots, (x_k, y_k)$ , the unique polynomial of degree $$k-1$$ through them is:

f(x) = \sum_{i=1}^{k} y_i \prod_{j \ne i} \frac{x - x_j}{x_i - x_j} \implies f(0) = \sum_{i=1}^{k} y_i \prod_{j \ne i} \frac{x_j}{x_j - x_i}

Each term is $$y_i$$ times a product that is 1 at $$x_i$$ and 0 at every other $$x_j$$ , so the sum passes through all $$k$$ points. For a line this would reduce to solving the equation:

y = 14\left(\frac{x - 7}{1 - 7}\right) + 44\left(\frac{x - 1}{7 - 1}\right) = 5x + 9

So where $$x = 0$$ we have our secret! $$s = 9$$ .

To say this is oversimplified is an understatement. In the real world, we don't do SSS over the integers like we do above, we do it over a finite field. Using the integers leaks information about the secret. There's a great explanation of this on Wikipedia.

Finite Fields, What are They?

For our purposes what we need to know is:

They're finite.
The number of elements they have must be a prime (we usually write this prime as $$p$$ ) or a prime power (written $$p^m$$ ).
They have the operations: addition, subtraction, multiplication, and division all mod $$p$$ . More on finite field arithmetic here.
Every element has an additive inverse, and every element except 0 has a multiplicative inverse.

Finite fields are also called Galois Fields (so-named in honor of Évariste Galois). We'll use the notation $$GF(p^m)$$ for a finite field of order $$p^m$$ . My SSS implementation uses $$GF(2^8)$$ , but I'll explain the other choices and why I chose $$GF(2^8)$$ .

Field Representations

We have two different ways of representing these fields, depending on their order. If we have $$GF(p)$$ (so $$m = 1$$ ), we can just use the integers $\mathbb{Z}/p\mathbb{Z}$ . If $$m > 1$$ for $$GF(p^m)$$ it gets more complicated, and we have to use the monomial basis, where each element in the field is itself represented as a polynomial. So the secret coefficients of our SSS polynomial are themselves polynomials. We get two layers of polynomials!

In general, for a given $$GF(p^m)$$ to get our set of polynomials we will enumerate over all polynomials of degree at most $$m - 1$$ with all coefficients from $\{0, 1, \ldots, p-1\}$ . Multiplication of polynomials is done modulo an irreducible polynomial of degree $$m$$ . We call the irreducible polynomial $$m(x)$$ .

There can be multiple irreducible polynomials for a given $$GF(p^m)$$ , and different choices yield different results. The fields they produce are all isomorphic, so no choice is mathematically better than another -- but two implementations that pick differently will not interoperate. So the choice has to be agreed on, not just valid.

Which $$GF(p^m)$$ do we want?

There are really only three practical choices (that I know of):

$$GF(p)$$ where $$p > s$$ . This avoids the monomial basis, so the math is simpler, but it requires choosing a new prime for an arbitrary secret. And because $$p$$ can be arbitrarily large, it requires arbitrary-precision arithmetic.
$$GF(2^m)$$ where $$m$$ is the bit-length of the secret. This requires having an irreducible polynomial $$m(x)$$ of degree $$m$$ for every $$m$$ , and everyone must agree on these $$m(x)$$ . And large $$m$$ would again require arbitrary-precision arithmetic.
$$GF(2^8)$$ -- our choice. The field is small, byte-sized! The secret doesn't have to fit in it, because we just apply the whole scheme to each byte of the secret independently. The standard irreducible polynomial used is AES's $$x^8 + x^4 + x^3 + x + 1$$ .

Implementing GF(2⁸)

Elements in GF(2⁸) can be represented by a byte. The coefficients of the polynomial are either 0 or 1, and these map to bit positions in the byte. Like:

\begin{aligned} \mathtt{00000001} \;&\rightarrow\; 1 \\ \mathtt{10000011} \;&\rightarrow\; x^7 + x + 1 \\ \mathtt{01010111} \;&\rightarrow\; x^6 + x^4 + x^2 + x + 1 \end{aligned}

In this representation addition and subtraction are the same operation, and both are equivalent to XOR of the bytes. To see why, consider adding two polynomials that both have an $$x^i$$ term. Since the coefficients are $\bmod 2$ , you get $x^i + x^i \rightarrow 2x^i \rightarrow 0$ . So addition cancels a term whenever it appears in both inputs, which is exactly what XOR does. A full example makes this clearer:

\begin{aligned} (x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) &= x^7 + x^6 + x^4 + x^2 \\ \mathtt{01010111} \oplus \mathtt{10000011} &= \mathtt{11010100} \end{aligned}

Multiplication

Multiplication gets more complicated. Multiplying two degree 7 (x⁷) polynomials gives a degree 14 (x¹⁴) polynomial, which must then be reduced modulo the following fixed polynomial:

\[m(x) = x^8 + x^4 + x^3 + x + 1\]

This reduction is done in almost the same way it would if we were working with integers: we repeatedly subtract (or here we XOR) the modulus from the element, until it is small enough.

The code is fairly self-explanatory:

fn reduce_polynomial(polynomial: u16) -> u8 {
    let mut out = polynomial;
    for i in (8..15).rev() {
        // If bit i is set...
        if (out >> i) & 1 != 0 {
            // Then XOR from the ith bit
            out ^= MODULUS << (i - 8);
        }
    }
    out as u8 // higher bits are zero'd
}

The Advanced Encryption Standard (AES) also uses GF(2⁸), and the spec has a full explanation of this. See section 4.2 of FIPS-197.

This implementation has a problem though: it branches on input data, which is a problem in cryptography-related code because it can enable side-channel attacks. Strictly speaking I don't know whether the compiled output branches -- the body is a single XOR, so LLVM may well turn it into a conditional move. But that's the real issue, not a reprieve: I can't rely on either outcome. Code that needs to be constant time has to be written to survive the optimizer, not just to look branchless in source. And verifying that it worked is difficult, often requiring cross-platform testing. So I decided to keep what I have and note the problem.

Division and Fermat's little theorem

The last operation we need to define for our field is division. To do this we use Fermat's little theorem. It is defined as:

a^{p} \equiv a \bmod p

Where

\(p\)

is prime. This gives us a way to calculate the inverse of any element because it implies

a^{p - 2} \equiv a^{-1} \bmod p

. So in our case, for an element

\(a\)

\(GF(2^8)\)

, its inverse is

a^{254} = a^{-1}

. Then we can use the inverse to define division as:

a / b = a \cdot b^{-1}

You may have noticed a problem though: this only applies where $$p$$ is prime, and $$2^8$$ is not. It still works, but what actually justifies $a^{254} = a^{-1}$ is a generalization from group theory. The 255 nonzero elements of $$GF(2^8)$$ form a group under multiplication. Lagrange's theorem says every element's order has to divide the size of the group, so raising any element to the 255th power lands you back at the identity: $a^{255} = 1$ , and therefore $a^{254} = a^{-1}$ .

You could get $a^{254}$ by multiplying $$a$$ by itself 253 times, but there's a much shorter route. An addition chain builds the exponent out of powers you've already computed, so every step reuses earlier work:

fn poly_inv(a: GF28Element) -> GF28Element {
    let a2 = poly_pow(a, 2);
    let a3 = a2 * a;
    let a12 = poly_pow(a3, 4);
    let a14 = a12 * a2;
    let a15 = a12 * a3;
    let a240 = poly_pow(a15, 16);
    a240 * a14
}

My implementation of poly_pow is naive multiplication in a loop, so this costs 23 multiplications -- much better than 253, but not as good as it could be. Every exponent passed to poly_pow here is a power of two, so those calls are really just repeated squaring. Doing it that way would bring the whole chain down to 7 squarings and 4 multiplications.

Evaluating Polynomials

To hand out shares we need to evaluate $$f(x)$$ at each share's $$x$$ . Done literally, that means computing $x^2, x^3, \ldots$ and summing the terms. But we can factor the $$x$$ 's out like this:

a_0 + a_1x + a_2x^2 + a_3x^3 = a_0 + x\Big(a_1 + x\big(a_2 + x a_3\big)\Big)

This is known as Horner's rule. We start at the highest coefficient and repeatedly multiply by $$x$$ and add the next one down. No powers are ever computed, and it costs $$k-1$$ multiplications and $$k-1$$ additions.

Since coefficients are stored constant-first, it's just a fold over the reversed slice:

pub fn evaluate_polynomial(x: GF28Element, poly: &[GF28Element]) -> GF28Element {
    poly.iter()
        .rev()
        .fold(GF28Element(0), |acc, &a| acc * x + a)
}

Every * here is polynomial multiplication mod $$m(x)$$ , and every + is XOR.

Lagrange Interpolation

With the finite field math working, the last hurdle was the interpolation itself, and that turned out to be easier than I expected. Remember the formula from way back at the top of the post: we never actually need the whole polynomial -- only $$f(0)$$ -- so we can go straight to:

f(0) = \sum_{i=1}^{k} y_i \prod_{j \ne i} \frac{x_j}{x_j - x_i}

And in the code:

pub fn lagrange_interpolation(coords: &[(GF28Element, GF28Element)]) -> GF28Element {
    let mut sum = GF28Element(0);
    for (i, (x_i, y_i)) in coords.iter().copied().enumerate() {
        let mut product = GF28Element(1);
        for (j, (x_j, _)) in coords.iter().copied().enumerate() {
            if i == j {
                continue;
            }
            product = product * (x_j / (x_j - x_i));
        }
        sum = sum + (y_i * product);
    }
    sum
}

Bringing it all Together

Once the finite field math is correct, the rest conceptually isn't so hard.

For every byte of our secret, we generate a random polynomial with $$f(0) = s_i$$ , where $$s_i$$ is the i'th byte of the secret.
Then for each user -- we'll call the j'th user $$u_j$$ -- we evaluate every polynomial at $$x = j$$ . Those values become $$u_j$$ 's shares. We use $$x = j$$ for convenience, but the values could be anything, as long as each user gets a different one. They must also be nonzero, since $$x = 0$$ is the secret itself.
Later, users come together with their shares, and for each byte they feed the corresponding points into lagrange_interpolation. That gives back the secret, one byte at a time.

The result looks like this:

use share_secret_stuff::{split_secret, reconstruct_secret};

let secret = b"Hello, world!"; // My favorite secret
let n_shares: u8 = 12;         // Max shares is 255
let k_threshold: u8 = 7;       // Threshold must not exceed the number of shares

// We get `n_shares` shares. Each one holds a single point from each byte's polynomial.
let shares = split_secret(secret, k_threshold, n_shares).unwrap();
let result = reconstruct_secret(&shares[..(k_threshold as usize)]).unwrap();
assert_eq!(result, secret);

What is Secret Sharing

Shamir Secret Sharing (SSS)