--- /dev/null
+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
## -*-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
##
##----- 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'.
##
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.
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 \
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') \
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 \
CTESTRIG(mpmul)
CTESTRIG(gfx)
CTESTRIG(gfx-kmul)
+CTESTRIG(ec-prime)
CTESTRIG(pgen)
CTESTRIG(dsa-gen)
CTESTRIG(dsa-sign)
/* -*-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
*
/*----- 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.
*
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;
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;
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 -------------------------------------------------*/
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
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
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 ---
/* -*-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
*
/*----- 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.
*
mp *a, *b;
} ecctx;
-/*----- Main code ---------------------------------------------------------*/
+/*----- Simple prime curves -----------------------------------------------*/
static const ec_ops ec_primeops;
/* --- @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.
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);
}
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);
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);
}
/* -*-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
*
/*----- 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.
*
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
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
EXP_SIMPLE(*d, t, n);
else
EXP_WINDOW(*d, t, n);
+ EC_DESTROY(&t);
return (d);
}
/* -*-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
*
/*----- 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.
*
} 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))
/* --- @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.
/* -*-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
*
/*----- 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.
*
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)
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)
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);
}
/* -*-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
*/
/*----- 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.
*