From 4e67e30be6dbcc7d4f23be754b67bf7c6a0ade92 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Sat, 11 Feb 2006 20:50:29 +0000 Subject: [PATCH] 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. --- Makefile.m4 | 2 +- dh-kcdsa.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dh.h | 23 +++++++++++ key.1 | 31 ++++++++++++--- keyutil.c | 28 +++++++++++++- 5 files changed, 201 insertions(+), 9 deletions(-) create mode 100644 dh-kcdsa.c diff --git a/Makefile.m4 b/Makefile.m4 index 98218ba..0025dc6 100644 --- 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 \ - 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 \ diff --git a/dh-kcdsa.c b/dh-kcdsa.c new file mode 100644 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 + +#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 --- 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*/); +/* --- @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 diff --git a/key.1 b/key.1 index 459a0b3..9efedf7 100644 --- a/key.1 +++ b/key.1 @@ -48,7 +48,7 @@ is one of: .RI [ item ...] .br .B add -.RB [ \-lqrLS ] +.RB [ \-lqrLKS ] .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 -.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 -.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." @@ -578,7 +583,7 @@ If no .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, @@ -602,7 +607,7 @@ is a multiple of .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 @@ -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 +.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 -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; diff --git a/keyutil.c b/keyutil.c index 269a85d..1adb840 100644 --- 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_kcdsa 64u /* Generate KCDSA primes */ /* --- @dolock@ --- * * @@ -609,6 +610,24 @@ static void alg_dhparam(keyopts *k) 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); @@ -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' }, + { "kcdsa", 0, 0, 'K' }, { 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; @@ -1113,6 +1133,9 @@ static int cmd_add(int argc, char *argv[]) case 'L': k.f |= f_limlee; break; + case 'K': + k.f |= f_kcdsa; + 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\ - 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\ @@ -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\ +-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 } -- 2.11.0