X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ceb3f0c0a3b7bb3fa3250d31b04c382894095e52..b817bfc642225b8c3c0b6a7e42d1fb949b61a606:/ec-prime.c

diff --git a/ec-prime.c b/ec-prime.c
index 40f487e..8f3c731 100644
--- a/ec-prime.c
+++ b/ec-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-prime.c,v 1.3.4.3 2004/03/21 22:39:46 mdw Exp $
+ * $Id: ec-prime.c,v 1.11 2004/04/08 01:36:15 mdw Exp $
  *
  * Elliptic curves over prime fields
  *
@@ -27,42 +27,12 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: ec-prime.c,v $
- * Revision 1.3.4.3  2004/03/21 22:39:46  mdw
- * Elliptic curves on binary fields work.
- *
- * Revision 1.3.4.2  2004/03/20 00:13:31  mdw
- * Projective coordinates for prime curves
- *
- * Revision 1.3.4.1  2003/06/10 13:43:53  mdw
- * Simple (non-projective) curves over prime fields now seem to work.
- *
- * Revision 1.3  2003/05/15 23:25:59  mdw
- * Make elliptic curve stuff build.
- *
- * Revision 1.2  2002/01/13 13:48:44  mdw
- * Further progress.
- *
- * Revision 1.1  2001/04/29 18:12:33  mdw
- * Prototype version.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include <mLib/sub.h>
 
 #include "ec.h"
 
-/*----- Data structures ---------------------------------------------------*/
-
-typedef struct ecctx {
-  ec_curve c;
-  mp *a, *b;
-} ecctx;
-
 /*----- Simple prime curves -----------------------------------------------*/
 
 static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops;
@@ -78,14 +48,13 @@ static ec *ecneg(ec_curve *c, ec *d, const ec *p)
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {
   mp *p, *q;
-  ecctx *cc = (ecctx *)c;
   field *f = c->f;
 
   q = F_SQR(f, MP_NEW, x);
   p = F_MUL(f, MP_NEW, x, q);
-  q = F_MUL(f, q, x, cc->a);
+  q = F_MUL(f, q, x, c->a);
   p = F_ADD(f, p, p, q);
-  p = F_ADD(f, p, p, cc->b);
+  p = F_ADD(f, p, p, c->b);
   MP_DROP(q);
   p = F_SQRT(f, p, p);
   if (!p)
@@ -105,14 +74,13 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
     EC_COPY(d, a);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
     mp *lambda;
     mp *dy, *dx;
 
     dx = F_SQR(f, MP_NEW, a->x);	/* %$x^2$% */
     dy = F_DBL(f, MP_NEW, a->y);	/* %$2 y$% */
     dx = F_TPL(f, dx, dx);		/* %$3 x^2$% */
-    dx = F_ADD(f, dx, dx, cc->a);	/* %$3 x^2 + A$% */
+    dx = F_ADD(f, dx, dx, c->a);	/* %$3 x^2 + A$% */
     dy = F_INV(f, dy, dy);		/* %$(2 y)^{-1}$% */
     lambda = F_MUL(f, MP_NEW, dx, dy);	/* %$\lambda = (3 x^2 + A)/(2 y)$% */
 
@@ -140,12 +108,11 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
     EC_COPY(d, a);
   else {
     field *f = c->f;
-    ecctx *cc = (ecctx *)c;
     mp *p, *q, *m, *s, *dx, *dy, *dz;
 
     p = F_SQR(f, MP_NEW, a->z);		/* %$z^2$% */
     q = F_SQR(f, MP_NEW, p);		/* %$z^4$% */
-    p = F_MUL(f, p, q, cc->a);		/* %$A z^4$% */
+    p = F_MUL(f, p, q, c->a);		/* %$A z^4$% */
     m = F_SQR(f, MP_NEW, a->x);		/* %$x^2$% */
     m = F_TPL(f, m, m);			/* %$3 x^2$% */
     m = F_ADD(f, m, m, p);		/* %$m = 3 x^2 + A z^4$% */
@@ -243,10 +210,9 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
       EC_SETINF(d);
       return (d);
     } else {
-      ecctx *cc = (ecctx *)c;
       dx = F_SQR(f, MP_NEW, a->x);	/* %$x_0^2$% */
       dx = F_TPL(f, dx, dx);		/* %$3 x_0^2$% */
-      dx = F_ADD(f, dx, dx, cc->a);	/* %$3 x_0^2 + A$% */
+      dx = F_ADD(f, dx, dx, c->a);	/* %$3 x_0^2 + A$% */
       dy = F_DBL(f, MP_NEW, a->y);	/* %$2 y_0$% */
       dy = F_INV(f, dy, dy);		/* %$(2 y_0)^{-1}$% */
       lambda = F_MUL(f, MP_NEW, dx, dy);
@@ -279,19 +245,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));
@@ -301,12 +274,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$% */
@@ -334,15 +308,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;
+  mp *l, *x, *r;
   int rc;
