/* -*-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
*
/*----- 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.
*
#include <string.h>
#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
* 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 -------------------------------------------------*/
/* -*-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
*
/*----- 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.
*
#include <stdlib.h>
#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;
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);
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);
}
/* -*-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
*
/*----- 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.
*
#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 ---------------------------------------------------*/
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@ --- *
*
projects / u / mdw / catacomb / commitdiff