Support subgroups of binary fields.
[u/mdw/catacomb] / keyutil.c
index 174bbfe..9ea8419 100644 (file)
--- a/keyutil.c
+++ b/keyutil.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: keyutil.c,v 1.10 2000/10/08 12:02:21 mdw Exp $
+ * $Id$
  *
  * Simple key manager program
  *
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: keyutil.c,v $
- * Revision 1.10  2000/10/08 12:02:21  mdw
- * Use @MP_EQ@ instead of @MP_CMP@.
- *
- * Revision 1.9  2000/08/15 21:40:49  mdw
- * Minor formatting change in listing attributes.
- *
- * Revision 1.8  2000/07/29 09:59:13  mdw
- * Support Lim-Lee primes in Diffie-Hellman parameter generation.
- *
- * Revision 1.7  2000/07/01 11:18:51  mdw
- * Use new interfaces for key manipulation.
- *
- * Revision 1.6  2000/06/17 11:28:22  mdw
- * Use secure memory interface from MP library.  `rand_getgood' is
- * deprecated.
- *
- * Revision 1.5  2000/02/12 18:21:03  mdw
- * Overhaul of key management (again).
- *
- * Revision 1.4  1999/12/22 15:48:10  mdw
- * Track new key-management changes.  Support new key generation
- * algorithms.
- *
- * Revision 1.3  1999/11/02 15:23:24  mdw
- * Fix newlines in keyring list.
- *
- * Revision 1.2  1999/10/15 21:05:28  mdw
- * In `key list', show timezone for local times, and support `-u' option
- * for UTC output.
- *
- * Revision 1.1  1999/09/03 08:41:12  mdw
- * Initial import.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "config.h"
 #include <noise.h>
 #include <rand.h>
 
+#include "bintab.h"
 #include "bbs.h"
 #include "dh.h"
 #include "dsa.h"
+#include "dsarand.h"
+#include "ec.h"
+#include "ec-keys.h"
+#include "ectab.h"
 #include "fibrand.h"
 #include "getdate.h"
+#include "gfreduce.h"
 #include "key.h"
 #include "mp.h"
 #include "mpmont.h"
 #include "mprand.h"
 #include "mptext.h"
 #include "pgen.h"
+#include "ptab.h"
 #include "rsa.h"
 
+#include "cc.h"
+#include "sha-mgf.h"
+#include "sha256-mgf.h"
+#include "sha224-mgf.h"
+#include "sha384-mgf.h"
+#include "sha512-mgf.h"
+#include "tiger-mgf.h"
+#include "rmd128-mgf.h"
+#include "rmd160-mgf.h"
+#include "rmd256-mgf.h"
+#include "rmd320-mgf.h"
+#include "md5-mgf.h"
+#include "dsarand.h"
+
 /*----- Handy global state ------------------------------------------------*/
 
 static const char *keyfile = "keyring";
@@ -159,8 +142,11 @@ static void setattr(key_file *f, key *k, char *v[])
     int err;
     char *p = *v;
     size_t eq = strcspn(p, "=");
-    if (p[eq] == 0)
-      moan("invalid assignment: `%s'", p);
+    if (!p[eq]) {
+      moan("invalid assignment: `%s' (ignored)", p);
+      v++;
+      continue;
+    }
     p[eq] = 0;
     p += eq + 1;
     if ((err = key_putattr(f, k, *v, *p ? p : 0)) != 0)
@@ -169,6 +155,26 @@ static void setattr(key_file *f, key *k, char *v[])
   }
 }
 
+/*----- Seeding -----------------------------------------------------------*/
+
+const struct seedalg { const char *p; grand *(*gen)(const void *, size_t); }
+seedtab[] = {
+  { "dsarand",         dsarand_create },
+  { "rmd128-mgf",  rmd128_mgfrand },
+  { "rmd160-mgf",  rmd160_mgfrand },
+  { "rmd256-mgf",  rmd256_mgfrand },
+  { "rmd320-mgf",  rmd320_mgfrand },
+  { "sha-mgf",  sha_mgfrand },
+  { "sha224-mgf",  sha224_mgfrand },
+  { "sha256-mgf",  sha256_mgfrand },
+  { "sha384-mgf",  sha384_mgfrand },
+  { "sha512-mgf",  sha512_mgfrand },
+  { "tiger-mgf",  tiger_mgfrand },
+  { 0, 0 }
+};
+
+#define SEEDALG_DEFAULT (seedtab + 2)
+
 /*----- Key generation ----------------------------------------------------*/
 
 /* --- Key generation parameters --- */
@@ -179,16 +185,17 @@ typedef struct keyopts {
   dstr tag;                            /* Full tag name for the key */
   unsigned f;                          /* Flags for the new key */
   unsigned bits, qbits;                        /* Bit length for the new key */
+  const char *curve;                   /* Elliptic curve name/info */
+  grand *r;                            /* Random number source */
   key *p;                              /* Parameters key-data */
 } keyopts;
 
