Test elliptic curves more thoroughly.

diff --git a/Makefile.m4 b/Makefile.m4
index 2bb62f2..ee3872a 100644 (file)
--- a/Makefile.m4
+++ b/Makefile.m4
@@ -1,6 +1,6 @@
 ## -*-m4-*-
 ##
 ## -*-m4-*-
 ##

-## $Id: Makefile.m4,v 1.68 2004/03/21 23:03:30 mdw Exp $
+## $Id: Makefile.m4,v 1.69 2004/03/23 15:19:32 mdw Exp $

 ##
 ## Makefile for Catacomb
 ##
 ##
 ## Makefile for Catacomb
 ##


@@ -29,6 +29,9 @@
 ##----- Revision history ----------------------------------------------------
 ##
 ## $Log: Makefile.m4,v $
 ##----- Revision history ----------------------------------------------------
 ##
 ## $Log: Makefile.m4,v $

+## Revision 1.69  2004/03/23 15:19:32  mdw
+## Test elliptic curves more thoroughly.
+##

 ## Revision 1.68  2004/03/21 23:03:30  mdw
 ## Distribute headers properly.
 ##
 ## Revision 1.68  2004/03/21 23:03:30  mdw
 ## Distribute headers properly.
 ##


@@ -352,7 +355,7 @@ pkginclude_HEADERS = \
        oaep.h pkcs1.h pss.h tlsprf.h sslprf.h \
        gfshare.h share.h \
        rho.h \
        oaep.h pkcs1.h pss.h tlsprf.h sslprf.h \
        gfshare.h share.h \
        rho.h \

-       field.h ec.h ec-exp.h \
+       field.h ec.h ec-exp.h ec-test.h \

        allwithsuffix(`ciphers', `cipher_modes', `.h') \
        allwithsuffix(`hashes', `hash_modes', `.h') \
        addsuffix(`cipher_modes', `-def.h') \
        allwithsuffix(`ciphers', `cipher_modes', `.h') \
        allwithsuffix(`hashes', `hash_modes', `.h') \
        addsuffix(`cipher_modes', `-def.h') \


@@ -374,7 +377,7 @@ define(`GF_SOURCES',
        `gfx.c gfx-kmul.c gfx-sqr.c gf-arith.c gf-gcd.c gfreduce.c')
 
 define(`EC_SOURCES',
        `gfx.c gfx-kmul.c gfx-sqr.c gf-arith.c gf-gcd.c gfreduce.c')
 
 define(`EC_SOURCES',

-       `field.c f-prime.c f-binpoly.c ec.c ec-prime.c ec-bin.c')
+       `field.c f-prime.c f-binpoly.c ec.c ec-prime.c ec-bin.c ec-test.c')

 
 define(`PGEN_SOURCES',
        `pfilt.c rabin.c \
 
 define(`PGEN_SOURCES',
        `pfilt.c rabin.c \


@@ -550,6 +553,7 @@ CTESTRIG(gf-gcd)
 CTESTRIG(gfreduce)
 CTESTRIG(ec-prime)
 CTESTRIG(ec-bin)
 CTESTRIG(gfreduce)
 CTESTRIG(ec-prime)
 CTESTRIG(ec-bin)

+CTESTRIG(ec-test)

 CTESTRIG(pgen)
 CTESTRIG(dsa-gen)
 CTESTRIG(dsa-sign)
 CTESTRIG(pgen)
 CTESTRIG(dsa-gen)
 CTESTRIG(dsa-sign)

diff --git a/calc/ecp.cal b/calc/ecp.cal
index 7c560c5..3834359 100644 (file)
--- a/calc/ecp.cal
+++ b/calc/ecp.cal
@@ -1,6 +1,6 @@
 /* -*-apcalc-*-
  *
 /* -*-apcalc-*-
  *

- * $Id: ecp.cal,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: ecp.cal,v 1.3 2004/03/23 15:19:32 mdw Exp $

  *
  * Testbed for elliptic curve arithmetic over prime fields
  *
  *
  * Testbed for elliptic curve arithmetic over prime fields
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ecp.cal,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ecp.cal,v $

+ * Revision 1.3  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.2  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *
  * Revision 1.2  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *


@@ -48,7 +51,6 @@
 
 obj ecp_curve { a, b, p };
 obj ecp_pt { x, y, e };
 
 obj ecp_curve { a, b, p };
 obj ecp_pt { x, y, e };

-obj ecpp_pt { x, y, z, e };

 
 /*----- Main code ---------------------------------------------------------*/
 
 
 /*----- Main code ---------------------------------------------------------*/
 


@@ -70,72 +72,6 @@ define ecp_pt(x, y, e)
   return (p);
 }
 
   return (p);
 }
 

-define ecpp_pt(p)
-{
-  local obj ecpp_pt pp;
-  if (istype(p, 1))
-    return (0);
-  pp.x = p.x;
-  pp.y = p.y;
-  pp.z = 1;
-  pp.e = p.e;
-  return (pp);
-}
-
-define ecpp_fix(pp)
-{
-  local obj ecp_pt p;
-  local e, zi, z2, z3;
-  if (istype(pp, 1) || pp.z == 0)
-    return (0);
-  e = pp.e;
-  zi = minv(pp.z, e.p);
-  z2 = zi * zi;
-  z3 = zi * z2;
-  p.x = pp.x * z2 % e.p;
-  p.y = pp.y * z3 % e.p;
-  p.e = e;
-  return (p);
-}
-
-define ecpp_dbl(a)
-{
-  local m, s, t, y2;
-  local e;
-  local obj ecpp_pt d;
-  if (istype(a, 1) || a.y == 0)
-    return (0);
-  e = a.e;
-  if (e.a % e.p == e.p - 3) {
-    m = a.z^3 % e.p;
-    m = 3 * (a.x + t4) * (a.x - t4) % e.p;
-  } else {
-    m = (3 * a.x^2 - e.a * a.z^4) % e.p;
-  }
-  d.z = 2 * a.y * a.z % e.p;
-  y2 = a.y^2 % e.p;
-  s = 4 * a.x * a.y % e.p;
-  d.x = (m^2 - 2 * s) % e.p;
-  d.y = (m * (s - d.x) - y * y2^2) % e.p;
-  d.e = e;
-  return (d);
-}
-
-define ecpp_add(a, b)
-{
-  if (a == 0)
-    d = b;
-  else if (b == 0)
-    d = a;
-  else if (!istype(a, b))
-    quit "bad type arguments to ecp_pt_add";
-  else if (a.e != b.e)
-    quit "points from different curves in ecp_pt_add";
-  else {
-    e = a.e;
-    
-}
-

 define ecp_pt_print(a)
 {
   print "(" : a.x : ", " : a.y : ")" :;
 define ecp_pt_print(a)
 {
   print "(" : a.x : ", " : a.y : ")" :;

diff --git a/ec-bin.c b/ec-bin.c
index 42aaad8..a71ed2d 100644 (file)
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: ec-bin.c,v 1.3 2004/03/22 02:19:09 mdw Exp $
+ * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $

  *
  * Arithmetic for elliptic curves over binary fields
  *
  *
  * Arithmetic for elliptic curves over binary fields
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-bin.c,v $
 /*----- 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
  * 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


@@ -82,8 +85,33 @@ static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
 
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {
 
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {

-  /* write me */
-  return (0);
+  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);
+  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$% */
+    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)
 }
 
 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)


