X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/b0ab12e6a6cb035df2b6312df7ad1736af0a6128..2b645fb792c62ae0d38fcde4c39e1bd0889b0e06:/ec-prime.c

diff --git a/ec-prime.c b/ec-prime.c
index 5a806da..4611855 100644
--- a/ec-prime.c
+++ b/ec-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-prime.c,v 1.1 2001/04/29 18:12:33 mdw Exp $
+ * $Id: ec-prime.c,v 1.3 2003/05/15 23:25:59 mdw Exp $
  *
  * Elliptic curves over prime fields
  *
@@ -30,6 +30,12 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-prime.c,v $
+ * 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.
  *
@@ -37,6 +43,8 @@
 
 /*----- Header files ------------------------------------------------------*/
 
+#include <mLib/sub.h>
+
 #include "ec.h"
 
 /*----- Data structures ---------------------------------------------------*/
@@ -48,25 +56,167 @@ typedef struct ecctx {
 
 /*----- Main code ---------------------------------------------------------*/
 
-static void ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
+static const ec_ops ec_primeops;
+
+static ec *ecneg(ec_curve *c, ec *d, const ec *p)
+{
+  EC_COPY(d, p);
+  d->y = F_NEG(c->f, d->y, d->y);
+  return (d);
+}
+
+static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
 {
-  /* --- Deal with the simple cases --- */
+  if (EC_ATINF(a))
+    EC_SETINF(d);
+  else if (!MP_LEN(a->y))
+    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);
+    dy = F_DBL(f, MP_NEW, a->y);
+    dx = F_TPL(f, dx, dx);
+    dx = F_ADD(f, dx, dx, cc->a);
+    dy = F_INV(f, dy, dy);
+    lambda = F_MUL(f, MP_NEW, dx, dy);
+
+    dx = F_SQR(f, dx, lambda);
+    dy = F_DBL(f, dy, a->x);
+    dx = F_SUB(f, dx, dx, dy);
+    dy = F_SUB(f, dy, a->x, dx);
+    dy = F_MUL(f, dy, lambda, dy);
+    dy = F_SUB(f, dy, dy, a->y);
 
+    EC_DESTROY(d);
+    d->x = dx;
+    d->y = dy;
+    d->z = 0;
+    MP_DROP(lambda);
+  }
+  return (d);
+}
+
+static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
+{
   if (a == b)
     ecdbl(c, d, a);
   else if (EC_ATINF(a))
     EC_COPY(d, b);
   else if (EC_ATINF(b))
     EC_COPY(d, a);
-  else if (MP_EQ(a->x, b->x) && MP_EQ(a->z, b->z)) {
-    if ((a->y->f ^ b->y->f) & MP_NEG)
+  else {
+    field *f = c->f;
+    mp *lambda;
+    mp *dy, *dx;
+
+    if (!MP_EQ(a->x, b->x)) {
+      dy = F_SUB(f, MP_NEW, a->y, b->y);
+      dx = F_SUB(f, MP_NEW, a->x, b->x);
+      dx = F_INV(f, dx, dx);
+      lambda = F_MUL(f, MP_NEW, dy, dx);
+    } else if (!MP_LEN(a->y) || !MP_EQ(a->y, b->y)) {
       EC_SETINF(d);
-    else
-      ecdbl(c, d, a);
-  } else {
+      return (d);
+    } else {
+      ecctx *cc = (ecctx *)c;
+      dx = F_SQR(f, MP_NEW, a->x);
+      dx = F_TPL(f, dx, dx);
+      dx = F_ADD(f, dx, dx, cc->a);
+      dy = F_DBL(f, MP_NEW, a->y);
+      dy = F_INV(f, dy, dy);
+      lambda = F_MUL(f, MP_NEW, dx, dy);
+    }
 
-    /* --- 
+    dx = F_SQR(f, dx, lambda);
+    dx = F_SUB(f, dx, dx, a->x);
+    dx = F_SUB(f, dx, dx, b->x);
+    dy = F_SUB(f, dy, b->x, dx);
+    dy = F_MUL(f, dy, lambda, dy);
+    dy = F_SUB(f, dy, dy, b->y);
+
+    EC_DESTROY(d);
+    d->x = dx;
+    d->y = dy;
+    d->z = 0;
+    MP_DROP(lambda);
   }
+  return (d);
+}
+
+static void ecdestroy(ec_curve *c)
+{
+  ecctx *cc = (ecctx *)c;
+  MP_DROP(cc->a);
+  MP_DROP(cc->b);
+  DESTROY(cc);
+}
+
+/* --- @ec_prime@, @ec_primeproj@ --- *
+ *
+ * Arguments:	@field *f@ = the underyling field for this elliptic curve
+ *		@mp *a, *b@ = the coefficients for this curve
+ *
+ * Returns:	A pointer to the curve.
+ *
+ * Use:		Creates a curve structure for an elliptic curve defined over
+ *		a prime field.  The @primeproj@ variant uses projective
+ *		coordinates, which can be a win.
+ */
+
+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 = MP_COPY(a);
+  cc->b = MP_COPY(b);
+  return (&cc->c);
+}
+
+static const ec_ops ec_primeops = {
+  ecdestroy, ec_idin, ec_idout, 0, ecneg, ecadd, ec_stdsub, ecdbl
+};
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
+
+int main(void)
+{
+  field *f;
+  ec_curve *c;
+  ec g = EC_INIT, d = EC_INIT;
+  mp *p, *a, *b, *r;
+
+  a = MP(-3);
+  b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
+  p = MP(6277101735386680763835789423207666416083908700390324961279);
+  r = MP(6277101735386680763835789423176059013767194773182842284081);
+
+  f = field_prime(p);
+  c = ec_prime(f, a, b);
+  
+  g.x = MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012);
+  g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
+
+  ec_mul(c, &d, &g, r);
+  MP_PRINT("d.x", d.x);
+  MP_PRINT("d.y", d.y);
+
+  ec_destroy(&d);
+  ec_destroy(&g);
+  ec_destroycurve(c);
+  F_DESTROY(f);
+
+  return (0);
 }
 
+#endif
+
 /*----- That's all, folks -------------------------------------------------*/