## -*-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
##
##----- 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.
##
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') \
`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 \
CTESTRIG(gfreduce)
CTESTRIG(ec-prime)
CTESTRIG(ec-bin)
+CTESTRIG(ec-test)
CTESTRIG(pgen)
CTESTRIG(dsa-gen)
CTESTRIG(dsa-sign)
/* -*-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
*
/*----- 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.
*
obj ecp_curve { a, b, p };
obj ecp_pt { x, y, e };
-obj ecpp_pt { x, y, z, e };
/*----- Main code ---------------------------------------------------------*/
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 : ")" :;
/* -*-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
*
/*----- 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
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)
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);
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,
- 0, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+ ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};
/*----- Test rig ----------------------------------------------------------*/
printf("ec-bin: ");
fflush(stdout);
a = MP(1);
- b = MP(0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad);
- p = MP(0x20000000000000000000000000000000000000004000000000000000001);
+ b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f);
+ p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001);
r =
- MP(6901746346790563787434755862277025555839812737345013555379383634485462);
+ MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770);
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);
/* -*-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
*
/*----- 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
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,
- 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,
- 0, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
+ ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
};
/*----- Test rig ----------------------------------------------------------*/
--- /dev/null
+/* -*-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 -------------------------------------------------*/
--- /dev/null
+/* -*-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
/* -*-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
*
/*----- 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.
*
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@ --- *
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);
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
/* -*-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
*
/*----- 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
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@ --- *
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
/* -*-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
*
/*----- 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.
*
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));
/* --- 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,
/* -*-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
*
/*----- 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.
*
/* --- Field operations table --- */
static field_ops fops = {
+ FTY_PRIME, "prime",
fdestroy, frand,
fin, fout,
fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
/* -*-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
*
/*----- 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.
*
mp *zero, *one; /* Identities in the field */
} field;
+enum {
+ FTY_PRIME,
+ FTY_BINARY
+};
+
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*/);
} 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_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))
/* -*-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
*
/*----- 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.
*
}
MP_DROP(t);
MP_DROP(x);
- d->v[0] &= ~(mpw)1;
+ if (d) d->v[0] &= ~(mpw)1;
return (d);
}
--- /dev/null
+# $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;
+}
-# $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
0x10000000000000000000000000000000000000000003
0x3b818b447e90713da04f13c3b07cb5e2681d08e4700
0x27aa17c97dfa80bbdef9f91b243c6e6ddba1a223cac;
+ 0x800000000000000000000000000000000000000c9
+ 0x158fe327cc763a2fd7371ee80641ed1871a32aaa8
+ 0x29ab0d7da05ffc3f1b3f97ac10e2092694aadbb7c;
}