@@ -306,7 +334,7 @@ static int eccheck(ec_curve *c, const ec *p)
   u = F_ADD(f, u, u, v);
   v = F_SQR(f, v, p->y);
   u = F_ADD(f, u, u, v);
   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);
   mp_drop(u);
   mp_drop(v);
   return (rc);


@@ -369,12 +397,12 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b)
 
 static const ec_ops ec_binops = {
   ecdestroy, ec_idin, ec_idout, ec_idfix,
 
 static const ec_ops ec_binops = {
   ecdestroy, ec_idin, ec_idout, ec_idfix,

-  0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck

 };
 
 static const ec_ops ec_binprojops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,
 };
 
 static const ec_ops ec_binprojops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,

-  0, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck

 };
 
 /*----- Test rig ----------------------------------------------------------*/
 };
 
 /*----- Test rig ----------------------------------------------------------*/


@@ -394,16 +422,16 @@ int main(int argc, char *argv[])
   printf("ec-bin: ");
   fflush(stdout);
   a = MP(1);
   printf("ec-bin: ");
   fflush(stdout);
   a = MP(1);

-  b = MP(0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad);
-  p = MP(0x20000000000000000000000000000000000000004000000000000000001);
+  b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f);
+  p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001);

   r =
   r =

-  MP(6901746346790563787434755862277025555839812737345013555379383634485462);
+  MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770);

 
   f = field_binpoly(p);
   c = ec_binproj(f, a, b);
   
 
   f = field_binpoly(p);
   c = ec_binproj(f, a, b);
   

-  g.x = MP(0x0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b);
-  g.y = MP(0x1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052);
+  g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7);
+  g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706);

 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);
 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);

diff --git a/ec-prime.c b/ec-prime.c
index 827c0f2..5c6297f 100644 (file)
--- a/ec-prime.c
+++ b/ec-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: ec-prime.c,v 1.5 2004/03/22 02:19:10 mdw Exp $
+ * $Id: ec-prime.c,v 1.6 2004/03/23 15:19:32 mdw Exp $

  *
  * Elliptic curves over prime fields
  *
  *
  * Elliptic curves over prime fields
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-prime.c,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-prime.c,v $

+ * Revision 1.6  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.5  2004/03/22 02:19:10  mdw
  * Rationalise the sliding-window threshold.  Drop guarantee that right
  * arguments to EC @add@ are canonical, and fix up projective implementations
  * Revision 1.5  2004/03/22 02:19:10  mdw
  * Rationalise the sliding-window threshold.  Drop guarantee that right
  * arguments to EC @add@ are canonical, and fix up projective implementations


