[u/mdw/catacomb] / share.c

/* -*-c-*-
 *
 * $Id$
 *
 * 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.
 */

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "grand.h"
#include "mp.h"
#include "mpint.h"
#include "mpbarrett.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"
#include "share.h"

/*----- Main code ---------------------------------------------------------*/

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

void share_create(share *s, unsigned t)
{
  s->t = t;
  s->i = 0;
  s->p = 0;
  s->v = 0;
}

/* --- @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.
 */

void share_destroy(share *s)
{
  unsigned i;

  /* --- Dispose of the share vector --- */

  if (s->v) {
    for (i = 0; i < s->t; i++)
      mp_drop(s->v[i].y);
    xfree(s->v);
  }

  /* --- Other stuff --- */

  mp_drop(s->p);
}

/* --- @share_mkshares@ --- *
 *
 * Arguments:	@share *s@ = pointer to share context to fill in
 *		@grand *r@ = pointer to random number source
 *		@mp *n@ = 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 @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.
 */

void share_mkshares(share *s, grand *r, mp *n)
{
  unsigned i;

  /* --- If there's no prime, construct one --- */

  if (!s->p) {
    pgen_filterctx pf;
    rabin pr;
    mp *p;
    unsigned bits = (mp_octets(n) + 1) * 8;

    pf.step = 2;
    p = mprand(MP_NEW, bits, r, 1);
    s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
		rabin_iters(bits), pgen_test, &pr);
  }

  /* --- Construct the polynomial --- */

  if (!s->v)
    s->v = xmalloc(s->t * sizeof(share_pt));
  for (i = 0; i < s->t - 1; i++)
    s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0);
  s->v[s->t - 1].y = mp_copy(n);
}

/* --- @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.
 */

mp *share_get(share *s, mp *d, unsigned x)
{
  mpbarrett mb;
  mpw uw = x + 1;
  mp u;
  unsigned i;

  /* --- Various bits of initialization --- */

  mp_build(&u, &uw, &uw + 1);
  mp_drop(d);

  /* --- Evaluate the polynomial at %$x = i + 1$% --- */

  d = MP_ZERO;
  mpbarrett_create(&mb, s->p);
  for (i = 0; i < s->t; i++) {
    d = mp_mul(d, d, &u);
    d = mp_add(d, d, s->v[i].y);
    d = mpbarrett_reduce(&mb, d, d);
  }
  mpbarrett_destroy(&mb);

  return (d);
}

/* --- @share_addedp@ --- *
 *
 * Arguments:	@share *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 share_addedp(share *s, unsigned x)
{
  unsigned i;

  for (i = 0; i < s->i; i++) {
    if (s->v[i].x == x + 1)
      return (1);
  }
  return (0);
}

/* --- @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@.
 */

unsigned share_add(share *s, unsigned x, mp *y)
{
  assert(((void)"Share context is full", s->i < s->t));
  assert(((void)"Share already present", !share_addedp(s, x)));

  /* --- If no vector has been allocated, create one --- */

  if (!s->v) {
    unsigned i;
    s->v = xmalloc(s->t * sizeof(share_pt));
    s->i = 0;
    for (i = 0; i < s->t; i++)
      s->v[i].y = 0;
  }

  /* --- Store the share in the vector --- */

  s->v[s->i].x = x + 1;
  s->v[s->i].y = mp_copy(y);
  s->i++;

  /* --- Done --- */

  return (s->t - s->i);
}

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

