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

   1 /* -*-c-*-
   2  *
   3  * $Id: share.h,v 1.1 2000/06/17 12:09:38 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.h,v $
  33  * Revision 1.1  2000/06/17 12:09:38  mdw
  34  * Shamir's secret sharing system.
  35  *
  36  */
  37
  38 /*----- Notes on the sharing system ---------------------------------------*
  39  *
  40  * Shamir's secret-sharing system is based on polynomial interpolation modulo
  41  * a prime number.  It is `perfect' in that fewer participants than the
  42  * threshold can derive no information about the secret by pooling their
  43  * shares, and `ideal' in that the shares are the same size as the secret.
  44  *
  45  * This implementation stays close to the definition, in order to support
  46  * other schemes for (e.g.) threshold cryptography.  It is, however, rather
  47  * slow.
  48  */
  49
  50 #ifndef CATACOMB_SHARE_H
  51 #define CATACOMB_SHARE_H
  52
  53 #ifdef __cplusplus
  54   extern "C" {
  55 #endif
  56
  57 /*----- Header files ------------------------------------------------------*/
  58
  59 #ifndef CATACOMB_GRAND_H
  60 #  include "grand.h"
  61 #endif
  62
  63 #ifndef CATACOMB_MP_H
  64 #  include "mp.h"
  65 #endif
  66
  67 /*----- Data structures ---------------------------------------------------*/
  68
  69 /* --- A secret sharing context --- */
  70
  71 typedef struct share_pt {
  72   unsigned x;                           /* Index of this share */
  73   mp *y;                                /* Payload of this share */
  74 } share_pt;
  75
  76 typedef struct share {
  77   unsigned t;                           /* Threshold */
  78   unsigned n;                           /* The number of shares to make */
  79   unsigned i;                           /* Next free slot in the vector */
  80   mp *s;                                /* The secret */
  81   mp *p;                                /* Modulus for arithmetic */
  82   share_pt *v;                          /* Vector of share information */
  83 } share;
  84
  85 #define SHARE_INIT(t, n) { t, n, 0, 0, 0, 0 }
  86
  87 /*----- Functions provided ------------------------------------------------*/
  88
  89 /* --- @share_create@ --- *
  90  *
  91  * Arguments:   @share *s@ = pointer to share context to initialize
  92  *              @unsigned t, n@ = threshold parameters for the system
  93  *
  94  * Returns:     ---
  95  *
  96  * Use:         Initializes a sharing context.
  97  */
  98
  99 extern void share_create(share */*s*/, unsigned /*t*/, unsigned /*n*/);
 100
 101 /* --- @share_destroy@ --- *
 102  *
 103  * Arguments:   @share *s@ = pointer to share context to destroy
 104  *
 105  * Returns:     ---
 106  *
 107  * Use:         Disposes of a sharing context.  All memory is freed, all
 108  *              integers are dropped.
 109  */
 110
 111 extern void share_destroy(share */*s*/);
 112
 113 /* --- @share_mkshares@ --- *
 114  *
 115  * Arguments:   @share *s@ = pointer to share context to fill in
 116  *              @grand *r@ = pointer to random number source
 117  *
 118  * Returns:     ---
 119  *
 120  * Use:         Generates @c->n@ secret shares, such that any @c->t@ of them
 121  *              may be used to recover the secret.
 122  *
 123  *              The context structure is expected to be mostly filled in.  In
 124  *              particular, @t@, @n@ and @s@ must be initialized.  If @p@ is
 125  *              zero, a prime number of appropriate size is generated
 126  *              automatically.  If @v@ is zero, a vector of appropriate size
 127  *              is allocated.  You should use the macro @SHARE_INIT@ or
 128  *              @share_create@ to construct sharing contexts.
 129  */
 130
 131 extern void share_mkshares(share */*s*/, grand */*r*/);
 132
 133 /* --- @share_add@ --- *
 134  *
 135  * Arguments:   @share *s@ = pointer to sharing context
 136  *              @unsigned x@ = which share number this is
 137  *              @mp *y@ = the share value
 138  *
 139  * Returns:     Number of shares required before recovery may be performed.
 140  *
 141  * Use:         Adds a share to the context.  The context must have been
 142  *              initialized with the correct prime @p@ and threshold @t@.
 143  */
 144
 145 extern unsigned share_add(share */*s*/, unsigned /*x*/, mp */*y*/);
 146
 147 /* --- @share_combine@ --- *
 148  *
 149  * Arguments:   @share *s@ = pointer to share context
 150  *
 151  * Returns:     The secret, as a multiprecision integer.
 152  *
 153  * Use:         Reconstructs a secret, given enough shares.
 154  */
 155
 156 extern mp *share_combine(share */*s*/);
 157
 158 /*----- That's all, folks -------------------------------------------------*/
 159
 160 #ifdef __cplusplus
 161   }
 162 #endif
 163
 164 #endif