/* -*-c-*-
*
- * $Id: dsa-gen.c,v 1.2 1999/11/20 22:23:48 mdw Exp $
+ * $Id: dsa-gen.c,v 1.10 2004/04/08 01:36:15 mdw Exp $
*
* Generate DSA shared parameters
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
* 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: dsa-gen.c,v $
- * 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.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include <stdio.h>
#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 "rc4.h"
+#include "prim.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
- * @int (*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).
- *
- * 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);
- rc4_ctx rc4;
- int fail = 0;
-
- l /= 8;
- rc4_init(&rc4, k, sz);
-
- /* --- Generate @q@ --- */
-
- {
- 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 --- */
-
- {
- 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;
- }
- }
+ mp *m;
+ int rc;
- /* --- Ensure that @q@ is prime --- *
- *
- * This requires 18 iterations, because the DSA spec is paranoid.
- * Fortunately, it doesn't actually take very long.
- */
+ /* --- Load the new candidate --- */
- {
- 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 && (fail = proc(DSAEV_PASSQ, q, arg)) != 0)
- break;
- }
- 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 (d->seedbuf)
+ d->r->ops->misc(d->r, DSARAND_GETSEED, d->seedbuf);
+ m = mprand(ev->m, d->bits, d->r, 0);
- /* --- Now generate @p@ --- *
- *
- * This is, unfortunately, rather more messy and complicated.
- */
-
- {
- 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++) {
- rc4_encrypt(&rc4, 0, pbuf, psz - b);
- g = mp_loadb(g, pbuf, psz - b);
- 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);
- break;
- }
+ /* --- Force to be a multiple of @q@ --- */
- free(pbuf);
- mp_drop(q2);
- mp_drop(ll);
- if (j >= 4096 || fail)
- goto fail_1;
+ 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;
- /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */
+ /* --- Do the trial division --- */
- {
- mp *pp = MP_NEW;
- mpw hw;
- mp h;
- unsigned i;
- mpmont mm;
+ rc = pfilt_smallfactor(m);
+ d->count++;
- /* --- Calculate %$p' = (p - 1)/q$% --- */
+ /* --- Return the result --- */
- {
- mp *p1 = mp_sub(MP_NEW, p, MP_ONE);
- mp_div(&pp, 0, p1, q);
- mp_drop(p1);
- }
+ return (rc);
+}
- /* --- 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, &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);
- if (fail)
- goto fail_1;
- if (i >= NPRIME) {
- fail = DSAEV_FAILH;
- goto fail_1;
- }
+/* --- @dsa_step@ --- */
+
+int dsa_step(int rq, pgen_event *ev, void *p)
+{
+ dsa_stepctx *d = p;
+
+ switch (rq) {
+ case PGEN_BEGIN:
+ case PGEN_TRY:
+ return (next(ev, d));
+ case PGEN_DONE:
+ return (PGEN_DONE);
}
- if (proc && (fail = proc(DSAEV_GOODG, g, arg) != 0))
- goto fail_2;
+ return (PGEN_ABORT);
+}
- /* --- Return the important information that I succeeded --- */
+/*----- Glue code ---------------------------------------------------------*/
- dp->g = g;
- dp->p = p;
- dp->q = q;
- mp_drop(s);
- free(sbuf);
- return (0);
+/* --- @dsa_gen@ --- *
+ *
+ * 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
+ * @dsa_seed *ds@ = optional pointer for output seed information
+ * @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.
+ */
- /* --- Tidy up after failure --- */
-
-fail_2:
- mp_drop(g);
-fail_1:
- mp_drop(p);
-fail_0:
- mp_drop(q);
- mp_drop(s);
- free(sbuf);
- return (-1);
+int dsa_gen(dsa_param *dp, unsigned ql, unsigned pl, unsigned steps,
+ const void *k, size_t sz, dsa_seed *ds,
+ pgen_proc *event, void *ectx)
+{
+ dsa_stepctx s;
+ prim_ctx p;
+ int i;
+ rabin r;
+ mp *qc;
+
+ /* --- Initialize the stepping context --- */
+
+ s.r = dsarand_create(k, sz);
+
+ /* --- Find @q@ --- */
+
+ s.q = 0;
+ s.r->ops->misc(s.r, DSARAND_PASSES, 2);
+ s.bits = ql;
+ s.count = 0;
+ s.or = 1;
+ if (!ds)
+ s.seedbuf = 0;
+ else {
+ ds->sz = sz;
+ ds->p = s.seedbuf = xmalloc(sz);
+ }
+ 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;
+
+ /* --- Find @p@ --- */
+
+ s.count = ~0;
+ s.q = mp_lsl(MP_NEW, dp->q, 1);
+ s.r->ops->misc(s.r, DSARAND_PASSES, 1);
+ s.bits = pl;
+ s.seedbuf = 0;
+ 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);
+ if (ds)
+ ds->count = s.count;
+
+ /* --- 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.exp = 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);
+ if (ds)
+ xfree(ds->p);
+ return (PGEN_ABORT);
}
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
-static char baton[] = "/-\\|";
-static char *b = baton;
-
-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);
-}
-
static int verify(dstr *v)
{
- mp *q = *(mp **)v[2].buf;
- mp *p = *(mp **)v[3].buf;
- mp *g = *(mp **)v[4].buf;
+ mp *q = *(mp **)v[4].buf;
+ mp *p = *(mp **)v[5].buf;
+ mp *g = *(mp **)v[6].buf;
dsa_param dp;
- unsigned l = *(unsigned *)v[1].buf;
+ dsa_seed ds;
+ unsigned long l = *(unsigned long *)v[1].buf;
+ unsigned long n = *(unsigned long *)v[3].buf;
int ok = 1;
int rc;
+ keycheck kc;
+ keycheck_reportctx kcr;
- rc = dsa_seed(&dp, l, v[0].buf, v[0].len, event, 0);
- if (rc || MP_CMP(q, !=, dp.q) ||
- MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) {
+ rc = dsa_gen(&dp, 160, l, 16, v[0].buf, v[0].len, &ds, pgen_evspin, 0);
+ if (rc || ds.count != n || ds.sz != v[2].len ||
+ memcmp(ds.p, v[2].buf, v[2].len) != 0 ||
+ !MP_EQ(q, dp.q) || !MP_EQ(p, dp.p) || !MP_EQ(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 g = ", stderr); mp_writefile(g, stderr, 16);
+ fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
+ fprintf(stderr, "\nl = %lu", l);
+ fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
+ fprintf(stderr, "\ncount = %lu", n);
+ fputs("\n q = ", 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) {
+ dstr d;
+ d.buf = ds.p; d.len = ds.sz;
+ fputs("\nds.seed = ", stderr); type_hex.dump(&d, stderr);
+ fprintf(stderr, "\nds.count = %u", ds.count);
fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
ok = 0;
}
+ kcr.fp = stderr;
+ kcr.sev = KCSEV_ERR;
+ keycheck_init(&kc, keycheck_stdreport, &kcr);
+ if (!rc)
+ dsa_checkparam(&kc, &dp, &ds);
+ if (!keycheck_allclear(&kc, KCSEV_ERR)) {
+ fputs("\n*** gen failed check", stderr);
+ fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
+ fprintf(stderr, "\nl = %lu", l);
+ fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
+ fprintf(stderr, "\ncount = %lu", n);
+ fputs("\n q = ", stderr); mp_writefile(q, stderr, 16);
+ fputs("\n p = ", stderr); mp_writefile(p, stderr, 16);
+ fputs("\n g = ", stderr); mp_writefile(g, stderr, 16);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
mp_drop(q); mp_drop(p); mp_drop(g);
if (!rc) {
- mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
+ mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g); xfree(ds.p);
}
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
return (ok);
}
static test_chunk tests[] = {
{ "gen", verify,
- { &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 } },
+ { &type_hex, &type_ulong, &type_hex, &type_ulong,
+ &type_mp, &type_mp, &type_mp, 0 } },
{ 0, 0, { 0 } }
};
projects / u / mdw / catacomb / blobdiff