prime generation: Deploy the new Baillie--PSW testers.

[catacomb] / pub / dh-gen.c

/* -*-c-*-
 *
 * Generate Diffie-Hellman 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 <mLib/macros.h>

#include "dh.h"
#include "grand.h"
#include "mp.h"
#include "mpmont.h"
#include "mprand.h"
#include "pfilt.h"
#include "pgen.h"
#include "prim.h"
#include "rabin.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @dh_gen@ --- *
 *
 * Arguments:	@dh_param *dp@ = pointer to output parameter block
 *		@unsigned ql@ = length of %$q$% in bits, or zero
 *		@unsigned pl@ = length of %$p$% in bits
 *		@unsigned steps@ = number of steps to go
 *		@grand *r@ = random number source
 *		@pgen_proc *event@ = event handler function
 *		@void *ectx@ = argument for the event handler
 *
 * Returns:	@PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
 *
 * Use:		Generates Diffie-Hellman parameters.
 *
 *		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 DSA parameter set, but the
 *		generation algorithm is different.  Also, if @ql@ is zero,
 *		this algorithm forces %$k = 2$%, and chooses %$g = 4$%.  Make
 *		sure you have something interesting to do if you choose this
 *		option.
 */

int dh_gen(dh_param *dp, unsigned ql, unsigned pl, unsigned steps, grand *r,
	   pgen_proc *event, void *ectx)
{
  /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */

  if (!ql) {
    pgen_simulprime sp[2];
    pgen_simulctx ss;

    mp *m = mprand(MP_NEW, pl - 1, r, 1);
    ss.step = MP_TWO;
    sp[0].mul = MP_ONE; sp[0].add = MP_ZERO; sp[0].f = 0;
    sp[1].mul = MP_TWO; sp[1].add = MP_ONE; sp[1].f = PGENF_KEEP;
    ss.v = sp; ss.n = N(sp);
    dp->q = pgen("p", MP_NEW, m, event, ectx, steps, pgen_simulstep, &ss,
		 PGEN_BAILLIEPSWNTESTS, pgen_simulbailliepswtest, &ss);
    mp_drop(m);
    if (!dp->q) {
      mp_drop(sp[1].u.x);
      return (PGEN_ABORT);
    }
    dp->p = sp[1].u.x;
    dp->g = MP_FOUR;
    return (PGEN_DONE);
  }

  /* --- Otherwise the job is much simpler --- *
   *
   * But doesn't look it...
   */

  else {
    pgen_filterctx c;
    pgen_jumpctx j;
    prim_ctx p;
    int i;
    mp *m = MP_NEW;
    mp *x, *y;

    /* --- Generate @q@ first --- */

    c.step = 2;
    m = mprand(MP_NEW, ql, r, 1);
    dp->q = pgen("q", MP_NEW, m, event, ectx, steps, pgen_filter, &c,
		 PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0);
    if (!dp->q)
      goto fail_q;

    /* --- Now pick a suitable @p@ --- */

    m = mp_lsl(m, dp->q, 1);
    x = mprand(MP_NEW, pl, r, 0);
    y = MP_NEW; mp_div(0, &y, x, m);
    x = mp_sub(x, x, y);
    x = mp_add(x, x, MP_ONE);
    mp_drop(y);
    pfilt_create(&c.f, m);
    j.j = &c.f;
    dp->p = pgen("p", MP_NEW, x, event, ectx, steps, pgen_jump, &j,
		 PGEN_BAILLIEPSWNTESTS, pgen_bailliepswtest, 0);
    pfilt_destroy(&c.f);
    mp_drop(x);
    if (!dp->p)
      goto fail_p;

    /* --- And finally a suitable @g@ --- */

    mpmont_create(&p.mm, dp->p);
    mp_div(&m, 0, dp->p, dp->q);
    i = 0;
    p.exp = m;
    p.n = 0;
    dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i,
		 1, prim_test, &p);
    mpmont_destroy(&p.mm);
    if (!dp->g)
      goto fail_g;
    mp_drop(m);
    return (PGEN_DONE);

    /* --- Tidy up --- */

  fail_g:
    mp_drop(dp->q);
  fail_q:
    mp_drop(dp->p);
  fail_p:
    mp_drop(m);
    return (PGEN_ABORT);
  }
}

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