@@ -427,17 +430,17 @@ extern ec_curve *ec_primeproj(field *f, mp *a, mp *b)
 
 static const ec_ops ec_primeops = {
   ecdestroy, ec_idin, ec_idout, ec_idfix,
 
 static const ec_ops ec_primeops = {
   ecdestroy, ec_idin, ec_idout, ec_idfix,

-  0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck

 };
 
 static const ec_ops ec_primeprojops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,
 };
 
 static const ec_ops ec_primeprojops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,

-  0, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck

 };
 
 static const ec_ops ec_primeprojxops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,
 };
 
 static const ec_ops ec_primeprojxops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,

-  0, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
+  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck

 };
 
 /*----- Test rig ----------------------------------------------------------*/
 };
 
 /*----- Test rig ----------------------------------------------------------*/

diff --git a/ec-test.c b/ec-test.c
new file mode 100644 (file)
index 0000000..6d42a70
--- /dev/null
+++ b/ec-test.c
@@ -0,0 +1,418 @@
+/* -*-c-*-
+ *
+ * $Id: ec-test.c,v 1.1 2004/03/23 15:19:32 mdw Exp $
+ *
+ * Code for testing elliptic-curve stuff
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------* 
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------* 
+ *
+ * $Log: ec-test.c,v $
+ * Revision 1.1  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <assert.h>
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <mLib/alloc.h>
+#include <mLib/testrig.h>
+#include <mLib/sub.h>
+
+#include "ec.h"
+#include "ec-test.h"
+
+/*----- Cardboard cut-out elliptic curve ----------------------------------*/
+
+typedef struct ecctx {
+  ec_curve c;
+  unsigned long magic;
+  char *name;
+  ec_curve *real;
+} ecctx;
+
+#define MAGIC 0x3a1f0b07
+
+static void ecDESTROY(ec_curve *cc)
+{
+  ecctx *c = (ecctx *)cc;
+  xfree(c->name);
+  ec_destroycurve(c->real);
+  DESTROY(c);
+}
+
+#define UNOP(OP)                                                       \
+  static ec *ec##OP(ec_curve *cc, ec *d, const ec *p) {                        \
+    ecctx *c = (ecctx *)cc;                                            \
+    return (EC_##OP(c->real, d, p));                                   \
+  }
+
+#define BINOP(OP)                                                      \
+  static ec *ec##OP(ec_curve *cc, ec *d, const ec *p, const ec *q) {   \
+    ecctx *c = (ecctx *)cc;                                            \
+    return (EC_##OP(c->real, d, p, q));                                        \
+  }
+
+UNOP(IN)
+UNOP(OUT)
+UNOP(FIX)
+UNOP(NEG)
+UNOP(DBL)
+BINOP(ADD)
+BINOP(SUB)
+
+#undef UNOP
+#undef BINOP
+
+static ec *ecFIND(ec_curve *cc, ec *d, mp *x)
+{
+  ecctx *c = (ecctx *)cc;
+  return (EC_FIND(c->real, d, x));
+}
+
+static int ecCHECK(ec_curve *cc, const ec *p)
+{
+  ecctx *c = (ecctx *)cc;
+  return (EC_CHECK(c->real, p));
+}
+
+static ec_ops ecops = {
+  ecDESTROY, ecIN, ecOUT, ecFIX,
+  ecFIND, ecNEG, ecADD, ecSUB, ecDBL, ecCHECK
+};
+
+static ec_curve *ec_cutout(ec_curve *real, const char *name)
+{
+  ecctx *c = CREATE(ecctx);
+  c->c.f = real->f;
+  c->c.ops = &ecops;
+  c->magic = MAGIC;
+  c->name = xstrdup(name);
+  c->real = real;
+  return (&c->c);
+}
+
+static const char *ec_name(ec_curve *cc)
+{
+  ecctx *c = (ecctx *)cc;
+  assert(c->magic == MAGIC);
+  return (c->name);
+}
+
+/*----- Test field types --------------------------------------------------*
+ *
+ * Really lazy parser.  Sorry.
+ */
+
+static void skipws(const char **p)
+{
+  while (isspace((unsigned char)**p)) (*p)++;
+}
+
+static void ckchar(const char **p, int ch)
+{ skipws(p); if (**p == ch) (*p)++; }
+
+static void ckend(const char **p)
+{
+  skipws(p);
+  if (**p) {
+    fprintf(stderr, "syntax error: junk at end of line\n");
+    abort();
+  }
+}
+
+static int ckstring(const char **p, const char **s)
+{
+  int i;
+  size_t n;
+
+  skipws(p);
+  for (i = 0; s[i]; i++) {
+    n = strlen(s[i]);
+    if (strncmp(*p, s[i], n) == 0 && !isalnum((unsigned char)(*p)[n])) {
+      *p += n;
+      return (i);
+    }
+  }
+  fprintf(stderr, "syntax error: couldn't recognize keyword\n");
+  abort();
+}
+
+static mp *getmp(const char **p)
+{
+  char *q;
+  mp *m;
+  skipws(p);
+  m = mp_readstring(MP_NEW, *p, &q, 0);
+  if (!m || isalnum((unsigned char)*q)) {
+    fprintf(stderr, "syntax error: bad number\n");
+    abort();
+  }
+  *p = q;
+  return (m);
+}
+
+static void ecvcvt(const char *buf, dstr *d)
+{
+  field *f;
+  ec_curve *v;
+  mp *m, *n;
+  const char *p = buf;
+  int i;
+
+  static const char *fnames[] = {
+    "prime", "binpoly", 0
+  };
+  static const char *ecnames[] = {
+    "prime", "primeproj", "bin", "binproj", 0
+  };
+
+  switch (i = ckstring(&p, fnames), ckchar(&p, ':'), i) {
+    case 0: m = getmp(&p); f = field_prime(m); mp_drop(m); break;
+    case 1: m = getmp(&p); f = field_binpoly(m); mp_drop(m); break;
+    default: abort();
+  }
+  ckchar(&p, '/');
+
+  switch (i = ckstring(&p, ecnames), ckchar(&p, ':'), i) {
+    case 0: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
+      v = ec_prime(f, m, n); mp_drop(m); mp_drop(n); break;
+    case 1: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
+      v = ec_primeproj(f, m, n); mp_drop(m); mp_drop(n); break;
+    case 2: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
+      v = ec_bin(f, m, n); mp_drop(m); mp_drop(n); break;
+    case 3: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
+      v = ec_binproj(f, m, n); mp_drop(m); mp_drop(n); break;
+    default: abort();
+  }
+  ckend(&p);
+
+  dstr_ensure(d, sizeof(v));
+  *(ec_curve **)d->buf = ec_cutout(v, buf);
+  d->len += sizeof(v);
+}
+
+static void ecvdump(dstr *d, FILE *fp)
+{
+  ec_curve *v = *(ec_curve **)d->buf;
+  fprintf(fp, "%s", ec_name(v));
+}
+
+test_type type_ecurve = { ecvcvt, ecvdump };
+
+static void eccvt(const char *p, dstr *d)
+{
+  ec *a;
+
+  dstr_ensure(d, sizeof(ec));
+  a = (ec *)d->buf;
+  d->len += sizeof(ec);
+  ec_create(a);
+  skipws(&p);
+  if (strcmp(p, "inf") == 0)
+    EC_SETINF(a);
+  else
+  { a->x = getmp(&p); ckchar(&p, ','); a->y = getmp(&p); ckend(&p); }
+}
+
+static void ecdodump(ec *a, FILE *fp)
+{
+  if (EC_ATINF(a))
+    fputs("inf", fp);
+  else {
+    fputs("0x", fp); 
+    mp_writefile(a->x, fp, 16);
+    fputs(", 0x", fp);
+    mp_writefile(a->y, fp, 16);
+  }
+}
+
+static void ecdump(dstr *d, FILE *fp)
+{
+  ec *a = (ec *)d->buf;
+  ecdodump(a, fp);
+}
+
+test_type type_ec = { eccvt, ecdump };
+
+/*----- Testing elliptic curve functionality ------------------------------*/
+
+#ifdef TEST_RIG
+
+static void ecdestroy(ec_curve *c)
+{
+  field *f = c->f;
+  ec_destroycurve(c);
+  F_DESTROY(f);
+}
+
+#define UNOP(op)                                                       \
+  static int v##op(dstr v[])                                           \
+  {                                                                    \
+    ec_curve *e = *(ec_curve **)v[0].buf;                              \
+    ec *a = (ec *)v[1].buf;                                            \
+    ec *r = (ec *)v[2].buf;                                            \
+    ec c = EC_INIT;                                                    \
+    int ok = 1;                                                                \
+    ec_##op(e, &c, a);                                                 \
+    if (!EC_EQ(r, &c)) {                                               \
+      fprintf(stderr, #op "failed");                                   \
+      fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);      \
+      fprintf(stderr, "\n    a = "); ecdodump(a, stderr);              \
+      fprintf(stderr, "\n    r = "); ecdodump(r, stderr);              \
+      fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);             \
+      fprintf(stderr, "\n");                                           \
+      ok = 0;                                                          \
+    }                                                                  \
+    EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c);                      \
+    ecdestroy(e);                                                      \
+    return (ok);                                                       \
+  }
+
+#define BINOP(op)                                                      \
+  static int v##op(dstr v[])                                           \
+  {                                                                    \
+    ec_curve *e = *(ec_curve **)v[0].buf;                              \
+    ec *a = (ec *)v[1].buf;                                            \
+    ec *b = (ec *)v[2].buf;                                            \
+    ec *r = (ec *)v[3].buf;                                            \
+    ec c = EC_INIT;                                                    \
+    int ok = 1;                                                                \
+    ec_##op(e, &c, a, b);                                              \
+    if (!EC_EQ(r, &c)) {                                               \
+      fprintf(stderr, #op "failed");                                   \
+      fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);      \
+      fprintf(stderr, "\n    a = "); ecdodump(a, stderr);              \
+      fprintf(stderr, "\n    b = "); ecdodump(b, stderr);              \
+      fprintf(stderr, "\n    r = "); ecdodump(r, stderr);              \
+      fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);             \
+      fprintf(stderr, "\n");                                           \
+      ok = 0;                                                          \
+    }                                                                  \
+    EC_DESTROY(a); EC_DESTROY(b); EC_DESTROY(r); EC_DESTROY(&c);       \
+    ecdestroy(e);                                                      \
+    return (ok);                                                       \
+  }
+
+UNOP(neg)
+UNOP(dbl)
+BINOP(add)
+BINOP(sub)
+
+static int vcheck(dstr v[])
+{
+  ec_curve *e = *(ec_curve **)v[0].buf;
+  ec *a = (ec *)v[1].buf;
+  int r = *(int *)v[2].buf;
+  int c;
+  int ok = 1;
+  c = ec_check(e, a);
+  if (r != c) {
+    fprintf(stderr, "check failed");
+    fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
+    fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
+    fprintf(stderr, "\n    r = %d", r);
+    fprintf(stderr, "\n    c = %d", c); 
+    fprintf(stderr, "\n");
+    ok = 0;
+  }
+  EC_DESTROY(a);
+  ecdestroy(e);
+  return (ok);
+}
+
+static int vmul(dstr v[])
+{
+  ec_curve *e = *(ec_curve **)v[0].buf;
+  ec *a = (ec *)v[1].buf;
+  mp *n = *(mp **)v[2].buf;
+  ec *r = (ec *)v[3].buf;
+  ec c = EC_INIT;
+  int ok = 1;
+  ec_mul(e, &c, a, n);
+  if (!EC_EQ(r, &c)) {
+    fprintf(stderr, "mul failed");
+    fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
+    fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
+    fprintf(stderr, "\n    n = "); mp_writefile(n, stderr, 10);
+    fprintf(stderr, "\n    r = "); ecdodump(r, stderr);
+    fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);
+    fprintf(stderr, "\n");
+    ok = 0;
+  }
+  EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); MP_DROP(n);
+  ecdestroy(e);
+  return (ok);
+}
+
+static int vfind(dstr v[])
+{
+  ec_curve *e = *(ec_curve **)v[0].buf;
+  mp *x = *(mp **)v[1].buf;
+  ec *r = (ec *)v[2].buf;
+  ec c = EC_INIT;
+  int ok = 1;
+  if (!ec_find(e, &c, x)) EC_SETINF(&c);
+  if (!EC_EQ(r, &c)) {
+    fprintf(stderr, "find failed");
+    fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
+    fprintf(stderr, "\n    x = "); mp_writefile(x, stderr, 16);
+    fprintf(stderr, "\n    r = "); ecdodump(r, stderr);
+    fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);
+    fprintf(stderr, "\n");
+    ok = 0;
+  }
+  MP_DROP(x); EC_DESTROY(r); EC_DESTROY(&c);
+  ecdestroy(e);
+  return (ok);
+}
+
+static test_chunk tests[] = {
+  { "neg", vneg, { &type_ecurve, &type_ec, &type_ec } },
+  { "dbl", vdbl, { &type_ecurve, &type_ec, &type_ec } },
+  { "add", vadd, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
+  { "sub", vsub, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
+  { "mul", vmul, { &type_ecurve, &type_ec, &type_mp, &type_ec } },
+  { "check", vcheck, { &type_ecurve, &type_ec, &type_int } },
+  { "find", vfind, { &type_ecurve, &type_mp, &type_ec } },
+  { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+  sub_init();
+  test_run(argc, argv, tests, SRCDIR "/tests/ec");
+  return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/

diff --git a/ec-test.h b/ec-test.h
new file mode 100644 (file)
index 0000000..a4ca0d7
--- /dev/null
+++ b/ec-test.h
@@ -0,0 +1,63 @@
+/* -*-c-*-
+ *
+ * $Id: ec-test.h,v 1.1 2004/03/23 15:19:32 mdw Exp $
+ *
+ * Elliptic curve test functions
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------* 
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------* 
+ *
+ * $Log: ec-test.h,v $
+ * Revision 1.1  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *
+ */
+
+#ifndef CATACOMB_EC_TEST_H
+#define CATACOMB_EC_TEST_H
+
+#ifdef __cplusplus
+  extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <mLib/testrig.h>
+
+#ifndef CATACOMB_EC_H
+#  include "ec.h"
+#endif
+
+/*----- Test vector types -------------------------------------------------*/
+
+extern test_type type_ecurve, type_ec;
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+  }
+#endif
+
+#endif

diff --git a/ec.c b/ec.c
index c95333f..ac00c92 100644 (file)
--- a/ec.c
+++ b/ec.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: ec.c,v 1.5 2004/03/21 22:52:06 mdw Exp $
+ * $Id: ec.c,v 1.6 2004/03/23 15:19:32 mdw Exp $

  *
  * Elliptic curve definitions
  *
  *
  * Elliptic curve definitions
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.c,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.c,v $

+ * Revision 1.6  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.5  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *
  * Revision 1.5  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *


@@ -117,6 +120,16 @@ ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
 
 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
 
 
 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
 

+/* --- @ec_eq@ --- *
+ *
+ * Arguments:  @const ec *p, *q@ = two points
+ *
+ * Returns:    Nonzero if the points are equal.  Compares external-format
+ *             points.
+ */
+
+int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }
+

 /*----- Standard curve operations -----------------------------------------*/
 
 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
 /*----- Standard curve operations -----------------------------------------*/
 
 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *


@@ -348,7 +361,7 @@ ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
   ec pp, qq;
   EC_IN(c, &pp, p);
   EC_IN(c, &qq, q);
   ec pp, qq;
   EC_IN(c, &pp, p);
   EC_IN(c, &qq, q);

-  EC_SUB(c, d, &qq, &qq);
+  EC_SUB(c, d, &pp, &qq);

   EC_OUT(c, d, d);
   EC_DESTROY(&pp);
   EC_DESTROY(&qq);
   EC_OUT(c, d, d);
   EC_DESTROY(&pp);
   EC_DESTROY(&qq);


@@ -396,6 +409,26 @@ int ec_check(ec_curve *c, const ec *p)
   return (rc);
 }
 
   return (rc);
 }
 

