From 432c4e184d44704511a5991b80224a87cb1d4613 Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 27 Mar 2004 17:54:12 +0000 Subject: [PATCH] Standard curves and curve checking. --- Makefile.m4 | 26 ++- ec-bin.c | 41 ++-- ec-gentab.sh | 143 +++++++++++++ ec-info.c | 585 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ec-prime.c | 74 +++---- ec-test.c | 110 ++-------- ec.c | 7 +- ec.h | 122 +++++++++++- ectab-canonify.pl | 16 ++ ectab.h | 83 ++++++++ ectab.in | 341 +++++++++++++++++++++++++++++++ f-binpoly.c | 13 +- f-niceprime.c | 8 +- f-prime.c | 8 +- field-parse.c | 86 ++++++++ field.h | 27 ++- gf-arith.c | 55 ++++- gf.h | 14 +- gfx-kmul.c | 9 +- mp-sqrt.c | 7 +- mpdump.c | 82 ++++++++ mpx-kmul.c | 9 +- qdparse.c | 151 ++++++++++++++ qdparse.h | 123 ++++++++++++ tests/ec | 8 +- tests/gf | 13 +- tests/gfreduce | 8 +- 27 files changed, 1979 insertions(+), 190 deletions(-) create mode 100755 ec-gentab.sh create mode 100644 ec-info.c create mode 100644 ectab-canonify.pl create mode 100644 ectab.h create mode 100644 ectab.in create mode 100644 field-parse.c create mode 100644 mpdump.c create mode 100644 qdparse.c create mode 100644 qdparse.h diff --git a/Makefile.m4 b/Makefile.m4 index cc500de..805696b 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-m4-*- ## -## $Id: Makefile.m4,v 1.70 2004/03/27 00:04:46 mdw Exp $ +## $Id: Makefile.m4,v 1.71 2004/03/27 17:54:11 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ +## Revision 1.71 2004/03/27 17:54:11 mdw +## Standard curves and curve checking. +## ## Revision 1.70 2004/03/27 00:04:46 mdw ## Implement efficient reduction for pleasant-looking primes. ## @@ -328,6 +331,10 @@ mptypes.h: mptypes ./mptypes >mptypes.h.new mv mptypes.h.new mptypes.h +ectab.c: ectab.in ec-gentab.sh mpdump + $(srcdir)/ec-gentab.sh <$(srcdir)/ectab.in >ectab.c.new + mv ectab.c.new ectab.c + BUILT_SOURCES = \ getdate.c modes-stamp \ addsuffix(join(`ciphers', `-', `cipher_modes'), `.c') \ @@ -344,7 +351,7 @@ libcatacomb_la_LDFLAGS = -version-info 3:0:1 ## difference between the first and last numbers is major version. pkginclude_HEADERS = \ - arena.h paranoia.h buf.h \ + arena.h paranoia.h buf.h qdparse.h \ blkc.h hash.h gcipher.h ghash.h gmac.h grand.h ghash-def.h \ 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 \ @@ -382,8 +389,8 @@ define(`GF_SOURCES', gfreduce.c gfreduce-exp.h ') define(`EC_SOURCES', - `field.c f-prime.c f-niceprime.c f-binpoly.c \ - ec.c ec-prime.c ec-bin.c ec-test.c') + `field.c field-parse.c f-prime.c f-niceprime.c f-binpoly.c \ + ec.c ec-prime.c ec-bin.c ec-test.c ec-info.c ectab.c') define(`PGEN_SOURCES', `pfilt.c rabin.c \ @@ -402,7 +409,7 @@ define(`PGEN_SOURCES', libcatacomb_la_SOURCES = \ grand.c keysz.c \ lcrand.c fibrand.c rc4.c seal.c rand.c noise.c fipstest.c maurer.c \ - arena.c \ + arena.c qdparse.c \ passphrase.c pixie-client.c pixie-common.c lmem.c \ oaep.c pkcs1.c pss.c tlsprf.c sslprf.c \ gfshare.c \ @@ -438,7 +445,7 @@ patsubst(PGEN_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o: primetab.h bin_PROGRAMS = dsig key pixie rspit factorial hashsum mkphrase bin_SCRIPTS = catacomb-config xpixie noinst_PROGRAMS = \ - genprimes mptypes serpent-check bittest \ + genprimes mptypes serpent-check bittest mpdump \ addsuffix(`gen_tables', `-mktab') LDADD = libcatacomb.la @@ -467,6 +474,13 @@ genprimes_LDADD = mptypes_SOURCES = mptypes.c mptypes_LDADD = +mpdump_SOURCES = \ + mpdump.c \ + mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c \ + mp-misc.c mp-mem.c mp-const.c mp-arith.c mp-io.c \ + mptext.c mptext-string.c +mpdump_LDADD = + ## --- Install the pixie setuid-root if we can --- ## ## Bodge around a bug in Automake: it doesn't call `install-exec-hook' from diff --git a/ec-bin.c b/ec-bin.c index a71ed2d..0efb72f 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $ + * $Id: ec-bin.c,v 1.5 2004/03/27 17:54:11 mdw Exp $ * * Arithmetic for elliptic curves over binary fields * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-bin.c,v $ + * Revision 1.5 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.4 2004/03/23 15:19:32 mdw * Test elliptic curves more thoroughly. * @@ -56,7 +59,6 @@ typedef struct ecctx { ec_curve c; - mp *a, *b; mp *bb; } ecctx; @@ -86,15 +88,14 @@ static ec *ecprojneg(ec_curve *c, ec *d, const ec *p) static ec *ecfind(ec_curve *c, ec *d, mp *x) { 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); + y = F_SQRT(f, MP_NEW, c->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$% */ + y = F_MUL(f, MP_NEW, u, c->a); /* %$a x^2$% */ + y = F_ADD(f, y, y, c->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)) { @@ -120,7 +121,6 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a) EC_SETINF(d); else { field *f = c->f; - ecctx *cc = (ecctx *)c; mp *lambda; mp *dx, *dy; @@ -130,7 +130,7 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a) dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */ dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */ - dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */ + dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */ dy = F_ADD(f, MP_NEW, a->x, dx); /* %$ x + x' $% */ dy = F_MUL(f, dy, dy, lambda); /* %$ (x + x') \lambda$% */ @@ -196,7 +196,6 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) EC_COPY(d, a); else { field *f = c->f; - ecctx *cc = (ecctx *)c; mp *lambda; mp *dx, *dy; @@ -209,7 +208,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */ dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */ - dx = F_ADD(f, dx, dx, cc->a); /* %$a + \lambda^2 + \lambda$% */ + dx = F_ADD(f, dx, dx, c->a); /* %$a + \lambda^2 + \lambda$% */ dx = F_ADD(f, dx, dx, a->x); /* %$a + \lambda^2 + \lambda + x_0$% */ dx = F_ADD(f, dx, dx, b->x); /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */ @@ -223,7 +222,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */ dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */ - dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */ + dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */ dy = MP_NEW; } @@ -251,7 +250,6 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) EC_COPY(d, a); else { field *f = c->f; - ecctx *cc = (ecctx *)c; mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l; dz = F_SQR(f, MP_NEW, b->z); /* %$z_1^2$% */ @@ -293,7 +291,7 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) t = F_ADD(f, t, r, dz); /* %$t = r + z'$% */ uu = F_SQR(f, MP_NEW, dz); /* %$z'^2$% */ - dx = F_MUL(f, MP_NEW, uu, cc->a); /* %$a z'^2$% */ + dx = F_MUL(f, MP_NEW, uu, c->a); /* %$a z'^2$% */ uu = F_MUL(f, uu, t, r); /* %$t r$% */ dx = F_ADD(f, dx, dx, uu); /* %$a z'^2 + t r$% */ r = F_SQR(f, r, w); /* %$w^2$% */ @@ -320,16 +318,15 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) static int eccheck(ec_curve *c, const ec *p) { - ecctx *cc = (ecctx *)c; field *f = c->f; int rc; mp *u, *v; v = F_SQR(f, MP_NEW, p->x); u = F_MUL(f, MP_NEW, v, p->x); - v = F_MUL(f, v, v, cc->a); + v = F_MUL(f, v, v, c->a); u = F_ADD(f, u, u, v); - u = F_ADD(f, u, u, cc->b); + u = F_ADD(f, u, u, c->b); v = F_MUL(f, v, p->x, p->y); u = F_ADD(f, u, u, v); v = F_SQR(f, v, p->y); @@ -354,8 +351,8 @@ static int ecprojcheck(ec_curve *c, const ec *p) static void ecdestroy(ec_curve *c) { ecctx *cc = (ecctx *)c; - MP_DROP(cc->a); - MP_DROP(cc->b); + MP_DROP(cc->c.a); + MP_DROP(cc->c.b); if (cc->bb) MP_DROP(cc->bb); DESTROY(cc); } @@ -377,8 +374,8 @@ ec_curve *ec_bin(field *f, mp *a, mp *b) ecctx *cc = CREATE(ecctx); cc->c.ops = &ec_binops; cc->c.f = f; - cc->a = F_IN(f, MP_NEW, a); - cc->b = F_IN(f, MP_NEW, b); + cc->c.a = F_IN(f, MP_NEW, a); + cc->c.b = F_IN(f, MP_NEW, b); cc->bb = 0; return (&cc->c); } @@ -388,8 +385,8 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b) ecctx *cc = CREATE(ecctx); cc->c.ops = &ec_binprojops; cc->c.f = f; - cc->a = F_IN(f, MP_NEW, a); - cc->b = F_IN(f, MP_NEW, b); + cc->c.a = F_IN(f, MP_NEW, a); + cc->c.b = F_IN(f, MP_NEW, b); cc->bb = F_SQRT(f, MP_NEW, b); cc->bb = F_SQRT(f, cc->bb, cc->bb); return (&cc->c); diff --git a/ec-gentab.sh b/ec-gentab.sh new file mode 100755 index 0000000..ea63094 --- /dev/null +++ b/ec-gentab.sh @@ -0,0 +1,143 @@ +#! /bin/sh + +set -e + +cat <&2 "$0: unknown keyword $t"; exit 1;; + esac + + names="$names $n=$n" + cat <&2 "$0: wanted p; found $t"; exit 1; fi + read t a + if [ $t != a ]; then echo >&2 "$0: wanted a; found $t"; exit 1; fi + read t b + if [ $t != b ]; then echo >&2 "$0: wanted b; found $t"; exit 1; fi + + cat <&2 "$0: unknown field type $f"; exit 1;; + esac + + read t r + if [ $t != r ]; then echo >&2 "$0: wanted r; found $t"; exit 1; fi + read t h + if [ $t != h ]; then echo >&2 "$0: wanted h; found $t"; exit 1; fi + read t gx + if [ $t != gx ]; then echo >&2 "$0: wanted gx; found $t"; exit 1; fi + read t gy + if [ $t != gy ]; then echo >&2 "$0: wanted gy; found $t"; exit 1; fi + + cat <e = "field not prime"; + goto fail; + } + qd_delim(qd, ':'); + if ((a = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); + if ((b = qd_getmp(qd)) == 0) goto fail; + c = ec_prime(f, a, b); + break; + case 1: + if (F_TYPE(f) != FTY_PRIME) { + qd->e = "field not prime"; + goto fail; + } + qd_delim(qd, ':'); + if ((a = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); + if ((b = qd_getmp(qd)) == 0) goto fail; + c = ec_primeproj(f, a, b); + break; + case 2: + if (F_TYPE(f) != FTY_BINARY) { + qd->e = "field not binary"; + goto fail; + } + qd_delim(qd, ':'); + if ((a = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); + if ((b = qd_getmp(qd)) == 0) goto fail; + c = ec_bin(f, a, b); + break; + case 3: + if (F_TYPE(f) != FTY_BINARY) { + qd->e = "field not binary"; + goto fail; + } + qd_delim(qd, ':'); + if ((a = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); + if ((b = qd_getmp(qd)) == 0) goto fail; + c = ec_binproj(f, a, b); + break; + default: + goto fail; + } + if (a) MP_DROP(a); + if (b) MP_DROP(b); + return (c); + +fail: + if (f) F_DESTROY(f); + if (a) MP_DROP(a); + if (b) MP_DROP(b); + return (0); +} + +/* --- @ec_ptparse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * @ec *p@ = where to put the point + * + * Returns: The point address, or null. + * + * Use: Parses an elliptic curve point. This has the form + * + * * %$x$%-coordinate + * * optional `,' + * * %$y$%-coordinate + */ + +ec *ec_ptparse(qd_parse *qd, ec *p) +{ + mp *x = MP_NEW, *y = MP_NEW; + + if (qd_enum(qd, "inf") >= 0) { + EC_SETINF(p); + return (p); + } + if ((x = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); + if ((y = qd_getmp(qd)) == 0) goto fail; + EC_DESTROY(p); + p->x = x; + p->y = y; + p->z = 0; + return (p); + +fail: + if (x) MP_DROP(x); + if (y) MP_DROP(y); + return (0); +} + +/* --- @ec_infoparse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * @ec_info *ei@ = curve information block, currently + * uninitialized + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Parses an elliptic curve information string, and stores the + * information in @ei@. This has the form + * + * * elliptic curve description + * * optional `/' + * * common point + * * optional `:' + * * group order + * * optional `*' + * * cofactor + */ + +int ec_infoparse(qd_parse *qd, ec_info *ei) +{ + ec_curve *c = 0; + field *f; + ec g = EC_INIT; + mp *r = MP_NEW, *h = MP_NEW; + + if ((c = ec_curveparse(qd)) == 0) goto fail; + qd_delim(qd, '/'); if (!ec_ptparse(qd, &g)) goto fail; + qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail; + + ei->c = c; ei->g = g; ei->r = r; ei->h = h; + return (0); + +fail: + EC_DESTROY(&g); + if (r) MP_DROP(r); + if (h) MP_DROP(h); + if (c) { f = c->f; ec_destroycurve(c); F_DESTROY(f); } + return (-1); +} + +/* --- @getinfo@ --- * + * + * Arguments: @ec_info *ei@ = where to write the information + * @const ecdata *ed@ = raw data + * + * Returns: --- + * + * Use: Loads elliptic curve information about one of the standard + * curves. + */ + +static mp *getmp(const mpw *v, size_t n) +{ + mp *x = mp_new(n, 0); + memcpy(x->v, v, MPWS(n)); + return (x); +} + +static void getinfo(ec_info *ei, const ecdata *ed) +{ + field *f; + mp *p = 0, *a = 0, *b = 0; + + switch (ed->ftag) { + case FTAG_PRIME: + p = getmp(ed->p, ed->psz); + f = field_prime(p); + a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz); + ei->c = ec_primeproj(f, a, b); + break; + case FTAG_NICEPRIME: + p = getmp(ed->p, ed->psz); + f = field_niceprime(p); + a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz); + ei->c = ec_primeproj(f, a, b); + break; + case FTAG_BINPOLY: + p = getmp(ed->p, ed->psz); + f = field_binpoly(p); + a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz); + ei->c = ec_binproj(f, a, b); + break; + default: + abort(); + } + + EC_CREATE(&ei->g); + ei->g.x = getmp(ed->gx, ed->gxsz); + ei->g.y = getmp(ed->gy, ed->gysz); + ei->g.z = 0; + ei->r = getmp(ed->r, ed->rsz); + ei->h = getmp(ed->h, ed->hsz); + + MP_DROP(p); + MP_DROP(a); + MP_DROP(b); +} + +/* --- @ec_getinfo@ --- * + * + * Arguments: @ec_info *ei@ = where to write the information + * @const char *p@ = string describing a curve + * + * Returns: Null on success, or a pointer to an error message. + * + * Use: Parses out information about a curve. The string is either a + * standard curve name, or a curve info string. + */ + +const char *ec_getinfo(ec_info *ei, const char *p) +{ + qd_parse qd; + const ecentry *ee; + + qd.p = p; + qd.e = 0; + for (ee = ectab; ee->name; ee++) { + if (qd_enum(&qd, ee->name) >= 0) { + getinfo(ei, ee->data); + goto found; + } + } + if (ec_infoparse(&qd, ei)) + return (qd.e); +found: + if (!qd_eofp(&qd)) { + ec_freeinfo(ei); + return ("junk found at end of string"); + } + return (0); +} + +/* --- @ec_freeinfo@ --- * + * + * Arguments: @ec_info *ei@ = elliptic curve information block to free + * + * Returns: --- + * + * Use: Frees the information block. + */ + +void ec_freeinfo(ec_info *ei) +{ + field *f; + + EC_DESTROY(&ei->g); + MP_DROP(ei->r); + MP_DROP(ei->h); + f = ei->c->f; ec_destroycurve(ei->c); F_DESTROY(f); +} + +/* --- @ec_checkinfo@ --- * + * + * Arguments: @const ec_info *ei@ = elliptic curve information block + * + * Returns: Null if OK, or pointer to error message. + * + * Use: Checks an elliptic curve according to the rules in SEC1. + */ + +static int primep(mp *p, grand *gr) +{ + int i = rabin_iters(mp_bits(p)); + rabin r; + mp *x = MP_NEW; + + switch (pfilt_smallfactor(p)) { + case PGEN_DONE: return (1); + case PGEN_FAIL: return (0); + } + rabin_create(&r, p); + while (i) { + x = mprand_range(x, p, gr, 0); + if (rabin_rtest(&r, x) == PGEN_FAIL) + break; + i--; + } + MP_DROP(x); + rabin_destroy(&r); + return (!i); +} + +static int primeeltp(mp *x, field *f) +{ + return (!MP_ISNEG(x) && MP_CMP(x, <, f->m)); +} + +static const char *primecheck(const ec_info *ei, grand *gr) +{ + ec_curve *c = ei->c; + field *f = c->f; + int i; + mp *x, *y; + ec p; + int rc; + + /* --- Check %$p$% is an odd prime --- */ + + if (!primep(f->m, gr)) return ("p not prime"); + + /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */ + + if (!primeeltp(c->a, f)) return ("a out of range"); + if (!primeeltp(c->b, f)) return ("b out of range"); + if (!primeeltp(ei->g.x, f)) return ("G_x out of range"); + if (!primeeltp(ei->g.x, f)) return ("G_y out of range"); + + /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */ + + x = F_SQR(f, MP_NEW, c->a); + x = F_MUL(f, x, x, c->a); + x = F_QDL(f, x, x); + y = F_SQR(f, MP_NEW, c->b); + y = F_TPL(f, y, y); + y = F_TPL(f, y, y); + y = F_TPL(f, y, y); + x = F_ADD(f, x, x, y); + rc = F_ZEROP(f, x); + MP_DROP(x); + MP_DROP(y); + if (rc) return ("not an elliptic curve"); + + /* --- Check %$G \in E$% --- */ + + if (EC_ATINF(&ei->g)) return ("generator at infinity"); + if (ec_check(c, &ei->g)) return ("generator not on curve"); + + /* --- Check %$r$% is prime --- */ + + if (!primep(ei->r, gr)) return ("generator order not prime"); + + /* --- Check %$0 < h \le 4$% --- */ + + if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR)) + return ("cofactor out of range"); + + /* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- * + * + * This seems to work with the approximate-sqrt in the library, but might + * not be so good in some cases. Throw in some extra significate figures + * for good measure. + */ + + x = mp_lsl(MP_NEW, f->m, 128); + x = mp_sqrt(x, x); + y = mp_lsl(MP_NEW, MP_ONE, 64); + x = mp_add(x, x, y); + x = mp_sqr(x, x); + mp_div(&x, 0, x, ei->r); + x = mp_lsr(x, x, 128); + rc = MP_EQ(x, ei->h); + MP_DROP(x); + MP_DROP(y); + if (!rc) return ("incorrect cofactor"); + + /* --- Check %$n G = O$% --- */ + + EC_CREATE(&p); + ec_mul(c, &p, &ei->g, ei->r); + rc = EC_ATINF(&p); + EC_DESTROY(&p); + if (!rc) return ("incorrect group order"); + + /* --- Check that %$p^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- * + * + * The spec says %$q$%, not %$p$%, but I think that's a misprint. + */ + + x = MP_NEW; + mp_div(0, &x, f->m, ei->r); + i = 20; + while (i) { + if (MP_EQ(x, MP_ONE)) break; + x = mp_mul(x, x, f->m); + mp_div(0, &x, x, ei->r); + i--; + } + MP_DROP(x); + if (i) return ("curve is weak"); + + /* --- Done --- */ + + return (0); +} + +static const char *bincheck(const ec_info *ei, grand *gr) +{ + ec_curve *c = ei->c; + field *f = c->f; + int i; + mp *x, *y; + ec p; + int rc; + + /* --- Check that %$p$% is irreducible --- */ + + if (!gf_irreduciblep(f->m)) return ("p not irreducible"); + + /* --- Check that %$a, b, G_x, G_y$% have degree less than %$p$% --- */ + + if (mp_bits(c->a) > f->nbits) return ("a out of range"); + if (mp_bits(c->b) > f->nbits) return ("a out of range"); + if (mp_bits(ei->g.x) > f->nbits) return ("G_x out of range"); + if (mp_bits(ei->g.y) > f->nbits) return ("G_y out of range"); + + /* --- Check that %$b \ne 0$% --- */ + + if (F_ZEROP(f, c->b)) return ("b is zero"); + + /* --- Check that %$G \in E$% --- */ + + if (EC_ATINF(&ei->g)) return ("generator at infinity"); + if (ec_check(c, &ei->g)) return ("generator not on curve"); + + /* --- Check %$r$% is prime --- */ + + if (!primep(ei->r, gr)) return ("generator order not prime"); + + /* --- Check %$0 < h \le 4$% --- */ + + if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR)) + return ("cofactor out of range"); + + /* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- * + * + * This seems to work with the approximate-sqrt in the library, but might + * not be so good in some cases. Throw in some extra significate figures + * for good measure. + */ + + x = mp_lsl(MP_NEW, MP_ONE, f->nbits + 128); + x = mp_sqrt(x, x); + y = mp_lsl(MP_NEW, MP_ONE, 64); + x = mp_add(x, x, y); + x = mp_sqr(x, x); + mp_div(&x, 0, x, ei->r); + x = mp_lsr(x, x, 128); + rc = MP_EQ(x, ei->h); + MP_DROP(x); + MP_DROP(y); + if (!rc) return ("incorrect cofactor"); + + /* --- Check %$n G = O$% --- */ + + EC_CREATE(&p); + ec_mul(c, &p, &ei->g, ei->r); + rc = EC_ATINF(&p); + EC_DESTROY(&p); + if (!rc) return ("incorrect group order"); + + /* --- Check %$2^{m B} \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- */ + + x = mp_lsl(MP_NEW, MP_ONE, f->nbits); + mp_div(0, &x, x, ei->r); + i = 20; + while (i) { + if (MP_EQ(x, MP_ONE)) break; + x = mp_mul(x, x, f->m); + mp_div(0, &x, x, ei->r); + i--; + } + MP_DROP(x); + if (i) return ("curve is weak"); + + /* --- Done --- */ + + return (0); +} + +const char *ec_checkinfo(const ec_info *ei, grand *gr) +{ + switch (F_TYPE(ei->c->f)) { + case FTY_PRIME: return (primecheck(ei, gr)); break; + case FTY_BINARY: return (bincheck(ei, gr)); break; + } + return ("unknown curve type"); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include "fibrand.h" + +int main(void) +{ + const ecentry *ee; + const char *e; + int ok = 1; + grand *gr; + + gr = fibrand_create(0); + fputs("checking standard curves: ", stdout); + for (ee = ectab; ee->name; ee++) { + ec_info ei; + getinfo(&ei, ee->data); + e = ec_checkinfo(&ei, gr); + ec_freeinfo(&ei); + if (e) { + fprintf(stderr, "\n*** curve %s fails: %s\n", ee->name, e); + ok = 0; + } + putchar('.'); + fflush(stdout); + } + gr->ops->destroy(gr); + fputs(ok ? " ok\n" : " failed\n", stdout); + return (!ok); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/ec-prime.c b/ec-prime.c index 7712bbf..ce81ba1 100644 --- a/ec-prime.c +++ b/ec-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-prime.c,v 1.7 2004/03/27 00:04:46 mdw Exp $ + * $Id: ec-prime.c,v 1.8 2004/03/27 17:54:11 mdw Exp $ * * Elliptic curves over prime fields * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-prime.c,v $ + * Revision 1.8 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.7 2004/03/27 00:04:46 mdw * Implement efficient reduction for pleasant-looking primes. * @@ -70,13 +73,6 @@ #include "ec.h" -/*----- Data structures ---------------------------------------------------*/ - -typedef struct ecctx { - ec_curve c; - mp *a, *b; -} ecctx; - /*----- Simple prime curves -----------------------------------------------*/ static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops; @@ -92,14 +88,13 @@ static ec *ecneg(ec_curve *c, ec *d, const ec *p) static ec *ecfind(ec_curve *c, ec *d, mp *x) { mp *p, *q; - ecctx *cc = (ecctx *)c; field *f = c->f; q = F_SQR(f, MP_NEW, x); p = F_MUL(f, MP_NEW, x, q); - q = F_MUL(f, q, x, cc->a); + q = F_MUL(f, q, x, c->a); p = F_ADD(f, p, p, q); - p = F_ADD(f, p, p, cc->b); + p = F_ADD(f, p, p, c->b); MP_DROP(q); p = F_SQRT(f, p, p); if (!p) @@ -119,14 +114,13 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a) EC_COPY(d, a); else { field *f = c->f; - ecctx *cc = (ecctx *)c; mp *lambda; mp *dy, *dx; dx = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */ dy = F_DBL(f, MP_NEW, a->y); /* %$2 y$% */ dx = F_TPL(f, dx, dx); /* %$3 x^2$% */ - dx = F_ADD(f, dx, dx, cc->a); /* %$3 x^2 + A$% */ + dx = F_ADD(f, dx, dx, c->a); /* %$3 x^2 + A$% */ dy = F_INV(f, dy, dy); /* %$(2 y)^{-1}$% */ lambda = F_MUL(f, MP_NEW, dx, dy); /* %$\lambda = (3 x^2 + A)/(2 y)$% */ @@ -154,12 +148,11 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a) EC_COPY(d, a); else { field *f = c->f; - ecctx *cc = (ecctx *)c; mp *p, *q, *m, *s, *dx, *dy, *dz; p = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */ q = F_SQR(f, MP_NEW, p); /* %$z^4$% */ - p = F_MUL(f, p, q, cc->a); /* %$A z^4$% */ + p = F_MUL(f, p, q, c->a); /* %$A z^4$% */ m = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */ m = F_TPL(f, m, m); /* %$3 x^2$% */ m = F_ADD(f, m, m, p); /* %$m = 3 x^2 + A z^4$% */ @@ -257,10 +250,9 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) EC_SETINF(d); return (d); } else { - ecctx *cc = (ecctx *)c; dx = F_SQR(f, MP_NEW, a->x); /* %$x_0^2$% */ dx = F_TPL(f, dx, dx); /* %$3 x_0^2$% */ - dx = F_ADD(f, dx, dx, cc->a); /* %$3 x_0^2 + A$% */ + dx = F_ADD(f, dx, dx, c->a); /* %$3 x_0^2 + A$% */ dy = F_DBL(f, MP_NEW, a->y); /* %$2 y_0$% */ dy = F_INV(f, dy, dy); /* %$(2 y_0)^{-1}$% */ lambda = F_MUL(f, MP_NEW, dx, dy); @@ -356,15 +348,14 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) static int eccheck(ec_curve *c, const ec *p) { - ecctx *cc = (ecctx *)c; field *f = c->f; int rc; mp *l = F_SQR(f, MP_NEW, p->y); mp *x = F_SQR(f, MP_NEW, p->x); mp *r = F_MUL(f, MP_NEW, x, p->x); - x = F_MUL(f, x, cc->a, p->x); + x = F_MUL(f, x, c->a, p->x); r = F_ADD(f, r, r, x); - r = F_ADD(f, r, r, cc->b); + r = F_ADD(f, r, r, c->b); rc = MP_EQ(l, r) ? 0 : -1; mp_drop(l); mp_drop(x); @@ -385,10 +376,9 @@ static int ecprojcheck(ec_curve *c, const ec *p) static void ecdestroy(ec_curve *c) { - ecctx *cc = (ecctx *)c; - MP_DROP(cc->a); - MP_DROP(cc->b); - DESTROY(cc); + MP_DROP(c->a); + MP_DROP(c->b); + DESTROY(c); } /* --- @ec_prime@, @ec_primeproj@ --- * @@ -405,30 +395,30 @@ static void ecdestroy(ec_curve *c) extern ec_curve *ec_prime(field *f, mp *a, mp *b) { - ecctx *cc = CREATE(ecctx); - cc->c.ops = &ec_primeops; - cc->c.f = f; - cc->a = F_IN(f, MP_NEW, a); - cc->b = F_IN(f, MP_NEW, b); - return (&cc->c); + ec_curve *c = CREATE(ec_curve); + c->ops = &ec_primeops; + c->f = f; + c->a = F_IN(f, MP_NEW, a); + c->b = F_IN(f, MP_NEW, b); + return (c); } extern ec_curve *ec_primeproj(field *f, mp *a, mp *b) { - ecctx *cc = CREATE(ecctx); + ec_curve *c = CREATE(ec_curve); mp *ax; ax = mp_add(MP_NEW, a, MP_THREE); ax = F_IN(f, ax, ax); if (F_ZEROP(f, ax)) - cc->c.ops = &ec_primeprojxops; + c->ops = &ec_primeprojxops; else - cc->c.ops = &ec_primeprojops; + c->ops = &ec_primeprojops; MP_DROP(ax); - cc->c.f = f; - cc->a = F_IN(f, MP_NEW, a); - cc->b = F_IN(f, MP_NEW, b); - return (&cc->c); + c->f = f; + c->a = F_IN(f, MP_NEW, a); + c->b = F_IN(f, MP_NEW, b); + return (c); } static const ec_ops ec_primeops = { @@ -463,15 +453,15 @@ int main(int argc, char *argv[]) printf("ec-prime: "); fflush(stdout); a = MP(-3); - b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1); - p = MP(6277101735386680763835789423207666416083908700390324961279); - r = MP(6277101735386680763835789423176059013767194773182842284080); + b = MP(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef); + p = MP(39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319); + r = MP(39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942642); f = field_niceprime(p); c = ec_primeproj(f, a, b); - g.x = MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012); - g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811); + g.x = MP(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7); + g.y = MP(0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f); for (i = 0; i < n; i++) { ec_mul(c, &d, &g, r); diff --git a/ec-test.c b/ec-test.c index 59acf4e..2f81015 100644 --- a/ec-test.c +++ b/ec-test.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-test.c,v 1.2 2004/03/27 00:04:46 mdw Exp $ + * $Id: ec-test.c,v 1.3 2004/03/27 17:54:11 mdw Exp $ * * Code for testing elliptic-curve stuff * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-test.c,v $ + * Revision 1.3 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.2 2004/03/27 00:04:46 mdw * Implement efficient reduction for pleasant-looking primes. * @@ -130,95 +133,20 @@ static const char *ec_name(ec_curve *cc) 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); -} +/*----- Test field types --------------------------------------------------*/ 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", "niceprime", "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_niceprime(m); mp_drop(m); break; - case 2: 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(); + qd_parse qd; + + qd.p = buf; + qd.e = 0; + if ((v = ec_curveparse(&qd)) == 0) { + fprintf(stderr, "bad curve `%.*s|%s': %s\n", + qd.p - buf, buf, qd.p, qd.e); + exit(1); } - ckend(&p); - dstr_ensure(d, sizeof(v)); *(ec_curve **)d->buf = ec_cutout(v, buf); d->len += sizeof(v); @@ -235,16 +163,18 @@ test_type type_ecurve = { ecvcvt, ecvdump }; static void eccvt(const char *p, dstr *d) { ec *a; + qd_parse qd; + qd.p = p; + qd.e = 0; 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); } + if (!ec_ptparse(&qd, a)) { + fprintf(stderr, "bad point `%.*s|%s': %s\n", qd.p - p, p, qd.p, qd.e); + exit(1); + } } static void ecdodump(ec *a, FILE *fp) diff --git a/ec.c b/ec.c index ac00c92..d4dfafb 100644 --- a/ec.c +++ b/ec.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec.c,v 1.6 2004/03/23 15:19:32 mdw Exp $ + * $Id: ec.c,v 1.7 2004/03/27 17:54:11 mdw Exp $ * * Elliptic curve definitions * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec.c,v $ + * Revision 1.7 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.6 2004/03/23 15:19:32 mdw * Test elliptic curves more thoroughly. * @@ -358,7 +361,7 @@ ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q) ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q) { - ec pp, qq; + ec pp = EC_INIT, qq = EC_INIT; EC_IN(c, &pp, p); EC_IN(c, &qq, q); EC_SUB(c, d, &pp, &qq); diff --git a/ec.h b/ec.h index d398f4a..79e3654 100644 --- a/ec.h +++ b/ec.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec.h,v 1.7 2004/03/23 15:19:32 mdw Exp $ + * $Id: ec.h,v 1.8 2004/03/27 17:54:11 mdw Exp $ * * Elliptic curve definitions * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec.h,v $ + * Revision 1.8 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.7 2004/03/23 15:19:32 mdw * Test elliptic curves more thoroughly. * @@ -74,8 +77,17 @@ /*----- Header files ------------------------------------------------------*/ -#include "field.h" -#include "mp.h" +#ifndef CATACOMB_FIELD_H +# include "field.h" +#endif + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +#ifndef CATACOMB_QDPARSE_H +# include "qdparse.h" +#endif /*----- Data structures ---------------------------------------------------*/ @@ -84,6 +96,7 @@ typedef struct ec_curve { const struct ec_ops *ops; /* Curve operations */ field *f; /* Underlying field structure */ + mp *a, *b; /* Standard params (internal form) */ } ec_curve; /* --- An elliptic curve point --- */ @@ -135,6 +148,15 @@ typedef struct ec_ops { #define EC_DBL(c, d, p) (c)->ops->dbl((c), (d), (p)) #define EC_CHECK(c, p) (c)->ops->check((c), (p)) +/* --- Elliptic curve parameters --- */ + +typedef struct ec_info { + ec_curve *c; /* The actual curve */ + ec g; /* The common point */ + mp *r; /* Order of %$g$% */ + mp *h; /* Cofactor %$h = \#E/r$% */ +} ec_info; + /*----- Simple memory management things -----------------------------------*/ /* --- @ec_create@ --- * @@ -480,6 +502,100 @@ extern ec_curve *ec_primeproj(field */*f*/, mp */*a*/, mp */*b*/); extern ec_curve *ec_bin(field */*f*/, mp */*a*/, mp */*b*/); extern ec_curve *ec_binproj(field */*f*/, mp */*a*/, mp */*b*/); +/*----- Curve parameter sets ----------------------------------------------*/ + +/* --- @ec_curveparse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * + * Returns: Elliptic curve pointer if OK, or null. + * + * Use: Parses an elliptic curve description, which has the form + * + * * a field description + * * an optional `/' + * * `prime', `primeproj', `bin', or `binproj' + * * an optional `:' + * * the %$a$% parameter + * * an optional `,' + * * the %$b$% parameter + */ + +extern ec_curve *ec_curveparse(qd_parse */*qd*/); + +/* --- @ec_ptparse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * @ec *p@ = where to put the point + * + * Returns: The point address, or null. + * + * Use: Parses an elliptic curve point. This has the form + * + * * %$x$%-coordinate + * * optional `,' + * * %$y$%-coordinate + */ + +extern ec *ec_ptparse(qd_parse */*qd*/, ec */*p*/); + +/* --- @ec_infoparse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * @ec_info *ei@ = curve information block, currently + * uninitialized + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Parses an elliptic curve information string, and stores the + * information in @ei@. This has the form + * + * * elliptic curve description + * * optional `/' + * * common point + * * optional `:' + * * group order + * * optional `*' + * * cofactor + */ + +extern int ec_infoparse(qd_parse */*qd*/, ec_info */*ei*/); + +/* --- @ec_getinfo@ --- * + * + * Arguments: @ec_info *ei@ = where to write the information + * @const char *p@ = string describing a curve + * + * Returns: Null on success, or a pointer to an error message. + * + * Use: Parses out information about a curve. The string is either a + * standard curve name, or a curve info string. + */ + +extern const char *ec_getinfo(ec_info */*ei*/, const char */*p*/); + +/* --- @ec_freeinfo@ --- * + * + * Arguments: @ec_info *ei@ = elliptic curve information block to free + * + * Returns: --- + * + * Use: Frees the information block. + */ + +extern void ec_freeinfo(ec_info */*ei*/); + +/* --- @ec_checkinfo@ --- * + * + * Arguments: @const ec_info *ei@ = elliptic curve information block + * + * Returns: Null if OK, or pointer to error message. + * + * Use: Checks an elliptic curve according to the rules in SEC1. + */ + +extern const char *ec_checkinfo(const ec_info */*ei*/, grand */*gr*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus diff --git a/ectab-canonify.pl b/ectab-canonify.pl new file mode 100644 index 0000000..e153214 --- /dev/null +++ b/ectab-canonify.pl @@ -0,0 +1,16 @@ +#! /usr/bin/perl + +while (<>) { + print, next if /^\s*(\#|$)/; + @F = split; + $k = shift @F; + print, next if $k eq "curve"; + $n = lc(join("", @F)); + if ($n =~ m"^/") { + $p = join(" + ", map("2^$_", split(m"/", substr($n, 1)))); + $n = `calc 'printf("%x", $p)'`; + } elsif ($n =~ /../ && $n !~ /^0x/) { + $n = "0x$n"; + } + print " $k $n\n"; +} diff --git a/ectab.h b/ectab.h new file mode 100644 index 0000000..d8d4302 --- /dev/null +++ b/ectab.h @@ -0,0 +1,83 @@ +/* -*-c-*- + * + * $Id: ectab.h,v 1.1 2004/03/27 17:54:11 mdw Exp $ + * + * Table of standard elliptic curves (internal) + * + * (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: ectab.h,v $ + * Revision 1.1 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * + */ + +#ifndef CATACOMB_ECTAB_H +#define CATACOMB_ECTAB_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include "ec.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct ecdata { + unsigned ftag; /* The kind of curve this is */ + const mpw *p; size_t psz; /* Modulus */ + const mpw *a; size_t asz; /* Elliptic curve parameters */ + const mpw *b; size_t bsz; + const mpw *r; size_t rsz; /* Order of common point %$g$% */ + const mpw *h; size_t hsz; /* Cofactor %$h = \#E/r$% */ + const mpw *gx; size_t gxsz; /* Common point */ + const mpw *gy; size_t gysz; +} ecdata; + +enum { + FTAG_PRIME, /* Prime but not nice */ + FTAG_NICEPRIME, /* Nice prime field */ + FTAG_BINPOLY /* Any old binary field */ +}; + +typedef struct ecentry { + const char *name; + const ecdata *data; +} ecentry; + +/*----- Global variables --------------------------------------------------*/ + +extern const ecentry ectab[]; + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/ectab.in b/ectab.in new file mode 100644 index 0000000..2de574c --- /dev/null +++ b/ectab.in @@ -0,0 +1,341 @@ +# $Id: ectab.in,v 1.1 2004/03/27 17:54:11 mdw Exp $ +# +# Standard ellipic curves + +#----- Curves from SEC2 ----------------------------------------------------- + +curve secp112r1 prime + p 0xdb7c2abf62e35e668076bead208b + a 0xdb7c2abf62e35e668076bead2088 + b 0x659ef8ba043916eede8911702b22 + r 0xdb7c2abf62e35e7628dfac6561c5 + h 1 + gx 0x09487239995a5ee76b55f9c2f098 + gy 0xa89ce5af8724c0a23e0e0ff77500 + +curve secp112r2 prime + p 0xdb7c2abf62e35e668076bead208b + a 0x6127c24c05f38a0aaaf65c0ef02c + b 0x51def1815db5ed74fcc34c85d709 + r 0x36df0aafd8b8d7597ca10520d04b + h 4 + gx 0x4ba30ab5e892b4e1649dd0928643 + gy 0xadcd46f5882e3747def36e956e97 + +curve secp128r1 niceprime + p 0xfffffffdffffffffffffffffffffffff + a 0xfffffffdfffffffffffffffffffffffc + b 0xe87579c11079f43dd824993c2cee5ed3 + r 0xfffffffe0000000075a30d1b9038a115 + h 1 + gx 0x161ff7528b899b2d0c28607ca52c5b86 + gy 0xcf5ac8395bafeb13c02da292dded7a83 + +curve secp128r2 niceprime + p 0xfffffffdffffffffffffffffffffffff + a 0xd6031998d1b3bbfebf59cc9bbff9aee1 + b 0x5eeefca380d02919dc2c6558bb6d8a5d + r 0x3fffffff7fffffffbe0024720613b5a3 + h 4 + gx 0x7b6aa5d85e572983e6fb32a7cdebc140 + gy 0x27b6916a894d3aee7106fe805fc34b44 + +curve secp160k1 niceprime + p 0xfffffffffffffffffffffffffffffffeffffac73 + a 0 + b 7 + r 0x0100000000000000000001b8fa16dfab9aca16b6b3 + h 1 + gx 0x3b4c382ce37aa192a4019e763036f4f5dd4d7ebb + gy 0x938cf935318fdced6bc28286531733c3f03c4fee + +curve secp160r1 niceprime + p 0xffffffffffffffffffffffffffffffff7fffffff + a 0xffffffffffffffffffffffffffffffff7ffffffc + b 0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45 + r 0x0100000000000000000001f4c8f927aed3ca752257 + h 1 + gx 0x4a96b5688ef573284664698968c38bb913cbfc82 + gy 0x23a628553168947d59dcc912042351377ac5fb32 + +curve secp160r2 niceprime + p 0xfffffffffffffffffffffffffffffffeffffac73 + a 0xfffffffffffffffffffffffffffffffeffffac70 + b 0xb4e134d3fb59eb8bab57274904664d5af50388ba + r 0x0100000000000000000000351ee786a818f3a1a16b + h 1 + gx 0x52dcb034293a117e1f4ff11b30f7199d3144ce6d + gy 0xfeaffef2e331f296e071fa0df9982cfea7d43f2e + +curve secp192k1 niceprime + p 0xfffffffffffffffffffffffffffffffffffffffeffffee37 + a 0 + b 3 + r 0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d + h 1 + gx 0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d + gy 0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d + +curve secp192r1 niceprime + p 0xfffffffffffffffffffffffffffffffeffffffffffffffff + a 0xfffffffffffffffffffffffffffffffefffffffffffffffc + b 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1 + r 0xffffffffffffffffffffffff99def836146bc9b1b4d22831 + h 1 + gx 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012 + gy 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811 + +curve secp224k1 niceprime + p 0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d + a 0 + b 5 + r 0x010000000000000000000000000001dce8d2ec6184caf0a971769fb1f7 + h 1 + gx 0xa1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c + gy 0x7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5 + +curve secp224r1 niceprime + p 0xffffffffffffffffffffffffffffffff000000000000000000000001 + a 0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe + b 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4 + r 0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d + h 1 + gx 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21 + gy 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34 + +curve secp256k1 niceprime + p 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f + a 0 + b 7 + r 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 + h 1 + gx 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 + gy 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 + +curve secp256r1 niceprime + p 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff + a 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc + b 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b + r 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 + h 1 + gx 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 + gy 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5 + +curve secp384r1 niceprime + p 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff + a 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc + b 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef + r 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 + h 1 + gx 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7 + gy 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f + +curve secp521r1 niceprime + p 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + a 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc + b 0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00 + r 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409 + h 1 + gx 0x00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66 + gy 0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650 + +curve sect113r1 binpoly + p 0x20000000000000000000000000201 + a 0x003088250ca6e7c7fe649ce85820f7 + b 0x00e8bee4d3e2260744188be0e9c723 + r 0x0100000000000000d9ccec8a39e56f + h 2 + gx 0x009d73616f35f4ab1407d73562c10f + gy 0x00a52830277958ee84d1315ed31886 + +curve sect113r2 binpoly + p 0x20000000000000000000000000201 + a 0x00689918dbec7e5a0dd6dfc0aa55c7 + b 0x0095e9a9ec9b297bd4bf36e059184f + r 0x010000000000000108789b2496af93 + h 2 + gx 0x01a57a6a7b26ca5ef52fcdb8164797 + gy 0x00b3adc94ed1fe674c06e695baba1d + +curve sect131r1 binpoly + p 0x80000000000000000000000000000010d + a 0x07a11b09a76b562144418ff3ff8c2570b8 + b 0x0217c05610884b63b9c6c7291678f9d341 + r 0x0400000000000000023123953a9464b54d + h 2 + gx 0x0081baf91fdf9833c40f9c181343638399 + gy 0x078c6e7ea38c001f73c8134b1b4ef9e150 + +curve sect131r2 binpoly + p 0x80000000000000000000000000000010d + a 0x03e5a88919d7cafcbf415f07c2176573b2 + b 0x04b8266a46c55657ac734ce38f018f2192 + r 0x0400000000000000016954a233049ba98f + h 2 + gx 0x0356dcd8f2f95031ad652d23951bb366a8 + gy 0x0648f06d867940a5366d9e265de9eb240f + +curve sect163k1 binpoly + p 0x800000000000000000000000000000000000000c9 + a 1 + b 1 + r 0x04000000000000000000020108a2e0cc0d99f8a5ef + h 2 + gx 0x02fe13c0537bbc11acaa07d793de4e6d5e5c94eee8 + gy 0x0289070fb05d38ff58321f2e800536d538ccdaa3d9 + +curve sect163r1 binpoly + p 0x800000000000000000000000000000000000000c9 + a 0x07b6882caaefa84f9554ff8428bd88e246d2782ae2 + b 0x0713612dcddcb40aab946bda29ca91f73af958afd9 + r 0x03ffffffffffffffffffff48aab689c29ca710279b + h 2 + gx 0x0369979697ab43897789566789567f787a7876a654 + gy 0x00435edb42efafb2989d51fefce3c80988f41ff883 + +curve sect163r2 binpoly + p 0x800000000000000000000000000000000000000c9 + a 1 + b 0x020a601907b8c953ca1481eb10512f78744a3205fd + r 0x040000000000000000000292fe77e70c12a4234c33 + h 2 + gx 0x03f0eba16286a2d57ea0991168d4994637e8343e36 + gy 0x00d51fbc6c71a0094fa2cdd545b11c5c0c797324f1 + +curve sect193r1 binpoly + p 0x2000000000000000000000000000000000000000000008001 + a 0x0017858feb7a98975169e171f77b4087de098ac8a911df7b01 + b 0x00fdfb49bfe6c3a89facadaa7a1e5bbc7cc1c2e5d831478814 + r 0x01000000000000000000000000c7f34a778f443acc920eba49 + h 2 + gx 0x01f481bc5f0ff84a74ad6cdf6fdef4bf6179625372d8c0c5e1 + gy 0x0025e399f2903712ccf3ea9e3a1ad17fb0b3201b6af7ce1b05 + +curve sect193r2 binpoly + p 0x2000000000000000000000000000000000000000000008001 + a 0x0163f35a5137c2ce3ea6ed8667190b0bc43ecd69977702709b + b 0x00c9bb9e8927d4d64c377e2ab2856a5b16e3efb7f61d4316ae + r 0x010000000000000000000000015aab561b005413ccd4ee99d5 + h 2 + gx 0x00d9b67d192e0367c803f39e1a7e82ca14a651350aae617e8f + gy 0x01ce94335607c304ac29e7defbd9ca01f596f927224cdecf6c + +curve sect233k1 binpoly + p 0x20000000000000000000000000000000000000004000000000000000001 + a 0 + b 1 + r 0x8000000000000000000000000000069d5bb915bcd46efb1ad5f173abdf + h 4 + gx 0x017232ba853a7e731af129f22ff4149563a419c26bf50a4c9d6eefad6126 + gy 0x01db537dece819b7f70f555a67c427a8cd9bf18aeb9b56e0c11056fae6a3 + +curve sect233r1 binpoly + p 0x20000000000000000000000000000000000000004000000000000000001 + a 1 + b 0x0066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad + r 0x01000000000000000000000000000013e974e72f8a6922031d2603cfe0d7 + h 2 + gx 0x00fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b + gy 0x01006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052 + +curve sect239k1 binpoly + p 0x800000000000000000004000000000000000000000000000000000000001 + a 0 + b 1 + r 0x2000000000000000000000000000005a79fec67cb6e91f1c1da800e478a5 + h 4 + gx 0x29a0b6a887a983e9730988a68727a8b2d126c44cc2cc7b2a6555193035dc + gy 0x76310804f12e549bdb011c103089e73510acb275fc312a5dc6b76553f0ca + +curve sect283k1 binpoly + p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 + a 0 + b 1 + r 0x01ffffffffffffffffffffffffffffffffffe9ae2ed07577265dff7f94451e061e163c61 + h 4 + gx 0x0503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836 + gy 0x01ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259 + +curve sect283r1 binpoly + p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 + a 1 + b 0x027b680ac8b8596da5a4af8a19a0303fca97fd7645309fa2a581485af6263e313b79a2f5 + r 0x03ffffffffffffffffffffffffffffffffffef90399660fc938a90165b042a7cefadb307 + h 2 + gx 0x05f939258db7dd90e1934f8c70b0dfec2eed25b8557eac9c80e2e198f8cdbecd86b12053 + gy 0x03676854fe24141cb98fe6d4b20d02b4516ff702350eddb0826779c813f0df45be8112f4 + +curve sect409k1 binpoly + p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 + a 0 + b 1 + r 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffe5f83b2d4ea20400ec4557d5ed3e3e7ca5b4b5c83b8e01e5fcf + h 4 + gx 0x0060f05f658f49c1ad3ab1890f7184210efd0987e307c84c27accfb8f9f67cc2c460189eb5aaaa62ee222eb1b35540cfe9023746 + gy 0x01e369050b7c4e42acba1dacbf04299c3460782f918ea427e6325165e9ea10e3da5f6c42e9c55215aa9ca27a5863ec48d8e0286b + +curve sect409r1 binpoly + p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 + a 1 + b 0x0021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f + r 0x010000000000000000000000000000000000000000000000000001e2aad6a612f33307be5fa47c3c9e052f838164cd37d9a21173 + h 2 + gx 0x015d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7 + gy 0x0061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706 + +curve sect571k1 binpoly + p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 + a 0 + b 1 + r 0x020000000000000000000000000000000000000000000000000000000000000000000000131850e1f19a63e4b391a8db917f4138b630d84be5d639381e91deb45cfe778f637c1001 + h 4 + gx 0x026eb7a859923fbc82189631f8103fe4ac9ca2970012d5d46024804801841ca44370958493b205e647da304db4ceb08cbbd1ba39494776fb988b47174dca88c7e2945283a01c8972 + gy 0x0349dc807f4fbf374f4aeade3bca95314dd58cec9f307a54ffc61efc006d8a2c9d4979c0ac44aea74fbebbb9f772aedcb620b01a7ba7af1b320430c8591984f601cd4c143ef1c7a3 + +curve sect571r1 binpoly + p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 + a 1 + b 0x02f40e7e2221f295de297117b7f3d62f5c6a97ffcb8ceff1cd6ba8ce4a9a18ad84ffabbd8efa59332be7ad6756a66e294afd185a78ff12aa520e4de739baca0c7ffeff7f2955727a + r 0x03ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe661ce18ff55987308059b186823851ec7dd9ca1161de93d5174d66e8382e9bb2fe84e47 + h 2 + gx 0x0303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19 + gy 0x037bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b + +#----- Curves from RFC2414 (Oakley) ----------------------------------------- +# +# oakley155 has too large a cofactor +# oakley185's group has composite order; we double the generator to +# produce a group of composite order + +curve oakley185 binpoly + p 0x020000000000000000000000000000200000000000000001 + a 0 + b 0x1ee9 + r 0x007ffffffffffffffffffffff6fcbe226dcf92105d7e53af + h 4 + gx 0x1bd555555555555555555555555554e8000000000000158 + gy 0x14e999999999999999999999999998d7000000000001fe6 + +#----- NIST curves from FIPS186-2 ------------------------------------------- +# +# Most of these are duplicates of SEC2 curves. + +alias nist-p192 secp192r1 +alias nist-p224 secp224r1 +alias nist-p256 secp256r1 +alias nist-p384 secp384r1 +alias nist-p521 secp521r1 + +alias nist-k163 sect163k1 +alias nist-k233 sect233k1 +alias nist-k283 sect283k1 +alias nist-k409 sect409k1 +alias nist-k571 sect571k1 + +alias nist-b163 sect163r2 +alias nist-b233 sect233r1 +alias nist-b283 sect283r1 +alias nist-b409 sect409r1 +alias nist-b571 sect571r1 + +#----- That's all, folks ---------------------------------------------------- diff --git a/f-binpoly.c b/f-binpoly.c index 1da5d12..bd4d8b0 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-binpoly.c,v 1.4 2004/03/23 15:19:32 mdw Exp $ + * $Id: f-binpoly.c,v 1.5 2004/03/27 17:54:11 mdw Exp $ * * Binary fields with polynomial basis representation * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-binpoly.c,v $ + * Revision 1.5 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.4 2004/03/23 15:19:32 mdw * Test elliptic curves more thoroughly. * @@ -71,10 +74,9 @@ static void fdestroy(field *ff) DESTROY(f); } -static mp *frand(field *ff, mp *d, grand *r) +static mp *frand(field *f, mp *d, grand *r) { - fctx *f = (fctx *)ff; - return (mprand(d, mp_octets(f->r.p) - 1, r, 0)); + return (mprand(d, f->nbits, r, 0)); } static int fzerop(field *ff, mp *x) @@ -152,7 +154,10 @@ field *field_binpoly(mp *p) f->f.ops = &fops; f->f.zero = MP_ZERO; f->f.one = MP_ONE; + f->f.nbits = mp_bits(p) - 1; + f->f.noctets = (f->f.nbits + 7) >> 3; gfreduce_create(&f->r, p); + f->f.m = f->r.p; return (&f->f); } diff --git a/f-niceprime.c b/f-niceprime.c index c34e24e..b4b4091 100644 --- a/f-niceprime.c +++ b/f-niceprime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-niceprime.c,v 1.1 2004/03/27 00:04:46 mdw Exp $ + * $Id: f-niceprime.c,v 1.2 2004/03/27 17:54:11 mdw Exp $ * * Prime fields with efficient reduction for special-form primes * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-niceprime.c,v $ + * Revision 1.2 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.1 2004/03/27 00:04:46 mdw * Implement efficient reduction for pleasant-looking primes. * @@ -203,7 +206,10 @@ field *field_niceprime(mp *p) f->f.ops = &fops; f->f.zero = MP_ZERO; f->f.one = MP_ONE; + f->f.nbits = mp_bits(p); + f->f.noctets = (f->f.nbits + 7) >> 3; mpreduce_create(&f->r, p); + f->f.m = f->r.p; return (&f->f); } diff --git a/f-prime.c b/f-prime.c index 08ed300..a82f3a0 100644 --- a/f-prime.c +++ b/f-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-prime.c,v 1.6 2004/03/23 15:19:32 mdw Exp $ + * $Id: f-prime.c,v 1.7 2004/03/27 17:54:11 mdw Exp $ * * Prime fields with Montgomery arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-prime.c,v $ + * Revision 1.7 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.6 2004/03/23 15:19:32 mdw * Test elliptic curves more thoroughly. * @@ -246,6 +249,9 @@ field *field_prime(mp *p) mpmont_create(&f->mm, p); f->f.zero = MP_ZERO; f->f.one = f->mm.r; + f->f.m = f->mm.m; + f->f.nbits = mp_bits(p); + f->f.noctets = (f->f.nbits + 7) >> 3; return (&f->f); } diff --git a/field-parse.c b/field-parse.c new file mode 100644 index 0000000..0a09e57 --- /dev/null +++ b/field-parse.c @@ -0,0 +1,86 @@ +/* -*-c-*- + * + * $Id: field-parse.c,v 1.1 2004/03/27 17:54:11 mdw Exp $ + * + * Parse field descriptions + * + * (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: field-parse.c,v $ + * Revision 1.1 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "field.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @field_parse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * + * Returns: Field pointer if OK, or null. + * + * Use: Parses a field description, which has the form + * + * * `prime', `niceprime' or `binpoly' + * * an optional `:' + * * the field modulus + */ + +field *field_parse(qd_parse *qd) +{ + field *f; + mp *m = MP_NEW; + + switch (qd_enum(qd, "prime,niceprime,binpoly")) { + case 0: + qd_delim(qd, ':'); + if ((m = qd_getmp(qd)) == 0) return (0); + f = field_prime(m); + break; + case 1: + qd_delim(qd, ':'); + if ((m = qd_getmp(qd)) == 0) return (0); + f = field_niceprime(m); + break; + case 2: + qd_delim(qd, ':'); + if ((m = qd_getmp(qd)) == 0) return (0); + f = field_binpoly(m); + break; + default: + f = 0; + break; + } + mp_drop(m); + return (f); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/field.h b/field.h index 21ac7dd..7af9b4f 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field.h,v 1.7 2004/03/27 00:04:46 mdw Exp $ + * $Id: field.h,v 1.8 2004/03/27 17:54:11 mdw Exp $ * * Definitions for field arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: field.h,v $ + * Revision 1.8 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.7 2004/03/27 00:04:46 mdw * Implement efficient reduction for pleasant-looking primes. * @@ -76,11 +79,18 @@ # include "mp.h" #endif +#ifndef CATACOMB_QDPARSE_H +# include "qdparse.h" +#endif + /*----- Data structures ---------------------------------------------------*/ typedef struct field { const struct field_ops *ops; /* Field operations */ mp *zero, *one; /* Identities in the field */ + mp *m; /* Modulus (prime and binary) */ + unsigned long nbits; /* Length of field element in bits */ + size_t noctets; /* Length of element in octets */ } field; enum { @@ -206,6 +216,21 @@ extern field *field_niceprime(mp */*p*/); extern field *field_binpoly(mp */*p*/); +/* --- @field_parse@ --- * + * + * Arguments: @qd_parse *qd@ = parser context + * + * Returns: Field pointer if OK, or null. + * + * Use: Parses a field description, which has the form + * + * * `prime', `niceprime' or `binpoly' + * * an optional `:' + * * the field modulus + */ + +extern field *field_parse(qd_parse */*qd*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus diff --git a/gf-arith.c b/gf-arith.c index debfba1..209c3fc 100644 --- a/gf-arith.c +++ b/gf-arith.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: gf-arith.c,v 1.2 2004/03/21 22:52:06 mdw Exp $ + * $Id: gf-arith.c,v 1.3 2004/03/27 17:54:11 mdw Exp $ * * Basic arithmetic on binary polynomials * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: gf-arith.c,v $ + * Revision 1.3 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.2 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -85,8 +88,8 @@ mp *gf_mul(mp *d, mp *a, mp *b) size_t m = MAX(MP_LEN(a), MP_LEN(b)); mpw *s; MP_DEST(d, 2 * m, a->f | b->f | MP_UNDEF); - s = mpalloc(d->a, 2 * m); - gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 2 * m); + s = mpalloc(d->a, 3 * m); + gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 3 * m); mpfree(d->a, s); } @@ -181,6 +184,33 @@ void gf_div(mp **qq, mp **rr, mp *a, mp *b) } } +/* --- @gf_irreduciblep@ --- * + * + * Arguments: @mp *f@ = a polynomial + * + * Returns: Nonzero if the polynomial is irreducible; otherwise zero. + */ + +int gf_irreduciblep(mp *f) +{ + unsigned long m = mp_bits(f) - 1; + mp *u = MP_TWO; + mp *v = MP_NEW; + + m /= 2; + while (m) { + u = gf_sqr(u, u); + gf_div(0, &u, u, f); + v = gf_add(v, u, MP_TWO); + gf_gcd(&v, 0, 0, v, f); + if (!MP_EQ(v, MP_ONE)) break; + m--; + } + MP_DROP(u); + MP_DROP(v); + return (!m); +} + /*----- Test rig ----------------------------------------------------------*/ #ifdef TEST_RIG @@ -246,11 +276,30 @@ static int tdiv(dstr *v) return (ok); } +static int tirred(dstr *v) +{ + mp *a = *(mp **)v[0].buf; + int r = *(int *)v[1].buf; + int c = gf_irreduciblep(a); + int ok = 1; + if (r != c) { + ok = 0; + fprintf(stderr, "\n*** irred failed"); + fputs("\n*** a = ", stderr); mp_writefile(a, stderr, 16); + fprintf(stderr, "\n*** r = %d\n", r); + fprintf(stderr, "*** c = %d\n", c); + } + mp_drop(a); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + static test_chunk tests[] = { { "add", tadd, { &type_mp, &type_mp, &type_mp, 0 } }, { "mul", tmul, { &type_mp, &type_mp, &type_mp, 0 } }, { "sqr", tsqr, { &type_mp, &type_mp, 0 } }, { "div", tdiv, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, + { "irred", tirred, { &type_mp, &type_int, 0 } }, { 0, 0, { 0 } }, }; diff --git a/gf.h b/gf.h index ebf67f1..fba801c 100644 --- a/gf.h +++ b/gf.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: gf.h,v 1.2 2004/03/21 22:52:06 mdw Exp $ + * $Id: gf.h,v 1.3 2004/03/27 17:54:11 mdw Exp $ * * Arithmetic on binary polynomials * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: gf.h,v $ + * Revision 1.3 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.2 2004/03/21 22:52:06 mdw * Merge and close elliptic curve branch. * @@ -102,6 +105,15 @@ extern mp *gf_sqr(mp */*d*/, mp */*a*/); extern void gf_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/); +/* --- @gf_irreduciblep@ --- * + * + * Arguments: @mp *f@ = a polynomial + * + * Returns: Nonzero if the polynomial is irreducible; otherwise zero. + */ + +extern int gf_irreduciblep(mp */*f*/); + /* --- @gf_gcd@ --- * * * Arguments: @mp **gcd, **xx, **yy@ = where to write the results diff --git a/gfx-kmul.c b/gfx-kmul.c index f5390f4..c692f9c 100644 --- a/gfx-kmul.c +++ b/gfx-kmul.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: gfx-kmul.c,v 1.2 2002/10/09 00:36:03 mdw Exp $ + * $Id: gfx-kmul.c,v 1.3 2004/03/27 17:54:11 mdw Exp $ * * Karatsuba's multiplication algorithm on binary polynomials * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: gfx-kmul.c,v $ + * Revision 1.3 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.2 2002/10/09 00:36:03 mdw * Fix bounds on workspace for Karatsuba operations. * @@ -139,8 +142,8 @@ void gfx_kmul(mpw *dv, mpw *dvl, mpw *bsv = sv + m, *ssv = bsv + m; mpw *rdv = dv + m, *rdvl = rdv + 2 * m; - assert(rdvl < dvl); - assert(ssv < svl); + assert(rdvl <= dvl); + assert(ssv <= svl); UXOR2(sv, bsv, av, avm, avm, avl); UXOR2(bsv, ssv, bv, bvm, bvm, bvl); if (m > GFK_THRESH) diff --git a/mp-sqrt.c b/mp-sqrt.c index 7b65ec0..83880f9 100644 --- a/mp-sqrt.c +++ b/mp-sqrt.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-sqrt.c,v 1.3 2001/02/03 12:00:29 mdw Exp $ + * $Id: mp-sqrt.c,v 1.4 2004/03/27 17:54:11 mdw Exp $ * * Compute integer square roots * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-sqrt.c,v $ + * Revision 1.4 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * * Revision 1.3 2001/02/03 12:00:29 mdw * Now @mp_drop@ checks its argument is non-NULL before attempting to free * it. Note that the macro version @MP_DROP@ doesn't do this. @@ -85,7 +88,6 @@ mp *mp_sqrt(mp *d, mp *a) z >>= 1; mp_copy(a); d = mp_lsr(d, a, z); - mp_drop(a); /* --- Main approximation --- * * @@ -118,6 +120,7 @@ mp *mp_sqrt(mp *d, mp *a) /* --- Finished, at last --- */ + mp_drop(a); mp_drop(q); mp_drop(r); return (d); diff --git a/mpdump.c b/mpdump.c new file mode 100644 index 0000000..5a8030f --- /dev/null +++ b/mpdump.c @@ -0,0 +1,82 @@ +/* -*-c-*- + * + * $Id: mpdump.c,v 1.1 2004/03/27 17:54:11 mdw Exp $ + * + * Dump a multiprecision integer as C data + * + * (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: mpdump.c,v $ + * Revision 1.1 2004/03/27 17:54:11 mdw + * Standard curves and curve checking. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "mp.h" + +/*----- Main code ---------------------------------------------------------*/ + +int main(int argc, char *argv[]) +{ + mp *x; + int i; + int w, n; + + if (argc != 2) { + fprintf(stderr, "%s: missing argument\n", argv[0]); + return (1); + } + if ((x = mp_readstring(0, argv[1], 0, 0)) == 0) { + fprintf(stderr, "%s: bad integer `%s'", argv[0], argv[1]); + return (1); + } + fputs(" ", stdout); + w = (MPW_BITS + 3)/4; + n = 1; + while (2 + 2 * n * (4 + w) < 72) n <<= 1; + i = 0; + for (;;) { + printf("0x%0*x", w, x->v[i]); + i++; + if (i >= MP_LEN(x)) break; + fputs(",", stdout); + if (i % n) fputs(" ", stdout); else fputs("\n ", stdout); + } + if (fflush(stdout) || ferror(stdout)) { + fprintf(stderr, "%s: error writing data: %s", argv[0], strerror(errno)); + return (1); + } + fputs("\n", stdout); + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/mpx-kmul.c b/mpx-kmul.c index 1981a28..228cabd 100644 --- a/mpx-kmul.c +++ b/mpx-kmul.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx-kmul.c,v 1.8 2002/10/09 00:36:03 mdw Exp $ + * $Id: mpx-kmul.c,v 1.9 2004/03/27 17:54:12 mdw Exp $ * * Karatsuba's multiplication algorithm * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx-kmul.c,v $ + * Revision 1.9 2004/03/27 17:54:12 mdw + * Standard curves and curve checking. + * * Revision 1.8 2002/10/09 00:36:03 mdw * Fix bounds on workspace for Karatsuba operations. * @@ -158,8 +161,8 @@ void mpx_kmul(mpw *dv, mpw *dvl, mpw *bsv = sv + m + 1, *ssv = bsv + m + 1; mpw *rdv = dv + m, *rdvl = rdv + 2 * (m + 2); - assert(rdvl < dvl); - assert(ssv < svl); + assert(rdvl <= dvl); + assert(ssv <= svl); UADD2(sv, bsv, av, avm, avm, avl); UADD2(bsv, ssv, bv, bvm, bvm, bvl); if (m > MPK_THRESH) diff --git a/qdparse.c b/qdparse.c new file mode 100644 index 0000000..2fe6998 --- /dev/null +++ b/qdparse.c @@ -0,0 +1,151 @@ +/* -*-c-*- + * + * $Id: qdparse.c,v 1.1 2004/03/27 17:54:12 mdw Exp $ + * + * Quick-and-dirty parser + * + * (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: qdparse.c,v $ + * Revision 1.1 2004/03/27 17:54:12 mdw + * Standard curves and curve checking. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include + +#include "qdparse.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @qd_skipspc@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: --- + * + * Use: Skips spaces in the string. No errors. + */ + +void qd_skipspc(qd_parse *qd) +{ + while (isspace((unsigned char)*qd->p)) + qd->p++; +} + +/* --- @qd_delim@ --- * + * + * Arguments: @qd_parse *qd@ = context + * @int ch@ = character to compare with + * + * Returns: Nonzero if it was, zero if it wasn't. + * + * Use: Checks the next (non-whitespace) character is what we + * expect. If it is, the character is eaten; otherwise it's no + * big deal. + */ + +int qd_delim(qd_parse *qd, int ch) +{ + qd_skipspc(qd); + if (*qd->p != ch) + return (0); + qd->p++; + return (1); +} + +/* --- @qd_enum@ --- * + * + * Arguments: @qd_parse *qd@ = context + * @const char *e@ = list of enum strings, space separated + * + * Returns: Index of the string matched, or @-1@. + * + * Use: Matches a keyword. + */ + +int qd_enum(qd_parse *qd, const char *e) +{ + size_t n; + int i = 0; + + qd_skipspc(qd); + for (;;) { + e += strspn(e, ", "); + if (!*e) break; + n = strcspn(e, ", "); + if (strncmp(qd->p, e, n) == 0 && !isalnum((unsigned char)qd->p[n])) { + qd->p += n; + return (i); + } + i++; e += n; + } + qd->e = "unrecognized keyword"; + return (-1); +} + +/* --- @qd_getmp@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: The integer extracted, or null. + * + * Use: Parses a multiprecision integer from a string. + */ + +mp *qd_getmp(qd_parse *qd) +{ + char *q; + mp *m; + + qd_skipspc(qd); + m = mp_readstring(MP_NEW, qd->p, &q, 0); + if (m && !isalnum((unsigned char)*q)) + qd->p = q; + else { + mp_drop(m); + qd->e = "bad number"; + } + return (m); +} + +/* --- @qd_eofp@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: Nonzero if at EOF, zero otherwise. + */ + +int qd_eofp(qd_parse *qd) +{ + qd_skipspc(qd); + return (!*qd->p); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/qdparse.h b/qdparse.h new file mode 100644 index 0000000..078b344 --- /dev/null +++ b/qdparse.h @@ -0,0 +1,123 @@ +/* -*-c-*- + * + * $Id: qdparse.h,v 1.1 2004/03/27 17:54:12 mdw Exp $ + * + * Quick-and-dirty parser + * + * (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: qdparse.h,v $ + * Revision 1.1 2004/03/27 17:54:12 mdw + * Standard curves and curve checking. + * + */ + +#ifndef CATACOMB_QDPARSE_H +#define CATACOMB_QDPARSE_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct qd_parse { + const char *p; /* Where we are right now */ + const char *e; /* Error string (output) */ +} qd_parse; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @qd_skipspc@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: --- + * + * Use: Skips spaces in the string. No errors. + */ + +extern void qd_skipspc(qd_parse */*qd*/); + +/* --- @qd_delim@ --- * + * + * Arguments: @qd_parse *qd@ = context + * @int ch@ = character to compare with + * + * Returns: Nonzero if it was, zero if it wasn't. + * + * Use: Checks the next (non-whitespace) character is what we + * expect. If it is, the character is eaten; otherwise it's no + * big deal. + */ + +extern int qd_delim(qd_parse */*qd*/, int /*ch*/); + +/* --- @qd_enum@ --- * + * + * Arguments: @qd_parse *qd@ = context + * @const char *e@ = list of enum strings, space separated + * + * Returns: Index of the string matched, or @-1@. + * + * Use: Matches a keyword. + */ + +extern int qd_enum(qd_parse */*qd*/, const char */*e*/); + +/* --- @qd_getmp@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: The integer extracted, or null. + * + * Use: Parses a multiprecision integer from a string. + */ + +extern mp *qd_getmp(qd_parse */*qd*/); + +/* --- @qd_eofp@ --- * + * + * Arguments: @qd_parse *qd@ = context + * + * Returns: Nonzero if at EOF, zero otherwise. + */ + +extern int qd_eofp(qd_parse */*qd*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/tests/ec b/tests/ec index 1ea76ff..aba2b58 100644 --- a/tests/ec +++ b/tests/ec @@ -1,4 +1,4 @@ -# $Id: ec,v 1.2 2004/03/27 00:04:46 mdw Exp $ +# $Id: ec,v 1.3 2004/03/27 17:54:12 mdw Exp $ # # Elliptic curve tests @@ -236,6 +236,12 @@ dbl { 0x325f41d0ef702dc310254c42d65851a3b91471ac7" "0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4, 0x49ed3be7f510e30e2462c517ad39038e493fc573c"; + + "binpoly: 0x020000000000000000000000000000200000000000000001 + bin: 0, 0x1ee9" + "0x18, 0xd" + "0x1bd555555555555555555555555554e8000000000000158, + 0x14e999999999999999999999999998d7000000000001fe6"; } add { diff --git a/tests/gf b/tests/gf index bbb1514..df5b793 100644 --- a/tests/gf +++ b/tests/gf @@ -1,4 +1,4 @@ -# $Id: gf,v 1.2 2004/03/21 22:52:06 mdw Exp $ +# $Id: gf,v 1.3 2004/03/27 17:54:12 mdw Exp $ # # Test cases for higher-level binary poly arithmetic. @@ -51,6 +51,12 @@ div { 0x398c4111da6d06cdf3d83704ee403101; } +irred { + 0xc1a7bd3b4e853fc92d4e1588719986aa 0; + 0x800000000000000000000000000000000000000c9 1; + 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 1; +} + gcd { 0xc1a7bd3b4e853fc92d4e1588719986aa 0xbe1f8593ee2c6f8f9497cc7335d97111 @@ -63,6 +69,11 @@ gcd { 0x35a8e33503b3695be00528f8b82db931 0x283ed59f1226dcefa7ff0ef87ceff5d5; 0x800000000000000000000000000000000000000c9 + 4 + 1 + 1 + 0x20000000000000000000000000000000000000032; + 0x800000000000000000000000000000000000000c9 0x3f0eba16286a2d57ea0991168d4994637e8343e36 1 0xa17e704470d80cb5a78f295db0ce543dda16a169 diff --git a/tests/gfreduce b/tests/gfreduce index 2688a0c..f548b95 100644 --- a/tests/gfreduce +++ b/tests/gfreduce @@ -1,4 +1,4 @@ -# $Id: gfreduce,v 1.3 2004/03/23 15:19:32 mdw Exp $ +# $Id: gfreduce,v 1.4 2004/03/27 17:54:12 mdw Exp $ # # Test efficient polynomial reduction @@ -39,10 +39,10 @@ modexp { sqrt { 0x20000000000000000000000000000000000000000000000000000000000001001 0x1f081e69f45d3254530766ab98d55fa612c7bb27ea31bc2621d894be9c0b196b3 - 0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b4e853fc92d4e1588719986aa; + 0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b4e853fc92d4e1588719986aa; 0x10000000000000000000000000000000000000000003 - 0x4594094509835690805698083560980459903450984 - 0x820291881a244a02840a2f8ece3f23f88f38bf0b3a; + 0x4594094509835690805698083560980459903450984 + 0x820291881a244a02840a2f8ece3f23f88f38bf0b3a; } halftrace { -- 2.11.0