From 052b36d05a622a93733b735acce2de865b14627b Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 12 Feb 2000 18:21:23 +0000 Subject: [PATCH] Overhaul of key management (again). --- Makefile.m4 | 16 +- bbs-gen.c | 80 ++++++--- bbs.h | 14 +- dh-gen.c | 162 ++++++++++++++++++ dh-prime.c | 169 ------------------ dh.h | 64 ++++--- dsa-gen.c | 12 +- key-attr.c | 7 +- key-binary.c | 251 +++++++++++++++++++++++++++ key-data.c | 540 ++++------------------------------------------------------ key-data.h | 399 +++++++++++++++++++++++++++++++++++++++++++ key-error.c | 75 ++++++++ key-flags.c | 32 +++- key-io.c | 6 +- key-misc.c | 39 +---- key-text.c | 305 +++++++++++++++++++++++++++++++++ key.1 | 449 ++++++++++++++++++++++++++++++++++++++++++------ key.h | 345 ++----------------------------------- keyutil.c | 178 +++++++++++-------- pgen-safe.c | 111 ++++++++++-- pgen.h | 18 +- rspit.c | 12 +- strongprime.c | 108 ++++++++---- strongprime.h | 29 +++- 24 files changed, 2131 insertions(+), 1290 deletions(-) create mode 100644 dh-gen.c delete mode 100644 dh-prime.c create mode 100644 key-binary.c create mode 100644 key-data.h create mode 100644 key-error.c create mode 100644 key-text.c diff --git a/Makefile.m4 b/Makefile.m4 index 536007d..302e2f4 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-makefile-*- ## -## $Id: Makefile.m4,v 1.22 1999/12/22 16:04:06 mdw Exp $ +## $Id: Makefile.m4,v 1.23 2000/02/12 18:21:01 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ +## Revision 1.23 2000/02/12 18:21:01 mdw +## Overhaul of key management (again). +## ## Revision 1.22 1999/12/22 16:04:06 mdw ## Lots of new files. ## @@ -174,7 +177,7 @@ pkginclude_HEADERS = \ mprand.h \ primetab.h pfilt.h primorial.h rabin.h \ pgen.h prim.h strongprime.h \ - bbs.h rsa.h dsarand.h dsa.h \ + bbs.h rsa.h dh.h dsarand.h dsa.h \ allwithsuffix(`ciphers', `cipher_modes', `.h') \ allwithsuffix(`hashes', `hash_modes', `.h') \ addsuffix(`cipher_modes', `-def.h') \ @@ -186,8 +189,8 @@ libcatacomb_la_SOURCES = \ des-base.c des-base.h des_sp.h bf_ikey.h daftstory.h \ rc4.c \ rand.c noise.c \ - key-misc.c key-file.c key-data.c key-attr.c key-flags.c \ - key-io.c key-pass.c key-moan.c \ + key-data.c key-flags.c key-text.c key-binary.c key-pass.c \ + key-misc.c key-file.c key-attr.c key-io.c key-moan.c key-error.c \ passphrase.c pixie-client.c pixie-common.c lmem.c \ lcrand.c fibrand.c \ mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c \ @@ -202,6 +205,7 @@ libcatacomb_la_SOURCES = \ pgen.c pgen-stdev.c pgen-safe.c prim.c strongprime.c \ bbs-rand.c bbs-gen.c bbs-jump.c \ rsa-decrypt.c rsa-gen.c rsa-recover.c \ + dh-gen.c \ dsarand.c dsa-sign.c dsa-verify.c dsa-gen.c \ addsuffix(join(`ciphers', `-', `cipher_modes'), `.c') \ addsuffix(join(`hashes', `-', `hash_modes'), `.c') \ @@ -212,7 +216,7 @@ mpx.lo: mptypes.h ## --- Utility programs --- -bin_PROGRAMS = key pixie rspit +bin_PROGRAMS = key pixie rspit distsig bin_SCRIPTS = catacomb-config xpixie noinst_PROGRAMS = des-mktab genprimes mptypes LDADD = libcatacomb.la @@ -224,6 +228,8 @@ pixie_LDADD = rspit_SOURCES = rspit.c +distsig_SOURCES = distsig.c + des_mktab_SOURCES = des-mktab.c des_mktab_LDADD = diff --git a/bbs-gen.c b/bbs-gen.c index 8780274..43b6990 100644 --- a/bbs-gen.c +++ b/bbs-gen.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs-gen.c,v 1.2 1999/12/22 15:52:28 mdw Exp $ + * $Id: bbs-gen.c,v 1.3 2000/02/12 18:21:02 mdw Exp $ * * Generate Blum integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: bbs-gen.c,v $ + * Revision 1.3 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.2 1999/12/22 15:52:28 mdw * Reworking for new prime-search system. * @@ -48,13 +51,14 @@ #include "mp.h" #include "mprand.h" #include "pgen.h" +#include "strongprime.h" /*----- Data structures ---------------------------------------------------*/ typedef struct gcdctx { - mp *q; + mp *q, *jq; + pfilt p, jp; mp *r; - pfilt p; } gcdctx; /*----- Custom stepper ----------------------------------------------------*/ @@ -66,21 +70,40 @@ static int gcdstep(int rq, pgen_event *ev, void *p) mp *z = MP_NEW; switch (rq) { + + /* --- Set everything up --- */ + case PGEN_BEGIN: { - mp *p = ev->m = mp_split(ev->m); - p->v[0] |= 3; - g->q = mp_lsr(MP_NEW, p, 1); + mp *p = ev->m; + if ((p->v[0] & 3) != 3) + p = mp_add(p, p, g->jp.m); rc = pfilt_create(&g->p, p); + g->q = mp_lsr(MP_NEW, p, 1); + g->jq = MP_COPY(g->jp.m); + pfilt_muladd(&g->jp, &g->jp, 2, 0); + g->jq = mp_lsr(MP_NEW, p, 1); + mp_drop(p); } break; + + /* --- Grind through another iteration --- */ + case PGEN_TRY: - g->q = mp_add(g->q, g->q, MP_FOUR); - rc = pfilt_step(&g->p, 4); + mp_drop(ev->m); + rc = pfilt_jump(&g->p, &g->jp); + g->q = mp_add(g->q, g->q, g->jq); break; + + /* --- Finished --- */ + case PGEN_DONE: pfilt_destroy(&g->p); mp_drop(g->q); + mp_drop(g->jq); return (PGEN_DONE); } + + /* --- Step on until everything is OK --- */ + for (;;) { if (rc != PGEN_FAIL) { mp_gcd(&z, 0, 0, g->r, g->q); @@ -89,12 +112,11 @@ static int gcdstep(int rq, pgen_event *ev, void *p) } if (rc != PGEN_FAIL) break; - g->q = mp_add(g->q, g->q, MP_FOUR); - rc = pfilt_step(&g->p, 4); + rc = pfilt_jump(&g->p, &g->jp); + g->q = mp_add(g->q, g->q, g->jq); } mp_drop(z); - mp_drop(ev->m); ev->m = MP_COPY(g->p.m); return (rc); } @@ -104,8 +126,9 @@ static int gcdstep(int rq, pgen_event *ev, void *p) /* --- @bbs_gen@ --- * * * Arguments: @bbs_param *bp@ = pointer to parameter block - * @mp *p, *q@ = initial numbers to search from - * @size_t n@ = number of attempts to make + * @unsigned nbits@ = number of bits in the modulus + * @grand *r@ = pointer to random number source + * @unsigned n@ = number of attempts to make * @pgen_proc *event@ = event handler function * @void *ectx@ = argument for event handler * @@ -118,38 +141,51 @@ static int gcdstep(int rq, pgen_event *ev, void *p) * Shub pseudorandom bit generator. */ -int bbs_gen(bbs_param *bp, mp *p, mp *q, size_t n, +int bbs_gen(bbs_param *bp, unsigned nbits, grand *r, unsigned n, pgen_proc *event, void *ectx) { - rabin r; - pgen_safestepctx c; + rabin rb; + pgen_safejumpctx j; gcdctx g; + unsigned nb = nbits/2; + mp *x = MP_NEW; /* --- Generate @p@ --- */ - if ((bp->p = pgen("p", MP_NEW, p, event, ectx, n, pgen_safestep, &c, - rabin_iters(mp_bits(p)), pgen_test, &r)) == 0) + if ((x = strongprime_setup("p", x, &j.jq, nb, r, n, event, ectx)) == 0) + goto fail_x; + bp->p = pgen("p", MP_NEW, x, event, ectx, n, pgen_safejump, &j, + rabin_iters(nb), pgen_test, &rb); + pfilt_destroy(&j.jq); + if (!bp->p) goto fail_p; /* --- Generate @q@ --- */ + nb = nbits - nb; + if ((x = strongprime_setup("q", x, &g.jp, nb, r, n, event, ectx)) == 0) + goto fail_q; g.r = mp_lsr(MP_NEW, bp->p, 1); - if ((bp->q = pgen("q", MP_NEW, q, event, ectx, n, gcdstep, &g, - rabin_iters(mp_bits(q)), pgen_test, &r)) == 0) + bp->q = pgen("q", MP_NEW, x, event, ectx, n, gcdstep, &g, + rabin_iters(nb), pgen_test, &rb); + pfilt_destroy(&g.jp); + mp_drop(g.r); + if (!bp->q) goto fail_q; /* --- Compute @n@ --- */ bp->n = mp_mul(MP_NEW, bp->p, bp->q); - mp_drop(g.r); + mp_drop(x); return (PGEN_DONE); /* --- Tidy up if things went wrong --- */ fail_q: - mp_drop(g.r); mp_drop(bp->p); fail_p: + mp_drop(x); +fail_x: return (PGEN_ABORT); } diff --git a/bbs.h b/bbs.h index 485fb76..6e23d02 100644 --- a/bbs.h +++ b/bbs.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs.h,v 1.2 1999/12/22 15:52:08 mdw Exp $ + * $Id: bbs.h,v 1.3 2000/02/12 18:21:02 mdw Exp $ * * The Blum-Blum-Shub random bit generator * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: bbs.h,v $ + * Revision 1.3 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.2 1999/12/22 15:52:08 mdw * Rename `bbs_params' to `bbs_param' for consistency. * @@ -231,8 +234,9 @@ extern void bbs_rew(bbs */*b*/, bbs_param */*bp*/, unsigned long /*n*/); /* --- @bbs_gen@ --- * * * Arguments: @bbs_param *bp@ = pointer to parameter block - * @mp *p, *q@ = initial numbers to search from - * @size_t n@ = number of attempts to make + * @unsigned nbits@ = number of bits in the modulus + * @grand *r@ = pointer to random number source + * @unsigned n@ = number of attempts to make * @pgen_proc *event@ = event handler function * @void *ectx@ = argument for event handler * @@ -245,8 +249,8 @@ extern void bbs_rew(bbs */*b*/, bbs_param */*bp*/, unsigned long /*n*/); * Shub pseudorandom bit generator. */ -extern int bbs_gen(bbs_param */*bp*/, mp */*p*/, mp */*q*/, size_t /*n*/, - pgen_proc */*event*/, void */*ectx*/); +extern int bbs_gen(bbs_param */*bp*/, unsigned /*nbits*/, grand */*r*/, + unsigned /*n*/, pgen_proc */*event*/, void */*ectx*/); /*----- Generic random number generator interface -------------------------*/ diff --git a/dh-gen.c b/dh-gen.c new file mode 100644 index 0000000..e909989 --- /dev/null +++ b/dh-gen.c @@ -0,0 +1,162 @@ +/* -*-c-*- + * + * $Id: dh-gen.c,v 1.1 2000/02/12 18:21:02 mdw Exp $ + * + * Generate Diffie-Hellman parameters + * + * (c) 1999 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: dh-gen.c,v $ + * Revision 1.1 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "dh.h" +#include "grand.h" +#include "mp.h" +#include "mpmont.h" +#include "mprand.h" +#include "pfilt.h" +#include "pgen.h" +#include "prim.h" +#include "rabin.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @dh_gen@ --- * + * + * Arguments: @dh_param *dp@ = pointer to output parameter block + * @unsigned ql@ = length of %$q$% in bits, or zero + * @unsigned pl@ = length of %$p$% in bits + * @unsigned steps@ = number of steps to go + * @grand *r@ = random number source + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for the event handler + * + * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't. + * + * Use: Generates Diffie-Hellman parameters. + * + * The parameters are a prime %$q$%, relatively small, and a + * large prime %$p = kq + 1$% for some %$k$%, together with a + * generator %$g$% of the cyclic subgroup of order %$q$%. These + * are actually the same as the DSA parameter set, but the + * generation algorithm is different. Also, if @ql@ is zero, + * this algorithm forces %$k = 2$%, and chooses %$g = 4$%. Make + * sure you have something interesting to do if you choose this + * option. + */ + +int dh_gen(dh_param *dp, unsigned ql, unsigned pl, unsigned steps, grand *r, + pgen_proc *event, void *ectx) +{ + /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */ + + if (!ql) { + pgen_safetestctx c; + + mp *m = mprand(MP_NEW, pl, r, 3); + dp->p = pgen("p", MP_NEW, m, event, ectx, steps, pgen_safestep, &c.c, + rabin_iters(pl), pgen_safetest, &c); + mp_drop(m); + if (!dp->p) + return (PGEN_ABORT); + dp->q = mp_lsr(MP_NEW, dp->p, 1); + dp->g = MP_FOUR; + return (PGEN_DONE); + } + + /* --- Otherwise the job is much simpler --- * + * + * But doesn't look it... + */ + + else { + pgen_filterctx c; + pgen_jumpctx j; + rabin rb; + prim_ctx p; + int i; + mp *m = MP_NEW; + mp *x, *y; + + /* --- Generate @q@ first --- */ + + c.step = 2; + m = mprand(MP_NEW, ql, r, 1); + dp->q = pgen("q", MP_NEW, m, event, ectx, steps, pgen_filter, &c, + rabin_iters(ql), pgen_test, &rb); + if (!dp->q) + goto fail_q; + + /* --- Now pick a suitable @p@ --- */ + + m = mp_lsl(m, dp->q, 1); + x = mprand(MP_NEW, pl, r, 0); + y = MP_NEW; mp_div(0, &y, x, m); + x = mp_sub(x, x, y); + x = mp_add(x, x, MP_ONE); + mp_drop(y); + pfilt_create(&c.f, m); + j.j = &c.f; + dp->p = pgen("p", MP_NEW, x, event, ectx, steps, pgen_jump, &j, + rabin_iters(pl), pgen_test, &rb); + pfilt_destroy(&c.f); + mp_drop(x); + if (!dp->p) + goto fail_p; + + /* --- And finally a suitable @g@ --- */ + + mpmont_create(&p.mm, dp->p); + mp_div(&m, 0, dp->p, dp->q); + i = 0; + p.f = m; + p.n = 0; + dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i, + 1, prim_test, &p); + mpmont_destroy(&p.mm); + if (!dp->g) + goto fail_g; + mp_drop(m); + return (PGEN_DONE); + + /* --- Tidy up --- */ + + fail_g: + mp_drop(dp->q); + fail_q: + mp_drop(dp->p); + fail_p: + mp_drop(m); + return (PGEN_ABORT); + } +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/dh-prime.c b/dh-prime.c deleted file mode 100644 index ebe3a33..0000000 --- a/dh-prime.c +++ /dev/null @@ -1,169 +0,0 @@ -/* -*-c-*- - * - * $Id: dh-prime.c,v 1.2 1999/12/10 23:18:38 mdw Exp $ - * - * Generate (safe) Diffie-Hellman primes - * - * (c) 1999 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. - */ - -/*----- Revision history --------------------------------------------------* - * - * $Log: dh-prime.c,v $ - * Revision 1.2 1999/12/10 23:18:38 mdw - * Change interface for suggested destinations. - * - * Revision 1.1 1999/11/20 22:24:44 mdw - * Add Diffie-Hellman support. - * - */ - -/*----- Header files ------------------------------------------------------*/ - -#include -#include -#include - -#include "dh.h" -#include "fibrand.h" -#include "mp.h" -#include "mprand.h" -#include "pgen.h" -#include "rabin.h" - -/*----- Main code ---------------------------------------------------------*/ - -/* --- @dh_prime@ --- * - * - * Arguments: @mp *s@ = start point for search (must be odd) - * @size_t n@ = number of concerted attempts to make, or zero - * @void (*proc)(int ev, void *p)@ = event handler - * @void *p@ = argument for event handler - * - * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%. - * - * Use: Finds a safe prime by sequential search from a given starting - * point. If it fails, a null pointer is returned. - * - * The event handler is informed of the progress of the search. - * It may abort the search at any time by returning a nonzero - * value. - */ - -mp *dh_prime(mp *s, size_t n, - int (*proc)(int /*ev*/, void */*p*/), void *arg) -{ - pgen pq, pp; - int rc_q, rc_p; - grand *gr = fibrand_create(0); - mp *b = MP_NEW; - size_t sz = mp_bits(s); - - /* --- Initialize prime generators --- */ - - rc_q = pgen_create(&pq, s); - rc_p = pgen_muladd(&pp, &pq, 2, 1); - - /* --- Now step along until something crops up --- */ - - for (;;) { - rabin rq, rp; - int i; - - /* --- Don't do expensive testing unless necessary --- */ - - if (rc_q == PGEN_PRIME && rc_p == PGEN_PRIME) - break; - if (rc_q == PGEN_COMPOSITE || rc_p == PGEN_COMPOSITE) - goto next; - - /* --- Initialize Rabin-Miller contexts --- */ - - if (rc_q == PGEN_MAYBE) - rabin_create(&rq, pq.m); - if (rc_p == PGEN_MAYBE) - rabin_create(&rp, pp.m); - - /* --- Now run tests on each in turn --- * - * - * On the sorts of modulus sizes which work well in discrete log - * problems, five tests should be sufficient. - */ - - for (i = 0; i < 5; i++) { - b = mprand(b, sz, gr, 1); - if (rc_q == PGEN_MAYBE && - (rc_q = rabin_test(&rq, b)) == PGEN_COMPOSITE) - break; - if (rc_p == PGEN_MAYBE && - (rc_p = rabin_test(&rp, b)) == PGEN_COMPOSITE) - break; - if (proc && proc(DHEV_PASS, arg)) - break; - } - if (rc_q != PGEN_PRIME) - rabin_destroy(&rq); - if (rc_p != PGEN_PRIME) - rabin_destroy(&rp); - - /* --- If the tests passed, accept the numbers --- */ - - if (i >= 5) - break; - if (proc && proc(DHEV_FAIL, arg)) - goto fail; - if (n) { - n--; - if (!n) - goto fail; - } - - /* --- Step the contexts on --- */ - - next: - rc_q = pgen_step(&pq, 2); - rc_p = pgen_step(&pp, 4); - } - - /* --- Return a result --- */ - - { - mp *p = MP_COPY(pp.m); - pgen_destroy(&pq); - pgen_destroy(&pp); - mp_drop(b); - gr->ops->destroy(gr); - return (p); - } - - /* --- Failure --- */ - -fail: - pgen_destroy(&pq); - pgen_destroy(&pp); - mp_drop(b); - gr->ops->destroy(gr); - return (0); -} - -/*----- That's all, folks -------------------------------------------------*/ diff --git a/dh.h b/dh.h index bf8d79a..465f59f 100644 --- a/dh.h +++ b/dh.h @@ -1,8 +1,9 @@ /* -*-c-*- * - * $Id: dh.h,v 1.2 1999/12/10 23:29:48 mdw Exp $ + * $Id: dh.h,v 1.3 2000/02/12 18:21:02 mdw Exp $ + * + * Diffie-Hellman and related public-key systems * - * [Diffie-Hellman key negotiation * * (c) 1999 Straylight/Edgeware */ @@ -29,11 +30,8 @@ /*----- Revision history --------------------------------------------------* * * $Log: dh.h,v $ - * Revision 1.2 1999/12/10 23:29:48 mdw - * Change header file guard names. - * - * Revision 1.1 1999/11/20 22:24:44 mdw - * Add Diffie-Hellman support. + * Revision 1.3 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). * */ @@ -46,40 +44,50 @@ /*----- Header files ------------------------------------------------------*/ -#ifndef CATACOMB_MP_H -# include "mp.h" +#ifndef CATACOMB_GRAND_H +# include "grand.h" #endif -/*----- Event codes -------------------------------------------------------*/ +#ifndef CATACOMB_PGEN_H +# include "pgen.h" +#endif -enum { - DHEV_OK, +/*----- Data structures ---------------------------------------------------*/ - DHEV_FAIL, - DHEV_PASS -}; +typedef struct dh_param { + mp *p, *q; + mp *g; +} dh_param; /*----- Functions provided ------------------------------------------------*/ -/* --- @dh_prime@ --- * +/* --- @dh_gen@ --- * * - * Arguments: @mp *s@ = start point for search (must be odd) - * @size_t n@ = number of concerted attempts to make, or zero - * @void (*proc)(int ev, void *p)@ = event handler - * @void *p@ = argument for event handler + * Arguments: @dh_param *dp@ = pointer to output parameter block + * @unsigned ql@ = length of %$q$% in bits, or zero + * @unsigned pl@ = length of %$p$% in bits + * @unsigned steps@ = number of steps to go + * @grand *r@ = random number source + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for the event handler * - * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%. + * Returns: @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't. * - * Use: Finds a safe prime by sequential search from a given starting - * point. If it fails, a null pointer is returned. + * Use: Generates Diffie-Hellman parameters. * - * The event handler is informed of the progress of the search. - * It may abort the search at any time by returning a nonzero - * value. + * The parameters are a prime %$q$%, relatively small, and a + * large prime %$p = kq + 1$% for some %$k$%, together with a + * generator %$g$% of the cyclic subgroup of order %$q$%. These + * are actually the same as the DSA parameter set, but the + * generation algorithm is different. Also, if @ql@ is zero, + * this algorithm forces %$k = 2$%, and chooses %$g = 4$%. Make + * sure you have something interesting to do if you choose this + * option. */ -extern mp *dh_prime(mp */*s*/, size_t /*n*/, - int (*proc)(int /*ev*/, void */*p*/), void */*p*/); +extern int dh_gen(dh_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/, + unsigned /*steps*/, grand */*r*/, pgen_proc */*event*/, + void */*ectx*/); /*----- That's all, folks -------------------------------------------------*/ diff --git a/dsa-gen.c b/dsa-gen.c index d26bfe4..40454d8 100644 --- a/dsa-gen.c +++ b/dsa-gen.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: dsa-gen.c,v 1.4 1999/12/22 15:52:44 mdw Exp $ + * $Id: dsa-gen.c,v 1.5 2000/02/12 18:21:02 mdw Exp $ * * Generate DSA shared parameters * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: dsa-gen.c,v $ + * Revision 1.5 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.4 1999/12/22 15:52:44 mdw * Reworking for new prime-search system. * @@ -141,7 +144,12 @@ int dsa_step(int rq, pgen_event *ev, void *p) * Returns: @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise. * * Use: Generates the DSA shared parameters from a given seed value. - * This can take quite a long time. + * + * The parameters are a prime %$q$%, relatively small, and a + * large prime %$p = kq + 1$% for some %$k$%, together with a + * generator %$g$% of the cyclic subgroup of order %$q$%. These + * are actually the same as the Diffie-Hellman parameter set, + * but the generation algorithm is different. * * The algorithm used is a compatible extension of the method * described in the DSA standard, FIPS 186. The standard diff --git a/key-attr.c b/key-attr.c index 3737a5d..b779323 100644 --- a/key-attr.c +++ b/key-attr.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-attr.c,v 1.1 1999/12/22 15:47:48 mdw Exp $ + * $Id: key-attr.c,v 1.2 2000/02/12 18:21:02 mdw Exp $ * * Key attribute manipulation * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key-attr.c,v $ + * Revision 1.2 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -43,7 +46,7 @@ #include #include -#include +#include #include #include "key.h" diff --git a/key-binary.c b/key-binary.c new file mode 100644 index 0000000..4459ff1 --- /dev/null +++ b/key-binary.c @@ -0,0 +1,251 @@ +/* -*-c-*- + * + * $Id: key-binary.c,v 1.1 2000/02/12 18:21:02 mdw Exp $ + * + * Key binary encoding + * + * (c) 1999 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: key-binary.c,v $ + * Revision 1.1 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include + +#include +#include +#include +#include + +#include "key-data.h" +#include "mp.h" +#include "mptext.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @key_decode@ --- * + * + * Arguments: @const void *p@ = pointer to buffer to read + * @size_t sz@ = size of the buffer + * @key_data *k@ = pointer to key data block to write to + * + * Returns: Zero if everything worked, nonzero otherwise. + * + * Use: Decodes a binary representation of a key. + */ + +int key_decode(const void *p, size_t sz, key_data *k) +{ + const octet *q = p; + size_t psz; + unsigned e; + + /* --- Parse the header information --- * + * + * Make sure the size matches external reality. Security holes have been + * known to creep in without this sort of check. (No, this isn't an after- + * the-fact patch-up.) + */ + + e = LOAD16(q); + psz = LOAD16(q + 2); + if (psz + 4 > sz) + return (-1); + k->e = e; + + /* --- Now decide what to do --- */ + + switch (e & KF_ENCMASK) { + + /* --- Plain binary data --- */ + + case KENC_BINARY: + case KENC_ENCRYPT: + k->u.k.k = sub_alloc(psz); + memcpy(k->u.k.k, q + 4, psz); + k->u.k.sz = psz; + break; + + /* --- Multiprecision integer data --- */ + + case KENC_MP: + k->u.m = mp_loadb(MP_NEW, q + 4, psz); + if (k->e & KF_BURN) + mp_burn(k->u.m); + break; + + /* --- Structured key data --- */ + + case KENC_STRUCT: { + dstr d = DSTR_INIT; + key_struct *ks; + unsigned f; + + if ((k->e & ~KF_ENCMASK) || (psz & 3)) + return (-1); + q += 4; + sym_create(&k->u.s); + + while (psz) { + + /* --- Read the tag string --- */ + + DRESET(&d); + sz = LOAD8(q); + if (sz >= psz) + goto fail; + DPUTM(&d, q + 1, sz); + DPUTZ(&d); + sz = (sz + 4) & ~3; + q += sz; psz -= sz; + + /* --- Read the encoding and size --- */ + + e = LOAD16(q); + sz = (LOAD16(q + 2) + 7) & ~3; + if (sz > psz) + goto fail; + + /* --- Create a table node and fill it in --- */ + + ks = sym_find(&k->u.s, d.buf, d.len + 1, sizeof(*ks), &f); + if (f) + goto fail; + if (key_decode(q, sz, &ks->k)) { + sym_remove(&k->u.s, ks); + goto fail; + } + psz -= sz; + q += sz; + } + dstr_destroy(&d); + break; + + /* --- Tidy up after a failure --- */ + + fail: + dstr_destroy(&d); + key_destroy(k); + return (-1); + } break; + + /* --- Everything else --- */ + + default: + return (-1); + } + + /* --- OK, that was good --- */ + + return (0); +} + +/* --- @key_encode@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @dstr *d@ = pointer to destination string + * @const key_filter *kf@ = pointer to key selection block + * + * Returns: Nonzero if an item was actually written. + * + * Use: Encodes a key block as binary data. + */ + +int key_encode(key_data *k, dstr *d, const key_filter *kf) +{ + int rc = 0; + if (!KEY_MATCH(k, kf)) + return (0); + switch (k->e & KF_ENCMASK) { + case KENC_BINARY: + case KENC_ENCRYPT: { + char *p; + + DENSURE(d, (k->u.k.sz + 7) & ~3); + p = d->buf + d->len; + STORE16(p, k->e); + STORE16(p + 2, k->u.k.sz); + d->len += 4; + DPUTM(d, k->u.k.k, k->u.k.sz); + rc = 1; + } break; + + case KENC_MP: { + char *p; + size_t sz = mp_octets(k->u.m); + + DENSURE(d, (sz + 7) & ~3); + p = d->buf + d->len; + STORE16(p, k->e); + STORE16(p + 2, sz); + mp_storeb(k->u.m, p + 4, sz); + d->len += sz + 4; + rc = 1; + } break; + + case KENC_STRUCT: { + size_t n; + char *p; + key_struct *ks; + sym_iter i; + + n = d->len; + DENSURE(d, 4); + p = d->buf + n; + STORE16(p, k->e & KF_ENCMASK); + d->len += 4; + for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { + size_t o = d->len; + DENSURE(d, 1); + *(octet *)(d->buf + d->len++) = strlen(SYM_NAME(ks)); + DPUTS(d, SYM_NAME(ks)); + while (d->len & 3) + DPUTC(d, 0); + if (key_encode(&ks->k, d, kf)) + rc = 1; + else + d->len = o; + } + if (!rc) + d->len = n; + else { + p = d->buf + n + 2; + n = d->len - n - 4; + STORE16(p, n); + } + } break; + } + while (d->len & 3) + DPUTC(d, 0); + return (rc); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/key-data.c b/key-data.c index 01def8c..5da8b38 100644 --- a/key-data.c +++ b/key-data.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-data.c,v 1.1 1999/12/22 15:47:48 mdw Exp $ + * $Id: key-data.c,v 1.2 2000/02/12 18:21:02 mdw Exp $ * * Encoding and decoding of key data * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key-data.c,v $ + * Revision 1.2 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -41,51 +44,16 @@ #include #include -#include #include #include #include #include #include -#include "key.h" +#include "key-data.h" #include "mp.h" #include "mptext.h" -/*----- Disposal ----------------------------------------------------------*/ - -/* --- @key_destroy@ --- * - * - * Arguments: @key_data *k@ = pointer to key data to destroy - * - * Returns: --- - * - * Use: Destroys a lump of key data. - */ - -void key_destroy(key_data *k) -{ - switch (k->e & KF_ENCMASK) { - case KENC_BINARY: - case KENC_ENCRYPT: - if (k->e & KF_BURN) - memset(k->u.k.k, 0, k->u.k.sz); - sub_free(k->u.k.k, k->u.k.sz); - break; - case KENC_MP: - mp_drop(k->u.m); - break; - case KENC_STRUCT: { - sym_iter i; - key_struct *ks; - - for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) - key_destroy(&ks->k); - sym_destroy(&k->u.s); - } break; - } -} - /*----- Setting new values ------------------------------------------------*/ /* --- @key_binary@ --- * @@ -194,35 +162,44 @@ key_data *key_structcreate(key_data *k, const char *tag) ks = sym_find(&k->u.s, tag, -1, sizeof(*ks), &f); if (f) key_destroy(&ks->k); - ks->k.e = 0; + ks->k.e = KF_TEMP; return (&ks->k); } -/* --- @key_match@ --- * +/*----- Miscellaneous operations ------------------------------------------*/ + +/* --- @key_destroy@ --- * * - * Arguments: @key_data *k@ = pointer to key data block - * @const key_filter *kf@ = pointer to filter block + * Arguments: @key_data *k@ = pointer to key data to destroy * - * Returns: Nonzero if the key matches the filter. + * Returns: --- * - * Use: Checks whether a key matches a filter. + * Use: Destroys a lump of key data. */ -int key_match(key_data *k, const key_filter *kf) +void key_destroy(key_data *k) { - sym_iter i; - key_struct *ks; - - if (!kf) - return (1); - if ((k->e & KF_ENCMASK) != KENC_STRUCT) - return ((k->e & kf->m) == kf->f); + switch (k->e & KF_ENCMASK) { + case KENC_BINARY: + case KENC_ENCRYPT: + if (k->e & KF_BURN) + memset(k->u.k.k, 0, k->u.k.sz); + sub_free(k->u.k.k, k->u.k.sz); + break; + case KENC_MP: + mp_drop(k->u.m); + break; + case KENC_STRUCT: { + sym_iter i; + key_struct *ks; - for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { - if (key_match(&ks->k, kf)) - return (1); + for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { + if (!(ks->k.e & KF_TEMP)) + key_destroy(&ks->k); + } + sym_destroy(&k->u.s); + } break; } - return (0); } /* --- @key_do@ --- * @@ -266,8 +243,6 @@ int key_do(key_data *k, const key_filter *kf, dstr *d, } } -/*----- Copying -----------------------------------------------------------*/ - /* --- @key_copy@ --- * * * Arguments: @key_data *kd@ = pointer to destination data block @@ -329,455 +304,4 @@ int key_copy(key_data *kd, key_data *k, const key_filter *kf) return (1); } -/*----- Textual encoding --------------------------------------------------*/ - -/* --- @key_read@ --- * - * - * Arguments: @const char *p@ = pointer to textual key representation - * @key_data *k@ = pointer to output block for key data - * @char **pp@ = where to store the end pointer - * - * Returns: Zero if all went well, nonzero if there was a problem. - * - * Use: Parses a textual key description. - */ - -int key_read(const char *p, key_data *k, char **pp) -{ - unsigned e; - - /* --- Read the encoding type --- * - * - * The key format is `[FLAGS:]DATA'. If there is no encoding type - * named, assume that it's `binary' for backwards compatibility. - */ - - if (strchr(p, ':') == 0) - e = 0; - else { - char *q; - if (key_readflags(p, &q, &e, 0)) - return (-1); - p = q + 1; - } - - /* --- Now scan the data based on the encoding type --- */ - - k->e = e; - switch (e & KF_ENCMASK) { - - /* --- Binary encoding --- * - * - * Simply read out the Base64-encoded data. Since `,' and `]' are our - * delimeter characters, and they can't appear in Base64-encoded data, I - * can just do a simple search to find the end of the encoded data. - */ - - case KENC_BINARY: - case KENC_ENCRYPT: { - dstr d = DSTR_INIT; - base64_ctx b; - size_t sz = strcspn(p, ",]"); - - base64_init(&b); - base64_decode(&b, p, sz, &d); - base64_decode(&b, 0, 0, &d); - k->u.k.k = sub_alloc(d.len); - k->u.k.sz = d.len; - memcpy(k->u.k.k, d.buf, d.len); - dstr_destroy(&d); - p += sz; - } break; - - /* --- Multiprecision integer encoding --- * - * - * Multiprecision integers have a convenient reading function. - */ - - case KENC_MP: { - char *q; - mp *m = mp_readstring(MP_NEW, p, &q, 0); - if (!m) - return (-1); - if (k->e & KF_BURN) - mp_burn(m); - k->u.m = m; - p = q; - } break; - - /* --- Structured information encoding --- * - * - * The format for structured key data is `[NAME=KEY,...]', where the - * brackets are part of the syntax. Structured keys have no flags apart - * from the encoding. - * - * The binary encoding only allows names up to 255 bytes long. Check for - * this here. - */ - - case KENC_STRUCT: { - dstr d = DSTR_INIT; - char *q; - - /* --- Read the opening bracket --- */ - - k->e &= KF_ENCMASK; - if (*p != '[') - return (-1); - p++; - sym_create(&k->u.s); - - /* --- Read named key subparts --- */ - - for (;;) { - size_t sz; - key_struct *ks; - - /* --- Stop if there's a close-bracket --- * - * - * This allows `[]' to be an empty structured key, which is good. It - * also makes `[foo=enc:bar,]' legal, and that's less good but I can - * live with it. - */ - - if (*p == ']') - break; - - /* --- Read the name out and check the length --- */ - - if ((q = strchr(p, '=')) == 0) - goto fail; - sz = q - p; - if (sz >= 256) - goto fail; - DRESET(&d); - DPUTM(&d, p, sz); - DPUTZ(&d); - - /* --- Add an appropriate block to the key table --- * - * - * Simply destroy old data if there's already a match. - */ - - { - unsigned f; - ks = sym_find(&k->u.s, d.buf, d.len + 1, sizeof(*ks), &f); - if (f) - key_destroy(&ks->k); - } - - /* --- Read the key data for the subkey --- */ - - if (key_read(q + 1, &ks->k, &q)) { - sym_remove(&k->u.s, ks); - goto fail; - } - p = q; - - /* --- Read the comma or close-bracket --- */ - - if (*p == ']') - break; - else if (*p == ',') - p++; - else - goto fail; - } - - /* --- Step past the close bracket --- */ - - p++; - dstr_destroy(&d); - break; - - /* --- Tidy up after a failure --- */ - - fail: - dstr_destroy(&d); - key_destroy(k); - return (-1); - } break; - - /* --- Anything else is unknown --- */ - - default: - return (-1); - } - - /* --- Return the end pointer --- */ - - if (pp) - *pp = (char *)p; - return (0); -} - -/* --- @key_write@ --- * - * - * Arguments: @key_data *k@ = pointer to key data - * @dstr *d@ = destination string to write on - * @const key_filter *kf@ = pointer to key selection block - * - * Returns: Nonzero if an item was actually written. - * - * Use: Writes a key in a textual encoding. - */ - -int key_write(key_data *k, dstr *d, const key_filter *kf) -{ - int rc = 0; - if (!KEY_MATCH(k, kf)) - return (0); - switch (k->e & KF_ENCMASK) { - case KENC_BINARY: - case KENC_ENCRYPT: { - base64_ctx b; - - if ((k->e & KF_ENCMASK) == KENC_BINARY) - key_writeflags(k->e, d); - else - DPUTS(d, "encrypt,secret"); - DPUTC(d, ':'); - base64_init(&b); - b.indent = ""; - b.maxline = 0; - base64_encode(&b, k->u.k.k, k->u.k.sz, d); - base64_encode(&b, 0, 0, d); - rc = 1; - } break; - case KENC_MP: - key_writeflags(k->e, d); - DPUTC(d, ':'); - mp_writedstr(k->u.m, d, 10); - rc = 1; - break; - case KENC_STRUCT: { - sym_iter i; - key_struct *ks; - char del = 0; - size_t n = d->len; - - DPUTS(d, "struct:["); - for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { - size_t o = d->len; - if (del) - DPUTC(d, del); - DPUTS(d, SYM_NAME(ks)); - DPUTC(d, '='); - if (!key_write(&ks->k, d, kf)) - d->len = o; - else { - del = ','; - rc = 1; - } - } - if (!rc) - d->len = n; - else - DPUTC(d, ']'); - } break; - } - DPUTZ(d); - - return (rc); -} - -/*----- Binary encoding ---------------------------------------------------*/ - -/* --- @key_decode@ --- * - * - * Arguments: @const void *p@ = pointer to buffer to read - * @size_t sz@ = size of the buffer - * @key_data *k@ = pointer to key data block to write to - * - * Returns: Zero if everything worked, nonzero otherwise. - * - * Use: Decodes a binary representation of a key. - */ - -int key_decode(const void *p, size_t sz, key_data *k) -{ - const octet *q = p; - size_t psz; - unsigned e; - - /* --- Parse the header information --- * - * - * Make sure the size matches external reality. Security holes have been - * known to creep in without this sort of check. (No, this isn't an after- - * the-fact patch-up.) - */ - - e = LOAD16(q); - psz = LOAD16(q + 2); - if (psz + 4 > sz) - return (-1); - k->e = e; - - /* --- Now decide what to do --- */ - - switch (e & KF_ENCMASK) { - - /* --- Plain binary data --- */ - - case KENC_BINARY: - case KENC_ENCRYPT: - k->u.k.k = sub_alloc(psz); - memcpy(k->u.k.k, q + 4, psz); - k->u.k.sz = psz; - break; - - /* --- Multiprecision integer data --- */ - - case KENC_MP: - k->u.m = mp_loadb(MP_NEW, q + 4, psz); - if (k->e & KF_BURN) - mp_burn(k->u.m); - break; - - /* --- Structured key data --- */ - - case KENC_STRUCT: { - dstr d = DSTR_INIT; - key_struct *ks; - unsigned f; - - if ((k->e & ~KF_ENCMASK) || (psz & 3)) - return (-1); - q += 4; - sym_create(&k->u.s); - - while (psz) { - - /* --- Read the tag string --- */ - - DRESET(&d); - sz = LOAD8(q); - if (sz >= psz) - goto fail; - DPUTM(&d, q + 1, sz); - DPUTZ(&d); - sz = (sz + 4) & ~3; - q += sz; psz -= sz; - - /* --- Read the encoding and size --- */ - - e = LOAD16(q); - sz = (LOAD16(q + 2) + 7) & ~3; - if (sz > psz) - goto fail; - - /* --- Create a table node and fill it in --- */ - - ks = sym_find(&k->u.s, d.buf, d.len + 1, sizeof(*ks), &f); - if (f) - goto fail; - if (key_decode(q, sz, &ks->k)) { - sym_remove(&k->u.s, ks); - goto fail; - } - psz -= sz; - q += sz; - } - dstr_destroy(&d); - break; - - /* --- Tidy up after a failure --- */ - - fail: - dstr_destroy(&d); - key_destroy(k); - return (-1); - } break; - - /* --- Everything else --- */ - - default: - return (-1); - } - - /* --- OK, that was good --- */ - - return (0); -} - -/* --- @key_encode@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @dstr *d@ = pointer to destination string - * @const key_filter *kf@ = pointer to key selection block - * - * Returns: Nonzero if an item was actually written. - * - * Use: Encodes a key block as binary data. - */ - -int key_encode(key_data *k, dstr *d, const key_filter *kf) -{ - int rc = 0; - if (!KEY_MATCH(k, kf)) - return (0); - switch (k->e & KF_ENCMASK) { - case KENC_BINARY: - case KENC_ENCRYPT: { - char *p; - - DENSURE(d, (k->u.k.sz + 7) & ~3); - p = d->buf + d->len; - STORE16(p, k->e); - STORE16(p + 2, k->u.k.sz); - d->len += 4; - DPUTM(d, k->u.k.k, k->u.k.sz); - rc = 1; - } break; - - case KENC_MP: { - char *p; - size_t sz = mp_octets(k->u.m); - - DENSURE(d, (sz + 7) & ~3); - p = d->buf + d->len; - STORE16(p, k->e); - STORE16(p + 2, sz); - mp_storeb(k->u.m, p + 4, sz); - d->len += sz + 4; - rc = 1; - } break; - - case KENC_STRUCT: { - size_t n; - char *p; - key_struct *ks; - sym_iter i; - - n = d->len; - DENSURE(d, 4); - p = d->buf + n; - STORE16(p, k->e & KF_ENCMASK); - d->len += 4; - for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { - size_t o = d->len; - DENSURE(d, 1); - *(octet *)(d->buf + d->len++) = strlen(SYM_NAME(ks)); - DPUTS(d, SYM_NAME(ks)); - while (d->len & 3) - DPUTC(d, 0); - if (key_encode(&ks->k, d, kf)) - rc = 1; - else - d->len = o; - } - if (!rc) - d->len = n; - else { - p = d->buf + n + 2; - n = d->len - n - 4; - STORE16(p, n); - } - } break; - } - while (d->len & 3) - DPUTC(d, 0); - return (rc); -} - /*----- That's all, folks -------------------------------------------------*/ diff --git a/key-data.h b/key-data.h new file mode 100644 index 0000000..6cf2439 --- /dev/null +++ b/key-data.h @@ -0,0 +1,399 @@ +/* -*-c-*- + * + * $Id: key-data.h,v 1.1 2000/02/12 18:21:23 mdw Exp $ + * + * Manipulating key data + * + * (c) 1999 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: key-data.h,v $ + * Revision 1.1 2000/02/12 18:21:23 mdw + * Overhaul of key management (again). + * + */ + +#ifndef CATACOMB_KEY_DATA_H +#define CATACOMB_KEY_DATA_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include +#include +#include + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +/* --- Key binary data --- */ + +typedef struct key_bin { + octet *k; /* Pointer to key data */ + size_t sz; /* Size of the key data (in bytes) */ +} key_bin; + +/* --- Key data structure --- */ + +typedef struct key_data { + unsigned e; /* Encoding type for key data */ + union { + key_bin k; /* Binary key data */ + mp *m; /* Multiprecision integer */ + sym_table s; /* Structured key data */ + } u; +} key_data; + +typedef struct key_struct { + sym_base _b; + key_data k; +} key_struct; + +/* --- Key binary encoding --- * + * + * The binary encoding consists of a header containing a 16-bit encoding type + * and a 16-bit length, followed immediately by the key data, followed by + * between zero and three zero bytes to make the total length a multiple of + * four. The format of the following data depends on the encoding type: + * + * @KENC_BINARY@ Binary data. + * + * @KENC_MP@ Octet array interpreted in big-endian byte order. + * + * @KENC_STRUCT@ An array of pairs, each containing a string (8-bit + * length followed by data and zero-padding to 4-byte + * boundary) and key binary encodings. + * + * @KENC_ENCRYPT@ Binary data, format + */ + +/* --- Key encoding methods and other flags--- */ + +enum { + + /* --- Bottom two bits are the encoding type --- */ + + KF_ENCMASK = 0x03, /* Encoding mask */ + KENC_BINARY = 0x00, /* Plain binary key (@k@) */ + KENC_MP = 0x01, /* Multiprecision integer (@i@) */ + KENC_STRUCT = 0x02, /* Structured key data (@s@) */ + KENC_ENCRYPT = 0x03, /* Encrypted key type (@k@) */ + + /* --- Key category bits --- */ + + KF_CATMASK = 0x0c, /* Category mask */ + KCAT_SYMM = 0x00, /* Symmetric encryption key */ + KCAT_PRIV = 0x04, /* Private (asymmetric) key */ + KCAT_PUB = 0x08, /* Public (asymmetric) key */ + KCAT_SHARE = 0x0c, /* Shared (asymmetric) key */ + KF_NONSECRET = 0x08, /* Bit flag for non-secret keys */ + + /* --- Other flags --- */ + + KF_BURN = 0x10, /* Burn key after use */ + KF_TEMP = 0x20, /* Temporary copy flag */ + + /* --- Tag end --- */ + + KENC_MAX /* Dummy limit constant */ +}; + +/* --- Key flag filtering --- */ + +typedef struct key_filter { + unsigned f; + unsigned m; +} key_filter; + +/* --- Matching aginst key selection --- */ + +#define KEY_MATCH(kd, kf) \ + (!(kf) || \ + ((kd)->e & KF_ENCMASK) == KENC_STRUCT || \ + ((kd)->e & (kf)->m) == (kf)->f) + +/*----- Key flags and filtering -------------------------------------------*/ + +/* --- @key_readflags@ --- * + * + * Arguments: @const char *p@ = pointer to string to read + * @char **pp@ = where to store the end pointer + * @unsigned *ff@ = where to store the flags + * @unsigned *mm@ = where to store the mask + * + * Returns: Zero if all went well, nonzero if there was an error. + * + * Use: Reads a flag string. + */ + +extern int key_readflags(const char */*p*/, char **/*pp*/, + unsigned */*ff*/, unsigned */*mm*/); + +/* --- @key_writeflags@ --- * + * + * Arguments: @unsigned f@ = flags to write + * @dstr *d@ = pointer to destination string + * + * Returns: --- + * + * Use: Emits a flags word as a string representation. + */ + +extern void key_writeflags(unsigned /*f*/, dstr */*d*/); + +/* --- @key_match@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const key_filter *kf@ = pointer to filter block + * + * Returns: Nonzero if the key matches the filter. + * + * Use: Checks whether a key matches a filter. + */ + +extern int key_match(key_data */*k*/, const key_filter */*kf*/); + +/*----- Setting new key data ----------------------------------------------*/ + +/* --- @key_binary@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const void *p@ = pointer to key data + * @size_t sz@ = size of the key data + * + * Returns: --- + * + * Use: Sets a binary key in a key data block. + */ + +extern void key_binary(key_data */*k*/, const void */*p*/, size_t /*sz*/); + +/* --- @key_encrypted@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const void *p@ = pointer to key data + * @size_t sz@ = size of the key data + * + * Returns: --- + * + * Use: Sets an encrypted key in a key data block. + */ + +extern void key_encrypted(key_data */*k*/, const void */*p*/, size_t /*sz*/); + +/* --- @key_mp@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @mp *m@ = pointer to the value to set + * + * Returns: --- + * + * Use: Sets a multiprecision integer key in a key block. + */ + +extern void key_mp(key_data */*k*/, mp */*m*/); + +/* --- @key_structure@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * + * Returns: --- + * + * Use: Initializes a structured key type. + */ + +extern void key_structure(key_data */*k*/); + +/* --- @key_structfind@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const char *tag@ = pointer to tag string + * + * Returns: Pointer to key data block, or null. + * + * Use: Looks up the tag in a structured key. + */ + +extern key_data *key_structfind(key_data */*k*/, const char */*tag*/); + +/* --- @key_structcreate@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const char *tag@ = pointer to tag string + * + * Returns: Pointer to newly created key data. + * + * Use: Creates a new uninitialized subkey. + */ + +extern key_data *key_structcreate(key_data */*k*/, const char */*tag*/); + +/*----- Miscellaneous operations ------------------------------------------*/ + +/* --- @key_destroy@ --- * + * + * Arguments: @key_data *k@ = pointer to key data to destroy + * + * Returns: --- + * + * Use: Destroys a lump of key data. + */ + +extern void key_destroy(key_data */*k*/); + +/* --- @key_do@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const key_filter *kf@ = pointer to filter block + * @dstr *d@ = pointer to base string + * @int (*func)(key_data *kd, dstr *d, void *p@ = function + * @void *p@ = argument to function + * + * Returns: Nonzero return code from function, or zero. + * + * Use: Runs a function over all the leaves of a key. + */ + +extern int key_do(key_data */*k*/, const key_filter */*kf*/, dstr */*d*/, + int (*/*func*/)(key_data */*kd*/, + dstr */*d*/, void */*p*/), + void */*p*/); + +/* --- @key_copy@ --- * + * + * Arguments: @key_data *kd@ = pointer to destination data block + * @key_data *k@ = pointer to source data block + * @const key_filter *kf@ = pointer to filter block + * + * Returns: Nonzero if an item was actually copied. + * + * Use: Copies a chunk of key data from one place to another. + */ + +extern int key_copy(key_data */*kd*/, key_data */*k*/, + const key_filter */*kf*/); + +/*----- Textual encoding --------------------------------------------------*/ + +/* --- @key_read@ --- * + * + * Arguments: @const char *p@ = pointer to textual key representation + * @key_data *k@ = pointer to output block for key data + * @char **pp@ = where to store the end pointer + * + * Returns: Zero if all went well, nonzero if there was a problem. + * + * Use: Parses a textual key description. + */ + +extern int key_read(const char */*p*/, key_data */*k*/, char **/*pp*/); + +/* --- @key_write@ --- * + * + * Arguments: @key_data *k@ = pointer to key data + * @dstr *d@ = destination string to write on + * @const key_filter *kf@ = pointer to key selection block + * + * Returns: Nonzero if any items were actually written. + * + * Use: Writes a key in a textual encoding. + */ + +extern int key_write(key_data */*k*/, dstr */*d*/, + const key_filter */*kf*/); + +/*----- Key binary encoding -----------------------------------------------*/ + +/* --- @key_decode@ --- * + * + * Arguments: @const void *p@ = pointer to buffer to read + * @size_t sz@ = size of the buffer + * @key_data *k@ = pointer to key data block to write to + * + * Returns: Zero if everything worked, nonzero otherwise. + * + * Use: Decodes a binary representation of a key. + */ + +extern int key_decode(const void */*p*/, size_t /*sz*/, key_data */*k*/); + +/* --- @key_encode@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @dstr *d@ = pointer to destination string + * @const key_filter *kf@ = pointer to key selection block + * + * Returns: Nonzero if any items were actually written. + * + * Use: Encodes a key block as binary data. + */ + +extern int key_encode(key_data */*k*/, dstr */*d*/, + const key_filter */*kf*/); + +/*----- Passphrase encryption ---------------------------------------------*/ + +/* --- @key_plock@ --- * + * + * Arguments: @const char *tag@ = tag to use for passphrase + * @key_data *k@ = source key data block + * @key_data *kt@ = target key data block + * + * Returns: Zero if successful, nonzero if there was a problem. + * + * Use: Locks a key by encrypting it with a passphrase. + */ + +extern int key_plock(const char */*tag*/, key_data */*k*/, key_data */*kt*/); + +/* --- @key_punlock@ --- * + * + * Arguments: @const char *tag@ = tag to use for passphrase + * @key_data *k@ = source key data block + * @key_data *kt@ = target key data block + * + * Returns: Zero if it worked, nonzero if it didn't. + * + * Use: Unlocks a passphrase-locked key. + */ + +extern int key_punlock(const char */*tag*/, + key_data */*k*/, key_data */*kt*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/key-error.c b/key-error.c new file mode 100644 index 0000000..8ca934e --- /dev/null +++ b/key-error.c @@ -0,0 +1,75 @@ +/* -*-c-*- + * + * $Id: key-error.c,v 1.1 2000/02/12 18:21:02 mdw Exp $ + * + * Translating key error codes into strings + * + * (c) 2000 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: key-error.c,v $ + * Revision 1.1 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "key.h" + +/*----- Error reporting ---------------------------------------------------*/ + +/* --- @key_strerror@ --- * + * + * Arguments: @int err@ = error code from @key_new@ + * + * Returns: Pointer to error string. + * + * Use: Translates a @KERR@ error code into a human-readable + * string. + */ + +const char *key_strerror(int err) +{ + char *tab[] = { + "No error", + "Bad tag string", + "Bad type string", + "Bad comment string", + "Keyid already exists", + "Key tag already exists", + "Key file is read-only", + "Key will eventually expire", + "Bad key flags string", + "Unknown error code" + }; + + unsigned e = -err; + if (e >= KERR_MAX) + e = KERR_MAX; + return (tab[e]); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/key-flags.c b/key-flags.c index f25bb21..7840462 100644 --- a/key-flags.c +++ b/key-flags.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-flags.c,v 1.1 1999/12/22 15:47:48 mdw Exp $ + * $Id: key-flags.c,v 1.2 2000/02/12 18:21:02 mdw Exp $ * * Reading and writing key flag strings * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key-flags.c,v $ + * Revision 1.2 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -176,4 +179,31 @@ void key_writeflags(unsigned f, dstr *d) } } +/* --- @key_match@ --- * + * + * Arguments: @key_data *k@ = pointer to key data block + * @const key_filter *kf@ = pointer to filter block + * + * Returns: Nonzero if the key matches the filter. + * + * Use: Checks whether a key matches a filter. + */ + +int key_match(key_data *k, const key_filter *kf) +{ + sym_iter i; + key_struct *ks; + + if (!kf) + return (1); + if ((k->e & KF_ENCMASK) != KENC_STRUCT) + return ((k->e & kf->m) == kf->f); + + for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { + if (key_match(&ks->k, kf)) + return (1); + } + return (0); +} + /*----- That's all, folks -------------------------------------------------*/ diff --git a/key-io.c b/key-io.c index 7ab32f3..6d4876f 100644 --- a/key-io.c +++ b/key-io.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-io.c,v 1.1 1999/12/22 15:47:48 mdw Exp $ + * $Id: key-io.c,v 1.2 2000/02/12 18:21:02 mdw Exp $ * * Adding new keys to a key file * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key-io.c,v $ + * Revision 1.2 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -44,7 +47,6 @@ #include #include -#include #include #include #include diff --git a/key-misc.c b/key-misc.c index 2d9c855..12a5f21 100644 --- a/key-misc.c +++ b/key-misc.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key-misc.c,v 1.1 1999/12/22 15:47:48 mdw Exp $ + * $Id: key-misc.c,v 1.2 2000/02/12 18:21:02 mdw Exp $ * * Simple key management * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key-misc.c,v $ + * Revision 1.2 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -42,7 +45,6 @@ #include #include -#include #include #include #include @@ -61,39 +63,6 @@ #define KEY_LOAD(n) ((n) * 2) -/*----- Error reporting ---------------------------------------------------*/ - -/* --- @key_strerror@ --- * - * - * Arguments: @int err@ = error code from @key_new@ - * - * Returns: Pointer to error string. - * - * Use: Translates a @KERR@ error code into a human-readable - * string. - */ - -const char *key_strerror(int err) -{ - char *tab[] = { - "No error", - "Bad tag string", - "Bad type string", - "Bad comment string", - "Keyid already exists", - "Key tag already exists", - "Key file is read-only", - "Key will eventually expire", - "Bad key flags string", - "Unknown error code" - }; - - unsigned e = -err; - if (e >= KERR_MAX) - e = KERR_MAX; - return (tab[e]); -} - /*----- Iteration and iterators -------------------------------------------*/ /* --- @key_mkiter@ --- * diff --git a/key-text.c b/key-text.c new file mode 100644 index 0000000..490b00b --- /dev/null +++ b/key-text.c @@ -0,0 +1,305 @@ +/* -*-c-*- + * + * $Id: key-text.c,v 1.1 2000/02/12 18:21:02 mdw Exp $ + * + * Key textual encoding + * + * (c) 1999 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: key-text.c,v $ + * Revision 1.1 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include + +#include +#include +#include +#include +#include + +#include "key-data.h" +#include "mp.h" +#include "mptext.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @key_read@ --- * + * + * Arguments: @const char *p@ = pointer to textual key representation + * @key_data *k@ = pointer to output block for key data + * @char **pp@ = where to store the end pointer + * + * Returns: Zero if all went well, nonzero if there was a problem. + * + * Use: Parses a textual key description. + */ + +int key_read(const char *p, key_data *k, char **pp) +{ + unsigned e; + + /* --- Read the encoding type --- * + * + * The key format is `[FLAGS:]DATA'. If there is no encoding type + * named, assume that it's `binary' for backwards compatibility. + */ + + if (strchr(p, ':') == 0) + e = 0; + else { + char *q; + if (key_readflags(p, &q, &e, 0)) + return (-1); + p = q + 1; + } + + /* --- Now scan the data based on the encoding type --- */ + + k->e = e; + switch (e & KF_ENCMASK) { + + /* --- Binary encoding --- * + * + * Simply read out the Base64-encoded data. Since `,' and `]' are our + * delimeter characters, and they can't appear in Base64-encoded data, I + * can just do a simple search to find the end of the encoded data. + */ + + case KENC_BINARY: + case KENC_ENCRYPT: { + dstr d = DSTR_INIT; + base64_ctx b; + size_t sz = strcspn(p, ",]"); + + base64_init(&b); + base64_decode(&b, p, sz, &d); + base64_decode(&b, 0, 0, &d); + k->u.k.k = sub_alloc(d.len); + k->u.k.sz = d.len; + memcpy(k->u.k.k, d.buf, d.len); + dstr_destroy(&d); + p += sz; + } break; + + /* --- Multiprecision integer encoding --- * + * + * Multiprecision integers have a convenient reading function. + */ + + case KENC_MP: { + char *q; + mp *m = mp_readstring(MP_NEW, p, &q, 0); + if (!m) + return (-1); + if (k->e & KF_BURN) + mp_burn(m); + k->u.m = m; + p = q; + } break; + + /* --- Structured information encoding --- * + * + * The format for structured key data is `[NAME=KEY,...]', where the + * brackets are part of the syntax. Structured keys have no flags apart + * from the encoding. + * + * The binary encoding only allows names up to 255 bytes long. Check for + * this here. + */ + + case KENC_STRUCT: { + dstr d = DSTR_INIT; + char *q; + + /* --- Read the opening bracket --- */ + + k->e &= KF_ENCMASK; + if (*p != '[') + return (-1); + p++; + sym_create(&k->u.s); + + /* --- Read named key subparts --- */ + + for (;;) { + size_t sz; + key_struct *ks; + + /* --- Stop if there's a close-bracket --- * + * + * This allows `[]' to be an empty structured key, which is good. It + * also makes `[foo=enc:bar,]' legal, and that's less good but I can + * live with it. + */ + + if (*p == ']') + break; + + /* --- Read the name out and check the length --- */ + + if ((q = strchr(p, '=')) == 0) + goto fail; + sz = q - p; + if (sz >= 256) + goto fail; + DRESET(&d); + DPUTM(&d, p, sz); + DPUTZ(&d); + + /* --- Add an appropriate block to the key table --- * + * + * Simply destroy old data if there's already a match. + */ + + { + unsigned f; + ks = sym_find(&k->u.s, d.buf, d.len + 1, sizeof(*ks), &f); + if (f) + key_destroy(&ks->k); + } + + /* --- Read the key data for the subkey --- */ + + if (key_read(q + 1, &ks->k, &q)) { + sym_remove(&k->u.s, ks); + goto fail; + } + p = q; + + /* --- Read the comma or close-bracket --- */ + + if (*p == ']') + break; + else if (*p == ',') + p++; + else + goto fail; + } + + /* --- Step past the close bracket --- */ + + p++; + dstr_destroy(&d); + break; + + /* --- Tidy up after a failure --- */ + + fail: + dstr_destroy(&d); + key_destroy(k); + return (-1); + } break; + + /* --- Anything else is unknown --- */ + + default: + return (-1); + } + + /* --- Return the end pointer --- */ + + if (pp) + *pp = (char *)p; + return (0); +} + +/* --- @key_write@ --- * + * + * Arguments: @key_data *k@ = pointer to key data + * @dstr *d@ = destination string to write on + * @const key_filter *kf@ = pointer to key selection block + * + * Returns: Nonzero if an item was actually written. + * + * Use: Writes a key in a textual encoding. + */ + +int key_write(key_data *k, dstr *d, const key_filter *kf) +{ + int rc = 0; + if (!KEY_MATCH(k, kf)) + return (0); + switch (k->e & KF_ENCMASK) { + case KENC_BINARY: + case KENC_ENCRYPT: { + base64_ctx b; + + if ((k->e & KF_ENCMASK) == KENC_BINARY) + key_writeflags(k->e, d); + else + DPUTS(d, "encrypt,secret"); + DPUTC(d, ':'); + base64_init(&b); + b.indent = ""; + b.maxline = 0; + base64_encode(&b, k->u.k.k, k->u.k.sz, d); + base64_encode(&b, 0, 0, d); + rc = 1; + } break; + case KENC_MP: + key_writeflags(k->e, d); + DPUTC(d, ':'); + mp_writedstr(k->u.m, d, 10); + rc = 1; + break; + case KENC_STRUCT: { + sym_iter i; + key_struct *ks; + char del = 0; + size_t n = d->len; + + DPUTS(d, "struct:["); + for (sym_mkiter(&i, &k->u.s); (ks = sym_next(&i)) != 0; ) { + size_t o = d->len; + if (del) + DPUTC(d, del); + DPUTS(d, SYM_NAME(ks)); + DPUTC(d, '='); + if (!key_write(&ks->k, d, kf)) + d->len = o; + else { + del = ','; + rc = 1; + } + } + if (!rc) + d->len = n; + else + DPUTC(d, ']'); + } break; + } + DPUTZ(d); + + return (rc); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/key.1 b/key.1 index 95cba9b..2f47eff 100644 --- a/key.1 +++ b/key.1 @@ -1,4 +1,12 @@ .\" -*-nroff-*- +.ie t \{\ +. ds ss \s8\u +. ds se \d\s0 +.\} +.el \{\ +. ds ss ^ +. ds se +.\} .TH key 1 "5 June 1999" Catacomb .SH NAME key \- simple key management system @@ -13,33 +21,68 @@ where is one of: .PP .B add -.RB [ \-b +.RB [ \-lq ] +.RB [ \-a +.IR alg ] +.RB [ \-b | \-B .IR bits ] +.RB [ \-p +.IR param ] +.RB [ \-r +.IR tag ] +.br +\h'8n' .RB [ \-e .IR expire ] +.RB [ \-t +.IR tag ] .RB [ \-c .IR comment ] .I type .IR attr ... .br .B expire -.IR keyid ... +.IR tag ... .br .B delete -.IR keyid ... +.IR tag ... +.br +.B tag +.I tag +.RI [ new-tag ] +.br +.B comment +.I tag +.RI [ comment ] .br .B setattr -.I keyid +.I tag .IR attr ... .br +.B lock +.I qtag +.br +.B unlock +.I qtag +.br .B list -.RB [ \-quv ] +.RB [ \-uqv ] +.RB [ \-f +.IR filter ] +.RI [ tag ...] +.br +.B fingerprint +.RB [ \-f +.IR filter ] +.RI [ tag ...] .br .B tidy .br .B extract +.RB [ \-f +.IR filter ] .I file -.IR keyid ... +.RI [ tag ...] .br .B merge .I file @@ -86,21 +129,72 @@ report a failure. In addition to the actual key data itself, a Catacomb key has a number of other pieces of information attached to it: .TP -.B keyid -Every key has a 32-bit identifying number, written in hexadecimal. The -keyid is derived from the actual key contents (although knowledge of a -key's keyid doesn't help one to guess the key itself). Applications use -keyids to refer to specific keys. A +.B "keyid" +Every key has a 32-bit identifying number, written in hexadecimal. +Keyids are not actually related to the key contents: they're generated +randomly. Applications use keyids to refer to specific keys; users are +probably better off with tags and types. A .I deleted key cannot be looked up by keyid. .TP -.B type +.B "tag" +A key's tag is a unique string which can be used by users and +applications to identify the key. Tag strings may not contain spaces, +colons or dots. A +.I deleted +key cannot be looked up by tag. Whenever a tag name is wanted, a hex +keyid or key type string can be given instead. +.TP +.B "type" A key's type string describes what the key may be used for. The type string is arbitrary, except that it may not contain whitespace -characters. Applications use key types to obtain an arbitrary but -suitable key for some purpose. An +characters, dots or colons. Applications use key types to obtain an +arbitrary but suitable key for some purpose. An .I expired -key cannot be looked up by type, but may be looked up by keyid. +key cannot be looked up by type, but may be looked up by keyid or tag. +.TP +.B "key encoding" +There are a number of different ways in which keys can be represented, +according to the uses to which the key will be put. Most symmetric +algorithms use +.I binary +keys. Keys used with number-theoretic systems (like most common +public-key systems) use +.I "multiprecision integer" +keys. Algorithms which require several key constituents (again, like +most public-key systems) use +.I structured +keys, which consist of a collection of named parts. Finally, keys +(including structured keys) can be encrypted. +.TP +.B "filter" +Keys and key components may be selected by a filter expression, a +sequence of flag names separated by commas. Flags are: +.BR binary , +.BR integer , +.B struct +or +.B encrypt +(describing the key encoding); +.BR symmetric , +.BR private , +.B public +or +.B shared +(describing the category of key); +.B burn +and its negation +.B \-burn +(whether the key should be erased from memory after use); and +.B secret +and its negation +.B \-secret +(whether the key is safe to divulge). +.TP +.B "qualified tag" +A key component may be identified by the key's tag (or keyid, or type). +Subcomponents of structured keys are identified by following the tag by +a dot and the name of the subcomponent. .TP .B "expiry time" Most keys expire after a certain amount of time. Once a key has @@ -112,19 +206,17 @@ reached. A key's deletion time is the latest expiry time of any of the objects which require that key. For example, a key used for authenticating cryptographic cookies should have its deletion time set to the longest -expiry time of any of the cookies it can authenticate. A key is never -deleted until it has also expired. Once a key has expired -.I and -its deletion time is passed, it can no longer be referred to by +expiry time of any of the cookies it can authenticate. Once a key's +deletion time is passed, it can no longer be referred to by applications, and will be removed from the keyring next time it's written to disk. .TP -.B comment +.B "comment" A key may be given a comment when it's created. The comment is for the benefit of users, and isn't interpreted by applications at all. (Hopefully.) .TP -.B attributes +.B "attributes" A key as zero or more name/value pairs. The names and values are arbitrary strings, except they may not contain null bytes. Some attributes may have meaning for particular applications or key types; @@ -136,10 +228,22 @@ The command creates a new key and adds it to the keyring. The command accepts the following options: .TP +.BI "\-a, \-\-algorithm " alg +Selects a key generation algorithm. The default algorithm is +.BR binary ; +the different algorithms are described below. +.TP .BI "\-b, \-\-bits " bits The length of the key to generate, in bits. The default, if this option -is not supplied, is 128 bits. The bit length must be nonzero, and must -be a multiple of 8. +is not supplied, depends on the key-generation algorithm. +.TP +.BI "\-B, \-\-qbits " bits +The length of the subsidiary key or parameter, in bits. Not all +key-generation algorithms have a subsidiary key size. +.TP +.BI "\-p, \-\-parameters " tag +Selects a key containing parameter values to copy. Not all +key-generation algorithms allow the use of shared parameters. .TP .BI "\-e, \-\-expire " expire The expiry date for the generated key. This may be the string @@ -159,6 +263,28 @@ The default is to allow a 2 week expiry, which isn't useful. .TP .BI "\-c, \-\-comment " comment Sets a comment for the key. The default is not to attach a comment. +.TP +.BI "\-t, \-\-tag " tag +Selects a tag string for the key. The default is not to set a tag. It +is an error to select a tag which already exists. +.TP +.BI "\-r, \-\-rand-id " tag +Selects the key to use for the random number generator. Catacomb's +random number generator can be +.IR keyed , +so that, even if the inputs to the generator are compromised, knowledge +of the key is also necessary to be able to predict the output. By +default, the latest-expiring key with type +.B catacomb-rand +is used, if present; if not, no key is used. +.TP +.BI "\-l, \-\-lock" +Requests that the secret parts of the newly-generated key be encrypted +using a passphrase. +.TP +.BI "\-q, \-\-quiet" +Suppresses the progress indication which is usually generated while +time-consuming key generation tasks are being performed. .PP The key's type is given by the required .I type @@ -167,36 +293,236 @@ attached to the key in the same way as for the .B setattr command. .PP -The -.B key -program only generates random bitstrings, which are suitable for most -symmetric algorithms but not for public key cryptography. Generating -keys for more exotic algorithms is a feature which will be added later. -The keys are generated using the Catacomb random number generator, using -the -.B rand_goodbits -function. The Catacomb generator is believed to be strong. -.SS expire +The key-generation algorithms supported are as follows: +.TP +.B "binary" +Generates a plain binary key of the requested length. If the requested +key length is not a multiple of eight, the high-order bits of the first +octet of the key are zeroed. The default key length is 128 bits. +.TP +.B "des" +Generates a DES key, with parity bits. The key length must be 56, 112 +or 168; the default is 56. The low-order bit of each octet is ignored by +the DES algorithm; it is used to give each octet odd parity. +.TP +.B "rsa" +Generates a public/private key pair for use with the RSA algorithm. +.IP +The key components are +.I p +and +.IR q , +a pair of prime numbers; +.IR n , +the product of +.I p +and +.IR q ; +.IR e , +the public exponent; +.IR d , +the private exponent, chosen such that +.IR ed \ \(==\ 1 +(mod +.RI ( p \ \-\ 1)( q \ \-\ 1)); +and some other values useful for optimizing private-key operations: +.IR q \*(ss\-1\*(se\ mod\ p , +.IR d \ mod\ p \ \-\ 1, +and +.IR d \ mod\ q \ \-\ 1. +The values +.I n +and +.I e +constitute the public key; the rest must be kept secret. The key size +requested by the +.B \-b +option determines the size of the modulus +.IR n ; +the default is 1024 bits. +.IP +The key generation algorithm chooses +.I p +and +.I q +to be +.I strong +primes: both +.IR p \ \-\ 1 +and +.IR p \ +\ 1 +have large prime factors \- call them +.I r +and +.I s +respectively \- and +.IR r \ \-\ 1 +also has a large prime factor; +.I q +has similar properties. +.IP +The modulus +.I n +cannot be sensibly used as a shared parameter, since knowledge of +corrssponding public and private exponents is sufficient to be able to +factor the modulus and recover other users' private keys. +.TP +.B "dh-params" +Generates parameters for use with the Diffie-Hellman key exchange +protocol, and many related systems, such as ElGamal encryption and +signatures, and even DSA (although the DSA algorithm is probably better +for this). The parameters are a prime number +.IR q , +a larger prime number +.IR p , +and a generator +.I g +of the +.RI order- q +subgroup of the integers +.RI mod\ p . +.IP +The key size set by the +.B \-b +option determines the size of the modulus +.IR p ; +the size of the generator order +.I q +is set by the +.B \-B +option. The default modulus size is 1024 bits; if no size is specified +for +.IR q , +the parameters are chosen such that +.IR p \ =\ 2 q \ +\ 1, +and +.I +g +is assigned the value 4. This takes much longer. +.IP +If used with the +.B \-p +option, the algorithm simply copies the parameters from an existing key. +.TP +.B "dh" +Generates a public/private key pair for use with offline Diffie-Hellman, +ElGamal, DSA or similar discrete-logarithm-based systems. It selects a +private key +.IR x \ <\ q , +and computes the public key +.IR y \ =\ g\*(ssx\*(se \ mod\ p . +.TP +.B "dsa-param" +Generates parameters for the DSA algorithm. DSA parameters are also +suitable for use with Diffie-Hellman and ElGamal system. +.IP +The main difference between DSA and Diffie-Hellman parameter generation +is thatthe DSA parameter generation +algorithm creates a +.I seed +from which the parameters are derived, and, assuming that the SHA-1 hash +function is strong, it's not feasible to construct a seed from which +deliberately weak parameters are derived. The algorithm used is the one +described in the DSA standard, FIPS\ 186, extended only to allow +sequential search for a prime +.I q +and to allow arbitrary parameter sizes. The seed is stored, +Base64-encoded, as the value of the attribute +.BR seed . +.IP +The default lengths for +.I p +and +.I q +are 768 and 160 bits respectively, since the DSA standard specifies that +.I q +be 160 bits, and the choice of 768 bits for +.I p +gives commensurate security. +.TP +.B "dsa" +Generates a public/private key pair for DSA. As for Diffie-Hellman +keys, it selects a +private key +.IR x \ <\ q , +and computes the public key +.IR y \ =\ g\*(ssx\*(se \ mod\ p . +.TP +.B "bbs" +Generates a public/private key pair for the Blum-Blum-Shub random-number +generator, and the Blum-Goldwasser semantically-secure public-key +encryption system. +.IP +The key components are prime numbers +.I p +and +.IR q , +both congruent to 3 (mod\ 4), and their product +.IR n . +The public key is simply the modulus +.IR n ; +the factors +.I p +and +.I q +are the private key. +.IP +The key-generation algorithm ensures that the two primes +.I p +and +.I q +are +.I strong +(see the discussion of strong primes above, in the section on RSA keys), +and that +.RI ( p \ \-\ 1)/2 +and +.RI ( q \ \-\ 1)/2 +are relatively prime, giving a maximum possible period length. +.IP +The key size requested by the +.B \-b +option determines the length of the modulus +.IR n ; +the default length is 1024 bits. +.SS "expire" Forces keys to immediately expire. An expired key is not chosen when a program requests a key by its type. The keys to expire are listed by their -.IR keyid s. -.SS delete +.IR tag s. +.SS "delete" Deletes keys immediately. The keys to delete are listed by their -.IR keyid s. +.IR tag s. Be careful when deleting keys. It might be a better idea to expire keys rather than deleting them. -.SS setattr +.SS "tag" +Sets, deletes or changes the tag attached to a key. The first tag or +keyid names the key to be modified; the second, if present specifies the +new tag to be set. If no second argument is given, the existing tag, if +any, is removed and no new tag is set. +.SS "setattr" Attaches attributes to a key. The key to which the attributes should be attached is given by its -.IR keyid . +.IR tag . Each attribute has the form .IB name = value\fR. An attribute can be deleted by assigning it an empty value. Although the keyring file format is capable of representing an attribute with an empty value as distinct from a nonexistant attribute, this interface does not allow empty attributes to be set. -.SS list +.SS "comment" +Sets, deletes or changes the comment attached to a key. The first +argument is a key tag or keyid which names the key to be modified; the +second, if present, is the new comment. If no second argument is given, +the existing comment, if any, is removed, and no new comment is set. +.SS "lock" +Locks a key or key component using a passphrase. If the key is already +locked, the existing passphrase is requested, and a new passphrase is +set. +.SS "unlock" +Unlocks a passphrase-locked key or key component. If the key is not +locked, an error is reported. +.SS "list" Lists the keys in the keyring. A couple of options are supported: .TP .B "\-v, \-\-verbose" @@ -211,24 +537,48 @@ option. .TP .B "\-u, \-\-utc" Display key expiry times as UTC rather than using the local time zone. +.TP +.BI "\-f, \-\-filter " filter +Specifies a filter. Only keys and key components which match the filter +are listed. .PP By default, a single line of output is generated for each, showing keyids, types, expiry and deletion dates, and comments. Additional .RB ` \-v ' options show more information, such as the exact time of day for expiry -and deletion, key attributes, and a hex dump of the actual key data. -.SS tidy +and deletion, key attributes, and a dump of the actual key data. If the +verbosity level is sufficiently high, passphrases are requested to +decrypt locked keys. Make sure nobody is looking over your shoulder +when you do this! +.SS "fingerprint" +Reports a fingerprint (secure hash) on components of requested keys. +The following option is supported: +.TP +.BI "\-f, \-\-filter " filter +Specifies a filter. Only keys and key components which match the filter +are fingerprinted. The default is to only fingerprint nonsecret +components. +.PP +The keys to be fingerprinted are named by their tags or keyids given as +command line arguments. If no key tags are given, all keys which match +the filter are fingerprinted. +.SS "tidy" Simply reads the keyring from file and writes it back again. This has the effect of removing any deleted keys from the file. -.SS extract -Writes a selection of keys to the named -.IR file , +.SS "extract" +Writes a selection of keys to a file. An option is supported: +.TP +.BI "\-f, \-\-filter " filter +Specifies a filter. Only keys and key components which match the filter +are written. +.PP +Keys extracted are written to the file named by the first argument, which may be .RB ` \- ' to designate standard output. The keys to extract are listed by their -.IR keyid s. -The output is a valid keyring file. -.SS merge +tags; if no tags are given, all keys which match the filter are +extracted. The output is a valid keyring file. +.SS "merge" Merges the keys from the named .IR file , which may be @@ -236,11 +586,6 @@ which may be to designate standard input, with the keyring. Keys already in the keyring are not overwritten: you must explicitly remove them first if you want them to be replaced during the merge. -.SH BUGS -The ability to generate keys for specific algorithms ought to be added, -for DES (setting the parity bits correctly), RSA, ElGamal and DSA, at -the very least. (None of these systems are actually implemented in -Catacomb at the moment, however.) .SH "SEE ALSO" .BR keyring (5). .SH AUTHOR diff --git a/key.h b/key.h index 6a17ded..d779489 100644 --- a/key.h +++ b/key.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: key.h,v 1.3 1999/12/22 15:47:48 mdw Exp $ + * $Id: key.h,v 1.4 2000/02/12 18:21:02 mdw Exp $ * * Simple key management * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: key.h,v $ + * Revision 1.4 2000/02/12 18:21:02 mdw + * Overhaul of key management (again). + * * Revision 1.3 1999/12/22 15:47:48 mdw * Major key-management revision. * @@ -58,6 +61,10 @@ #include #include +#ifndef CATACOMB_KEY_DATA_H +# include "key-data.h" +#endif + #ifndef CATACOMB_MP_H # include "mp.h" #endif @@ -76,99 +83,6 @@ typedef struct key_attr { char *p; /* Pointer to attribute value */ } key_attr; -/* --- Key data structure --- */ - -typedef struct key_data { - unsigned e; /* Encoding type for key data */ - union { - - /* --- Plain binary key data --- * - * - * Also used for encrypted key types. - */ - - struct { - octet *k; /* Actual key data */ - size_t sz; /* Size of the key data */ - } k; /* Plain binary key */ - - /* --- Multiprecision integer keys --- */ - - mp *m; /* Multiprecision integer */ - - /* --- Structured key data --- */ - - sym_table s; /* Structured key data */ - } u; -} key_data; - -typedef struct key_struct { - sym_base _b; - key_data k; -} key_struct; - -/* --- Key binary encoding --- * - * - * The binary encoding consists of a header containing a 16-bit encoding type - * and a 16-bit length, followed immediately by the key data, followed by - * between zero and three zero bytes to make the total length a multiple of - * four. The format of the following data depends on the encoding type: - * - * @KENC_BINARY@ Binary data. - * - * @KENC_MP@ Octet array interpreted in big-endian byte order. - * - * @KENC_STRUCT@ An array of pairs, each containing a string (8-bit - * length followed by data and zero-padding to 4-byte - * boundary) and key binary encodings. - * - * @KENC_ENCRYPT@ Binary data, format - */ - -/* --- Key encoding methods and other flags--- */ - -enum { - - /* --- Bottom two bits are the encoding type --- */ - - KF_ENCMASK = 0x03, /* Encoding mask */ - KENC_BINARY = 0x00, /* Plain binary key (@k@) */ - KENC_MP = 0x01, /* Multiprecision integer (@i@) */ - KENC_STRUCT = 0x02, /* Structured key data (@s@) */ - KENC_ENCRYPT = 0x03, /* Encrypted key type (@k@) */ - - /* --- Key category bits --- */ - - KF_CATMASK = 0x0c, /* Category mask */ - KCAT_SYMM = 0x00, /* Symmetric encryption key */ - KCAT_PRIV = 0x04, /* Private (asymmetric) key */ - KCAT_PUB = 0x08, /* Public (asymmetric) key */ - KCAT_SHARE = 0x0c, /* Shared (asymmetric) key */ - KF_NONSECRET = 0x08, /* Bit flag for non-secret keys */ - - /* --- Other flags --- */ - - KF_BURN = 0x10, /* Burn key after use */ - - /* --- Tag end --- */ - - KENC_MAX /* Dummy limit constant */ -}; - -/* --- Key flag filtering --- */ - -typedef struct key_filter { - unsigned f; - unsigned m; -} key_filter; - -/* --- Matching aginst key selection --- */ - -#define KEY_MATCH(kd, kf) \ - (!(kf) || \ - ((kd)->e & KF_ENCMASK) == KENC_STRUCT || \ - ((kd)->e & (kf)->m) == (kf)->f) - /* --- Main key structure --- * * * Each key is stored in two symbol tables, one indexed by keyid, and the @@ -250,7 +164,7 @@ enum { /* --- Key error codes --- */ enum { - KERR_OK, /* No error */ + KERR_OK = 0, /* No error */ KERR_BADTAG = -1, /* Malformed tag string */ KERR_BADTYPE = -2, /* Malformed type string */ KERR_BADCOMMENT = -3, /* Malformed comment string */ @@ -260,6 +174,9 @@ enum { KERR_WILLEXPIRE = -7, /* Key will eventually expire */ KERR_EXPIRED = -8, /* Key has already expired */ KERR_BADFLAGS = -9, /* Error in flags string */ + KERR_BADPASS = -10, /* Error decrypting locked key */ + KERR_BADTYPE = -11, /* Key has incorrect type */ + KERR_NOTFOUND = -12, /* Key couldn't be found */ KERR_MAX /* Largest possible error */ }; @@ -281,244 +198,6 @@ typedef void key_reporter(const char */*file*/, int /*line*/, #define KEY_EXPIRED(now, exp) \ ((exp) == KEXP_EXPIRE || ((exp) != KEXP_FOREVER && (exp) < (now))) -/*----- Key data manipulation ---------------------------------------------*/ - -/* --- @key_destroy@ --- * - * - * Arguments: @key_data *k@ = pointer to key data to destroy - * - * Returns: --- - * - * Use: Destroys a lump of key data. - */ - -extern void key_destroy(key_data */*k*/); - -/* --- @key_readflags@ --- * - * - * Arguments: @const char *p@ = pointer to string to read - * @char **pp@ = where to store the end pointer - * @unsigned *ff@ = where to store the flags - * @unsigned *mm@ = where to store the mask - * - * Returns: Zero if all went well, nonzero if there was an error. - * - * Use: Reads a flag string. - */ - -extern int key_readflags(const char */*p*/, char **/*pp*/, - unsigned */*ff*/, unsigned */*mm*/); - -/* --- @key_writeflags@ --- * - * - * Arguments: @unsigned f@ = flags to write - * @dstr *d@ = pointer to destination string - * - * Returns: --- - * - * Use: Emits a flags word as a string representation. - */ - -extern void key_writeflags(unsigned /*f*/, dstr */*d*/); - -/* --- @key_binary@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const void *p@ = pointer to key data - * @size_t sz@ = size of the key data - * - * Returns: --- - * - * Use: Sets a binary key in a key data block. - */ - -extern void key_binary(key_data */*k*/, const void */*p*/, size_t /*sz*/); - -/* --- @key_encrypted@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const void *p@ = pointer to key data - * @size_t sz@ = size of the key data - * - * Returns: --- - * - * Use: Sets an encrypted key in a key data block. - */ - -extern void key_encrypted(key_data */*k*/, const void */*p*/, size_t /*sz*/); - -/* --- @key_mp@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @mp *m@ = pointer to the value to set - * - * Returns: --- - * - * Use: Sets a multiprecision integer key in a key block. - */ - -extern void key_mp(key_data */*k*/, mp */*m*/); - -/* --- @key_structure@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * - * Returns: --- - * - * Use: Initializes a structured key type. - */ - -extern void key_structure(key_data */*k*/); - -/* --- @key_structfind@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const char *tag@ = pointer to tag string - * - * Returns: Pointer to key data block, or null. - * - * Use: Looks up the tag in a structured key. - */ - -extern key_data *key_structfind(key_data */*k*/, const char */*tag*/); - -/* --- @key_structcreate@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const char *tag@ = pointer to tag string - * - * Returns: Pointer to newly created key data. - * - * Use: Creates a new uninitialized subkey. - */ - -extern key_data *key_structcreate(key_data */*k*/, const char */*tag*/); - -/* --- @key_match@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const key_filter *kf@ = pointer to filter block - * - * Returns: Nonzero if the key matches the filter. - * - * Use: Checks whether a key matches a filter. - */ - -extern int key_match(key_data */*k*/, const key_filter */*kf*/); - -/* --- @key_do@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @const key_filter *kf@ = pointer to filter block - * @dstr *d@ = pointer to base string - * @int (*func)(key_data *kd, dstr *d, void *p@ = function - * @void *p@ = argument to function - * - * Returns: Nonzero return code from function, or zero. - * - * Use: Runs a function over all the leaves of a key. - */ - -extern int key_do(key_data */*k*/, const key_filter */*kf*/, dstr */*d*/, - int (*/*func*/)(key_data */*kd*/, - dstr */*d*/, void */*p*/), - void */*p*/); - -/* --- @key_copy@ --- * - * - * Arguments: @key_data *kd@ = pointer to destination data block - * @key_data *k@ = pointer to source data block - * @const key_filter *kf@ = pointer to filter block - * - * Returns: Nonzero if an item was actually copied. - * - * Use: Copies a chunk of key data from one place to another. - */ - -extern int key_copy(key_data */*kd*/, key_data */*k*/, - const key_filter */*kf*/); - -/* --- @key_read@ --- * - * - * Arguments: @const char *p@ = pointer to textual key representation - * @key_data *k@ = pointer to output block for key data - * @char **pp@ = where to store the end pointer - * - * Returns: Zero if all went well, nonzero if there was a problem. - * - * Use: Parses a textual key description. - */ - -extern int key_read(const char */*p*/, key_data */*k*/, char **/*pp*/); - -/* --- @key_write@ --- * - * - * Arguments: @key_data *k@ = pointer to key data - * @dstr *d@ = destination string to write on - * @const key_filter *kf@ = pointer to key selection block - * - * Returns: Nonzero if any items were actually written. - * - * Use: Writes a key in a textual encoding. - */ - -extern int key_write(key_data */*k*/, dstr */*d*/, - const key_filter */*kf*/); - -/* --- @key_decode@ --- * - * - * Arguments: @const void *p@ = pointer to buffer to read - * @size_t sz@ = size of the buffer - * @key_data *k@ = pointer to key data block to write to - * - * Returns: Zero if everything worked, nonzero otherwise. - * - * Use: Decodes a binary representation of a key. - */ - -extern int key_decode(const void */*p*/, size_t /*sz*/, key_data */*k*/); - -/* --- @key_encode@ --- * - * - * Arguments: @key_data *k@ = pointer to key data block - * @dstr *d@ = pointer to destination string - * @const key_filter *kf@ = pointer to key selection block - * - * Returns: Nonzero if any items were actually written. - * - * Use: Encodes a key block as binary data. - */ - -extern int key_encode(key_data */*k*/, dstr */*d*/, - const key_filter */*kf*/); - -/* --- @key_plock@ --- * - * - * Arguments: @const char *tag@ = tag to use for passphrase - * @key_data *k@ = source key data block - * @key_data *kt@ = target key data block - * - * Returns: Zero if successful, nonzero if there was a problem. - * - * Use: Locks a key by encrypting it with a passphrase. - */ - -extern int key_plock(const char */*tag*/, key_data */*k*/, key_data */*kt*/); - -/* --- @key_punlock@ --- * - * - * Arguments: @const char *tag@ = tag to use for passphrase - * @key_data *k@ = source key data block - * @key_data *kt@ = target key data block - * - * Returns: Zero if it worked, nonzero if it didn't. - * - * Use: Unlocks a passphrase-locked key. - */ - -extern int key_punlock(const char */*tag*/, - key_data */*k*/, key_data */*kt*/); - /*----- Reading and writing keys and files --------------------------------*/ /* --- @key_merge@ --- * diff --git a/keyutil.c b/keyutil.c index b6b1bf9..673f4ea 100644 --- a/keyutil.c +++ b/keyutil.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: keyutil.c,v 1.4 1999/12/22 15:48:10 mdw Exp $ + * $Id: keyutil.c,v 1.5 2000/02/12 18:21:03 mdw Exp $ * * Simple key manager program * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: keyutil.c,v $ + * 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. @@ -66,6 +69,7 @@ #include #include "bbs.h" +#include "dh.h" #include "dsa.h" #include "fibrand.h" #include "getdate.h" @@ -97,7 +101,7 @@ static const char *keyfile = "keyring"; static void doopen(key_file *f, unsigned how) { if (key_open(f, keyfile, how, key_moan, 0)) - die(1, "couldn't open file `%s': %s", keyfile, strerror(errno)); + die(1, "couldn't open keyring `%s': %s", keyfile, strerror(errno)); } /* --- @doclose@ --- * @@ -268,6 +272,58 @@ static mp *getmp(key_data *k, const char *tag) return (k->u.m); } +/* --- @keyrand@ --- * + * + * Arguments: @key_file *kf@ = pointer to key file + * @const char *id@ = pointer to key id (or null) + * + * Returns: --- + * + * Use: Keys the random number generator. + */ + +static void keyrand(key_file *kf, const char *id) +{ + key *k; + + /* --- Find the key --- */ + + if (id) { + if ((k = key_bytag(kf, id)) == 0) + die(EXIT_FAILURE, "key `%s' not found", id); + } else + k = key_bytype(kf, "catacomb-rand"); + + if (k) { + key_data *kd = &k->k, kkd; + + again: + switch (kd->e & KF_ENCMASK) { + case KENC_BINARY: + break; + case KENC_ENCRYPT: { + dstr d = DSTR_INIT; + key_fulltag(k, &d); + if (key_punlock(d.buf, kd, &kkd)) + die(EXIT_FAILURE, "error unlocking key `%s'", d.buf); + dstr_destroy(&d); + kd = &kkd; + } goto again; + default: { + dstr d = DSTR_INIT; + key_fulltag(k, &d); + die(EXIT_FAILURE, "bad encoding type for key `%s'", d.buf); + } break; + } + + /* --- Key the generator --- */ + + rand_key(RAND_GLOBAL, kd->u.k.k, kd->u.k.sz); + if (kd == &kkd) + key_destroy(&kkd); + } +} + /* --- Key generation algorithms --- */ static void alg_binary(keyopts *k) @@ -310,10 +366,10 @@ static void alg_des(keyopts *k) p = sub_alloc(sz); rand_getgood(RAND_GLOBAL, p, sz); /* Too much work done here! */ for (i = 0; i < sz; i++) { - octet x = p[i] & 0xfe; + octet x = p[i] | 0x01; x = x ^ (x >> 4); x = x ^ (x >> 2); - x = x ^ (x >> 1) ^ 1; + x = x ^ (x >> 1); p[i] = (p[i] & 0xfe) | (x & 0x01); } key_binary(&k->k->k, p, sz); @@ -471,14 +527,15 @@ static void alg_dsa(keyopts *k) key_structure(kd); mpkey(kd, "x", x, KCAT_PRIV | KF_BURN); dolock(k, kd, "private"); + + mp_drop(x); mp_drop(y); } static void alg_dhparam(keyopts *k) { - static const char *pl[] = { "p", "g", 0 }; + static const char *pl[] = { "p", "q", "g", 0 }; if (!copyparam(k, pl)) { - pgen_safetestctx c; - mp *p, *q; + dh_param dp; key_data *kd = &k->k->k; if (!k->bits) @@ -486,35 +543,24 @@ static void alg_dhparam(keyopts *k) /* --- Choose a large safe prime number --- */ - q = MP_NEW; - q = mprand(q, k->bits, &rand_global, 3); - p = pgen("p", MP_NEW, q, (k->f & f_quiet) ? 0 : pgen_ev, 0, - 0, pgen_safestep, &c.c, - rabin_iters(k->bits), pgen_safetest, &c); - if (!p) + if (dh_gen(&dp, k->qbits, k->bits, 0, &rand_global, + (k->f & f_quiet) ? 0 : pgen_ev, 0)) die(EXIT_FAILURE, "Diffie-Hellman parameter generation failed"); key_structure(kd); - mpkey(kd, "p", p, KCAT_SHARE); - mp_drop(q); - mp_drop(p); - - /* --- The generator 4 is good --- * - * - * Since 4 is clearly a quadratic residue, and %$p = 2q + 1$% for prime - * %$q$%, the number 4 has order %$q$%. This is better than choosing a - * real primitive element, because it could conceivably be trapped in an - * order-2 subgroup. (Not very likely, I'll admit, but possible.) - */ - - mpkey(kd, "g", MP_FOUR, KCAT_SHARE); + mpkey(kd, "p", dp.p, KCAT_SHARE); + mpkey(kd, "q", dp.q, KCAT_SHARE); + mpkey(kd, "g", dp.g, KCAT_SHARE); + mp_drop(dp.q); + mp_drop(dp.p); + mp_drop(dp.g); } } static void alg_dh(keyopts *k) { mp *x, *y; - mp *p, *g; + mp *p, *q, *g; mpmont mm; key_data *kd = &k->k->k; @@ -522,6 +568,7 @@ static void alg_dh(keyopts *k) alg_dhparam(k); p = getmp(kd, "p"); + q = getmp(kd, "q"); g = getmp(kd, "g"); /* --- Choose a suitable private key --- * @@ -529,14 +576,13 @@ static void alg_dh(keyopts *k) * Since %$g$% has order %$q$%, choose %$x < q$%. */ - y = mp_lsr(MP_NEW, p, 1); - x = mprand_range(MP_NEW, y, &rand_global, 0); + x = mprand_range(MP_NEW, q, &rand_global, 0); mp_burn(x); /* --- Compute the public key %$y = g^x \bmod p$% --- */ mpmont_create(&mm, p); - y = mpmont_exp(&mm, y, g, x); + y = mpmont_exp(&mm, MP_NEW, g, x); mpmont_destroy(&mm); /* --- Store everything away --- */ @@ -547,13 +593,14 @@ static void alg_dh(keyopts *k) key_structure(kd); mpkey(kd, "x", x, KCAT_PRIV | KF_BURN); dolock(k, kd, "private"); + + mp_drop(x); mp_drop(y); } static void alg_bbs(keyopts *k) { bbs_param bp; key_data *kd; - mp *p, *q; /* --- Sanity checking --- */ @@ -564,12 +611,9 @@ static void alg_bbs(keyopts *k) /* --- Generate the BBS parameters --- */ - p = mprand(MP_NEW, k->bits / 2, &rand_global, 3); - q = mprand(MP_NEW, k->bits - k->bits / 2, &rand_global, 3); - mp_burn(p); mp_burn(q); - if (bbs_gen(&bp, p, q, 0, (k->f & f_quiet) ? 0 : pgen_ev, 0)) + if (bbs_gen(&bp, k->bits, &rand_global, 0, + (k->f & f_quiet) ? 0 : pgen_ev, 0)) die(EXIT_FAILURE, "Blum-Blum-Shub key generation failed"); - mp_drop(p); mp_drop(q); /* --- Allrighty then --- */ @@ -615,6 +659,7 @@ static int cmd_add(int argc, char *argv[]) const char *tag = 0, *ptag = 0; const char *c = 0; keyalg *alg = algtab; + const char *rtag = 0; keyopts k = { 0, 0, DSTR_INIT, 0, 0, 0, 0 }; /* --- Parse options for the subcommand --- */ @@ -628,11 +673,12 @@ 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' }, { "lock", 0, 0, 'l' }, { "quiet", 0, 0, 'q' }, { 0, 0, 0, 0 } }; - int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:l", opt, 0, 0, 0); + int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:r:lq", opt, 0, 0, 0); if (i < 0) break; @@ -720,6 +766,9 @@ static int cmd_add(int argc, char *argv[]) /* --- Other flags --- */ + case 'r': + rtag = optarg; + break; case 'l': k.f |= f_lock; break; @@ -757,6 +806,10 @@ static int cmd_add(int argc, char *argv[]) doopen(&f, KOPEN_WRITE); k.kf = &f; + /* --- Key the generator --- */ + + keyrand(&f, rtag); + for (;;) { uint32 id = rand_global.ops->word(&rand_global); int err; @@ -1192,26 +1245,6 @@ static int cmd_setattr(int argc, char *argv[]) /* --- @cmd_finger@ --- */ -static int fpkey(key_data *kd, dstr *d, void *p) -{ - rmd160_ctx *r = p; - switch (kd->e & KF_ENCMASK) { - case KENC_BINARY: - case KENC_ENCRYPT: - rmd160_hash(r, kd->u.k.k, kd->u.k.sz); - break; - case KENC_MP: { - size_t sz = mp_octets(kd->u.m); - octet *q = sub_alloc(sz); - mp_storeb(kd->u.m, q, sz); - rmd160_hash(r, q, sz); - memset(q, 0, sz); - sub_free(q, sz); - } break; - } - return (0); -} - static void fingerprint(key *k, const key_filter *kf) { rmd160_ctx r; @@ -1219,12 +1252,13 @@ static void fingerprint(key *k, const key_filter *kf) dstr d = DSTR_INIT; int i; - if (!key_match(&k->k, kf)) + if (!key_encode(&k->k, &d, kf)) return; rmd160_init(&r); - key_do(&k->k, kf, 0, fpkey, &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) @@ -1480,7 +1514,7 @@ static struct cmd { } cmds[] = { { "add", cmd_add, "add [options] type [attr...]\n\ - Options: [-l] [-a alg] [-b bits] [-p param]\n\ + Options: [-lq] [-a alg] [-b|-B bits] [-p param] [-r tag]\n\ [-e expire] [-t tag] [-c comment]" }, { "expire", cmd_expire, "expire tag..." }, @@ -1493,7 +1527,7 @@ static struct cmd { { "list", cmd_list, "list [-uqv] [-f filter] [tag...]" }, { "fingerprint", cmd_finger, "fingerprint [-f filter] [tag...]" }, { "tidy", cmd_tidy, "tidy" }, - { "extract", cmd_extract, "extract file qtag..." }, + { "extract", cmd_extract, "extract [-f filter] file [tag...]" }, { "merge", cmd_merge, "merge file" }, { 0, 0, 0 } }; @@ -1506,12 +1540,12 @@ typedef struct cmd cmd; void usage(FILE *fp) { - fprintf(fp, "Usage: %s [-k file] command [args]\n", QUIS); + pquis(fp, "Usage: $ [-k file] [-i tag] [-t type] command [args]\n"); } void version(FILE *fp) { - fprintf(fp, "%s, Catacomb version " VERSION "\n", QUIS); + pquis(fp, "$, Catacomb version " VERSION "\n"); } void help(FILE *fp) @@ -1529,6 +1563,8 @@ recognized are:\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", fp); @@ -1559,11 +1595,6 @@ int main(int argc, char *argv[]) ego(argv[0]); sub_init(); - /* --- Initialize the Catacomb random number generator --- */ - - rand_init(RAND_GLOBAL); - rand_noisesrc(RAND_GLOBAL, &noise_source); - /* --- Parse command line options --- */ for (;;) { @@ -1578,12 +1609,14 @@ 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:", opt, 0, 0, 0); + int i = mdwopt(argc, argv, "+hvu k:i:t:", opt, 0, 0, 0); if (i < 0) break; @@ -1621,6 +1654,11 @@ int main(int argc, char *argv[]) exit(1); } + /* --- Initialize the Catacomb random number generator --- */ + + rand_init(RAND_GLOBAL); + rand_noisesrc(RAND_GLOBAL, &noise_source); + /* --- Dispatch to appropriate command handler --- */ argc -= optind; diff --git a/pgen-safe.c b/pgen-safe.c index 32b91e3..a8c5ac7 100644 --- a/pgen-safe.c +++ b/pgen-safe.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: pgen-safe.c,v 1.1 1999/12/22 16:01:34 mdw Exp $ + * $Id: pgen-safe.c,v 1.2 2000/02/12 18:21:03 mdw Exp $ * * Safe prime generation * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: pgen-safe.c,v $ + * Revision 1.2 2000/02/12 18:21:03 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 16:01:34 mdw * Find `safe' primes (i.e., %$p = 2q + 1$%). * @@ -52,37 +55,113 @@ int pgen_safestep(int rq, pgen_event *ev, void *p) { pgen_safestepctx *c = p; - int prc = PGEN_ABORT, qrc; + int rc = PGEN_ABORT, qrc = 0; switch (rq) { + + /* --- Set up the contexts --- */ + case PGEN_BEGIN: { mp *p = mp_split(MP_COPY(ev->m)); mp *q; p->v[0] |= 3; q = mp_lsr(MP_NEW, p, 1); + rc = pfilt_create(&c->p, p); qrc = pfilt_create(&c->q, q); - prc = pfilt_create(&c->p, p); - mp_drop(p); - mp_drop(q); - } goto step; + mp_drop(p); mp_drop(q); + } break; + + /* --- Step along --- */ + case PGEN_TRY: - again: - qrc = pfilt_step(&c->q, 2); - prc = pfilt_step(&c->p, 4); - step: - if (qrc == PGEN_FAIL || prc == PGEN_FAIL) - goto again; mp_drop(ev->m); - ev->m = MP_COPY(c->p.m); - if (qrc == PGEN_TRY) - prc = PGEN_TRY; + rc = pfilt_step(&c->p, 4); + qrc = pfilt_step(&c->q, 2); + break; + break; + + /* --- Tidy the toys away --- */ + case PGEN_DONE: pfilt_destroy(&c->q); pfilt_destroy(&c->p); + return (PGEN_DONE); + } + + /* --- Continue stepping if necessary --- */ + + while (rc == PGEN_FAIL || qrc == PGEN_FAIL) { + rc = pfilt_step(&c->p, 4); + qrc = pfilt_step(&c->q, 2); + } + + ev->m = MP_COPY(c->p.m); + if (qrc == PGEN_TRY) + rc = PGEN_TRY; + return (rc); +} + +/* --- @pgen_safejump@ --- * + * + * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any + * small factors. + */ + +int pgen_safejump(int rq, pgen_event *ev, void *p) +{ + pgen_safejumpctx *j = p; + int rc = PGEN_ABORT, qrc = 0; + + switch (rq) { + + /* --- Set up the jump contexts --- * + * + * The jump in @j.q@ is congruent to 2 (mod 4); see @strongprime_setup@. + * If @p@ is initially 1 (mod 4) then add @j.q@. Then double @j.q@ to + * ensure that the step is 0 (mod 4). + */ + + case PGEN_BEGIN: { + mp *p = ev->m; + mp *q; + if ((p->v[0] & 3) != 3) + p = mp_add(p, p, j->jq.m); + rc = pfilt_create(&j->p, p); + pfilt_muladd(&j->jp, &j->jq, 2, 0); + q = mp_lsr(MP_NEW, p, 1); + qrc = pfilt_create(&j->q, q); + mp_drop(p); + mp_drop(q); + } break; + + /* --- Step on one place --- */ + + case PGEN_TRY: + mp_drop(ev->m); + rc = pfilt_jump(&j->p, &j->jp); + qrc = pfilt_jump(&j->q, &j->jq); break; + + /* --- Tidy everything up --- */ + + case PGEN_DONE: + pfilt_destroy(&j->jp); + pfilt_destroy(&j->p); + pfilt_destroy(&j->q); + return (PGEN_DONE); } - return (prc); + + /* --- Step on while @p@ or @q@ have small factors --- */ + + while (rc == PGEN_FAIL || qrc == PGEN_FAIL) { + rc = pfilt_jump(&j->p, &j->jp); + qrc = pfilt_jump(&j->q, &j->jq); + } + ev->m = MP_COPY(j->p.m); + if (qrc == PGEN_TRY) + rc = PGEN_TRY; + return (rc); } /* --- @pgen_safetest@ --- * diff --git a/pgen.h b/pgen.h index 9ce4e86..05d0a2c 100644 --- a/pgen.h +++ b/pgen.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: pgen.h,v 1.4 1999/12/22 16:01:11 mdw Exp $ + * $Id: pgen.h,v 1.5 2000/02/12 18:21:03 mdw Exp $ * * Prime generation glue * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: pgen.h,v $ + * Revision 1.5 2000/02/12 18:21:03 mdw + * Overhaul of key management (again). + * * Revision 1.4 1999/12/22 16:01:11 mdw * Same file, completely different code. Main interface for new prime- * search system. @@ -191,6 +194,19 @@ typedef struct pgen_safestepctx { extern int pgen_safestep(int /*rq*/, pgen_event */*ev*/, void */*p*/); +/* --- @pgen_safejump@ --- * + * + * Jumps two numbers, %$q$% and %$p = 2q + 1$% such that neither has any + * small factors. + */ + +typedef struct pgen_safejumpctx { + pfilt q, jq; + pfilt p, jp; +} pgen_safejumpctx; + +extern int pgen_safejump(int /*rq*/, pgen_event */*ev*/, void */*p*/); + /* --- @pgen_safetest@ --- * * * Applies Rabin-Miller tests to %$p$% and %$(p - 1)/2$%. diff --git a/rspit.c b/rspit.c index 3c14ab4..ec55707 100644 --- a/rspit.c +++ b/rspit.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: rspit.c,v 1.2 1999/12/22 15:59:51 mdw Exp $ + * $Id: rspit.c,v 1.3 2000/02/12 18:21:03 mdw Exp $ * * Spit out random numbers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: rspit.c,v $ + * Revision 1.3 2000/02/12 18:21:03 mdw + * Overhaul of key management (again). + * * Revision 1.2 1999/12/22 15:59:51 mdw * New prime-search system. Read BBS keys from key files. * @@ -441,11 +444,10 @@ static grand *gen_bbs(unsigned i) m = MP_COPY(kd->u.m); key_close(&kf); } else { - mp *p = mprand(MP_NEW, bits / 2, &rand_global, 3); - mp *q = mprand(MP_NEW, bits - bits / 2, &rand_global, 3); bbs_param bp; - if (bbs_gen(&bp, p, q, 0, (flags & f_progress) ? pgen_ev : 0, 0)) + if (bbs_gen(&bp, bits, &rand_global, 0, + (flags & f_progress) ? pgen_ev : 0, 0)) die(EXIT_FAILURE, "modulus generation failed"); m = bp.n; @@ -459,8 +461,6 @@ static grand *gen_bbs(unsigned i) fputc('\n', stderr); } - mp_drop(p); - mp_drop(q); mp_drop(bp.p); mp_drop(bp.q); } diff --git a/strongprime.c b/strongprime.c index 4a7ddb8..a5f6052 100644 --- a/strongprime.c +++ b/strongprime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: strongprime.c,v 1.1 1999/12/22 15:51:22 mdw Exp $ + * $Id: strongprime.c,v 1.2 2000/02/12 18:21:03 mdw Exp $ * * Generate `strong' prime numbers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: strongprime.c,v $ + * Revision 1.2 2000/02/12 18:21:03 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:51:22 mdw * Find `strong' RSA primes using Gordon's algorithm. * @@ -50,37 +53,34 @@ /*----- Main code ---------------------------------------------------------*/ -/* --- @strongprime@ --- * +/* --- @strongprime_setup@ --- * * * Arguments: @const char *name@ = pointer to name root - * @mp *d@ = destination integer + * @mp *d@ = destination for search start point + * @pfilt *f@ = where to store filter jump context * @unsigned nbits@ = number of bits wanted * @grand *r@ = random number source * @unsigned n@ = number of attempts to make * @pgen_proc *event@ = event handler function * @void *ectx@ = argument for the event handler * - * Returns: A `strong' prime, or zero. - * - * Use: Finds `strong' primes. A strong prime %$p$% is such that - * - * * %$p - 1$% has a large prime factor %$r$%, - * * %$p + 1$% has a large prime factor %$s$%, and - * * %$r - 1$% has a large prime factor %$t$%. + * Returns: A starting point for a `strong' prime search, or zero. * - * The numbers produced may be slightly larger than requested, - * by a few bits. + * Use: Sets up for a strong prime search, so that primes with + * particular properties can be found. It's probably important + * to note that the number left in the filter context @f@ is + * congruent to 2 (mod 4). */ -mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, - unsigned n, pgen_proc *event, void *ectx) +mp *strongprime_setup(const char *name, mp *d, pfilt *f, unsigned nbits, + grand *r, unsigned n, pgen_proc *event, void *ectx) { - mp *s, *t, *q, *p = 0; + mp *s, *t, *q; dstr dn = DSTR_INIT; - mp *rr = MP_NEW; + mp *rr = d; pgen_filterctx c; - pgen_jumpctx cj; + pgen_jumpctx j; rabin rb; /* --- The bitslop parameter --- * @@ -91,7 +91,7 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, * numbers around 10 seem to be good. */ -#define BITSLOP 10 +#define BITSLOP 12 /* --- Choose two primes %$s$% and %$t$% of half the required size --- */ @@ -101,7 +101,7 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, rr = mprand(rr, nbits, r, 1); DRESET(&dn); dstr_putf(&dn, "%s [s]", name); if ((s = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_filter, &c, - rabin_iters(nbits), pgen_test, &rb)) == 0) + rabin_iters(nbits), pgen_test, &rb)) == 0) goto fail_s; mp_burn(s); @@ -119,12 +119,13 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, rr = mp_lsl(rr, rr, BITSLOP - 1); rr = mp_add(rr, rr, MP_ONE); DRESET(&dn); dstr_putf(&dn, "%s [r]", name); - cj.j = &c.f; + j.j = &c.f; nbits += BITSLOP; - if ((q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &cj, - rabin_iters(nbits), pgen_test, &rb)) == 0) - goto fail_r; + q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &j, + rabin_iters(nbits), pgen_test, &rb); pfilt_destroy(&c.f); + if (!q) + goto fail_r; /* --- Select a suitable starting-point for finding %$p$% --- * * @@ -149,32 +150,75 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, mp *x; x = mp_mul(MP_NEW, q, s); x = mp_lsl(x, x, 1); - pfilt_create(&c.f, x); + pfilt_create(f, x); x = mp_lsl(x, x, BITSLOP - 1); rr = mp_add(rr, rr, x); mp_drop(x); } - if ((p = pgen(name, d, rr, event, ectx, n, pgen_jump, &cj, - rabin_iters(nbits * 2), pgen_test, &rb)) == 0) - goto fail_p; + /* --- Return the result --- */ - /* --- Tidy up because we've finished --- */ +#if 0 +fputs("r = ", stdout); mp_writefile(q, stdout, 10); putchar('\n'); +fputs("s = ", stdout); mp_writefile(s, stdout, 10); putchar('\n'); +fputs("t = ", stdout); mp_writefile(t, stdout, 10); putchar('\n'); +#endif -fail_p: mp_drop(q); + mp_drop(t); + mp_drop(s); + dstr_destroy(&dn); + return (rr); + + /* --- Tidy up if something failed --- */ + fail_r: - pfilt_destroy(&c.f); mp_drop(t); fail_t: mp_drop(s); fail_s: mp_drop(rr); dstr_destroy(&dn); - - return (p); + return (0); #undef BITSLOP } +/* --- @strongprime@ --- * + * + * Arguments: @const char *name@ = pointer to name root + * @mp *d@ = destination integer + * @unsigned nbits@ = number of bits wanted + * @grand *r@ = random number source + * @unsigned n@ = number of attempts to make + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for the event handler + * + * Returns: A `strong' prime, or zero. + * + * Use: Finds `strong' primes. A strong prime %$p$% is such that + * + * * %$p - 1$% has a large prime factor %$r$%, + * * %$p + 1$% has a large prime factor %$s$%, and + * * %$r - 1$% has a large prime factor %$t$%. + * + * The numbers produced may be slightly larger than requested, + * by a few bits. + */ + +mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, + unsigned n, pgen_proc *event, void *ectx) +{ + pfilt f; + pgen_jumpctx j; + rabin rb; + + d = strongprime_setup(name, d, &f, nbits, r, n, event, ectx); + j.j = &f; + d = pgen(name, d, d, event, ectx, n, pgen_jump, &j, + rabin_iters(nbits), pgen_test, &rb); + pfilt_destroy(&f); + return (d); +} + /*----- That's all, folks -------------------------------------------------*/ diff --git a/strongprime.h b/strongprime.h index 6f06cda..0b53a79 100644 --- a/strongprime.h +++ b/strongprime.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: strongprime.h,v 1.1 1999/12/22 15:51:22 mdw Exp $ + * $Id: strongprime.h,v 1.2 2000/02/12 18:21:03 mdw Exp $ * * Generate `strong' prime numbers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: strongprime.h,v $ + * Revision 1.2 2000/02/12 18:21:03 mdw + * Overhaul of key management (again). + * * Revision 1.1 1999/12/22 15:51:22 mdw * Find `strong' RSA primes using Gordon's algorithm. * @@ -54,6 +57,30 @@ /*----- Functions provided ------------------------------------------------*/ +/* --- @strongprime_setup@ --- * + * + * Arguments: @const char *name@ = pointer to name root + * @mp *d@ = destination for search start point + * @pfilt *f@ = where to store filter jump context + * @unsigned nbits@ = number of bits wanted + * @grand *r@ = random number source + * @unsigned n@ = number of attempts to make + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for the event handler + * + * Returns: A starting point for a `strong' prime search, or zero. + * + * Use: Sets up for a strong prime search, so that primes with + * particular properties can be found. It's probably important + * to note that the number left in the filter context @f@ is + * congruent to 2 (mod 4). + */ + +extern mp *strongprime_setup(const char */*name*/, mp */*d*/, pfilt */*f*/, + unsigned /*nbits*/, grand */*r*/, + unsigned /*n*/, pgen_proc */*event*/, + void */*ectx*/); + /* --- @strongprime@ --- * * * Arguments: @const char *name@ = pointer to name root -- 2.11.0