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

   1 /* -*-c-*-
   2  *
   3  * $Id: dsa-gen.c,v 1.6 2000/07/29 10:00:14 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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: dsa-gen.c,v $
  33  * Revision 1.6  2000/07/29 10:00:14  mdw
  34  * Rename `dsa_seed' to `dsa_gen' for consistency with other parameter-
  35  * generation interfaces.
  36  *
  37  * Revision 1.5  2000/02/12 18:21:02  mdw
  38  * Overhaul of key management (again).
  39  *
  40  * Revision 1.4  1999/12/22 15:52:44  mdw
  41  * Reworking for new prime-search system.
  42  *
  43  * Revision 1.3  1999/12/10 23:18:38  mdw
  44  * Change interface for suggested destinations.
  45  *
  46  * Revision 1.2  1999/11/20 22:23:48  mdw
  47  * Allow event handler to abort the search process.
  48  *
  49  * Revision 1.1  1999/11/19 19:28:00  mdw
  50  * Implementation of the Digital Signature Algorithm.
  51  *
  52  */
  53
  54 /*----- Header files ------------------------------------------------------*/
  55
  56 #include <stdio.h>
  57 #include <stdlib.h>
  58
  59 #include "dsa.h"
  60 #include "dsarand.h"
  61 #include "fibrand.h"
  62 #include "mp.h"
  63 #include "mprand.h"
  64 #include "pgen.h"
  65 #include "prim.h"
  66 #include "primorial.h"
  67 #include "sha.h"
  68
  69 /*----- The DSA stepper ---------------------------------------------------*/
  70
  71 /* --- @next@ --- *
  72  *
  73  * Arguments:   @pgen_event *ev@ = pointer to event block
  74  *              @dsa_stepctx *d@ = pointer to stepping context
  75  *
  76  * Returns:     A @PGEN@ result code.
  77  *
  78  * Use:         Steps the generator once, reads the result, and tests it.
  79  */
  80
  81 static int next(pgen_event *ev, dsa_stepctx *d)
  82 {
  83   mp *m;
  84   int rc;
  85
  86   /* --- Load the new candidate --- */
  87
  88   m = mprand(ev->m, d->bits, d->r, d->or);
  89
  90   /* --- Force to be a multiple of @q@ --- */
  91
  92   if (d->q) {
  93     mp *r = MP_NEW;
  94     mp_div(0, &r, m, d->q);
  95     m = mp_sub(m, m, r);
  96     mp_drop(r);
  97   }
  98   m->v[0] |= d->or;
  99   ev->m = m;
 100
 101   /* --- Do the trial division --- */
 102
 103   {
 104     mp *g = MP_NEW;
 105     mp_gcd(&g, 0, 0, m, primorial);
 106     if (MP_CMP(g, ==, MP_ONE) || MP_CMP(g, ==, m))
 107       rc = PGEN_TRY;
 108     else
 109       rc = PGEN_FAIL;
 110     mp_drop(g);
 111   }
 112
 113   /* --- Return the result --- */
 114
 115   return (rc);
 116 }
 117
 118 /* --- @dsa_step@ --- */
 119
 120 int dsa_step(int rq, pgen_event *ev, void *p)
 121 {
 122   dsa_stepctx *d = p;
 123
 124   switch (rq) {
 125     case PGEN_BEGIN:
 126       primorial_setup();
 127     case PGEN_TRY:
 128       return (next(ev, d));
 129     case PGEN_DONE:
 130       return (PGEN_DONE);
 131   }
 132   return (PGEN_ABORT);
 133 }
 134
 135 /*----- Glue code ---------------------------------------------------------*/
 136
 137 /* --- @dsa_gen@ --- *
 138  *
 139  * Arguments:   @dsa_param *dp@ = where to store parameters
 140  *              @unsigned ql@ = length of @q@ in bits
 141  *              @unsigned pl@ = length of @p@ in bits
 142  *              @unsigned steps@ = number of steps to find @q@
 143  *              @const void *k@ = pointer to key material
 144  *              @size_t sz@ = size of key material
 145  *              @pgen_proc *event@ = event handler function
 146  *              @void *ectx@ = argument for event handler
 147  *
 148  * Returns:     @PGEN_DONE@ if everything worked ok; @PGEN_ABORT@ otherwise.
 149  *
 150  * Use:         Generates the DSA shared parameters from a given seed value.
 151  *
 152  *              The parameters are a prime %$q$%, relatively small, and a
 153  *              large prime %$p = kq + 1$% for some %$k$%, together with a
 154  *              generator %$g$% of the cyclic subgroup of order %$q$%.  These
 155  *              are actually the same as the Diffie-Hellman parameter set,
 156  *              but the generation algorithm is different.
 157  *
 158  *              The algorithm used is a compatible extension of the method
 159  *              described in the DSA standard, FIPS 186.  The standard
 160  *              requires that %$q$% be 160 bits in size (i.e., @ql == 160@)
 161  *              and that the length of %$p$% be %$L = 512 + 64l$% for some
 162  *              %$l$%.  Neither limitation applies to this implementation.
 163  */
 164
 165 int dsa_gen(dsa_param *dp, unsigned ql, unsigned pl, unsigned steps,
 166             const void *k, size_t sz, pgen_proc *event, void *ectx)
 167 {
 168   dsa_stepctx s;
 169   prim_ctx p;
 170   int i;
 171   rabin r;
 172   mp *qc;
 173
 174   /* --- Initialize the stepping context --- */
 175
 176   s.r = dsarand_create(k, sz);
 177   s.or = 1;
 178
 179   /* --- Find @q@ --- */
 180
 181   s.q = 0;
 182   s.r->ops->misc(s.r, DSARAND_PASSES, 2);
 183   s.bits = ql;
 184   if ((dp->q = pgen("q", MP_NEW, MP_NEW, event, ectx, steps, dsa_step, &s,
 185                     rabin_iters(ql), pgen_test, &r)) == 0)
 186     goto fail_q;
 187
 188   /* --- Find @p@ --- */
 189
 190   s.q = mp_lsl(MP_NEW, dp->q, 1);
 191   s.r->ops->misc(s.r, DSARAND_PASSES, 1);
 192   s.bits = pl;
 193   if ((dp->p = pgen("p", MP_NEW, MP_NEW, event, ectx, 4096, dsa_step, &s,
 194                     rabin_iters(pl), pgen_test, &r)) == 0)
 195     goto fail_p;
 196   mp_drop(s.q);
 197
 198   /* --- Find @g@ --- *
 199    *
 200    * The division returns remainder 1.  This doesn't matter.
 201    */
 202
 203   mpmont_create(&p.mm, dp->p);
 204   qc = MP_NEW; mp_div(&qc, 0, dp->p, dp->q);
 205   i = 0;
 206   p.exp = qc;
 207   p.n = 0;
 208   if ((dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i,
 209                     1, prim_test, &p)) == 0)
 210     goto fail_g;
 211
 212   /* --- Done --- */
 213
 214   mp_drop(qc);
 215   mpmont_destroy(&p.mm);
 216   s.r->ops->destroy(s.r);
 217   return (PGEN_DONE);
 218
 219   /* --- Tidy up when things go wrong --- */
 220
 221 fail_g:
 222   mp_drop(qc);
 223   mpmont_destroy(&p.mm);
 224 fail_p:
 225   mp_drop(dp->q);
 226   mp_drop(s.q);
 227 fail_q:
 228   s.r->ops->destroy(s.r);
 229   return (PGEN_ABORT);
 230 }
 231
 232 /*----- Test rig ----------------------------------------------------------*/
 233
 234 #ifdef TEST_RIG
 235
 236 static int verify(dstr *v)
 237 {
 238   mp *q = *(mp **)v[2].buf;
 239   mp *p = *(mp **)v[3].buf;
 240   mp *g = *(mp **)v[4].buf;
 241   dsa_param dp;
 242   unsigned l = *(unsigned *)v[1].buf;
 243   int ok = 1;
 244   int rc;
 245
 246   rc = dsa_gen(&dp, 160, l, 1, v[0].buf, v[0].len, pgen_evspin, 0);
 247   if (rc || MP_CMP(q, !=, dp.q) ||
 248       MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) {
 249     fputs("\n*** gen failed", stderr);
 250     fputs("\nseed = ", stderr); type_hex.dump(&v[0], stderr);
 251     fprintf(stderr, "\nl = %u", l);
 252     fputs("\n   q = ", stderr); mp_writefile(q, stderr, 16);
 253     fputs("\n   p = ", stderr); mp_writefile(p, stderr, 16);
 254     fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
 255     if (!rc) {
 256       fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
 257       fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
 258       fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
 259     }
 260     fputc('\n', stderr);
 261     ok = 0;
 262   }
 263
 264   mp_drop(q); mp_drop(p); mp_drop(g);
 265   if (!rc) {
 266     mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
 267   }
 268   assert(mparena_count(MPARENA_GLOBAL) == 1); /* Primorial! */
 269   return (ok);
 270 }
 271
 272 static test_chunk tests[] = {
 273   { "gen", verify,
 274     { &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 }  },
 275   { 0, 0, { 0 } }
 276 };
 277
 278 int main(int argc, char *argv[])
 279 {
 280   sub_init();
 281   test_run(argc, argv, tests, SRCDIR "/tests/dsa");
 282   return (0);
 283 }
 284
 285 #endif
 286
 287 /*----- That's all, folks -------------------------------------------------*/