-enum {
-  f_bogus = 1,                         /* Error in parsing */
-  f_lock = 2,                          /* Passphrase-lock private key */
-  f_quiet = 4,                         /* Don't show a progress indicator */
-  f_limlee = 8,                                /* Generate Lim-Lee primes */
-  f_subgroup = 16                      /* Generate a subgroup */
-};
+#define f_bogus 1u                     /* Error in parsing */
+#define f_lock 2u                      /* Passphrase-lock private key */
+#define f_quiet 4u                     /* Don't show a progress indicator */
+#define f_limlee 8u                    /* Generate Lim-Lee primes */
+#define f_subgroup 16u                 /* Generate a subgroup */
+#define f_retag 32u                    /* Remove any existing tag */
 
 /* --- @dolock@ --- *
  *
@@ -244,6 +251,8 @@ static void mpkey(key_data *kd, const char *tag, mp *m, unsigned f)
 static int copyparam(keyopts *k, const char **pp)
 {
   key_filter kf;
+  key_attriter i;
+  const char *n, *v;
 
   /* --- Quick check if no parameters supplied --- */
 
@@ -267,6 +276,14 @@ static int copyparam(keyopts *k, const char **pp)
   kf.m = KF_CATMASK;
   if (!key_copy(&k->k->k, &k->p->k, &kf))
     die(EXIT_FAILURE, "unexpected failure while copying parameters");
+
+  /* --- Copy over attributes --- */
+
+  for (key_mkattriter(&i, k->p); key_nextattr(&i, &n, &v); )
+    key_putattr(k->kf, k->k, n, v);
+
+  /* --- Done --- */
+
   return (1);
 }
 
@@ -358,7 +375,7 @@ static void alg_binary(keyopts *k)
   sz = (k->bits + 7) >> 3;
   p = sub_alloc(sz);
   m = (1 << (((k->bits - 1) & 7) + 1)) - 1;
-  rand_get(RAND_GLOBAL, p, sz);
+  k->r->ops->fill(k->r, p, sz);
   *p &= m;
   key_binary(&k->k->k, p, sz);
   k->k->k.e |= KCAT_SYMM | KF_BURN;
@@ -374,7 +391,7 @@ static void alg_des(keyopts *k)
   int i;
 
   if (!k->bits)
-    k->bits = 112;
+    k->bits = 168;
   if (k->p)
     die(EXIT_FAILURE, "no shared parameters for DES keys");
   if (k->bits % 56 || k->bits > 168)
@@ -382,7 +399,7 @@ static void alg_des(keyopts *k)
 
   sz = k->bits / 7;
   p = sub_alloc(sz);
