+++ /dev/null
-/* -*-c-*-
- *
- * $Id$
- *
- * Secret sharing over %$\gf{2^8}$%
- *
- * (c) 2000 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * Catacomb is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * Catacomb is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with Catacomb; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-/*----- Header files ------------------------------------------------------*/
-
-#include <assert.h>
-#include <stdarg.h>
-#include <stdio.h>
-#include <string.h>
-
-#include <mLib/alloc.h>
-#include <mLib/bits.h>
-
-#include "arena.h"
-#include "gfshare.h"
-#include "gfshare-tab.h"
-#include "grand.h"
-
-/*----- Static variables --------------------------------------------------*/
-
-static const octet gflog[] = GFSHARE_LOG, gfexp[] = GFSHARE_EXP;
-
-/*----- Main code ---------------------------------------------------------*/
-
-/* --- @gfshare_create@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to share context to initialize
- * @unsigned t@ = threshold for the system
- * @size_t sz@ = size of the secret
- *
- * Returns: ---
- *
- * Use: Initializes a sharing context.
- */
-
-void gfshare_create(gfshare *s, unsigned t, size_t sz)
-{
- s->t = t;
- s->i = 0;
- s->sz = sz;
- s->v = 0;
-}
-
-/* --- @gfshare_destroy@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to share context to destroy
- *
- * Returns: ---
- *
- * Use: Disposes of a sharing context. The allocations for the
- * individual shares and the vector @v@ are freed; the secret is
- * left alone.
- */
-
-void gfshare_destroy(gfshare *s)
-{
- if (s->v)
- XS_FREE(s->v);
-}
-
-/* --- @gfshare_mkshares@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to share context to fill in
- * @grand *r@ = pointer to random number source
- * @const void *buf@ = pointer to the secret to share
- *
- * Returns: ---
- *
- * Use: Initializes a sharing context to be able to create shares.
- * The context structure is expected to be mostly filled in. In
- * particular, @t@ must be initialized. If @v@ is zero, a
- * vector of appropriate size is allocated. You should use the
- * macro @GFSHARE_INIT@ or @gfshare_create@ to construct sharing
- * contexts.
- */
-
-void gfshare_mkshares(gfshare *s, grand *r, const void *buf)
-{
- s->v = XS_ALLOC(s->sz * s->t);
- r->ops->fill(r, s->v, s->sz * (s->t - 1));
- memcpy(s->v + s->sz * (s->t - 1), buf, s->sz);
-}
-
-/* --- @gfshare_get@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to share conext
- * @unsigned x@ = share index to fetch
- * @void *buf@ = pointer to output buffer
- *
- * Returns: ---
- *
- * Use: Extracts a share from the system. You may extract up to 255
- * shares from the system. Shares are indexed from 0.
- */
-
-void gfshare_get(gfshare *s, unsigned x, void *buf)
-{
- unsigned i;
- const octet *p = s->v;
- unsigned ilog = gflog[x + 1];
-
- /* --- Evaluate the polynomial at %$x = i + 1$% --- */
-
- memcpy(buf, p, s->sz);
- p += s->sz;
-
- for (i = 1; i < s->t; i++) {
- octet *q = buf;
- unsigned k;
- for (k = 0; k < s->sz; k++) {
- unsigned qq = *q;
- if (qq)
- qq = gfexp[ilog + gflog[qq]];
- *q++ = qq ^ *p++;
- }
- }
-}
-
-/* --- @gfshare_addedp@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to sharing context
- * @unsigned x@ = which share number to check
- *
- * Returns: Nonzero if share @x@ has been added already, zero if it
- * hasn't.
- */
-
-int gfshare_addedp(gfshare *s, unsigned x)
-{
- unsigned i;
-
- for (i = 0; i < s->i; i++) {
- if (GFSHARE_INDEX(s, i) == x + 1)
- return (1);
- }
- return (0);
-}
-
-/* --- @gfshare_add@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to sharing context
- * @unsigned x@ = which share number this is
- * @const void *y@ = the share value
- *
- * Returns: Number of shares required before recovery may be performed.
- *
- * Use: Adds a share to the context. The context must have been
- * initialized with the correct threshold @t@.
- */
-
-unsigned gfshare_add(gfshare *s, unsigned x, const void *y)
-{
- octet *p;
-
- assert(((void)"Share context is full", s->i < s->t));
- assert(((void)"Share already present", !gfshare_addedp(s, x)));
-
- /* --- If no vector has been allocated, create one --- */
-
- if (!s->v) {
- s->v = XS_ALLOC(s->t * (s->sz + 1));
- s->i = 0;
- }
-
- /* --- Store the share in the vector --- */
-
- p = &GFSHARE_INDEX(s, s->i);
- *p++ = x + 1;
- memcpy(p, y, s->sz);
- s->i++;
-
- /* --- Done --- */
-
- return (s->t - s->i);
-}
-
-/* --- @gfshare_combine@ --- *
- *
- * Arguments: @gfshare *s@ = pointer to share context
- * @void *buf@ = pointer to output buffer for the secret
- *
- * Returns: ---
- *
- * Use: Reconstructs a secret, given enough shares.
- */
-
-void gfshare_combine(gfshare *s, void *buf)
-{
- unsigned i, j;
- unsigned xi, xj;
-
- /* --- Sanity checking --- */
-
- assert(((void)"Not enough shares yet", s->i == s->t));
-
- /* --- Grind through the shares --- */
-
- memset(buf, 0, s->sz);
-
- for (i = 0; i < s->t; i++) {
- octet *p = buf;
- octet *q = &GFSHARE_INDEX(s, i);
- unsigned c = 0, ci = 0;
-
- /* --- Compute the magic coefficient --- */
-
- xi = *q++;
- for (j = 0; j < s->t; j++) {
- if (i == j)
- continue;
- xj = GFSHARE_INDEX(s, j);
- c += gflog[xj];
- if (c >= 0xff)
- c -= 0xff;
- ci += gflog[xi ^ xj];
- if (ci >= 0xff)
- ci -= 0xff;
- }
- if (ci > c)
- c += 0xff;
- c -= ci;
-
- /* --- Work out another layer of the secret --- */
-
- p = buf;
- for (j = 0; j < s->sz; j++) {
- if (*q)
- *p ^= gfexp[c + gflog[*q]];
- p++, q++;
- }
- }
-}
-
-/*----- Test rig ----------------------------------------------------------*/
-
-#ifdef TEST_RIG
-
-#include "fibrand.h"
-
-static int verify(grand *r)
-{
- unsigned n = r->ops->range(r, 16) + 8;
- unsigned t = r->ops->range(r, n - 1) + 1;
- unsigned len = r->ops->range(r, 32) + 1;
-
- octet *v = xmalloc(t * len);
- unsigned *p = xmalloc(n * sizeof(unsigned));
- octet *sec = xmalloc(len), *sbuf = xmalloc(len);
- gfshare s;
- unsigned i;
-
- int ok = 1;
-
- for (i = 0; i < n; i++)
- p[i] = i;
- for (i = 0; i < t; i++) {
- unsigned long j = r->ops->range(r, n - i);
- unsigned x = p[i];
- p[i] = p[i + j];
- p[i + j] = x;
- }
-
- r->ops->fill(r, sec, len);
-
- gfshare_create(&s, t, len);
-
- gfshare_mkshares(&s, r, sec);
- for (i = 0; i < t; i++)
- gfshare_get(&s, p[i], v + (i * len));
- gfshare_destroy(&s);
-
- gfshare_create(&s, t, len);
- for (i = 0; i < t; i++)
- gfshare_add(&s, p[i], v + (i * len));
- gfshare_combine(&s, sbuf);
- gfshare_destroy(&s);
-
- if (memcmp(sec, sbuf, len) != 0) {
- ok = 0;
- fprintf(stderr, "\nbad recombination of shares\n");
- };
-
- xfree(sec);
- xfree(sbuf);
-
- xfree(v);
- xfree(p);
-
- return (ok);
-}
-
-int main(void)
-{
- grand *r = fibrand_create(0);
- unsigned i;
- int ok = 1;
-
- fputs("gfshare: ", stdout);
- for (i = 0; i < 40; i++) {
- if (!verify(r))
- ok = 0;
- fputc('.', stdout);
- fflush(stdout);
- }
-
- if (ok)
- fputs(" ok\n", stdout);
- else
- fputs(" failed\n", stdout);
- return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
-}
-
-#endif
-
-/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff