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

   1 /* -*-c-*-
   2  *
   3  * $Id: gfshare.c,v 1.1 2000/06/17 10:56:30 mdw Exp $
   4  *
   5  * Secret sharing over %$gf(2^8)$%
   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: gfshare.c,v $
  33  * Revision 1.1  2000/06/17 10:56:30  mdw
  34  * Fast but nonstandard secret sharing system.
  35  *
  36  */
  37
  38 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <assert.h>
  41 #include <stdarg.h>
  42 #include <stdio.h>
  43
  44 #include <mLib/alloc.h>
  45 #include <mLib/bits.h>
  46
  47 #include "arena.h"
  48 #include "gfshare.h"
  49 #include "gfshare-tab.h"
  50 #include "grand.h"
  51
  52 /*----- Static variables --------------------------------------------------*/
  53
  54 static octet gflog[] = GFSHARE_LOG, gfexp[] = GFSHARE_EXP;
  55
  56 /*----- Main code ---------------------------------------------------------*/
  57
  58 /* --- @gfshare_create@ --- *
  59  *
  60  * Arguments:   @gfshare *s@ = pointer to share context to initialize
  61  *              @unsigned t, n@ = threshold parameters for the system
  62  *              @size_t sz@ = size of the secret
  63  *
  64  * Returns:     ---
  65  *
  66  * Use:         Initializes a sharing context.
  67  */
  68
  69 void gfshare_create(gfshare *s, unsigned t, unsigned n, size_t sz)
  70 {
  71   s->t = t;
  72   s->n = n;
  73   s->i = 0;
  74   s->sz = sz;
  75   s->s = 0;
  76   s->v = 0;
  77 }
  78
  79 /* --- @gfshare_destroy@ --- *
  80  *
  81  * Arguments:   @gfshare *s@ = pointer to share context to destroy
  82  *
  83  * Returns:     ---
  84  *
  85  * Use:         Disposes of a sharing context.  The allocations for the
  86  *              individual shares and the vector @v@ are freed; the secret is
  87  *              left alone.
  88  */
  89
  90 void gfshare_destroy(gfshare *s)
  91 {
  92   unsigned n;
  93   unsigned i;
  94
  95   /* --- Dispose of the share vector --- */
  96
  97   if (s->v) {
  98     if (s->i)
  99       n = s->i;
 100     else if (s->n)
 101       n = s->n;
 102     else
 103       n = s->t;
 104     for (i = 0; i < n; i++) {
 105       if (s->v[i].y)
 106         XS_FREE(s->v[i].y);
 107     }
 108     xfree(s->v);
 109   }
 110 }
 111
 112 /* --- @gfshare_mkshares@ --- *
 113  *
 114  * Arguments:   @gfshare *s@ = pointer to share context to fill in
 115  *              @grand *r@ = pointer to random number source
 116  *
 117  * Returns:     ---
 118  *
 119  * Use:         Generates @c->n@ secret shares, such that any @c->t@ of them
 120  *              may be used to recover the secret.
 121  *
 122  *              The context structure is expected to be mostly filled in.  In
 123  *              particular, @t@, @n@, @ssz@ and @s@ must be initialized.  If
 124  *              @v@ is zero, a vector of appropriate size is allocated.  You
 125  *              should use the macro @GFSHARE_INIT@ or @gfshare_create@ to
 126  *              construct sharing contexts.
 127  */
 128
 129 void gfshare_mkshares(gfshare *s, grand *r)
 130 {
 131   octet *v;
 132   unsigned i;
 133
 134   /* --- Construct the coefficients --- */
 135
 136   v = XS_ALLOC(s->sz * s->t);
 137   r->ops->fill(r, v, s->sz * (s->t - 1));
 138   memcpy(v + s->sz * (s->t - 1), s->s, s->sz);
 139
 140
 141   /* --- Construct the shares --- */
 142
 143   if (!s->v)
 144     s->v = xmalloc(s->n * sizeof(gfshare_pt));
 145
 146   for (i = 0; i < s->n; i++) {
 147     unsigned j;
 148     const octet *p = v;
 149     unsigned ilog = gflog[i + 1];
 150
 151     /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 152
 153     s->v[i].y = XS_ALLOC(s->sz);
 154     memcpy(s->v[i].y, p, s->sz);
 155     p += s->sz;
 156     for (j = 1; j < s->t; j++) {
 157       octet *q = s->v[i].y;
 158       unsigned k;
 159       for (k = 0; k < s->sz; k++) {
 160         unsigned qq = *q;
 161         if (qq)
 162           qq = gfexp[ilog + gflog[qq]];
 163         *q++ = qq ^ *p++;
 164       }
 165     }
 166     s->v[i].x = i;
 167   }
 168
 169   /* --- Dispose of various bits of old rubbish --- */
 170
 171   XS_FREE(v);
 172 }
 173
 174 /* --- @gfshare_add@ --- *
 175  *
 176  * Arguments:   @gfshare *s@ = pointer to sharing context
 177  *              @unsigned x@ = which share number this is
 178  *              @const octet *y@ = the share value
 179  *
 180  * Returns:     Number of shares required before recovery may be performed.
 181  *
 182  * Use:         Adds a share to the context.  The context must have been
 183  *              initialized with the correct threshold @t@.
 184  */
 185
 186 unsigned gfshare_add(gfshare *s, unsigned x, const octet *y)
 187 {
 188   /* --- If no vector has been allocated, create one --- */
 189
 190   if (!s->v) {
 191     s->v = xmalloc(s->t * sizeof(gfshare_pt));
 192     s->i = 0;
 193   }
 194
 195   assert(((void)"Share context is full", s->i < s->t));
 196
 197   /* --- Store the share in the vector --- */
 198
 199   s->v[s->i].x = x;
 200   s->v[s->i].y = XS_ALLOC(s->sz);
 201   memcpy(s->v[s->i].y, y, s->sz);
 202   s->i++;
 203
 204   /* --- Done --- */
 205
 206   return (s->t - s->i);
 207 }
 208
 209 /* --- @gfshare_combine@ --- *
 210  *
 211  * Arguments:   @gfshare *s@ = pointer to share context
 212  *              @octet *buf@ = pointer to output buffer for the secret
 213  *
 214  * Returns:     ---
 215  *
 216  * Use:         Reconstructs a secret, given enough shares.
 217  */
 218
 219 void gfshare_combine(gfshare *s, octet *buf)
 220 {
 221   unsigned i, j;
 222   octet *v;
 223
 224   /* --- Sanity checking --- */
 225
 226   assert(((void)"Not enough shares yet", s->i == s->t));
 227
 228   /* --- Precomputation of coefficients --- */
 229
 230   v = XS_ALLOC(s->t);
 231
 232   for (i = 0; i < s->t; i++) {
 233     unsigned c = 0, ci = 0;
 234     for (j = 0; j < s->t; j++) {
 235       if (i == j)
 236         continue;
 237       c += gflog[s->v[j].x + 1];
 238       if (c >= 0xff)
 239         c -= 0xff;
 240       ci += gflog[(s->v[i].x + 1) ^ (s->v[j].x + 1)];
 241       if (ci >= 0xff)
 242         ci -= 0xff;
 243     }
 244     if (ci > c)
 245       c += 0xff;
 246     c -= ci;
 247     v[i] = c;
 248   }
 249
 250   /* --- Grind through the shares --- */
 251
 252   for (i = 0; i < s->sz; i++) {
 253     unsigned x = 0;
 254     for (j = 0; j < s->t; j++) {
 255       if (s->v[j].y[i])
 256         x ^= gfexp[v[j] + gflog[s->v[j].y[i]]];
 257     }
 258     buf[i] = x;
 259   }
 260
 261   XS_FREE(v);
 262 }
 263
 264 /*----- Test rig ----------------------------------------------------------*/
 265
 266 #ifdef TEST_RIG
 267
 268 #include "fibrand.h"
 269
 270 static int verify(grand *r)
 271 {
 272   unsigned n = r->ops->range(r, 16) + 8;
 273   unsigned t = r->ops->range(r, n - 1) + 1;
 274   unsigned len = r->ops->range(r, 32) + 1;
 275
 276   gfshare_pt *v = xmalloc(t * sizeof(gfshare_pt));
 277   unsigned *p = xmalloc(n * sizeof(unsigned));
 278   octet *sec = xmalloc(len), *sbuf = xmalloc(len);
 279   gfshare s;
 280   unsigned i;
 281
 282   int ok = 1;
 283
 284   for (i = 0; i < n; i++)
 285     p[i] = i;
 286   for (i = 0; i < t; i++) {
 287     unsigned long j = r->ops->range(r, n - i);
 288     unsigned x = p[i];
 289     p[i] = p[i + j];
 290     p[i + j] = x;
 291   }
 292
 293   r->ops->fill(r, sec, len);
 294
 295   gfshare_create(&s, t, n, len);
 296   s.s = sec;
 297
 298   gfshare_mkshares(&s, r);
 299   for (i = 0; i < t; i++) {
 300     v[i].x = s.v[p[i]].x;
 301     v[i].y = xmalloc(len);
 302     memcpy(v[i].y, s.v[p[i]].y, len);
 303   }
 304   gfshare_destroy(&s);
 305
 306   gfshare_create(&s, t, n, len);
 307   for (i = 0; i < t; i++) {
 308     gfshare_add(&s, v[i].x, v[i].y);
 309   }
 310   gfshare_combine(&s, sbuf);
 311   gfshare_destroy(&s);
 312
 313   if (memcmp(sec, sbuf, len) != 0) {
 314     ok = 0;
 315     fprintf(stderr, "\nbad recombination of shares\n");
 316   };
 317
 318   xfree(sec);
 319   xfree(sbuf);
 320
 321   for (i = 0; i < t; i++)
 322     xfree(v[i].y);
 323   xfree(v);
 324   xfree(p);
 325
 326   return (ok);
 327 }
 328
 329 int main(void)
 330 {
 331   grand *r = fibrand_create(0);
 332   unsigned i;
 333   int ok = 1;
 334
 335   fputs("gfshare: ", stdout);
 336   for (i = 0; i < 40; i++) {
 337     if (!verify(r))
 338       ok = 0;
 339     fputc('.', stdout);
 340     fflush(stdout);
 341   }
 342
 343   if (ok)
 344     fputs(" ok\n", stdout);
 345   else
 346     fputs(" failed\n", stdout);
 347   return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 348 }
 349
 350 #endif
 351
 352 /*----- That's all, folks -------------------------------------------------*/