+/* --- @ec_rand@ --- *
+ *
+ * Arguments:  @ec_curve *c@ = pointer to an elliptic curve
+ *             @ec *d@ = pointer to the destination point
+ *             @grand *r@ = random number source
+ *
+ * Returns:    The destination @d@.
+ *
+ * Use:                Finds a random point on the given curve.
+ */
+
+ec *ec_rand(ec_curve *c, ec *d, grand *r)
+{
+  mp *x = MP_NEW;
+  do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
+  mp_drop(x);
+  if (grand_range(r, 2)) EC_NEG(c, d, d);
+  return (EC_OUT(c, d, d));    
+}
+

 /* --- @ec_imul@, @ec_mul@ --- *
  *
  * Arguments:  @ec_curve *c@ = pointer to an elliptic curve
 /* --- @ec_imul@, @ec_mul@ --- *
  *
  * Arguments:  @ec_curve *c@ = pointer to an elliptic curve

diff --git a/ec.h b/ec.h
index 680bf9c..d398f4a 100644 (file)
--- a/ec.h
+++ b/ec.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: ec.h,v 1.6 2004/03/22 02:19:10 mdw Exp $
+ * $Id: ec.h,v 1.7 2004/03/23 15:19:32 mdw Exp $

  *
  * Elliptic curve definitions
  *
  *
  * Elliptic curve definitions
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.h,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.h,v $

+ * Revision 1.7  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.6  2004/03/22 02:19:10  mdw
  * Rationalise the sliding-window threshold.  Drop guarantee that right
  * arguments to EC @add@ are canonical, and fix up projective implementations
  * Revision 1.6  2004/03/22 02:19:10  mdw
  * Rationalise the sliding-window threshold.  Drop guarantee that right
  * arguments to EC @add@ are canonical, and fix up projective implementations


@@ -235,6 +238,22 @@ extern ec *ec_setinf(ec */*p*/);
 
 extern ec *ec_copy(ec */*d*/, const ec */*p*/);
 
 
 extern ec *ec_copy(ec */*d*/, const ec */*p*/);
 

