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

   1 /* -*-c-*-
   2  *
   3  * $Id: share.c,v 1.1 2000/06/17 12:09:38 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.1  2000/06/17 12:09:38  mdw
  34  * Shamir's secret sharing system.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43
  44 #include "grand.h"
  45 #include "mp.h"
  46 #include "mpint.h"
  47 #include "mpmont.h"
  48 #include "mprand.h"
  49 #include "pgen.h"
  50 #include "rabin.h"
  51 #include "share.h"
  52
  53 /*----- Main code ---------------------------------------------------------*/
  54
  55 /* --- @share_create@ --- *
  56  *
  57  * Arguments:   @share *s@ = pointer to share context to initialize
  58  *              @unsigned t, n@ = threshold parameters for the system
  59  *
  60  * Returns:     ---
  61  *
  62  * Use:         Initializes a sharing context.
  63  */
  64
  65 void share_create(share *s, unsigned t, unsigned n)
  66 {
  67   s->t = t;
  68   s->n = n;
  69   s->i = 0;
  70   s->s = 0;
  71   s->p = 0;
  72   s->v = 0;
  73 }
  74
  75 /* --- @share_destroy@ --- *
  76  *
  77  * Arguments:   @share *s@ = pointer to share context to destroy
  78  *
  79  * Returns:     ---
  80  *
  81  * Use:         Disposes of a sharing context.  All memory is freed, all
  82  *              integers are dropped.
  83  */
  84
  85 void share_destroy(share *s)
  86 {
  87   unsigned n;
  88   unsigned i;
  89
  90   /* --- Dispose of the share vector --- */
  91
  92   if (s->v) {
  93     if (s->i)
  94       n = s->i;
  95     else if (s->n)
  96       n = s->n;
  97     else
  98       n = s->t;
  99     for (i = 0; i < n; i++) {
 100       if (s->v[i].y)
 101         mp_drop(s->v[i].y);
 102     }
 103     xfree(s->v);
 104   }
 105
 106   /* --- Other stuff --- */
 107
 108   if (s->p)
 109     mp_drop(s->p);
 110   if (s->s)
 111     mp_drop(s->s);
 112 }
 113
 114 /* --- @share_mkshares@ --- *
 115  *
 116  * Arguments:   @share *s@ = pointer to share context to fill in
 117  *              @grand *r@ = pointer to random number source
 118  *
 119  * Returns:     ---
 120  *
 121  * Use:         Generates @c->n@ secret shares, such that any @c->t@ of them
 122  *              may be used to recover the secret.
 123  *
 124  *              The context structure is expected to be mostly filled in.  In
 125  *              particular, @t@, @n@ and @s@ must be initialized.  If @p@ is
 126  *              zero, a prime number of appropriate size is generated
 127  *              automatically.  If @v@ is zero, a vector of appropriate size
 128  *              is allocated.  You should use the macro @SHARE_INIT@ or
 129  *              @share_create@ to construct sharing contexts.
 130  */
 131
 132 void share_mkshares(share *s, grand *r)
 133 {
 134   mp **v;
 135   unsigned i;
 136   mp *u;
 137   mpmont mm;
 138
 139   /* --- If there's no prime, construct one --- */
 140
 141   if (!s->p) {
 142     pgen_filterctx pf;
 143     rabin pr;
 144     mp *p;
 145     unsigned bits = (mp_octets(s->s) + 1) * 8;
 146
 147     pf.step = 2;
 148     p = mprand(MP_NEW, bits, r, 1);
 149     s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
 150                 rabin_iters(bits), pgen_test, &pr);
 151   }
 152
 153   /* --- Construct the coefficients --- */
 154
 155   mpmont_create(&mm, s->p);
 156   v = xmalloc(s->t * sizeof(mp *));
 157   for (i = 0; i < s->t - 1; i++)
 158     v[i] = mprand_range(MP_NEW, s->p, r, 0);
 159   v[s->t - 1] = mpmont_mul(&mm, MP_NEW, s->s, mm.r2);
 160
 161   /* --- Construct the shares --- */
 162
 163   if (!s->v)
 164     s->v = xmalloc(s->n * sizeof(share_pt));
 165
 166   u = mp_copy(mm.r);
 167   for (i = 0; i < s->n; i++) {
 168     mp *m = MP_ZERO;
 169     unsigned j;
 170
 171     /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 172
 173     for (j = 0; j < s->t; j++) {
 174       m = mpmont_mul(&mm, m, m, u);
 175       m = mp_add(m, m, v[j]);
 176       if (MP_CMP(m, >=, s->p))
 177         m = mp_sub(m, m, s->p);
 178     }
 179
 180     /* --- Reduce the final result --- */
 181
 182     s->v[i].x = i;
 183     s->v[i].y = mpmont_reduce(&mm, m, m);
 184
 185     /* --- Compute the next point in Montgomery space --- */
 186
 187     u = mp_add(u, u, mm.r);
 188     if (MP_CMP(u, >=, s->p))
 189       u = mp_sub(u, u, s->p);
 190   }
 191   mpmont_destroy(&mm);
 192
 193   /* --- Dispose of various bits of old rubbish --- */
 194
 195   for (i = 0; i < s->t; i++)
 196     mp_drop(v[i]);
 197   mp_drop(u);
 198   xfree(v);
 199 }
 200
 201 /* --- @share_add@ --- *
 202  *
 203  * Arguments:   @share *s@ = pointer to sharing context
 204  *              @unsigned x@ = which share number this is
 205  *              @mp *y@ = the share value
 206  *
 207  * Returns:     Number of shares required before recovery may be performed.
 208  *
 209  * Use:         Adds a share to the context.  The context must have been
 210  *              initialized with the correct prime @p@ and threshold @t@.
 211  */
 212
 213 unsigned share_add(share *s, unsigned x, mp *y)
 214 {
 215   /* --- If no vector has been allocated, create one --- */
 216
 217   if (!s->v) {
 218     s->v = xmalloc(s->t * sizeof(share_pt));
 219     s->i = 0;
 220   }
 221
 222   assert(((void)"Share context is full", s->i < s->t));
 223
 224   /* --- Store the share in the vector --- */
 225
 226   s->v[s->i].x = x;
 227   s->v[s->i].y = mp_copy(y);
 228   s->i++;
 229
 230   /* --- Done --- */
 231
 232   return (s->t - s->i);
 233 }
 234
 235 /* --- @share_combine@ --- *
 236  *
 237  * Arguments:   @share *s@ = pointer to share context
 238  *
 239  * Returns:     The secret, as a multiprecision integer.
 240  *
 241  * Use:         Reconstructs a secret, given enough shares.
 242  */
 243
 244 mp *share_combine(share *s)
 245 {
 246   mp *a = MP_ZERO;
 247   mpmont mm;
 248   unsigned i, j;
 249   mp *ii = MP_NEW, *jj = MP_NEW;
 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   mpmont_create(&mm, s->p);
 259
 260   /* --- Grind through the shares --- */
 261
 262   for (i = 0; i < s->t; i++) {
 263     mp *c = mp_copy(mm.r);
 264
 265     ii = mp_fromuint(ii, s->v[i].x + 1);
 266     for (j = 0; j < s->t; j++) {
 267       if (i == j)
 268         continue;
 269       jj = mp_fromuint(jj, s->v[j].x + 1);
 270       if (s->v[j].x >= s->v[i].x)
 271         m = mp_sub(m, jj, ii);
 272       else {
 273         m = mp_sub(m, ii, jj);
 274         m = mp_sub(m, s->p, m);
 275       }
 276       jj = mpmont_mul(&mm, jj, jj, mm.r2);
 277       mp_gcd(0, 0, &m, s->p, m);
 278       m = mpmont_mul(&mm, m, m, mm.r2);
 279       m = mpmont_mul(&mm, m, m, jj);
 280       c = mpmont_mul(&mm, c, c, m);
 281     }
 282     m = mpmont_mul(&mm, m, s->v[i].y, mm.r2);
 283     c = mpmont_mul(&mm, c, c, m);
 284     a = mp_add(a, a, c);
 285     mp_drop(c);
 286   }
 287
 288   a = mpmont_reduce(&mm, a, a);
 289   s->s = mp_copy(a);
 290   mp_drop(ii);
 291   if (jj)
 292     mp_drop(jj);
 293   mp_drop(m);
 294   mpmont_destroy(&mm);
 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 -------------------------------------------------*/