From dbfee00a86609283c4633df870692be3db9bc5e4 Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Tue, 10 Jun 2003 13:43:53 +0000
Subject: [PATCH] Simple (non-projective) curves over prime fields now seem to
 work.

---
 .gdbinit     | 34 ++++++++++++++++++++++++++++++++++
 Makefile.m4  | 17 +++++++++++++----
 calc/ecp.cal | 36 ++++++++++++++++++++++++++++++++++--
 configure.in |  7 +++++--
 ec-prime.c   | 34 +++++++++++++++++++++++++---------
 ec.c         | 47 ++++++++++++++++++++++++++++++++++++++++++++++-
 ec.h         |  9 ++++++---
 f-prime.c    | 35 ++++++++++++++++++++++++++++-------
 field.c      |  8 ++++++--
 9 files changed, 197 insertions(+), 30 deletions(-)
 create mode 100644 .gdbinit

diff --git a/.gdbinit b/.gdbinit
new file mode 100644
index 0000000..daa7ee3
--- /dev/null
+++ b/.gdbinit
@@ -0,0 +1,34 @@
+define mp-print
+  call (void)fputs("$arg0 = ", stdout)
+  if $arg0 == 0
+    call (void)fputs("(null)", stdout)
+  else
+    call (void)mp_writefile($arg0, stdout, 10)
+  end
+  call (void)putchar('\n')
+end
+
+define mp-printr
+  call (void)fputs("$arg0 = ", stdout)
+  if $arg0 == 0
+    call (void)fputs("(null)", stdout)
+  else
+    if $arg1 == 16
+      call (void)fputs("0x", stdout)
+    else
+      if $arg1 == 8
+        call (void)fputs("0", stdout)
+      else
+        if $arg1 != 10
+          call (void)fputs("$arg1", stdout)
+        end
+      end
+    end
+    call (void)mp_writefile($arg0, stdout, $arg1)
+  end
+  call (void)putchar('\n')
+end
+
+document mp-print
+Print a Catacomb MP as a base-10 integer to stdout.
+end
diff --git a/Makefile.m4 b/Makefile.m4
index f2422f1..8185765 100644
--- a/Makefile.m4
+++ b/Makefile.m4
@@ -1,6 +1,6 @@
 ## -*-makefile-*-
 ##
-## $Id: Makefile.m4,v 1.60 2003/05/16 01:12:37 mdw Exp $
+## $Id: Makefile.m4,v 1.60.2.1 2003/06/10 13:43:53 mdw Exp $
 ##
 ## Makefile for Catacomb
 ##
@@ -29,6 +29,9 @@
 ##----- Revision history ----------------------------------------------------
 ##
 ## $Log: Makefile.m4,v $
+## Revision 1.60.2.1  2003/06/10 13:43:53  mdw
+## Simple (non-projective) curves over prime fields now seem to work.
+##
 ## Revision 1.60  2003/05/16 01:12:37  mdw
 ## Ship `rc2-tab.h' and `skipjack-tab.h'.
 ##
@@ -301,7 +304,7 @@ BUILT_SOURCES = \
 
 lib_LTLIBRARIES = libcatacomb.la
 
-libcatacomb_la_LDFLAGS = -version-info 2:0:0
+libcatacomb_la_LDFLAGS = -version-info 3:0:1
 ## Middle number is the patchlevel.  Final number is the minor version.  The
 ## difference between the first and last numbers is major version.
 
@@ -311,7 +314,8 @@ pkginclude_HEADERS = \
 	lcrand.h fibrand.h rc4.h seal.h rand.h noise.h fipstest.h maurer.h \
 	key.h key-data.h passphrase.h pixie.h lmem.h \
 	mpx.h bitops.h mpw.h mpscan.h mparena.h mp.h mptext.h mpint.h \
-	exp.h mpbarrett.h mpmont.h mpcrt.h mprand.h mpmul.h \
+	exp.h mpbarrett.h mpbarrett-exp.h mpmont.h mpmont-exp.h \
+	mpcrt.h mprand.h mpmul.h \
 	gfx.h \
 	primetab.h pfilt.h rabin.h \
 	pgen.h prim.h strongprime.h limlee.h keycheck.h \