mp *share_combine(share *s)
{
  mp *a = MP_ZERO;
  mpbarrett mb;
  unsigned i, j;
  mp ii, jj;
  mpw iiw, jjw;
  mp *m = MP_NEW;

  /* --- Sanity checking --- */

  assert(((void)"Not enough shares yet", s->i == s->t));

  /* --- Initialization --- */

  mpbarrett_create(&mb, s->p);
  mp_build(&ii, &iiw, &iiw + 1);
  mp_build(&jj, &jjw, &jjw + 1);

  /* --- Grind through the shares --- */

  for (i = 0; i < s->t; i++) {
    mp *c = MP_ONE;

    iiw = s->v[i].x;
    for (j = 0; j < s->t; j++) {
      if (i == j)
	continue;
      jjw = s->v[j].x;
      if (s->v[j].x >= s->v[i].x)
	m = mp_sub(m, &jj, &ii);
      else {
	m = mp_sub(m, &ii, &jj);
	m = mp_sub(m, s->p, m);
      }
      m = mp_modinv(m, m, s->p);
      c = mp_mul(c, c, &jj);
      c = mpbarrett_reduce(&mb, c, c);
      c = mp_mul(c, c, m);
      c = mpbarrett_reduce(&mb, c, c);
    }
    c = mp_mul(c, c, s->v[i].y);
    c = mpbarrett_reduce(&mb, c, c);
    a = mp_add(a, a, c);
    mp_drop(c);
  }

  a = mpbarrett_reduce(&mb, a, a);
  mp_drop(m);
  mpbarrett_destroy(&mb);
  return (a);
}

/*----- 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, 160);

  mp **v = xmalloc(t * sizeof(mp *));
  unsigned *p = xmalloc(n * sizeof(unsigned));
  mp *sec = mprand(MP_NEW, len, r, 0);
  share s;
  mp *pp;
  mp *ss;
  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;
  }

  share_create(&s, t);
  share_mkshares(&s, r, sec);
  for (i = 0; i < t; i++)
    v[i] = share_get(&s, MP_NEW, p[i]);
  pp = mp_copy(s.p);
  share_destroy(&s);
  assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2);

  share_create(&s, t);
  s.p = pp;
  for (i = 0; i < t; i++)
    share_add(&s, p[i], v[i]);
  ss = share_combine(&s);
  share_destroy(&s);

  if (!MP_EQ(sec, ss)) {
    ok = 0;
    fprintf(stderr, "\nbad recombination of shares\n");
  };

  mp_drop(sec);
  mp_drop(ss);

  for (i = 0; i < t; i++)
    mp_drop(v[i]);

  xfree(v);
  xfree(p);

  assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0);
  return (ok);
}

int main(void)
{
  grand *r = fibrand_create(0);
  unsigned i;
  int ok = 1;

  fputs("share: ", 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 -------------------------------------------------*/
Commit	Line	Data
71dfe576	1	/* --c--
71dfe576	2	*
aec42286	3	* $Id$
71dfe576	4	*
	5	* Shamir's secret sharing
	6	*
	7	* (c) 2000 Straylight/Edgeware
	8	*/
	9
45c0fd36	10	/----- Licensing notice --------------------------------------------------
71dfe576	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.
45c0fd36	18	*
71dfe576	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.
45c0fd36	23	*
71dfe576	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
71dfe576	30	/----- Header files ------------------------------------------------------/
	31
	32	#include <stdio.h>
	33	#include <stdlib.h>
	34	#include <string.h>
	35
	36	#include "grand.h"
	37	#include "mp.h"
	38	#include "mpint.h"
ad74e5b4	39	#include "mpbarrett.h"
71dfe576	40	#include "mprand.h"
	41	#include "pgen.h"
	42	#include "rabin.h"
	43	#include "share.h"
	44
	45	/----- Main code ---------------------------------------------------------/
	46
	47	/* --- @share_create@ --- *
	48	*
	49	* Arguments: @share *s@ = pointer to share context to initialize
3d64a35c	50	* @unsigned t@ = threshold for the system
71dfe576	51	*
	52	* Returns: ---
	53	*
	54	* Use: Initializes a sharing context.
	55	*/
	56
