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

   1 /* -*-c-*-
   2  *
   3  * Shamir's secret sharing
   4  *
   5  * (c) 2000 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  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.
  16  *
  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.
  21  *
  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,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Notes on the sharing system ---------------------------------------*
  29  *
  30  * Shamir's secret-sharing system is based on polynomial interpolation modulo
  31  * a prime number.  It is `perfect' in that fewer participants than the
  32  * threshold can derive no information about the secret by pooling their
  33  * shares, and `ideal' in that the shares are the same size as the secret.
  34  *
  35  * This implementation stays close to the definition, in order to support
  36  * other schemes for (e.g.) threshold cryptography.  It is, however, rather
  37  * slow.
  38  */
  39
  40 #ifndef CATACOMB_SHARE_H
  41 #define CATACOMB_SHARE_H
  42
  43 #ifdef __cplusplus
  44   extern "C" {
  45 #endif
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #ifndef CATACOMB_GRAND_H
  50 #  include "grand.h"
  51 #endif
  52
  53 #ifndef CATACOMB_MP_H
  54 #  include "mp.h"
  55 #endif
  56
  57 /*----- Data structures ---------------------------------------------------*/
  58
  59 /* --- A secret sharing context --- */
  60
  61 typedef struct share_pt {
  62   unsigned x;                           /* Index of this share */
  63   mp *y;                                /* Payload of this share */
  64 } share_pt;
  65
  66 typedef struct share {
  67   unsigned t;                           /* Threshold */
  68   unsigned i;                           /* Next free slot in the vector */
  69   mp *p;                                /* Modulus for arithmetic */
  70   share_pt *v;                          /* Vector of share information */
  71 } share;
  72
  73 #define SHARE_INIT(t) { t, 0, 0, 0 }
  74
  75 /*----- Functions provided ------------------------------------------------*/
  76
  77 /* --- @share_create@ --- *
  78  *
  79  * Arguments:   @share *s@ = pointer to share context to initialize
  80  *              @unsigned t@ = threshold for the system
  81  *
  82  * Returns:     ---
  83  *
  84  * Use:         Initializes a sharing context.
  85  */
  86
  87 extern void share_create(share */*s*/, unsigned /*t*/);
  88
  89 /* --- @share_destroy@ --- *
  90  *
  91  * Arguments:   @share *s@ = pointer to share context to destroy
  92  *
  93  * Returns:     ---
  94  *
  95  * Use:         Disposes of a sharing context.  All memory is freed, all
  96  *              integers are dropped.
  97  */
  98
  99 extern void share_destroy(share */*s*/);
 100
 101 /* --- @share_mkshares@ --- *
 102  *
 103  * Arguments:   @share *s@ = pointer to share context to fill in
 104  *              @grand *r@ = pointer to random number source
 105  *              @mp *n@ = the secret to share
 106  *
 107  * Returns:     ---
 108  *
 109  * Use:         Initializes a sharing context to be able to create shares.
 110  *              The context structure is expected to be mostly filled in.  In
 111  *              particular, @t@ must be initialized.  If @p@ is zero, a prime
 112  *              number of appropriate size is generated automatically.  If
 113  *              @v@ is zero, a vector of appropriate size is allocated.  You
 114  *              should use the macro @SHARE_INIT@ or @share_create@ to
 115  *              construct sharing contexts.
 116  */
 117
 118 extern void share_mkshares(share */*s*/, grand */*r*/, mp */*n*/);
 119
 120 /* --- @share_get@ --- *
 121  *
 122  * Arguments:   @share *s@ = pointer to share conext
 123  *              @mp *d@ = destination for the share
 124  *              @unsigned x@ = share index to fetch
 125  *
 126  * Returns:     The share, as requested.
 127  *
 128  * Use:         Extracts a share from the system.  You may extract @MPW_MAX@
 129  *              shares, or @s->p@ shares from the system, whichever is
 130  *              smaller.  Shares are indexed from 0.
 131  */
 132
 133 extern mp *share_get(share */*s*/, mp */*d*/, unsigned /*x*/);
 134
 135 /* --- @share_addedp@ --- *
 136  *
 137  * Arguments:   @share *s@ = pointer to sharing context
 138  *              @unsigned x@ = which share number to check
 139  *
 140  * Returns:     Nonzero if share @x@ has been added already, zero if it
 141  *              hasn't.
 142  */
 143
 144 extern int share_addedp(share */*s*/, unsigned /*x*/);
 145
 146 /* --- @share_add@ --- *
 147  *
 148  * Arguments:   @share *s@ = pointer to sharing context
 149  *              @unsigned x@ = which share number this is
 150  *              @mp *y@ = the share value
 151  *
 152  * Returns:     Number of shares required before recovery may be performed.
 153  *
 154  * Use:         Adds a share to the context.  The context must have been
 155  *              initialized with the correct prime @p@ and threshold @t@.
 156  */
 157
 158 extern unsigned share_add(share */*s*/, unsigned /*x*/, mp */*y*/);
 159
 160 /* --- @share_combine@ --- *
 161  *
 162  * Arguments:   @share *s@ = pointer to share context
 163  *
 164  * Returns:     The secret, as a multiprecision integer.
 165  *
 166  * Use:         Reconstructs a secret, given enough shares.
 167  */
 168
 169 extern mp *share_combine(share */*s*/);
 170
 171 /*----- That's all, folks -------------------------------------------------*/
 172
 173 #ifdef __cplusplus
 174   }
 175 #endif
 176
 177 #endif