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 of degree as () where is a prime number and is a finite field with elements. If we have ( for ) and with we can use Lagrange interpolation to directly calculate : .

But what are we going to use this for? Consider you want to divide a secret into different parts and you want that parts are required to reconstruct the secret. This is what is called a threshold scheme. We can use our little mathematics from above to implement such a scheme. Choose the secret and create a random polynomial of degree with . To create the parts (shares) evaluate the polynomial at random and distribute the pairs to the different participants (the can be public, the are private to each one). To reconstruct the secret, of the participants can share their 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:

- [AS] Adi Shamir: How to Share a Secret, http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/secret-shamir.pdf