git.distorted.org.uk Git - u/mdw/catacomb/blob - dsa-gen.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsa-gen.c,v 1.3 1999/12/10 23:18:38 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.3  1999/12/10 23:18:38  mdw
  34  * Change interface for suggested destinations.
  35  *
  36  * Revision 1.2  1999/11/20 22:23:48  mdw
  37  * Allow event handler to abort the search process.
  38  *
  39  * Revision 1.1  1999/11/19 19:28:00  mdw
  40  * Implementation of the Digital Signature Algorithm.
  41  *
  42  */
  43
  44 /*----- Header files ------------------------------------------------------*/
  45
  46 #include <stdio.h>
  47 #include <stdlib.h>
  48
  49 #include "dsa.h"
  50 #include "fibrand.h"
  51 #include "mp.h"
  52 #include "mprand.h"
  53 #include "pgen.h"
  54 #include "rabin.h"
  55 #include "sha.h"
  56
  57 /*----- Main code ---------------------------------------------------------*/
  58
  59 /* --- @dsa_seed@ --- *
  60  *
  61  * Arguments:   @dsa_param *dp@ = where to store parameters
  62  *              @unsigned l@ = bitlength of @p@ in bits
  63  *              @const void *k@ = pointer to key material
  64  *              @size_t sz@ = size of key material
  65  *              @int (*proc)(int ev, mp *m, void *p)@ = event procedure
  66  *
  67  * Returns:     Zero if all went well, nonzero if key material was
  68  *              unsuitable (one of the @DSAEV@ codes).
  69  *
  70  * Use:         Generates the DSA shared parameters from a given seed value.
  71  *              This can take quite a long time.  The size of @p@ in bits is
  72  *              %$l = 512 + 64l'$%.  The DSA standard, FIPS 186, only allows
  73  *              %$0 \le l' \le 8$%.  This implementation has no such limit,
  74  *              although @l@ must be a multiple of 8.
  75  *
  76  *              The event procedure is informed of various happenings during
  77  *              generation.  It is passed an event code describing what
  78  *              happened, and a multiprecision number which pertains to the
  79  *              event code.  It may abort the search at any time by returning
  80  *              a nonzero value, which is returned as the result of the
  81  *              function.
  82  */
  83
  84 int dsa_seed(dsa_param *dp, unsigned l, const void *k, size_t sz,
  85              int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg)
  86 {
  87   mp *q, *p, *g;
  88   mp *s = mp_loadb(MP_NEW, k, sz);
  89   octet *sbuf = xmalloc(sz);
  90   grand *gr;
  91   int fail = 0;
  92
  93   l /= 8;
  94   gr = fibrand_create(LOAD32(k));
  95
  96   /* --- Generate @q@ --- */
  97
  98   {
  99     octet xbuf[SHA_HASHSZ], ybuf[SHA_HASHSZ];
 100     sha_ctx c;
 101     int i;
 102
 103     sha_init(&c);
 104     sha_hash(&c, k, sz);
 105     sha_done(&c, xbuf);
 106
 107     mpx_uaddn(s->v, s->vl, 1);
 108     mp_storeb(s, sbuf, sz);
 109     sha_init(&c);
 110     sha_hash(&c, sbuf, sz);
 111     sha_done(&c, ybuf);
 112
 113     for (i = 0; i < sizeof(xbuf); i++)
 114       xbuf[i] ^= ybuf[i];
 115     xbuf[0] |= 0x80;
 116     xbuf[SHA_HASHSZ - 1] |= 0x01;
 117     q = mp_loadb(MP_NEW, xbuf, sizeof(xbuf));
 118   }
 119
 120   /* --- Quick primality check --- */
 121
 122   if (proc && (fail = proc(DSAEV_FINDQ, 0, arg)) != 0)
 123     goto fail_0;
 124
 125   {
 126     pgen pg;
 127     int rc = pgen_create(&pg, q);
 128     pgen_destroy(&pg);
 129     if (rc == PGEN_COMPOSITE) {
 130       if (proc)
 131         fail = proc(DSAEV_FAILQ, q, arg);
 132       if (!fail)
 133         fail = DSAEV_FAILQ;
 134       goto fail_0;
 135     }
 136   }
 137
 138   /* --- Ensure that @q@ is prime --- *
 139    *
 140    * This requires 18 iterations, because the DSA spec is paranoid.
 141    * Fortunately, it doesn't actually take very long.
 142    */
 143
 144   {
 145     rabin r;
 146     int i;
 147     mp *g = MP_NEW;
 148
 149     rabin_create(&r, q);
 150     for (i = 0; i < 18; i++) {
 151       g = mprand(g, 8 * SHA_HASHSZ, gr, 1);
 152       if (rabin_test(&r, g) == PGEN_COMPOSITE)
 153         break;
 154       if (proc && (fail = proc(DSAEV_PASSQ, q, arg)) != 0)
 155         break;
 156     }
 157     mp_drop(g);
 158     rabin_destroy(&r);
 159     if (fail)
 160       goto fail_0;
 161     if (i < 18) {
 162       if (proc)
 163         fail = proc(DSAEV_FAILQ, q, arg);
 164       if (!fail)
 165         fail = DSAEV_FAILQ;
 166       goto fail_0;
 167     }
 168     if (proc && (fail = proc(DSAEV_GOODQ, q, arg)) != 0)
 169       goto fail_0;
 170     if (proc && (fail = proc(DSAEV_FINDP, 0, arg)) != 0)
 171       goto fail_0;
 172   }
 173
 174   /* --- Now generate @p@ --- *
 175    *
 176    * This is, unfortunately, rather more messy and complicated.
 177    */
 178
 179   {
 180     mp *q2 = mp_lsl(MP_NEW, q, 1);
 181     mp *ll = mp_lsl(MP_NEW, MP_ONE, l * 8 - 1);
 182     unsigned n = l / SHA_HASHSZ, b = l % SHA_HASHSZ;
 183     size_t psz = SHA_HASHSZ * (n + 1);
 184     octet *pbuf = xmalloc(psz);
 185     sha_ctx c;
 186     unsigned i, j;
 187
 188     /* --- Fiddle with the leftover bytes count --- */
 189
 190     b = SHA_HASHSZ - b;
 191
 192     /* --- Go round 4096 times trying different @p@ values --- */
 193
 194     p = MP_NEW;
 195     for (j = 0; j < 4096; j++) {
 196
 197       /* --- Build a prospective value of @p@ --- */
 198
 199       {
 200         octet *pp = pbuf + SHA_HASHSZ * n;
 201
 202         for (i = 0; i <= n; i++) {
 203           mpx_uaddn(s->v, s->vl, 1);
 204           mp_storeb(s, sbuf, sz);
 205           sha_init(&c);
 206           sha_hash(&c, sbuf, sz);
 207           sha_done(&c, pp);
 208           pp -= SHA_HASHSZ;
 209         }
 210
 211         pbuf[b] &= 0x7f;
 212         p = mp_loadb(p, pbuf + b, psz - b);
 213         p = mp_add(p, p, ll);
 214       }
 215
 216       /* --- Adjust @p@ so that %$p \bmod 2q = 1$% --- */
 217
 218       {
 219         mp *c = MP_NEW;
 220         mp_div(0, &c, p, q2);
 221         c = mp_sub(c, c, MP_ONE);
 222         p = mp_sub(p, p, c);
 223         mp_drop(c);
 224       }
 225
 226       /* --- Check that @p@ is large enough --- */
 227
 228       if (MP_CMP(p, <, ll))
 229         continue;
 230
 231       /* --- Run a simple primality test --- */
 232
 233       {
 234         pgen pg;
 235         int rc = pgen_create(&pg, p);
 236         pgen_destroy(&pg);
 237         if (rc == PGEN_COMPOSITE)
 238           continue;
 239       }
 240
 241       /* --- Run the Rabin-Miller test --- */
 242
 243       {
 244         rabin r;
 245         mp *g = MP_NEW;
 246
 247         rabin_create(&r, p);
 248         if (proc && (fail = proc(DSAEV_TRYP, p, arg)) != 0)
 249           break;
 250         for (i = 0; i < 5; i++) {
 251           g = mprand(g, 8 * (psz - b), gr, 1);
 252           if (rabin_test(&r, g) == PGEN_COMPOSITE)
 253             break;
 254           if (proc && (fail = proc(DSAEV_PASSP, p, arg)) != 0)
 255             break;
 256         }
 257         mp_drop(g);
 258         rabin_destroy(&r);
 259         if (fail)
 260           break;
 261         if (i < 5) {
 262           if (proc && (fail = proc(DSAEV_FAILP, p, arg)) != 0)
 263             break;
 264           continue;
 265         }
 266       }
 267
 268       /* --- It worked! --- */
 269
 270       if (proc)
 271         fail = proc(DSAEV_GOODP, p, arg);
 272       if (proc && !fail)
 273         fail = proc(DSAEV_FINDG, 0, arg);
 274       break;
 275     }
 276
 277     free(pbuf);
 278     mp_drop(q2);
 279     mp_drop(ll);
 280     if (j >= 4096 || fail)
 281       goto fail_1;
 282   }
 283
 284   /* --- Choose a generator of an order-%$q$% subgroup of %$Z^*_p$% --- */
 285
 286   {
 287     mp *pp = MP_NEW;
 288     mpw hw;
 289     mp h;
 290     unsigned i;
 291     mpmont mm;
 292
 293     /* --- Calculate %$p' = (p - 1)/q$% --- */
 294
 295     pp = mp_sub(MP_NEW, p, MP_ONE);
 296     mp_div(&pp, 0, pp, q);
 297
 298     /* --- Now find %$h$% where %$g = h^{p'} \bmod p \ne 1$% --- */
 299
 300     mp_build(&h, &hw, &hw + 1);
 301     mpmont_create(&mm, p);
 302     for (i = 0; i < NPRIME; i++) {
 303       hw = ptab[i];
 304       if (proc && (fail = proc(DSAEV_TRYH, &h, arg)) != 0)
 305         break;
 306       g = mpmont_exp(&mm, MP_NEW, &h, pp);
 307       if (MP_CMP(g, !=, MP_ONE))
 308         break;
 309       mp_drop(g);
 310       if (proc && (fail = proc(DSAEV_FAILH, &h, arg)) != 0)
 311         break;
 312     }
 313     mp_drop(pp);
 314     mpmont_destroy(&mm);
 315     if (fail)
 316       goto fail_1;
 317     if (i >= NPRIME) {
 318       fail = DSAEV_FAILH;
 319       goto fail_1;
 320     }
 321   }
 322   if (proc && (fail = proc(DSAEV_GOODG, g, arg) != 0))
 323     goto fail_2;
 324
 325   /* --- Return the important information that I succeeded --- */
 326
 327   dp->g = g;
 328   dp->p = p;
 329   dp->q = q;
 330   mp_drop(s);
 331   free(sbuf);
 332   gr->ops->destroy(gr);
 333   return (0);
 334
 335   /* --- Tidy up after failure --- */
 336
 337 fail_2:
 338   mp_drop(g);
 339 fail_1:
 340   mp_drop(p);
 341 fail_0:
 342   mp_drop(q);
 343   mp_drop(s);
 344   free(sbuf);
 345   gr->ops->destroy(gr);
 346   return (-1);
 347 }
 348
 349 /*----- Test rig ----------------------------------------------------------*/
 350
 351 #ifdef TEST_RIG
 352
 353 static char baton[] = "/-\\|";
 354 static char *b = baton;
 355
 356 static int event(int ev, mp *m, void *p)
 357 {
 358   if (ev == DSAEV_TRYP || ev == DSAEV_PASSP) {
 359     fputc(*b++, stdout);
 360     fputc('\b', stdout);
 361     fflush(stdout);
 362     if (!*b)
 363       b = baton;
 364   }
 365   return (0);
 366 }
 367
 368 static int verify(dstr *v)
 369 {
 370   mp *q = *(mp **)v[2].buf;
 371   mp *p = *(mp **)v[3].buf;
 372   mp *g = *(mp **)v[4].buf;
 373   dsa_param dp;
 374   unsigned l = *(unsigned *)v[1].buf;
 375   int ok = 1;
 376   int rc;
 377
 378   rc = dsa_seed(&dp, l, v[0].buf, v[0].len, event, 0);
 379   if (rc || MP_CMP(q, !=, dp.q) ||
 380       MP_CMP(p, !=, dp.p) || MP_CMP(g, !=, dp.g)) {
 381     fputs("\n*** gen failed", stderr);
 382     fputs("\nseed = ", stderr); type_hex.dump(&v[0], stderr);
 383     fprintf(stderr, "\nl = %u", l);
 384     fputs("\n   q = ", stderr); mp_writefile(q, stderr, 16);
 385     fputs("\n   p = ", stderr); mp_writefile(q, stderr, 16);
 386     fputs("\n   g = ", stderr); mp_writefile(g, stderr, 16);
 387     if (!rc) {
 388       fputs("\ndp.q = ", stderr); mp_writefile(dp.q, stderr, 16);
 389       fputs("\ndp.p = ", stderr); mp_writefile(dp.p, stderr, 16);
 390       fputs("\ndp.g = ", stderr); mp_writefile(dp.g, stderr, 16);
 391     }
 392     fputc('\n', stderr);
 393     ok = 0;
 394   }
 395
 396   mp_drop(q); mp_drop(p); mp_drop(g);
 397   if (!rc) {
 398     mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g);
 399   }
 400   assert(mparena_count(MPARENA_GLOBAL) == 0);
 401   return (ok);
 402 }
 403
 404 static test_chunk tests[] = {
 405   { "gen", verify,
 406     { &type_hex, &type_int, &type_mp, &type_mp, &type_mp, 0 }  },
 407   { 0, 0, { 0 } }
 408 };
 409
 410 int main(int argc, char *argv[])
 411 {
 412   sub_init();
 413   test_run(argc, argv, tests, SRCDIR "/tests/dsa");
 414   return (0);
 415 }
 416
 417 #endif
 418
 419 /*----- That's all, folks -------------------------------------------------*/