X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/6c1035f55a83af8083af17432f2b4eb5afdb39dd..e564e3f84ad0ea42b78559c0bfe304893fd5e76b:/gfshare.c diff --git a/gfshare.c b/gfshare.c index cdc00d2..99b1223 100644 --- a/gfshare.c +++ b/gfshare.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: gfshare.c,v 1.1 2000/06/17 10:56:30 mdw Exp $ + * $Id$ * - * Secret sharing over %$gf(2^8)$% + * Secret sharing over %$\gf{2^8}$% * * (c) 2000 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,31 +15,24 @@ * 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: gfshare.c,v $ - * Revision 1.1 2000/06/17 10:56:30 mdw - * Fast but nonstandard secret sharing system. - * - */ - /*----- Header files ------------------------------------------------------*/ #include #include #include +#include #include #include @@ -51,14 +44,14 @@ /*----- Static variables --------------------------------------------------*/ -static octet gflog[] = GFSHARE_LOG, gfexp[] = GFSHARE_EXP; +static const octet gflog[] = GFSHARE_LOG, gfexp[] = GFSHARE_EXP; /*----- Main code ---------------------------------------------------------*/ /* --- @gfshare_create@ --- * * * Arguments: @gfshare *s@ = pointer to share context to initialize - * @unsigned t, n@ = threshold parameters for the system + * @unsigned t@ = threshold for the system * @size_t sz@ = size of the secret * * Returns: --- @@ -66,13 +59,11 @@ static octet gflog[] = GFSHARE_LOG, gfexp[] = GFSHARE_EXP; * Use: Initializes a sharing context. */ -void gfshare_create(gfshare *s, unsigned t, unsigned n, size_t sz) +void gfshare_create(gfshare *s, unsigned t, size_t sz) { s->t = t; - s->n = n; s->i = 0; s->sz = sz; - s->s = 0; s->v = 0; } @@ -89,93 +80,93 @@ void gfshare_create(gfshare *s, unsigned t, unsigned n, size_t sz) void gfshare_destroy(gfshare *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) - XS_FREE(s->v[i].y); - } - xfree(s->v); - } + if (s->v) + XS_FREE(s->v); } /* --- @gfshare_mkshares@ --- * * * Arguments: @gfshare *s@ = pointer to share context to fill in * @grand *r@ = pointer to random number source + * @const void *buf@ = pointer to 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@, @ssz@ and @s@ must be initialized. If - * @v@ is zero, a vector of appropriate size is allocated. You - * should use the macro @GFSHARE_INIT@ or @gfshare_create@ to - * construct sharing contexts. + * particular, @t@ must be initialized. If @v@ is zero, a + * vector of appropriate size is allocated. You should use the + * macro @GFSHARE_INIT@ or @gfshare_create@ to construct sharing + * contexts. */ -void gfshare_mkshares(gfshare *s, grand *r) +void gfshare_mkshares(gfshare *s, grand *r, const void *buf) { - octet *v; - unsigned i; - - /* --- Construct the coefficients --- */ - - v = XS_ALLOC(s->sz * s->t); - r->ops->fill(r, v, s->sz * (s->t - 1)); - memcpy(v + s->sz * (s->t - 1), s->s, s->sz); - - - /* --- Construct the shares --- */ - - if (!s->v) - s->v = xmalloc(s->n * sizeof(gfshare_pt)); - - for (i = 0; i < s->n; i++) { - unsigned j; - const octet *p = v; - unsigned ilog = gflog[i + 1]; + s->v = XS_ALLOC(s->sz * s->t); + r->ops->fill(r, s->v, s->sz * (s->t - 1)); + memcpy(s->v + s->sz * (s->t - 1), buf, s->sz); +} - /* --- Evaluate the polynomial at %$x = i + 1$% --- */ +/* --- @gfshare_get@ --- * + * + * Arguments: @gfshare *s@ = pointer to share conext + * @unsigned x@ = share index to fetch + * @void *buf@ = pointer to output buffer + * + * Returns: --- + * + * Use: Extracts a share from the system. You may extract up to 255 + * shares from the system. Shares are indexed from 0. + */ - s->v[i].y = XS_ALLOC(s->sz); - memcpy(s->v[i].y, p, s->sz); - p += s->sz; - for (j = 1; j < s->t; j++) { - octet *q = s->v[i].y; - unsigned k; - for (k = 0; k < s->sz; k++) { - unsigned qq = *q; - if (qq) - qq = gfexp[ilog + gflog[qq]]; - *q++ = qq ^ *p++; - } +void gfshare_get(gfshare *s, unsigned x, void *buf) +{ + unsigned i; + const octet *p = s->v; + unsigned ilog = gflog[x + 1]; + + /* --- Evaluate the polynomial at %$x = i + 1$% --- */ + + memcpy(buf, p, s->sz); + p += s->sz; + + for (i = 1; i < s->t; i++) { + octet *q = buf; + unsigned k; + for (k = 0; k < s->sz; k++) { + unsigned qq = *q; + if (qq) + qq = gfexp[ilog + gflog[qq]]; + *q++ = qq ^ *p++; } - s->v[i].x = i; } +} - /* --- Dispose of various bits of old rubbish --- */ +/* --- @gfshare_addedp@ --- * + * + * Arguments: @gfshare *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 gfshare_addedp(gfshare *s, unsigned x) +{ + unsigned i; - XS_FREE(v); + for (i = 0; i < s->i; i++) { + if (GFSHARE_INDEX(s, i) == x + 1) + return (1); + } + return (0); } /* --- @gfshare_add@ --- * * * Arguments: @gfshare *s@ = pointer to sharing context * @unsigned x@ = which share number this is - * @const octet *y@ = the share value + * @const void *y@ = the share value * * Returns: Number of shares required before recovery may be performed. * @@ -183,22 +174,25 @@ void gfshare_mkshares(gfshare *s, grand *r) * initialized with the correct threshold @t@. */ -unsigned gfshare_add(gfshare *s, unsigned x, const octet *y) +unsigned gfshare_add(gfshare *s, unsigned x, const void *y) { + octet *p; + + assert(((void)"Share context is full", s->i < s->t)); + assert(((void)"Share already present", !gfshare_addedp(s, x))); + /* --- If no vector has been allocated, create one --- */ if (!s->v) { - s->v = xmalloc(s->t * sizeof(gfshare_pt)); + s->v = XS_ALLOC(s->t * (s->sz + 1)); 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 = XS_ALLOC(s->sz); - memcpy(s->v[s->i].y, y, s->sz); + p = &GFSHARE_INDEX(s, s->i); + *p++ = x + 1; + memcpy(p, y, s->sz); s->i++; /* --- Done --- */ @@ -209,56 +203,58 @@ unsigned gfshare_add(gfshare *s, unsigned x, const octet *y) /* --- @gfshare_combine@ --- * * * Arguments: @gfshare *s@ = pointer to share context - * @octet *buf@ = pointer to output buffer for the secret + * @void *buf@ = pointer to output buffer for the secret * * Returns: --- * * Use: Reconstructs a secret, given enough shares. */ -void gfshare_combine(gfshare *s, octet *buf) +void gfshare_combine(gfshare *s, void *buf) { unsigned i, j; - octet *v; + unsigned xi, xj; /* --- Sanity checking --- */ assert(((void)"Not enough shares yet", s->i == s->t)); - /* --- Precomputation of coefficients --- */ + /* --- Grind through the shares --- */ - v = XS_ALLOC(s->t); + memset(buf, 0, s->sz); for (i = 0; i < s->t; i++) { + octet *p = buf; + octet *q = &GFSHARE_INDEX(s, i); unsigned c = 0, ci = 0; + + /* --- Compute the magic coefficient --- */ + + xi = *q++; for (j = 0; j < s->t; j++) { if (i == j) continue; - c += gflog[s->v[j].x + 1]; + xj = GFSHARE_INDEX(s, j); + c += gflog[xj]; if (c >= 0xff) c -= 0xff; - ci += gflog[(s->v[i].x + 1) ^ (s->v[j].x + 1)]; + ci += gflog[xi ^ xj]; if (ci >= 0xff) ci -= 0xff; } if (ci > c) c += 0xff; c -= ci; - v[i] = c; - } - /* --- Grind through the shares --- */ + /* --- Work out another layer of the secret --- */ - for (i = 0; i < s->sz; i++) { - unsigned x = 0; - for (j = 0; j < s->t; j++) { - if (s->v[j].y[i]) - x ^= gfexp[v[j] + gflog[s->v[j].y[i]]]; + p = buf; + for (j = 0; j < s->sz; j++) { + if (*q) + *p ^= gfexp[c + gflog[*q]]; + p++, q++; } - buf[i] = x; } - - XS_FREE(v); } /*----- Test rig ----------------------------------------------------------*/ @@ -273,7 +269,7 @@ static int verify(grand *r) unsigned t = r->ops->range(r, n - 1) + 1; unsigned len = r->ops->range(r, 32) + 1; - gfshare_pt *v = xmalloc(t * sizeof(gfshare_pt)); + octet *v = xmalloc(t * len); unsigned *p = xmalloc(n * sizeof(unsigned)); octet *sec = xmalloc(len), *sbuf = xmalloc(len); gfshare s; @@ -292,21 +288,16 @@ static int verify(grand *r) r->ops->fill(r, sec, len); - gfshare_create(&s, t, n, len); - s.s = sec; + gfshare_create(&s, t, len); - gfshare_mkshares(&s, r); - for (i = 0; i < t; i++) { - v[i].x = s.v[p[i]].x; - v[i].y = xmalloc(len); - memcpy(v[i].y, s.v[p[i]].y, len); - } + gfshare_mkshares(&s, r, sec); + for (i = 0; i < t; i++) + gfshare_get(&s, p[i], v + (i * len)); gfshare_destroy(&s); - gfshare_create(&s, t, n, len); - for (i = 0; i < t; i++) { - gfshare_add(&s, v[i].x, v[i].y); - } + gfshare_create(&s, t, len); + for (i = 0; i < t; i++) + gfshare_add(&s, p[i], v + (i * len)); gfshare_combine(&s, sbuf); gfshare_destroy(&s); @@ -318,8 +309,6 @@ static int verify(grand *r) xfree(sec); xfree(sbuf); - for (i = 0; i < t; i++) - xfree(v[i].y); xfree(v); xfree(p);