+++ /dev/null
-/* -*-c-*-
- *
- * $Id$
- *
- * 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 <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff