chiark - git - mdw - catacomb/blob - dsa-gen.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsa-gen.c,v 1.10 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Generate DSA shared parameters
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 #include "dsa.h"
  36 #include "dsarand.h"
  37 #include "fibrand.h"
  38 #include "mp.h"
  39 #include "mprand.h"
  40 #include "pgen.h"
  41 #include "prim.h"
  42 #include "sha.h"
  43
  44 /*----- The DSA stepper ---------------------------------------------------*/
  45
  46 /* --- @next@ --- *
  47  *
  48  * Arguments:   @pgen_event *ev@ = pointer to event block
  49  *              @dsa_stepctx *d@ = pointer to stepping context
  50  *
  51  * Returns:     A @PGEN@ result code.
  52  *
  53  * Use:         Steps the generator once, reads the result, and tests it.
  54  */
  55
  56 static int next(pgen_event *ev, dsa_stepctx *d)
  57 {
  58   mp *m;
  59   int rc;
  60
  61   /* --- Load the new candidate --- */
  62
  63   if (d->seedbuf)
  64     d->r->ops->misc(d->r, DSARAND_GETSEED, d->seedbuf);
  65   m = mprand(ev->m, d->bits, d->r, 0);
  66
  67   /* --- Force to be a multiple of @q@ --- */
  68
  69   if (d->q) {
  70     mp *r = MP_NEW;
  71     mp_div(0, &r, m, d->q);
  72     m = mp_sub(m, m, r);
  73     mp_drop(r);
  74   }
  75   m->v[0] |= d->or;
  76   ev->m = m;
  77
  78   /* --- Do the trial division --- */
  79
  80   rc = pfilt_smallfactor(m);
  81   d->count++;
  82
  83   /* --- Return the result --- */
  84
  85   return (rc);
  86 }
  87
  88 /* --- @dsa_step@ --- */
  89
  90 int dsa_step(int rq, pgen_event *ev, void *p)
  91 {
  92   dsa_stepctx *d = p;
  93
  94   switch (rq) {
  95     case PGEN_BEGIN:
  96     case PGEN_TRY:
  97       return (next(ev, d));
  98     case PGEN_DONE:
  99       return (PGEN_DONE);
 100   }
 101   return (PGEN_ABORT);
 102 }
 103
 104 /*----- Glue code ---------------------------------------------------------*/
 105
 106 /* --- @dsa_gen@ --- *
 107  *
 108  * Arguments:   @dsa_param *dp@ = where to store parameters
 109  *              @unsigned ql@ = length of @q@ in bits
 110  *              @unsigned pl@ = length of @p@ in bits
 111  *              @unsigned steps@ = number of steps to find @q@
 112  *              @const void *k@ = pointer to key material
 113  *              @size_t sz@ = size of key material
 114  *              @dsa_seed *ds@ = optional pointer for output seed information
 115  *              @pgen_proc *event@ = event handler function
 116  *              @void *ectx@ = argument for event handler
 117  *
 118  * Returns:     @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise.
 119  *
 120  * Use:         Generates the DSA shared parameters from a given seed value.
 121  *
 122  *              The parameters are a prime %$q$%, relatively small, and a
 123  *              large prime %$p = kq + 1$% for some %$k$%, together with a
 124  *              generator %$g$% of the cyclic subgroup of order %$q$%.  These
 125  *              are actually the same as the Diffie-Hellman parameter set,
 126  *              but the generation algorithm is different.
 127  *
 128  *              The algorithm used is a compatible extension of the method
 129  *              described in the DSA standard, FIPS 186.  The standard
 130  *              requires that %$q$% be 160 bits in size (i.e., @ql == 160@)
 131  *              and that the length of %$p$% be %$L = 512 + 64l$% for some
 132  *              %$l$%.  Neither limitation applies to this implementation.
 133  */
 134
 135 int dsa_gen(dsa_param *dp, unsigned ql, unsigned pl, unsigned steps,
 136             const void *k, size_t sz, dsa_seed *ds,
 137             pgen_proc *event, void *ectx)
 138 {
 139   dsa_stepctx s;
 140   prim_ctx p;
 141   int i;
 142   rabin r;
 143   mp *qc;
 144
 145   /* --- Initialize the stepping context --- */
 146
 147   s.r = dsarand_create(k, sz);
 148
 149   /* --- Find @q@ --- */
 150
 151   s.q = 0;
 152   s.r->ops->misc(s.r, DSARAND_PASSES, 2);
 153   s.bits = ql;
 154   s.count = 0;
 155   s.or = 1;
 156   if (!ds)
 157     s.seedbuf = 0;
 158   else {
 159     ds->sz = sz;
 160     ds->p = s.seedbuf = xmalloc(sz);
 161   }
 162   if ((dp->q = pgen("q", MP_NEW, MP_NEW, event, ectx, steps, dsa_step, &s,
 163                     rabin_iters(ql), pgen_test, &r)) == 0)
 164     goto fail_q;
 165
 166   /* --- Find @p@ --- */
 167
 168   s.count = ~0;
 169   s.q = mp_lsl(MP_NEW, dp->q, 1);
 170   s.r->ops->misc(s.r, DSARAND_PASSES, 1);
 171   s.bits = pl;
 172   s.seedbuf = 0;
 173   if ((dp->p = pgen("p", MP_NEW, MP_NEW, event, ectx, 4096, dsa_step, &s,
 174                     rabin_iters(pl), pgen_test, &r)) == 0)
 175     goto fail_p;
 176   mp_drop(s.q);
 177   if (ds)
 178     ds->count = s.count;
 179
 180   /* --- Find @g@ --- *
 181    *
 182    * The division returns remainder 1.  This doesn't matter.
 183    */
 184
 185   mpmont_create(&p.mm, dp->p);
 186   qc = MP_NEW; mp_div(&qc, 0, dp->p, dp->q);
 187   i = 0;
 188   p.exp = qc;
 189   p.n = 0;
 190   if ((dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i,
 191                     1, prim_test, &p)) == 0)
 192     goto fail_g;
 193
 194   /* --- Done --- */
 195
 196   mp_drop(qc);
 197   mpmont_destroy(&p.mm);
 198   s.r->ops->destroy(s.r);
 199   return (PGEN_DONE);
 200
 201   /* --- Tidy up when things go wrong --- */
 202
 203 fail_g:
 204   mp_drop(qc);
 205   mpmont_destroy(&p.mm);
 206 fail_p:
 207   mp_drop(dp->q);
 208   mp_drop(s.q);
 209 fail_q:
 210   s.r->ops->destroy(s.r);
 211   if (ds)
 212     xfree(ds->p);
 213   return (PGEN_ABORT);
 214 }
 215
 216 /*----- Test rig ----------------------------------------------------------*/
 217
 218 #ifdef TEST_RIG
 219
 220 static int verify(dstr *v)
 221 {
 222   mp *q = *(mp **)v[4].buf;
 223   mp *p = *(mp **)v[5].buf;
 224   mp *g = *(mp **)v[6].buf;
 225   dsa_param dp;
 226   dsa_seed ds;
 227   unsigned long l = *(unsigned long *)v[1].buf;
 228   unsigned long n = *(unsigned long *)v[3].buf;
 229   int ok = 1;
 230   int rc;
 231   keycheck kc;
 232   keycheck_reportctx kcr;
 233
 234   rc = dsa_gen(&dp, 160, l, 16, v[0].buf, v[0].len, &ds, pgen_evspin, 0);
 235   if (rc || ds.count != n || ds.sz != v[2].len ||
 236       memcmp(ds.p, v[2].buf, v[2].len) != 0 ||
 237       !MP_EQ(q, dp.q) || !MP_EQ(p, dp.p) || !MP_EQ(g, dp.g)) {
 238     fputs("\n*** gen failed", stderr);
 239     fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
 240     fprintf(stderr, "\nl = %lu", l);
 241     fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
 242     fprintf(stderr, "\ncount = %lu", n);
 243     fputs("\n   q = ", stderr); mp_writefile(q, stderr, 16);
 244     fputs("\n   p = ", stderr); mp_writefile(p, stderr, 16);
 245     fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
 246     if (!rc) {
 247       dstr d;
 248       d.buf = ds.p; d.len = ds.sz;
 249       fputs("\nds.seed = ", stderr); type_hex.dump(&d, stderr);
 250       fprintf(stderr, "\nds.count = %u", ds.count);
 251       fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
 252       fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
 253       fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
 254     }
 255     fputc('\n', stderr);
 256     ok = 0;
 257   }
 258
 259   kcr.fp = stderr;
 260   kcr.sev = KCSEV_ERR;
 261   keycheck_init(&kc, keycheck_stdreport, &kcr);
 262   if (!rc)
 263     dsa_checkparam(&kc, &dp, &ds);
 264   if (!keycheck_allclear(&kc, KCSEV_ERR)) {
 265     fputs("\n*** gen failed check", stderr);
 266     fputs("\nseed_in = ", stderr); type_hex.dump(&v[0], stderr);
 267     fprintf(stderr, "\nl = %lu", l);
 268     fputs("\nseed_out = ", stderr); type_hex.dump(&v[2], stderr);
 269     fprintf(stderr, "\ncount = %lu", n);
 270     fputs("\n   q = ", stderr); mp_writefile(q, stderr, 16);
 271     fputs("\n   p = ", stderr); mp_writefile(p, stderr, 16);
 272     fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
 273     fputc('\n', stderr);
 274     ok = 0;
 275   }
 276
 277   mp_drop(q); mp_drop(p); mp_drop(g);
 278   if (!rc) {
 279     mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g); xfree(ds.p);
 280   }
 281   assert(mparena_count(MPARENA_GLOBAL) == 0);
 282   return (ok);
 283 }
 284
 285 static test_chunk tests[] = {
 286   { "gen", verify,
 287     { &type_hex, &type_ulong, &type_hex, &type_ulong,
 288       &type_mp, &type_mp, &type_mp, 0 }  },
 289   { 0, 0, { 0 } }
 290 };
 291
 292 int main(int argc, char *argv[])
 293 {
 294   sub_init();
 295   test_run(argc, argv, tests, SRCDIR "/tests/dsa");
 296   return (0);
 297 }
 298
 299 #endif
 300
 301 /*----- That's all, folks -------------------------------------------------*/