-  rand_get(RAND_GLOBAL, p, sz);        /* Too much work done here! */
+  k->r->ops->fill(k->r, p, sz);
   for (i = 0; i < sz; i++) {
     octet x = p[i] | 0x01;
     x = x ^ (x >> 4);
@@ -411,14 +428,14 @@ static void alg_rsa(keyopts *k)
 
   /* --- Generate the RSA parameters --- */
 
-  if (rsa_gen(&rp, k->bits, &rand_global, 0,
+  if (rsa_gen(&rp, k->bits, k->r, 0,
              (k->f & f_quiet) ? 0 : pgen_ev, 0))
     die(EXIT_FAILURE, "RSA key generation failed");
 
   /* --- Run a test encryption --- */
 
   {
-    grand *g = fibrand_create(rand_global.ops->word(&rand_global));
+    grand *g = fibrand_create(k->r->ops->word(k->r));
     rsa_pub rpp;
     mp *m = mprand_range(MP_NEW, rp.n, g, 0);
     mp *c;
@@ -465,6 +482,7 @@ static void alg_dsaparam(keyopts *k)
     dstr d = DSTR_INIT;
     base64_ctx c;
     key_data *kd = &k->k->k;
+    dsa_seed ds;
 
     /* --- Choose appropriate bit lengths if necessary --- */
 
@@ -477,11 +495,11 @@ static void alg_dsaparam(keyopts *k)
 
     sz = (k->qbits + 7) >> 3;
     p = sub_alloc(sz);
-    rand_get(RAND_GLOBAL, p, sz);
+    k->r->ops->fill(k->r, p, sz);
 
     /* --- Allocate the parameters --- */
 
-    if (dsa_gen(&dp, k->qbits, k->bits, 0, p, sz,
+    if (dsa_gen(&dp, k->qbits, k->bits, 0, p, sz, &ds,
                (k->f & f_quiet) ? 0 : pgen_ev, 0))
       die(EXIT_FAILURE, "DSA parameter generation failed");
 
@@ -500,9 +518,13 @@ static void alg_dsaparam(keyopts *k)
     base64_init(&c);
     c.maxline = 0;
     c.indent = "";
-    base64_encode(&c, p, sz, &d);
+    base64_encode(&c, ds.p, ds.sz, &d);
     base64_encode(&c, 0, 0, &d);
     key_putattr(k->kf, k->k, "seed", d.buf);
+    DRESET(&d);
+    dstr_putf(&d, "%u", ds.count);
+    key_putattr(k->kf, k->k, "count", d.buf);
+    xfree(ds.p);
     sub_free(p, sz);
     dstr_destroy(&d);
   }
@@ -524,7 +546,7 @@ static void alg_dsa(keyopts *k)
 
   /* --- Choose a private key --- */
 
-  x = mprand_range(MP_NEWSEC, q, &rand_global, 0);
+  x = mprand_range(MP_NEWSEC, q, k->r, 0);
   mpmont_create(&mm, p);
   y = mpmont_exp(&mm, MP_NEW, g, x);
 
@@ -543,11 +565,34 @@ static void alg_dsa(keyopts *k)
 static void alg_dhparam(keyopts *k)
 {
   static const char *pl[] = { "p", "q", "g", 0 };
+  key_data *kd = &k->k->k;
   if (!copyparam(k, pl)) {
     dh_param dp;
-    key_data *kd = &k->k->k;
     int rc;
 
+    if (k->curve) {
+      qd_parse qd;
+      group *g;
+      const char *e;
+      
+      if (strcmp(k->curve, "list") == 0) {
+       unsigned i, w;
+       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 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;
 
@@ -560,7 +605,7 @@ static void alg_dhparam(keyopts *k)
        k->qbits = 256;
       rc = dh_limlee(&dp, k->qbits, k->bits,
                     (k->f & f_subgroup) ? DH_SUBGROUP : 0,
-                    0, &rand_global, (k->f & f_quiet) ? 0 : pgen_ev, 0,
+                    0, k->r, (k->f & f_quiet) ? 0 : pgen_ev, 0,
                     (k->f & f_quiet) ? 0 : pgen_evspin, 0, &nf, &f);
       if (!rc) {
        dstr d = DSTR_INIT;
@@ -575,12 +620,13 @@ static void alg_dhparam(keyopts *k)
        dstr_destroy(&d);
       }
     } else
-      rc = dh_gen(&dp, k->qbits, k->bits, 0, &rand_global,
+      rc = dh_gen(&dp, k->qbits, k->bits, 0, k->r,
                  (k->f & f_quiet) ? 0 : pgen_ev, 0);
 
     if (rc)
       die(EXIT_FAILURE, "Diffie-Hellman parameter generation failed");
 
+  done:
     key_structure(kd);
     mpkey(kd, "p", dp.p, KCAT_SHARE);
     mpkey(kd, "q", dp.q, KCAT_SHARE);
@@ -588,7 +634,7 @@ static void alg_dhparam(keyopts *k)
     mp_drop(dp.q);
     mp_drop(dp.p);
     mp_drop(dp.g);
-  }    
+  }
 }
 
 static void alg_dh(keyopts *k)
@@ -610,7 +656,7 @@ static void alg_dh(keyopts *k)
    * Since %$g$% has order %$q$%, choose %$x < q$%.
    */
 
-  x = mprand_range(MP_NEWSEC, q, &rand_global, 0);
+  x = mprand_range(MP_NEWSEC, q, k->r, 0);
 
   /* --- Compute the public key %$y = g^x \bmod p$% --- */
 
@@ -644,7 +690,7 @@ static void alg_bbs(keyopts *k)
 
   /* --- Generate the BBS parameters --- */
 
-  if (bbs_gen(&bp, k->bits, &rand_global, 0,
+  if (bbs_gen(&bp, k->bits, k->r, 0,
              (k->f & f_quiet) ? 0 : pgen_ev, 0))
     die(EXIT_FAILURE, "Blum-Blum-Shub key generation failed");
 
@@ -663,6 +709,191 @@ 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 };
+  if (!copyparam(k, pl)) {
+    ec_info ei;
+    const char *e;
+    key_data *kd = &k->k->k;
+
+    /* --- Decide on a curve --- */
+
+    if (!k->bits) k->bits = 256;
+    if (k->curve && strcmp(k->curve, "list") == 0) {
+      unsigned i, w;
+      LIST("Built-in elliptic curves", stdout,
+          ectab[i].name, ectab[i].name);
+      exit(0);
+    }
+    if (!k->curve) {
+      if (k->bits <= 56) k->curve = "secp112r1";
+      else if (k->bits <= 64) k->curve = "secp128r1";
+      else if (k->bits <= 80) k->curve = "secp160r1";
+      else if (k->bits <= 96) k->curve = "secp192r1";
+      else if (k->bits <= 112) k->curve = "secp224r1";
+      else if (k->bits <= 128) k->curve = "secp256r1";
+      else if (k->bits <= 192) k->curve = "secp384r1";
+      else if (k->bits <= 256) k->curve = "secp521r1";
+      else
+       die(EXIT_FAILURE, "no built-in curves provide %u-bit security",
+           k->bits);
+    }
+
+    /* --- Check it --- */
+
+    if ((e = ec_getinfo(&ei, k->curve)) != 0)
+      die(EXIT_FAILURE, "error in curve spec: %s", e);
+    if (!(k->f & f_quiet) && (e = ec_checkinfo(&ei, k->r)) != 0)
+      moan("WARNING!  curve check failed: %s", e);
+    ec_freeinfo(&ei);
+
+    /* --- Write out the answer --- */
+
+    key_structure(kd);
+    kd = key_structcreate(kd, "curve");
+    key_string(kd, k->curve);
+    kd->e |= KCAT_SHARE;
+  }
+}
+
+static void alg_ec(keyopts *k)
+{
+  key_data *kd = &k->k->k;
+  key_data *kkd;
+  mp *x = MP_NEW;
+  ec p = EC_INIT;
+  const char *e;
+  ec_info ei;
+
+  /* --- Get the curve --- */
+
+  alg_ecparam(k);
+  if ((kkd = key_structfind(kd, "curve")) == 0)
+    die(EXIT_FAILURE, "unexpected failure looking up subkey `curve')");
+  if ((kkd->e & KF_ENCMASK) != KENC_STRING)
+    die(EXIT_FAILURE, "subkey `curve' is not a string");
+  if ((e = ec_getinfo(&ei, kkd->u.p)) != 0)
+    die(EXIT_FAILURE, "error in curve spec: %s", e);
+
+  /* --- Invent a private exponent and compute the public key --- */
+
+  x = mprand_range(MP_NEWSEC, ei.r, k->r, 0);
+  ec_mul(ei.c, &p, &ei.g, x);
+
+  /* --- Store everything away --- */
+
+  kkd = key_structcreate(kd, "p");
+  key_ec(kkd, &p);
+  kkd->e |= KCAT_PUB;
+  kkd = key_structcreate(kd, "private");
+  key_structure(kkd);
+  mpkey(kkd, "x", x, KCAT_PRIV | KF_BURN);
+
+  /* --- Done --- */
+
+  ec_freeinfo(&ei);
+  mp_drop(x);
+}
+
 /* --- The algorithm tables --- */
 
 typedef struct keyalg {
@@ -675,11 +906,15 @@ 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 }
 };
 
@@ -693,7 +928,10 @@ static int cmd_add(int argc, char *argv[])
   const char *c = 0;
   keyalg *alg = algtab;
   const char *rtag = 0;
-  keyopts k = { 0, 0, DSTR_INIT, 0, 0, 0, 0 };
+  const struct seedalg *sa = SEEDALG_DEFAULT;
+  keyopts k = { 0, 0, DSTR_INIT, 0, 0, 0, 0, 0 };
+  const char *seed = 0;
+  k.r = &rand_global;
 
   /* --- Parse options for the subcommand --- */
 
@@ -706,14 +944,19 @@ static int cmd_add(int argc, char *argv[])
       { "expire",      OPTF_ARGREQ,    0,      'e' },
       { "comment",     OPTF_ARGREQ,    0,      'c' },
       { "tag",         OPTF_ARGREQ,    0,      't' },
-      { "rand-id",     OPTF_ARGREQ,    0,      'r' },
+      { "rand-id",     OPTF_ARGREQ,    0,      'R' },
+      { "curve",       OPTF_ARGREQ,    0,      'C' },
+      { "seedalg",     OPTF_ARGREQ,    0,      'A' },
+      { "seed",                OPTF_ARGREQ,    0,      's' },
+      { "newseed",     OPTF_ARGREQ,    0,      'n' },
       { "lock",                0,              0,      'l' },
       { "quiet",       0,              0,      'q' },
       { "lim-lee",     0,              0,      'L' },
       { "subgroup",    0,              0,      'S' },
       { 0,             0,              0,      0 }
     };
-    int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:r:lqLS", opt, 0, 0, 0);
+    int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:R:C:A:s:n:lqrLS",
+                  opt, 0, 0, 0);
     if (i < 0)
       break;
 
@@ -791,6 +1034,12 @@ static int cmd_add(int argc, char *argv[])
        c = optarg;
        break;
 
+      /* --- Elliptic curve parameters --- */
+
+      case 'C':
+       k.curve = optarg;
+       break;
+
       /* --- Store tags --- */
 
       case 't':
@@ -798,10 +1047,63 @@ static int cmd_add(int argc, char *argv[])
          die(EXIT_FAILURE, "bad tag string `%s'", optarg);
        tag = optarg;
        break;
+      case 'r':
+       k.f |= f_retag;
+       break;
+
+      /* --- Seeding --- */
+
+      case 'A': {
+       const struct seedalg *ss;
+       if (strcmp(optarg, "list") == 0) {
+         printf("Seed algorithms:\n");
+         for (ss = seedtab; ss->p; ss++)
+           printf("  %s\n", ss->p);
+         exit(0);
+       }
+       if (seed) die(EXIT_FAILURE, "seed already set -- put -A first");
+       sa = 0;
+       for (ss = seedtab; ss->p; ss++) {
+         if (strcmp(optarg, ss->p) == 0)
+           sa = ss;
+       }
+       if (!sa)
+         die(EXIT_FAILURE, "seed algorithm `%s' not known", optarg);
+      } break;
 
+      case 's': {
+       base64_ctx b;
+       dstr d = DSTR_INIT;
+       if (seed) die(EXIT_FAILURE, "seed already set"); 
+       base64_init(&b);
+       base64_decode(&b, optarg, strlen(optarg), &d);
+       base64_decode(&b, 0, 0, &d);
+       k.r = sa->gen(d.buf, d.len);
+       seed = optarg;
+       dstr_destroy(&d);
+      } break;
+       
+      case 'n': {
+       base64_ctx b;
+       dstr d = DSTR_INIT;
+       char *p;
+       unsigned n = strtoul(optarg, &p, 0);
+       if (n == 0 || *p != 0 || n % 8 != 0)
+         die(EXIT_FAILURE, "bad seed length `%s'", optarg);
+       if (seed) die(EXIT_FAILURE, "seed already set"); 
+       n /= 8;
+       p = xmalloc(n);
+       rand_get(RAND_GLOBAL, p, n);
+       base64_init(&b);
+       base64_encode(&b, p, n, &d);
+       base64_encode(&b, 0, 0, &d);
+       seed = d.buf;
+       k.r = sa->gen(p, n);
+      } break;
+       
       /* --- Other flags --- */
 
-      case 'r':
+      case 'R':
        rtag = optarg;
        break;
       case 'l':
@@ -829,7 +1131,7 @@ static int cmd_add(int argc, char *argv[])
 
   if ((k.f & f_bogus) || optind + 1 > argc) {
     die(EXIT_FAILURE,
-       "Usage: add [options] type [attr...]");
+       "Usage: add [OPTIONS] TYPE [ATTR...]");
   }
   if (key_chkident(argv[optind]))
     die(EXIT_FAILURE, "bad key type `%s'", argv[optind]);
@@ -864,8 +1166,13 @@ static int cmd_add(int argc, char *argv[])
   /* --- Set various simple attributes --- */
 
   if (tag) {
-    int err = key_settag(&f, k.k, tag);
-    if (err)
+    int err;
+    key *kk;
+    if (k.f & f_retag) {
+      if ((kk = key_bytag(&f, tag)) != 0 && strcmp(kk->tag, tag) == 0)
+       key_settag(&f, kk, 0);
+    }
+    if ((err = key_settag(&f, k.k, tag)) != 0)
       die(EXIT_FAILURE, "error setting key tag: %s", key_strerror(err));
   }
 
@@ -876,6 +1183,10 @@ static int cmd_add(int argc, char *argv[])
   }
 
   setattr(&f, k.k, argv + optind + 1);
+  if (seed) {
+    key_putattr(&f, k.k, "genseed", seed);
+    key_putattr(&f, k.k, "seedalg", sa->p);
+  }
 
   key_fulltag(k.k, &k.tag);
 
@@ -912,11 +1223,9 @@ typedef struct listopts {
 
 /* --- Listing flags --- */
 
-enum {
-  f_newline = 2,                       /* Write newline before next entry */
-  f_attr = 4,                          /* Written at least one attribute */
-  f_utc = 8                            /* Emit UTC time, not local time */
-};
+#define f_newline 2u                   /* Write newline before next entry */
+#define f_attr 4u                      /* Written at least one attribute */
+#define f_utc 8u                       /* Emit UTC time, not local time */
 
 /* --- @showkeydata@ --- *
  *
@@ -1001,6 +1310,24 @@ static void showkeydata(key_data *k, int ind, listopts *o, dstr *d)
       putchar('\n');
       break;
 
+    /* --- Strings --- */
+
+    case KENC_STRING:
+      printf(" `%s'\n", k->u.p);
+      break;
+
+    /* --- Elliptic curve points --- */
+
+    case KENC_EC:
+      if (EC_ATINF(&k->u.e))
+       fputs(" inf\n", stdout);
+      else {
+       fputs(" 0x", stdout); mp_writefile(k->u.e.x, stdout, 16);
+       fputs(", 0x", stdout); mp_writefile(k->u.e.y, stdout, 16);
+       putchar('\n');
+      }
+      break;      
+
     /* --- Structured keys --- *
      *
      * Just iterate over the subkeys.
@@ -1171,7 +1498,7 @@ static int cmd_list(int argc, char *argv[])
   }
 
   if (o.f & f_bogus)
-    die(EXIT_FAILURE, "Usage: list [-uqv] [-f filter] [tag...]");
+    die(EXIT_FAILURE, "Usage: list [-uqv] [-f FILTER] [TAG...]");
 
   /* --- Open the key file --- */
 
@@ -1229,7 +1556,7 @@ static int cmd_expire(int argc, char *argv[])
   int rc = 0;
 
   if (argc < 2)
-    die(EXIT_FAILURE, "Usage: expire tag...");
+    die(EXIT_FAILURE, "Usage: expire TAG...");
   doopen(&f, KOPEN_WRITE);
   for (i = 1; i < argc; i++) {
     if ((k = key_bytag(&f, argv[i])) != 0)
@@ -1253,7 +1580,7 @@ static int cmd_delete(int argc, char *argv[])
   int rc = 0;
 
   if (argc < 2)
-    die(EXIT_FAILURE, "Usage: delete tag...");
+    die(EXIT_FAILURE, "Usage: delete TAG...");
   doopen(&f, KOPEN_WRITE);
   for (i = 1; i < argc; i++) {
     if ((k = key_bytag(&f, argv[i])) != 0)
@@ -1275,7 +1602,7 @@ static int cmd_setattr(int argc, char *argv[])
   key *k;
 
   if (argc < 3)
-    die(EXIT_FAILURE, "Usage: setattr tag attr...");
+    die(EXIT_FAILURE, "Usage: setattr TAG ATTR...");
   doopen(&f, KOPEN_WRITE);
   if ((k = key_bytag(&f, argv[1])) == 0)
     die(EXIT_FAILURE, "key `%s' not found", argv[1]);
@@ -1286,42 +1613,42 @@ static int cmd_setattr(int argc, char *argv[])
 
 /* --- @cmd_finger@ --- */
 
-static void fingerprint(key *k, const key_filter *kf)
+static void fingerprint(key *k, const gchash *ch, const key_filter *kf)
 {
-  rmd160_ctx r;
-  octet hash[RMD160_HASHSZ];
+  ghash *h;
   dstr d = DSTR_INIT;
-  int i;
+  const octet *p;
+  size_t i;
 
-  if (!key_encode(&k->k, &d, kf))
-    return;
-  rmd160_init(&r);
-  rmd160_hash(&r, d.buf, d.len);
-  rmd160_done(&r, hash);
-
-  DRESET(&d);
-  key_fulltag(k, &d);
-  for (i = 0; i < sizeof(hash); i++) {
-    if (i && i % 4 == 0)
-      putchar('-');
-    printf("%02x", hash[i]);
+  h = GH_INIT(ch);
+  if (key_fingerprint(k, h, kf)) {
+    p = GH_DONE(h, 0);
+    key_fulltag(k, &d);
+    for (i = 0; i < ch->hashsz; i++) {
+      if (i && i % 4 == 0)
+       putchar('-');
+      printf("%02x", p[i]);
+    }
+    printf(" %s\n", d.buf);
   }
-  printf(" %s\n", d.buf);
   dstr_destroy(&d);
+  GH_DESTROY(h);
 }
 
 static int cmd_finger(int argc, char *argv[])
 {
   key_file f;
   int rc = 0;
+  const gchash *ch = &rmd160;
   key_filter kf = { KF_NONSECRET, KF_NONSECRET };
 
   for (;;) {
     static struct option opt[] = {
       { "filter",      OPTF_ARGREQ,    0,      'f' },
+      { "algorithm",   OPTF_ARGREQ,    0,      'a' },
       { 0,             0,              0,      0 }
     };
-    int i = mdwopt(argc, argv, "f:", opt, 0, 0, 0);
+    int i = mdwopt(argc, argv, "+f:a:", opt, 0, 0, 0);
     if (i < 0)
       break;
     switch (i) {
@@ -1331,6 +1658,10 @@ static int cmd_finger(int argc, char *argv[])
        if (err || *p)
          die(EXIT_FAILURE, "bad filter string `%s'", optarg);
       } break;
+      case 'a':
+       if ((ch = ghash_byname(optarg)) == 0)
+         die(EXIT_FAILURE, "unknown hash algorithm `%s'", optarg);
+       break;
       default:
        rc = 1;
        break;
@@ -1339,7 +1670,7 @@ static int cmd_finger(int argc, char *argv[])
 
   argv += optind; argc -= optind;
   if (rc)
-    die(EXIT_FAILURE, "Usage: fingerprint [-f filter] [tag...]");
+    die(EXIT_FAILURE, "Usage: fingerprint [-f FILTER] [TAG...]");
 
   doopen(&f, KOPEN_READ);
 
@@ -1348,7 +1679,7 @@ static int cmd_finger(int argc, char *argv[])
     for (i = 0; i < argc; i++) {
       key *k = key_bytag(&f, argv[i]);
       if (k)
-       fingerprint(k, &kf);
+       fingerprint(k, ch, &kf);
       else {
        rc = 1;
        moan("key `%s' not found", argv[i]);
@@ -1358,7 +1689,7 @@ static int cmd_finger(int argc, char *argv[])
     key_iter i;
     key *k;
     for (key_mkiter(&i, &f); (k = key_next(&i)) != 0; )
-      fingerprint(k, &kf);
+      fingerprint(k, ch, &kf);
   }
   return (rc);
 }
@@ -1372,7 +1703,7 @@ static int cmd_comment(int argc, char *argv[])
   int err;
 
   if (argc < 2 || argc > 3)
-    die(EXIT_FAILURE, "Usage: comment tag [comment]");
+    die(EXIT_FAILURE, "Usage: comment TAG [COMMENT]");
   doopen(&f, KOPEN_WRITE);
   if ((k = key_bytag(&f, argv[1])) == 0)
     die(EXIT_FAILURE, "key `%s' not found", argv[1]);
@@ -1389,14 +1720,39 @@ static int cmd_tag(int argc, char *argv[])
   key_file f;
   key *k;
   int err;
+  unsigned flags = 0;
+  int rc = 0;
 
-  if (argc < 2 || argc > 3)
-    die(EXIT_FAILURE, "Usage: tag tag [new-tag]");
+  for (;;) {
+    static struct option opt[] = {
+      { "retag",       0,              0,      'r' },
+      { 0,             0,              0,      0 }
+    };
+    int i = mdwopt(argc, argv, "+r", opt, 0, 0, 0);
+    if (i < 0)
+      break;
+    switch (i) {
+      case 'r':
+       flags |= f_retag;
+       break;
+      default:
+       rc = 1;
+       break;
+    }
+  }
+
+  argv += optind; argc -= optind;
+  if (argc < 1 || argc > 2 || rc)
+    die(EXIT_FAILURE, "Usage: tag [-r] TAG [NEW-TAG]");
   doopen(&f, KOPEN_WRITE);
-  if ((k = key_bytag(&f, argv[1])) == 0)
-    die(EXIT_FAILURE, "key `%s' not found", argv[1]);
-  if ((err = key_settag(&f, k, argv[2])) != 0)
-    die(EXIT_FAILURE, "bad tag `%s': %s", argv[2], key_strerror(err));
+  if (flags & f_retag) {
+    if ((k = key_bytag(&f, argv[1])) != 0 && strcmp(k->tag, argv[1]) == 0)
+      key_settag(&f, k, 0);
+  }
+  if ((k = key_bytag(&f, argv[0])) == 0)
+    die(EXIT_FAILURE, "key `%s' not found", argv[0]);
+  if ((err = key_settag(&f, k, argv[1])) != 0)
+    die(EXIT_FAILURE, "bad tag `%s': %s", argv[1], key_strerror(err));
   doclose(&f);
   return (0);
 }
@@ -1411,7 +1767,7 @@ static int cmd_lock(int argc, char *argv[])
   dstr d = DSTR_INIT;
 
   if (argc != 2)
-    die(EXIT_FAILURE, "Usage: lock qtag");
+    die(EXIT_FAILURE, "Usage: lock QTAG");
   doopen(&f, KOPEN_WRITE);
   if (key_qtag(&f, argv[1], &d, &k, &kd))
     die(EXIT_FAILURE, "key `%s' not found", argv[1]);
@@ -1434,7 +1790,7 @@ static int cmd_unlock(int argc, char *argv[])
   dstr d = DSTR_INIT;
 
   if (argc != 2)
-    die(EXIT_FAILURE, "Usage: unlock qtag");
+    die(EXIT_FAILURE, "Usage: unlock QTAG");
   doopen(&f, KOPEN_WRITE);
   if (key_qtag(&f, argv[1], &d, &k, &kd))
     die(EXIT_FAILURE, "key `%s' not found", argv[1]);
@@ -1481,7 +1837,7 @@ static int cmd_extract(int argc, char *argv[])
 
   argv += optind; argc -= optind;
   if (rc || argc < 1)
-    die(EXIT_FAILURE, "Usage: extract [-f filter] file [tag...]");
+    die(EXIT_FAILURE, "Usage: extract [-f FILTER] FILE [TAG...]");
   if (strcmp(*argv, "-") == 0)
     fp = stdout;
   else if (!(fp = fopen(*argv, "w"))) {
@@ -1517,7 +1873,7 @@ static int cmd_tidy(int argc, char *argv[])
 {
   key_file f;
   if (argc != 1)
-    die(EXIT_FAILURE, "usage: tidy");
+    die(EXIT_FAILURE, "Usage: tidy");
   doopen(&f, KOPEN_WRITE);
   f.f |= KF_MODIFIED; /* Nasty hack */
   doclose(&f);
@@ -1532,7 +1888,7 @@ static int cmd_merge(int argc, char *argv[])
   FILE *fp;
 
   if (argc != 2)
-    die(EXIT_FAILURE, "Usage: merge file");
+    die(EXIT_FAILURE, "Usage: merge FILE");
   if (strcmp(argv[1], "-") == 0)
     fp = stdin;
   else if (!(fp = fopen(argv[1], "r"))) {
@@ -1546,42 +1902,114 @@ static int cmd_merge(int argc, char *argv[])
   return (0);
 }
 
+/* --- @cmd_show@ --- */
+
+#define LISTS(LI)                                                      \
+  LI("Lists", list,                                                    \
+     listtab[i].name, listtab[i].name)                                 \
+  LI("Hash functions", hash,                                           \
+     ghashtab[i], ghashtab[i]->name)                                   \
+  LI("Elliptic curves", ec,                                            \
+     ectab[i].name, ectab[i].name)                                     \
+  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,                                        \
+     seedtab[i].p, seedtab[i].p)
+
+MAKELISTTAB(listtab, LISTS)
+
+static int cmd_show(int argc, char *argv[])
+{
+  return (displaylists(listtab, argv + 1));
+}
+
 /*----- Main command table ------------------------------------------------*/
 
-static struct cmd {
-  const char *name;
-  int (*cmd)(int /*argc*/, char */*argv*/[]);
-  const char *help;
-} cmds[] = {
-  { "add", cmd_add,
-    "add [options] type [attr...]\n\
-       Options: [-lqLS] [-a alg] [-b|-B bits] [-p param] [-r tag]\n\
-                [-e expire] [-t tag] [-c comment]"
-  },
-  { "expire", cmd_expire, "expire tag..." },
-  { "delete", cmd_delete, "delete tag..." },
-  { "tag", cmd_tag, "tag tag [new-tag]" },
-  { "setattr", cmd_setattr, "setattr tag attr..." },
-  { "comment", cmd_comment, "comment tag [comment]" },
-  { "lock", cmd_lock, "lock qtag" },
-  { "unlock", cmd_unlock, "unlock qtag" },
-  { "list", cmd_list, "list [-uqv] [-f filter] [tag...]" },
-  { "fingerprint", cmd_finger, "fingerprint [-f filter] [tag...]" },
+static int cmd_help(int argc, char *argv[]);
+
+static cmd cmds[] = {
+  { "help", cmd_help, "help [COMMAND...]" },
+  { "show", cmd_show, "show [ITEM...]" },
+  { "list", cmd_list, "list [-uqv] [-f FILTER] [TAG...]", "\
+Options:\n\
+\n\
+-u, --utc              Display expiry times etc. in UTC, not local time.\n\
+-q, --quiet            Show less information.\n\
+-v, --verbose          Show more information.\n\
+" },
+  { "fingerprint", cmd_finger, "fingerprint [-f FILTER] [TAG...]", "\
+Options:\n\
+\n\
+-f, --filter=FILT      Only hash key components matching FILT.\n\
+-a, --algorithm=HASH   Use the named HASH algorithm.\n\
+                         ($ show hash for list.)\n\
+" },
+  { "extract", cmd_extract, "extract [-f FILTER] FILE [TAG...]", "\
+Options:\n\
+\n\
+-f, --filter=FILT      Only extract key components matching FILT.\n\
+" },
+  { "merge", cmd_merge, "merge FILE" },
+  { "expire", cmd_expire, "expire TAG..." },
+  { "delete", cmd_delete, "delete TAG..." },
+  { "setattr", cmd_setattr, "setattr TAG ATTR..." },
+  { "comment", cmd_comment, "comment TAG [COMMENT]" },
+  { "lock", cmd_lock, "lock QTAG" },
+  { "unlock", cmd_unlock, "unlock QTAG" },
+  { "tag", cmd_tag, "tag [-r] TAG [NEW-TAG]", "\
+Options:\n\
+\n\
+-r, --retag            Untag any key currently called new-tag.\n\
+" },
   { "tidy", cmd_tidy, "tidy" },
-  { "extract", cmd_extract, "extract [-f filter] file [tag...]" },
-  { "merge", cmd_merge, "merge file" },
+  { "add", cmd_add,
+    "add [-OPTIONS] TYPE [ATTR...]\n\
+       Options: [-lqrLS] [-a ALG] [-bB BITS] [-p PARAM] [-R TAG]\n\
+                [-A SEEDALG] [-s SEED] [-n BITS]\n\
+                [-e EXPIRE] [-t TAG] [-c COMMENT]", "\
+Options:\n\
+\n\
+-a, --algorithm=ALG    Generate keys suitable for ALG.\n\
+                         ($ show keygen for list.)\n\
+-b, --bits=N           Generate an N-bit key.\n\
+-B, --qbits=N          Use an N-bit subgroup or factors.\n\
+-p, --parameters=TAG   Get group parameters from TAG.\n\
+-C, --curve=NAME       Use elliptic curve or DH group NAME.\n\
+                         ($ show ec or $ show dh for list.)\n\
+-A, --seedalg=ALG      Use pseudorandom generator ALG to generate key.\n\
+                         ($ show seed for list.)\n\
+-s, --seed=BASE64      Use Base64-encoded string BASE64 as seed.\n\
+-n, --newseed=COUNT    Generate new COUNT-bit seed.\n\
+-e, --expire=TIME      Make the key expire after TIME.\n\
+-c, --comment=STRING   Attach the command STRING to the key.\n\
+-t, --tag=TAG          Tag the key with the name TAG.\n\
+-r, --retag            Untag any key currently with that tag.\n\
+-R, --rand-id=TAG      Use key named TAG for the random number generator.\n\
+-l, --lock             Lock the generated key with a passphrase.\n\
+-q, --quiet            Don't give progress indicators while working.\n\
+-L, --lim-lee          Generate Lim-Lee primes for Diffie-Hellman groups.\n\
+-S, --subgroup         Use a prime-order subgroup for Diffie-Hellman.\n\
+" },
   { 0, 0, 0 }
 };
 
-typedef struct cmd cmd;
+static int cmd_help(int argc, char *argv[])
+{
+  sc_help(cmds, stdout, argv + 1);
+  return (0);
+}
 
 /*----- Main code ---------------------------------------------------------*/
 
 /* --- Helpful GNUy functions --- */
 
-void usage(FILE *fp)
+static void usage(FILE *fp)
 {
-  pquis(fp, "Usage: $ [-k file] [-i tag] [-t type] command [args]\n");
+  pquis(fp, "Usage: $ [-k KEYRING] COMMAND [ARGS]\n");
 }
 
 void version(FILE *fp)
@@ -1589,28 +2017,20 @@ void version(FILE *fp)
   pquis(fp, "$, Catacomb version " VERSION "\n");
 }
 
-void help(FILE *fp)
+void help_global(FILE *fp)
 {
-  cmd *c;
-  version(fp);
-  fputc('\n', fp);
   usage(fp);
   fputs("\n\
-Performs various simple key management operations.  Command line options\n\
-recognized are:\n\
+Performs various simple key management operations.\n\
 \n\
--h, --help             Display this help text.\n\
+Global command line options:\n\
+\n\
+-h, --help [COMMAND...]        Display this help text (or help for COMMANDs).\n\
 -v, --version          Display version number.\n\
 -u, --usage            Display short usage summary.\n\
 \n\
--k, --keyring=FILE     Read and write keys in FILE.\n\
--i, --id=TAG           Use key TAG for random number generator.\n\
--t, --type=TYPE                Use key TYPE for random number generator.\n\
-\n\
-The following commands are understood:\n\n",
+-k, --keyring=FILE     Read and write keys in FILE.\n",
        fp);
-  for (c = cmds; c->name; c++)
-    fprintf(fp, "%s\n", c->help);
 }
 
 /* --- @main@ --- *
@@ -1627,9 +2047,7 @@ int main(int argc, char *argv[])
 {
   unsigned f = 0;
 
-  enum {
-    f_bogus = 1
-  };
+#define f_bogus 1u
 
   /* --- Initialization --- */
 
@@ -1650,22 +2068,21 @@ int main(int argc, char *argv[])
       /* --- Real live useful options --- */
 
       { "keyring",     OPTF_ARGREQ,    0,      'k' },
-      { "id",          OPTF_ARGREQ,    0,      'i' },
-      { "type",                OPTF_ARGREQ,    0,      't' },
 
       /* --- Magic terminator --- */
 
       { 0,             0,              0,      0 }
     };
-    int i = mdwopt(argc, argv, "+hvu k:i:t:", opt, 0, 0, 0);
+    int i = mdwopt(argc, argv, "+hvu k:", opt, 0, 0, 0);
 
     if (i < 0)
       break;
     switch (i) {
 
       /* --- GNU help options --- */
+
       case 'h':
-       help(stdout);
+       sc_help(cmds, stdout, argv + optind);
        exit(0);
       case 'v':
        version(stdout);
@@ -1705,26 +2122,7 @@ int main(int argc, char *argv[])
   argc -= optind;
   argv += optind;
   optind = 0;
-
-  {
-    cmd *c, *chosen = 0;
-    size_t sz = strlen(argv[0]);
-
-    for (c = cmds; c->name; c++) {
-      if (strncmp(argv[0], c->name, sz) == 0) {
-       if (c->name[sz] == 0) {
-         chosen = c;
-         break;
-       } else if (chosen)
-         die(EXIT_FAILURE, "ambiguous command name `%s'", argv[0]);
-       else
-         chosen = c;
-      }
-    }
-    if (!chosen)
-      die(EXIT_FAILURE, "unknown command name `%s'", argv[0]);
-    return (chosen->cmd(argc, argv));
-  }
+  return (findcmd(cmds, argv[0])->cmd(argc, argv));
 }
 
 /*----- That's all, folks -------------------------------------------------*/