3d64a35c	57	void share_create(share *s, unsigned t)
71dfe576	58	{
71dfe576	59	s->t = t;
71dfe576	60	s->i = 0;
71dfe576	61	s->p = 0;
	62	s->v = 0;
	63	}
	64
	65	/* --- @share_destroy@ --- *
	66	*
	67	* Arguments: @share *s@ = pointer to share context to destroy
	68	*
	69	* Returns: ---
	70	*
	71	* Use: Disposes of a sharing context. All memory is freed, all
	72	* integers are dropped.
	73	*/
	74
	75	void share_destroy(share *s)
	76	{
71dfe576	77	unsigned i;
	78
	79	/* --- Dispose of the share vector --- */
	80
	81	if (s->v) {
eab06f16	82	for (i = 0; i < s->t; i++)
eab06f16	83	mp_drop(s->v[i].y);
71dfe576	84	xfree(s->v);
	85	}
	86
	87	/* --- Other stuff --- */
	88
eab06f16	89	mp_drop(s->p);
71dfe576	90	}
	91
	92	/* --- @share_mkshares@ --- *
	93	*
	94	* Arguments: @share *s@ = pointer to share context to fill in
	95	* @grand *r@ = pointer to random number source
5d4fee2a	96	* @mp *n@ = the secret to share
71dfe576	97	*
	98	* Returns: ---
	99	*
3d64a35c	100	* Use: Initializes a sharing context to be able to create shares.
71dfe576	101	* The context structure is expected to be mostly filled in. In
5d4fee2a	102	* particular, @t@ must be initialized. If @p@ is zero, a prime
	103	* number of appropriate size is generated automatically. If
	104	* @v@ is zero, a vector of appropriate size is allocated. You
	105	* should use the macro @SHARE_INIT@ or @share_create@ to
	106	* construct sharing contexts.
71dfe576	107	*/
71dfe576	108
5d4fee2a	109	void share_mkshares(share s, grand r, mp *n)
71dfe576	110	{
71dfe576	111	unsigned i;
71dfe576	112
	113	/* --- If there's no prime, construct one --- */
	114
	115	if (!s->p) {
	116	pgen_filterctx pf;
	117	rabin pr;
	118	mp *p;
5d4fee2a	119	unsigned bits = (mp_octets(n) + 1) * 8;
71dfe576	120
	121	pf.step = 2;
	122	p = mprand(MP_NEW, bits, r, 1);
	123	s->p = pgen("p", p, p, 0, 0, 0, pgen_filter, &pf,
	124	rabin_iters(bits), pgen_test, &pr);
	125	}
	126
3d64a35c	127	/* --- Construct the polynomial --- */
71dfe576	128
3d64a35c	129	if (!s->v)
3d64a35c	130	s->v = xmalloc(s->t * sizeof(share_pt));
71dfe576	131	for (i = 0; i < s->t - 1; i++)
3d64a35c	132	s->v[i].y = mprand_range(MP_NEWSEC, s->p, r, 0);
5d4fee2a	133	s->v[s->t - 1].y = mp_copy(n);
3d64a35c	134	}
71dfe576	135
3d64a35c	136	/* --- @share_get@ --- *
	137	*
	138	* Arguments: @share *s@ = pointer to share conext
	139	* @mp *d@ = destination for the share
	140	* @unsigned x@ = share index to fetch
	141	*
	142	* Returns: The share, as requested.
	143	*
	144	* Use: Extracts a share from the system. You may extract @MPW_MAX@
	145	* shares, or @s->p@ shares from the system, whichever is
	146	* smaller. Shares are indexed from 0.
	147	*/
