projects / u / mdw / catacomb / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Support subgroups of binary fields.
[u/mdw/catacomb] / keyutil.c
diff --git a/keyutil.c b/keyutil.c
index 0b54df2..9ea8419 100644 (file)
--- a/keyutil.c
+++ b/keyutil.c
@@ -46,6 +46,7 @@
 #include <noise.h>
 #include <rand.h>
 
 #include <noise.h>
 #include <rand.h>
 
+#include "bintab.h"
 #include "bbs.h"
 #include "dh.h"
 #include "dsa.h"
 #include "bbs.h"
 #include "dh.h"
 #include "dsa.h"
@@ -55,6 +56,7 @@
 #include "ectab.h"
 #include "fibrand.h"
 #include "getdate.h"
 #include "ectab.h"
 #include "fibrand.h"
 #include "getdate.h"
+#include "gfreduce.h"
 #include "key.h"
 #include "mp.h"
 #include "mpmont.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;
 
     if (k->curve) {
       qd_parse qd;
+      group *g;
+      const char *e;
       
       if (strcmp(k->curve, "list") == 0) {
        unsigned i, w;
       
       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))
        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;
     }
       goto done;
     }
-
+    
     if (!k->bits)
       k->bits = 1024;
 
     if (!k->bits)
       k->bits = 1024;
 
@@ -698,6 +709,104 @@ static void alg_bbs(keyopts *k)
   bbs_privfree(&bp);
 }
 
   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 };
 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" },
   { "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" },
   { "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 }
   { "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)                                     \
      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)                                       \
      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,                                        \
   LI("Key-generation algorithms", keygen,                              \
      algtab[i].name, algtab[i].name)                                   \
   LI("Random seeding algorithms", seed,                                        \
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)