$(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')) \
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',
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 \
--- /dev/null
+#! /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");
+}
--- /dev/null
+/* -*-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
--- /dev/null
+# $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 ----------------------------------------------------
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))
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);
}
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
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);
}
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
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 }
};
}
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);
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);
}
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
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);
}
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
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);
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
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);
}
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
{ "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 }
};
#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
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++) {
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 ----------------------------------------------------------*/
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;
} 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);
/* -*-c-*-
*
- * $Id: dh.h,v 1.9 2004/04/08 01:36:15 mdw Exp $
+ * $Id$
*
* Diffie-Hellman and related public-key systems
*
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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 <mLib/sub.h>
+
+#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 -------------------------------------------------*/
# include "mpmont.h"
#endif
+#ifndef CATACOMB_GFREDUCE_H
+# include "gfreduce.h"
+#endif
+
#ifndef CATACOMB_GROUP_H
# include "group.h"
#endif
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
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@ --- *
/* -*-c-*-
*
- * $Id: key-data.h,v 1.4 2004/04/08 01:36:15 mdw Exp $
+ * $Id$
*
* Manipulating key data
*
*/
extern int key_write(key_data */*k*/, dstr */*d*/,
- const key_filter */*kf*/);
+ const key_filter */*kf*/);
/*----- Key binary encoding -----------------------------------------------*/
#include <noise.h>
#include <rand.h>
+#include "bintab.h"
#include "bbs.h"
#include "dh.h"
#include "dsa.h"
#include "ectab.h"
#include "fibrand.h"
#include "getdate.h"
+#include "gfreduce.h"
#include "key.h"
#include "mp.h"
#include "mpmont.h"
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;
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 };
{ "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 }
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, \
#! /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)
{
BEGIN {
print "/* -*-c-*-";
print " *";
- print " * Table of elliptic curves [generated]";
+ print " * Table of prime groups [generated]";
print " */";
print "";
print "#include \"ptab.h\"";
--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+
+#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);
+ }
+}