More changes. Still embryonic.

[u/mdw/catacomb] / dh-prime.c

/* -*-c-*-
 *
 * $Id: dh-prime.c,v 1.2 1999/12/10 23:18:38 mdw Exp $
 *
 * Generate (safe) Diffie-Hellman primes
 *
 * (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: dh-prime.c,v $
 * Revision 1.2  1999/12/10 23:18:38  mdw
 * Change interface for suggested destinations.
 *
 * Revision 1.1  1999/11/20 22:24:44  mdw
 * Add Diffie-Hellman support.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dh.h"
#include "fibrand.h"
#include "mp.h"
#include "mprand.h"
#include "pgen.h"
#include "rabin.h"

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

/* --- @dh_prime@ --- *
 *
 * Arguments:	@mp *s@ = start point for search (must be odd)
 *		@size_t n@ = number of concerted attempts to make, or zero
 *		@void (*proc)(int ev, void *p)@ = event handler
 *		@void *p@ = argument for event handler
 *
 * Returns:	A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%.
 *
 * Use:		Finds a safe prime by sequential search from a given starting
 *		point.  If it fails, a null pointer is returned.
 *
 *		The event handler is informed of the progress of the search.
 *		It may abort the search at any time by returning a nonzero
 *		value.
 */

mp *dh_prime(mp *s, size_t n,
	     int (*proc)(int /*ev*/, void */*p*/), void *arg)
{
  pgen pq, pp;
  int rc_q, rc_p;
  grand *gr = fibrand_create(0);
  mp *b = MP_NEW;
  size_t sz = mp_bits(s);

  /* --- Initialize prime generators --- */

  rc_q = pgen_create(&pq, s);
  rc_p = pgen_muladd(&pp, &pq, 2, 1);

  /* --- Now step along until something crops up --- */

  for (;;) {
    rabin rq, rp;
    int i;

    /* --- Don't do expensive testing unless necessary --- */

    if (rc_q == PGEN_PRIME && rc_p == PGEN_PRIME)
      break;
    if (rc_q == PGEN_COMPOSITE || rc_p == PGEN_COMPOSITE)
      goto next;

    /* --- Initialize Rabin-Miller contexts --- */

    if (rc_q == PGEN_MAYBE)
      rabin_create(&rq, pq.m);
    if (rc_p == PGEN_MAYBE)
      rabin_create(&rp, pp.m);

    /* --- Now run tests on each in turn --- *
     *
     * On the sorts of modulus sizes which work well in discrete log
     * problems, five tests should be sufficient.
     */

    for (i = 0; i < 5; i++) {
      b = mprand(b, sz, gr, 1);
      if (rc_q == PGEN_MAYBE &&
	  (rc_q = rabin_test(&rq, b)) == PGEN_COMPOSITE)
	break;
      if (rc_p == PGEN_MAYBE &&
	  (rc_p = rabin_test(&rp, b)) == PGEN_COMPOSITE)
	break;
      if (proc && proc(DHEV_PASS, arg))
	break;
    }
    if (rc_q != PGEN_PRIME)
      rabin_destroy(&rq);
    if (rc_p != PGEN_PRIME)
      rabin_destroy(&rp);

    /* --- If the tests passed, accept the numbers --- */

    if (i >= 5)
      break;
    if (proc && proc(DHEV_FAIL, arg))
      goto fail;
    if (n) {
      n--;
      if (!n)
	goto fail;
    }

    /* --- Step the contexts on --- */

  next:
    rc_q = pgen_step(&pq, 2);
    rc_p = pgen_step(&pp, 4);
  }

  /* --- Return a result --- */

  {
    mp *p = MP_COPY(pp.m);
    pgen_destroy(&pq);
    pgen_destroy(&pp);
    mp_drop(b);
    gr->ops->destroy(gr);
    return (p);
  }

  /* --- Failure --- */

fail:
  pgen_destroy(&pq);
  pgen_destroy(&pp);
  mp_drop(b);
  gr->ops->destroy(gr);
  return (0);
}

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