X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/pub/dsa-gen.c

diff --git a/pub/dsa-gen.c b/pub/dsa-gen.c
new file mode 100644
index 00000000..7c6c3ba8
--- /dev/null
+++ b/pub/dsa-gen.c
@@ -0,0 +1,299 @@
+/* -*-c-*-
+ *
+ * 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.
+ */
+
+/*----- 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 "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 --- */
+
+  if (d->seedbuf)
+    d->r->ops->misc(d->r, DSARAND_GETSEED, d->seedbuf);
+  m = mprand(ev->m, d->bits, d->r, 0);
+
+  /* --- 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 --- */
+
+  rc = pfilt_smallfactor(m);
+  d->count++;
+
+  /* --- 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:
+    case PGEN_TRY:
+      return (next(ev, d));
+    case PGEN_DONE:
+      return (PGEN_DONE);
+  }
+  return (PGEN_ABORT);
+}
+
+/*----- Glue code ---------------------------------------------------------*/
+
+/* --- @dsa_gen@ --- *
+ *
+ * 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
+ *		@dsa_seed *ds@ = optional pointer for output seed information
+ *		@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.
+ *
+ *		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 Diffie-Hellman parameter set,
+ *		but the generation algorithm is different.
+ *
+ *		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_gen(dsa_param *dp, unsigned ql, unsigned pl, unsigned steps,
+	    const void *k, size_t sz, dsa_seed *ds,
+	    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);
+
+  /* --- Find @q@ --- */
+
+  s.q = 0;
+  s.r->ops->misc(s.r, DSARAND_PASSES, 2);
+  s.bits = ql;
+  s.count = 0;
+  s.or = 1;
+  if (!ds)
+    s.seedbuf = 0;
+  else {
+    ds->sz = sz;
+    ds->p = s.seedbuf = xmalloc(sz);
+  }
+  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.count = ~0;
+  s.q = mp_lsl(MP_NEW, dp->q, 1);
+  s.r->ops->misc(s.r, DSARAND_PASSES, 1);
+  s.bits = pl;
+  s.seedbuf = 0;
+  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);
+  if (ds)
+    ds->count = s.count;
+
+  /* --- 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.exp = 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);
+  if (ds)
+    xfree(ds->p);
+  return (PGEN_ABORT);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static int verify(dstr *v)
+{
+  mp *q = *(mp **)v[4].buf;
+  mp *p = *(mp **)v[5].buf;
+  mp *g = *(mp **)v[6].buf;
+  dsa_param dp;
+  dsa_seed ds;
+  unsigned long l = *(unsigned long *)v[1].buf;
+  unsigned long n = *(unsigned long *)v[3].buf;
+  int ok = 1;
+  int rc;
+  keycheck kc;
+  keycheck_reportctx kcr;
+
+  rc = dsa_gen(&dp, 160, l, 16, v[0].buf, v[0].len, &ds, pgen_evspin, 0);
+  if (rc || ds.count != n || ds.sz != v[2].len ||
+      memcmp(ds.p, v[2].buf, v[2].len) != 0 ||
+      !MP_EQ(q, dp.q) || !MP_EQ(p, dp.p) || !MP_EQ(g, dp.g)) {
+    fputs("\n*** gen failed", stderr);
+    fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
+    fprintf(stderr, "\nl = %lu", l);
+    fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
+    fprintf(stderr, "\ncount = %lu", n);
+    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) {
+      dstr d;
+      d.buf = ds.p; d.len = ds.sz;
+      fputs("\nds.seed = ", stderr); type_hex.dump(&d, stderr);
+      fprintf(stderr, "\nds.count = %u", ds.count);
+      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;
+  }
+
+  kcr.fp = stderr;
+  kcr.sev = KCSEV_ERR;
+  keycheck_init(&kc, keycheck_stdreport, &kcr);
+  if (!rc)
+    dsa_checkparam(&kc, &dp, &ds);
+  if (!keycheck_allclear(&kc, KCSEV_ERR)) {
+    fputs("\n*** gen failed check", stderr);
+    fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
+    fprintf(stderr, "\nl = %lu", l);
+    fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
+    fprintf(stderr, "\ncount = %lu", n);
+    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);
+    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); xfree(ds.p);
+  }
+  assert(mparena_count(MPARENA_GLOBAL) == 0);
+  return (ok);
+}
+
+static test_chunk tests[] = {
+  { "gen", verify,
+    { &type_hex, &type_ulong, &type_hex, &type_ulong,
+      &type_mp, &type_mp, &type_mp, 0 }	 },
+  { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+  sub_init();
+  test_run(argc, argv, tests, SRCDIR "/t/dsa");
+  return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/