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

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