Category Archives: Cryptography

Shamir’s Secret Sharing

Posted on by

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),
    "098765432100DEADBEEF000000000000"
    "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");
//...

/*
* P(9EF35877FC0E2DB6B76BFF03B8CFA2EADD90190719DA598482D1569C6F9CA1EF) =
* B451E41F20E5E85EC35CB94E6E88E292B25CBF67B687D93B6B42D18EEE26A8A9
*
* P(810A3DB3AB3E4EA758A535A0616A6C9E1FE08B610D5F0496911A1AFFD3BC8136) =
* B1B26A93205BD5416288A8EB0DE050C76D501247A8BE7BD4BA4416FEB743C90D
*
* P(37D9B47A812B434077C025ADA5300EA41778036222ECD4853E4D64CB92CDF135) =
* 9D58638CB24E0783966106ED8BB9D21F8F308C845829E6DD3CF1F7AD0C0499BB
*
* secret =
* 098765432100DEADBEEF000000000000000000000000CAFEBABE001234567890
*/

References: