# Shamir’s Secret Sharing

To be able to understand what is going to follow, I first have to do a little mathematics:

Let’s define a polynomial over a finite field $P \in \mathbb{F}_q[X]$ of degree $k$ as $P(X) = a_0 + a_1 X + a_2 X^2 + \dots + a_k X^k$ ($a_0,\dots,a_k \in \mathbb{F}_q$) where $q$ is a prime number and $\mathbb{F}_q$ is a finite field with $q$ elements. If we have $(X_i)$ ($X_i \ne X_j$ for $i \ne j$) and $(Y_i = P(X_i))$ with $i = 1,\dots,k$ we can use Lagrange interpolation to directly calculate $a_0$: $a_0 = \sum_i Y_i \cdot \prod_{i \ne j} (-X_j)(X_i - X_j)^{-1}$.

But what are we going to use this for? Consider you want to divide a secret into $n$ different parts and you want that $k \leq n$ parts are required to reconstruct the secret. This is what is called a $(n,k)$ threshold scheme. We can use our little mathematics from above to implement such a scheme. Choose the secret $S$ and create a random polynomial of degree $k - 1$ with $a_0 = S$. To create the parts (shares) $Y_i$ evaluate the polynomial at random $X_i$ and distribute the pairs $(X_i, Y_i)$ to the different participants (the $X_i$ can be public, the $Y_i$ are private to each one). To reconstruct the secret, $k$ of the participants can share their $Y_i$ and then use the explicit formula from above ([AS]).

Here is an example run along with some source of my implementation:

//...
bn_t *N = bn_from_str(bn_alloc(32),
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
"FFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
bn_t *s = bn_from_str(bn_alloc(32),
"000000000000CAFEBABE001234567890");

//Create random polynomial.
poly_t *p = ssecrets_create_poly(s, 3, N);

bn_t **lx = (bn_t **)malloc(sizeof(bn_t *) * 4);
bn_t **ls = (bn_t **)malloc(sizeof(bn_t *) * 4);

u32 i;
for(i = 0; i < 3; i++)
{
//Evaluate at random x.
lx[i] = bn_reduce(bn_rand(bn_alloc(N->n)), N);
ls[i] = ssecrets_create_share(p, lx[i]);
bn_print(stdout, "P(", lx[i], ") = ");
bn_print(stdout, "", ls[i], "\n");
}

//Reconstruct secret.
bn_t *cs = ssecrets_calc_secret(lx, ls, 3, N);
bn_print(stdout, "secret = ", cs, "\n");
//...

/*
* B451E41F20E5E85EC35CB94E6E88E292B25CBF67B687D93B6B42D18EEE26A8A9
*
* P(810A3DB3AB3E4EA758A535A0616A6C9E1FE08B610D5F0496911A1AFFD3BC8136) =
* B1B26A93205BD5416288A8EB0DE050C76D501247A8BE7BD4BA4416FEB743C90D
*