math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / pub / dsa-gen.c

/* -*-c-*-
 *
 * 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 "/t/dsa");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/