From: mdw Date: Thu, 1 Apr 2004 21:28:47 +0000 (+0000) Subject: Normal basis support (translates to poly basis internally). Rewrite X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/4edc47b89bc56cd4041fdb0f4e8e892acd589ed8 Normal basis support (translates to poly basis internally). Rewrite EC and prime group table generators in awk, so that they can reuse data for repeated constants. --- diff --git a/Makefile.m4 b/Makefile.m4 index 7adc8d8..e15b5eb 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-m4-*- ## -## $Id: Makefile.m4,v 1.76 2004/04/01 12:59:40 mdw Exp $ +## $Id: Makefile.m4,v 1.77 2004/04/01 21:28:41 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,6 +29,11 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ +## Revision 1.77 2004/04/01 21:28:41 mdw +## Normal basis support (translates to poly basis internally). Rewrite +## EC and prime group table generators in awk, so that they can reuse data +## for repeated constants. +## ## Revision 1.76 2004/04/01 12:59:40 mdw ## Ooops! qdparse needs mp headers. ## @@ -351,12 +356,12 @@ 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 +ectab.c: ectab.in ec-gentab.awk mpdump + $(srcdir)/ec-gentab.awk <$(srcdir)/ectab.in >ectab.c.new mv ectab.c.new ectab.c -ptab.c: ptab.in p-gentab.sh mpdump - $(srcdir)/p-gentab.sh <$(srcdir)/ptab.in >ptab.c.new +ptab.c: ptab.in p-gentab.awk mpdump + $(srcdir)/p-gentab.awk <$(srcdir)/ptab.in >ptab.c.new mv ptab.c.new ptab.c BUILT_SOURCES = \ @@ -382,7 +387,7 @@ pkginclude_HEADERS = \ mpx.h bitops.h mpw.h mpscan.h mparena.h mp.h mptext.h mpint.h \ exp.h mpbarrett.h mpmont.h mpreduce.h \ mpcrt.h mprand.h mpmul.h \ - gfx.h gf.h gfreduce.h \ + gfx.h gf.h gfreduce.h gfn.h \ primetab.h pfilt.h rabin.h \ pgen.h prim.h strongprime.h limlee.h keycheck.h \ bbs.h rsa.h dh.h dsarand.h dsa.h \ @@ -413,7 +418,7 @@ define(`MP_SOURCES', define(`GF_SOURCES', `gfx.c gfx-kmul.c gfx-sqr.c gf-arith.c gf-gcd.c \ - gfreduce.c gfreduce-exp.h') + gfreduce.c gfreduce-exp.h gfn.c') define(`EC_SOURCES', `field.c field-parse.c f-prime.c f-niceprime.c f-binpoly.c \ @@ -536,7 +541,7 @@ man_MANS = key.1 hashsum.1 keyring.5 pixie.1 EXTRA_DIST = \ Makefile.m4 genmodes $(man_MANS) xpixie group-test.c \ - ectab.in ec-gentab.sh ptab.in p-gentab.sh \ + ectab.in ec-gentab.awk ptab.in p-gentab.awk \ README.cipher README.hash README.random README.mp \ debian/rules debian/copyright debian/control debian/changelog \ debian/catacomb-bin.postinst debian/catacomb-bin.config \ @@ -603,6 +608,7 @@ CTESTRIG(gfx-kmul) CTESTRIG(gf-arith) CTESTRIG(gf-gcd) CTESTRIG(gfreduce) +CTESTRIG(gfn) CTESTRIG(ec-prime) CTESTRIG(ec-bin) CTESTRIG(ec-test) diff --git a/ec-bin.c b/ec-bin.c index 36c5098..db1bebf 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-bin.c,v 1.6 2004/04/01 12:50:09 mdw Exp $ + * $Id: ec-bin.c,v 1.7 2004/04/01 21:28:41 mdw Exp $ * * Arithmetic for elliptic curves over binary fields * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-bin.c,v $ + * Revision 1.7 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.6 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -395,7 +400,7 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b) cc->c.f = f; 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, MP_NEW, cc->c.b); cc->bb = F_SQRT(f, cc->bb, cc->bb); return (&cc->c); } @@ -421,22 +426,21 @@ int main(int argc, char *argv[]) field *f; ec_curve *c; ec g = EC_INIT, d = EC_INIT; - mp *p, *a, *b, *r; + mp *p, *a, *b, *r, *beta; int i, n = argc == 1 ? 1 : atoi(argv[1]); printf("ec-bin: "); fflush(stdout); - a = MP(1); - b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f); - p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001); - r = - MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770); + a = MP(0x7ffffffffffffffffffffffffffffffffffffffff); + b = MP(0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb); + p = MP(0x800000000000000000000000000000000000000c9); + beta = MP(0x715169c109c612e390d347c748342bcd3b02a0bef); + r = MP(0x040000000000000000000292fe77e70c12a4234c32); - f = field_binpoly(p); + f = field_binnorm(p, beta); c = ec_binproj(f, a, b); - - g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7); - g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706); + g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8); + g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f); for (i = 0; i < n; i++) { ec_mul(c, &d, &g, r); @@ -457,7 +461,7 @@ int main(int argc, char *argv[]) ec_destroy(&g); ec_destroycurve(c); F_DESTROY(f); - MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); + MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); MP_DROP(beta); assert(!mparena_count(&mparena_global)); printf("ok\n"); return (0); diff --git a/ec-gentab.awk b/ec-gentab.awk new file mode 100755 index 0000000..b00300c --- /dev/null +++ b/ec-gentab.awk @@ -0,0 +1,116 @@ +#! /usr/bin/awk -f +# +# $Id: ec-gentab.awk,v 1.1 2004/04/01 21:28:41 mdw Exp $ + +function banner(name, s, i) +{ + s = "/*----- " name " "; + while (length(s) < 75) s = s "-"; + return (s "*/"); +} + +function fix(name) +{ + gsub(/[^0-9A-Za-z_]+/, "_", name); + return (name); +} + +BEGIN { + print "/* -*-c-*-"; + print " *"; + print " * Table of elliptic curves [generated]"; + print " */"; + print ""; + print "#include \"ectab.h\""; + print ""; + print "#define N(x) (sizeof(x)/sizeof(*x))"; + print "#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }"; + print "#define NOMP { 0, 0, 0, 0, 0 }"; + print ""; + print banner("Curve data"); + print ""; + + d_i = 0; + name = ""; +} + +function putmp(x, d) +{ + if (!(x in data)) { + print "curve " name ": missing " x >"/dev/stderr"; + exit 1; + } + d = data[x]; + if (!(d in cache)) { + n = "c_" fix(name) "_" x; + print "static mpw " n "[] = {"; + system("./mpdump " d); + print "};"; + print ""; + cache[d] = n; + } + mp[x] = cache[d]; +} + +function flush() +{ + if (name == "") return; + print "/* --- Curve " name " --- */"; + delete mp; + print ""; + putmp("p"); + if (type == "binnorm") putmp("beta"); + putmp("a"); + putmp("b"); + putmp("r"); + putmp("h"); + putmp("gx"); + putmp("gy"); + print "static ecdata c_" fix(name) " = {"; + print " FTAG_" toupper(type) ","; + print " MP(" mp["p"] ")," + if (type == "binnorm") + print " MP(" mp["beta"] "),"; + else + print " NOMP,"; + print " MP(" mp["a"] ")," + print " MP(" mp["b"] ")," + print " MP(" mp["r"] ")," + print " MP(" mp["h"] ")," + print " MP(" mp["gx"] ")," + print " MP(" mp["gy"] ")" + print "};"; + print ""; + dname[d_i++] = name; + d[name] = name; + r[name] = "c_" fix(name); + name = ""; +} + +/^[ \t]*(#|$)/ { next; } + +$1 == "alias" { flush(); dname[d_i++] = $2; d[$2] = $3; next; } + +$1 == "curve" { flush(); delete data; name = $2; type = $3; next; } + +{ data[$1] = $2; next; } + +END { + flush(); + print banner("Main table"); + print ""; + print "const ecentry ectab[] = {"; + for (i = 0; i < d_i; i++) { + name = dname[i]; + rname = d[name]; + if (!rname in r) { + print "curve " rname " not found (alias from " name ")" >"/dev/stderr"; + exit 1; + } + print " { \"" name "\", &" r[rname] " },"; + } + print " { 0, 0 }"; + print "};" + print ""; + print banner("That's all, folks"); +} diff --git a/ec-gentab.sh b/ec-gentab.sh deleted file mode 100755 index 40fd853..0000000 --- a/ec-gentab.sh +++ /dev/null @@ -1,144 +0,0 @@ -#! /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 <p); ei->c = ec_binproj(f, &ed->a, &ed->b); break; + case FTAG_BINNORM: + f = field_binnorm(&ed->p, &ed->beta); + ei->c = ec_binproj(f, &ed->a, &ed->b); + break; default: abort(); } diff --git a/ec.c b/ec.c index 13e9b84..9a929ca 100644 --- a/ec.c +++ b/ec.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec.c,v 1.8 2004/04/01 12:50:09 mdw Exp $ + * $Id: ec.c,v 1.9 2004/04/01 21:28:41 mdw Exp $ * * Elliptic curve definitions * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec.c,v $ + * Revision 1.9 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.8 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -216,7 +221,7 @@ ec *ec_idfix(ec_curve *c, ec *d, const ec *p) return (d); } -/* --- @ec_projin@, @ec_projout@ --- * +/* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- * * * Arguments: @ec_curve *c@ = pointer to an elliptic curve * @ec *d@ = pointer to the destination @@ -282,7 +287,7 @@ ec *ec_projfix(ec_curve *c, ec *d, const ec *p) mp_drop(d->z); d->z = MP_COPY(f->one); } - return (d); + return (d); } /* --- @ec_stdsub@ --- * diff --git a/ectab.h b/ectab.h index 925924d..d75e79c 100644 --- a/ectab.h +++ b/ectab.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ectab.h,v 1.2 2004/04/01 12:50:09 mdw Exp $ + * $Id: ectab.h,v 1.3 2004/04/01 21:28:41 mdw Exp $ * * Table of standard elliptic curves * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: ectab.h,v $ + * Revision 1.3 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.2 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -57,7 +62,7 @@ typedef struct ecdata { unsigned ftag; /* The kind of curve this is */ - mp p; /* Modulus */ + mp p, beta; /* Modulus, and conversion magic */ mp a, b; /* Elliptic curve parameters */ mp r; /* Order of common point %$g$% */ mp h; /* Cofactor %$h = \#E/r$% */ @@ -67,7 +72,8 @@ typedef struct ecdata { enum { FTAG_PRIME, /* Prime but not nice */ FTAG_NICEPRIME, /* Nice prime field */ - FTAG_BINPOLY /* Any old binary field */ + FTAG_BINPOLY, /* Binary field, poly basis */ + FTAG_BINNORM /* Binary field, normal basis */ }; typedef struct ecentry { diff --git a/ectab.in b/ectab.in index 2de574c..ce4078d 100644 --- a/ectab.in +++ b/ectab.in @@ -1,4 +1,4 @@ -# $Id: ectab.in,v 1.1 2004/03/27 17:54:11 mdw Exp $ +# $Id: ectab.in,v 1.2 2004/04/01 21:28:41 mdw Exp $ # # Standard ellipic curves @@ -338,4 +338,105 @@ alias nist-b283 sect283r1 alias nist-b409 sect409r1 alias nist-b571 sect571r1 -#----- That's all, folks ---------------------------------------------------- +curve nist-k163n binnorm + p 0x800000000000000000000000000000000000000c9 + beta 0x715169c109c612e390d347c748342bcd3b02a0bef + a 0x7ffffffffffffffffffffffffffffffffffffffff + b 0x7ffffffffffffffffffffffffffffffffffffffff + r 0x04000000000000000000020108a2e0cc0d99f8a5ef + h 2 + gx 0x05679b353caa46825fea2d3713ba450da0c2a4541 + gy 0x235b7c6710050689906bac3d9dec76a835591edb2 + +curve nist-b163n binnorm + p 0x800000000000000000000000000000000000000c9 + beta 0x715169c109c612e390d347c748342bcd3b02a0bef + a 0x7ffffffffffffffffffffffffffffffffffffffff + b 0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb + r 0x040000000000000000000292fe77e70c12a4234c33 + h 2 + gx 0x0311103c17167564ace77ccb09c681f886ba54ee8 + gy 0x333ac13c6447f2e67613bf7009daf98c87bb50c7f + +curve nist-k233n binnorm + p 0x20000000000000000000000000000000000000004000000000000000001 + beta 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9 + a 0 + b 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + r 0x8000000000000000000000000000069d5bb915bcd46efb1ad5f173abdf + h 4 + gx 0x0fde76d9dcd26e643ac26f1aa901aa129784b71fc0722b2d05614d650b3 + gy 0x0643e317633155c9e0447ba8020a3c43177450ee036d633501434cac978 + +curve nist-b233n binnorm + p 0x20000000000000000000000000000000000000004000000000000000001 + beta 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9 + a 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + b 0x1a003e0962d4f9a8e407c904a9538163adb825212600c7752ad52233279 + r 0x01000000000000000000000000000013e974e72f8a6922031d2603cfe0d7 + h 2 + gx 0x18b863524b3cdfefb94f2784e0b116faac54404bc9162a363bab84a14c5 + gy 0x04925df77bd8b8ff1a5ff519417822bfedf2bbd752644292c98c7af6e02 + +curve nist-k283n binnorm + p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 + beta 0x31e0ed791c3282dc5624a720818049d053e8c7ab8663792bc1d792eba9867fc7b317a99 + a 0 + b 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + r 0x01ffffffffffffffffffffffffffffffffffe9ae2ed07577265dff7f94451e061e163c61 + h 4 + gx 0x3ab9593f8db09fc188f1d7c4ac9fcc3e57fcd3bdb15024b212c70229de5fcd92eb0ea60 + gy 0x2118c4755e7345cd8f603ef93b98b106fe8854ffeb9a3b304634cc83a0e759f0c2686b1 + +curve nist-b283n binnorm + p 0x800000000000000000000000000000000000000000000000000000000000000000010a1 + beta 0x31e0ed791c3282dc5624a720818049d053e8c7ab8663792bc1d792eba9867fc7b317a99 + a 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + b 0x157261b894739fb5a13503f55f0b3f10c5601166633102201138cc180c0206bdafbc951 + r 0x03ffffffffffffffffffffffffffffffffffef90399660fc938a90165b042a7cefadb307 + h 2 + gx 0x749468e464ee468634b21f7f61cb700701817e6bc36a2364cb8906e940948eaa463c35d + gy 0x62968bd3b489ac5c9b859da68475c315bafcdc4ccd0dc905b70f62446f49c052f49c08c + +curve nist-k409n binnorm + p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 + beta 0x0dfa06be206aa97b7a41fffb9b0c55f8f048062fbe8381b4248adf92912ccc8e3f91a24e1cfb3950532b988971c23042e85708d + a 0 + b 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + r 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffe5f83b2d4ea20400ec4557d5ed3e3e7ca5b4b5c83b8e01e5fcf + h 4 + gx 0x1b559c7cba2422e3affe13343e808b55e012d726ca0b7e6a63aeafbc1e3a98e10ca0fcf98350c3b7f89a9754a8e1dc0713cec4a + gy 0x16d8c42052f07e7713e7490eff318ba1abd6fef8a5433c894b24f5c817aeb79852496fbee803a47bc8a203878ebf1c499afd7d6 + +curve nist-b409n binnorm + p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 + beta 0x0dfa06be206aa97b7a41fffb9b0c55f8f048062fbe8381b4248adf92912ccc8e3f91a24e1cfb3950532b988971c23042e85708d + a 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + b 0x124d0651c3d3772f7f5a1fe6e715559e2129bdfa04d52f7b6ac7c532cf0ed06f610072d88ad2fdcc50c6fde72843670f8b3742a + r 0x010000000000000000000000000000000000000000000000000001e2aad6a612f33307be5fa47c3c9e052f838164cd37d9a21173 + h 2 + gx 0x0ceacbc9f475767d8e69f3b5dfab39813685262bcacf22b84c7b6dd981899e7318c96f0761f77c602c016ced7c548de830d708f + gy 0x199d64ba8f089c6db0e0b61e80bb95934afd0caf2e8be76d1c5e9affc7476df49142691ad30390288aa09bcc59c1573aa3c009a + +curve nist-k571n binnorm + p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 + beta 0x452186bbf5840a0bcf8c9f02a54efa04e813b43c3d4149606c4d27b487bf107393c8907f79d9778beb35ee87467d3288274caebda6ce05aeb4ca5cf3c3044bd4372232f2c1a27c4 + a 0 + b 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + r 0x020000000000000000000000000000000000000000000000000000000000000000000000131850e1f19a63e4b391a8db917f4138b630d84be5d639381e91deb45cfe778f637c1001 + h 4 + gx 0x04bb2dba418d0db107adae003427e5d7cc139acb465e5934f0bea2ab2f3622bc29b3d5b9aa7a1fdfd5d8be66057c1008e71e484bcd98f22bf8476423767367429ef2ec5bc3ebcf7 + gy 0x44cbb57de20788d2c952d7b56cf39bd3e89b18984bd124e751ceff4369dd8dac6a59e6e745df44d8220ce22aa2c852cfcbbef49ebaa98bd2483e33180e04286feaa253050caff60 + +curve nist-b571n binnorm + p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425 + beta 0x452186bbf5840a0bcf8c9f02a54efa04e813b43c3d4149606c4d27b487bf107393c8907f79d9778beb35ee87467d3288274caebda6ce05aeb4ca5cf3c3044bd4372232f2c1a27c4 + a 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + b 0x3762d0d47116006179da35688eeaccf591a5cdea75000118d9608c59132d43426101a1dfb3774115f586623f75f00001ce611983c1275fa31f5bc9f4be1a0f467f01ca885c74777 + + r 0x03ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe661ce18ff55987308059b186823851ec7dd9ca1161de93d5174d66e8382e9bb2fe84e47 + h 2 + gx 0x0735e035def5925cc33173eb2a8ce7767522b466d278b650a2916127dfea9d2d361089f0a7a0247a184e1c70d417866e0fe0feb0ff8f2f3f9176418f97d117e624e2015df1662a8 + gy 0x04a36420572616cdf7e606fccadaecfc3b76dab0eb1248dd03fbdfc9cd3242c4726be579855e812de7ec5c500b4576a24628048b6a72d880062eed0dd34b1096d3acbb6b01a4a97 + +#----- That's all, folks----------------------------------------------------- diff --git a/f-binpoly.c b/f-binpoly.c index aeec0cf..45e1449 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-binpoly.c,v 1.6 2004/04/01 12:50:09 mdw Exp $ + * $Id: f-binpoly.c,v 1.7 2004/04/01 21:28:41 mdw Exp $ * * Binary fields with polynomial basis representation * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-binpoly.c,v $ + * Revision 1.7 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.6 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -62,78 +67,48 @@ #include "gf.h" #include "gfreduce.h" #include "mprand.h" +#include "gfn.h" -/*----- Data structures ---------------------------------------------------*/ +/*----- Polynomial basis --------------------------------------------------*/ typedef struct fctx { field f; gfreduce r; } fctx; -/*----- Main code ---------------------------------------------------------*/ - /* --- Field operations --- */ static void fdestroy(field *ff) -{ - fctx *f = (fctx *)ff; - gfreduce_destroy(&f->r); - DESTROY(f); -} + { fctx *f = (fctx *)ff; gfreduce_destroy(&f->r); DESTROY(f); } static mp *frand(field *f, mp *d, grand *r) -{ - return (mprand(d, f->nbits, r, 0)); -} + { return (mprand(d, f->nbits, r, 0)); } -static int fzerop(field *ff, mp *x) -{ - return (!MP_LEN(x)); -} +static int fzerop(field *ff, mp *x) { return (!MP_LEN(x)); } -static mp *fadd(field *ff, mp *d, mp *x, mp *y) -{ - return (gf_add(d, x, y)); -} +static mp *fadd(field *ff, mp *d, mp *x, mp *y) { return (gf_add(d, x, y)); } -static mp *fmul(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = gf_mul(d, x, y); +static mp *fmul(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = gf_mul(d, x, y); return (gfreduce_do(&f->r, d, d)); } -static mp *fsqr(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = gf_sqr(d, x); +static mp *fsqr(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = gf_sqr(d, x); return (gfreduce_do(&f->r, d, d)); } static mp *finv(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - gf_gcd(0, 0, &d, f->r.p, x); - return (d); -} + { fctx *f = (fctx *)ff; gf_gcd(0, 0, &d, f->r.p, x); return (d); } static mp *freduce(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (gfreduce_do(&f->r, d, x)); -} + { fctx *f = (fctx *)ff; return (gfreduce_do(&f->r, d, x)); } static mp *fsqrt(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (gfreduce_sqrt(&f->r, d, x)); -} + { fctx *f = (fctx *)ff; return (gfreduce_sqrt(&f->r, d, x)); } static mp *fquadsolve(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (gfreduce_quadsolve(&f->r, d, x)); -} + { fctx *f = (fctx *)ff; return (gfreduce_quadsolve(&f->r, d, x)); } /* --- Field operations table --- */ @@ -168,4 +143,67 @@ field *field_binpoly(mp *p) return (&f->f); } +/*----- Normal basis ------------------------------------------------------*/ + +typedef struct fnctx { + fctx f; + gfn ntop, pton; +} fnctx; + +/* --- Field operations --- */ + +static void fndestroy(field *ff) { + fnctx *f = (fnctx *)ff; gfreduce_destroy(&f->f.r); + gfn_destroy(&f->ntop); gfn_destroy(&f->pton); + DESTROY(f); +} + +static int fnsamep(field *ff, field *gg) { + fnctx *f = (fnctx *)ff, *g = (fnctx *)gg; + return (MP_EQ(f->ntop.r[0], g->ntop.r[0]) && field_stdsamep(ff, gg)); +} + +static mp *fnin(field *ff, mp *d, mp *x) + { fnctx *f = (fnctx *)ff; return (gfn_transform(&f->ntop, d, x)); } + +static mp *fnout(field *ff, mp *d, mp *x) + { fnctx *f = (fnctx *)ff; return (gfn_transform(&f->pton, d, x)); } + +/* --- Field operations table --- */ + +static field_ops fnops = { + FTY_BINARY, "binnorm", + fndestroy, frand, fnsamep, + fnin, fnout, + fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt, + fquadsolve, + 0, 0, 0, 0 +}; + +/* --- @field_binnorm@ --- * + * + * Arguments: @mp *p@ = the reduction polynomial + * @mp *beta@ = representation of normal point + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a binary field mod @p@ which + * uses a normal basis representation externally. Computations + * are still done on a polynomial-basis representation. + */ + +field *field_binnorm(mp *p, mp *beta) +{ + fnctx *f = CREATE(fnctx); + f->f.f.ops = &fnops; + f->f.f.zero = MP_ZERO; + f->f.f.one = MP_ONE; + f->f.f.nbits = mp_bits(p) - 1; + f->f.f.noctets = (f->f.f.nbits + 7) >> 3; + gfreduce_create(&f->f.r, p); + f->f.f.m = f->f.r.p; + gfn_create(p, beta, &f->ntop, &f->pton); + return (&f->f.f); +} + /*----- That's all, folks -------------------------------------------------*/ diff --git a/f-niceprime.c b/f-niceprime.c index 4ffc028..2a51352 100644 --- a/f-niceprime.c +++ b/f-niceprime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-niceprime.c,v 1.3 2004/04/01 12:50:09 mdw Exp $ + * $Id: f-niceprime.c,v 1.4 2004/04/01 21:28:41 mdw Exp $ * * Prime fields with efficient reduction for special-form primes * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-niceprime.c,v $ + * Revision 1.4 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.3 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -53,136 +58,82 @@ #include "mpreduce.h" #include "mprand.h" -/*----- Data structures ---------------------------------------------------*/ +/*----- Main code ---------------------------------------------------------*/ typedef struct fctx { field f; mpreduce r; } fctx; -/*----- Main code ---------------------------------------------------------*/ - /* --- Field operations --- */ static void fdestroy(field *ff) -{ - fctx *f = (fctx *)ff; - mpreduce_destroy(&f->r); - DESTROY(f); -} + { fctx *f = (fctx *)ff; mpreduce_destroy(&f->r); DESTROY(f); } static mp *frand(field *ff, mp *d, grand *r) -{ - fctx *f = (fctx *)ff; - return (mprand_range(d, f->r.p, r, 0)); -} + { fctx *f = (fctx *)ff; return (mprand_range(d, f->r.p, r, 0)); } -static int fzerop(field *ff, mp *x) -{ - return (!MP_LEN(x)); -} +static int fzerop(field *ff, mp *x) { return (!MP_LEN(x)); } static mp *fneg(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (mp_sub(d, f->r.p, x)); -} + { fctx *f = (fctx *)ff; return (mp_sub(d, f->r.p, x)); } -static mp *fadd(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = mp_add(d, x, y); - if (d->f & MP_NEG) - d = mp_add(d, d, f->r.p); - else if (MP_CMP(d, >, f->r.p)) - d = mp_sub(d, d, f->r.p); +static mp *fadd(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = mp_add(d, x, y); + if (d->f & MP_NEG) d = mp_add(d, d, f->r.p); + else if (MP_CMP(d, >, f->r.p)) d = mp_sub(d, d, f->r.p); return (d); } -static mp *fsub(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = mp_sub(d, x, y); - if (d->f & MP_NEG) - d = mp_add(d, d, f->r.p); - else if (MP_CMP(d, >, f->r.p)) - d = mp_sub(d, d, f->r.p); +static mp *fsub(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = mp_sub(d, x, y); + if (d->f & MP_NEG) d = mp_add(d, d, f->r.p); + else if (MP_CMP(d, >, f->r.p)) d = mp_sub(d, d, f->r.p); return (d); } -static mp *fmul(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = mp_mul(d, x, y); +static mp *fmul(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = mp_mul(d, x, y); return (mpreduce_do(&f->r, d, d)); } -static mp *fsqr(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_sqr(d, x); +static mp *fsqr(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_sqr(d, x); return (mpreduce_do(&f->r, d, d)); } static mp *finv(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - mp_gcd(0, 0, &d, f->r.p, x); - return (d); -} + { fctx *f = (fctx *)ff; mp_gcd(0, 0, &d, f->r.p, x); return (d); } static mp *freduce(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (mpreduce_do(&f->r, d, x)); -} + { fctx *f = (fctx *)ff; return (mpreduce_do(&f->r, d, x)); } static mp *fsqrt(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (mp_modsqrt(d, x, f->r.p)); -} + { fctx *f = (fctx *)ff; return (mp_modsqrt(d, x, f->r.p)); } -static mp *fdbl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_lsl(d, x, 1); - if (MP_CMP(d, >, f->r.p)) - d = mp_sub(d, d, f->r.p); +static mp *fdbl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_lsl(d, x, 1); + if (MP_CMP(d, >, f->r.p)) d = mp_sub(d, d, f->r.p); return (d); } -static mp *ftpl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - MP_DEST(d, MP_LEN(x) + 1, x->f); +static mp *ftpl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; MP_DEST(d, MP_LEN(x) + 1, x->f); MPX_UMULN(d->v, d->vl, x->v, x->vl, 3); - while (MP_CMP(d, >, f->r.p)) - d = mp_sub(d, d, f->r.p); + while (MP_CMP(d, >, f->r.p)) d = mp_sub(d, d, f->r.p); return (d); } -static mp *fqdl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_lsl(d, x, 2); - while (MP_CMP(d, >, f->r.p)) - d = mp_sub(d, d, f->r.p); +static mp *fqdl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_lsl(d, x, 2); + while (MP_CMP(d, >, f->r.p)) d = mp_sub(d, d, f->r.p); return (d); } -static mp *fhlv(field *ff, mp *d, mp *x) -{ +static mp *fhlv(field *ff, mp *d, mp *x) { fctx *f = (fctx *)ff; - if (!MP_LEN(x)) { - MP_COPY(x); - MP_DROP(d); - return (x); - } - if (x->v[0] & 1) { - d = mp_add(d, x, f->r.p); - x = d; - } + if (!MP_LEN(x)) { MP_COPY(x); MP_DROP(d); return (x); } + if (x->v[0] & 1) { d = mp_add(d, x, f->r.p); x = d; } return (mp_lsr(d, x, 1)); } diff --git a/f-prime.c b/f-prime.c index 473ba4c..088032b 100644 --- a/f-prime.c +++ b/f-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: f-prime.c,v 1.8 2004/04/01 12:50:09 mdw Exp $ + * $Id: f-prime.c,v 1.9 2004/04/01 21:28:41 mdw Exp $ * * Prime fields with Montgomery arithmetic * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: f-prime.c,v $ + * Revision 1.9 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.8 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -77,154 +82,94 @@ #include "mpmont.h" #include "mprand.h" -/*----- Data structures ---------------------------------------------------*/ +/*----- Main code ---------------------------------------------------------*/ typedef struct fctx { field f; mpmont mm; } fctx; -/*----- Main code ---------------------------------------------------------*/ - /* --- Field operations --- */ static void fdestroy(field *ff) -{ - fctx *f = (fctx *)ff; - mpmont_destroy(&f->mm); - DESTROY(f); -} + { fctx *f = (fctx *)ff; mpmont_destroy(&f->mm); DESTROY(f); } static mp *frand(field *ff, mp *d, grand *r) -{ - fctx *f = (fctx *)ff; - return (mprand_range(d, f->mm.m, r, 0)); -} + { fctx *f = (fctx *)ff; return (mprand_range(d, f->mm.m, r, 0)); } -static mp *fin(field *ff, mp *d, mp *x) -{ +static mp *fin(field *ff, mp *d, mp *x) { fctx *f = (fctx *)ff; mp_div(0, &d, x, f->mm.m); return (mpmont_mul(&f->mm, d, d, f->mm.r2)); } static mp *fout(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (mpmont_reduce(&f->mm, d, x)); -} + { fctx *f = (fctx *)ff; return (mpmont_reduce(&f->mm, d, x)); } -static int fzerop(field *ff, mp *x) -{ - return (!MP_LEN(x)); -} +static int fzerop(field *ff, mp *x) { return (!MP_LEN(x)); } static mp *fneg(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - return (mp_sub(d, f->mm.m, x)); -} + { fctx *f = (fctx *)ff; return (mp_sub(d, f->mm.m, x)); } -static mp *fadd(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = mp_add(d, x, y); - if (d->f & MP_NEG) - d = mp_add(d, d, f->mm.m); - else if (MP_CMP(d, >, f->mm.m)) - d = mp_sub(d, d, f->mm.m); +static mp *fadd(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = mp_add(d, x, y); + if (d->f & MP_NEG) d = mp_add(d, d, f->mm.m); + else if (MP_CMP(d, >, f->mm.m)) d = mp_sub(d, d, f->mm.m); return (d); } -static mp *fsub(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - d = mp_sub(d, x, y); - if (d->f & MP_NEG) - d = mp_add(d, d, f->mm.m); - else if (MP_CMP(d, >, f->mm.m)) - d = mp_sub(d, d, f->mm.m); +static mp *fsub(field *ff, mp *d, mp *x, mp *y) { + fctx *f = (fctx *)ff; d = mp_sub(d, x, y); + if (d->f & MP_NEG) d = mp_add(d, d, f->mm.m); + else if (MP_CMP(d, >, f->mm.m)) d = mp_sub(d, d, f->mm.m); return (d); } static mp *fmul(field *ff, mp *d, mp *x, mp *y) -{ - fctx *f = (fctx *)ff; - return (mpmont_mul(&f->mm, d, x, y)); -} + { fctx *f = (fctx *)ff; return (mpmont_mul(&f->mm, d, x, y)); } -static mp *fsqr(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_sqr(d, x); +static mp *fsqr(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_sqr(d, x); return (mpmont_reduce(&f->mm, d, d)); } -static mp *finv(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mpmont_reduce(&f->mm, d, x); - mp_gcd(0, 0, &d, f->mm.m, d); - return (mpmont_mul(&f->mm, d, d, f->mm.r2)); +static mp *finv(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mpmont_reduce(&f->mm, d, x); + mp_gcd(0, 0, &d, f->mm.m, d); return (mpmont_mul(&f->mm, d, d, f->mm.r2)); } static mp *freduce(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - mp_div(0, &d, x, f->mm.m); - return (d); -} + { fctx *f = (fctx *)ff; mp_div(0, &d, x, f->mm.m); return (d); } -static mp *fsqrt(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mpmont_reduce(&f->mm, d, x); - d = mp_modsqrt(d, d, f->mm.m); - if (!d) - return (d); +static mp *fsqrt(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mpmont_reduce(&f->mm, d, x); + d = mp_modsqrt(d, d, f->mm.m); if (!d) return (d); return (mpmont_mul(&f->mm, d, d, f->mm.r2)); } -static mp *fdbl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_lsl(d, x, 1); - if (MP_CMP(d, >, f->mm.m)) - d = mp_sub(d, d, f->mm.m); +static mp *fdbl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_lsl(d, x, 1); + if (MP_CMP(d, >, f->mm.m)) d = mp_sub(d, d, f->mm.m); return (d); } -static mp *ftpl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - MP_DEST(d, MP_LEN(x) + 1, x->f); +static mp *ftpl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; MP_DEST(d, MP_LEN(x) + 1, x->f); MPX_UMULN(d->v, d->vl, x->v, x->vl, 3); - while (MP_CMP(d, >, f->mm.m)) - d = mp_sub(d, d, f->mm.m); + while (MP_CMP(d, >, f->mm.m)) d = mp_sub(d, d, f->mm.m); return (d); } -static mp *fqdl(field *ff, mp *d, mp *x) -{ - fctx *f = (fctx *)ff; - d = mp_lsl(d, x, 2); - while (MP_CMP(d, >, f->mm.m)) - d = mp_sub(d, d, f->mm.m); +static mp *fqdl(field *ff, mp *d, mp *x) { + fctx *f = (fctx *)ff; d = mp_lsl(d, x, 2); + while (MP_CMP(d, >, f->mm.m)) d = mp_sub(d, d, f->mm.m); return (d); } -static mp *fhlv(field *ff, mp *d, mp *x) -{ +static mp *fhlv(field *ff, mp *d, mp *x) { fctx *f = (fctx *)ff; - if (!MP_LEN(x)) { - MP_COPY(x); - MP_DROP(d); - return (x); - } - if (x->v[0] & 1) { - d = mp_add(d, x, f->mm.m); - x = d; - } + if (!MP_LEN(x)) { MP_COPY(x); MP_DROP(d); return (x); } + if (x->v[0] & 1) { d = mp_add(d, x, f->mm.m); x = d; } return (mp_lsr(d, x, 1)); } diff --git a/field-parse.c b/field-parse.c index 0a09e57..e815a9f 100644 --- a/field-parse.c +++ b/field-parse.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field-parse.c,v 1.1 2004/03/27 17:54:11 mdw Exp $ + * $Id: field-parse.c,v 1.2 2004/04/01 21:28:41 mdw Exp $ * * Parse field descriptions * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: field-parse.c,v $ + * Revision 1.2 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.1 2004/03/27 17:54:11 mdw * Standard curves and curve checking. * @@ -56,30 +61,39 @@ field *field_parse(qd_parse *qd) { - field *f; - mp *m = MP_NEW; + field *f = 0; + mp *m = MP_NEW, *b = MP_NEW; - switch (qd_enum(qd, "prime,niceprime,binpoly")) { + switch (qd_enum(qd, "prime,niceprime,binpoly,binnorm")) { case 0: qd_delim(qd, ':'); - if ((m = qd_getmp(qd)) == 0) return (0); + if ((m = qd_getmp(qd)) == 0) goto done; f = field_prime(m); break; case 1: qd_delim(qd, ':'); - if ((m = qd_getmp(qd)) == 0) return (0); + if ((m = qd_getmp(qd)) == 0) goto done; f = field_niceprime(m); break; case 2: qd_delim(qd, ':'); - if ((m = qd_getmp(qd)) == 0) return (0); + if ((m = qd_getmp(qd)) == 0) goto done; f = field_binpoly(m); break; + case 3: + qd_delim(qd, ':'); + if ((m = qd_getmp(qd)) == 0) goto done; + qd_delim(qd, ','); + if ((b = qd_getmp(qd)) == 0) goto done; + f = field_binnorm(m, b); + break; default: f = 0; break; } +done: mp_drop(m); + mp_drop(b); return (f); } diff --git a/field.h b/field.h index bf0428a..3a46ac9 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field.h,v 1.9 2004/04/01 12:50:09 mdw Exp $ + * $Id: field.h,v 1.10 2004/04/01 21:28:41 mdw Exp $ * * Definitions for field arithmetic * @@ -30,6 +30,11 @@ /*----- Revision history --------------------------------------------------* * * $Log: field.h,v $ + * Revision 1.10 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * * Revision 1.9 2004/04/01 12:50:09 mdw * Add cyclic group abstraction, with test code. Separate off exponentation * functions for better static linking. Fix a buttload of bugs on the way. @@ -250,6 +255,20 @@ extern field *field_niceprime(mp */*p*/); extern field *field_binpoly(mp */*p*/); +/* --- @field_binnorm@ --- * + * + * Arguments: @mp *p@ = the reduction polynomial + * @mp *beta@ = representation of normal point + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a binary field mod @p@ which + * uses a normal basis representation externally. Computations + * are still done on a polynomial-basis representation. + */ + +extern field *field_binnorm(mp */*p*/, mp */*beta*/); + /* --- @field_parse@ --- * * * Arguments: @qd_parse *qd@ = parser context @@ -258,9 +277,10 @@ extern field *field_binpoly(mp */*p*/); * * Use: Parses a field description, which has the form * - * * `prime', `niceprime' or `binpoly' + * * `prime', `niceprime', `binpoly', or `binnorm' * * an optional `:' * * the field modulus + * * for `binnorm', an optional `,' and the beta value */ extern field *field_parse(qd_parse */*qd*/); diff --git a/gfn.c b/gfn.c new file mode 100644 index 0000000..1b5a98c --- /dev/null +++ b/gfn.c @@ -0,0 +1,284 @@ +/* -*-c-*- + * + * $Id: gfn.c,v 1.1 2004/04/01 21:28:41 mdw Exp $ + * + * Normal-basis translation for binary fields + * + * (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: gfn.c,v $ + * Revision 1.1 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "gfreduce.h" +#include "gfn.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @gfn_copy@ --- * + * + * Arguments: @gfn *d@ = where to put the copy + * @const gfn *s@ = where the source is + * + * Returns: --- + * + * Use: Makes a copy of a translation matrix. + */ + +void gfn_copy(gfn *d, const gfn *s) +{ + size_t i; + + d->n = s->n; + d->r = xmalloc(s->n * sizeof(mp *)); + for (i = 0; i < s->n; i++) + d->r[i] = MP_COPY(s->r[i]); +} + +/* --- @gfn_destroy@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix to free + * + * Returns: --- + * + * Use: Frees up a transformation matrix when it's no longer wanted. + */ + +void gfn_destroy(gfn *m) + { size_t i; for (i = 0; i < m->n; i++) MP_DROP(m->r[i]); xfree(m->r); } + +/* --- @gfn_identity@ --- * + * + * Arguments: @gfn *m@ = where to put the matrix + * @size_t n@ = size of the matrix + * + * Returns: --- + * + * Use: Fills @m@ with an identity matrix. + */ + +void gfn_identity(gfn *m, size_t n) +{ + size_t i; + + m->n = n; + m->r = xmalloc(n * sizeof(mp *)); + m->r[0] = MP_ONE; + for (i = 1; i < n; i++) + m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1); +} + +/* --- @gfn_invert@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix + * + * Returns: Zero if successful, nonzero if the matrix was singular. + * + * Use: Inverts a transformation matrix. + */ + +int gfn_invert(gfn *m) +{ + size_t i, j; + gfn mm; + mp *t; + int rc = -1; + + mm = *m; + gfn_identity(m, mm.n); + for (i = 0; i < mm.n; i++) { + if (!mp_testbit(mm.r[i], i)) { + for (j = i + 1; j < mm.n; j++) { + if (mp_testbit(mm.r[j], i)) + goto found_set; + } + goto fail; + found_set: + t = mm.r[i]; mm.r[i] = mm.r[j]; mm.r[j] = t; + t = m->r[i]; m->r[i] = m->r[j]; m->r[j] = t; + } + for (j = 0; j < mm.n; j++) { + if (j == i) continue; + if (mp_testbit(mm.r[j], i)) { + mm.r[j] = mp_xor(mm.r[j], mm.r[j], mm.r[i]); + m->r[j] = mp_xor(m->r[j], m->r[j], m->r[i]); + } + } + } + rc = 0; +fail: + gfn_destroy(&mm); + return (rc); +} + +/* --- @gfn_transform@ --- * + * + * Arguments: @gfn *m@ = conversion matrix to apply + * @mp *d@ = destination pointer + * @mp *x@ = input value + * + * Returns: The transformed element. + * + * Use: Transforms a field element according to the given matrix. + */ + +mp *gfn_transform(gfn *m, mp *d, mp *x) +{ + mp *y = MP_ZERO; + size_t i; + mpscan sc; + + for (i = 0, mp_scan(&sc, x); i < m->n && mp_step(&sc); i++) + if (mp_bit(&sc)) y = mp_xor(y, y, m->r[i]); + mp_drop(d); + return (y); +} + +/* --- @gfn_create@ --- * + * + * Arguments: @mp *p@ = modulus for polynomial basis + * @mp *beta@ = the generator of the normal basis, expressed + * relative to the polynomial basis + * @gfn *ntop@ = output normal-to-polynomail conversion matrix + * @gfn *pton@ = output polynomial-to-normal conversion matrix + * + * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$% + * doesn't generate a proper basis). + * + * Use: Constructs conversion matrices between polynomial and normal + * basis representations of binary field elements. + */ + +int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton) +{ + size_t m = mp_bits(p) - 1; + size_t i; + gfreduce gr; + gfn *np, tmp; + + /* --- We start by building the the @ntop@ matrix --- * + * + * For mad reasons, the string representation of normal-basis elements is + * backwards. + */ + + gfreduce_create(&gr, p); + np = ntop ? ntop : &tmp; + np->n = m; + np->r = xmalloc(m * sizeof(mp *)); + np->r[m - 1] = MP_COPY(beta); + for (i = m - 1; i--; ) { + mp *x = gf_sqr(MP_NEW, np->r[i + 1]); + np->r[i] = gfreduce_do(&gr, x, x); + } + gfreduce_destroy(&gr); + + /* --- That was easy -- now invert it --- */ + + if (pton) { + if (ntop) gfn_copy(pton, np); else *pton = *np; + if (gfn_invert(pton)) { + gfn_destroy(pton); + if (ntop) gfn_destroy(ntop); + return (-1); + } + } + + /* --- And we're done --- */ + + return (0); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +static int check(dstr *v) +{ + mp *p = *(mp **)v[0].buf; + mp *beta = *(mp **)v[1].buf; + mp *xp = *(mp **)v[2].buf; + mp *xn = *(mp **)v[3].buf; + mp *y = MP_NEW; + gfn pton, ntop, ii; + size_t i; + int ok = 1; + + gfn_create(p, beta, &ntop, &pton); + gfn_identity(&ii, pton.n); + for (i = 0; i < pton.n; i++) { + y = gfn_transform(&ntop, y, pton.r[i]); + if (!MP_EQ(y, ii.r[i])) { + ok = 0; + fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n", + (unsigned long)i); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** computed", y); + } + } + gfn_destroy(&ii); + y = gfn_transform(&pton, y, xp); + if (!MP_EQ(y, xn)) { + ok = 0; + fprintf(stderr, "*** pton failed\n"); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); + MP_EPRINTX("*** computed", y); + } + y = gfn_transform(&ntop, y, xn); + if (!MP_EQ(y, xp)) { + ok = 0; + fprintf(stderr, "*** ntop failed\n"); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); + MP_EPRINTX("*** computed", y); + } + gfn_destroy(&pton); gfn_destroy(&ntop); + mp_drop(p); mp_drop(beta); mp_drop(xp); mp_drop(xn); mp_drop(y); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +static test_chunk tests[] = { + { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } }, + { 0 } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR "/tests/gfn"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/gfn.h b/gfn.h new file mode 100644 index 0000000..48531b9 --- /dev/null +++ b/gfn.h @@ -0,0 +1,142 @@ +/* -*-c-*- + * + * $Id: gfn.h,v 1.1 2004/04/01 21:28:41 mdw Exp $ + * + * Normal-basis translation for binary fields + * + * (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: gfn.h,v $ + * Revision 1.1 2004/04/01 21:28:41 mdw + * Normal basis support (translates to poly basis internally). Rewrite + * EC and prime group table generators in awk, so that they can reuse data + * for repeated constants. + * + */ + +#ifndef CATACOMB_GFN_H +#define CATACOMB_GFN_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include "gf.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct gfn { + size_t n; /* Number of rows */ + mp **r; /* Array of the rows */ +} gfn; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @gfn_copy@ --- * + * + * Arguments: @gfn *d@ = where to put the copy + * @const gfn *s@ = where the source is + * + * Returns: --- + * + * Use: Makes a copy of a translation matrix. + */ + +extern void gfn_copy(gfn */*d*/, const gfn */*s*/); + +/* --- @gfn_destroy@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix to free + * + * Returns: --- + * + * Use: Frees up a transformation matrix when it's no longer wanted. + */ + +extern void gfn_destroy(gfn */*m*/); + +/* --- @gfn_identity@ --- * + * + * Arguments: @gfn *m@ = where to put the matrix + * @size_t n@ = size of the matrix + * + * Returns: --- + * + * Use: Fills @m@ with an identity matrix. + */ + +extern void gfn_identity(gfn */*m*/, size_t /*n*/); + +/* --- @gfn_invert@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix + * + * Returns: Zero if successful, nonzero if the matrix was singular. + * + * Use: Inverts a transformation matrix. + */ + +extern int gfn_invert(gfn */*m*/); + +/* --- @gfn_transform@ --- * + * + * Arguments: @gfn *m@ = conversion matrix to apply + * @mp *d@ = destination pointer + * @mp *x@ = input value + * + * Returns: The transformed element. + * + * Use: Transforms a field element according to the given matrix. + */ + +extern mp *gfn_transform(gfn */*m*/, mp */*d*/, mp */*x*/); + +/* --- @gfn_create@ --- * + * + * Arguments: @mp *p@ = modulus for polynomial basis + * @mp *beta@ = the generator of the normal basis, expressed + * relative to the polynomial basis + * @gfn *ntop@ = output normal-to-polynomail conversion matrix + * @gfn *pton@ = output polynomial-to-normal conversion matrix + * + * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$% + * doesn't generate a proper basis). + * + * Use: Constructs conversion matrices between polynomial and normal + * basis representations of binary field elements. + */ + +extern int gfn_create(mp */*p*/, mp */*beta*/, gfn */*ntop*/, gfn */*pton*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/p-gentab.awk b/p-gentab.awk new file mode 100755 index 0000000..a1b6da5 --- /dev/null +++ b/p-gentab.awk @@ -0,0 +1,102 @@ +#! /usr/bin/awk -f +# +# $Id: p-gentab.awk,v 1.1 2004/04/01 21:28:41 mdw Exp $ + +function banner(name, s, i) +{ + s = "/*----- " name " "; + while (length(s) < 75) s = s "-"; + return (s "*/"); +} + +function fix(name) +{ + gsub(/[^0-9A-Za-z_]+/, "_", name); + return (name); +} + +BEGIN { + print "/* -*-c-*-"; + print " *"; + print " * Table of elliptic curves [generated]"; + print " */"; + print ""; + print "#include \"ptab.h\""; + print ""; + print "#define N(x) (sizeof(x)/sizeof(*x))"; + print "#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }"; + print "#define NOMP { 0, 0, 0, 0, 0 }"; + print ""; + print banner("Prime data"); + print ""; + + d_i = 0; + name = ""; +} + +function putmp(x, d) +{ + if (!(x in data)) { + print "group " name ": missing " x >"/dev/stderr"; + exit 1; + } + d = data[x]; + if (!(d in cache)) { + n = "p_" fix(name) "_" x; + print "static mpw " n "[] = {"; + system("./mpdump " d); + print "};"; + print ""; + cache[d] = n; + } + mp[x] = cache[d]; +} + +function flush() +{ + if (name == "") return; + print "/* --- Group " name " --- */"; + delete mp; + print ""; + putmp("p"); + putmp("q"); + putmp("g"); + print "static pdata p_" fix(name) " = {"; + print " MP(" mp["p"] ")," + print " MP(" mp["q"] ")," + print " MP(" mp["g"] ")" + print "};"; + print ""; + dname[d_i++] = name; + d[name] = name; + r[name] = "p_" fix(name); + name = ""; +} + +/^[ \t]*(#|$)/ { next; } + +$1 == "alias" { flush(); dname[d_i++] = $2; d[$2] = $3; next; } + +$1 == "group" { flush(); delete data; name = $2; next; } + +{ data[$1] = $2; next; } + +END { + flush(); + print banner("Main table"); + print ""; + print "const pentry ptab[] = {"; + for (i = 0; i < d_i; i++) { + name = dname[i]; + rname = d[name]; + if (!rname in r) { + print "group " rname " not found (alias from " name ")" >"/dev/stderr"; + exit 1; + } + print " { \"" name "\", &" r[rname] " },"; + } + print " { 0, 0 }"; + print "};" + print ""; + print banner("That's all, folks"); +} diff --git a/p-gentab.sh b/p-gentab.sh deleted file mode 100755 index 210073b..0000000 --- a/p-gentab.sh +++ /dev/null @@ -1,90 +0,0 @@ -#! /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 q - if [ $t != q ]; then echo >&2 "$0: wanted q; found $t"; exit 1; fi - read t g - if [ $t != g ]; then echo >&2 "$0: wanted g; found $t"; exit 1; fi - - cat <