From: mdw Date: Sat, 17 Jun 2000 12:09:38 +0000 (+0000) Subject: Shamir's secret sharing system. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/71dfe576992502b96b601a7e3dce7a9d98e1682e Shamir's secret sharing system. --- diff --git a/share.c b/share.c new file mode 100644 index 0000000..f450934 --- /dev/null +++ b/share.c @@ -0,0 +1,390 @@ +/* -*-c-*- + * + * $Id: share.c,v 1.1 2000/06/17 12:09:38 mdw Exp $ + * + * Shamir's secret sharing + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: share.c,v $ + * Revision 1.1 2000/06/17 12:09:38 mdw + * Shamir's secret sharing system. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "grand.h" +#include "mp.h" +#include "mpint.h" +#include "mpmont.h" +#include "mprand.h" +#include "pgen.h" +#include "rabin.h" +#include "share.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @share_create@ --- * + * + * Arguments: @share *s@ = pointer to share context to initialize + * @unsigned t, n@ = threshold parameters for the system + * + * Returns: --- + * + * Use: Initializes a sharing context. + */ + +void share_create(share *s, unsigned t, unsigned n) +{ + s->t = t; + s->n = n; + s->i = 0; + s->s = 0; + s->p = 0; + s->v = 0; +} + +/* --- @share_destroy@ --- * + * + * Arguments: @share *s@ = pointer to share context to destroy + * + * Returns: --- + * + * Use: Disposes of a sharing context. All memory is freed, all + * integers are dropped. + */ + +void share_destroy(share *s) +{ + unsigned n; + unsigned i; + + /* --- Dispose of the share vector --- */ + + if (s->v) { + if (s->i) + n = s->i; + else if (s->n) + n = s->n; + else + n = s->t; + for (i = 0; i < n; i++) { + if (s->v[i].y) + mp_drop(s->v[i].y); + } + xfree(s->v); + } + + /* --- Other stuff --- */ + + if (s->p) + mp_drop(s->p); + if (s->s) + mp_drop(s->s); +} + +/* --- @share_mkshares@ --- * + * + * Arguments: @share *s@ = pointer to share context to fill in + * @grand *r@ = pointer to random number source + * + * Returns: --- + * + * Use: Generates @c->n@ secret shares, such that any @c->t@ of them + * may be used to recover the secret. + * + * The context structure is expected to be mostly filled in. In + * particular, @t@, @n@ and @s@ must be initialized. If @p@ is + * zero, a prime number of appropriate size is generated + * automatically. If @v@ is zero, a vector of appropriate size + * is allocated. You should use the macro @SHARE_INIT@ or + * @share_create@ to construct sharing contexts. + */ + +void share_mkshares(share *s, grand *r) +{ + mp **v; + unsigned i; + mp *u; + mpmont mm; + + /* --- If there's no prime, construct one --- */ + + if (!s->p) { + pgen_filterctx pf; + rabin pr; + mp *p; + unsigned bits = (mp_octets(s->s) + 1) * 8; + + pf.step = 2; + p = mprand(MP_NEW, bits, r, 1); + s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf, + rabin_iters(bits), pgen_test, &pr); + } + + /* --- Construct the coefficients --- */ + + mpmont_create(&mm, s->p); + v = xmalloc(s->t * sizeof(mp *)); + for (i = 0; i < s->t - 1; i++) + v[i] = mprand_range(MP_NEW, s->p, r, 0); + v[s->t - 1] = mpmont_mul(&mm, MP_NEW, s->s, mm.r2); + + /* --- Construct the shares --- */ + + if (!s->v) + s->v = xmalloc(s->n * sizeof(share_pt)); + + u = mp_copy(mm.r); + for (i = 0; i < s->n; i++) { + mp *m = MP_ZERO; + unsigned j; + + /* --- Evaluate the polynomial at %$x = i + 1$% --- */ + + for (j = 0; j < s->t; j++) { + m = mpmont_mul(&mm, m, m, u); + m = mp_add(m, m, v[j]); + if (MP_CMP(m, >=, s->p)) + m = mp_sub(m, m, s->p); + } + + /* --- Reduce the final result --- */ + + s->v[i].x = i; + s->v[i].y = mpmont_reduce(&mm, m, m); + + /* --- Compute the next point in Montgomery space --- */ + + u = mp_add(u, u, mm.r); + if (MP_CMP(u, >=, s->p)) + u = mp_sub(u, u, s->p); + } + mpmont_destroy(&mm); + + /* --- Dispose of various bits of old rubbish --- */ + + for (i = 0; i < s->t; i++) + mp_drop(v[i]); + mp_drop(u); + xfree(v); +} + +/* --- @share_add@ --- * + * + * Arguments: @share *s@ = pointer to sharing context + * @unsigned x@ = which share number this is + * @mp *y@ = the share value + * + * Returns: Number of shares required before recovery may be performed. + * + * Use: Adds a share to the context. The context must have been + * initialized with the correct prime @p@ and threshold @t@. + */ + +unsigned share_add(share *s, unsigned x, mp *y) +{ + /* --- If no vector has been allocated, create one --- */ + + if (!s->v) { + s->v = xmalloc(s->t * sizeof(share_pt)); + s->i = 0; + } + + assert(((void)"Share context is full", s->i < s->t)); + + /* --- Store the share in the vector --- */ + + s->v[s->i].x = x; + s->v[s->i].y = mp_copy(y); + s->i++; + + /* --- Done --- */ + + return (s->t - s->i); +} + +/* --- @share_combine@ --- * + * + * Arguments: @share *s@ = pointer to share context + * + * Returns: The secret, as a multiprecision integer. + * + * Use: Reconstructs a secret, given enough shares. + */ + +mp *share_combine(share *s) +{ + mp *a = MP_ZERO; + mpmont mm; + unsigned i, j; + mp *ii = MP_NEW, *jj = MP_NEW; + mp *m = MP_NEW; + + /* --- Sanity checking --- */ + + assert(((void)"Not enough shares yet", s->i == s->t)); + + /* --- Initialization --- */ + + mpmont_create(&mm, s->p); + + /* --- Grind through the shares --- */ + + for (i = 0; i < s->t; i++) { + mp *c = mp_copy(mm.r); + + ii = mp_fromuint(ii, s->v[i].x + 1); + for (j = 0; j < s->t; j++) { + if (i == j) + continue; + jj = mp_fromuint(jj, s->v[j].x + 1); + if (s->v[j].x >= s->v[i].x) + m = mp_sub(m, jj, ii); + else { + m = mp_sub(m, ii, jj); + m = mp_sub(m, s->p, m); + } + jj = mpmont_mul(&mm, jj, jj, mm.r2); + mp_gcd(0, 0, &m, s->p, m); + m = mpmont_mul(&mm, m, m, mm.r2); + m = mpmont_mul(&mm, m, m, jj); + c = mpmont_mul(&mm, c, c, m); + } + m = mpmont_mul(&mm, m, s->v[i].y, mm.r2); + c = mpmont_mul(&mm, c, c, m); + a = mp_add(a, a, c); + mp_drop(c); + } + + a = mpmont_reduce(&mm, a, a); + s->s = mp_copy(a); + mp_drop(ii); + if (jj) + mp_drop(jj); + mp_drop(m); + mpmont_destroy(&mm); + return (a); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include "fibrand.h" + +static int verify(grand *r) +{ + unsigned n = r->ops->range(r, 16) + 8; + unsigned t = r->ops->range(r, n - 1) + 1; + unsigned len = r->ops->range(r, 160); + + share_pt *v = xmalloc(t * sizeof(share_pt)); + unsigned *p = xmalloc(n * sizeof(unsigned)); + mp *sec = mprand(MP_NEW, len, r, 0); + share s; + mp *pp; + mp *ss; + unsigned i; + + int ok = 1; + + for (i = 0; i < n; i++) + p[i] = i; + for (i = 0; i < t; i++) { + unsigned long j = r->ops->range(r, n - i); + unsigned x = p[i]; + p[i] = p[i + j]; + p[i + j] = x; + } + + share_create(&s, t, n); + s.s = mp_copy(sec); + share_mkshares(&s, r); + for (i = 0; i < t; i++) { + v[i].x = s.v[p[i]].x; + v[i].y = mp_copy(s.v[p[i]].y); + } + pp = mp_copy(s.p); + share_destroy(&s); + + assert(mparena_count(MPARENA_GLOBAL) == t + 2); + + share_create(&s, t, n); + s.p = pp; + for (i = 0; i < t; i++) { + share_add(&s, v[i].x, v[i].y); + } + ss = share_combine(&s); + share_destroy(&s); + + if (MP_CMP(sec, !=, ss)) { + ok = 0; + fprintf(stderr, "\nbad recombination of shares\n"); + }; + + mp_drop(sec); + mp_drop(ss); + + for (i = 0; i < t; i++) + mp_drop(v[i].y); + + xfree(v); + xfree(p); + + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +int main(void) +{ + grand *r = fibrand_create(0); + unsigned i; + int ok = 1; + + fputs("share: ", stdout); + for (i = 0; i < 40; i++) { + if (!verify(r)) + ok = 0; + fputc('.', stdout); + fflush(stdout); + } + + if (ok) + fputs(" ok\n", stdout); + else + fputs(" failed\n", stdout); + return (ok ? EXIT_SUCCESS : EXIT_FAILURE); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/share.h b/share.h new file mode 100644 index 0000000..9584378 --- /dev/null +++ b/share.h @@ -0,0 +1,164 @@ +/* -*-c-*- + * + * $Id: share.h,v 1.1 2000/06/17 12:09:38 mdw Exp $ + * + * Shamir's secret sharing + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: share.h,v $ + * Revision 1.1 2000/06/17 12:09:38 mdw + * Shamir's secret sharing system. + * + */ + +/*----- Notes on the sharing system ---------------------------------------* + * + * Shamir's secret-sharing system is based on polynomial interpolation modulo + * a prime number. It is `perfect' in that fewer participants than the + * threshold can derive no information about the secret by pooling their + * shares, and `ideal' in that the shares are the same size as the secret. + * + * This implementation stays close to the definition, in order to support + * other schemes for (e.g.) threshold cryptography. It is, however, rather + * slow. + */ + +#ifndef CATACOMB_SHARE_H +#define CATACOMB_SHARE_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +/* --- A secret sharing context --- */ + +typedef struct share_pt { + unsigned x; /* Index of this share */ + mp *y; /* Payload of this share */ +} share_pt; + +typedef struct share { + unsigned t; /* Threshold */ + unsigned n; /* The number of shares to make */ + unsigned i; /* Next free slot in the vector */ + mp *s; /* The secret */ + mp *p; /* Modulus for arithmetic */ + share_pt *v; /* Vector of share information */ +} share; + +#define SHARE_INIT(t, n) { t, n, 0, 0, 0, 0 } + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @share_create@ --- * + * + * Arguments: @share *s@ = pointer to share context to initialize + * @unsigned t, n@ = threshold parameters for the system + * + * Returns: --- + * + * Use: Initializes a sharing context. + */ + +extern void share_create(share */*s*/, unsigned /*t*/, unsigned /*n*/); + +/* --- @share_destroy@ --- * + * + * Arguments: @share *s@ = pointer to share context to destroy + * + * Returns: --- + * + * Use: Disposes of a sharing context. All memory is freed, all + * integers are dropped. + */ + +extern void share_destroy(share */*s*/); + +/* --- @share_mkshares@ --- * + * + * Arguments: @share *s@ = pointer to share context to fill in + * @grand *r@ = pointer to random number source + * + * Returns: --- + * + * Use: Generates @c->n@ secret shares, such that any @c->t@ of them + * may be used to recover the secret. + * + * The context structure is expected to be mostly filled in. In + * particular, @t@, @n@ and @s@ must be initialized. If @p@ is + * zero, a prime number of appropriate size is generated + * automatically. If @v@ is zero, a vector of appropriate size + * is allocated. You should use the macro @SHARE_INIT@ or + * @share_create@ to construct sharing contexts. + */ + +extern void share_mkshares(share */*s*/, grand */*r*/); + +/* --- @share_add@ --- * + * + * Arguments: @share *s@ = pointer to sharing context + * @unsigned x@ = which share number this is + * @mp *y@ = the share value + * + * Returns: Number of shares required before recovery may be performed. + * + * Use: Adds a share to the context. The context must have been + * initialized with the correct prime @p@ and threshold @t@. + */ + +extern unsigned share_add(share */*s*/, unsigned /*x*/, mp */*y*/); + +/* --- @share_combine@ --- * + * + * Arguments: @share *s@ = pointer to share context + * + * Returns: The secret, as a multiprecision integer. + * + * Use: Reconstructs a secret, given enough shares. + */ + +extern mp *share_combine(share */*s*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif