chiark - git - mdw - catacomb/blob - share.c

   1 /* -*-c-*-
   2  *
   3  * $Id: share.c,v 1.3 2000/06/24 18:29:05 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.3  2000/06/24 18:29:05  mdw
  34  * Interface change: allow shares to be extracted from a context on demand,
  35  * rather than building them all up-front.
  36  *
  37  * Revision 1.2  2000/06/18 23:05:19  mdw
  38  * Minor performance tweak: use Barrett reduction rather than Montgomery.
  39  * Fast secret sharing isn't done here, though: see `gfshare' instead.
  40  *
  41  * Revision 1.1  2000/06/17 12:09:38  mdw
  42  * Shamir's secret sharing system.
  43  *
  44  */
  45
  46 /*----- Header files ------------------------------------------------------*/
  47
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50 #include <string.h>
  51
  52 #include "grand.h"
  53 #include "mp.h"
  54 #include "mpint.h"
  55 #include "mpbarrett.h"
  56 #include "mprand.h"
  57 #include "pgen.h"
  58 #include "rabin.h"
  59 #include "share.h"
  60
  61 /*----- Main code ---------------------------------------------------------*/
  62
  63 /* --- @share_create@ --- *
  64  *
  65  * Arguments:   @share *s@ = pointer to share context to initialize
  66  *              @unsigned t@ = threshold for the system
  67  *
  68  * Returns:     ---
  69  *
  70  * Use:         Initializes a sharing context.
  71  */
  72
  73 void share_create(share *s, unsigned t)
  74 {
  75   s->t = t;
  76   s->i = 0;
  77   s->s = 0;
  78   s->p = 0;
  79   s->v = 0;
  80 }
  81
  82 /* --- @share_destroy@ --- *
  83  *
  84  * Arguments:   @share *s@ = pointer to share context to destroy
  85  *
  86  * Returns:     ---
  87  *
  88  * Use:         Disposes of a sharing context.  All memory is freed, all
  89  *              integers are dropped.
  90  */
  91
  92 void share_destroy(share *s)
  93 {
  94   unsigned i;
  95
  96   /* --- Dispose of the share vector --- */
  97
  98   if (s->v) {
  99     for (i = 0; i < s->t; 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:         Initializes a sharing context to be able to create shares.
 122  *              The context structure is expected to be mostly filled in.  In
 123  *              particular, @t@ and @s@ must be initialized.  If @p@ is zero,
 124  *              a prime number of appropriate size is generated
 125  *              automatically.  If @v@ is zero, a vector of appropriate size
 126  *              is allocated.  You should use the macro @SHARE_INIT@ or
 127  *              @share_create@ to construct sharing contexts.
 128  */
 129
 130 void share_mkshares(share *s, grand *r)
 131 {
 132   unsigned i;
 133
 134   /* --- If there's no prime, construct one --- */
 135
 136   if (!s->p) {
 137     pgen_filterctx pf;
 138     rabin pr;
 139     mp *p;
 140     unsigned bits = (mp_octets(s->s) + 1) * 8;
 141
 142     pf.step = 2;
 143     p = mprand(MP_NEW, bits, r, 1);
 144     s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
 145                 rabin_iters(bits), pgen_test, &pr);
 146   }
 147
 148   /* --- Construct the polynomial --- */
 149
 150   if (!s->v)
 151     s->v = xmalloc(s->t * sizeof(share_pt));
 152   for (i = 0; i < s->t - 1; i++)
 153     s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0);
 154   s->v[s->t - 1].y = mp_copy(s->s);
 155 }
 156
 157 /* --- @share_get@ --- *
 158  *
 159  * Arguments:   @share *s@ = pointer to share conext
 160  *              @mp *d@ = destination for the share
 161  *              @unsigned x@ = share index to fetch
 162  *
 163  * Returns:     The share, as requested.
 164  *
 165  * Use:         Extracts a share from the system.  You may extract @MPW_MAX@
 166  *              shares, or @s->p@ shares from the system, whichever is
 167  *              smaller.  Shares are indexed from 0.
 168  */
 169
 170 mp *share_get(share *s, mp *d, unsigned x)
 171 {
 172   mpbarrett mb;
 173   mpw uw = x + 1;
 174   mp u;
 175   unsigned i;
 176
 177   /* --- Various bits of initialization --- */
 178
 179   mp_build(&u, &uw, &uw + 1);
 180   if (d)
 181     mp_drop(d);
 182
 183   /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 184
 185   d = MP_ZERO;
 186   mpbarrett_create(&mb, s->p);
 187   for (i = 0; i < s->t; i++) {
 188     d = mp_mul(d, d, &u);
 189     d = mp_add(d, d, s->v[i].y);
 190     d = mpbarrett_reduce(&mb, d, d);
 191   }
 192   mpbarrett_destroy(&mb);
 193
 194   return (d);
 195 }
 196
 197 /* --- @share_add@ --- *
 198  *
 199  * Arguments:   @share *s@ = pointer to sharing context
 200  *              @unsigned x@ = which share number this is
 201  *              @mp *y@ = the share value
 202  *
 203  * Returns:     Number of shares required before recovery may be performed.
 204  *
 205  * Use:         Adds a share to the context.  The context must have been
 206  *              initialized with the correct prime @p@ and threshold @t@.
 207  */
 208
 209 unsigned share_add(share *s, unsigned x, mp *y)
 210 {
 211   /* --- If no vector has been allocated, create one --- */
 212
 213   if (!s->v) {
 214     unsigned i;
 215     s->v = xmalloc(s->t * sizeof(share_pt));
 216     s->i = 0;
 217     for (i = 0; i < s->t; i++)
 218       s->v[i].y = 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 + 1;
 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;
 268     for (j = 0; j < s->t; j++) {
 269       if (i == j)
 270         continue;
 271       jjw = s->v[j].x;
 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   mp **v = xmalloc(t * sizeof(mp *));
 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);
 330   s.s = mp_copy(sec);
 331   share_mkshares(&s, r);
 332   for (i = 0; i < t; i++)
 333     v[i] = share_get(&s, MP_NEW, p[i]);
 334   pp = mp_copy(s.p);
 335   share_destroy(&s);
 336   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2);
 337
 338   share_create(&s, t);
 339   s.p = pp;
 340   for (i = 0; i < t; i++)
 341     share_add(&s, p[i], v[i]);
 342   ss = share_combine(&s);
 343   share_destroy(&s);
 344
 345   if (MP_CMP(sec, !=, ss)) {
 346     ok = 0;
 347     fprintf(stderr, "\nbad recombination of shares\n");
 348   };
 349
 350   mp_drop(sec);
 351   mp_drop(ss);
 352
 353   for (i = 0; i < t; i++)
 354     mp_drop(v[i]);
 355
 356   xfree(v);
 357   xfree(p);
 358
 359   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0);
 360   return (ok);
 361 }
 362
 363 int main(void)
 364 {
 365   grand *r = fibrand_create(0);
 366   unsigned i;
 367   int ok = 1;
 368
 369   fputs("share: ", stdout);
 370   for (i = 0; i < 40; i++) {
 371     if (!verify(r))
 372       ok = 0;
 373     fputc('.', stdout);
 374     fflush(stdout);
 375   }
 376
 377   if (ok)
 378     fputs(" ok\n", stdout);
 379   else
 380     fputs(" failed\n", stdout);
 381   return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 382 }
 383
 384 #endif
 385
 386 /*----- That's all, folks -------------------------------------------------*/