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

diff --git a/ec-bin.c b/ec-bin.c
index 42aaad8..30e19a9 100644
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-bin.c,v 1.3 2004/03/22 02:19:09 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,22 +27,6 @@
  * MA 02111-1307, USA.
  */
 
-/*----- 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.
- *
- * Revision 1.1.2.1  2004/03/21 22:39:46  mdw
- * Elliptic curves on binary fields work.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include <mLib/sub.h>
@@ -53,7 +37,6 @@
 
 typedef struct ecctx {
   ec_curve c;
-  mp *a, *b;
   mp *bb;
 } ecctx;
 
@@ -82,8 +65,32 @@ static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
 
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {
-  /* write me */
-  return (0);
+  field *f = c->f;
+  mp *y, *u, *v;
+  
+  if (F_ZEROP(f, x))
+    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, 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)) {
+      u = F_INV(f, u, u);		/* %$x^{-2}$% */
+      v = F_MUL(f, v, u, y);	    /* %$B = A x^{-2} = x + a + b x^{-2}$% */
+      y = F_QUADSOLVE(f, y, v);		/* %$z^2 + z = B$% */
+      if (y) y = F_MUL(f, y, y, x);	/* %$y = z x$% */
+    }
+    MP_DROP(u);
+    MP_DROP(v);
+  }
+  if (!y) return (0);
+  EC_DESTROY(d);
+  d->x = MP_COPY(x);
+  d->y = y;
+  d->z = MP_COPY(f->one);
+  return (d);
 }
 
 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
@@ -92,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;
 
@@ -102,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$% */
@@ -151,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);
 }
@@ -168,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;
 
@@ -181,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$% */
@@ -195,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;
     }
       
@@ -223,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$% */
@@ -265,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$% */
@@ -292,21 +293,21 @@ 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);
   u = F_ADD(f, u, u, v);
-  rc = F_ZEROP(f, u);
+  rc = F_ZEROP(f, u) ? 0 : -1;
   mp_drop(u);
   mp_drop(v);
   return (rc);
@@ -326,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);
 }
@@ -337,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
@@ -349,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);
 }
@@ -360,21 +361,28 @@ 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,
-  0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+  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,
-  0, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
+  ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 };
 
 /*----- Test rig ----------------------------------------------------------*/
@@ -388,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(0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad);
-  p = MP(0x20000000000000000000000000000000000000004000000000000000001);
-  r =
-  MP(6901746346790563787434755862277025555839812737345013555379383634485462);
+  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(0x0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b);
-  g.y = MP(0x1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052);
+  g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8);
+  g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f);
 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);
@@ -424,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);