## -*-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
##
##----- 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.
##
./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 = \
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 \
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 \
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 \
CTESTRIG(gf-arith)
CTESTRIG(gf-gcd)
CTESTRIG(gfreduce)
+CTESTRIG(gfn)
CTESTRIG(ec-prime)
CTESTRIG(ec-bin)
CTESTRIG(ec-test)
/* -*-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
*
/*----- 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.
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);
}
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);
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);
--- /dev/null
+#! /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");
+}
+++ /dev/null
-#! /bin/sh
-
-set -e
-
-cat <<EOF
-/* -*-c-*-
- *
- * Table of standard elliptic curves [generated]
- */
-
-#include "ectab.h"
-
-#define N(x) (sizeof(x)/sizeof(*x))
-#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }
-
-/*----- Curve data --------------------------------------------------------*/
-
-EOF
-
-names=""
-while read t n f; do
-
- case $t in
- curve) ;;
- alias) names="$names $n=$f" continue;;
- \#* | "") continue;;
- *) echo >&2 "$0: unknown keyword $t"; exit 1;;
- esac
-
- names="$names $n=$n"
- cat <<EOF
-/* --- Curve $n --- */
-
-EOF
-
- n=`echo $n | sed 's/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
- case $f in
- prime | niceprime | binpoly)
- read t p;
- if [ $t != p ]; then echo >&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 <<EOF
-static mpw c_${n}_p[] = {
-EOF
- ./mpdump $p
- cat <<EOF
-};
-
-static mpw c_${n}_a[] = {
-EOF
- ./mpdump $a
- cat <<EOF
-};
-
-static mpw c_${n}_b[] = {
-EOF
- ./mpdump $b
- cat <<EOF
-};
-
-EOF
- ;;
- *) echo >&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 <<EOF
-static mpw c_${n}_r[] = {
-EOF
- ./mpdump $r
- cat <<EOF
-};
-
-static mpw c_${n}_h[] = {
-EOF
- ./mpdump $h
- cat <<EOF
-};
-
-static mpw c_${n}_gx[] = {
-EOF
- ./mpdump $gx
- cat <<EOF
-};
-
-static mpw c_${n}_gy[] = {
-EOF
- ./mpdump $gy
- cat <<EOF
-};
-
-EOF
-
- case $f in
- prime) ftag=FTAG_PRIME;;
- niceprime) ftag=FTAG_NICEPRIME;;
- binpoly) ftag=FTAG_BINPOLY;;
- esac
- cat <<EOF
-static ecdata c_$n = {
- $ftag,
- MP(c_${n}_p),
- MP(c_${n}_a),
- MP(c_${n}_b),
- MP(c_${n}_r),
- MP(c_${n}_h),
- MP(c_${n}_gx),
- MP(c_${n}_gy)
-};
-
-EOF
-
-done
-
-cat <<EOF
-/*----- Main table --------------------------------------------------------*/
-
-const ecentry ectab[] = {
-EOF
-for i in $names; do
- a=`echo $i | sed 's/=.*$//'`
- n=`echo $i | sed 's/^.*=//; s/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
- cat <<EOF
- { "$a", &c_$n },
-EOF
-done
-cat <<EOF
- { 0, 0 }
-};
-
-/*----- That's all, folks -------------------------------------------------*/
-EOF
/* -*-c-*-
*
- * $Id: ec-info.c,v 1.2 2004/04/01 12:50:09 mdw Exp $
+ * $Id: ec-info.c,v 1.3 2004/04/01 21:28:41 mdw Exp $
*
* Elliptic curve information management
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-info.c,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.
f = field_binpoly(&ed->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();
}
/* -*-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
*
/*----- 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.
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
mp_drop(d->z);
d->z = MP_COPY(f->one);
}
- return (d);
+ return (d);
}
/* --- @ec_stdsub@ --- *
/* -*-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
*
/*----- 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.
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$% */
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 {
-# $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
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-----------------------------------------------------
/* -*-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
*
/*----- 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.
#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 --- */
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 -------------------------------------------------*/
/* -*-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
*
/*----- 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.
#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));
}
/* -*-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
*
/*----- 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.
#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));
}
/* -*-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
*
/*----- 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.
*
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);
}
/* -*-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
*
/*----- 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.
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
*
* 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*/);
--- /dev/null
+/* -*-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 -------------------------------------------------*/
--- /dev/null
+/* -*-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
--- /dev/null
+#! /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");
+}
+++ /dev/null
-#! /bin/sh
-
-set -e
-
-cat <<EOF
-/* -*-c-*-
- *
- * Table of standard prime subgroups [generated]
- */
-
-#include "ptab.h"
-
-#define N(x) (sizeof(x)/sizeof(*x))
-#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }
-
-/*----- Prime data --------------------------------------------------------*/
-
-EOF
-
-names=""
-while read t n; do
-
- case $t in
- group) ;;
- alias) names="$names $n=$f" continue;;
- \#* | "") continue;;
- *) echo >&2 "$0: unknown keyword $t"; exit 1;;
- esac
-
- names="$names $n=$n"
- cat <<EOF
-/* --- Group $n --- */
-
-EOF
-
- n=`echo $n | sed 's/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
- read t p
- if [ $t != p ]; then echo >&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 <<EOF
-static mpw p_${n}_p[] = {
-EOF
- ./mpdump $p
- cat <<EOF
-};
-
-static mpw p_${n}_q[] = {
-EOF
- ./mpdump $q
- cat <<EOF
-};
-
-static mpw p_${n}_g[] = {
-EOF
- ./mpdump $g
- cat <<EOF
-};
-
-static pdata p_$n = {
- MP(p_${n}_p),
- MP(p_${n}_q),
- MP(p_${n}_g)
-};
-
-EOF
-
-done
-
-cat <<EOF
-/*----- Main table --------------------------------------------------------*/
-
-const pentry ptab[] = {
-EOF
-for i in $names; do
- a=`echo $i | sed 's/=.*$//'`
- n=`echo $i | sed 's/^.*=//; s/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
- cat <<EOF
- { "$a", &p_$n },
-EOF
-done
-cat <<EOF
- { 0, 0 }
-};
-
-/*----- That's all, folks -------------------------------------------------*/
-EOF
--- /dev/null
+# $Id: gfn,v 1.1 2004/04/01 21:28:47 mdw Exp $
+#
+# Normal basis conversions
+
+gfn {
+ 0x800000000000000000000000000000000000000c9
+ 0x715169c109c612e390d347c748342bcd3b02a0bef
+ 0 0;
+
+ 0x800000000000000000000000000000000000000c9
+ 0x715169c109c612e390d347c748342bcd3b02a0bef
+ 1
+ 0x7ffffffffffffffffffffffffffffffffffffffff;
+
+ 0x800000000000000000000000000000000000000c9
+ 0x715169c109c612e390d347c748342bcd3b02a0bef
+ 0x2fe13c0537bbc11acaa07d793de4e6d5e5c94eee8
+ 0x05679b353caa46825fea2d3713ba450da0c2a4541;
+
+ 0x20000000000000000000000000000000000000004000000000000000001
+ 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9
+ 0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad
+ 0x1a003e0962d4f9a8e407c904a9538163adb825212600c7752ad52233279;
+
+ 0x20000000000000000000000000000000000000004000000000000000001
+ 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9
+ 0x0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b
+ 0x18b863524b3cdfefb94f2784e0b116faac54404bc9162a363bab84a14c5;
+
+ 0x20000000000000000000000000000000000000004000000000000000001
+ 0x1499e398ac5d79e368559b35ca49bb7305da6c0390bcf9e2300253203c9
+ 0x1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052
+ 0x04925df77bd8b8ff1a5ff519417822bfedf2bbd752644292c98c7af6e02;
+
+
+}
projects / u / mdw / catacomb / commitdiff