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

   1 /* -*-c-*-
   2  *
   3  * $Id$
   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_addedp@ --- *
 176  *
 177  * Arguments:   @share *s@ = pointer to sharing context
 178  *              @unsigned x@ = which share number to check
 179  *
 180  * Returns:     Nonzero if share @x@ has been added already, zero if it
 181  *              hasn't.
 182  */
 183
 184 int share_addedp(share *s, unsigned x)
 185 {
 186   unsigned i;
 187
 188   for (i = 0; i < s->i; i++) {
 189     if (s->v[i].x == x + 1)
 190       return (1);
 191   }
 192   return (0);
 193 }
 194
 195 /* --- @share_add@ --- *
 196  *
 197  * Arguments:   @share *s@ = pointer to sharing context
 198  *              @unsigned x@ = which share number this is
 199  *              @mp *y@ = the share value
 200  *
 201  * Returns:     Number of shares required before recovery may be performed.
 202  *
 203  * Use:         Adds a share to the context.  The context must have been
 204  *              initialized with the correct prime @p@ and threshold @t@.
 205  */
 206
 207 unsigned share_add(share *s, unsigned x, mp *y)
 208 {
 209   assert(((void)"Share context is full", s->i < s->t));
 210   assert(((void)"Share already present", !share_addedp(s, x)));
 211
 212   /* --- If no vector has been allocated, create one --- */
 213
 214   if (!s->v) {
 215     unsigned i;
 216     s->v = xmalloc(s->t * sizeof(share_pt));
 217     s->i = 0;
 218     for (i = 0; i < s->t; i++)
 219       s->v[i].y = 0;
 220   }
 221
 222   /* --- Store the share in the vector --- */
 223
 224   s->v[s->i].x = x + 1;
 225   s->v[s->i].y = mp_copy(y);
 226   s->i++;
 227
 228   /* --- Done --- */
 229
 230   return (s->t - s->i);
 231 }
 232
 233 /* --- @share_combine@ --- *
 234  *
 235  * Arguments:   @share *s@ = pointer to share context
 236  *
 237  * Returns:     The secret, as a multiprecision integer.
 238  *
 239  * Use:         Reconstructs a secret, given enough shares.
 240  */
 241
 242 mp *share_combine(share *s)
 243 {
 244   mp *a = MP_ZERO;
 245   mpbarrett mb;
 246   unsigned i, j;
 247   mp ii, jj;
 248   mpw iiw, jjw;
 249   mp *m = MP_NEW;
 250
 251   /* --- Sanity checking --- */
 252
 253   assert(((void)"Not enough shares yet", s->i == s->t));
 254
 255   /* --- Initialization --- */
 256
 257   mpbarrett_create(&mb, s->p);
 258   mp_build(&ii, &iiw, &iiw + 1);
 259   mp_build(&jj, &jjw, &jjw + 1);
 260
 261   /* --- Grind through the shares --- */
 262
 263   for (i = 0; i < s->t; i++) {
 264     mp *c = MP_ONE;
 265
 266     iiw = s->v[i].x;
 267     for (j = 0; j < s->t; j++) {
 268       if (i == j)
 269         continue;
 270       jjw = s->v[j].x;
 271       if (s->v[j].x >= s->v[i].x)
 272         m = mp_sub(m, &jj, &ii);
 273       else {
 274         m = mp_sub(m, &ii, &jj);
 275         m = mp_sub(m, s->p, m);
 276       }
 277       m = mp_modinv(m, m, s->p);
 278       c = mp_mul(c, c, &jj);
 279       c = mpbarrett_reduce(&mb, c, c);
 280       c = mp_mul(c, c, m);
 281       c = mpbarrett_reduce(&mb, c, c);
 282     }
 283     c = mp_mul(c, c, s->v[i].y);
 284     c = mpbarrett_reduce(&mb, c, c);
 285     a = mp_add(a, a, c);
 286     mp_drop(c);
 287   }
 288
 289   a = mpbarrett_reduce(&mb, a, a);
 290   mp_drop(m);
 291   mpbarrett_destroy(&mb);
 292   return (a);
 293 }
 294
 295 /*----- Test rig ----------------------------------------------------------*/
 296
 297 #ifdef TEST_RIG
 298
 299 #include "fibrand.h"
 300
 301 static int verify(grand *r)
 302 {
 303   unsigned n = r->ops->range(r, 16) + 8;
 304   unsigned t = r->ops->range(r, n - 1) + 1;
 305   unsigned len = r->ops->range(r, 160);
 306
 307   mp **v = xmalloc(t * sizeof(mp *));
 308   unsigned *p = xmalloc(n * sizeof(unsigned));
 309   mp *sec = mprand(MP_NEW, len, r, 0);
 310   share s;
 311   mp *pp;
 312   mp *ss;
 313   unsigned i;
 314
 315   int ok = 1;
 316
 317   for (i = 0; i < n; i++)
 318     p[i] = i;
 319   for (i = 0; i < t; i++) {
 320     unsigned long j = r->ops->range(r, n - i);
 321     unsigned x = p[i];
 322     p[i] = p[i + j];
 323     p[i + j] = x;
 324   }
 325
 326   share_create(&s, t);
 327   share_mkshares(&s, r, sec);
 328   for (i = 0; i < t; i++)
 329     v[i] = share_get(&s, MP_NEW, p[i]);
 330   pp = mp_copy(s.p);
 331   share_destroy(&s);
 332   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2);
 333
 334   share_create(&s, t);
 335   s.p = pp;
 336   for (i = 0; i < t; i++)
 337     share_add(&s, p[i], v[i]);
 338   ss = share_combine(&s);
 339   share_destroy(&s);
 340
 341   if (!MP_EQ(sec, ss)) {
 342     ok = 0;
 343     fprintf(stderr, "\nbad recombination of shares\n");
 344   };
 345
 346   mp_drop(sec);
 347   mp_drop(ss);
 348
 349   for (i = 0; i < t; i++)
 350     mp_drop(v[i]);
 351
 352   xfree(v);
 353   xfree(p);
 354
 355   assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0);
 356   return (ok);
 357 }
 358
 359 int main(void)
 360 {
 361   grand *r = fibrand_create(0);
 362   unsigned i;
 363   int ok = 1;
 364
 365   fputs("share: ", stdout);
 366   for (i = 0; i < 40; i++) {
 367     if (!verify(r))
 368       ok = 0;
 369     fputc('.', stdout);
 370     fflush(stdout);
 371   }
 372
 373   if (ok)
 374     fputs(" ok\n", stdout);
 375   else
 376     fputs(" failed\n", stdout);
 377   return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 378 }
 379
 380 #endif
 381
 382 /*----- That's all, folks -------------------------------------------------*/