X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/3d64a35c9b151e739eb6a8712915810ea574eac8..cd6eca4375f46a35b93e2fea4b0428a23b451aa3:/share.c diff --git a/share.c b/share.c index 0d61a78..1afa189 100644 --- a/share.c +++ b/share.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: share.c,v 1.3 2000/06/24 18:29:05 mdw Exp $ + * $Id$ * * Shamir's secret sharing * * (c) 2000 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,34 +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.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. - * - */ - /*----- Header files ------------------------------------------------------*/ #include @@ -74,7 +58,6 @@ void share_create(share *s, unsigned t) { s->t = t; s->i = 0; - s->s = 0; s->p = 0; s->v = 0; } @@ -96,38 +79,34 @@ void share_destroy(share *s) /* --- Dispose of the share vector --- */ if (s->v) { - for (i = 0; i < s->t; 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: Initializes a sharing context to be able to create shares. * The context structure is expected to be mostly filled in. In - * particular, @t@ 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) { unsigned i; @@ -137,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); @@ -151,7 +130,7 @@ void share_mkshares(share *s, grand *r) 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(s->s); + s->v[s->t - 1].y = mp_copy(n); } /* --- @share_get@ --- * @@ -177,8 +156,7 @@ mp *share_get(share *s, mp *d, unsigned x) /* --- Various bits of initialization --- */ mp_build(&u, &uw, &uw + 1); - if (d) - mp_drop(d); + mp_drop(d); /* --- Evaluate the polynomial at %$x = i + 1$% --- */ @@ -194,6 +172,26 @@ mp *share_get(share *s, mp *d, unsigned x) return (d); } +/* --- @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. + */ + +int share_addedp(share *s, unsigned x) +{ + unsigned i; + + for (i = 0; i < s->i; i++) { + if (s->v[i].x == x + 1) + return (1); + } + return (0); +} + /* --- @share_add@ --- * * * Arguments: @share *s@ = pointer to sharing context @@ -208,6 +206,9 @@ mp *share_get(share *s, mp *d, unsigned x) 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) { @@ -218,8 +219,6 @@ unsigned share_add(share *s, unsigned x, mp *y) 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 + 1; @@ -275,7 +274,7 @@ mp *share_combine(share *s) m = mp_sub(m, &ii, &jj); m = mp_sub(m, s->p, m); } - mp_gcd(0, 0, &m, s->p, 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); @@ -288,9 +287,7 @@ mp *share_combine(share *s) } a = mpbarrett_reduce(&mb, a, a); - s->s = mp_copy(a); - if (m) - mp_drop(m); + mp_drop(m); mpbarrett_destroy(&mb); return (a); } @@ -327,8 +324,7 @@ static int verify(grand *r) } share_create(&s, t); - s.s = mp_copy(sec); - share_mkshares(&s, r); + 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); @@ -342,7 +338,7 @@ static int verify(grand *r) 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"); };