From bc985cefafea2e1b02095a2ff2a9982c4c647d17 Mon Sep 17 00:00:00 2001 From: mdw Date: Tue, 23 Mar 2004 15:19:32 +0000 Subject: [PATCH] Test elliptic curves more thoroughly. --- Makefile.m4 | 10 +- calc/ecp.cal | 72 +--------- ec-bin.c | 50 +++++-- ec-prime.c | 11 +- ec-test.c | 418 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ec-test.h | 63 +++++++++ ec.c | 37 ++++- ec.h | 34 ++++- f-binpoly.c | 8 +- f-prime.c | 6 +- field.h | 19 ++- gfreduce.c | 7 +- tests/ec | 291 +++++++++++++++++++++++++++++++++++++++ tests/gfreduce | 5 +- 14 files changed, 935 insertions(+), 96 deletions(-) create mode 100644 ec-test.c create mode 100644 ec-test.h create mode 100644 tests/ec diff --git a/Makefile.m4 b/Makefile.m4 index 2bb62f2..ee3872a 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-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 ## @@ -29,6 +29,9 @@ ##----- 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. ## @@ -352,7 +355,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 \ + 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') \ @@ -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', - `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 \ @@ -550,6 +553,7 @@ CTESTRIG(gf-gcd) CTESTRIG(gfreduce) CTESTRIG(ec-prime) CTESTRIG(ec-bin) +CTESTRIG(ec-test) CTESTRIG(pgen) CTESTRIG(dsa-gen) CTESTRIG(dsa-sign) diff --git a/calc/ecp.cal b/calc/ecp.cal index 7c560c5..3834359 100644 --- a/calc/ecp.cal +++ b/calc/ecp.cal @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -48,7 +51,6 @@ obj ecp_curve { a, b, p }; obj ecp_pt { x, y, e }; -obj ecpp_pt { x, y, z, e }; /*----- Main code ---------------------------------------------------------*/ @@ -70,72 +72,6 @@ define ecp_pt(x, y, e) 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 : ")" :; diff --git a/ec-bin.c b/ec-bin.c index 42aaad8..a71ed2d 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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 @@ -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) { - /* 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) @@ -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); - rc = F_ZEROP(f, u); + rc = F_ZEROP(f, u) ? 0 : -1; 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, - 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 ----------------------------------------------------------*/ @@ -394,16 +422,16 @@ int main(int argc, char *argv[]) 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); diff --git a/ec-prime.c b/ec-prime.c index 827c0f2..5c6297f 100644 --- a/ec-prime.c +++ b/ec-prime.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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 @@ -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, - 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 ----------------------------------------------------------*/ diff --git a/ec-test.c b/ec-test.c new file mode 100644 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 +#include +#include +#include +#include + +#include +#include +#include + +#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 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 + +#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 --- a/ec.c +++ b/ec.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -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_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@ --- * @@ -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_SUB(c, d, &qq, &qq); + EC_SUB(c, d, &pp, &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); } +/* --- @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 diff --git a/ec.h b/ec.h index 680bf9c..d398f4a 100644 --- a/ec.h +++ b/ec.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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 @@ -235,6 +238,22 @@ extern ec *ec_setinf(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@ --- * @@ -253,6 +272,19 @@ extern ec *ec_copy(ec */*d*/, const ec */*p*/); 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 diff --git a/f-binpoly.c b/f-binpoly.c index 463dbb2..1da5d12 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -68,7 +71,7 @@ static void fdestroy(field *ff) 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)); @@ -126,6 +129,7 @@ static mp *fquadsolve(field *ff, mp *d, mp *x) /* --- 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, diff --git a/f-prime.c b/f-prime.c index 5ab4204..08ed300 100644 --- a/f-prime.c +++ b/f-prime.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -218,6 +221,7 @@ static mp *fhlv(field *ff, mp *d, mp *x) /* --- Field operations table --- */ static field_ops fops = { + FTY_PRIME, "prime", 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 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -77,8 +80,18 @@ typedef struct field { 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*/); @@ -110,7 +123,11 @@ typedef struct 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_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)) diff --git a/gfreduce.c b/gfreduce.c index 819c276..929c46c 100644 --- a/gfreduce.c +++ b/gfreduce.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,9 @@ /*----- 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. * @@ -440,7 +443,7 @@ mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x) } MP_DROP(t); MP_DROP(x); - d->v[0] &= ~(mpw)1; + if (d) d->v[0] &= ~(mpw)1; return (d); } diff --git a/tests/ec b/tests/ec new file mode 100644 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 --- 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 @@ -58,4 +58,7 @@ quadsolve { 0x10000000000000000000000000000000000000000003 0x3b818b447e90713da04f13c3b07cb5e2681d08e4700 0x27aa17c97dfa80bbdef9f91b243c6e6ddba1a223cac; + 0x800000000000000000000000000000000000000c9 + 0x158fe327cc763a2fd7371ee80641ed1871a32aaa8 + 0x29ab0d7da05ffc3f1b3f97ac10e2092694aadbb7c; } -- 2.11.0