+/* -*-c-*-
+ *
+ * $Id: dh-prime.c,v 1.1 1999/11/20 22:24:44 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.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 "mp.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;
+ mpw bw;
+ mp b;
+
+ /* --- Initialize prime generators --- */
+
+ rc_q = pgen_create(&pq, s);
+ rc_p = pgen_muladd(&pp, &pq, 2, 1);
+ mp_build(&b, &bw, &bw + 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++) {
+ bw = ptab[i];
+ 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);
+ return (p);
+ }
+
+ /* --- Failure --- */
+
+fail:
+ pgen_destroy(&pq);
+ pgen_destroy(&pp);
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/