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

   1 /* -*-c-*-
   2  *
   3  * $Id: share.c,v 1.2 2000/06/18 23:05:19 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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: share.c,v $
  33  * Revision 1.2  2000/06/18 23:05:19  mdw
  34  * Minor performance tweak: use Barrett reduction rather than Montgomery.
  35  * Fast secret sharing isn't done here, though: see `gfshare' instead.
  36  *
  37  * Revision 1.1  2000/06/17 12:09:38  mdw
  38  * Shamir's secret sharing system.
  39  *
  40  */
  41
  42 /*----- Header files ------------------------------------------------------*/
  43
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 #include "grand.h"
  49 #include "mp.h"
  50 #include "mpint.h"
  51 #include "mpbarrett.h"
  52 #include "mprand.h"
  53 #include "pgen.h"
  54 #include "rabin.h"
  55 #include "share.h"
  56
  57 /*----- Main code ---------------------------------------------------------*/
  58
  59 /* --- @share_create@ --- *
  60  *
  61  * Arguments:   @share *s@ = pointer to share context to initialize
  62  *              @unsigned t, n@ = threshold parameters for the system
  63  *
  64  * Returns:     ---
  65  *
  66  * Use:         Initializes a sharing context.
  67  */
  68
  69 void share_create(share *s, unsigned t, unsigned n)
  70 {
  71   s->t = t;
  72   s->n = n;
  73   s->i = 0;
  74   s->s = 0;
  75   s->p = 0;
  76   s->v = 0;
  77 }
  78
  79 /* --- @share_destroy@ --- *
  80  *
  81  * Arguments:   @share *s@ = pointer to share context to destroy
  82  *
  83  * Returns:     ---
  84  *
  85  * Use:         Disposes of a sharing context.  All memory is freed, all
  86  *              integers are dropped.
  87  */
  88
  89 void share_destroy(share *s)
  90 {
  91   unsigned n;
  92   unsigned i;
  93
  94   /* --- Dispose of the share vector --- */
  95
  96   if (s->v) {
  97     if (s->i)
  98       n = s->i;
  99     else if (s->n)
 100       n = s->n;
 101     else
 102       n = s->t;
 103     for (i = 0; i < n; i++) {
 104       if (s->v[i].y)
 105         mp_drop(s->v[i].y);
 106     }
 107     xfree(s->v);
 108   }
 109
 110   /* --- Other stuff --- */
 111
 112   if (s->p)
 113     mp_drop(s->p);
 114   if (s->s)
 115     mp_drop(s->s);
 116 }
 117
 118 /* --- @share_mkshares@ --- *
 119  *
 120  * Arguments:   @share *s@ = pointer to share context to fill in
 121  *              @grand *r@ = pointer to random number source
 122  *
 123  * Returns:     ---
 124  *
 125  * Use:         Generates @c->n@ secret shares, such that any @c->t@ of them
 126  *              may be used to recover the secret.
 127  *
 128  *              The context structure is expected to be mostly filled in.  In
 129  *              particular, @t@, @n@ and @s@ must be initialized.  If @p@ is
 130  *              zero, a prime number of appropriate size is generated
 131  *              automatically.  If @v@ is zero, a vector of appropriate size
 132  *              is allocated.  You should use the macro @SHARE_INIT@ or
 133  *              @share_create@ to construct sharing contexts.
 134  */
 135
 136 void share_mkshares(share *s, grand *r)
 137 {
 138   mp **v;
 139   unsigned i;
 140   mp u;
 141   mpw uw;
 142   mpbarrett mb;
 143
 144   /* --- If there's no prime, construct one --- */
 145
 146   if (!s->p) {
 147     pgen_filterctx pf;
 148     rabin pr;
 149     mp *p;
 150     unsigned bits = (mp_octets(s->s) + 1) * 8;
 151
 152     pf.step = 2;
 153     p = mprand(MP_NEW, bits, r, 1);
 154     s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
 155                 rabin_iters(bits), pgen_test, &pr);
 156   }
 157
 158   /* --- Construct the coefficients --- */
 159
 160   mpbarrett_create(&mb, s->p);
 161   v = xmalloc(s->t * sizeof(mp *));
 162   for (i = 0; i < s->t - 1; i++)
 163     v[i] = mprand_range(MP_NEW, s->p, r, 0);
 164   v[s->t - 1] = s->s;
 165
 166   /* --- Construct the shares --- */
 167
 168   if (!s->v)
 169     s->v = xmalloc(s->n * sizeof(share_pt));
 170
 171   mp_build(&u, &uw, &uw + 1);
 172   for (uw = 1; uw <= s->n; uw++) {
 173     mp *m = MP_ZERO;
 174     unsigned j;
 175
 176     /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 177
 178     for (j = 0; j < s->t; j++) {
 179       m = mp_mul(m, m, &u);
 180       m = mpbarrett_reduce(&mb, m, m);
 181       m = mp_add(m, m, v[j]);
 182       if (MP_CMP(m, >=, s->p))
 183         m = mp_sub(m, m, s->p);
 184     }
 185
 186     /* --- Reduce the final result --- */
 187
 188     s->v[uw - 1].x = uw - 1;
 189     s->v[uw - 1].y = m;
 190   }
 191   mpbarrett_destroy(&mb);
 192
 193   /* --- Dispose of various bits of old rubbish --- */
 194
 195   for (i = 0; i < s->t - 1; i++)
 196     mp_drop(v[i]);
 197   xfree(v);
 198 }
 199
 200 /* --- @share_add@ --- *
 201  *
 202  * Arguments:   @share *s@ = pointer to sharing context
 203  *              @unsigned x@ = which share number this is
 204  *              @mp *y@ = the share value
 205  *
 206  * Returns:     Number of shares required before recovery may be performed.
 207  *
 208  * Use:         Adds a share to the context.  The context must have been
 209  *              initialized with the correct prime @p@ and threshold @t@.
 210  */
 211
 212 unsigned share_add(share *s, unsigned x, mp *y)
 213 {
 214   /* --- If no vector has been allocated, create one --- */
 215
 216   if (!s->v) {
 217     s->v = xmalloc(s->t * sizeof(share_pt));
 218     s->i = 0;
 219   }
 220
 221   assert(((void)"Share context is full", s->i < s->t));
 222
 223   /* --- Store the share in the vector --- */
 224
 225   s->v[s->i].x = x;
 226   s->v[s->i].y = mp_copy(y);
 227   s->i++;
 228
 229   /* --- Done --- */
 230
 231   return (s->t - s->i);
 232 }
 233
 234 /* --- @share_combine@ --- *
 235  *
 236  * Arguments:   @share *s@ = pointer to share context
 237  *
 238  * Returns:     The secret, as a multiprecision integer.
 239  *
 240  * Use:         Reconstructs a secret, given enough shares.
 241  */
 242
 243 mp *share_combine(share *s)
 244 {
 245   mp *a = MP_ZERO;
 246   mpbarrett mb;
 247   unsigned i, j;
 248   mp ii, jj;
 249   mpw iiw, jjw;
 250   mp *m = MP_NEW;
 251
 252   /* --- Sanity checking --- */
 253
 254   assert(((void)"Not enough shares yet", s->i == s->t));
 255
 256   /* --- Initialization --- */
 257
 258   mpbarrett_create(&mb, s->p);
 259   mp_build(&ii, &iiw, &iiw + 1);
 260   mp_build(&jj, &jjw, &jjw + 1);
 261
 262   /* --- Grind through the shares --- */
 263
 264   for (i = 0; i < s->t; i++) {
 265     mp *c = MP_ONE;
 266
 267     iiw = s->v[i].x + 1;
 268     for (j = 0; j < s->t; j++) {
 269       if (i == j)
 270         continue;
 271       jjw = s->v[j].x + 1;
 272       if (s->v[j].x >= s->v[i].x)
 273         m = mp_sub(m, &jj, &ii);
 274       else {
 275         m = mp_sub(m, &ii, &jj);
 276         m = mp_sub(m, s->p, m);
 277       }
 278       mp_gcd(0, 0, &m, s->p, m);
 279       c = mp_mul(c, c, &jj);
 280       c = mpbarrett_reduce(&mb, c, c);
 281       c = mp_mul(c, c, m);
 282       c = mpbarrett_reduce(&mb, c, c);
 283     }
 284     c = mp_mul(c, c, s->v[i].y);
 285     c = mpbarrett_reduce(&mb, c, c);
 286     a = mp_add(a, a, c);
 287     mp_drop(c);
 288   }
 289
 290   a = mpbarrett_reduce(&mb, a, a);
 291   s->s = mp_copy(a);
 292   if (m)
 293     mp_drop(m);
 294   mpbarrett_destroy(&mb);
 295   return (a);
 296 }
 297
 298 /*----- Test rig ----------------------------------------------------------*/
 299
 300 #ifdef TEST_RIG
 301
 302 #include "fibrand.h"
 303
 304 static int verify(grand *r)
 305 {
 306   unsigned n = r->ops->range(r, 16) + 8;
 307   unsigned t = r->ops->range(r, n - 1) + 1;
 308   unsigned len = r->ops->range(r, 160);
 309
 310   share_pt *v = xmalloc(t * sizeof(share_pt));
 311   unsigned *p = xmalloc(n * sizeof(unsigned));
 312   mp *sec = mprand(MP_NEW, len, r, 0);
 313   share s;
 314   mp *pp;
 315   mp *ss;
 316   unsigned i;
 317
 318   int ok = 1;
 319
 320   for (i = 0; i < n; i++)
 321     p[i] = i;
 322   for (i = 0; i < t; i++) {
 323     unsigned long j = r->ops->range(r, n - i);
 324     unsigned x = p[i];
 325     p[i] = p[i + j];
 326     p[i + j] = x;
 327   }
 328
 329   share_create(&s, t, n);
 330   s.s = mp_copy(sec);
 331   share_mkshares(&s, r);
 332   for (i = 0; i < t; i++) {
 333     v[i].x = s.v[p[i]].x;
 334     v[i].y = mp_copy(s.v[p[i]].y);
 335   }
 336   pp = mp_copy(s.p);
 337   share_destroy(&s);
 338
 339   assert(mparena_count(MPARENA_GLOBAL) == t + 2);
 340
 341   share_create(&s, t, n);
 342   s.p = pp;
 343   for (i = 0; i < t; i++) {
 344     share_add(&s, v[i].x, v[i].y);
 345   }
 346   ss = share_combine(&s);
 347   share_destroy(&s);
 348
 349   if (MP_CMP(sec, !=, ss)) {
 350     ok = 0;
 351     fprintf(stderr, "\nbad recombination of shares\n");
 352   };
 353
 354   mp_drop(sec);
 355   mp_drop(ss);
 356
 357   for (i = 0; i < t; i++)
 358     mp_drop(v[i].y);
 359
 360   xfree(v);
 361   xfree(p);
 362
 363   assert(mparena_count(MPARENA_GLOBAL) == 0);
 364   return (ok);
 365 }
 366
 367 int main(void)
 368 {
 369   grand *r = fibrand_create(0);
 370   unsigned i;
 371   int ok = 1;
 372
 373   fputs("share: ", stdout);
 374   for (i = 0; i < 40; i++) {
 375     if (!verify(r))
 376       ok = 0;
 377     fputc('.', stdout);
 378     fflush(stdout);
 379   }
 380
 381   if (ok)
 382     fputs(" ok\n", stdout);
 383   else
 384     fputs(" failed\n", stdout);
 385   return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 386 }
 387
 388 #endif
 389
 390 /*----- That's all, folks -------------------------------------------------*/