+/* --- @ec_eq@ --- *
+ *
+ * Arguments:  @const ec *p, *q@ = two points
+ *
+ * Returns:    Nonzero if the points are equal.  Compares external-format
+ *             points.
+ */
+
+#define EC_EQ(p, q)                                                    \
+    ((EC_ATINF(p) && EC_ATINF(q)) ||                                   \
+     (!EC_ATINF(p) && !EC_ATINF(q) &&                                  \
+      MP_EQ((p)->x, (q)->x) &&                                         \
+      MP_EQ((p)->y, (q)->y)))
+
+extern int ec_eq(const ec *p, const ec *q);
+

 /*----- Interesting arithmetic --------------------------------------------*/
 
 /* --- @ec_find@ --- *
 /*----- Interesting arithmetic --------------------------------------------*/
 
 /* --- @ec_find@ --- *


@@ -253,6 +272,19 @@ extern ec *ec_copy(ec */*d*/, const ec */*p*/);
 
 extern ec *ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/);
 
 
 extern ec *ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/);
 

+/* --- @ec_rand@ --- *
+ *
+ * Arguments:  @ec_curve *c@ = pointer to an elliptic curve
+ *             @ec *d@ = pointer to the destination point
+ *             @grand *r@ = random number source
+ *
+ * Returns:    The destination @d@.
+ *
+ * Use:                Finds a random point on the given curve.
+ */
+
+extern ec *ec_rand(ec_curve */*c*/, ec */*d*/, grand */*r*/);
+

 /* --- @ec_neg@ --- *
  *
  * Arguments:  @ec_curve *c@ = pointer to an elliptic curve
 /* --- @ec_neg@ --- *
  *
  * Arguments:  @ec_curve *c@ = pointer to an elliptic curve

diff --git a/f-binpoly.c b/f-binpoly.c
index 463dbb2..1da5d12 100644 (file)
--- a/f-binpoly.c
+++ b/f-binpoly.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: f-binpoly.c,v 1.3 2004/03/23 12:08:26 mdw Exp $
+ * $Id: f-binpoly.c,v 1.4 2004/03/23 15:19:32 mdw Exp $

  *
  * Binary fields with polynomial basis representation
  *
  *
  * Binary fields with polynomial basis representation
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: f-binpoly.c,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: f-binpoly.c,v $

+ * Revision 1.4  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.3  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *
  * Revision 1.3  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *


@@ -68,7 +71,7 @@ static void fdestroy(field *ff)
   DESTROY(f);
 }
 
   DESTROY(f);
 }
 

-static mp *frand(field *ff, grand *r, mp *d)
+static mp *frand(field *ff, mp *d, grand *r)

 {
   fctx *f = (fctx *)ff;
   return (mprand(d, mp_octets(f->r.p) - 1, r, 0));
 {
   fctx *f = (fctx *)ff;
   return (mprand(d, mp_octets(f->r.p) - 1, r, 0));


@@ -126,6 +129,7 @@ static mp *fquadsolve(field *ff, mp *d, mp *x)
 /* --- Field operations table --- */
 
 static field_ops fops = {
 /* --- Field operations table --- */
 
 static field_ops fops = {

+  FTY_BINARY, "binpoly",

   fdestroy, frand,
   freduce, field_id,
   fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt,
   fdestroy, frand,
   freduce, field_id,
   fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt,

diff --git a/f-prime.c b/f-prime.c
index 5ab4204..08ed300 100644 (file)
--- a/f-prime.c
+++ b/f-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: f-prime.c,v 1.5 2004/03/23 12:08:26 mdw Exp $
+ * $Id: f-prime.c,v 1.6 2004/03/23 15:19:32 mdw Exp $

  *
  * Prime fields with Montgomery arithmetic
  *
  *
  * Prime fields with Montgomery arithmetic
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: f-prime.c,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: f-prime.c,v $

+ * Revision 1.6  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.5  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *
  * Revision 1.5  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *


@@ -218,6 +221,7 @@ static mp *fhlv(field *ff, mp *d, mp *x)
 /* --- Field operations table --- */
 
 static field_ops fops = {
 /* --- Field operations table --- */
 
 static field_ops fops = {

+  FTY_PRIME, "prime",

   fdestroy, frand,
   fin, fout,
   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
   fdestroy, frand,
   fin, fout,
   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,

diff --git a/field.h b/field.h
index 909332f..db27e63 100644 (file)
--- a/field.h
+++ b/field.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: field.h,v 1.5 2004/03/23 12:08:26 mdw Exp $
+ * $Id: field.h,v 1.6 2004/03/23 15:19:32 mdw Exp $

  *
  * Definitions for field arithmetic
  *
  *
  * Definitions for field arithmetic
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: field.h,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: field.h,v $

+ * Revision 1.6  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.5  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *
  * Revision 1.5  2004/03/23 12:08:26  mdw
  * Random field-element selection.
  *


@@ -77,8 +80,18 @@ typedef struct field {
   mp *zero, *one;                      /* Identities in the field */
 } field;
 
   mp *zero, *one;                      /* Identities in the field */
 } field;
 

+enum {
+  FTY_PRIME,
+  FTY_BINARY
+};
+

 typedef struct field_ops {
 
 typedef struct field_ops {
 

+  /* --- General information --- */
+
+  unsigned ty;                         /* What kind of field this is */
+  const char *name;                    /* Human-readable name string */
+

   /* --- Universal operations --- */
 
   void (*destroy)(field */*f*/);
   /* --- Universal operations --- */
 
   void (*destroy)(field */*f*/);


@@ -110,7 +123,11 @@ typedef struct field_ops {
 
 } field_ops;
 
 
 } field_ops;
 

+#define F_TYPE(f)              (f)->ops->ty
+#define F_NAME(f)              (f)->ops->name
+

 #define F_DESTROY(f)           (f)->ops->destroy((f))
 #define F_DESTROY(f)           (f)->ops->destroy((f))

+#define F_RAND(f, d, r)                (f)->ops->rand((f), (d), (r))

 
 #define F_IN(f, d, x)          (f)->ops->in((f), (d), (x))
 #define F_OUT(f, d, x)         (f)->ops->out((f), (d), (x))
 
 #define F_IN(f, d, x)          (f)->ops->in((f), (d), (x))
 #define F_OUT(f, d, x)         (f)->ops->out((f), (d), (x))

diff --git a/gfreduce.c b/gfreduce.c
index 819c276..929c46c 100644 (file)
--- a/gfreduce.c
+++ b/gfreduce.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: gfreduce.c,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: gfreduce.c,v 1.3 2004/03/23 15:19:32 mdw Exp $

  *
  * Efficient reduction modulo sparse binary polynomials
  *
  *
  * Efficient reduction modulo sparse binary polynomials
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: gfreduce.c,v $
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: gfreduce.c,v $

+ * Revision 1.3  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *

  * Revision 1.2  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *
  * Revision 1.2  2004/03/21 22:52:06  mdw
  * Merge and close elliptic curve branch.
  *


@@ -440,7 +443,7 @@ mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
   }
   MP_DROP(t);
   MP_DROP(x);
   }
   MP_DROP(t);
   MP_DROP(x);

-  d->v[0] &= ~(mpw)1;
+  if (d) d->v[0] &= ~(mpw)1;

   return (d);
 }
 
   return (d);
 }
 

