X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/bc985cefafea2e1b02095a2ff2a9982c4c647d17..c65df27983057ec76ed0e72bb370f9a5ae7dad28:/ec-bin.c

diff --git a/ec-bin.c b/ec-bin.c
index a71ed2d..30e19a9 100644
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec-bin.c,v 1.9 2004/04/08 01:36:15 mdw Exp $
  *
  * Arithmetic for elliptic curves over binary fields
  *
@@ -27,25 +27,6 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: ec-bin.c,v $
- * 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>
@@ -56,7 +37,6 @@
 
 typedef struct ecctx {
   ec_curve c;
-  mp *a, *b;
   mp *bb;
 } ecctx;
 
@@ -86,15 +66,14 @@ static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {
   field *f = c->f;
-  ecctx *cc = (ecctx *)c;
   mp *y, *u, *v;
   
   if (F_ZEROP(f, x))
-    y = F_SQRT(f, MP_NEW, cc->b);
+    y = F_SQRT(f, MP_NEW, c->b);
   else {
     u = F_SQR(f, MP_NEW, x);		/* %$x^2$% */
-    y = F_MUL(f, MP_NEW, u, cc->a);	/* %$a x^2$% */
-    y = F_ADD(f, y, y, cc->b);		/* %$a x^2 + b$% */
+    y = F_MUL(f, MP_NEW, u, c->a);	/* %$a x^2$% */
+    y = F_ADD(f, y, y, c->b);		/* %$a x^2 + b$% */
     v = F_MUL(f, MP_NEW, u, x);		/* %$x^3$% */
     y = F_ADD(f, y, y, v);		/* %$A = x^3 + a x^2 + b$% */
     if (!F_ZEROP(f, y)) {
@@ -120,7 +99,6 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
     EC_SETINF(d);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
     mp *lambda;
     mp *dx, *dy;
 
@@ -130,7 +108,7 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
 
     dx = F_SQR(f, dx, lambda);		/* %$\lambda^2$% */
     dx = F_ADD(f, dx, dx, lambda);	/* %$\lambda^2 + \lambda$% */
-    dx = F_ADD(f, dx, dx, cc->a);     /* %$x' = a + \lambda^2 + \lambda$% */
+    dx = F_ADD(f, dx, dx, c->a);       /* %$x' = a + \lambda^2 + \lambda$% */
 
     dy = F_ADD(f, MP_NEW, a->x, dx);	/* %$ x + x' $% */
     dy = F_MUL(f, dy, dy, lambda);	/* %$ (x + x') \lambda$% */
@@ -179,9 +157,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);
 }
@@ -196,7 +171,6 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
     EC_COPY(d, a);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
     mp *lambda;
     mp *dx, *dy;
 
@@ -209,7 +183,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 
       dx = F_SQR(f, dx, lambda);	/* %$\lambda^2$% */
       dx = F_ADD(f, dx, dx, lambda);	/* %$\lambda^2 + \lambda$% */
-      dx = F_ADD(f, dx, dx, cc->a);	/* %$a + \lambda^2 + \lambda$% */
+      dx = F_ADD(f, dx, dx, c->a);	/* %$a + \lambda^2 + \lambda$% */
       dx = F_ADD(f, dx, dx, a->x);    /* %$a + \lambda^2 + \lambda + x_0$% */
       dx = F_ADD(f, dx, dx, b->x);
                            /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */
@@ -223,7 +197,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 
       dx = F_SQR(f, dx, lambda);	/* %$\lambda^2$% */
       dx = F_ADD(f, dx, dx, lambda);	/* %$\lambda^2 + \lambda$% */
-      dx = F_ADD(f, dx, dx, cc->a);    /* %$x' = a + \lambda^2 + \lambda$% */
+      dx = F_ADD(f, dx, dx, c->a);    /* %$x' = a + \lambda^2 + \lambda$% */
       dy = MP_NEW;
     }
       
@@ -251,7 +225,6 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b)
     EC_COPY(d, a);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
     mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l;
 
     dz = F_SQR(f, MP_NEW, b->z);	/* %$z_1^2$% */
@@ -293,7 +266,7 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b)
     t = F_ADD(f, t, r, dz);		/* %$t = r + z'$% */
 
     uu = F_SQR(f, MP_NEW, dz);		/* %$z'^2$% */
