git.distorted.org.uk Git - u/mdw/catacomb/blob - share.c

   1 /* -*-c-*-
   2  *
   3  * $Id: share.c,v 1.7 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Shamir's secret sharing
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include "grand.h"
  37 #include "mp.h"
  38 #include "mpint.h"
  39 #include "mpbarrett.h"
  40 #include "mprand.h"
  41 #include "pgen.h"
  42 #include "rabin.h"
  43 #include "share.h"
  44
  45 /*----- Main code ---------------------------------------------------------*/
  46
  47 /* --- @share_create@ --- *
  48  *
  49  * Arguments:   @share *s@ = pointer to share context to initialize
  50  *              @unsigned t@ = threshold for the system
  51  *
  52  * Returns:     ---
  53  *
  54  * Use:         Initializes a sharing context.
  55  */
  56
  57 void share_create(share *s, unsigned t)
  58 {
  59   s->t = t;
  60   s->i = 0;
  61   s->p = 0;
  62   s->v = 0;
  63 }
  64
  65 /* --- @share_destroy@ --- *
  66  *
  67  * Arguments:   @share *s@ = pointer to share context to destroy
  68  *
  69  * Returns:     ---
  70  *
  71  * Use:         Disposes of a sharing context.  All memory is freed, all
  72  *              integers are dropped.
  73  */
  74
  75 void share_destroy(share *s)
  76 {
  77   unsigned i;
  78
  79   /* --- Dispose of the share vector --- */
  80
  81   if (s->v) {
  82     for (i = 0; i < s->t; i++)
  83       mp_drop(s->v[i].y);
  84     xfree(s->v);
  85   }
  86
  87   /* --- Other stuff --- */
  88
  89   mp_drop(s->p);
  90 }
  91
  92 /* --- @share_mkshares@ --- *
  93  *
  94  * Arguments:   @share *s@ = pointer to share context to fill in
  95  *              @grand *r@ = pointer to random number source
  96  *              @mp *n@ = the secret to share
  97  *
  98  * Returns:     ---
  99  *
 100  * Use:         Initializes a sharing context to be able to create shares.
 101  *              The context structure is expected to be mostly filled in.  In
 102  *              particular, @t@ must be initialized.  If @p@ is zero, a prime
 103  *              number of appropriate size is generated automatically.  If
 104  *              @v@ is zero, a vector of appropriate size is allocated.  You
 105  *              should use the macro @SHARE_INIT@ or @share_create@ to
 106  *              construct sharing contexts.
 107  */
 108
 109 void share_mkshares(share *s, grand *r, mp *n)
 110 {
 111   unsigned i;
 112
 113   /* --- If there's no prime, construct one --- */
 114
 115   if (!s->p) {
 116     pgen_filterctx pf;
 117     rabin pr;
 118     mp *p;
 119     unsigned bits = (mp_octets(n) + 1) * 8;
 120
 121     pf.step = 2;
 122     p = mprand(MP_NEW, bits, r, 1);
 123     s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
 124                 rabin_iters(bits), pgen_test, &pr);
 125   }
 126
 127   /* --- Construct the polynomial --- */
 128
 129   if (!s->v)
 130     s->v = xmalloc(s->t * sizeof(share_pt));
 131   for (i = 0; i < s->t - 1; i++)
 132     s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0);
 133   s->v[s->t - 1].y = mp_copy(n);
 134 }
 135
 136 /* --- @share_get@ --- *
 137  *
 138  * Arguments:   @share *s@ = pointer to share conext
 139  *              @mp *d@ = destination for the share
 140  *              @unsigned x@ = share index to fetch
 141  *
 142  * Returns:     The share, as requested.
 143  *
 144  * Use:         Extracts a share from the system.  You may extract @MPW_MAX@
 145  *              shares, or @s->p@ shares from the system, whichever is
 146  *              smaller.  Shares are indexed from 0.
 147  */
 148
 149 mp *share_get(share *s, mp *d, unsigned x)
 150 {
 151   mpbarrett mb;
 152   mpw uw = x + 1;
 153   mp u;
 154   unsigned i;
 155
 156   /* --- Various bits of initialization --- */
 157
 158   mp_build(&u, &uw, &uw + 1);
 159   mp_drop(d);
 160
 161   /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 162
 163   d = MP_ZERO;
 164   mpbarrett_create(&mb, s->p);
 165   for (i = 0; i < s->t; i++) {
 166     d = mp_mul(d, d, &u);
 167     d = mp_add(d, d, s->v[i].y);
 168     d = mpbarrett_reduce(&mb, d, d);
 169   }
 170   mpbarrett_destroy(&mb);
 171
 172   return (d);
 173 }
 174
 175 /* --- @share_add@ --- *
 176  *
 177  * Arguments:   @share *s@ = pointer to sharing context
 178  *              @unsigned x@ = which share number this is
 179  *              @mp *y@ = the share value
 180  *
 181  * Returns:     Number of shares required before recovery may be performed.
 182  *
 183  * Use:         Adds a share to the context.  The context must have been
 184  *              initialized with the correct prime @p@ and threshold @t@.
 185  */
 186
 187 unsigned share_add(share *s, unsigned x, mp *y)
 188 {
 189   /* --- If no vector has been allocated, create one --- */
 190
 191   if (!s->v) {
 192     unsigned i;
 193     s->v = xmalloc(s->t * sizeof(share_pt));
 194     s->i = 0;
 195     for (i = 0; i < s->t; i++)
 196       s->v[i].y = 0;
 197   }
 198
 199   assert(((void)"Share context is full", s->i < s->t));
 200
 201   /* --- Store the share in the vector --- */
 202
 203   s->v[s->i].x = x + 1;
 204   s->v[s->i].y = mp_copy(y);
 205   s->i++;
 206
 207   /* --- Done --- */
 208
 209   return (s->t - s->i);
 210 }
 211
 212 /* --- @share_combine@ --- *
 213  *
 214  * Arguments:   @share *s@ = pointer to share context
 215  *
 216  * Returns:     The secret, as a multiprecision integer.
 217  *
 218  * Use:         Reconstructs a secret, given enough shares.
 219  */
 220
 221 mp *share_combine(share *s)
 222 {
 223   mp *a = MP_ZERO;
 224   mpbarrett mb;
 225   unsigned i, j;
 226   mp ii, jj;
 227   mpw iiw, jjw;
 228   mp *m = MP_NEW;
 229
 230   /* --- Sanity checking --- */
 231
 232   assert(((void)"Not enough shares yet", s->i == s->t));
 233
 234   /* --- Initialization --- */
 235
 236   mpbarrett_create(&mb, s->p);
 237   mp_build(&ii, &iiw, &iiw + 1);
 238   mp_build(&jj, &jjw, &jjw + 1);
 239
 240   /* --- Grind through the shares --- */
 241
 242   for (i = 0; i < s->t; i++) {
 243     mp *c = MP_ONE;
 244
 245     iiw = s->v[i].x;
 246     for (j = 0; j < s->t; j++) {
 247       if (i == j)
 248         continue;
 249       jjw = s->v[j].x;
 250       if (s->v[j].x >= s->v[i].x)
 251         m = mp_sub(m, &jj, &ii);
 252       else {
 253         m = mp_sub(m, &ii, &jj);
 254         m = mp_sub(m, s->p, m);
 255       }
 256       m = mp_modinv(m, m, s->p);
 257       c = mp_mul(c, c, &jj);
 258       c = mpbarrett_reduce(&mb, c, c);
 259       c = mp_mul(c, c, m);
 260       c = mpbarrett_reduce(&mb, c, c);
 261     }
 262     c = mp_mul(c, c, s->v[i].y);
 263     c = mpbarrett_reduce(&mb, c, c);
 264     a = mp_add(a, a, c);
 265     mp_drop(c);
 266   }
 267
 268   a = mpbarrett_reduce(&mb, a, a);
 269   mp_drop(m);
 270   mpbarrett_destroy(&mb);
 271   return (a);
 272 }
 273
 274 /*----- Test rig ----------------------------------------------------------*/
 275
 276 #ifdef TEST_RIG
 277
 278 #include "fibrand.h"
 279
 280 static int verify(grand *r)
 281 {
 282   unsigned n = r->ops->range(r, 16) + 8;
 283   unsigned t = r->ops->range(r, n - 1) + 1;
 284   unsigned len = r->ops->range(r, 160);
 285
 286   mp **v = xmalloc(t * sizeof(mp *));
 287   unsigned *p = xmalloc(n * sizeof(unsigned));
 288   mp *sec = mprand(MP_NEW, len, r, 0);
 289   share s;
 290   mp *pp;
 291   mp *ss;
 292   unsigned i;
 293
 294   int ok = 1;
 295
 296   for (i = 0; i < n; i++)
 297     p[i] = i;
 298   for (i = 0; i < t; i++) {
 299     unsigned long j = r->ops->range(r, n - i);
 300     unsigned x = p[i];
 301     p[i] = p[i + j];
 302     p[i + j] = x;
 303   }
 304
 305   share_create(&s, t);
 306   share_mkshares(&s, r, sec);
 307   for (i = 0; i < t; i++)
 308     v[i] = share_get(&s, MP_NEW, p[i]);
 309   pp = mp_copy(s.p);
 310   share_destroy(&s);
 311   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2);
 312
 313   share_create(&s, t);
 314   s.p = pp;
 315   for (i = 0; i < t; i++)
 316     share_add(&s, p[i], v[i]);
 317   ss = share_combine(&s);
 318   share_destroy(&s);
 319
 320   if (!MP_EQ(sec, ss)) {
 321     ok = 0;
 322     fprintf(stderr, "\nbad recombination of shares\n");
 323   };
 324
 325   mp_drop(sec);
 326   mp_drop(ss);
 327
 328   for (i = 0; i < t; i++)
 329     mp_drop(v[i]);
 330
 331   xfree(v);
 332   xfree(p);
 333
 334   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0);
 335   return (ok);
 336 }
 337
 338 int main(void)
 339 {
 340   grand *r = fibrand_create(0);
 341   unsigned i;
 342   int ok = 1;
 343
 344   fputs("share: ", stdout);
 345   for (i = 0; i < 40; i++) {
 346     if (!verify(r))
 347       ok = 0;
 348     fputc('.', stdout);
 349     fflush(stdout);
 350   }
 351
 352   if (ok)
 353     fputs(" ok\n", stdout);
 354   else
 355     fputs(" failed\n", stdout);
 356   return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 357 }
 358
 359 #endif
 360
 361 /*----- That's all, folks -------------------------------------------------*/