X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/71dfe576992502b96b601a7e3dce7a9d98e1682e..cd6eca4375f46a35b93e2fea4b0428a23b451aa3:/share.c diff --git a/share.c b/share.c index f450934..1afa189 100644 --- a/share.c +++ b/share.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: share.c,v 1.1 2000/06/17 12:09:38 mdw Exp $ + * $Id$ * * Shamir's secret sharing * * (c) 2000 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,26 +15,18 @@ * 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 @@ -44,7 +36,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 +47,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 +74,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 +116,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 +124,72 @@ void share_mkshares(share *s, grand *r) rabin_iters(bits), pgen_test, &pr); } - /* --- Construct the coefficients --- */ + /* --- Construct the polynomial --- */ - mpmont_create(&mm, s->p); - v = xmalloc(s->t * sizeof(mp *)); + if (!s->v) + s->v = xmalloc(s->t * sizeof(share_pt)); 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 --- */ + s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0); + s->v[s->t - 1].y = mp_copy(n); +} - if (!s->v) - s->v = xmalloc(s->n * sizeof(share_pt)); +/* --- @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. + */ - u = mp_copy(mm.r); - for (i = 0; i < s->n; i++) { - mp *m = MP_ZERO; - unsigned j; +mp *share_get(share *s, mp *d, unsigned x) +{ + mpbarrett mb; + mpw uw = x + 1; + mp u; + unsigned i; - /* --- Evaluate the polynomial at %$x = i + 1$% --- */ + /* --- Various bits of initialization --- */ - 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_build(&u, &uw, &uw + 1); + mp_drop(d); - /* --- Reduce the final result --- */ + /* --- Evaluate the polynomial at %$x = i + 1$% --- */ - s->v[i].x = i; - s->v[i].y = mpmont_reduce(&mm, m, m); + 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); + } + mpbarrett_destroy(&mb); - /* --- Compute the next point in Montgomery space --- */ + return (d); +} - u = mp_add(u, u, mm.r); - if (MP_CMP(u, >=, s->p)) - u = mp_sub(u, u, s->p); - } - mpmont_destroy(&mm); +/* --- @share_addedp@ --- * + * + * Arguments: @share *s@ = pointer to sharing context + * @unsigned x@ = which share number to check + * + * Returns: Nonzero if share @x@ has been added already, zero if it + * hasn't. + */ - /* --- Dispose of various bits of old rubbish --- */ +int share_addedp(share *s, unsigned x) +{ + unsigned i; - for (i = 0; i < s->t; i++) - mp_drop(v[i]); - mp_drop(u); - xfree(v); + for (i = 0; i < s->i; i++) { + if (s->v[i].x == x + 1) + return (1); + } + return (0); } /* --- @share_add@ --- * @@ -212,18 +206,22 @@ void share_mkshares(share *s, grand *r) unsigned share_add(share *s, unsigned x, mp *y) { + assert(((void)"Share context is full", s->i < s->t)); + assert(((void)"Share already present", !share_addedp(s, x))); + /* --- 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 +242,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 +254,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); + m = mp_modinv(m, m, s->p); + 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 +304,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 +323,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 +347,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); }