diff --git a/tests/ec b/tests/ec
new file mode 100644 (file)
index 0000000..3831c53
--- /dev/null
+++ b/tests/ec
@@ -0,0 +1,291 @@
+# $Id: ec,v 1.1 2004/03/23 15:19:32 mdw Exp $
+#
+# Elliptic curve tests
+
+check {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    0;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794810"
+    -1;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee"
+    0;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18801f4ff0afd82ff1411, 
+      0xdccf19d3e76abfa05d529c07575f54c94fa5fc9f3decc246"
+    0;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    0;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794810"
+    -1;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee"
+    0;
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1"
+    0;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f0"
+    -1;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    0;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1"
+    0;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f0"
+    -1;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    0;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0591168d4994637e8343e36, 
+      0x7fa8423c5ae194b56cdf21998ad8a721ef1201b8c"
+    0;
+}
+
+find {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1011 inf;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    0x188da80eb03090f67cbf20eb43a18801f4ff0afd82ff1411
+    "0x188da80eb03090f67cbf20eb43a18801f4ff0afd82ff1411, 
+      0xdccf19d3e76abfa05d529c07575f54c94fa5fc9f3decc246";
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    0x3f0eba16286a2d57ea0991168d4994637e8343e36
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    0x310eba16386a2d57ea0591168d4997637e8745e36 inf;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    0x3f0eba16286a2d57ea0591168d4994637e8343e36
+    "0x3f0eba16286a2d57ea0591168d4994637e8343e36, 
+      0x7fa8423c5ae194b56cdf21998ad8a721ef1201b8c";
+}
+
+neg {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee";
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1";
+}
+
+dbl {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c";
+}
+
+add {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd";
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c"
+    "0x634000577f86aa315009d6f9b906691f6edd691fe,
+      0x235a3db7a94446301e666cafea5e12cb331f4a140";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c"
+    "0x634000577f86aa315009d6f9b906691f6edd691fe,
+      0x235a3db7a94446301e666cafea5e12cb331f4a140";
+}
+
+sub {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+    "0x76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da,
+       0x782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+    "0xdafebf5828783f2ad35534631588a3f629a70fb16982a888,
+       0xdd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab";
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x634000577f86aa315009d6f9b906691f6edd691fe,
+      0x235a3db7a94446301e666cafea5e12cb331f4a140"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x634000577f86aa315009d6f9b906691f6edd691fe,
+      0x235a3db7a94446301e666cafea5e12cb331f4a140"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
+      0x49ed3be7f510e30e2462c517ad39038e493fc573c";
+}
+
+mul {
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+     6277101735386680763835789423176059013767194773182842284080
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+        0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     prime: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+     6277101735386680763835789423176059013767194773182842284081
+     inf;
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+     6277101735386680763835789423176059013767194773182842284080
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+        0xf8e6d46a003725879cefee1294db32298c06885ee186b7ee";
+  "prime: 6277101735386680763835789423207666416083908700390324961279
+     primeproj: -3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"
+     "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+       0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
+     6277101735386680763835789423176059013767194773182842284081
+     inf;
+
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    5846006549323611672814742442876390689256843201586
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0xd51fbc6c71a0094fa2cdd545b11c5c0c797324f1";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    bin: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    5846006549323611672814742442876390689256843201587
+    inf;
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    5846006549323611672814742442876390689256843201586
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0xd51fbc6c71a0094fa2cdd545b11c5c0c797324f1";
+  "binpoly: 0x800000000000000000000000000000000000000c9
+    binproj: 1, 0x20a601907b8c953ca1481eb10512f78744a3205fd"
+    "0x3f0eba16286a2d57ea0991168d4994637e8343e36,
+      0x325f41d0ef702dc310254c42d65851a3b91471ac7"
+    5846006549323611672814742442876390689256843201587
+    inf;
+}

diff --git a/tests/gfreduce b/tests/gfreduce
index 806ec28..2688a0c 100644 (file)
--- a/tests/gfreduce
+++ b/tests/gfreduce
@@ -1,4 +1,4 @@
-# $Id: gfreduce,v 1.2 2004/03/21 22:52:06 mdw Exp $
+# $Id: gfreduce,v 1.3 2004/03/23 15:19:32 mdw Exp $

 #
 # Test efficient polynomial reduction
 
 #
 # Test efficient polynomial reduction
 


@@ -58,4 +58,7 @@ quadsolve {
   0x10000000000000000000000000000000000000000003
    0x3b818b447e90713da04f13c3b07cb5e2681d08e4700
    0x27aa17c97dfa80bbdef9f91b243c6e6ddba1a223cac;
   0x10000000000000000000000000000000000000000003
    0x3b818b447e90713da04f13c3b07cb5e2681d08e4700
    0x27aa17c97dfa80bbdef9f91b243c6e6ddba1a223cac;

+  0x800000000000000000000000000000000000000c9
+    0x158fe327cc763a2fd7371ee80641ed1871a32aaa8
+    0x29ab0d7da05ffc3f1b3f97ac10e2092694aadbb7c;

 }
 }