ec-bin (ec_binproj): Make curve setup faster.

[u/mdw/catacomb] / ec-bin.c

diff --git a/ec-bin.c b/ec-bin.c
index db1bebf..e84252c 100644 (file)
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-bin.c,v 1.7 2004/04/01 21:28:41 mdw Exp $
+ * $Id$
  *
  * Arithmetic for elliptic curves over binary fields
  *
@@ -27,52 +27,12 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: ec-bin.c,v $
- * Revision 1.7  2004/04/01 21:28:41  mdw
- * Normal basis support (translates to poly basis internally).  Rewrite
- * EC and prime group table generators in awk, so that they can reuse data
- * for repeated constants.
- *
- * Revision 1.6  2004/04/01 12:50:09  mdw
- * Add cyclic group abstraction, with test code.  Separate off exponentation
- * functions for better static linking.  Fix a buttload of bugs on the way.
- * Generally ensure that negative exponents do inversion correctly.  Add
- * table of standard prime-field subgroups.  (Binary field subgroups are
- * currently unimplemented but easy to add if anyone ever finds a good one.)
- *
- * Revision 1.5  2004/03/27 17:54:11  mdw
- * Standard curves and curve checking.
- *
- * Revision 1.4  2004/03/23 15:19:32  mdw
- * Test elliptic curves more thoroughly.
- *
- * 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.
- *
- * Revision 1.1.2.1  2004/03/21 22:39:46  mdw
- * Elliptic curves on binary fields work.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include <mLib/sub.h>
 
 #include "ec.h"
-
-/*----- Data structures ---------------------------------------------------*/
-
-typedef struct ecctx {
-  ec_curve c;
-  mp *bb;
-} ecctx;
+#include "ec-guts.h"
 
 /*----- Main code ---------------------------------------------------------*/
 
@@ -164,7 +124,7 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
     EC_SETINF(d);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
+    ecctx_bin *cc = (ecctx_bin *)c;
     mp *dx, *dy, *dz, *u, *v;
 
     dy = F_SQR(f, MP_NEW, a->z);       /* %$z^2$% */
@@ -191,9 +151,6 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
     d->z = dz;
     MP_DROP(u);
     MP_DROP(v);
-    assert(!(d->x->f & MP_DESTROYED));
-    assert(!(d->y->f & MP_DESTROYED));
-    assert(!(d->z->f & MP_DESTROYED));
   }
   return (d);
 }
@@ -363,7 +320,7 @@ static int ecprojcheck(ec_curve *c, const ec *p)
 
 static void ecdestroy(ec_curve *c)
 {
-  ecctx *cc = (ecctx *)c;
+  ecctx_bin *cc = (ecctx_bin *)c;
   MP_DROP(cc->c.a);
   MP_DROP(cc->c.b);
   if (cc->bb) MP_DROP(cc->bb);
@@ -375,7 +332,7 @@ static void ecdestroy(ec_curve *c)
  * Arguments:  @field *f@ = the underlying field for this elliptic curve
  *             @mp *a, *b@ = the coefficients for this curve
  *
- * Returns:    A pointer to the curve.
+ * Returns:    A pointer to the curve, or null.
  *
  * Use:                Creates a curve structure for an elliptic curve defined over
  *             a binary field.  The @binproj@ variant uses projective
@@ -384,7 +341,7 @@ static void ecdestroy(ec_curve *c)
 
 ec_curve *ec_bin(field *f, mp *a, mp *b)
 {
-  ecctx *cc = CREATE(ecctx);
+  ecctx_bin *cc = CREATE(ecctx_bin);
   cc->c.ops = &ec_binops;
   cc->c.f = f;
   cc->c.a = F_IN(f, MP_NEW, a);
@@ -395,22 +352,40 @@ ec_curve *ec_bin(field *f, mp *a, mp *b)
 
 ec_curve *ec_binproj(field *f, mp *a, mp *b)
 {
-  ecctx *cc = CREATE(ecctx);
+  ecctx_bin *cc = CREATE(ecctx_bin);
+  int i;
+  mp *c, *d;
+
   cc->c.ops = &ec_binprojops;
   cc->c.f = f;
   cc->c.a = F_IN(f, MP_NEW, a);
   cc->c.b = F_IN(f, MP_NEW, b);
-  cc->bb = F_SQRT(f, MP_NEW, cc->c.b);
-  cc->bb = F_SQRT(f, cc->bb, cc->bb);
+
+  c = MP_COPY(cc->c.b);
+  for (i = 0; i < f->nbits - 2; i++)
+    c = F_SQR(f, c, c);
+  d = F_SQR(f, MP_NEW, c); d = F_SQR(f, d, d);
+  if (!MP_EQ(d, cc->c.b)) {
+    MP_DROP(c);
+    MP_DROP(d);
+    MP_DROP(cc->c.a);
+    MP_DROP(cc->c.b);
+    DESTROY(cc);
+    return (0);
+  }
+  cc->bb = c;
+  MP_DROP(d);
   return (&cc->c);
 }
 
 static const ec_ops ec_binops = {
+  "bin",
   ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
   ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
 };
 
 static const ec_ops ec_binprojops = {
+  "binproj",
   ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
   ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 };