-    dx = F_MUL(f, MP_NEW, uu, cc->a);	/* %$a z'^2$% */
+    dx = F_MUL(f, MP_NEW, uu, c->a);	/* %$a z'^2$% */
     uu = F_MUL(f, uu, t, r);		/* %$t r$% */
     dx = F_ADD(f, dx, dx, uu);		/* %$a z'^2 + t r$% */
     r = F_SQR(f, r, w);			/* %$w^2$% */
@@ -320,16 +293,16 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 
 static int eccheck(ec_curve *c, const ec *p)
 {
-  ecctx *cc = (ecctx *)c;
   field *f = c->f;
   int rc;
   mp *u, *v;
 
+  if (EC_ATINF(p)) return (0);
   v = F_SQR(f, MP_NEW, p->x);
   u = F_MUL(f, MP_NEW, v, p->x);
-  v = F_MUL(f, v, v, cc->a);
+  v = F_MUL(f, v, v, c->a);
   u = F_ADD(f, u, u, v);
-  u = F_ADD(f, u, u, cc->b);
+  u = F_ADD(f, u, u, c->b);
   v = F_MUL(f, v, p->x, p->y);
   u = F_ADD(f, u, u, v);
   v = F_SQR(f, v, p->y);
@@ -354,8 +327,8 @@ static int ecprojcheck(ec_curve *c, const ec *p)
 static void ecdestroy(ec_curve *c)
 {
   ecctx *cc = (ecctx *)c;
-  MP_DROP(cc->a);
-  MP_DROP(cc->b);
+  MP_DROP(cc->c.a);
+  MP_DROP(cc->c.b);
   if (cc->bb) MP_DROP(cc->bb);
   DESTROY(cc);
 }
@@ -365,7 +338,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
@@ -377,8 +350,8 @@ ec_curve *ec_bin(field *f, mp *a, mp *b)
   ecctx *cc = CREATE(ecctx);
   cc->c.ops = &ec_binops;
   cc->c.f = f;
-  cc->a = F_IN(f, MP_NEW, a);
-  cc->b = F_IN(f, MP_NEW, b);
+  cc->c.a = F_IN(f, MP_NEW, a);
+  cc->c.b = F_IN(f, MP_NEW, b);
   cc->bb = 0;
   return (&cc->c);
 }
@@ -388,20 +361,27 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b)
   ecctx *cc = CREATE(ecctx);
   cc->c.ops = &ec_binprojops;
   cc->c.f = f;
-  cc->a = F_IN(f, MP_NEW, a);
-  cc->b = F_IN(f, MP_NEW, b);
-  cc->bb = F_SQRT(f, MP_NEW, b);
-  cc->bb = F_SQRT(f, cc->bb, cc->bb);
+  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);
+  if (cc->bb)
+    cc->bb = F_SQRT(f, cc->bb, cc->bb);
+  if (!cc->bb) {
+    MP_DROP(cc->c.a);
+    MP_DROP(cc->c.b);
+    DESTROY(cc);
+    return (0);
+  }
   return (&cc->c);
 }
 
 static const ec_ops ec_binops = {
-  ecdestroy, ec_idin, ec_idout, ec_idfix,
+  ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
   ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
 };
 
 static const ec_ops ec_binprojops = {
-  ecdestroy, ec_projin, ec_projout, ec_projfix,
+  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
   ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 };
 
@@ -416,22 +396,21 @@ int main(int argc, char *argv[])
   field *f;
   ec_curve *c;
   ec g = EC_INIT, d = EC_INIT;
-  mp *p, *a, *b, *r;
+  mp *p, *a, *b, *r, *beta;
   int i, n = argc == 1 ? 1 : atoi(argv[1]);
 
   printf("ec-bin: ");
   fflush(stdout);
-  a = MP(1);
-  b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f);
-  p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001);
-  r =
-  MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770);
+  a = MP(0x7ffffffffffffffffffffffffffffffffffffffff);
+  b = MP(0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb);
+  p = MP(0x800000000000000000000000000000000000000c9);
+  beta = MP(0x715169c109c612e390d347c748342bcd3b02a0bef);
+  r = MP(0x040000000000000000000292fe77e70c12a4234c32);
 
-  f = field_binpoly(p);
+  f = field_binnorm(p, beta);
   c = ec_binproj(f, a, b);
-  
-  g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7);
-  g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706);
+  g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8);
+  g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f);
 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);
@@ -452,7 +431,7 @@ int main(int argc, char *argv[])
   ec_destroy(&g);
   ec_destroycurve(c);
   F_DESTROY(f);
-  MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r);
+  MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); MP_DROP(beta);
   assert(!mparena_count(&mparena_global));
   printf("ok\n");
   return (0);