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

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