projects
/
u
/
mdw
/
catacomb
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Use the new @mp_odd@ function.
[u/mdw/catacomb]
/
share.c
diff --git
a/share.c
b/share.c
index
f450934
..
d427706
100644
(file)
--- a/
share.c
+++ b/
share.c
@@
-1,6
+1,6
@@
/* -*-c-*-
*
/* -*-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
*
*
* Shamir's secret sharing
*
@@
-30,6
+30,10
@@
/*----- Revision history --------------------------------------------------*
*
* $Log: share.c,v $
/*----- 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.
*
* Revision 1.1 2000/06/17 12:09:38 mdw
* Shamir's secret sharing system.
*
@@
-44,7
+48,7
@@
#include "grand.h"
#include "mp.h"
#include "mpint.h"
#include "grand.h"
#include "mp.h"
#include "mpint.h"
-#include "mp
mon
t.h"
+#include "mp
barret
t.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"
@@
-133,8
+137,9
@@
void share_mkshares(share *s, grand *r)
{
mp **v;
unsigned i;
{
mp **v;
unsigned i;
- mp *u;
- mpmont mm;
+ mp u;
+ mpw uw;
+ mpbarrett mb;
/* --- If there's no prime, construct one --- */
/* --- If there's no prime, construct one --- */
@@
-152,26
+157,27
@@
void share_mkshares(share *s, grand *r)
/* --- Construct the coefficients --- */
/* --- Construct the coefficients --- */
- mp
mont_create(&mm
, s->p);
+ mp
barrett_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 = 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));
/* --- 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++) {
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);
m = mp_add(m, m, v[j]);
if (MP_CMP(m, >=, s->p))
m = mp_sub(m, m, s->p);
@@
-179,22
+185,15
@@
void share_mkshares(share *s, grand *r)
/* --- Reduce the final result --- */
/* --- 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;
}
}
- mp
mont_destroy(&mm
);
+ mp
barrett_destroy(&mb
);
/* --- Dispose of various bits of old rubbish --- */
/* --- 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(v[i]);
- mp_drop(u);
xfree(v);
}
xfree(v);
}
@@
-244,9
+243,10
@@
unsigned share_add(share *s, unsigned x, mp *y)
mp *share_combine(share *s)
{
mp *a = MP_ZERO;
mp *share_combine(share *s)
{
mp *a = MP_ZERO;
- mp
mont mm
;
+ mp
barrett mb
;
unsigned i, j;
unsigned i, j;
- mp *ii = MP_NEW, *jj = MP_NEW;
+ mp ii, jj;
+ mpw iiw, jjw;
mp *m = MP_NEW;
/* --- Sanity checking --- */
mp *m = MP_NEW;
/* --- Sanity checking --- */
@@
-255,43
+255,43
@@
mp *share_combine(share *s)
/* --- Initialization --- */
/* --- 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++) {
/* --- 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)
;
+ ii
w = s->v[i].x + 1
;
for (j = 0; j < s->t; j++) {
if (i == j)
continue;
for (j = 0; j < s->t; j++) {
if (i == j)
continue;
- jj
= mp_fromuint(jj, s->v[j].x + 1)
;
+ jj
w = s->v[j].x + 1
;
if (s->v[j].x >= s->v[i].x)
if (s->v[j].x >= s->v[i].x)
- m = mp_sub(m,
jj,
ii);
+ m = mp_sub(m,
&jj, &
ii);
else {
else {
- m = mp_sub(m,
ii,
jj);
+ m = mp_sub(m,
&ii, &
jj);
m = mp_sub(m, s->p, m);
}
m = mp_sub(m, s->p, m);
}
- jj = mpmont_mul(&mm, jj, jj, mm.r2);
mp_gcd(0, 0, &m, s->p, m);
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 = mp
mont_mul(&mm, c, c, m
);
+
c = mp_mul(c, c, s->v[i].y
);
+ c = mp
barrett_reduce(&mb, c, c
);
a = mp_add(a, a, c);
mp_drop(c);
}
a = mp_add(a, a, c);
mp_drop(c);
}
- a = mp
mont_reduce(&mm
, a, a);
+ a = mp
barrett_reduce(&mb
, a, a);
s->s = mp_copy(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);
}
return (a);
}