From 3688eb757240b2332f67ec827be8caf6f6abe924 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 20 Oct 2004 00:18:07 +0000 Subject: [PATCH] Support subgroups of binary fields. --- Makefile.m4 | 11 +++- bin-gentab.awk | 102 ++++++++++++++++++++++++++++++++ bintab.h | 57 ++++++++++++++++++ bintab.in | 37 ++++++++++++ cc-kem.c | 38 ++++++++++-- cc-sig.c | 70 +++++++++++++++++++--- dh-param.c | 62 ++++++++++++++++---- dh.h | 9 +-- g-bin.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ group-guts.h | 11 ++++ group.h | 16 ++++++ key-data.h | 4 +- keyutil.c | 123 +++++++++++++++++++++++++++++++++++++-- p-gentab.awk | 4 +- utils/bingen.c | 58 +++++++++++++++++++ 15 files changed, 743 insertions(+), 38 deletions(-) create mode 100755 bin-gentab.awk create mode 100644 bintab.h create mode 100644 bintab.in create mode 100644 g-bin.c create mode 100644 utils/bingen.c diff --git a/Makefile.m4 b/Makefile.m4 index de3f154..9753dc3 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -113,6 +113,10 @@ ptab.c: ptab.in p-gentab.awk mpdump $(srcdir)/p-gentab.awk <$(srcdir)/ptab.in >ptab.c.new mv ptab.c.new ptab.c +bintab.c: bintab.in bin-gentab.awk mpdump + $(srcdir)/bin-gentab.awk <$(srcdir)/bintab.in >bintab.c.new + mv bintab.c.new bintab.c + gciphertab.c: gengctab $(srcdir)/gengctab gccipher gcipher >gciphertab.c.new \ "lit(join(`ciphers', `-', `cipher_modes')) \ @@ -179,9 +183,10 @@ define(`MP_SOURCES', mpbarrett.c mpbarrett-exp.c mpbarrett-mexp.c mpbarrett-exp.h \ mpmont.c mpmont-exp.c mpmont-mexp.c mpmont-exp.h \ mpreduce.c mpreduce-exp.h \ - group-stdops.c group-exp.c group-exp.h g-prime.c group-parse.c \ + group-stdops.c group-exp.c group-exp.h g-prime.c g-bin.c \ + group-parse.c \ group-string.c group-file.c group-dstr.c \ - rho.c buf.c ptab.c \ + rho.c buf.c ptab.c bintab.c \ GF_SOURCES PGEN_SOURCES EC_SOURCES') define(`GF_SOURCES', @@ -325,7 +330,7 @@ man_MANS = key.1 dsig.1 cookie.1 catcrypt.1 hashsum.1 keyring.5 pixie.1 EXTRA_DIST = \ Makefile.m4 genmodes gengctab $(man_MANS) xpixie \ group-test.c rsa-test.c \ - ectab.in ec-gentab.awk ptab.in p-gentab.awk \ + ectab.in ec-gentab.awk ptab.in p-gentab.awk bin-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 \ diff --git a/bin-gentab.awk b/bin-gentab.awk new file mode 100755 index 0000000..fb8630e --- /dev/null +++ b/bin-gentab.awk @@ -0,0 +1,102 @@ +#! /usr/bin/awk -f +# +# $Id: p-gentab.awk 2187 2004-09-04 07:50:08Z mdw $ + +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 binary groups [generated]"; + print " */"; + print ""; + print "#include \"bintab.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("Binary group 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 bindata bin_" 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] = "bin_" 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 binentry bintab[] = {"; + 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/bintab.h b/bintab.h new file mode 100644 index 0000000..ef4d814 --- /dev/null +++ b/bintab.h @@ -0,0 +1,57 @@ +/* -*-c-*- + * + * $Id$ + * + * Table of standard (ish) binary groups + * + * (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. + */ + +#ifndef CATACOMB_BINTAB_H +#define CATACOMB_BINTAB_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include "mp.h" +#include "ptab.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef pdata bindata; +typedef pentry binentry; + +/*----- Global variables --------------------------------------------------*/ + +extern const binentry bintab[]; + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/bintab.in b/bintab.in new file mode 100644 index 0000000..debe112 --- /dev/null +++ b/bintab.in @@ -0,0 +1,37 @@ +# $Id$ +# +# Standard binary groups + +#----- From P1363 annex A --------------------------------------------------- + +group p1363-40 + p 0x200000000000000000000000000000000000000000000065 + q 0xabbcb671934086d21ff5f7 + g 0x66704fca38d7962439e5f9bdab4d9ac6f0dd745c72f822e + +group p1363-56 + p 0x100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100d + q 0x5538ed0653399777d80d50e508fd01 + g 0x44e2fd3317b4a1968ce65b7e72f8d64262987d0a818a5a5189a6d588b67317c9ee05a38e3e5691e34933e3e050543d8b + +group p1363-64 + p 0x4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000800001 + q 0x84b73a6a902299c1aeeb8b537f1ea87c1 + g 0xce10e3ae38cacb7c1076723b80be855c629c03abef26d2a5ca898f75d2bd794daa9e21781f063ab2785a8c402f976d73e5c8d66072cd950dee1ea722bb8f3d + +group p1363-80 + p 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080043 + q 0x519f0cb14cf36cfcda7d08fab2b578314c9542801 + g 0xd0f0d0046d995f82b1599c7bceb20010b2ec0d27748d113c532657584c9ea11ab6be6b7236cfafc2a087503e1ad108e559206d559e7c30f4a516da71fa3e08fc50e03084f18af4a59e9c6835beb67dfd2b47ef8d0ea30d8f65e378e9ba82819ffc0ade685fa6cb346dcecca7134893db0a6950c2beab89ee38508f03f2f1f186 + +group p1363-112 + p 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040481 + q 0x399ac734bd00a6f622bdd00c5f930dcf2ae5d7c521755f7b664f104e423bddd + g 0x40154611e5cd5d4826382b23d4ba28fa9d050bb4db5e81b90816fa2823b62328798b70c061734b327e7e3221002a08554e4902f26c476a152380f49e7e2624066de81ef26ddabf4b2c4cc9374f60189e4e5446e04c39d1de05947c54eb6d8c63e498a83d5025ea9fcf2ff3195fb76d76cc2df73918268b72f693a28a01c14622351cc53546bdaacfc95ad19aee16d3d88fbb5fe8143a8a3dcf3d48525be95bef28921edcee081b5269d0b5307ed97f55e5d0218dd17a39f393e017fcfe999626f1fc6ae9a485395a62a3e969d2e0cce55755cc0e22c4356741313d762505c9a2594af3e94d8f913798d92ccf6a73d2447c474ed2924a29856c5c2feeb178a35b15545 + +group p1363-128 + p 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002441 + q 0xa5c52c0d53fc1f43b2cbfd7447d53d55c37004338502dfda0f31b7df76bde74081 + g 0x9447bb7ca087a37a5268c9e4cd3b9c3eb752272af39657d616181d28f18634368ba972a26b93b2980b391e23d7a9313785a5a17adfd9f810a3677cc20342965e09afc81b8413c5b3054c3adffec6411f088942d5877eef220b2a01cd7c48e8bae8f394b2a0893eb293f6355fc3ea962e503ae1d6fd0c3d718de374100cf89cb9c72e125fac9f930abb9959d03ef18354dd16f3a51e42e2c43ef100a8c3ca9523e6decbdf1f67db454df5781d16d55e94663f9633985d2f76b71a9bb10a985a8c6e8cb4190bef038798e9f402ea8027698e9d28a4ee14f0a6724f38dab82578a0e9600fa5717f40d8f107cb148c896c3061945318b25436c04f84a1b0fa043417bf7904915fa6afaed5fd24c73a5a1328973f39e8bc930ccc3099d7f715f8738b13d0b113899200b2293cdba34a46d22c0fab4d8ed33a71c691ba90687000030ad2fe05b5668520e24edb37edcf43827d9cf0b96ff776f88a2041eadd6902e12428716b46533d765d + +#----- That's all, folks ---------------------------------------------------- diff --git a/cc-kem.c b/cc-kem.c index 8ba29fd..aaa21bd 100644 --- a/cc-kem.c +++ b/cc-kem.c @@ -169,14 +169,16 @@ typedef struct dh_encctx { ge *y; } dh_encctx; -static dh_encctx *dh_doinit(key *k, const gprime_param *gp, mp *y) +static dh_encctx *dh_doinit(key *k, const gprime_param *gp, mp *y, + group *(*makegroup)(const gprime_param *), + const char *what) { dh_encctx *de = CREATE(dh_encctx); dstr t = DSTR_INIT; key_fulltag(k, &t); - if ((de->g = group_prime(gp)) == 0) - die(EXIT_FAILURE, "bad prime group in key `%s'", t.buf); + if ((de->g = makegroup(gp)) == 0) + die(EXIT_FAILURE, "bad %s group in key `%s'", what, t.buf); de->x = MP_NEW; de->y = G_CREATE(de->g); if (G_FROMINT(de->g, de->y, y)) @@ -207,7 +209,14 @@ static dh_encctx *ec_doinit(key *k, const char *cstr, const ec *y) static kem *dh_encinit(key *k, void *kd) { dh_pub *dp = kd; - dh_encctx *de = dh_doinit(k, &dp->dp, dp->y); + dh_encctx *de = dh_doinit(k, &dp->dp, dp->y, group_prime, "prime"); + return (&de->k); +} + +static kem *bindh_encinit(key *k, void *kd) +{ + dh_pub *dp = kd; + dh_encctx *de = dh_doinit(k, &dp->dp, dp->y, group_binary, "binary"); return (&de->k); } @@ -267,6 +276,11 @@ static const kemops dh_encops = { dh_encinit, dh_encdoit, dh_enccheck, dh_encdestroy }; +static const kemops bindh_encops = { + dh_pubfetch, sizeof(dh_pub), + bindh_encinit, dh_encdoit, dh_enccheck, dh_encdestroy +}; + static const kemops ec_encops = { ec_pubfetch, sizeof(ec_pub), ec_encinit, dh_encdoit, dh_enccheck, dh_encdestroy @@ -275,7 +289,15 @@ static const kemops ec_encops = { static kem *dh_decinit(key *k, void *kd) { dh_priv *dp = kd; - dh_encctx *de = dh_doinit(k, &dp->dp, dp->y); + dh_encctx *de = dh_doinit(k, &dp->dp, dp->y, group_prime, "prime"); + de->x = MP_COPY(dp->x); + return (&de->k); +} + +static kem *bindh_decinit(key *k, void *kd) +{ + dh_priv *dp = kd; + dh_encctx *de = dh_doinit(k, &dp->dp, dp->y, group_binary, "binary"); de->x = MP_COPY(dp->x); return (&de->k); } @@ -317,6 +339,11 @@ static const kemops dh_decops = { dh_decinit, dh_decdoit, dh_enccheck, dh_encdestroy }; +static const kemops bindh_decops = { + dh_privfetch, sizeof(dh_priv), + bindh_decinit, dh_decdoit, dh_enccheck, dh_encdestroy +}; + static const kemops ec_decops = { ec_privfetch, sizeof(ec_priv), ec_decinit, dh_decdoit, dh_enccheck, dh_encdestroy @@ -327,6 +354,7 @@ static const kemops ec_decops = { const struct kemtab kemtab[] = { { "rsa", &rsa_encops, &rsa_decops }, { "dh", &dh_encops, &dh_decops }, + { "bindh", &bindh_encops, &bindh_decops }, { "ec", &ec_encops, &ec_decops }, { 0, 0, 0 } }; diff --git a/cc-sig.c b/cc-sig.c index b7ce0b7..027fa52 100644 --- a/cc-sig.c +++ b/cc-sig.c @@ -288,14 +288,16 @@ static void dsa_initcommon(dsa_sigctx *ds, const gchash *hc, } static dsa_sigctx *dsa_doinit(key *k, const gprime_param *gp, - mp *y, const gchash *hc) + mp *y, const gchash *hc, + group *(*makegroup)(const gprime_param *), + const char *what) { dsa_sigctx *ds = CREATE(dsa_sigctx); dstr t = DSTR_INIT; key_fulltag(k, &t); - if ((ds->g.g = group_prime(gp)) == 0) - die(EXIT_FAILURE, "bad prime group in key `%s'", t.buf); + if ((ds->g.g = makegroup(gp)) == 0) + die(EXIT_FAILURE, "bad %s group in key `%s'", what, t.buf); ds->g.p = G_CREATE(ds->g.g); if (G_FROMINT(ds->g.g, ds->g.p, y)) die(EXIT_FAILURE, "bad public key in key `%s'", t.buf); @@ -327,7 +329,15 @@ static dsa_sigctx *ecdsa_doinit(key *k, const char *cstr, static sig *dsa_siginit(key *k, void *kd, const gchash *hc) { dh_priv *dp = kd; - dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc); + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_prime, "prime"); + ds->g.u = MP_COPY(dp->x); + return (&ds->s); +} + +static sig *bindsa_siginit(key *k, void *kd, const gchash *hc) +{ + dh_priv *dp = kd; + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_binary, "binary"); ds->g.u = MP_COPY(dp->x); return (&ds->s); } @@ -379,6 +389,11 @@ static const sigops dsa_sig = { dsa_siginit, dsa_sigdoit, dsa_sigcheck, dsa_sigdestroy }; +static const sigops bindsa_sig = { + dh_privfetch, sizeof(dh_priv), + bindsa_siginit, dsa_sigdoit, dsa_sigcheck, dsa_sigdestroy +}; + static const sigops ecdsa_sig = { ec_privfetch, sizeof(ec_priv), ecdsa_siginit, dsa_sigdoit, dsa_sigcheck, dsa_sigdestroy @@ -387,7 +402,14 @@ static const sigops ecdsa_sig = { static sig *dsa_vrfinit(key *k, void *kd, const gchash *hc) { dh_pub *dp = kd; - dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc); + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_prime, "prime"); + return (&ds->s); +} + +static sig *bindsa_vrfinit(key *k, void *kd, const gchash *hc) +{ + dh_pub *dp = kd; + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_binary, "binary"); return (&ds->s); } @@ -417,6 +439,11 @@ static const sigops dsa_vrf = { dsa_vrfinit, dsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy }; +static const sigops bindsa_vrf = { + dh_pubfetch, sizeof(dh_pub), + bindsa_vrfinit, dsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy +}; + static const sigops ecdsa_vrf = { ec_pubfetch, sizeof(ec_pub), ecdsa_vrfinit, dsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy @@ -433,7 +460,16 @@ static void kcdsa_sethash(dsa_sigctx *ds, const gchash *hc) static sig *kcdsa_siginit(key *k, void *kd, const gchash *hc) { dh_priv *dp = kd; - dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc); + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_prime, "prime"); + kcdsa_privkey(ds, dp->x); + kcdsa_sethash(ds, hc); + return (&ds->s); +} + +static sig *binkcdsa_siginit(key *k, void *kd, const gchash *hc) +{ + dh_priv *dp = kd; + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_binary, "binary"); kcdsa_privkey(ds, dp->x); kcdsa_sethash(ds, hc); return (&ds->s); @@ -468,6 +504,11 @@ static const sigops kcdsa_sig = { kcdsa_siginit, kcdsa_sigdoit, dsa_sigcheck, dsa_sigdestroy }; +static const sigops binkcdsa_sig = { + dh_privfetch, sizeof(dh_priv), + binkcdsa_siginit, kcdsa_sigdoit, dsa_sigcheck, dsa_sigdestroy +}; + static const sigops eckcdsa_sig = { ec_privfetch, sizeof(ec_priv), eckcdsa_siginit, kcdsa_sigdoit, dsa_sigcheck, dsa_sigdestroy @@ -476,7 +517,15 @@ static const sigops eckcdsa_sig = { static sig *kcdsa_vrfinit(key *k, void *kd, const gchash *hc) { dh_pub *dp = kd; - dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc); + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_prime, "prime"); + kcdsa_sethash(ds, hc); + return (&ds->s); +} + +static sig *binkcdsa_vrfinit(key *k, void *kd, const gchash *hc) +{ + dh_pub *dp = kd; + dsa_sigctx *ds = dsa_doinit(k, &dp->dp, dp->y, hc, group_binary, "binary"); kcdsa_sethash(ds, hc); return (&ds->s); } @@ -510,6 +559,11 @@ static const sigops kcdsa_vrf = { kcdsa_vrfinit, kcdsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy }; +static const sigops binkcdsa_vrf = { + dh_pubfetch, sizeof(dh_pub), + binkcdsa_vrfinit, kcdsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy +}; + static const sigops eckcdsa_vrf = { ec_pubfetch, sizeof(ec_pub), eckcdsa_vrfinit, kcdsa_vrfdoit, dsa_sigcheck, dsa_sigdestroy @@ -521,8 +575,10 @@ const struct sigtab sigtab[] = { { "rsapkcs1", &rsap1_sig, &rsap1_vrf, &sha }, { "rsapss", &rsapss_sig, &rsapss_vrf, &sha }, { "dsa", &dsa_sig, &dsa_vrf, &sha }, + { "bindsa", &bindsa_sig, &bindsa_vrf, &sha }, { "ecdsa", &ecdsa_sig, &ecdsa_vrf, &sha }, { "kcdsa", &kcdsa_sig, &kcdsa_vrf, &has160 }, + { "binkcdsa", &binkcdsa_sig, &binkcdsa_vrf, &has160 }, { "eckcdsa", &eckcdsa_sig, &eckcdsa_vrf, &has160 }, { 0, 0, 0 } }; diff --git a/dh-param.c b/dh-param.c index 5ecb3cb..b02e84b 100644 --- a/dh-param.c +++ b/dh-param.c @@ -31,10 +31,11 @@ #include "dh.h" #include "ptab.h" +#include "bintab.h" /*----- Main code ---------------------------------------------------------*/ -/* --- @dh_parse@ --- * +/* --- @dh_parse@, @dhbin_parse@ --- * * * Arguments: @qd_parse *qd@ = parser context * @dh_param *dp@ = parameters to fill in @@ -49,9 +50,22 @@ static void getinfo(dh_param *dp, pdata *pd) { dp->p = &pd->p; dp->q = &pd->q; dp->g = &pd->g; } -int dh_parse(qd_parse *qd, dh_param *dp) +static int parse(qd_parse *qd, gprime_param *dp) { mp *p = MP_NEW, *q = MP_NEW, *g = MP_NEW; + + if ((p = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); if ((q = qd_getmp(qd)) == 0) goto fail; + qd_delim(qd, ','); if ((g = qd_getmp(qd)) == 0) goto fail; + dp->p = p; dp->q = q; dp->g = g; + return (0); +fail: + mp_drop(p); mp_drop(q); mp_drop(g); + return (-1); +} + +int dh_parse(qd_parse *qd, dh_param *dp) +{ const pentry *pe; for (pe = ptab; pe->name; pe++) { @@ -60,16 +74,26 @@ int dh_parse(qd_parse *qd, dh_param *dp) goto found; } } - if ((p = qd_getmp(qd)) == 0) goto fail; - qd_delim(qd, ','); if ((q = qd_getmp(qd)) == 0) goto fail; - qd_delim(qd, ','); if ((g = qd_getmp(qd)) == 0) goto fail; - dp->p = p; dp->q = q; dp->g = g; + if (parse(qd, dp)) + return (-1); found: return (0); +} -fail: - mp_drop(p); mp_drop(q); mp_drop(g); - return (-1); +int dhbin_parse(qd_parse *qd, gbin_param *gb) +{ + const binentry *be; + + for (be = bintab; be->name; be++) { + if (qd_enum(qd, be->name) >= 0) { + getinfo(gb, be->data); + goto found; + } + } + if (parse(qd, gb)) + return (-1); +found: + return (0); } /*----- Test rig ----------------------------------------------------------*/ @@ -81,12 +105,13 @@ fail: int main(int argc, char *argv[]) { const pentry *pe; + const binentry *be; const char *e; int ok = 1; grand *gr; gr = fibrand_create(0); - fputs("checking standard prime fields...\n", stdout); + fputs("checking standard prime groups...\n", stdout); for (pe = ptab; pe->name; pe++) { dh_param dp; group *g; @@ -108,6 +133,23 @@ int main(int argc, char *argv[]) } else fputs("ok\n", stdout); } + fputs("checking standard binary groups...\n", stdout); + for (be = bintab; be->name; be++) { + gbin_param gb; + group *g; + getinfo(&gb, be->data); + printf(" %s: ", be->name); + g = group_binary(&gb); + fflush(stdout); + e = G_CHECK(g, gr); + G_DESTROYGROUP(g); + dh_paramfree(&gb); + if (e) { + printf("fails: %s\n", e); + ok = 0; + } else + fputs("ok\n", stdout); + } gr->ops->destroy(gr); if (ok) fputs("all ok\n", stdout); diff --git a/dh.h b/dh.h index 5fcb611..8288740 100644 --- a/dh.h +++ b/dh.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: dh.h,v 1.9 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * Diffie-Hellman and related public-key systems * @@ -182,19 +182,20 @@ extern int dh_limlee(dh_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/, extern int dh_checkparam(keycheck */*kc*/, const dh_param */*dp*/, mp **/*v*/, size_t /*n*/); -/* --- @dh_parse@ --- * +/* --- @dh_parse@, @dhbin_parse@ --- * * * Arguments: @qd_parse *qd@ = parser context * @dh_param *dp@ = parameters to fill in * * Returns: Zero if OK, nonzero on error. * - * Use: Parses a prime group string. This is either one of the - * standard group strings, or a %$p$%, %$q$%, %$g$% triple + * Use: Parses a prime/binary group string. This is either one of + * the standard group strings, or a %$p$%, %$q$%, %$g$% triple * separated by commas. */ extern int dh_parse(qd_parse */*qd*/, dh_param */*dp*/); +extern int dhbin_parse(qd_parse */*qd*/, gbin_param */*gb*/); /*----- That's all, folks -------------------------------------------------*/ diff --git a/g-bin.c b/g-bin.c new file mode 100644 index 0000000..4718178 --- /dev/null +++ b/g-bin.c @@ -0,0 +1,179 @@ +/* -*-c-*- + * + * $Id$ + * + * Abstraction for prime groups + * + * (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. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "mpmont.h" +#include "pgen.h" + +#define ge mp * +#include "group.h" +#include "group-guts.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- Group operations --- */ + +static void gdestroygroup(group *gg) { + gctx_bin *g = (gctx_bin *)gg; + mp_drop(g->gen); mp_drop(g->g.r); mp_drop(g->g.h); + gfreduce_destroy(&g->r); + DESTROY(g); +} + +static mp **gcreate(group *gg) + { mp **x = CREATE(mp *); *x = MP_COPY(*gg->i); return (x); } + +static void gcopy(group *gg, mp **d, mp **x) + { mp *t = MP_COPY(*x); MP_DROP(*d); *d = t; } + +static void gburn(group *gg, mp **x) { (*x)->f |= MP_BURN; } + +static void gdestroy(group *gg, mp **x) { MP_DROP(*x); DESTROY(x); } + +static int gsamep(group *gg, group *hh) { + gctx_bin *g = (gctx_bin *)gg, *h = (gctx_bin *)hh; + return (MP_EQ(g->r.p, h->r.p)); +} + +static int geq(group *gg, mp **x, mp **y) { return (MP_EQ(*x, *y)); } + +static const char *gcheck(group *gg, grand *gr) { + gctx_bin *g = (gctx_bin *)gg; int rc; mp *t, *tt; + if (!gf_irreduciblep(g->r.p)) return ("p is not irreducible"); + t = mp_mul(MP_NEW, g->g.r, g->g.h); t = mp_add(t, t, MP_ONE); + tt = mp_lsl(MP_NEW, MP_ONE, g->g.nbits); + rc = MP_EQ(t, tt); MP_DROP(t); MP_DROP(tt); + if (!rc) return ("not a subgroup"); + return (group_stdcheck(gg, gr)); +} + +static void gmul(group *gg, mp **d, mp **x, mp **y) { + gctx_bin *g = (gctx_bin *)gg; mp *r = gf_mul(*d, *x, *y); + *d = gfreduce_do(&g->r, r, r); +} + +static void gsqr(group *gg, mp **d, mp **x) { + gctx_bin *g = (gctx_bin *)gg; mp *r = gf_sqr(*d, *x); + *d = gfreduce_do(&g->r, r, r); +} + +static void ginv(group *gg, mp **d, mp **x) + { gctx_bin *g = (gctx_bin *)gg; *d = gf_modinv(*d, *x, g->r.p); } + +static void gexp(group *gg, mp **d, mp **x, mp *n) + { gctx_bin *g = (gctx_bin *)gg; *d = gfreduce_exp(&g->r, *d, *x, n); } + +static int gread(group *gg, mp **d, const mptext_ops *ops, void *p) { + mp *t; if ((t = mp_read(MP_NEW, 0, ops, p)) == 0) return (-1); + mp_drop(*d); *d = t; return (0); +} + +static int gwrite(group *gg, mp **x, const mptext_ops *ops, void *p) { + int rc = -1; + if (!ops->put("0x", 2, p) && !mp_write(*x, 16, ops, p)) rc = 0; + return (rc); +} + +static mp *gtoint(group *gg, mp *d, mp **x) { return MP_COPY(*x); } + +static int gfromint(group *gg, mp **d, mp *x) { *d = MP_COPY(x); return 0; } + +static int gtobuf(group *gg, buf *b, mp **x) + { int rc = buf_putmp(b, *x); return (rc); } + +static int gfrombuf(group *gg, buf *b, mp **d) { + gctx_bin *g = (gctx_bin *)gg; mp *x; + if ((x = buf_getmp(b)) == 0) return (-1); + MP_DROP(*d); *d = gfreduce_do(&g->r, x, x); + return (0); +} + +static int gtoraw(group *gg, buf *b, mp **x) { + gctx_bin * g = (gctx_bin *)gg; octet *q; + if ((q = buf_get(b, g->g.noctets)) == 0) return (-1); + mp_storeb(*x, q, g->g.noctets); return (0); +} + +static int gfromraw(group *gg, buf *b, mp **d) { + gctx_bin * g = (gctx_bin *)gg; mp *x; octet *q; + if ((q = buf_get(b, g->g.noctets)) == 0) return (-1); + x = mp_loadb(MP_NEW, q, g->g.noctets); + MP_DROP(*d); *d = gfreduce_do(&g->r, x, x); + return (0); +} + +/* --- @group_binary@ --- * + * + * Arguments: @const gbin_param *gb@ = group parameters + * + * Returns: A pointer to the group, or null. + * + * Use: Constructs an abstract group interface for a subgroup of a + * prime field. Group elements are @mp *@ pointers. + */ + +static const group_ops gops = { + GTY_BINARY, "bin", + gdestroygroup, gcreate, gcopy, gburn, gdestroy, + gsamep, geq, group_stdidentp, + gcheck, + gmul, gsqr, ginv, group_stddiv, gexp, group_stdmexp, + gread, gwrite, + gtoint, gfromint, group_stdtoec, group_stdfromec, gtobuf, gfrombuf, + gtoraw, gfromraw +}; + +group *group_binary(const gbin_param *gb) +{ + gctx_bin *g; + mp *t; + + if (!MP_POSP(gb->p)) + return (0); + g = CREATE(gctx_bin); + g->g.ops = &gops; + g->g.nbits = mp_bits(gb->p) - 1; + g->g.noctets = (g->g.nbits + 7) >> 3; + gfreduce_create(&g->r, gb->p); + g->one = MP_ONE; + g->g.i = &g->one; + g->gen = MP_COPY(gb->g); + g->g.g = &g->gen; + g->g.r = MP_COPY(gb->q); + t = mp_lsl(MP_NEW, MP_ONE, g->g.nbits); + t = mp_sub(t, t, MP_ONE); + g->g.h = MP_NEW; mp_div(&g->g.h, 0, t, gb->q); + MP_DROP(t); + return (&g->g); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/group-guts.h b/group-guts.h index c684579..8fbebe7 100644 --- a/group-guts.h +++ b/group-guts.h @@ -48,6 +48,10 @@ # include "mpmont.h" #endif +#ifndef CATACOMB_GFREDUCE_H +# include "gfreduce.h" +#endif + #ifndef CATACOMB_GROUP_H # include "group.h" #endif @@ -66,6 +70,13 @@ typedef struct gctx_ec { ec_info ei; } gctx_ec; +typedef struct gctx_bin { + group g; + mp *gen; + mp *one; + gfreduce r; +} gctx_bin; + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus diff --git a/group.h b/group.h index aae0e60..5ea7786 100644 --- a/group.h +++ b/group.h @@ -341,6 +341,22 @@ typedef struct gprime_param { group *group_prime(const gprime_param */*gp*/); +/*----- Binary field subgroups --------------------------------------------*/ + +typedef gprime_param gbin_param; + +/* --- @group_binary@ --- * + * + * Arguments: @const gbin_param *gb@ = group parameters + * + * Returns: A pointer to the group, or null. + * + * Use: Constructs an abstract group interface for a subgroup of a + * prime field. Group elements are @mp *@ pointers. + */ + +group *group_binary(const gbin_param */*gp*/); + /*----- Elliptic curve groups ---------------------------------------------*/ /* --- @group_ec@ --- * diff --git a/key-data.h b/key-data.h index 40b8b4b..b9c9dc4 100644 --- a/key-data.h +++ b/key-data.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-data.h,v 1.4 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * Manipulating key data * @@ -367,7 +367,7 @@ extern int key_read(const char */*p*/, key_data */*k*/, char **/*pp*/); */ extern int key_write(key_data */*k*/, dstr */*d*/, - const key_filter */*kf*/); + const key_filter */*kf*/); /*----- Key binary encoding -----------------------------------------------*/ diff --git a/keyutil.c b/keyutil.c index 0b54df2..9ea8419 100644 --- a/keyutil.c +++ b/keyutil.c @@ -46,6 +46,7 @@ #include #include +#include "bintab.h" #include "bbs.h" #include "dh.h" #include "dsa.h" @@ -55,6 +56,7 @@ #include "ectab.h" #include "fibrand.h" #include "getdate.h" +#include "gfreduce.h" #include "key.h" #include "mp.h" #include "mpmont.h" @@ -570,18 +572,27 @@ static void alg_dhparam(keyopts *k) if (k->curve) { qd_parse qd; + group *g; + const char *e; if (strcmp(k->curve, "list") == 0) { unsigned i, w; - LIST("Built-in prime groups", stdout, ptab[i].name, ptab[i].name); + LIST("Built-in prime fields", stdout, ptab[i].name, ptab[i].name); exit(0); } qd.p = k->curve; if (dh_parse(&qd, &dp)) - die(EXIT_FAILURE, "error in group spec: %s", qd.e); + die(EXIT_FAILURE, "error in field spec: %s", qd.e); + if (!qd_eofp(&qd)) + die(EXIT_FAILURE, "junk at end of field spec"); + if ((g = group_prime(&dp)) == 0) + die(EXIT_FAILURE, "invalid prime field"); + if (!(k->f & f_quiet) && (e = G_CHECK(g, &rand_global)) != 0) + moan("WARNING! group check failed: %s", e); + G_DESTROYGROUP(g); goto done; } - + if (!k->bits) k->bits = 1024; @@ -698,6 +709,104 @@ static void alg_bbs(keyopts *k) bbs_privfree(&bp); } +static void alg_binparam(keyopts *k) +{ + static const char *pl[] = { "p", "q", "g", 0 }; + if (!copyparam(k, pl)) { + gbin_param gb; + qd_parse qd; + group *g; + const char *e; + key_data *kd = &k->k->k; + + /* --- Decide on a field --- */ + + if (!k->bits) k->bits = 128; + if (k->curve && strcmp(k->curve, "list") == 0) { + unsigned i, w; + LIST("Built-in binary fields", stdout, + bintab[i].name, bintab[i].name); + exit(0); + } + if (!k->curve) { + if (k->bits <= 40) k->curve = "p1363-40"; + else if (k->bits <= 56) k->curve = "p1363-56"; + else if (k->bits <= 64) k->curve = "p1363-64"; + else if (k->bits <= 80) k->curve = "p1363-80"; + else if (k->bits <= 112) k->curve = "p1363-112"; + else if (k->bits <= 128) k->curve = "p1363-128"; + else { + die(EXIT_FAILURE, + "no built-in binary fields provide %u-bit security", + k->bits); + } + } + + /* --- Check it --- */ + + qd.e = 0; + qd.p = k->curve; + if (dhbin_parse(&qd, &gb)) + die(EXIT_FAILURE, "error in field spec: %s", qd.e); + if (!qd_eofp(&qd)) + die(EXIT_FAILURE, "junk at end of field spec"); + if ((g = group_binary(&gb)) == 0) + die(EXIT_FAILURE, "invalid binary field"); + if (!(k->f & f_quiet) && (e = G_CHECK(g, &rand_global)) != 0) + moan("WARNING! group check failed: %s", e); + G_DESTROYGROUP(g); + + /* --- Write out the answer --- */ + + key_structure(kd); + mpkey(kd, "p", gb.p, KCAT_SHARE); + mpkey(kd, "q", gb.q, KCAT_SHARE); + mpkey(kd, "g", gb.g, KCAT_SHARE); + mp_drop(gb.q); + mp_drop(gb.p); + mp_drop(gb.g); + } +} + +static void alg_bin(keyopts *k) +{ + mp *x, *y; + mp *p, *q, *g; + gfreduce r; + key_data *kd = &k->k->k; + + /* --- Get the shared parameters --- */ + + alg_binparam(k); + p = getmp(kd, "p"); + q = getmp(kd, "q"); + g = getmp(kd, "g"); + + /* --- Choose a suitable private key --- * + * + * Since %$g$% has order %$q$%, choose %$x < q$%. + */ + + x = mprand_range(MP_NEWSEC, q, k->r, 0); + + /* --- Compute the public key %$y = g^x \bmod p$% --- */ + + gfreduce_create(&r, p); + y = gfreduce_exp(&r, MP_NEW, g, x); + gfreduce_destroy(&r); + + /* --- Store everything away --- */ + + mpkey(kd, "y", y, KCAT_PUB); + + kd = key_structcreate(kd, "private"); + key_structure(kd); + mpkey(kd, "x", x, KCAT_PRIV | KF_BURN); + dolock(k, kd, "private"); + + mp_drop(x); mp_drop(y); +} + static void alg_ecparam(keyopts *k) { static const char *pl[] = { "curve", 0 }; @@ -797,11 +906,13 @@ static keyalg algtab[] = { { "binary", alg_binary, "Plain binary data" }, { "des", alg_des, "Binary with DES-style parity" }, { "rsa", alg_rsa, "RSA public-key encryption" }, + { "bbs", alg_bbs, "Blum-Blum-Shub generator" }, { "dsa", alg_dsa, "DSA digital signatures" }, { "dsa-param", alg_dsaparam, "DSA shared parameters" }, { "dh", alg_dh, "Diffie-Hellman key exchange" }, { "dh-param", alg_dhparam, "Diffie-Hellman parameters" }, - { "bbs", alg_bbs, "Blum-Blum-Shub generator" }, + { "bindh", alg_bin, "DH over a binary field" }, + { "bindh-param", alg_binparam, "Binary-field DH parameters" }, { "ec-param", alg_ecparam, "Elliptic curve parameters" }, { "ec", alg_ec, "Elliptic curve crypto" }, { 0, 0 } @@ -1800,8 +1911,10 @@ static int cmd_merge(int argc, char *argv[]) ghashtab[i], ghashtab[i]->name) \ LI("Elliptic curves", ec, \ ectab[i].name, ectab[i].name) \ - LI("Diffie-Hellman groups", dh, \ + LI("Prime Diffie-Hellman groups", dh, \ ptab[i].name, ptab[i].name) \ + LI("Binary Diffie-Hellman groups", bindh, \ + bintab[i].name, bintab[i].name) \ LI("Key-generation algorithms", keygen, \ algtab[i].name, algtab[i].name) \ LI("Random seeding algorithms", seed, \ diff --git a/p-gentab.awk b/p-gentab.awk index a1b6da5..09a1c37 100755 --- a/p-gentab.awk +++ b/p-gentab.awk @@ -1,6 +1,6 @@ #! /usr/bin/awk -f # -# $Id: p-gentab.awk,v 1.1 2004/04/01 21:28:41 mdw Exp $ +# $Id$ function banner(name, s, i) { @@ -18,7 +18,7 @@ function fix(name) BEGIN { print "/* -*-c-*-"; print " *"; - print " * Table of elliptic curves [generated]"; + print " * Table of prime groups [generated]"; print " */"; print ""; print "#include \"ptab.h\""; diff --git a/utils/bingen.c b/utils/bingen.c new file mode 100644 index 0000000..cfbd8e0 --- /dev/null +++ b/utils/bingen.c @@ -0,0 +1,58 @@ +#include +#include + +#include "rand.h" +#include "group.h" +#include "gfreduce.h" + +int main(int argc, char *argv[]) +{ + mp *p, *q, *g, *gg, *t, *h; + gfreduce r; + group *grp; + gbin_param gb; + const char *e; + int i; + + t = MP_NEW; + q = mp_readstring(MP_NEW, argv[1], 0, 0); + p = MP_ZERO; + for (i = 2; i < argc; i++) { + t = mp_lsl(t, MP_ONE, atoi(argv[i])); + p = mp_add(p, p, t); + } + gfreduce_create(&r, p); + t = mp_lsl(t, MP_ONE, mp_bits(p) - 1); + t = mp_sub(t, t, MP_ONE); + h = MP_NEW; + mp_div(&h, &t, t, q); + assert(MP_ZEROP(t)); + g = MP_NEW; + gg = MP_TWO; + for (;;) { + g = gfreduce_exp(&r, g, gg, h); + t = gfreduce_exp(&r, t, g, q); + if (MP_EQ(t, MP_ONE) && !MP_EQ(g, MP_ONE)) { + gb.p = p; + gb.q = q; + gb.g = g; + grp = group_binary(&gb); + assert(grp); + if ((e = G_CHECK(grp, &rand_global)) != 0) { + fprintf(stderr, "badness: %s\n", e); + exit(1); + } + fputs(" p 0x", stdout); + mp_writefile(p, stdout, 16); + putchar('\n'); + fputs(" q 0x", stdout); + mp_writefile(q, stdout, 16); + putchar('\n'); + fputs(" g 0x", stdout); + mp_writefile(g, stdout, 16); + putchar('\n'); + return (0); + } + gg = mp_add(gg, gg, MP_ONE); + } +} -- 2.11.0