3 * Secret sharing over %$\gf{2^8}$%
5 * (c) 2000 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
35 #include <mLib/alloc.h>
36 #include <mLib/bits.h>
42 /*----- Static variables --------------------------------------------------*/
44 extern const octet gfshare_log[256], gfshare_exp[510];
46 /*----- Main code ---------------------------------------------------------*/
48 /* --- @gfshare_create@ --- *
50 * Arguments: @gfshare *s@ = pointer to share context to initialize
51 * @unsigned t@ = threshold for the system
52 * @size_t sz@ = size of the secret
56 * Use: Initializes a sharing context.
59 void gfshare_create(gfshare *s, unsigned t, size_t sz)
67 /* --- @gfshare_destroy@ --- *
69 * Arguments: @gfshare *s@ = pointer to share context to destroy
73 * Use: Disposes of a sharing context. The allocations for the
74 * individual shares and the vector @v@ are freed; the secret is
78 void gfshare_destroy(gfshare *s)
84 /* --- @gfshare_mkshares@ --- *
86 * Arguments: @gfshare *s@ = pointer to share context to fill in
87 * @grand *r@ = pointer to random number source
88 * @const void *buf@ = pointer to the secret to share
92 * Use: Initializes a sharing context to be able to create shares.
93 * The context structure is expected to be mostly filled in. In
94 * particular, @t@ must be initialized. If @v@ is zero, a
95 * vector of appropriate size is allocated. You should use the
96 * macro @GFSHARE_INIT@ or @gfshare_create@ to construct sharing
100 void gfshare_mkshares(gfshare *s, grand *r, const void *buf)
102 s->v = XS_ALLOC(s->sz * s->t);
103 r->ops->fill(r, s->v, s->sz * (s->t - 1));
104 memcpy(s->v + s->sz * (s->t - 1), buf, s->sz);
107 /* --- @gfshare_get@ --- *
109 * Arguments: @gfshare *s@ = pointer to share conext
110 * @unsigned x@ = share index to fetch
111 * @void *buf@ = pointer to output buffer
115 * Use: Extracts a share from the system. You may extract up to 255
116 * shares from the system. Shares are indexed from 0.
119 void gfshare_get(gfshare *s, unsigned x, void *buf)
122 const octet *p = s->v;
123 unsigned ilog = gfshare_log[x + 1];
125 /* --- Evaluate the polynomial at %$x = i + 1$% --- */
127 memcpy(buf, p, s->sz);
130 for (i = 1; i < s->t; i++) {
133 for (k = 0; k < s->sz; k++) {
136 qq = gfshare_exp[ilog + gfshare_log[qq]];
142 /* --- @gfshare_addedp@ --- *
144 * Arguments: @gfshare *s@ = pointer to sharing context
145 * @unsigned x@ = which share number to check
147 * Returns: Nonzero if share @x@ has been added already, zero if it
151 int gfshare_addedp(gfshare *s, unsigned x)
155 for (i = 0; i < s->i; i++) {
156 if (GFSHARE_INDEX(s, i) == x + 1)
162 /* --- @gfshare_add@ --- *
164 * Arguments: @gfshare *s@ = pointer to sharing context
165 * @unsigned x@ = which share number this is
166 * @const void *y@ = the share value
168 * Returns: Number of shares required before recovery may be performed.
170 * Use: Adds a share to the context. The context must have been
171 * initialized with the correct threshold @t@.
174 unsigned gfshare_add(gfshare *s, unsigned x, const void *y)
178 assert(((void)"Share context is full", s->i < s->t));
179 assert(((void)"Share already present", !gfshare_addedp(s, x)));
181 /* --- If no vector has been allocated, create one --- */
184 s->v = XS_ALLOC(s->t * (s->sz + 1));
188 /* --- Store the share in the vector --- */
190 p = &GFSHARE_INDEX(s, s->i);
197 return (s->t - s->i);
200 /* --- @gfshare_combine@ --- *
202 * Arguments: @gfshare *s@ = pointer to share context
203 * @void *buf@ = pointer to output buffer for the secret
207 * Use: Reconstructs a secret, given enough shares.
210 void gfshare_combine(gfshare *s, void *buf)
215 /* --- Sanity checking --- */
217 assert(((void)"Not enough shares yet", s->i == s->t));
219 /* --- Grind through the shares --- */
221 memset(buf, 0, s->sz);
223 for (i = 0; i < s->t; i++) {
225 octet *q = &GFSHARE_INDEX(s, i);
226 unsigned c = 0, ci = 0;
228 /* --- Compute the magic coefficient --- */
231 for (j = 0; j < s->t; j++) {
234 xj = GFSHARE_INDEX(s, j);
235 c += gfshare_log[xj];
238 ci += gfshare_log[xi ^ xj];
246 /* --- Work out another layer of the secret --- */
249 for (j = 0; j < s->sz; j++) {
251 *p ^= gfshare_exp[c + gfshare_log[*q]];
257 /*----- Test rig ----------------------------------------------------------*/
263 static int verify(grand *r)
265 unsigned n = r->ops->range(r, 16) + 8;
266 unsigned t = r->ops->range(r, n - 1) + 1;
267 unsigned len = r->ops->range(r, 32) + 1;
269 octet *v = xmalloc(t * len);
270 unsigned *p = xmalloc(n * sizeof(unsigned));
271 octet *sec = xmalloc(len), *sbuf = xmalloc(len);
277 for (i = 0; i < n; i++)
279 for (i = 0; i < t; i++) {
280 unsigned long j = r->ops->range(r, n - i);
286 r->ops->fill(r, sec, len);
288 gfshare_create(&s, t, len);
290 gfshare_mkshares(&s, r, sec);
291 for (i = 0; i < t; i++)
292 gfshare_get(&s, p[i], v + (i * len));
295 gfshare_create(&s, t, len);
296 for (i = 0; i < t; i++)
297 gfshare_add(&s, p[i], v + (i * len));
298 gfshare_combine(&s, sbuf);
301 if (memcmp(sec, sbuf, len) != 0) {
303 fprintf(stderr, "\nbad recombination of shares\n");
317 grand *r = fibrand_create(0);
321 fputs("gfshare: ", stdout);
322 for (i = 0; i < 40; i++) {
330 fputs(" ok\n", stdout);
332 fputs(" failed\n", stdout);
333 return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
338 /*----- That's all, folks -------------------------------------------------*/