71dfe576	148
3d64a35c	149	mp share_get(share s, mp *d, unsigned x)
	150	{
	151	mpbarrett mb;
	152	mpw uw = x + 1;
	153	mp u;
	154	unsigned i;
71dfe576	155
3d64a35c	156	/* --- Various bits of initialization --- */
71dfe576	157
3d64a35c	158	mp_build(&u, &uw, &uw + 1);
eab06f16	159	mp_drop(d);
71dfe576	160
3d64a35c	161	/* --- Evaluate the polynomial at %$x = i + 1$% --- */
71dfe576	162
3d64a35c	163	d = MP_ZERO;
	164	mpbarrett_create(&mb, s->p);
	165	for (i = 0; i < s->t; i++) {
	166	d = mp_mul(d, d, &u);
	167	d = mp_add(d, d, s->v[i].y);
	168	d = mpbarrett_reduce(&mb, d, d);
71dfe576	169	}
ad74e5b4	170	mpbarrett_destroy(&mb);
71dfe576	171
3d64a35c	172	return (d);
71dfe576	173	}
71dfe576	174
aec42286	175	/* --- @share_addedp@ --- *
	176	*
	177	* Arguments: @share *s@ = pointer to sharing context
	178	* @unsigned x@ = which share number to check
	179	*
	180	* Returns: Nonzero if share @x@ has been added already, zero if it
	181	* hasn't.
	182	*/
	183
	184	int share_addedp(share *s, unsigned x)
	185	{
	186	unsigned i;
	187
	188	for (i = 0; i < s->i; i++) {
	189	if (s->v[i].x == x + 1)
	190	return (1);
	191	}
	192	return (0);
	193	}
	194
71dfe576	195	/* --- @share_add@ --- *
	196	*
	197	* Arguments: @share *s@ = pointer to sharing context
	198	* @unsigned x@ = which share number this is
	199	* @mp *y@ = the share value
	200	*
	201	* Returns: Number of shares required before recovery may be performed.
	202	*
	203	* Use: Adds a share to the context. The context must have been
	204	* initialized with the correct prime @p@ and threshold @t@.
	205	*/
	206
	207	unsigned share_add(share s, unsigned x, mp y)
	208	{
aec42286	209	assert(((void)"Share context is full", s->i < s->t));
	210	assert(((void)"Share already present", !share_addedp(s, x)));
	211
71dfe576	212	/* --- If no vector has been allocated, create one --- */
	213
	214	if (!s->v) {
3d64a35c	215	unsigned i;
71dfe576	216	s->v = xmalloc(s->t * sizeof(share_pt));
71dfe576	217	s->i = 0;
3d64a35c	218	for (i = 0; i < s->t; i++)
3d64a35c	219	s->v[i].y = 0;
71dfe576	220	}
71dfe576	221
71dfe576	222	/* --- Store the share in the vector --- */
71dfe576	223
3d64a35c	224	s->v[s->i].x = x + 1;
71dfe576	225	s->v[s->i].y = mp_copy(y);
	226	s->i++;
	227
	228	/* --- Done --- */
	229
	230	return (s->t - s->i);
	231	}
	232
	233	/* --- @share_combine@ --- *
	234	*
	235	* Arguments: @share *s@ = pointer to share context
	236	*
	237	* Returns: The secret, as a multiprecision integer.
	238	*
	239	* Use: Reconstructs a secret, given enough shares.
	240	*/
	241
	242	mp share_combine(share s)
	243	{
	244	mp *a = MP_ZERO;
ad74e5b4	245	mpbarrett mb;
71dfe576	246	unsigned i, j;
ad74e5b4	247	mp ii, jj;
ad74e5b4	248	mpw iiw, jjw;
71dfe576	249	mp *m = MP_NEW;
	250
	251	/* --- Sanity checking --- */
	252
	253	assert(((void)"Not enough shares yet", s->i == s->t));
	254
	255	/* --- Initialization --- */
	256
ad74e5b4	257	mpbarrett_create(&mb, s->p);
	258	mp_build(&ii, &iiw, &iiw + 1);
	259	mp_build(&jj, &jjw, &jjw + 1);
71dfe576	260
	261	/* --- Grind through the shares --- */
	262
	263	for (i = 0; i < s->t; i++) {
ad74e5b4	264	mp *c = MP_ONE;
71dfe576	265
3d64a35c	266	iiw = s->v[i].x;
71dfe576	267	for (j = 0; j < s->t; j++) {
	268	if (i == j)
	269	continue;
3d64a35c	270	jjw = s->v[j].x;
71dfe576	271	if (s->v[j].x >= s->v[i].x)
ad74e5b4	272	m = mp_sub(m, &jj, &ii);
71dfe576	273	else {
ad74e5b4	274	m = mp_sub(m, &ii, &jj);
71dfe576	275	m = mp_sub(m, s->p, m);
71dfe576	276	}
b817bfc6	277	m = mp_modinv(m, m, s->p);
ad74e5b4	278	c = mp_mul(c, c, &jj);
	279	c = mpbarrett_reduce(&mb, c, c);
	280	c = mp_mul(c, c, m);
	281	c = mpbarrett_reduce(&mb, c, c);
71dfe576	282	}
ad74e5b4	283	c = mp_mul(c, c, s->v[i].y);
ad74e5b4	284	c = mpbarrett_reduce(&mb, c, c);
71dfe576	285	a = mp_add(a, a, c);
	286	mp_drop(c);
	287	}
	288
ad74e5b4	289	a = mpbarrett_reduce(&mb, a, a);
eab06f16	290	mp_drop(m);
ad74e5b4	291	mpbarrett_destroy(&mb);
71dfe576	292	return (a);
	293	}
	294
	295	/----- Test rig ----------------------------------------------------------/
	296
	297	#ifdef TEST_RIG
	298
	299	#include "fibrand.h"
	300
	301	static int verify(grand *r)
	302	{
	303	unsigned n = r->ops->range(r, 16) + 8;
	304	unsigned t = r->ops->range(r, n - 1) + 1;
	305	unsigned len = r->ops->range(r, 160);
	306
3d64a35c	307	mp *v = xmalloc(t sizeof(mp *));
71dfe576	308	unsigned p = xmalloc(n sizeof(unsigned));
	309	mp *sec = mprand(MP_NEW, len, r, 0);
	310	share s;
	311	mp *pp;
	312	mp *ss;
	313	unsigned i;
	314
	315	int ok = 1;
	316
	317	for (i = 0; i < n; i++)
	318	p[i] = i;
	319	for (i = 0; i < t; i++) {
	320	unsigned long j = r->ops->range(r, n - i);
	321	unsigned x = p[i];
	322	p[i] = p[i + j];
	323	p[i + j] = x;
	324	}
	325
3d64a35c	326	share_create(&s, t);
5d4fee2a	327	share_mkshares(&s, r, sec);
3d64a35c	328	for (i = 0; i < t; i++)
3d64a35c	329	v[i] = share_get(&s, MP_NEW, p[i]);
71dfe576	330	pp = mp_copy(s.p);
71dfe576	331	share_destroy(&s);
3d64a35c	332	assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == t + 2);
71dfe576	333
3d64a35c	334	share_create(&s, t);
71dfe576	335	s.p = pp;
3d64a35c	336	for (i = 0; i < t; i++)
3d64a35c	337	share_add(&s, p[i], v[i]);
71dfe576	338	ss = share_combine(&s);
	339	share_destroy(&s);
	340
