X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/misc/share.c diff --git a/misc/share.c b/misc/share.c new file mode 100644 index 0000000..e99781e --- /dev/null +++ b/misc/share.c @@ -0,0 +1,380 @@ +/* -*-c-*- + * + * 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. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "grand.h" +#include "mp.h" +#include "mpint.h" +#include "mpbarrett.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@ = threshold for the system + * + * Returns: --- + * + * Use: Initializes a sharing context. + */ + +void share_create(share *s, unsigned t) +{ + s->t = t; + s->i = 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 i; + + /* --- Dispose of the share vector --- */ + + if (s->v) { + for (i = 0; i < s->t; i++) + mp_drop(s->v[i].y); + xfree(s->v); + } + + /* --- Other stuff --- */ + + 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@ 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 *n) +{ + unsigned i; + + /* --- If there's no prime, construct one --- */ + + if (!s->p) { + pgen_filterctx pf; + rabin pr; + mp *p; + unsigned bits = (mp_octets(n) + 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 polynomial --- */ + + if (!s->v) + 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); +} + +/* --- @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. + */ + +mp *share_get(share *s, mp *d, unsigned x) +{ + mpbarrett mb; + mpw uw = x + 1; + mp u; + unsigned i; + + /* --- Various bits of initialization --- */ + + mp_build(&u, &uw, &uw + 1); + mp_drop(d); + + /* --- Evaluate the polynomial at %$x = i + 1$% --- */ + + 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); + + 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 + * @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) +{ + 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; + } + + /* --- Store the share in the vector --- */ + + s->v[s->i].x = x + 1; + 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; + mpbarrett mb; + unsigned i, j; + mp ii, jj; + mpw iiw, jjw; + mp *m = MP_NEW; + + /* --- Sanity checking --- */ + + assert(((void)"Not enough shares yet", s->i == s->t)); + + /* --- Initialization --- */ + + 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_ONE; + + iiw = s->v[i].x; + for (j = 0; j < s->t; j++) { + if (i == j) + continue; + jjw = s->v[j].x; + 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); + } + 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); + } + 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 = mpbarrett_reduce(&mb, a, a); + mp_drop(m); + mpbarrett_destroy(&mb); + 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); + + mp **v = xmalloc(t * sizeof(mp *)); + 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); + 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); + + share_create(&s, t); + s.p = pp; + for (i = 0; i < t; i++) + share_add(&s, p[i], v[i]); + ss = share_combine(&s); + share_destroy(&s); + + if (!MP_EQ(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]); + + xfree(v); + xfree(p); + + assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 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 -------------------------------------------------*/