+++ /dev/null
-/* -*-c-*-
- *
- * $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 --------------------------------------------------*
- *
- * 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.
- */
-
-/*----- 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 "prim.h"
-#include "sha.h"
-
-/*----- The DSA stepper ---------------------------------------------------*/
-
-/* --- @next@ --- *
- *
- * Arguments: @pgen_event *ev@ = pointer to event block
- * @dsa_stepctx *d@ = pointer to stepping context
- *
- * Returns: A @PGEN@ result code.
- *
- * Use: Steps the generator once, reads the result, and tests it.
- */
-
-static int next(pgen_event *ev, dsa_stepctx *d)
-{
- mp *m;
- int rc;
-
- /* --- Load the new candidate --- */
-
- if (d->seedbuf)
- d->r->ops->misc(d->r, DSARAND_GETSEED, d->seedbuf);
- m = mprand(ev->m, d->bits, d->r, 0);
-
- /* --- Force to be a multiple of @q@ --- */
-
- 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;
-
- /* --- Do the trial division --- */
-
- rc = pfilt_smallfactor(m);
- d->count++;
-
- /* --- Return the result --- */
-
- return (rc);
-}
-
-/* --- @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);
- }
- return (PGEN_ABORT);
-}
-
-/*----- Glue code ---------------------------------------------------------*/
-
-/* --- @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.
- */
-
-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 int verify(dstr *v)
-{
- mp *q = *(mp **)v[4].buf;
- mp *p = *(mp **)v[5].buf;
- mp *g = *(mp **)v[6].buf;
- dsa_param dp;
- 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_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_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);
- }
- fputc('\n', stderr);
- 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); xfree(ds.p);
- }
- assert(mparena_count(MPARENA_GLOBAL) == 0);
- return (ok);
-}
-
-static test_chunk tests[] = {
- { "gen", verify,
- { &type_hex, &type_ulong, &type_hex, &type_ulong,
- &type_mp, &type_mp, &type_mp, 0 } },
- { 0, 0, { 0 } }
-};
-
-int main(int argc, char *argv[])
-{
- sub_init();
- test_run(argc, argv, tests, SRCDIR "/tests/dsa");
- return (0);
-}
-
-#endif
-
-/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff