X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/71dfe576992502b96b601a7e3dce7a9d98e1682e..2685767a6125c1620719c7de6234aedf41857b7e:/share.c diff --git a/share.c b/share.c index f450934..d0fd0f5 100644 --- a/share.c +++ b/share.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: share.c,v 1.1 2000/06/17 12:09:38 mdw Exp $ + * $Id: share.c,v 1.6 2001/02/03 16:05:41 mdw Exp $ * * Shamir's secret sharing * @@ -30,6 +30,25 @@ /*----- Revision history --------------------------------------------------* * * $Log: share.c,v $ + * Revision 1.6 2001/02/03 16:05:41 mdw + * Now @mp_drop@ checks its argument is non-NULL before attempting to free + * it. Note that the macro version @MP_DROP@ doesn't do this. + * + * Revision 1.5 2000/12/06 20:30:10 mdw + * Change secret sharing interface: present the secret at share + * construction time. + * + * Revision 1.4 2000/10/08 12:16:17 mdw + * Use @MP_EQ@ instead of @MP_CMP@. + * + * Revision 1.3 2000/06/24 18:29:05 mdw + * Interface change: allow shares to be extracted from a context on demand, + * rather than building them all up-front. + * + * Revision 1.2 2000/06/18 23:05:19 mdw + * Minor performance tweak: use Barrett reduction rather than Montgomery. + * Fast secret sharing isn't done here, though: see `gfshare' instead. + * * Revision 1.1 2000/06/17 12:09:38 mdw * Shamir's secret sharing system. * @@ -44,7 +63,7 @@ #include "grand.h" #include "mp.h" #include "mpint.h" -#include "mpmont.h" +#include "mpbarrett.h" #include "mprand.h" #include "pgen.h" #include "rabin.h" @@ -55,19 +74,17 @@ /* --- @share_create@ --- * * * Arguments: @share *s@ = pointer to share context to initialize - * @unsigned t, n@ = threshold parameters for the system + * @unsigned t@ = threshold for the system * * Returns: --- * * Use: Initializes a sharing context. */ -void share_create(share *s, unsigned t, unsigned n) +void share_create(share *s, unsigned t) { s->t = t; - s->n = n; s->i = 0; - s->s = 0; s->p = 0; s->v = 0; } @@ -84,57 +101,41 @@ void share_create(share *s, unsigned t, unsigned n) 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); - } + for (i = 0; i < s->t; i++) + 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); + mp_drop(s->p); } /* --- @share_mkshares@ --- * * * Arguments: @share *s@ = pointer to share context to fill in * @grand *r@ = pointer to random number source + * @mp *n@ = the secret to share * * Returns: --- * - * Use: Generates @c->n@ secret shares, such that any @c->t@ of them - * may be used to recover the secret. - * + * Use: Initializes a sharing context to be able to create shares. * 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. + * particular, @t@ 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) +void share_mkshares(share *s, grand *r, mp *n) { - mp **v; unsigned i; - mp *u; - mpmont mm; /* --- If there's no prime, construct one --- */ @@ -142,7 +143,7 @@ void share_mkshares(share *s, grand *r) pgen_filterctx pf; rabin pr; mp *p; - unsigned bits = (mp_octets(s->s) + 1) * 8; + unsigned bits = (mp_octets(n) + 1) * 8; pf.step = 2; p = mprand(MP_NEW, bits, r, 1); @@ -150,52 +151,52 @@ void share_mkshares(share *s, grand *r) 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 --- */ + /* --- Construct the polynomial --- */ 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; + s->v = xmalloc(s->t * sizeof(share_pt)); + for (i = 0; i < s->t - 1; i++) + s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0); + s->v[s->t - 1].y = mp_copy(n); +} - /* --- Evaluate the polynomial at %$x = i + 1$% --- */ +/* --- @share_get@ --- * + * + * Arguments: @share *s@ = pointer to share conext + * @mp *d@ = destination for the share + * @unsigned x@ = share index to fetch + * + * Returns: The share, as requested. + * + * Use: Extracts a share from the system. You may extract @MPW_MAX@ + * shares, or @s->p@ shares from the system, whichever is + * smaller. Shares are indexed from 0. + */ - 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); - } +mp *share_get(share *s, mp *d, unsigned x) +{ + mpbarrett mb; + mpw uw = x + 1; + mp u; + unsigned i; - /* --- Reduce the final result --- */ + /* --- Various bits of initialization --- */ - s->v[i].x = i; - s->v[i].y = mpmont_reduce(&mm, m, m); + mp_build(&u, &uw, &uw + 1); + mp_drop(d); - /* --- Compute the next point in Montgomery space --- */ + /* --- Evaluate the polynomial at %$x = i + 1$% --- */ - u = mp_add(u, u, mm.r); - if (MP_CMP(u, >=, s->p)) - u = mp_sub(u, u, s->p); + d = MP_ZERO; + mpbarrett_create(&mb, s->p); + for (i = 0; i < s->t; i++) { + d = mp_mul(d, d, &u); + d = mp_add(d, d, s->v[i].y); + d = mpbarrett_reduce(&mb, d, d); } - mpmont_destroy(&mm); - - /* --- Dispose of various bits of old rubbish --- */ + mpbarrett_destroy(&mb); - for (i = 0; i < s->t; i++) - mp_drop(v[i]); - mp_drop(u); - xfree(v); + return (d); } /* --- @share_add@ --- * @@ -215,15 +216,18 @@ unsigned share_add(share *s, unsigned x, mp *y) /* --- If no vector has been allocated, create one --- */ if (!s->v) { + unsigned i; s->v = xmalloc(s->t * sizeof(share_pt)); s->i = 0; + for (i = 0; i < s->t; i++) + s->v[i].y = 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].x = x + 1; s->v[s->i].y = mp_copy(y); s->i++; @@ -244,9 +248,10 @@ unsigned share_add(share *s, unsigned x, mp *y) mp *share_combine(share *s) { mp *a = MP_ZERO; - mpmont mm; + mpbarrett mb; unsigned i, j; - mp *ii = MP_NEW, *jj = MP_NEW; + mp ii, jj; + mpw iiw, jjw; mp *m = MP_NEW; /* --- Sanity checking --- */ @@ -255,43 +260,41 @@ mp *share_combine(share *s) /* --- Initialization --- */ - mpmont_create(&mm, s->p); + mpbarrett_create(&mb, s->p); + mp_build(&ii, &iiw, &iiw + 1); + mp_build(&jj, &jjw, &jjw + 1); /* --- Grind through the shares --- */ for (i = 0; i < s->t; i++) { - mp *c = mp_copy(mm.r); + mp *c = MP_ONE; - ii = mp_fromuint(ii, s->v[i].x + 1); + iiw = s->v[i].x; for (j = 0; j < s->t; j++) { if (i == j) continue; - jj = mp_fromuint(jj, s->v[j].x + 1); + jjw = s->v[j].x; if (s->v[j].x >= s->v[i].x) - m = mp_sub(m, jj, ii); + m = mp_sub(m, &jj, &ii); else { - m = mp_sub(m, ii, jj); + 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); + c = mp_mul(c, c, &jj); + c = mpbarrett_reduce(&mb, c, c); + c = mp_mul(c, c, m); + c = mpbarrett_reduce(&mb, c, c); } - m = mpmont_mul(&mm, m, s->v[i].y, mm.r2); - c = mpmont_mul(&mm, c, c, m); + c = mp_mul(c, c, s->v[i].y); + c = mpbarrett_reduce(&mb, c, c); 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); + a = mpbarrett_reduce(&mb, a, a); mp_drop(m); - mpmont_destroy(&mm); + mpbarrett_destroy(&mb); return (a); } @@ -307,7 +310,7 @@ static int verify(grand *r) unsigned t = r->ops->range(r, n - 1) + 1; unsigned len = r->ops->range(r, 160); - share_pt *v = xmalloc(t * sizeof(share_pt)); + mp **v = xmalloc(t * sizeof(mp *)); unsigned *p = xmalloc(n * sizeof(unsigned)); mp *sec = mprand(MP_NEW, len, r, 0); share s; @@ -326,27 +329,22 @@ static int verify(grand *r) 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); - } + share_create(&s, t); + share_mkshares(&s, r, sec); + for (i = 0; i < t; i++) + v[i] = share_get(&s, MP_NEW, p[i]); pp = mp_copy(s.p); share_destroy(&s); + assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2); - assert(mparena_count(MPARENA_GLOBAL) == t + 2); - - share_create(&s, t, n); + share_create(&s, t); s.p = pp; - for (i = 0; i < t; i++) { - share_add(&s, v[i].x, v[i].y); - } + for (i = 0; i < t; i++) + share_add(&s, p[i], v[i]); ss = share_combine(&s); share_destroy(&s); - if (MP_CMP(sec, !=, ss)) { + if (!MP_EQ(sec, ss)) { ok = 0; fprintf(stderr, "\nbad recombination of shares\n"); }; @@ -355,12 +353,12 @@ static int verify(grand *r) mp_drop(ss); for (i = 0; i < t; i++) - mp_drop(v[i].y); + mp_drop(v[i]); xfree(v); xfree(p); - assert(mparena_count(MPARENA_GLOBAL) == 0); + assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0); return (ok); }