dh, keyutil: Implement KCDSA key generation.

New function dh_kcdsagen generates KCDSA prime groups.  It's less quick
than I'd hoped, but it appears to do the right thing.  Make the keyutil
generate keys of this kind, and add documentation.

Currently no tests.

diff --git a/Makefile.m4 b/Makefile.m4
index 98218ba..0025dc6 100644 (file)
--- a/Makefile.m4
+++ b/Makefile.m4
@@ -208,7 +208,7 @@ define(`PGEN_SOURCES',
        bbs-rand.c bbs-gen.c bbs-jump.c bbs-fetch.c \
        rsa-priv.c rsa-pub.c rsa-gen.c rsa-recover.c rsa-fetch.c \
        oaep.c pkcs1.c pss.c \
        bbs-rand.c bbs-gen.c bbs-jump.c bbs-fetch.c \
        rsa-priv.c rsa-pub.c rsa-gen.c rsa-recover.c rsa-fetch.c \
        oaep.c pkcs1.c pss.c \

-       dh-gen.c dh-limlee.c dh-check.c dh-fetch.c dh-param.c \
+       dh-gen.c dh-limlee.c dh-kcdsa.c dh-check.c dh-fetch.c dh-param.c \

        dsarand.c dsa-sign.c dsa-verify.c dsa-gen.c dsa-check.c \
        gdsa.c gkcdsa.c \
        key-data.c key-flags.c key-text.c key-binary.c key-pass.c \
        dsarand.c dsa-sign.c dsa-verify.c dsa-gen.c dsa-check.c \
        gdsa.c gkcdsa.c \
        key-data.c key-flags.c key-text.c key-binary.c key-pass.c \

diff --git a/dh-kcdsa.c b/dh-kcdsa.c
new file mode 100644 (file)
index 0000000..d92148b
--- /dev/null
+++ b/dh-kcdsa.c
@@ -0,0 +1,126 @@
+/* -*-c-*-
+ *
+ * $Id$
+ *
+ * Generate KCDSA prime groups
+ *
+ * (c) 2006 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/macros.h>
+
+#include "dh.h"
+#include "mprand.h"
+#include "pgen.h"
+#include "prim.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @dh_kcdsagen@ --- *
+ *
+ * Arguments:  @dh_param *dp@ = pointer to output parameter block
+ *             @unsigned ql@ = size of small factor of %$(p - 1)/2$%
+ *             @unsigned pl@ = size of %$p$% in bits
+ *             @unsigned flags@ = other generation flags
+ *             @unsigned steps@ = number of steps to go
+ *             @grand *r@ = random number source
+ *             @pgen_proc *ev@ = event handler function
+ *             @void *ec@ = context for the event handler
+ *
+ * Returns:    @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it failed.
+ *
+ * Use:                Generates a KCDSA prime group.  That is, it chooses a prime
+ *             %$p$%, such that $%p = 2 q v + 1$%, for primes %$q$% and
+ *             %$v$%.  The actual group of interest is the subgroup of order
+ *             %$q$%.
+ */
+
+int dh_kcdsagen(dh_param *dp, unsigned ql, unsigned pl,
+               unsigned flags, unsigned steps, grand *r,
+               pgen_proc *ev, void *ec)
+{
+  pgen_filterctx pf;
+  pgen_simulprime sp[2];
+  pgen_simulctx ss;
+  prim_ctx pc;
+  rabin rb;
+  int rc = PGEN_ABORT;
+  int i;
+  mp *x;
+
+  /* --- First trick: find %$q$% --- */
+
+  pf.step = 2;
+  x = mprand(MP_NEW, ql, r, 1);
+  dp->q = pgen("q", MP_NEW, x, ev, ec,
+              steps, pgen_filter, &pf,
+              rabin_iters(ql), pgen_test, &rb);
+  if (!dp->q)
+    goto fail_0;
+
+  /* --- Second trick: find %$p$% and %$v$% --- */
+
+  x = mp_lsl(x, dp->q, 1);
+  sp[0].add = MP_ZERO; sp[0].mul = MP_ONE; sp[0].f = 0;
+  sp[1].add = MP_ONE; sp[1].mul = x; sp[1].f = PGENF_KEEP;
+  ss.step = MP_TWO; ss.v = sp; ss.n = N(sp);
+  x = mprand(MP_NEW, pl - ql, r, 1);
+  x = pgen("p", x, x, ev, ec,
+          steps, pgen_simulstep, &ss,
+          rabin_iters(pl - ql), pgen_simultest, &ss);
+  mp_drop(sp[0].mul);
+  if (!x)
+    goto fail_1;
+  dp->p = sp[1].u.x;
+
+  /* --- Third trick: find a generator --- */
+
+  mpmont_create(&pc.mm, dp->p);
+  mp_div(&x, 0, dp->p, dp->q);
+  i = 0;
+  pc.exp = x;
+  pc.n = 0;
+  dp->g = pgen("g", MP_NEW, MP_NEW, ev, ec,
+              0, prim_step, &i, 1, prim_test, &pc);
+  mpmont_destroy(&pc.mm);
+  if (!dp->g)
+    goto fail_2;
+
+  rc = PGEN_DONE;
+  goto done;
+
+  /* --- Tidying up and going home --- */
+
+fail_2:
+  mp_drop(dp->p);
+fail_1:
+  mp_drop(dp->q);
+fail_0:
+done:
+  mp_drop(x);
+  return (rc);
+}
+
+/*----- That's all, folks -------------------------------------------------*/

diff --git a/dh.h b/dh.h
index 0ddc342..689d8f1 100644 (file)
--- a/dh.h
+++ b/dh.h
@@ -166,6 +166,29 @@ extern int dh_limlee(dh_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/,
                     pgen_proc */*oev*/, void */*oec*/, pgen_proc */*iev*/,
                     void */*iec*/, size_t */*nf*/, mp ***/*f*/);
 
                     pgen_proc */*oev*/, void */*oec*/, pgen_proc */*iev*/,
                     void */*iec*/, size_t */*nf*/, mp ***/*f*/);
 

+/* --- @dh_kcdsagen@ --- *
+ *
+ * Arguments:  @dh_param *dp@ = pointer to output parameter block
+ *             @unsigned ql@ = size of small factor of %$(p - 1)/2$%
+ *             @unsigned pl@ = size of %$p$% in bits
+ *             @unsigned flags@ = other generation flags (none defined)
+ *             @unsigned steps@ = number of steps to go
+ *             @grand *r@ = random number source
+ *             @pgen_proc *ev@ = event handler function
+ *             @void *ec@ = context for the event handler
+ *
+ * Returns:    @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it failed.
+ *
+ * Use:                Generates a KCDSA prime group.  That is, it chooses a prime
+ *             %$p$%, such that $%p = 2 q v + 1$%, for primes %$q$% and
+ *             %$v$%.  The actual group of interest is the subgroup of order
+ *             %$q$%.
+ */
+
+extern int dh_kcdsagen(dh_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/,
+                      unsigned /*flags*/, unsigned /*steps*/, grand */*r*/,
+                      pgen_proc */*ev*/, void */*ec*/);
+

 /* --- @dh_checkparam@ --- *
  *
  * Arguments:  @keycheck *kc@ = keycheck state
 /* --- @dh_checkparam@ --- *
  *
  * Arguments:  @keycheck *kc@ = keycheck state

diff --git a/key.1 b/key.1
index 459a0b3..9efedf7 100644 (file)
--- a/key.1
+++ b/key.1
@@ -48,7 +48,7 @@ is one of:
 .RI [ item ...]
 .br
 .B add
 .RI [ item ...]
 .br
 .B add

-.RB [ \-lqrLS ]
+.RB [ \-lqrLKS ]

 .RB [ \-a
 .IR alg ]
 .RB [ \-b | \-B
 .RB [ \-a
 .IR alg ]
 .RB [ \-b | \-B


@@ -462,12 +462,17 @@ using a passphrase.
 Suppresses the progress indication which is usually generated while
 time-consuming key generation tasks are being performed.
 .TP
 Suppresses the progress indication which is usually generated while
 time-consuming key generation tasks are being performed.
 .TP

-.BI "\-L, --lim-lee"
+.BI "\-L, \-\-lim-lee"

 When generating Diffie-Hellman parameters, generate a Lim-Lee prime
 rather than a random (or safe) prime.  See the details on Diffie-Hellman
 key generation below.
 .TP
 When generating Diffie-Hellman parameters, generate a Lim-Lee prime
 rather than a random (or safe) prime.  See the details on Diffie-Hellman
 key generation below.
 .TP

-.BI "\-S, --subgroup"
+.BI "\-K, \-\-kcdsa"
+When generating Diffie-Hellman parameters, generate a KCDSA-style
+Lim-Lee prime rather than a random (or safe) prime.  See the details on
+Diffie-Hellman key generation below.
+.TP
+.BI "\-S, \-\-subgroup"

 When generating Diffie-Hellman parameters with a Lim-Lee prime, choose a
 generator of a prime-order subgroup rather than a subgroup of order
 .RI ( p "- 1)/2."
 When generating Diffie-Hellman parameters with a Lim-Lee prime, choose a
 generator of a prime-order subgroup rather than a subgroup of order
 .RI ( p "- 1)/2."


@@ -578,7 +583,7 @@ If no
 .I q
 size is selected using the
 .B \-B
 .I q
 size is selected using the
 .B \-B

-option and the Lim-Lee prime option is disabled, then 
+option and the Lim-Lee prime options are disabled, then 

 .I p
 is chosen to be a `safe' prime (i.e.,
 .IR p \ =\ 2 q \ +\ 1,
 .I p
 is chosen to be a `safe' prime (i.e.,
 .IR p \ =\ 2 q \ +\ 1,


@@ -602,7 +607,7 @@ is a multiple of
 .IP
 If the
 .B \-L
 .IP
 If the
 .B \-L

-option was given Lim-Lee primes are selected: the parameters are chosen
+option was given, Lim-Lee primes are selected: the parameters are chosen

 such that
 .IR p \ =\ 2\  q \*(us0\*(ue\ q \*(us1\*(ue\ q \*(us2\*(ue\ ...\ +\ 1,
 where the
 such that
 .IR p \ =\ 2\  q \*(us0\*(ue\ q \*(us1\*(ue\ q \*(us2\*(ue\ ...\ +\ 1,
 where the


@@ -612,8 +617,22 @@ are primes at least as large as the setting given by the
 option (or 256 bits, if no setting was given).
 .IP
 If the
 option (or 256 bits, if no setting was given).
 .IP
 If the

+.B \-K 
+option was given, KCDSA-style Lim-Lee primes are selected: the
+parameters are chosen such that
+.IR p \ =\ 2\  q\ v \ +\ 1,
+where
+.IR p, 
+.I q
+and
+.I v
+are primes.
+.IP
+If the

 .B \-S
 .B \-S

-option was given, the generator
+or
+.B \-K
+options were given, the generator

 .I g
 is chosen to generate the subgroup of order
 .IR q \*(us0\*(ue;
 .I g
 is chosen to generate the subgroup of order
 .IR q \*(us0\*(ue;

diff --git a/keyutil.c b/keyutil.c
index 269a85d..1adb840 100644 (file)
--- a/keyutil.c
+++ b/keyutil.c
@@ -197,6 +197,7 @@ typedef struct keyopts {
 #define f_limlee 8u                    /* Generate Lim-Lee primes */
 #define f_subgroup 16u                 /* Generate a subgroup */
 #define f_retag 32u                    /* Remove any existing tag */
 #define f_limlee 8u                    /* Generate Lim-Lee primes */
 #define f_subgroup 16u                 /* Generate a subgroup */
 #define f_retag 32u                    /* Remove any existing tag */

+#define f_kcdsa 64u                    /* Generate KCDSA primes */

 
 /* --- @dolock@ --- *
  *
 
 /* --- @dolock@ --- *
  *


@@ -609,6 +610,24 @@ static void alg_dhparam(keyopts *k)
        key_putattr(k->kf, k->k, "factors", d.buf);
        dstr_destroy(&d);
       }
        key_putattr(k->kf, k->k, "factors", d.buf);
        dstr_destroy(&d);
       }

+    } else if (k->f & f_kcdsa) {
+      if (!k->qbits)
+       k->qbits = 256;
+      rc = dh_kcdsagen(&dp, k->qbits, k->bits, 0,
+                      0, k->r, (k->f & f_quiet) ? 0 : pgen_ev, 0);
+      if (!rc) {
+       dstr d = DSTR_INIT;
+       mp *v = MP_NEW;
+
+       mp_writedstr(dp.q, &d, 10);
+       mp_div(&v, 0, dp.p, dp.q);
+       v = mp_lsr(v, v, 1);
+       dstr_puts(&d, ", ");
+       mp_writedstr(v, &d, 10);
+       mp_drop(v);
+       key_putattr(k->kf, k->k, "factors", d.buf);
+       dstr_destroy(&d);
+      }

     } else
       rc = dh_gen(&dp, k->qbits, k->bits, 0, k->r,
                  (k->f & f_quiet) ? 0 : pgen_ev, 0);
     } else
       rc = dh_gen(&dp, k->qbits, k->bits, 0, k->r,
                  (k->f & f_quiet) ? 0 : pgen_ev, 0);


@@ -951,9 +970,10 @@ static int cmd_add(int argc, char *argv[])
       { "quiet",       0,              0,      'q' },
       { "lim-lee",     0,              0,      'L' },
       { "subgroup",    0,              0,      'S' },
       { "quiet",       0,              0,      'q' },
       { "lim-lee",     0,              0,      'L' },
       { "subgroup",    0,              0,      'S' },

+      { "kcdsa",       0,              0,      'K' },

       { 0,             0,              0,      0 }
     };
       { 0,             0,              0,      0 }
     };

-    int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:R:C:A:s:n:lqrLS",
+    int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:R:C:A:s:n:lqrLKS",

                   opt, 0, 0, 0);
     if (i < 0)
       break;
                   opt, 0, 0, 0);
     if (i < 0)
       break;


@@ -1113,6 +1133,9 @@ static int cmd_add(int argc, char *argv[])
       case 'L':
        k.f |= f_limlee;
        break;
       case 'L':
        k.f |= f_limlee;
        break;

+      case 'K':
+       k.f |= f_kcdsa;
+       break;

       case 'S':
        k.f |= f_subgroup;
        break;
       case 'S':
        k.f |= f_subgroup;
        break;


@@ -2102,7 +2125,7 @@ Options:\n\
   { "tidy", cmd_tidy, "tidy" },
   { "add", cmd_add,
     "add [-OPTIONS] TYPE [ATTR...]\n\
   { "tidy", cmd_tidy, "tidy" },
   { "add", cmd_add,
     "add [-OPTIONS] TYPE [ATTR...]\n\

-       Options: [-lqrLS] [-a ALG] [-bB BITS] [-p PARAM] [-R TAG]\n\
+       Options: [-lqrLKS] [-a ALG] [-bB BITS] [-p PARAM] [-R TAG]\n\

                 [-A SEEDALG] [-s SEED] [-n BITS]\n\
                 [-e EXPIRE] [-t TAG] [-c COMMENT]", "\
 Options:\n\
                 [-A SEEDALG] [-s SEED] [-n BITS]\n\
                 [-e EXPIRE] [-t TAG] [-c COMMENT]", "\
 Options:\n\


@@ -2126,6 +2149,7 @@ Options:\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\
 -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\

+-K, --kcdsa            Generate KCDSA-style Lim-Lee primes for DH groups.\n\

 -S, --subgroup         Use a prime-order subgroup for Diffie-Hellman.\n\
 " },
   { 0, 0, 0 }
 -S, --subgroup         Use a prime-order subgroup for Diffie-Hellman.\n\
 " },
   { 0, 0, 0 }