-  mp *l = F_SQR(f, MP_NEW, p->y);
-  mp *x = F_SQR(f, MP_NEW, p->x);
-  mp *r = F_MUL(f, MP_NEW, x, p->x);
-  x = F_MUL(f, x, cc->a, p->x);
+  if (EC_ATINF(p)) return (0);
+  l = F_SQR(f, MP_NEW, p->y);
+  x = F_SQR(f, MP_NEW, p->x);
+  r = F_MUL(f, MP_NEW, x, p->x);
+  x = F_MUL(f, x, c->a, p->x);
   r = F_ADD(f, r, r, x);
-  r = F_ADD(f, r, r, cc->b);
+  r = F_ADD(f, r, r, c->b);
   rc = MP_EQ(l, r) ? 0 : -1;
   mp_drop(l);
   mp_drop(x);
@@ -363,10 +338,9 @@ 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);
-  DESTROY(cc);
+  MP_DROP(c->a);
+  MP_DROP(c->b);
+  DESTROY(c);
 }
 
 /* --- @ec_prime@, @ec_primeproj@ --- *
@@ -374,7 +348,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 prime field.  The @primeproj@ variant uses projective
@@ -383,45 +357,45 @@ static void ecdestroy(ec_curve *c)
 
 extern ec_curve *ec_prime(field *f, mp *a, mp *b)
 {
-  ecctx *cc = CREATE(ecctx);
-  cc->c.ops = &ec_primeops;
-  cc->c.f = f;
-  cc->a = F_IN(f, MP_NEW, a);
-  cc->b = F_IN(f, MP_NEW, b);
-  return (&cc->c);
+  ec_curve *c = CREATE(ec_curve);
+  c->ops = &ec_primeops;
+  c->f = f;
+  c->a = F_IN(f, MP_NEW, a);
+  c->b = F_IN(f, MP_NEW, b);
+  return (c);
 }
 
 extern ec_curve *ec_primeproj(field *f, mp *a, mp *b)
 {
-  ecctx *cc = CREATE(ecctx);
+  ec_curve *c = CREATE(ec_curve);
   mp *ax;
 
   ax = mp_add(MP_NEW, a, MP_THREE);
   ax = F_IN(f, ax, ax);
   if (F_ZEROP(f, ax))
-    cc->c.ops = &ec_primeprojxops;
+    c->ops = &ec_primeprojxops;
   else
-    cc->c.ops = &ec_primeprojops;
+    c->ops = &ec_primeprojops;
   MP_DROP(ax);
-  cc->c.f = f;
-  cc->a = F_IN(f, MP_NEW, a);
-  cc->b = F_IN(f, MP_NEW, b);
-  return (&cc->c);
+  c->f = f;
+  c->a = F_IN(f, MP_NEW, a);
+  c->b = F_IN(f, MP_NEW, b);
+  return (c);
 }
 
 static const ec_ops ec_primeops = {
-  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_primeprojops = {
-  ecdestroy, ec_projin, ec_projout, ec_projfix,
-  0, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
+  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 };
 
 static const ec_ops ec_primeprojxops = {
-  ecdestroy, ec_projin, ec_projout, ec_projfix,
-  0, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
+  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
+  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
 };
 
 /*----- Test rig ----------------------------------------------------------*/
@@ -441,15 +415,15 @@ int main(int argc, char *argv[])
   printf("ec-prime: ");
   fflush(stdout);
   a = MP(-3);
-  b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
-  p = MP(6277101735386680763835789423207666416083908700390324961279);
-  r = MP(6277101735386680763835789423176059013767194773182842284080);
+  b = MP(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef);
+  p = MP(39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319);
+  r = MP(39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942642);
 
-  f = field_prime(p);
+  f = field_niceprime(p);
   c = ec_primeproj(f, a, b);
   
-  g.x = MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012);
-  g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
+  g.x = MP(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7);
+  g.y = MP(0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f);
 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);