/* -*-c-*-
*
- * $Id: share.c,v 1.1 2000/06/17 12:09:38 mdw Exp $
+ * $Id: share.c,v 1.2 2000/06/18 23:05:19 mdw Exp $
*
* Shamir's secret sharing
*
/*----- Revision history --------------------------------------------------*
*
* $Log: share.c,v $
+ * Revision 1.2 2000/06/18 23:05:19 mdw
+ * Minor performance tweak: use Barrett reduction rather than Montgomery.
+ * Fast secret sharing isn't done here, though: see `gfshare' instead.
+ *
* Revision 1.1 2000/06/17 12:09:38 mdw
* Shamir's secret sharing system.
*
#include "grand.h"
#include "mp.h"
#include "mpint.h"
-#include "mpmont.h"
+#include "mpbarrett.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"
{
mp **v;
unsigned i;
- mp *u;
- mpmont mm;
+ mp u;
+ mpw uw;
+ mpbarrett mb;
/* --- If there's no prime, construct one --- */
/* --- Construct the coefficients --- */
- mpmont_create(&mm, s->p);
+ mpbarrett_create(&mb, s->p);
v = xmalloc(s->t * sizeof(mp *));
for (i = 0; i < s->t - 1; i++)
v[i] = mprand_range(MP_NEW, s->p, r, 0);
- v[s->t - 1] = mpmont_mul(&mm, MP_NEW, s->s, mm.r2);
+ v[s->t - 1] = s->s;
/* --- Construct the shares --- */
if (!s->v)
s->v = xmalloc(s->n * sizeof(share_pt));
- u = mp_copy(mm.r);
- for (i = 0; i < s->n; i++) {
+ mp_build(&u, &uw, &uw + 1);
+ for (uw = 1; uw <= s->n; uw++) {
mp *m = MP_ZERO;
unsigned j;
/* --- Evaluate the polynomial at %$x = i + 1$% --- */
for (j = 0; j < s->t; j++) {
- m = mpmont_mul(&mm, m, m, u);
+ m = mp_mul(m, m, &u);
+ m = mpbarrett_reduce(&mb, m, m);
m = mp_add(m, m, v[j]);
if (MP_CMP(m, >=, s->p))
m = mp_sub(m, m, s->p);
/* --- Reduce the final result --- */
- s->v[i].x = i;
- s->v[i].y = mpmont_reduce(&mm, m, m);
-
- /* --- Compute the next point in Montgomery space --- */
-
- u = mp_add(u, u, mm.r);
- if (MP_CMP(u, >=, s->p))
- u = mp_sub(u, u, s->p);
+ s->v[uw - 1].x = uw - 1;
+ s->v[uw - 1].y = m;
}
- mpmont_destroy(&mm);
+ mpbarrett_destroy(&mb);
/* --- Dispose of various bits of old rubbish --- */
- for (i = 0; i < s->t; i++)
+ for (i = 0; i < s->t - 1; i++)
mp_drop(v[i]);
- mp_drop(u);
xfree(v);
}
mp *share_combine(share *s)
{
mp *a = MP_ZERO;
- mpmont mm;
+ mpbarrett mb;
unsigned i, j;
- mp *ii = MP_NEW, *jj = MP_NEW;
+ mp ii, jj;
+ mpw iiw, jjw;
mp *m = MP_NEW;
/* --- Sanity checking --- */
/* --- Initialization --- */
- mpmont_create(&mm, s->p);
+ 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_copy(mm.r);
+ mp *c = MP_ONE;
- ii = mp_fromuint(ii, s->v[i].x + 1);
+ iiw = s->v[i].x + 1;
for (j = 0; j < s->t; j++) {
if (i == j)
continue;
- jj = mp_fromuint(jj, s->v[j].x + 1);
+ jjw = s->v[j].x + 1;
if (s->v[j].x >= s->v[i].x)
- m = mp_sub(m, jj, ii);
+ m = mp_sub(m, &jj, &ii);
else {
- m = mp_sub(m, ii, jj);
+ m = mp_sub(m, &ii, &jj);
m = mp_sub(m, s->p, m);
}
- jj = mpmont_mul(&mm, jj, jj, mm.r2);
mp_gcd(0, 0, &m, s->p, m);
- m = mpmont_mul(&mm, m, m, mm.r2);
- m = mpmont_mul(&mm, m, m, jj);
- c = mpmont_mul(&mm, c, c, m);
+ c = mp_mul(c, c, &jj);
+ c = mpbarrett_reduce(&mb, c, c);
+ c = mp_mul(c, c, m);
+ c = mpbarrett_reduce(&mb, c, c);
}
- m = mpmont_mul(&mm, m, s->v[i].y, mm.r2);
- c = mpmont_mul(&mm, c, c, m);
+ 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 = mpmont_reduce(&mm, a, a);
+ a = mpbarrett_reduce(&mb, a, a);
s->s = mp_copy(a);
- mp_drop(ii);
- if (jj)
- mp_drop(jj);
- mp_drop(m);
- mpmont_destroy(&mm);
+ if (m)
+ mp_drop(m);
+ mpbarrett_destroy(&mb);
return (a);
}