Pollard's rho algorithm for computing discrete logs.

[u/mdw/catacomb] / share.h

/* -*-c-*-
 *
 * $Id: share.h,v 1.2 2000/06/24 18:29:05 mdw Exp $
 *
 * Shamir's secret sharing
 *
 * (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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: share.h,v $
 * Revision 1.2  2000/06/24 18:29:05  mdw
 * Interface change: allow shares to be extracted from a context on demand,
 * rather than building them all up-front.
 *
 * Revision 1.1  2000/06/17 12:09:38  mdw
 * Shamir's secret sharing system.
 *
 */

/*----- Notes on the sharing system ---------------------------------------*
 *
 * Shamir's secret-sharing system is based on polynomial interpolation modulo
 * a prime number.  It is `perfect' in that fewer participants than the
 * threshold can derive no information about the secret by pooling their
 * shares, and `ideal' in that the shares are the same size as the secret.
 *
 * This implementation stays close to the definition, in order to support
 * other schemes for (e.g.) threshold cryptography.  It is, however, rather
 * slow.
 */

#ifndef CATACOMB_SHARE_H
#define CATACOMB_SHARE_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Header files ------------------------------------------------------*/

#ifndef CATACOMB_GRAND_H
#  include "grand.h"
#endif

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

/*----- Data structures ---------------------------------------------------*/

/* --- A secret sharing context --- */

typedef struct share_pt {
  unsigned x;				/* Index of this share */
  mp *y;				/* Payload of this share */
} share_pt;

typedef struct share {
  unsigned t;				/* Threshold */
  unsigned i;				/* Next free slot in the vector */
  mp *s;				/* The secret */
  mp *p;				/* Modulus for arithmetic */
  share_pt *v;				/* Vector of share information */
} share;

#define SHARE_INIT(t) { t, 0, 0, 0, 0 }

/*----- Functions provided ------------------------------------------------*/

/* --- @share_create@ --- *
 *
 * Arguments:	@share *s@ = pointer to share context to initialize
 *		@unsigned t@ = threshold for the system
 *
 * Returns:	---
 *
 * Use:		Initializes a sharing context.
 */

extern void share_create(share */*s*/, unsigned /*t*/);

/* --- @share_destroy@ --- *
 *
 * Arguments:	@share *s@ = pointer to share context to destroy
 *
 * Returns:	---
 *
 * Use:		Disposes of a sharing context.  All memory is freed, all
 *		integers are dropped.
 */

extern void share_destroy(share */*s*/);

/* --- @share_mkshares@ --- *
 *
 * Arguments:	@share *s@ = pointer to share context to fill in
 *		@grand *r@ = pointer to random number source
 *
 * 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@ and @s@ must be initialized.  If @p@ is	zero,
 *		a prime number of appropriate size is generated
 *		automatically.  If @v@ is zero, a vector of appropriate size
 *		is allocated.  You should use the macro @SHARE_INIT@ or
 *		@share_create@ to construct sharing contexts.
 */

extern void share_mkshares(share */*s*/, grand */*r*/);

/* --- @share_get@ --- *
 *
 * Arguments:	@share *s@ = pointer to share conext
 *		@mp *d@ = destination for the share
 *		@unsigned x@ = share index to fetch
 *
 * Returns:	The share, as requested.
 *
 * Use:		Extracts a share from the system.  You may extract @MPW_MAX@
 *		shares, or @s->p@ shares from the system, whichever is
 *		smaller.  Shares are indexed from 0.
 */

extern mp *share_get(share */*s*/, mp */*d*/, unsigned /*x*/);

/* --- @share_add@ --- *
 *
 * Arguments:	@share *s@ = pointer to sharing context
 *		@unsigned x@ = which share number this is
 *		@mp *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 prime @p@ and threshold @t@.
 */

extern unsigned share_add(share */*s*/, unsigned /*x*/, mp */*y*/);

/* --- @share_combine@ --- *
 *
 * Arguments:	@share *s@ = pointer to share context
 *
 * Returns:	The secret, as a multiprecision integer.
 *
 * Use:		Reconstructs a secret, given enough shares.
 */

extern mp *share_combine(share */*s*/);

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif