From 391faf428ac513f9031c773016d79fdbe8b4653c Mon Sep 17 00:00:00 2001 From: mdw Date: Mon, 22 Mar 2004 02:19:10 +0000 Subject: [PATCH] Rationalise the sliding-window threshold. Drop guarantee that right arguments to EC @add@ are canonical, and fix up projective implementations to cope. --- ec-bin.c | 8 ++++++-- ec-exp.h | 9 +++++++-- ec-prime.c | 29 +++++++++++++++++++++-------- ec.h | 16 ++++++++++++---- exp.h | 20 +++++++++++++++++--- 5 files changed, 63 insertions(+), 19 deletions(-) diff --git a/ec-bin.c b/ec-bin.c index 3e85e65..42aaad8 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-bin.c,v 1.2 2004/03/21 22:52:06 mdw Exp $ + * $Id: ec-bin.c,v 1.3 2004/03/22 02:19:09 mdw Exp $ * * Arithmetic for elliptic curves over binary fields * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-bin.c,v $ + * Revision 1.3 2004/03/22 02:19:09 mdw + * Rationalise the sliding-window threshold. Drop guarantee that right + * arguments to EC @add@ are canonical, and fix up projective implementations + * to cope. + * * Revision 1.2 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -411,7 +416,6 @@ int main(int argc, char *argv[]) fprintf(stderr, "didn't reach zero\n"); MP_EPRINTX("d.x", d.x); MP_EPRINTX("d.y", d.y); - MP_EPRINTX("d.z", d.y); return (1); } ec_destroy(&d); diff --git a/ec-exp.h b/ec-exp.h index 0daf717..fb3ed6e 100644 --- a/ec-exp.h +++ b/ec-exp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-exp.h,v 1.3 2004/03/21 22:52:06 mdw Exp $ + * $Id: ec-exp.h,v 1.4 2004/03/22 02:19:10 mdw Exp $ * * Exponentiation operations for elliptic curves * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-exp.h,v $ + * Revision 1.4 2004/03/22 02:19:10 mdw + * Rationalise the sliding-window threshold. Drop guarantee that right + * arguments to EC @add@ are canonical, and fix up projective implementations + * to cope. + * * Revision 1.3 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -64,7 +69,7 @@ #define EXP_MUL(a, x) EC_ADD(c, &(a), &(a), &(x)) #define EXP_SQR(a) EC_DBL(c, &(a), &(a)); -#define EXP_FIX(x) EC_FIX(c, &(x), &(x)); +#define EXP_FIX(x) #define EXP_SETMUL(d, x, y) do { \ EC_CREATE(&(d)); \ diff --git a/ec-prime.c b/ec-prime.c index bdc6368..827c0f2 100644 --- a/ec-prime.c +++ b/ec-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-prime.c,v 1.4 2004/03/21 22:52:06 mdw Exp $ + * $Id: ec-prime.c,v 1.5 2004/03/22 02:19:10 mdw Exp $ * * Elliptic curves over prime fields * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-prime.c,v $ + * Revision 1.5 2004/03/22 02:19:10 mdw + * Rationalise the sliding-window threshold. Drop guarantee that right + * arguments to EC @add@ are canonical, and fix up projective implementations + * to cope. + * * Revision 1.4 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -282,19 +287,26 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) EC_COPY(d, a); else { field *f = c->f; - mp *p, *q, *r, *w, *u, *s, *dx, *dy, *dz; + mp *p, *q, *r, *w, *u, *uu, *s, *ss, *dx, *dy, *dz; q = F_SQR(f, MP_NEW, a->z); /* %$z_0^2$% */ u = F_MUL(f, MP_NEW, q, b->x); /* %$u = x_1 z_0^2$% */ p = F_MUL(f, MP_NEW, q, b->y); /* %$y_1 z_0^2$% */ s = F_MUL(f, q, p, a->z); /* %$s = y_1 z_0^3$% */ - w = F_SUB(f, p, a->x, u); /* %$w = x_0 - u$% */ - r = F_SUB(f, MP_NEW, a->y, s); /* %$r = y_0 - s$% */ + q = F_SQR(f, MP_NEW, b->z); /* %$z_1^2$% */ + uu = F_MUL(f, MP_NEW, q, a->x); /* %$uu = x_0 z_1^2$%*/ + p = F_MUL(f, p, q, a->y); /* %$y_0 z_1^2$% */ + ss = F_MUL(f, q, p, b->z); /* %$ss = y_0 z_1^3$% */ + + w = F_SUB(f, p, uu, u); /* %$w = uu - u$% */ + r = F_SUB(f, MP_NEW, ss, s); /* %$r = ss - s$% */ if (F_ZEROP(f, w)) { MP_DROP(w); MP_DROP(u); MP_DROP(s); + MP_DROP(uu); + MP_DROP(ss); if (F_ZEROP(f, r)) { MP_DROP(r); return (c->ops->dbl(c, d, a)); @@ -304,12 +316,13 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) return (d); } } - u = F_ADD(f, u, u, a->x); /* %$t = x_0 + u$% */ - s = F_ADD(f, s, s, a->y); /* %$m = y_0 + r$% */ + u = F_ADD(f, u, u, uu); /* %$t = uu + u$% */ + s = F_ADD(f, s, s, ss); /* %$m = ss + r$% */ - dz = F_MUL(f, MP_NEW, a->z, w); /* %$z' = z_0 w$% */ + uu = F_MUL(f, uu, a->z, w); /* %$z_0 w$% */ + dz = F_MUL(f, ss, uu, b->z); /* %$z' = z_0 z_1 w$% */ - p = F_SQR(f, MP_NEW, w); /* %$w^2$% */ + p = F_SQR(f, uu, w); /* %$w^2$% */ q = F_MUL(f, MP_NEW, p, u); /* %$t w^2$% */ u = F_MUL(f, u, p, w); /* %$w^3$% */ p = F_MUL(f, p, u, s); /* %$m w^3$% */ diff --git a/ec.h b/ec.h index 07f1468..680bf9c 100644 --- a/ec.h +++ b/ec.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec.h,v 1.5 2004/03/21 22:52:06 mdw Exp $ + * $Id: ec.h,v 1.6 2004/03/22 02:19:10 mdw Exp $ * * Elliptic curve definitions * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec.h,v $ + * Revision 1.6 2004/03/22 02:19:10 mdw + * Rationalise the sliding-window threshold. Drop guarantee that right + * arguments to EC @add@ are canonical, and fix up projective implementations + * to cope. + * * Revision 1.5 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -95,9 +100,12 @@ typedef struct ec_mulfactor { /* --- Elliptic curve operations --- * * * All operations (apart from @destroy@ and @in@) are guaranteed to be - * performed on internal representations of points. Moreover, the second - * argument to @add@ and @mul@ is guaranteed to be the output of @in@ or - * @fix@. + * performed on internal representations of points. + * + * (Historical note. We used to guarantee that the second to @add@ and @mul@ + * was the output of @in@ or @fix@, but this canonification turned out to + * make the precomputation in @ec_exp@ too slow. Projective implementations + * must therefore cope with a pair of arbitrary points.) */ typedef struct ec_ops { diff --git a/exp.h b/exp.h index 6bfd686..59cb632 100644 --- a/exp.h +++ b/exp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: exp.h,v 1.2 2004/03/21 22:52:06 mdw Exp $ + * $Id: exp.h,v 1.3 2004/03/22 02:19:10 mdw Exp $ * * Generalized exponentiation * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: exp.h,v $ + * Revision 1.3 2004/03/22 02:19:10 mdw + * Rationalise the sliding-window threshold. Drop guarantee that right + * arguments to EC @add@ are canonical, and fix up projective implementations + * to cope. + * * Revision 1.2 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -84,10 +89,19 @@ typedef struct exp_simul { # define EXP_WINSZ 4 /* Predefine if you need to */ #endif -/* --- These are determined from the window size --- */ +/* --- These are determined from the window size --- * + * + * Given a %$k$%-bit exponent, I expect to do %$k/2$% multiplies if I use the + * simple way. If I use an n-bit sliding window, then I do %$2^n$% + * multiplies up front, but I only do %$(2^n - 1)/2^n k/n$% multiplies for + * the exponentiation. This is a win when + * + * %$k \ge \frac{n 2^{n+1}}{n - 2}$% + */ #define EXP_TABSZ (1 << EXP_WINSZ) -#define EXP_THRESH (((MPW_BITS / EXP_WINSZ) << 2) + 1) +#define EXP_THRESH \ + ((EXP_WINSZ * (2 << EXP_WINSZ))/((EXP_WINSZ - 2) * MPW_BITS)) /* --- Required operations --- * * -- 2.11.0