From b04a7659918367dcc8570e1c7b4246a97e88288d Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 22 Dec 1999 15:52:44 +0000 Subject: [PATCH] Reworking for new prime-search system. --- bbs-gen.c | 256 ++++++++++++-------------------------- dsa-gen.c | 422 +++++++++++++++++++++----------------------------------------- dsa.h | 87 ++++++------- 3 files changed, 266 insertions(+), 499 deletions(-) diff --git a/bbs-gen.c b/bbs-gen.c index 1855219..8780274 100644 --- a/bbs-gen.c +++ b/bbs-gen.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs-gen.c,v 1.1 1999/12/10 23:14:59 mdw Exp $ + * $Id: bbs-gen.c,v 1.2 1999/12/22 15:52:28 mdw Exp $ * * Generate Blum integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: bbs-gen.c,v $ + * Revision 1.2 1999/12/22 15:52:28 mdw + * Reworking for new prime-search system. + * * Revision 1.1 1999/12/10 23:14:59 mdw * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. * @@ -42,24 +45,71 @@ #include #include "bbs.h" -#include "fibrand.h" #include "mp.h" #include "mprand.h" #include "pgen.h" -#include "rabin.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct gcdctx { + mp *q; + mp *r; + pfilt p; +} gcdctx; + +/*----- Custom stepper ----------------------------------------------------*/ + +static int gcdstep(int rq, pgen_event *ev, void *p) +{ + gcdctx *g = p; + int rc = PGEN_ABORT; + mp *z = MP_NEW; + + switch (rq) { + case PGEN_BEGIN: { + mp *p = ev->m = mp_split(ev->m); + p->v[0] |= 3; + g->q = mp_lsr(MP_NEW, p, 1); + rc = pfilt_create(&g->p, p); + } break; + case PGEN_TRY: + g->q = mp_add(g->q, g->q, MP_FOUR); + rc = pfilt_step(&g->p, 4); + break; + case PGEN_DONE: + pfilt_destroy(&g->p); + mp_drop(g->q); + return (PGEN_DONE); + } + for (;;) { + if (rc != PGEN_FAIL) { + mp_gcd(&z, 0, 0, g->r, g->q); + if (MP_CMP(z, !=, MP_ONE)) + rc = PGEN_FAIL; + } + if (rc != PGEN_FAIL) + break; + g->q = mp_add(g->q, g->q, MP_FOUR); + rc = pfilt_step(&g->p, 4); + } + + mp_drop(z); + mp_drop(ev->m); + ev->m = MP_COPY(g->p.m); + return (rc); +} /*----- Main code ---------------------------------------------------------*/ /* --- @bbs_gen@ --- * * - * Arguments: @bbs_params *bp@ = pointer to parameter block + * Arguments: @bbs_param *bp@ = pointer to parameter block * @mp *p, *q@ = initial numbers to search from * @size_t n@ = number of attempts to make - * @void (*proc)(int ev, mp *m, void *p)@ = event handler - * @void *arg@ = argument for event handler + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for event handler * - * Returns: Zero if all went well, otherwise an event code which explains - * the problem. + * Returns: If it worked OK, @PGEN_DONE@, otherwise @PGEN_ABORT@. * * Use: Finds two prime numbers %$p'$% and %$q'$% such that both are * congruent to %$3 \bmod 4$%, and $(p - 1)/2$% and @@ -68,181 +118,39 @@ * Shub pseudorandom bit generator. */ -int bbs_gen(bbs_params *bp, mp *p, mp *q, size_t n, - int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg) +int bbs_gen(bbs_param *bp, mp *p, mp *q, size_t n, + pgen_proc *event, void *ectx) { - pgen px, py; - mp *pp; - mp *g = MP_NEW; - grand *gr = fibrand_create(0); - int rcx, rcy; - int fail = BBSEV_OK; - size_t sz; - - /* --- Initialize @p@ and @q@ --- * - * - * Divide both by two, and make the results odd. - */ - - p = mp_lsr(MP_NEW, p, 1); p->v[0] |= 1; - q = mp_lsr(MP_NEW, q, 1); q->v[0] |= 1; - - /* --- Set up the search for @p@ --- * - * - * I want a prime %$p$% such that %$(p - 1)/2$% has no small factors. - */ - - rcx = pgen_create(&px, p); mp_drop(p); - rcy = pgen_muladd(&py, &px, 2, 1); - - if (proc && (fail = proc(BBSEV_FINDP, 0, arg)) != 0) - goto fail_0; - - sz = mp_bits(py.m); - for (;;) { - if (rcx != PGEN_COMPOSITE && rcy != PGEN_COMPOSITE) { - if (rcy != PGEN_PRIME) { - rabin r; - int i; - - if (proc && (fail = proc(BBSEV_TRYP, py.m, arg)) != 0) - break; - rabin_create(&r, py.m); - for (i = 0; i < 5; i++) { - g = mprand(g, sz, gr, 1); - if ((rcy = rabin_test(&r, g)) == PGEN_COMPOSITE) - break; - if (proc && (fail = proc(BBSEV_PASSP, py.m, arg)) != 0) - break; - } - rabin_destroy(&r); - if (fail) - goto fail_0; - if (i < 5) { - if (proc && (fail = proc(BBSEV_FAILP, py.m, arg)) != 0) - goto fail_0; - if (n) { - n--; - if (!n) { - fail = BBSEV_FAILP; - goto fail_0; - } - } - } - } - - if (rcy != PGEN_COMPOSITE) - break; - } - rcx = pgen_step(&px, 2); - rcy = pgen_step(&py, 4); - } + rabin r; + pgen_safestepctx c; + gcdctx g; - if (proc && (fail = proc(BBSEV_GOODP, py.m, arg)) != 0) - goto fail_0; + /* --- Generate @p@ --- */ - /* --- I now have a @p@ (and a %$(p - 1)/2$%) --- */ + if ((bp->p = pgen("p", MP_NEW, p, event, ectx, n, pgen_safestep, &c, + rabin_iters(mp_bits(p)), pgen_test, &r)) == 0) + goto fail_p; - pp = MP_COPY(px.m); pgen_destroy(&px); - p = MP_COPY(py.m); pgen_destroy(&py); + /* --- Generate @q@ --- */ - /* --- Next trick is to generate @q@ --- * - * - * I don't care about small factors of %$(q - 1)/2$%, just that it's - * relatively prime to %$(p - 1)/2$%. - */ + 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) + goto fail_q; - { - mp *m = mp_lsl(MP_NEW, q, 1); - m->v[0] |= 1; - rcx = pgen_create(&px, m); - mp_drop(m); - } + /* --- Compute @n@ --- */ - if (proc && (fail = proc(BBSEV_FINDQ, 0, arg)) != 0) - goto fail_1; + bp->n = mp_mul(MP_NEW, bp->p, bp->q); + mp_drop(g.r); + return (PGEN_DONE); - for (;;) { - if (rcx != PGEN_COMPOSITE) { - int ok; - - /* --- Ensure that %$(p - 1)/2$% and %$(q - 1)/2$% are coprime --- */ - - mp_gcd(&g, 0, 0, pp, q); - ok = MP_CMP(g, ==, MP_ONE); - - if (ok && rcx != PGEN_PRIME) { - rabin r; - int i; - - if (proc && (fail = proc(BBSEV_TRYQ, px.m, arg)) != 0) - break; - rabin_create(&r, px.m); - for (i = 0; i < 5; i++) { - g = mprand(g, sz, gr, 1); - if ((rcx = rabin_test(&r, g)) == PGEN_COMPOSITE) - break; - if (proc && (fail = proc(BBSEV_PASSQ, px.m, arg)) != 0) - break; - } - rabin_destroy(&r); - if (fail) - goto fail_1; - if (i < 5) { - if (proc && (fail = proc(BBSEV_FAILQ, px.m, arg)) != 0) - goto fail_1; - if (n) { - n--; - if (!n) { - fail = BBSEV_FAILQ; - goto fail_1; - } - } - } - } - - if (ok && rcx != PGEN_COMPOSITE) - break; - } - - q = mp_add(q, q, MP_TWO); - rcx = pgen_step(&px, 4); - } + /* --- Tidy up if things went wrong --- */ - if (proc && (fail = proc(BBSEV_GOODQ, px.m, arg)) != 0) - goto fail_1; - - /* --- Done --- */ - - mp_drop(g); - mp_drop(q); - mp_drop(pp); - q = MP_COPY(px.m); - bp->p = p; - bp->q = q; - pgen_destroy(&px); - bp->n = mp_mul(MP_NEW, p, q); - gr->ops->destroy(gr); - return (0); - - /* --- Failed --- */ - -fail_1: - pgen_destroy(&px); - mp_drop(p); - mp_drop(pp); - mp_drop(g); - gr->ops->destroy(gr); - return (fail); - -fail_0: - if (g) - mp_drop(g); - pgen_destroy(&px); - pgen_destroy(&py); - mp_drop(q); - gr->ops->destroy(gr); - return (fail); +fail_q: + mp_drop(g.r); + mp_drop(bp->p); +fail_p: + return (PGEN_ABORT); } /*----- That's all, folks -------------------------------------------------*/ diff --git a/dsa-gen.c b/dsa-gen.c index b719a23..d26bfe4 100644 --- a/dsa-gen.c +++ b/dsa-gen.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: dsa-gen.c,v 1.3 1999/12/10 23:18:38 mdw Exp $ + * $Id: dsa-gen.c,v 1.4 1999/12/22 15:52:44 mdw Exp $ * * Generate DSA shared parameters * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: dsa-gen.c,v $ + * 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. * @@ -47,324 +50,177 @@ #include #include "dsa.h" +#include "dsarand.h" #include "fibrand.h" #include "mp.h" #include "mprand.h" #include "pgen.h" -#include "rabin.h" +#include "prim.h" +#include "primorial.h" #include "sha.h" -/*----- Main code ---------------------------------------------------------*/ +/*----- The DSA stepper ---------------------------------------------------*/ -/* --- @dsa_seed@ --- * - * - * Arguments: @dsa_param *dp@ = where to store parameters - * @unsigned l@ = bitlength of @p@ in bits - * @const void *k@ = pointer to key material - * @size_t sz@ = size of key material - * @int (*proc)(int ev, mp *m, void *p)@ = event procedure +/* --- @next@ --- * * - * Returns: Zero if all went well, nonzero if key material was - * unsuitable (one of the @DSAEV@ codes). + * Arguments: @pgen_event *ev@ = pointer to event block + * @dsa_stepctx *d@ = pointer to stepping context * - * 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. + * Returns: A @PGEN@ result code. * - * 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. It may abort the search at any time by returning - * a nonzero value, which is returned as the result of the - * function. + * 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, - int (*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); - grand *gr; - int fail = 0; - - l /= 8; - gr = fibrand_create(LOAD32(k)); - - /* --- Generate @q@ --- */ + mp *m; + int rc; - { - 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)); - } + /* --- Load the new candidate --- */ - /* --- Quick primality check --- */ + m = mprand(ev->m, d->bits, d->r, d->or); - if (proc && (fail = proc(DSAEV_FINDQ, 0, arg)) != 0) - goto fail_0; + /* --- Force to be a multiple of @q@ --- */ - { - pgen pg; - int rc = pgen_create(&pg, q); - pgen_destroy(&pg); - if (rc == PGEN_COMPOSITE) { - if (proc) - fail = proc(DSAEV_FAILQ, q, arg); - if (!fail) - 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; - - rabin_create(&r, q); - for (i = 0; i < 18; i++) { - g = mprand(g, 8 * SHA_HASHSZ, gr, 1); - if (rabin_test(&r, g) == PGEN_COMPOSITE) - break; - if (proc && (fail = proc(DSAEV_PASSQ, q, arg)) != 0) - break; - } + 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 (fail) - goto fail_0; - if (i < 18) { - if (proc) - fail = proc(DSAEV_FAILQ, q, arg); - if (!fail) - fail = DSAEV_FAILQ; - goto fail_0; - } - if (proc && (fail = proc(DSAEV_GOODQ, q, arg)) != 0) - goto fail_0; - if (proc && (fail = proc(DSAEV_FINDP, 0, arg)) != 0) - goto fail_0; } - /* --- 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; - - rabin_create(&r, p); - if (proc && (fail = proc(DSAEV_TRYP, p, arg)) != 0) - break; - for (i = 0; i < 5; i++) { - g = mprand(g, 8 * (psz - b), gr, 1); - if (rabin_test(&r, g) == PGEN_COMPOSITE) - break; - if (proc && (fail = proc(DSAEV_PASSP, p, arg)) != 0) - break; - } - mp_drop(g); - rabin_destroy(&r); - if (fail) - break; - if (i < 5) { - if (proc && (fail = proc(DSAEV_FAILP, p, arg)) != 0) - break; - continue; - } - } - - /* --- It worked! --- */ - - if (proc) - fail = proc(DSAEV_GOODP, p, arg); - if (proc && !fail) - fail = proc(DSAEV_FINDG, 0, arg); - break; - } + return (rc); +} - free(pbuf); - mp_drop(q2); - mp_drop(ll); - if (j >= 4096 || fail) - goto fail_1; +/* --- @dsa_step@ --- */ + +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$% --- */ - - pp = mp_sub(MP_NEW, p, MP_ONE); - mp_div(&pp, 0, pp, q); - - /* --- 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 && (fail = proc(DSAEV_TRYH, &h, arg)) != 0) - break; - g = mpmont_exp(&mm, MP_NEW, &h, pp); - if (MP_CMP(g, !=, MP_ONE)) - break; - mp_drop(g); - if (proc && (fail = proc(DSAEV_FAILH, &h, arg)) != 0) - break; - } - mp_drop(pp); - mpmont_destroy(&mm); - if (fail) - goto fail_1; - if (i >= NPRIME) { - fail = DSAEV_FAILH; - goto fail_1; - } - } - if (proc && (fail = proc(DSAEV_GOODG, g, arg) != 0)) - goto fail_2; +/* --- @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. + * This can take quite a long time. + * + * 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. + */ - /* --- Return the important information that I succeeded --- */ +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; - dp->g = g; - dp->p = p; - dp->q = q; - mp_drop(s); - free(sbuf); - gr->ops->destroy(gr); - return (0); + /* --- Initialize the stepping context --- */ - /* --- Tidy up after failure --- */ - -fail_2: - mp_drop(g); -fail_1: - mp_drop(p); -fail_0: - mp_drop(q); - mp_drop(s); - free(sbuf); - gr->ops->destroy(gr); - return (-1); -} + s.r = dsarand_create(k, sz); + s.or = 1; -/*----- Test rig ----------------------------------------------------------*/ + /* --- Find @q@ --- */ -#ifdef TEST_RIG + 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; -static char baton[] = "/-\\|"; -static char *b = baton; + /* --- Find @p@ --- */ -static int 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; - } - return (0); + 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); + + /* --- Find @g@ --- * + * + * The division returns remainder 1. This doesn't matter. + */ + + 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; @@ -375,14 +231,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); @@ -397,7 +253,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) == 0); + assert(mparena_count(MPARENA_GLOBAL) == 1); /* Primorial! */ return (ok); } diff --git a/dsa.h b/dsa.h index ba3bad8..e8dee83 100644 --- a/dsa.h +++ b/dsa.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: dsa.h,v 1.3 1999/12/10 23:29:48 mdw Exp $ + * $Id: dsa.h,v 1.4 1999/12/22 15:52:44 mdw Exp $ * * Digital Signature Algorithm * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: dsa.h,v $ + * Revision 1.4 1999/12/22 15:52:44 mdw + * Reworking for new prime-search system. + * * Revision 1.3 1999/12/10 23:29:48 mdw * Change header file guard names. * @@ -62,28 +65,10 @@ #ifndef CATACOMB_MP_H # include "mp.h" #endif - -/*----- Event codes -------------------------------------------------------*/ - -enum { - DSAEV_OK, /* Everything is fine */ - - DSAEV_FINDQ, /* Search for a @q@ */ - DSAEV_FAILQ, /* @q@ failed primality test */ - DSAEV_PASSQ, /* @q@ passeed one iteration */ - DSAEV_GOODQ, /* Found good prime @q@ */ - - DSAEV_FINDP, /* Search for a @p@ */ - DSAEV_TRYP, /* Try prospective @p@ */ - DSAEV_FAILP, /* @p@ failed primality test */ - DSAEV_PASSP, /* @p@ passed one iteration */ - DSAEV_GOODP, /* @p@ accepted as being prime */ - - DSAEV_FINDG, /* Search for a @g@ */ - DSAEV_TRYH, /* Try prospective @h@ */ - DSAEV_FAILH, /* @h@ failed */ - DSAEV_GOODG /* @g@ accepted as a generator */ -}; + +#ifndef CATACOMB_PGEN_H +# include "pgen.h" +#endif /*----- Data structures ---------------------------------------------------*/ @@ -112,37 +97,55 @@ typedef struct dsa_sig { octet s[DSA_SIGLEN]; /* 160-bit @s@ value */ } dsa_sig; +/*----- DSA stepper -------------------------------------------------------*/ + +typedef struct dsa_stepctx { + + /* --- To be initialized by the client --- */ + + grand *r; /* Random number generator */ + mp *q; /* Force @p@ to be a multiple */ + size_t bits; /* Number of bits in the result */ + unsigned or; /* OR mask for low order bits */ +} dsa_stepctx; + +/* --- @dsa_step@ --- * + * + * The stepper chooses random integers, ensures that they are a multiple of + * @q@ (if specified), sets the low-order bits, and then tests for + * divisibility by small primes. + */ + +extern int dsa_step(int /*rq*/, pgen_event */*ev*/, void */*p*/); + /*----- Functions provided ------------------------------------------------*/ /* --- @dsa_seed@ --- * * * Arguments: @dsa_param *dp@ = where to store parameters - * @unsigned l@ = bitlength of @p@ in bits + * @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 - * @int (*proc)(int ev, mp *m, void *p)@ = event procedure * @size_t sz@ = size of key material + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for event handler * - * Returns: Zero if all went well, nonzero if key material was - * unsuitable (one of the @DSAEV@ codes). + * 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 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. It may abort the search at any time by returning - * a nonzero value, which is returned as the result of the - * function. + * This can take quite a long time. + * + * 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. */ -extern int dsa_seed(dsa_param */*dp*/, unsigned /*l*/, - const void */*k*/, size_t /*sz*/, - int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), - void */*p*/); +extern int dsa_seed(dsa_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/, + unsigned /*steps*/, const void */*k*/, size_t /*sz*/, + pgen_proc */*event*/, void */*ectx*/); /* --- @dsa_mksig@ --- * * -- 2.11.0