Rearrange the file tree.

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

diff --git a/pub/dh-gen.c b/pub/dh-gen.c
new file mode 100644 (file)
index 0000000..17b34f6
--- /dev/null
+++ b/pub/dh-gen.c
@@ -0,0 +1,161 @@
+/* -*-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,
+                rabin_iters(pl), pgen_simultest, &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;
+    rabin rb;
+    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,
+                rabin_iters(ql), pgen_test, &rb);
+    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,
+                rabin_iters(pl), pgen_test, &rb);
+    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 -------------------------------------------------*/