X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/8b810a45dec25017a6256e4ef134236444a00921..f41f820e4b3e230d9314cc4323abf59babdd4e67:/dsa-gen.c diff --git a/dsa-gen.c b/dsa-gen.c index ac33088..40454d8 100644 --- a/dsa-gen.c +++ b/dsa-gen.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: dsa-gen.c,v 1.1 1999/11/19 19:28:00 mdw Exp $ + * $Id: dsa-gen.c,v 1.5 2000/02/12 18:21:02 mdw Exp $ * * Generate DSA shared parameters * @@ -30,6 +30,18 @@ /*----- 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. + * + * Revision 1.3 1999/12/10 23:18:38 mdw + * Change interface for suggested destinations. + * + * Revision 1.2 1999/11/20 22:23:48 mdw + * Allow event handler to abort the search process. + * * Revision 1.1 1999/11/19 19:28:00 mdw * Implementation of the Digital Signature Algorithm. * @@ -41,306 +53,182 @@ #include #include "dsa.h" +#include "dsarand.h" +#include "fibrand.h" #include "mp.h" +#include "mprand.h" #include "pgen.h" -#include "rabin.h" -#include "rc4.h" +#include "prim.h" +#include "primorial.h" #include "sha.h" -/*----- Main code ---------------------------------------------------------*/ +/*----- The DSA stepper ---------------------------------------------------*/ -/* --- @dsa_seed@ --- * +/* --- @next@ --- * * - * Arguments: @dsa_param *dp@ = where to store parameters - * @unsigned l@ = bitlength of @p@ in bits - * @const void *k@ = pointer to key material - * @void (*proc)(int ev, mp *m, void *p)@ = event procedure - * @size_t sz@ = size of key material + * Arguments: @pgen_event *ev@ = pointer to event block + * @dsa_stepctx *d@ = pointer to stepping context * - * Returns: Zero if all went well, nonzero if key material was - * unsuitable (one of the @DSAEV@ codes). + * Returns: A @PGEN@ result code. * - * Use: Generates the DSA shared parameters from a given seed value. - * This can take quite a long time. The size of @p@ in bits is - * %$l = 512 + 64l'$%. The DSA standard, FIPS 186, only allows - * %$0 \le l' \le 8$%. This implementation has no such limit, - * although @l@ must be a multiple of 8. - * - * The event procedure is informed of various happenings during - * generation. It is passed an event code describing what - * happened, and a multiprecision number which pertains to the - * event code. + * Use: Steps the generator once, reads the result, and tests it. */ -int dsa_seed(dsa_param *dp, unsigned l, const void *k, size_t sz, - void (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg) +static int next(pgen_event *ev, dsa_stepctx *d) { - mp *q, *p, *g; - mp *s = mp_loadb(MP_NEW, k, sz); - octet *sbuf = xmalloc(sz); - rc4_ctx rc4; - int fail; + mp *m; + int rc; - l /= 8; - rc4_init(&rc4, k, sz); + /* --- Load the new candidate --- */ - /* --- Generate @q@ --- */ + m = mprand(ev->m, d->bits, d->r, d->or); - { - octet xbuf[SHA_HASHSZ], ybuf[SHA_HASHSZ]; - sha_ctx c; - int i; - - sha_init(&c); - sha_hash(&c, k, sz); - sha_done(&c, xbuf); - - MPX_UADDN(s->v, s->vl, 1); - mp_storeb(s, sbuf, sz); - sha_init(&c); - sha_hash(&c, sbuf, sz); - sha_done(&c, ybuf); - - for (i = 0; i < sizeof(xbuf); i++) - xbuf[i] ^= ybuf[i]; - xbuf[0] |= 0x80; - xbuf[SHA_HASHSZ - 1] |= 0x01; - q = mp_loadb(MP_NEW, xbuf, sizeof(xbuf)); - } - - /* --- Quick primality check --- */ + /* --- Force to be a multiple of @q@ --- */ - { - pgen pg; - int rc = pgen_create(&pg, q); - pgen_destroy(&pg); - if (rc == PGEN_COMPOSITE) { - if (proc) - proc(DSAEV_FAILQ, q, arg); - fail = DSAEV_FAILQ; - goto fail_0; - } + if (d->q) { + mp *r = MP_NEW; + mp_div(0, &r, m, d->q); + m = mp_sub(m, m, r); + mp_drop(r); } + m->v[0] |= d->or; + ev->m = m; - /* --- Ensure that @q@ is prime --- * - * - * This requires 18 iterations, because the DSA spec is paranoid. - * Fortunately, it doesn't actually take very long. - */ + /* --- Do the trial division --- */ { - rabin r; - int i; mp *g = MP_NEW; - octet gbuf[SHA_HASHSZ]; - - rabin_create(&r, q); - for (i = 0; i < 18; i++) { - rc4_encrypt(&rc4, 0, gbuf, sizeof(gbuf)); - g = mp_loadb(g, gbuf, sizeof(gbuf)); - if (rabin_test(&r, g) == PGEN_COMPOSITE) - break; - if (proc) - proc(DSAEV_PASSQ, q, arg); - } + mp_gcd(&g, 0, 0, m, primorial); + if (MP_CMP(g, ==, MP_ONE) || MP_CMP(g, ==, m)) + rc = PGEN_TRY; + else + rc = PGEN_FAIL; mp_drop(g); - rabin_destroy(&r); - if (i < 18) { - if (proc) - proc(DSAEV_FAILQ, q, arg); - fail = DSAEV_FAILQ; - goto fail_0; - } - if (proc) - proc(DSAEV_GOODQ, q, arg); } - /* --- Now generate @p@ --- * - * - * This is, unfortunately, rather more messy and complicated. - */ + /* --- Return the result --- */ - { - mp *q2 = mp_lsl(MP_NEW, q, 1); - mp *ll = mp_lsl(MP_NEW, MP_ONE, l * 8 - 1); - unsigned n = l / SHA_HASHSZ, b = l % SHA_HASHSZ; - size_t psz = SHA_HASHSZ * (n + 1); - octet *pbuf = xmalloc(psz); - sha_ctx c; - unsigned i, j; - - /* --- Fiddle with the leftover bytes count --- */ - - b = SHA_HASHSZ - b; - - /* --- Go round 4096 times trying different @p@ values --- */ - - p = MP_NEW; - for (j = 0; j < 4096; j++) { - - /* --- Build a prospective value of @p@ --- */ - - { - octet *pp = pbuf + SHA_HASHSZ * n; - - for (i = 0; i <= n; i++) { - MPX_UADDN(s->v, s->vl, 1); - mp_storeb(s, sbuf, sz); - sha_init(&c); - sha_hash(&c, sbuf, sz); - sha_done(&c, pp); - pp -= SHA_HASHSZ; - } - - pbuf[b] &= 0x7f; - p = mp_loadb(p, pbuf + b, psz - b); - p = mp_add(p, p, ll); - } - - /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */ - - { - mp *c = MP_NEW; - mp_div(0, &c, p, q2); - c = mp_sub(c, c, MP_ONE); - p = mp_sub(p, p, c); - mp_drop(c); - } - - /* --- Check that @p@ is large enough --- */ - - if (MP_CMP(p, <, ll)) - continue; - - /* --- Run a simple primality test --- */ - - { - pgen pg; - int rc = pgen_create(&pg, p); - pgen_destroy(&pg); - if (rc == PGEN_COMPOSITE) - continue; - } - - /* --- Run the Rabin-Miller test --- */ - - { - rabin r; - mp *g = MP_NEW; - - if (proc) - proc(DSAEV_TRYP, p, arg); - rabin_create(&r, p); - for (i = 0; i < 5; i++) { - rc4_encrypt(&rc4, 0, pbuf, psz - b); - g = mp_loadb(g, pbuf, psz - b); - if (rabin_test(&r, g) == PGEN_COMPOSITE) - break; - if (proc) - proc(DSAEV_PASSP, p, arg); - } - mp_drop(g); - rabin_destroy(&r); - if (i < 5) { - if (proc) - proc(DSAEV_FAILP, p, arg); - fail = DSAEV_FAILP; - continue; - } - } - - /* --- It worked! --- */ - - if (proc) - proc(DSAEV_GOODP, p, arg); - break; - } + return (rc); +} + +/* --- @dsa_step@ --- */ - free(pbuf); - mp_drop(q2); - mp_drop(ll); - if (j >= 4096) - goto fail_1; +int dsa_step(int rq, pgen_event *ev, void *p) +{ + dsa_stepctx *d = p; + + switch (rq) { + case PGEN_BEGIN: + primorial_setup(); + case PGEN_TRY: + return (next(ev, d)); + case PGEN_DONE: + return (PGEN_DONE); } + return (PGEN_ABORT); +} - /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */ +/*----- Glue code ---------------------------------------------------------*/ - { - mp *pp = MP_NEW; - mpw hw; - mp h; - unsigned i; - mpmont mm; - - /* --- Calculate %$p' = (p - 1)/q$% --- */ - - { - mp *p1 = mp_sub(MP_NEW, p, MP_ONE); - mp_div(&pp, 0, p1, q); - mp_drop(p1); - } +/* --- @dsa_seed@ --- * + * + * Arguments: @dsa_param *dp@ = where to store parameters + * @unsigned ql@ = length of @q@ in bits + * @unsigned pl@ = length of @p@ in bits + * @unsigned steps@ = number of steps to find @q@ + * @const void *k@ = pointer to key material + * @size_t sz@ = size of key material + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for event handler + * + * Returns: @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise. + * + * Use: Generates the DSA shared parameters from a given seed 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 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 + * requires that %$q$% be 160 bits in size (i.e., @ql == 160@) + * and that the length of %$p$% be %$L = 512 + 64l$% for some + * %$l$%. Neither limitation applies to this implementation. + */ - /* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */ - - mp_build(&h, &hw, &hw + 1); - mpmont_create(&mm, p); - for (i = 0; i < NPRIME; i++) { - hw = ptab[i]; - if (proc) - proc(DSAEV_TRYH, &h, arg); - g = mpmont_exp(&mm, &h, pp); - if (MP_CMP(g, !=, MP_ONE)) - break; - if (proc) - proc(DSAEV_FAILH, &h, arg); - mp_drop(g); - } - mp_drop(pp); - if (i >= NPRIME) { - fail = DSAEV_FAILH; - goto fail_1; - } - } - if (proc) - proc(DSAEV_GOODG, g, arg); +int dsa_seed(dsa_param *dp, unsigned ql, unsigned pl, unsigned steps, + const void *k, size_t sz, pgen_proc *event, void *ectx) +{ + dsa_stepctx s; + prim_ctx p; + int i; + rabin r; + mp *qc; - /* --- Return the important information that I succeeded --- */ + /* --- Initialize the stepping context --- */ - dp->p = p; - dp->q = q; - dp->g = g; - free(sbuf); - return (0); + s.r = dsarand_create(k, sz); + s.or = 1; - /* --- Tidy up after failure --- */ + /* --- Find @q@ --- */ -fail_1: - mp_drop(p); -fail_0: - mp_drop(q); - mp_drop(s); - free(sbuf); - return (-1); -} + s.q = 0; + s.r->ops->misc(s.r, DSARAND_PASSES, 2); + s.bits = ql; + if ((dp->q = pgen("q", MP_NEW, MP_NEW, event, ectx, steps, dsa_step, &s, + rabin_iters(ql), pgen_test, &r)) == 0) + goto fail_q; -/*----- Test rig ----------------------------------------------------------*/ + /* --- Find @p@ --- */ -#ifdef TEST_RIG + s.q = mp_lsl(MP_NEW, dp->q, 1); + s.r->ops->misc(s.r, DSARAND_PASSES, 1); + s.bits = pl; + if ((dp->p = pgen("p", MP_NEW, MP_NEW, event, ectx, 4096, dsa_step, &s, + rabin_iters(pl), pgen_test, &r)) == 0) + goto fail_p; + mp_drop(s.q); -static char baton[] = "/-\\|"; -static char *b = baton; + /* --- Find @g@ --- * + * + * The division returns remainder 1. This doesn't matter. + */ -static void event(int ev, mp *m, void *p) -{ - if (ev == DSAEV_TRYP || ev == DSAEV_PASSP) { - fputc(*b++, stdout); - fputc('\b', stdout); - fflush(stdout); - if (!*b) - b = baton; - } + mpmont_create(&p.mm, dp->p); + qc = MP_NEW; mp_div(&qc, 0, dp->p, dp->q); + i = 0; + p.f = qc; + p.n = 0; + if ((dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i, + 1, prim_test, &p)) == 0) + goto fail_g; + + /* --- Done --- */ + + mp_drop(qc); + mpmont_destroy(&p.mm); + s.r->ops->destroy(s.r); + return (PGEN_DONE); + + /* --- Tidy up when things go wrong --- */ + +fail_g: + mp_drop(qc); + mpmont_destroy(&p.mm); +fail_p: + mp_drop(dp->q); + mp_drop(s.q); +fail_q: + s.r->ops->destroy(s.r); + return (PGEN_ABORT); } +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + static int verify(dstr *v) { mp *q = *(mp **)v[2].buf; @@ -351,14 +239,14 @@ static int verify(dstr *v) int ok = 1; int rc; - rc = dsa_seed(&dp, l, v[0].buf, v[0].len, event, 0); + rc = dsa_seed(&dp, 160, l, 1, v[0].buf, v[0].len, pgen_evspin, 0); if (rc || MP_CMP(q, !=, dp.q) || MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) { fputs("\n*** gen failed", stderr); fputs("\nseed = ", stderr); type_hex.dump(&v[0], stderr); fprintf(stderr, "\nl = %u", l); fputs("\n q = ", stderr); mp_writefile(q, stderr, 16); - fputs("\n p = ", stderr); mp_writefile(q, stderr, 16); + fputs("\n p = ", stderr); mp_writefile(p, stderr, 16); fputs("\n g = ", stderr); mp_writefile(g, stderr, 16); if (!rc) { fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16); @@ -373,6 +261,7 @@ static int verify(dstr *v) if (!rc) { mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g); } + assert(mparena_count(MPARENA_GLOBAL) == 1); /* Primorial! */ return (ok); }