Find `safe' primes (i.e., %$p = 2q + 1$%).

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

/* -*-c-*-
 *
 * $Id: dsa-gen.c,v 1.4 1999/12/22 15:52:44 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.
 */

/*----- 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.
 *
 * 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 "prim.h"
#include "primorial.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 --- */

  m = mprand(ev->m, d->bits, d->r, d->or);

  /* --- 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 --- */

  {
    mp *g = MP_NEW;
    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);
  }

  /* --- 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:
      primorial_setup();
    case PGEN_TRY:
      return (next(ev, d));
    case PGEN_DONE:
      return (PGEN_DONE);
  }
  return (PGEN_ABORT);
}

/*----- Glue code ---------------------------------------------------------*/

/* --- @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.
 */

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;

  /* --- Initialize the stepping context --- */

  s.r = dsarand_create(k, sz);
  s.or = 1;

  /* --- Find @q@ --- */

  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;

  /* --- Find @p@ --- */

  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;
  mp *p = *(mp **)v[3].buf;
  mp *g = *(mp **)v[4].buf;
  dsa_param dp;
  unsigned l = *(unsigned *)v[1].buf;
  int ok = 1;
  int rc;

  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(p, stderr, 16);
    fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
    if (!rc) {
      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;
  }

  mp_drop(q); mp_drop(p); mp_drop(g);
  if (!rc) {
    mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
  }
  assert(mparena_count(MPARENA_GLOBAL) == 1); /* Primorial! */
  return (ok);
}

static test_chunk tests[] = {
  { "gen", verify,
    { &type_hex, &type_int, &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 -------------------------------------------------*/