@@ -319,6 +323,7 @@ pkginclude_HEADERS = \
 	oaep.h pkcs1.h pss.h tlsprf.h sslprf.h \
 	gfshare.h share.h \
 	rho.h \
+	field.h ec.h ec-exp.h \
 	allwithsuffix(`ciphers', `cipher_modes', `.h') \
 	allwithsuffix(`hashes', `hash_modes', `.h') \
 	addsuffix(`cipher_modes', `-def.h') \
@@ -334,11 +339,14 @@ define(`MP_SOURCES',
 	mpbarrett.c mpbarrett-mexp.c mpbarrett-exp.h \
 	mpmont.c mpmont-mexp.c mpmont-exp.h \
 	rho.c \
-	GF_SOURCES PGEN_SOURCES')
+	GF_SOURCES PGEN_SOURCES EC_SOURCES')
 
 define(`GF_SOURCES',
 	`gfx.c gfx-kmul.c gfx-sqr.c')
 
+define(`EC_SOURCES',
+	`field.c f-prime.c ec.c ec-prime.c')
+
 define(`PGEN_SOURCES',
 	`pfilt.c rabin.c \
 	pgen.c pgen-stdev.c pgen-safe.c pgen-gcd.c prim.c strongprime.c \
@@ -504,6 +512,7 @@ CTESTRIG(mpcrt)
 CTESTRIG(mpmul)
 CTESTRIG(gfx)
 CTESTRIG(gfx-kmul)
+CTESTRIG(ec-prime)
 CTESTRIG(pgen)
 CTESTRIG(dsa-gen)
 CTESTRIG(dsa-sign)
diff --git a/calc/ecp.cal b/calc/ecp.cal
index 04971aa..82600f5 100644
--- a/calc/ecp.cal
+++ b/calc/ecp.cal
@@ -1,6 +1,6 @@
 /* -*-apcalc-*-
  *
- * $Id: ecp.cal,v 1.1 2000/10/08 16:01:37 mdw Exp $
+ * $Id: ecp.cal,v 1.1.4.1 2003/06/10 13:43:53 mdw Exp $
  *
  * Testbed for elliptic curve arithmetic over prime fields
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ecp.cal,v $
+ * Revision 1.1.4.1  2003/06/10 13:43:53  mdw
+ * Simple (non-projective) curves over prime fields now seem to work.
+ *
  * Revision 1.1  2000/10/08 16:01:37  mdw
  * Prototypes of various bits of code.
  *
@@ -96,6 +99,18 @@ define ecp_pt_add(a, b)
   return (d);
 }
 
+define ecp_pt_dbl(a)
+{
+  local e, alpha;
+  local obj ecp_pt d;
+  e = a.e;
+  alpha = (3 * a.x^2 + e.a) * minv(2 * a.y, e.p) % e.p;
+  d.x = (alpha^2 - 2 * a.x) % e.p;
+  d.y = (-a.y + alpha * (a.x - d.x)) % e.p;
+  d.e = e;
+  return (d);
+}
+
 define ecp_pt_neg(a)
 {
   local obj ecp_pt d;
@@ -105,6 +120,15 @@ define ecp_pt_neg(a)
   return (d);
 }
 
+define ecp_pt_check(a)
+{
+  local e;
+
+  e = a.e;
+  if (a.y^2 % e.p != (a.x^3 + e.a * a.x + e.b) % e.p)
+    quit "bad curve point";
+}
+
 define ecp_pt_mul(a, b)
 {
   local p, n;
@@ -124,10 +148,18 @@ define ecp_pt_mul(a, b)
     if (n & 1)
       d += p;
     n >>= 1;
-    p += p;
+    p = ecp_pt_dbl(p);
   }
   return (d);
 }
 
+/*----- FIPS186-2 standard curves -----------------------------------------*/
+
+p192 = ecp_curve(-3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
+		 6277101735386680763835789423207666416083908700390324961279);
+p192_r = 6277101735386680763835789423176059013767194773182842284081;
+p192_g = ecp_pt(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
+		0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811, p192);
+
 /*----- That's all, folks -------------------------------------------------*/
 
diff --git a/configure.in b/configure.in
index aa0fdf4..599cc28 100644
--- a/configure.in
+++ b/configure.in
@@ -1,6 +1,6 @@
 dnl -*-fundamental-*-
 dnl
-dnl $Id: configure.in,v 1.24 2003/05/16 00:30:28 mdw Exp $
+dnl $Id: configure.in,v 1.24.2.1 2003/06/10 13:43:53 mdw Exp $
 dnl
 dnl Autoconfiguration for Catacomb
 dnl
@@ -29,6 +29,9 @@ dnl MA 02111-1307, USA.
 dnl ----- Revision history --------------------------------------------------
 dnl
 dnl $Log: configure.in,v $
+dnl Revision 1.24.2.1  2003/06/10 13:43:53  mdw
+dnl Simple (non-projective) curves over prime fields now seem to work.
+dnl
 dnl Revision 1.24  2003/05/16 00:30:28  mdw
 dnl Version bump.
 dnl
@@ -78,7 +81,7 @@ dnl
 dnl --- Boring boilerplate ---
 
 AC_INIT(blkc.h)
-mdw_INIT_LIB(catacomb, Catacomb, 2.0.0)
+mdw_INIT_LIB(catacomb, Catacomb, 2.1.0ec1)
 AM_CONFIG_HEADER(config.h)
 
 dnl --- Make sure I can compile and build libraries ---
diff --git a/ec-prime.c b/ec-prime.c
index 4611855..b2bfd52 100644
--- a/ec-prime.c
+++ b/ec-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-prime.c,v 1.3 2003/05/15 23:25:59 mdw Exp $
+ * $Id: ec-prime.c,v 1.3.4.1 2003/06/10 13:43:53 mdw Exp $
  *
  * Elliptic curves over prime fields
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-prime.c,v $
+ * 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.
  *
@@ -54,7 +57,7 @@ typedef struct ecctx {
   mp *a, *b;
 } ecctx;
 
-/*----- Main code ---------------------------------------------------------*/
+/*----- Simple prime curves -----------------------------------------------*/
 
 static const ec_ops ec_primeops;
 
@@ -157,7 +160,7 @@ static void ecdestroy(ec_curve *c)
 
 /* --- @ec_prime@, @ec_primeproj@ --- *
  *
- * Arguments:	@field *f@ = the underyling field for this elliptic curve
+ * Arguments:	@field *f@ = the underlying field for this elliptic curve
  *		@mp *a, *b@ = the coefficients for this curve
  *
  * Returns:	A pointer to the curve.
@@ -172,8 +175,8 @@ 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);
+  cc->a = F_IN(f, MP_NEW, a);
+  cc->b = F_IN(f, MP_NEW, b);
   return (&cc->c);
 }
 
@@ -194,10 +197,12 @@ int main(void)
   ec g = EC_INIT, d = EC_INIT;
   mp *p, *a, *b, *r;
 
+  printf("ec-prime: ");
+  fflush(stdout);
   a = MP(-3);
   b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
   p = MP(6277101735386680763835789423207666416083908700390324961279);
-  r = MP(6277101735386680763835789423176059013767194773182842284081);
+  r = MP(6277101735386680763835789423176059013767194773182842284080);
 
   f = field_prime(p);
   c = ec_prime(f, a, b);
@@ -206,14 +211,25 @@ int main(void)
   g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
 
   ec_mul(c, &d, &g, r);
-  MP_PRINT("d.x", d.x);
-  MP_PRINT("d.y", d.y);
+  if (EC_ATINF(&d)) {
+    fprintf(stderr, "zero too early\n");
+    return (1);
+  }
+  ec_add(c, &d, &d, &g);
+  if (!EC_ATINF(&d)) {
+    fprintf(stderr, "didn't reach zero\n");
+    MP_EPRINT("d.x", d.x);
+    MP_EPRINT("d.y", d.y);
+    return (1);
+  }
 
   ec_destroy(&d);
   ec_destroy(&g);
   ec_destroycurve(c);
   F_DESTROY(f);
-
+  MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r);
+  assert(!mparena_count(&mparena_global));
+  printf("ok\n");
   return (0);
 }
 
diff --git a/ec.c b/ec.c
index 47c01a9..4111928 100644
--- a/ec.c
+++ b/ec.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec.c,v 1.4 2003/05/15 23:25:59 mdw Exp $
+ * $Id: ec.c,v 1.4.4.1 2003/06/10 13:43:53 mdw Exp $
  *
  * Elliptic curve definitions
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.c,v $
+ * Revision 1.4.4.1  2003/06/10 13:43:53  mdw
+ * Simple (non-projective) curves over prime fields now seem to work.
+ *
  * Revision 1.4  2003/05/15 23:25:59  mdw
  * Make elliptic curve stuff build.
  *
@@ -250,6 +253,24 @@ ec *ec_find(ec_curve *c, ec *d, mp *x)
   return (d);
 }
 
+/* --- @ec_neg@ --- *
+ *
+ * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
+ *		@ec *d@ = pointer to the destination point
+ *		@const ec *p@ = pointer to the operand point
+ *
+ * Returns:	The destination point.
+ *
+ * Use:		Computes the negation of the given point.
+ */
+
+ec *ec_neg(ec_curve *c, ec *d, const ec *p)
+{
+  EC_IN(c, d, p);
+  EC_NEG(c, d, d);
+  return (EC_OUT(c, d, d));
+}
+
 /* --- @ec_add@ --- *
  *
  * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
@@ -273,6 +294,29 @@ ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
   return (d);
 }
 
+/* --- @ec_sub@ --- *
+ *
+ * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
+ *		@ec *d@ = pointer to the destination point
+ *		@const ec *p, *q@ = pointers to the operand points
+ *
+ * Returns:	The destination @d@.
+ *
+ * Use:		Subtracts one point from another on an elliptic curve.
+ */
+
+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_SUB(c, d, &qq, &qq);
+  EC_OUT(c, d, d);
+  EC_DESTROY(&pp);
+  EC_DESTROY(&qq);
+  return (d);
+}
+
 /* --- @ec_dbl@ --- *
  *
  * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
@@ -320,6 +364,7 @@ ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
     EXP_SIMPLE(*d, t, n);
   else
     EXP_WINDOW(*d, t, n);
+  EC_DESTROY(&t);
   return (d);
 }
 
diff --git a/ec.h b/ec.h
index 105838c..72ee7a9 100644
--- a/ec.h
+++ b/ec.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec.h,v 1.4 2003/05/15 23:25:59 mdw Exp $
+ * $Id: ec.h,v 1.4.4.1 2003/06/10 13:43:53 mdw Exp $
  *
  * Elliptic curve definitions
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec.h,v $
+ * Revision 1.4.4.1  2003/06/10 13:43:53  mdw
+ * Simple (non-projective) curves over prime fields now seem to work.
+ *
  * Revision 1.4  2003/05/15 23:25:59  mdw
  * Make elliptic curve stuff build.
  *
@@ -94,7 +97,7 @@ typedef struct ec_ops {
 } ec_ops;
 
 #define EC_IN(c, d, p)		(c)->ops->in((c), (d), (p))
-#define EC_OUT(c, d, p)		(c)->ops->in((c), (d), (p))
+#define EC_OUT(c, d, p)		(c)->ops->out((c), (d), (p))
 
 #define EC_FIND(c, d, x)	(c)->ops->find((c), (d), (x))
 #define EC_NEG(c, d, x)		(c)->ops->neg((c), (d), (x))
@@ -402,7 +405,7 @@ extern void ec_destroycurve(ec_curve */*c*/);
 
 /* --- @ec_prime@, @ec_primeproj@ --- *
  *
- * Arguments:	@field *f@ = the underyling field for this elliptic curve
+ * Arguments:	@field *f@ = the underlying field for this elliptic curve
  *		@mp *a, *b@ = the coefficients for this curve
  *
  * Returns:	A pointer to the curve.
diff --git a/f-prime.c b/f-prime.c
index f4bf3a7..0d76da0 100644
--- a/f-prime.c
+++ b/f-prime.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: f-prime.c,v 1.3 2003/05/15 23:25:59 mdw Exp $
+ * $Id: f-prime.c,v 1.3.4.1 2003/06/10 13:43:53 mdw Exp $
  *
  * Prime fields with Montgomery arithmetic
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: f-prime.c,v $
+ * 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.
  *
@@ -69,7 +72,8 @@ static void fdestroy(field *ff)
 static mp *fin(field *ff, mp *d, mp *x)
 {
   fctx *f = (fctx *)ff;
-  return (mpmont_mul(&f->mm, d, x, f->mm.r2));
+  mp_div(0, &d, x, f->mm.m);
+  return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 }
 
 static mp *fout(field *ff, mp *d, mp *x)
@@ -86,12 +90,24 @@ static mp *fneg(field *ff, mp *d, mp *x)
 
 static mp *fadd(field *ff, mp *d, mp *x, mp *y)
 {
-  return (mp_add(d, x, y));
+  fctx *f = (fctx *)ff;
+  d = mp_add(d, x, y);
+  if (d->f & MP_NEG)
+    d = mp_add(d, d, f->mm.m);
+  else if (MP_CMP(d, >, f->mm.m))
+    d = mp_sub(d, d, f->mm.m);
+  return (d);
 }
 
 static mp *fsub(field *ff, mp *d, mp *x, mp *y)
 {
-  return (mp_sub(d, x, y));
+  fctx *f = (fctx *)ff;
+  d = mp_sub(d, x, y);
+  if (d->f & MP_NEG)
+    d = mp_add(d, d, f->mm.m);
+  else if (MP_CMP(d, >, f->mm.m))
+    d = mp_sub(d, d, f->mm.m);
+  return (d);
 }
 
 static mp *fmul(field *ff, mp *d, mp *x, mp *y)
@@ -124,15 +140,20 @@ static mp *freduce(field *ff, mp *d, mp *x)
 
 static mp *fdbl(field *ff, mp *d, mp *x)
 {
-/*   fctx *f = (fctx *)ff; */
-  return (mp_lsl(d, x, 1));
+  fctx *f = (fctx *)ff;
+  d = mp_lsl(d, x, 1);
+  if (MP_CMP(d, >, f->mm.m))
+    d = mp_sub(d, d, f->mm.m);
+  return (d);
 }
 
 static mp *ftpl(field *ff, mp *d, mp *x)
 {
-/*   fctx *f = (fctx *)ff; */
+  fctx *f = (fctx *)ff;
   MP_DEST(d, MP_LEN(x) + 1, x->f);
   MPX_UMULN(d->v, d->vl, x->v, x->vl, 3);
+  while (MP_CMP(d, >, f->mm.m))
+    d = mp_sub(d, d, f->mm.m);
   return (d);
 }
 
diff --git a/field.c b/field.c
index c7e7559..0f02fa7 100644
--- a/field.c
+++ b/field.c
@@ -1,8 +1,9 @@
 /* -*-c-*-
  *
- * $Id: field.c,v 1.1 2001/05/07 17:30:13 mdw Exp $
+ * $Id: field.c,v 1.1.4.1 2003/06/10 13:43:53 mdw Exp $
+ *
+ * Abstract field operations
  *
- * [Abstract field operations *
  * (c) 2001 Straylight/Edgeware
  */
 
@@ -29,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: field.c,v $
+ * Revision 1.1.4.1  2003/06/10 13:43:53  mdw
+ * Simple (non-projective) curves over prime fields now seem to work.
+ *
  * Revision 1.1  2001/05/07 17:30:13  mdw
  * Add an internal-representation no-op function.
  *
-- 
2.11.0