lib/openssl/crypto/dsa/dsa_gen.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /*
  11  * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
  12  * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
  13  * 180-1)
  14  */
  15 #define xxxHASH    EVP_sha1()
  16
  17 #include <openssl/opensslconf.h>
  18 #include <stdio.h>
  19 #include "internal/cryptlib.h"
  20 #include <openssl/evp.h>
  21 #include <openssl/bn.h>
  22 #include <openssl/rand.h>
  23 #include <openssl/sha.h>
  24 #include "dsa_locl.h"
  25
  26 int DSA_generate_parameters_ex(DSA *ret, int bits,
  27                                const unsigned char *seed_in, int seed_len,
  28                                int *counter_ret, unsigned long *h_ret,
  29                                BN_GENCB *cb)
  30 {
  31     if (ret->meth->dsa_paramgen)
  32         return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
  33                                        counter_ret, h_ret, cb);
  34     else {
  35         const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1();
  36         size_t qbits = EVP_MD_size(evpmd) * 8;
  37
  38         return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
  39                                     seed_in, seed_len, NULL, counter_ret,
  40                                     h_ret, cb);
  41     }
  42 }
  43
  44 int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
  45                          const EVP_MD *evpmd, const unsigned char *seed_in,
  46                          size_t seed_len, unsigned char *seed_out,
  47                          int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
  48 {
  49     int ok = 0;
  50     unsigned char seed[SHA256_DIGEST_LENGTH];
  51     unsigned char md[SHA256_DIGEST_LENGTH];
  52     unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
  53     BIGNUM *r0, *W, *X, *c, *test;
  54     BIGNUM *g = NULL, *q = NULL, *p = NULL;
  55     BN_MONT_CTX *mont = NULL;
  56     int i, k, n = 0, m = 0, qsize = qbits >> 3;
  57     int counter = 0;
  58     int r = 0;
  59     BN_CTX *ctx = NULL;
  60     unsigned int h = 2;
  61
  62     if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
  63         qsize != SHA256_DIGEST_LENGTH)
  64         /* invalid q size */
  65         return 0;
  66
  67     if (evpmd == NULL)
  68         /* use SHA1 as default */
  69         evpmd = EVP_sha1();
  70
  71     if (bits < 512)
  72         bits = 512;
  73
  74     bits = (bits + 63) / 64 * 64;
  75
  76     if (seed_in != NULL) {
  77         if (seed_len < (size_t)qsize)
  78             return 0;
  79         if (seed_len > (size_t)qsize) {
  80             /* Only consume as much seed as is expected. */
  81             seed_len = qsize;
  82         }
  83         memcpy(seed, seed_in, seed_len);
  84     }
  85
  86     if ((mont = BN_MONT_CTX_new()) == NULL)
  87         goto err;
  88
  89     if ((ctx = BN_CTX_new()) == NULL)
  90         goto err;
  91
  92     BN_CTX_start(ctx);
  93
  94     r0 = BN_CTX_get(ctx);
  95     g = BN_CTX_get(ctx);
  96     W = BN_CTX_get(ctx);
  97     q = BN_CTX_get(ctx);
  98     X = BN_CTX_get(ctx);
  99     c = BN_CTX_get(ctx);
 100     p = BN_CTX_get(ctx);
 101     test = BN_CTX_get(ctx);
 102
 103     if (test == NULL)
 104         goto err;
 105
 106     if (!BN_lshift(test, BN_value_one(), bits - 1))
 107         goto err;
 108
 109     for (;;) {
 110         for (;;) {              /* find q */
 111             int use_random_seed = (seed_in == NULL);
 112
 113             /* step 1 */
 114             if (!BN_GENCB_call(cb, 0, m++))
 115                 goto err;
 116
 117             if (use_random_seed) {
 118                 if (RAND_bytes(seed, qsize) <= 0)
 119                     goto err;
 120             } else {
 121                 /* If we come back through, use random seed next time. */
 122                 seed_in = NULL;
 123             }
 124             memcpy(buf, seed, qsize);
 125             memcpy(buf2, seed, qsize);
 126             /* precompute "SEED + 1" for step 7: */
 127             for (i = qsize - 1; i >= 0; i--) {
 128                 buf[i]++;
 129                 if (buf[i] != 0)
 130                     break;
 131             }
 132
 133             /* step 2 */
 134             if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
 135                 goto err;
 136             if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
 137                 goto err;
 138             for (i = 0; i < qsize; i++)
 139                 md[i] ^= buf2[i];
 140
 141             /* step 3 */
 142             md[0] |= 0x80;
 143             md[qsize - 1] |= 0x01;
 144             if (!BN_bin2bn(md, qsize, q))
 145                 goto err;
 146
 147             /* step 4 */
 148             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 149                                         use_random_seed, cb);
 150             if (r > 0)
 151                 break;
 152             if (r != 0)
 153                 goto err;
 154
 155             /* do a callback call */
 156             /* step 5 */
 157         }
 158
 159         if (!BN_GENCB_call(cb, 2, 0))
 160             goto err;
 161         if (!BN_GENCB_call(cb, 3, 0))
 162             goto err;
 163
 164         /* step 6 */
 165         counter = 0;
 166         /* "offset = 2" */
 167
 168         n = (bits - 1) / 160;
 169
 170         for (;;) {
 171             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 172                 goto err;
 173
 174             /* step 7 */
 175             BN_zero(W);
 176             /* now 'buf' contains "SEED + offset - 1" */
 177             for (k = 0; k <= n; k++) {
 178                 /*
 179                  * obtain "SEED + offset + k" by incrementing:
 180                  */
 181                 for (i = qsize - 1; i >= 0; i--) {
 182                     buf[i]++;
 183                     if (buf[i] != 0)
 184                         break;
 185                 }
 186
 187                 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
 188                     goto err;
 189
 190                 /* step 8 */
 191                 if (!BN_bin2bn(md, qsize, r0))
 192                     goto err;
 193                 if (!BN_lshift(r0, r0, (qsize << 3) * k))
 194                     goto err;
 195                 if (!BN_add(W, W, r0))
 196                     goto err;
 197             }
 198
 199             /* more of step 8 */
 200             if (!BN_mask_bits(W, bits - 1))
 201                 goto err;
 202             if (!BN_copy(X, W))
 203                 goto err;
 204             if (!BN_add(X, X, test))
 205                 goto err;
 206
 207             /* step 9 */
 208             if (!BN_lshift1(r0, q))
 209                 goto err;
 210             if (!BN_mod(c, X, r0, ctx))
 211                 goto err;
 212             if (!BN_sub(r0, c, BN_value_one()))
 213                 goto err;
 214             if (!BN_sub(p, X, r0))
 215                 goto err;
 216
 217             /* step 10 */
 218             if (BN_cmp(p, test) >= 0) {
 219                 /* step 11 */
 220                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 221                 if (r > 0)
 222                     goto end;   /* found it */
 223                 if (r != 0)
 224                     goto err;
 225             }
 226
 227             /* step 13 */
 228             counter++;
 229             /* "offset = offset + n + 1" */
 230
 231             /* step 14 */
 232             if (counter >= 4096)
 233                 break;
 234         }
 235     }
 236  end:
 237     if (!BN_GENCB_call(cb, 2, 1))
 238         goto err;
 239
 240     /* We now need to generate g */
 241     /* Set r0=(p-1)/q */
 242     if (!BN_sub(test, p, BN_value_one()))
 243         goto err;
 244     if (!BN_div(r0, NULL, test, q, ctx))
 245         goto err;
 246
 247     if (!BN_set_word(test, h))
 248         goto err;
 249     if (!BN_MONT_CTX_set(mont, p, ctx))
 250         goto err;
 251
 252     for (;;) {
 253         /* g=test^r0%p */
 254         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 255             goto err;
 256         if (!BN_is_one(g))
 257             break;
 258         if (!BN_add(test, test, BN_value_one()))
 259             goto err;
 260         h++;
 261     }
 262
 263     if (!BN_GENCB_call(cb, 3, 1))
 264         goto err;
 265
 266     ok = 1;
 267  err:
 268     if (ok) {
 269         BN_free(ret->p);
 270         BN_free(ret->q);
 271         BN_free(ret->g);
 272         ret->p = BN_dup(p);
 273         ret->q = BN_dup(q);
 274         ret->g = BN_dup(g);
 275         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 276             ok = 0;
 277             goto err;
 278         }
 279         if (counter_ret != NULL)
 280             *counter_ret = counter;
 281         if (h_ret != NULL)
 282             *h_ret = h;
 283         if (seed_out)
 284             memcpy(seed_out, seed, qsize);
 285     }
 286     if (ctx)
 287         BN_CTX_end(ctx);
 288     BN_CTX_free(ctx);
 289     BN_MONT_CTX_free(mont);
 290     return ok;
 291 }
 292
 293 /*
 294  * This is a parameter generation algorithm for the DSA2 algorithm as
 295  * described in FIPS 186-3.
 296  */
 297
 298 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
 299                           const EVP_MD *evpmd, const unsigned char *seed_in,
 300                           size_t seed_len, int idx, unsigned char *seed_out,
 301                           int *counter_ret, unsigned long *h_ret,
 302                           BN_GENCB *cb)
 303 {
 304     int ok = -1;
 305     unsigned char *seed = NULL, *seed_tmp = NULL;
 306     unsigned char md[EVP_MAX_MD_SIZE];
 307     int mdsize;
 308     BIGNUM *r0, *W, *X, *c, *test;
 309     BIGNUM *g = NULL, *q = NULL, *p = NULL;
 310     BN_MONT_CTX *mont = NULL;
 311     int i, k, n = 0, m = 0, qsize = N >> 3;
 312     int counter = 0;
 313     int r = 0;
 314     BN_CTX *ctx = NULL;
 315     EVP_MD_CTX *mctx = EVP_MD_CTX_new();
 316     unsigned int h = 2;
 317
 318     if (mctx == NULL)
 319         goto err;
 320
 321     if (evpmd == NULL) {
 322         if (N == 160)
 323             evpmd = EVP_sha1();
 324         else if (N == 224)
 325             evpmd = EVP_sha224();
 326         else
 327             evpmd = EVP_sha256();
 328     }
 329
 330     mdsize = EVP_MD_size(evpmd);
 331     /* If unverifiable g generation only don't need seed */
 332     if (!ret->p || !ret->q || idx >= 0) {
 333         if (seed_len == 0)
 334             seed_len = mdsize;
 335
 336         seed = OPENSSL_malloc(seed_len);
 337
 338         if (seed_out)
 339             seed_tmp = seed_out;
 340         else
 341             seed_tmp = OPENSSL_malloc(seed_len);
 342
 343         if (seed == NULL || seed_tmp == NULL)
 344             goto err;
 345
 346         if (seed_in)
 347             memcpy(seed, seed_in, seed_len);
 348
 349     }
 350
 351     if ((ctx = BN_CTX_new()) == NULL)
 352         goto err;
 353
 354     if ((mont = BN_MONT_CTX_new()) == NULL)
 355         goto err;
 356
 357     BN_CTX_start(ctx);
 358     r0 = BN_CTX_get(ctx);
 359     g = BN_CTX_get(ctx);
 360     W = BN_CTX_get(ctx);
 361     X = BN_CTX_get(ctx);
 362     c = BN_CTX_get(ctx);
 363     test = BN_CTX_get(ctx);
 364     if (test == NULL)
 365         goto err;
 366
 367     /* if p, q already supplied generate g only */
 368     if (ret->p && ret->q) {
 369         p = ret->p;
 370         q = ret->q;
 371         if (idx >= 0)
 372             memcpy(seed_tmp, seed, seed_len);
 373         goto g_only;
 374     } else {
 375         p = BN_CTX_get(ctx);
 376         q = BN_CTX_get(ctx);
 377     }
 378
 379     if (!BN_lshift(test, BN_value_one(), L - 1))
 380         goto err;
 381     for (;;) {
 382         for (;;) {              /* find q */
 383             unsigned char *pmd;
 384             /* step 1 */
 385             if (!BN_GENCB_call(cb, 0, m++))
 386                 goto err;
 387
 388             if (!seed_in) {
 389                 if (RAND_bytes(seed, seed_len) <= 0)
 390                     goto err;
 391             }
 392             /* step 2 */
 393             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 394                 goto err;
 395             /* Take least significant bits of md */
 396             if (mdsize > qsize)
 397                 pmd = md + mdsize - qsize;
 398             else
 399                 pmd = md;
 400
 401             if (mdsize < qsize)
 402                 memset(md + mdsize, 0, qsize - mdsize);
 403
 404             /* step 3 */
 405             pmd[0] |= 0x80;
 406             pmd[qsize - 1] |= 0x01;
 407             if (!BN_bin2bn(pmd, qsize, q))
 408                 goto err;
 409
 410             /* step 4 */
 411             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 412                                         seed_in ? 1 : 0, cb);
 413             if (r > 0)
 414                 break;
 415             if (r != 0)
 416                 goto err;
 417             /* Provided seed didn't produce a prime: error */
 418             if (seed_in) {
 419                 ok = 0;
 420                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
 421                 goto err;
 422             }
 423
 424             /* do a callback call */
 425             /* step 5 */
 426         }
 427         /* Copy seed to seed_out before we mess with it */
 428         if (seed_out)
 429             memcpy(seed_out, seed, seed_len);
 430
 431         if (!BN_GENCB_call(cb, 2, 0))
 432             goto err;
 433         if (!BN_GENCB_call(cb, 3, 0))
 434             goto err;
 435
 436         /* step 6 */
 437         counter = 0;
 438         /* "offset = 1" */
 439
 440         n = (L - 1) / (mdsize << 3);
 441
 442         for (;;) {
 443             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 444                 goto err;
 445
 446             /* step 7 */
 447             BN_zero(W);
 448             /* now 'buf' contains "SEED + offset - 1" */
 449             for (k = 0; k <= n; k++) {
 450                 /*
 451                  * obtain "SEED + offset + k" by incrementing:
 452                  */
 453                 for (i = seed_len - 1; i >= 0; i--) {
 454                     seed[i]++;
 455                     if (seed[i] != 0)
 456                         break;
 457                 }
 458
 459                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 460                     goto err;
 461
 462                 /* step 8 */
 463                 if (!BN_bin2bn(md, mdsize, r0))
 464                     goto err;
 465                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
 466                     goto err;
 467                 if (!BN_add(W, W, r0))
 468                     goto err;
 469             }
 470
 471             /* more of step 8 */
 472             if (!BN_mask_bits(W, L - 1))
 473                 goto err;
 474             if (!BN_copy(X, W))
 475                 goto err;
 476             if (!BN_add(X, X, test))
 477                 goto err;
 478
 479             /* step 9 */
 480             if (!BN_lshift1(r0, q))
 481                 goto err;
 482             if (!BN_mod(c, X, r0, ctx))
 483                 goto err;
 484             if (!BN_sub(r0, c, BN_value_one()))
 485                 goto err;
 486             if (!BN_sub(p, X, r0))
 487                 goto err;
 488
 489             /* step 10 */
 490             if (BN_cmp(p, test) >= 0) {
 491                 /* step 11 */
 492                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 493                 if (r > 0)
 494                     goto end;   /* found it */
 495                 if (r != 0)
 496                     goto err;
 497             }
 498
 499             /* step 13 */
 500             counter++;
 501             /* "offset = offset + n + 1" */
 502
 503             /* step 14 */
 504             if (counter >= (int)(4 * L))
 505                 break;
 506         }
 507         if (seed_in) {
 508             ok = 0;
 509             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
 510             goto err;
 511         }
 512     }
 513  end:
 514     if (!BN_GENCB_call(cb, 2, 1))
 515         goto err;
 516
 517  g_only:
 518
 519     /* We now need to generate g */
 520     /* Set r0=(p-1)/q */
 521     if (!BN_sub(test, p, BN_value_one()))
 522         goto err;
 523     if (!BN_div(r0, NULL, test, q, ctx))
 524         goto err;
 525
 526     if (idx < 0) {
 527         if (!BN_set_word(test, h))
 528             goto err;
 529     } else
 530         h = 1;
 531     if (!BN_MONT_CTX_set(mont, p, ctx))
 532         goto err;
 533
 534     for (;;) {
 535         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
 536         if (idx >= 0) {
 537             md[0] = idx & 0xff;
 538             md[1] = (h >> 8) & 0xff;
 539             md[2] = h & 0xff;
 540             if (!EVP_DigestInit_ex(mctx, evpmd, NULL))
 541                 goto err;
 542             if (!EVP_DigestUpdate(mctx, seed_tmp, seed_len))
 543                 goto err;
 544             if (!EVP_DigestUpdate(mctx, ggen, sizeof(ggen)))
 545                 goto err;
 546             if (!EVP_DigestUpdate(mctx, md, 3))
 547                 goto err;
 548             if (!EVP_DigestFinal_ex(mctx, md, NULL))
 549                 goto err;
 550             if (!BN_bin2bn(md, mdsize, test))
 551                 goto err;
 552         }
 553         /* g=test^r0%p */
 554         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 555             goto err;
 556         if (!BN_is_one(g))
 557             break;
 558         if (idx < 0 && !BN_add(test, test, BN_value_one()))
 559             goto err;
 560         h++;
 561         if (idx >= 0 && h > 0xffff)
 562             goto err;
 563     }
 564
 565     if (!BN_GENCB_call(cb, 3, 1))
 566         goto err;
 567
 568     ok = 1;
 569  err:
 570     if (ok == 1) {
 571         if (p != ret->p) {
 572             BN_free(ret->p);
 573             ret->p = BN_dup(p);
 574         }
 575         if (q != ret->q) {
 576             BN_free(ret->q);
 577             ret->q = BN_dup(q);
 578         }
 579         BN_free(ret->g);
 580         ret->g = BN_dup(g);
 581         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 582             ok = -1;
 583             goto err;
 584         }
 585         if (counter_ret != NULL)
 586             *counter_ret = counter;
 587         if (h_ret != NULL)
 588             *h_ret = h;
 589     }
 590     OPENSSL_free(seed);
 591     if (seed_out != seed_tmp)
 592         OPENSSL_free(seed_tmp);
 593     if (ctx)
 594         BN_CTX_end(ctx);
 595     BN_CTX_free(ctx);
 596     BN_MONT_CTX_free(mont);
 597     EVP_MD_CTX_free(mctx);
 598     return ok;
 599 }