22bab86c	341	if (!MP_EQ(sec, ss)) {
71dfe576	342	ok = 0;
	343	fprintf(stderr, "\nbad recombination of shares\n");
	344	};
	345
	346	mp_drop(sec);
	347	mp_drop(ss);
	348
	349	for (i = 0; i < t; i++)
3d64a35c	350	mp_drop(v[i]);
71dfe576	351
	352	xfree(v);
	353	xfree(p);
	354
3d64a35c	355	assert(mparena_count(MPARENA_GLOBAL) + mparena_count(MPARENA_SECURE) == 0);
71dfe576	356	return (ok);
	357	}
	358
	359	int main(void)
	360	{
	361	grand *r = fibrand_create(0);
	362	unsigned i;
	363	int ok = 1;
	364
	365	fputs("share: ", stdout);
	366	for (i = 0; i < 40; i++) {
	367	if (!verify(r))
	368	ok = 0;
	369	fputc('.', stdout);
	370	fflush(stdout);
	371	}
	372
	373	if (ok)
	374	fputs(" ok\n", stdout);
	375	else
	376	fputs(" failed\n", stdout);
	377	return (ok ? EXIT_SUCCESS : EXIT_FAILURE);
	378	}
	379
	380	#endif
	381
	382	/----- That's all, folks -------------------------------------------------/