legacy-libs/grpc-cloned/deps/grpc/third_party/boringssl/crypto/dsa/dsa.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  *
  57  * The DSS routines are based on patches supplied by
  58  * Steven Schoch <schoch@sheba.arc.nasa.gov>. */
  59
  60 #include <openssl/dsa.h>
  61
  62 #include <string.h>
  63
  64 #include <openssl/bn.h>
  65 #include <openssl/dh.h>
  66 #include <openssl/digest.h>
  67 #include <openssl/engine.h>
  68 #include <openssl/err.h>
  69 #include <openssl/ex_data.h>
  70 #include <openssl/mem.h>
  71 #include <openssl/rand.h>
  72 #include <openssl/sha.h>
  73 #include <openssl/thread.h>
  74
  75 #include "../fipsmodule/bn/internal.h"
  76 #include "../internal.h"
  77
  78
  79 #define OPENSSL_DSA_MAX_MODULUS_BITS 10000
  80
  81 // Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of
  82 // Rabin-Miller
  83 #define DSS_prime_checks 50
  84
  85 static int dsa_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv,
  86                           BIGNUM **out_r);
  87
  88 static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT;
  89
  90 DSA *DSA_new(void) {
  91   DSA *dsa = OPENSSL_malloc(sizeof(DSA));
  92   if (dsa == NULL) {
  93     OPENSSL_PUT_ERROR(DSA, ERR_R_MALLOC_FAILURE);
  94     return NULL;
  95   }
  96
  97   OPENSSL_memset(dsa, 0, sizeof(DSA));
  98
  99   dsa->references = 1;
 100
 101   CRYPTO_MUTEX_init(&dsa->method_mont_lock);
 102   CRYPTO_new_ex_data(&dsa->ex_data);
 103
 104   return dsa;
 105 }
 106
 107 void DSA_free(DSA *dsa) {
 108   if (dsa == NULL) {
 109     return;
 110   }
 111
 112   if (!CRYPTO_refcount_dec_and_test_zero(&dsa->references)) {
 113     return;
 114   }
 115
 116   CRYPTO_free_ex_data(&g_ex_data_class, dsa, &dsa->ex_data);
 117
 118   BN_clear_free(dsa->p);
 119   BN_clear_free(dsa->q);
 120   BN_clear_free(dsa->g);
 121   BN_clear_free(dsa->pub_key);
 122   BN_clear_free(dsa->priv_key);
 123   BN_MONT_CTX_free(dsa->method_mont_p);
 124   BN_MONT_CTX_free(dsa->method_mont_q);
 125   CRYPTO_MUTEX_cleanup(&dsa->method_mont_lock);
 126   OPENSSL_free(dsa);
 127 }
 128
 129 int DSA_up_ref(DSA *dsa) {
 130   CRYPTO_refcount_inc(&dsa->references);
 131   return 1;
 132 }
 133
 134 void DSA_get0_key(const DSA *dsa, const BIGNUM **out_pub_key,
 135                   const BIGNUM **out_priv_key) {
 136   if (out_pub_key != NULL) {
 137     *out_pub_key = dsa->pub_key;
 138   }
 139   if (out_priv_key != NULL) {
 140     *out_priv_key = dsa->priv_key;
 141   }
 142 }
 143
 144 void DSA_get0_pqg(const DSA *dsa, const BIGNUM **out_p, const BIGNUM **out_q,
 145                   const BIGNUM **out_g) {
 146   if (out_p != NULL) {
 147     *out_p = dsa->p;
 148   }
 149   if (out_q != NULL) {
 150     *out_q = dsa->q;
 151   }
 152   if (out_g != NULL) {
 153     *out_g = dsa->g;
 154   }
 155 }
 156
 157 int DSA_set0_key(DSA *dsa, BIGNUM *pub_key, BIGNUM *priv_key) {
 158   if (dsa->pub_key == NULL && pub_key == NULL) {
 159     return 0;
 160   }
 161
 162   if (pub_key != NULL) {
 163     BN_free(dsa->pub_key);
 164     dsa->pub_key = pub_key;
 165   }
 166   if (priv_key != NULL) {
 167     BN_free(dsa->priv_key);
 168     dsa->priv_key = priv_key;
 169   }
 170
 171   return 1;
 172 }
 173
 174 int DSA_set0_pqg(DSA *dsa, BIGNUM *p, BIGNUM *q, BIGNUM *g) {
 175   if ((dsa->p == NULL && p == NULL) ||
 176       (dsa->q == NULL && q == NULL) ||
 177       (dsa->g == NULL && g == NULL)) {
 178     return 0;
 179   }
 180
 181   if (p != NULL) {
 182     BN_free(dsa->p);
 183     dsa->p = p;
 184   }
 185   if (q != NULL) {
 186     BN_free(dsa->q);
 187     dsa->q = q;
 188   }
 189   if (g != NULL) {
 190     BN_free(dsa->g);
 191     dsa->g = g;
 192   }
 193
 194   return 1;
 195 }
 196
 197 int DSA_generate_parameters_ex(DSA *dsa, unsigned bits, const uint8_t *seed_in,
 198                                size_t seed_len, int *out_counter,
 199                                unsigned long *out_h, BN_GENCB *cb) {
 200   int ok = 0;
 201   unsigned char seed[SHA256_DIGEST_LENGTH];
 202   unsigned char md[SHA256_DIGEST_LENGTH];
 203   unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
 204   BIGNUM *r0, *W, *X, *c, *test;
 205   BIGNUM *g = NULL, *q = NULL, *p = NULL;
 206   BN_MONT_CTX *mont = NULL;
 207   int k, n = 0, m = 0;
 208   unsigned i;
 209   int counter = 0;
 210   int r = 0;
 211   BN_CTX *ctx = NULL;
 212   unsigned int h = 2;
 213   unsigned qsize;
 214   const EVP_MD *evpmd;
 215
 216   evpmd = (bits >= 2048) ? EVP_sha256() : EVP_sha1();
 217   qsize = EVP_MD_size(evpmd);
 218
 219   if (bits < 512) {
 220     bits = 512;
 221   }
 222
 223   bits = (bits + 63) / 64 * 64;
 224
 225   if (seed_in != NULL) {
 226     if (seed_len < (size_t)qsize) {
 227       return 0;
 228     }
 229     if (seed_len > (size_t)qsize) {
 230       // Only consume as much seed as is expected.
 231       seed_len = qsize;
 232     }
 233     OPENSSL_memcpy(seed, seed_in, seed_len);
 234   }
 235
 236   ctx = BN_CTX_new();
 237   if (ctx == NULL) {
 238     goto err;
 239   }
 240   BN_CTX_start(ctx);
 241
 242   r0 = BN_CTX_get(ctx);
 243   g = BN_CTX_get(ctx);
 244   W = BN_CTX_get(ctx);
 245   q = BN_CTX_get(ctx);
 246   X = BN_CTX_get(ctx);
 247   c = BN_CTX_get(ctx);
 248   p = BN_CTX_get(ctx);
 249   test = BN_CTX_get(ctx);
 250
 251   if (test == NULL || !BN_lshift(test, BN_value_one(), bits - 1)) {
 252     goto err;
 253   }
 254
 255   for (;;) {
 256     // Find q.
 257     for (;;) {
 258       // step 1
 259       if (!BN_GENCB_call(cb, 0, m++)) {
 260         goto err;
 261       }
 262
 263       int use_random_seed = (seed_in == NULL);
 264       if (use_random_seed) {
 265         if (!RAND_bytes(seed, qsize)) {
 266           goto err;
 267         }
 268       } else {
 269         // If we come back through, use random seed next time.
 270         seed_in = NULL;
 271       }
 272       OPENSSL_memcpy(buf, seed, qsize);
 273       OPENSSL_memcpy(buf2, seed, qsize);
 274       // precompute "SEED + 1" for step 7:
 275       for (i = qsize - 1; i < qsize; i--) {
 276         buf[i]++;
 277         if (buf[i] != 0) {
 278           break;
 279         }
 280       }
 281
 282       // step 2
 283       if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL) ||
 284           !EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) {
 285         goto err;
 286       }
 287       for (i = 0; i < qsize; i++) {
 288         md[i] ^= buf2[i];
 289       }
 290
 291       // step 3
 292       md[0] |= 0x80;
 293       md[qsize - 1] |= 0x01;
 294       if (!BN_bin2bn(md, qsize, q)) {
 295         goto err;
 296       }
 297
 298       // step 4
 299       r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, use_random_seed, cb);
 300       if (r > 0) {
 301         break;
 302       }
 303       if (r != 0) {
 304         goto err;
 305       }
 306
 307       // do a callback call
 308       // step 5
 309     }
 310
 311     if (!BN_GENCB_call(cb, 2, 0) || !BN_GENCB_call(cb, 3, 0)) {
 312       goto err;
 313     }
 314
 315     // step 6
 316     counter = 0;
 317     // "offset = 2"
 318
 319     n = (bits - 1) / 160;
 320
 321     for (;;) {
 322       if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) {
 323         goto err;
 324       }
 325
 326       // step 7
 327       BN_zero(W);
 328       // now 'buf' contains "SEED + offset - 1"
 329       for (k = 0; k <= n; k++) {
 330         // obtain "SEED + offset + k" by incrementing:
 331         for (i = qsize - 1; i < qsize; i--) {
 332           buf[i]++;
 333           if (buf[i] != 0) {
 334             break;
 335           }
 336         }
 337
 338         if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) {
 339           goto err;
 340         }
 341
 342         // step 8
 343         if (!BN_bin2bn(md, qsize, r0) ||
 344             !BN_lshift(r0, r0, (qsize << 3) * k) ||
 345             !BN_add(W, W, r0)) {
 346           goto err;
 347         }
 348       }
 349
 350       // more of step 8
 351       if (!BN_mask_bits(W, bits - 1) ||
 352           !BN_copy(X, W) ||
 353           !BN_add(X, X, test)) {
 354         goto err;
 355       }
 356
 357       // step 9
 358       if (!BN_lshift1(r0, q) ||
 359           !BN_mod(c, X, r0, ctx) ||
 360           !BN_sub(r0, c, BN_value_one()) ||
 361           !BN_sub(p, X, r0)) {
 362         goto err;
 363       }
 364
 365       // step 10
 366       if (BN_cmp(p, test) >= 0) {
 367         // step 11
 368         r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 369         if (r > 0) {
 370           goto end;  // found it
 371         }
 372         if (r != 0) {
 373           goto err;
 374         }
 375       }
 376
 377       // step 13
 378       counter++;
 379       // "offset = offset + n + 1"
 380
 381       // step 14
 382       if (counter >= 4096) {
 383         break;
 384       }
 385     }
 386   }
 387 end:
 388   if (!BN_GENCB_call(cb, 2, 1)) {
 389     goto err;
 390   }
 391
 392   // We now need to generate g
 393   // Set r0=(p-1)/q
 394   if (!BN_sub(test, p, BN_value_one()) ||
 395       !BN_div(r0, NULL, test, q, ctx)) {
 396     goto err;
 397   }
 398
 399   mont = BN_MONT_CTX_new_for_modulus(p, ctx);
 400   if (mont == NULL ||
 401       !BN_set_word(test, h)) {
 402     goto err;
 403   }
 404
 405   for (;;) {
 406     // g=test^r0%p
 407     if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) {
 408       goto err;
 409     }
 410     if (!BN_is_one(g)) {
 411       break;
 412     }
 413     if (!BN_add(test, test, BN_value_one())) {
 414       goto err;
 415     }
 416     h++;
 417   }
 418
 419   if (!BN_GENCB_call(cb, 3, 1)) {
 420     goto err;
 421   }
 422
 423   ok = 1;
 424
 425 err:
 426   if (ok) {
 427     BN_free(dsa->p);
 428     BN_free(dsa->q);
 429     BN_free(dsa->g);
 430     dsa->p = BN_dup(p);
 431     dsa->q = BN_dup(q);
 432     dsa->g = BN_dup(g);
 433     if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) {
 434       ok = 0;
 435       goto err;
 436     }
 437     if (out_counter != NULL) {
 438       *out_counter = counter;
 439     }
 440     if (out_h != NULL) {
 441       *out_h = h;
 442     }
 443   }
 444
 445   if (ctx) {
 446     BN_CTX_end(ctx);
 447     BN_CTX_free(ctx);
 448   }
 449
 450   BN_MONT_CTX_free(mont);
 451
 452   return ok;
 453 }
 454
 455 DSA *DSAparams_dup(const DSA *dsa) {
 456   DSA *ret = DSA_new();
 457   if (ret == NULL) {
 458     return NULL;
 459   }
 460   ret->p = BN_dup(dsa->p);
 461   ret->q = BN_dup(dsa->q);
 462   ret->g = BN_dup(dsa->g);
 463   if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 464     DSA_free(ret);
 465     return NULL;
 466   }
 467   return ret;
 468 }
 469
 470 int DSA_generate_key(DSA *dsa) {
 471   int ok = 0;
 472   BN_CTX *ctx = NULL;
 473   BIGNUM *pub_key = NULL, *priv_key = NULL;
 474
 475   ctx = BN_CTX_new();
 476   if (ctx == NULL) {
 477     goto err;
 478   }
 479
 480   priv_key = dsa->priv_key;
 481   if (priv_key == NULL) {
 482     priv_key = BN_new();
 483     if (priv_key == NULL) {
 484       goto err;
 485     }
 486   }
 487
 488   if (!BN_rand_range_ex(priv_key, 1, dsa->q)) {
 489     goto err;
 490   }
 491
 492   pub_key = dsa->pub_key;
 493   if (pub_key == NULL) {
 494     pub_key = BN_new();
 495     if (pub_key == NULL) {
 496       goto err;
 497     }
 498   }
 499
 500   if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, &dsa->method_mont_lock,
 501                               dsa->p, ctx) ||
 502       !BN_mod_exp_mont_consttime(pub_key, dsa->g, priv_key, dsa->p, ctx,
 503                                  dsa->method_mont_p)) {
 504     goto err;
 505   }
 506
 507   dsa->priv_key = priv_key;
 508   dsa->pub_key = pub_key;
 509   ok = 1;
 510
 511 err:
 512   if (dsa->pub_key == NULL) {
 513     BN_free(pub_key);
 514   }
 515   if (dsa->priv_key == NULL) {
 516     BN_free(priv_key);
 517   }
 518   BN_CTX_free(ctx);
 519
 520   return ok;
 521 }
 522
 523 DSA_SIG *DSA_SIG_new(void) {
 524   DSA_SIG *sig;
 525   sig = OPENSSL_malloc(sizeof(DSA_SIG));
 526   if (!sig) {
 527     return NULL;
 528   }
 529   sig->r = NULL;
 530   sig->s = NULL;
 531   return sig;
 532 }
 533
 534 void DSA_SIG_free(DSA_SIG *sig) {
 535   if (!sig) {
 536     return;
 537   }
 538
 539   BN_free(sig->r);
 540   BN_free(sig->s);
 541   OPENSSL_free(sig);
 542 }
 543
 544 DSA_SIG *DSA_do_sign(const uint8_t *digest, size_t digest_len, const DSA *dsa) {
 545   BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
 546   BIGNUM m;
 547   BIGNUM xr;
 548   BN_CTX *ctx = NULL;
 549   int reason = ERR_R_BN_LIB;
 550   DSA_SIG *ret = NULL;
 551
 552   BN_init(&m);
 553   BN_init(&xr);
 554
 555   if (!dsa->p || !dsa->q || !dsa->g) {
 556     reason = DSA_R_MISSING_PARAMETERS;
 557     goto err;
 558   }
 559
 560   s = BN_new();
 561   if (s == NULL) {
 562     goto err;
 563   }
 564   ctx = BN_CTX_new();
 565   if (ctx == NULL) {
 566     goto err;
 567   }
 568
 569 redo:
 570   if (!dsa_sign_setup(dsa, ctx, &kinv, &r)) {
 571     goto err;
 572   }
 573
 574   if (digest_len > BN_num_bytes(dsa->q)) {
 575     // if the digest length is greater than the size of q use the
 576     // BN_num_bits(dsa->q) leftmost bits of the digest, see
 577     // fips 186-3, 4.2
 578     digest_len = BN_num_bytes(dsa->q);
 579   }
 580
 581   if (BN_bin2bn(digest, digest_len, &m) == NULL) {
 582     goto err;
 583   }
 584
 585   // Compute  s = inv(k) (m + xr) mod q
 586   if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) {
 587     goto err;  // s = xr
 588   }
 589   if (!BN_add(s, &xr, &m)) {
 590     goto err;  // s = m + xr
 591   }
 592   if (BN_cmp(s, dsa->q) > 0) {
 593     if (!BN_sub(s, s, dsa->q)) {
 594       goto err;
 595     }
 596   }
 597   if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) {
 598     goto err;
 599   }
 600
 601   // Redo if r or s is zero as required by FIPS 186-3: this is
 602   // very unlikely.
 603   if (BN_is_zero(r) || BN_is_zero(s)) {
 604     goto redo;
 605   }
 606   ret = DSA_SIG_new();
 607   if (ret == NULL) {
 608     goto err;
 609   }
 610   ret->r = r;
 611   ret->s = s;
 612
 613 err:
 614   if (ret == NULL) {
 615     OPENSSL_PUT_ERROR(DSA, reason);
 616     BN_free(r);
 617     BN_free(s);
 618   }
 619   BN_CTX_free(ctx);
 620   BN_clear_free(&m);
 621   BN_clear_free(&xr);
 622   BN_clear_free(kinv);
 623
 624   return ret;
 625 }
 626
 627 int DSA_do_verify(const uint8_t *digest, size_t digest_len, DSA_SIG *sig,
 628                   const DSA *dsa) {
 629   int valid;
 630   if (!DSA_do_check_signature(&valid, digest, digest_len, sig, dsa)) {
 631     return -1;
 632   }
 633   return valid;
 634 }
 635
 636 int DSA_do_check_signature(int *out_valid, const uint8_t *digest,
 637                            size_t digest_len, DSA_SIG *sig, const DSA *dsa) {
 638   BN_CTX *ctx;
 639   BIGNUM u1, u2, t1;
 640   int ret = 0;
 641   unsigned i;
 642
 643   *out_valid = 0;
 644
 645   if (!dsa->p || !dsa->q || !dsa->g) {
 646     OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS);
 647     return 0;
 648   }
 649
 650   i = BN_num_bits(dsa->q);
 651   // fips 186-3 allows only different sizes for q
 652   if (i != 160 && i != 224 && i != 256) {
 653     OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE);
 654     return 0;
 655   }
 656
 657   if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
 658     OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE);
 659     return 0;
 660   }
 661
 662   BN_init(&u1);
 663   BN_init(&u2);
 664   BN_init(&t1);
 665
 666   ctx = BN_CTX_new();
 667   if (ctx == NULL) {
 668     goto err;
 669   }
 670
 671   if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
 672       BN_ucmp(sig->r, dsa->q) >= 0) {
 673     ret = 1;
 674     goto err;
 675   }
 676   if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
 677       BN_ucmp(sig->s, dsa->q) >= 0) {
 678     ret = 1;
 679     goto err;
 680   }
 681
 682   // Calculate W = inv(S) mod Q
 683   // save W in u2
 684   if (BN_mod_inverse(&u2, sig->s, dsa->q, ctx) == NULL) {
 685     goto err;
 686   }
 687
 688   // save M in u1
 689   if (digest_len > (i >> 3)) {
 690     // if the digest length is greater than the size of q use the
 691     // BN_num_bits(dsa->q) leftmost bits of the digest, see
 692     // fips 186-3, 4.2
 693     digest_len = (i >> 3);
 694   }
 695
 696   if (BN_bin2bn(digest, digest_len, &u1) == NULL) {
 697     goto err;
 698   }
 699
 700   // u1 = M * w mod q
 701   if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) {
 702     goto err;
 703   }
 704
 705   // u2 = r * w mod q
 706   if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) {
 707     goto err;
 708   }
 709
 710   if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p,
 711                               (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p,
 712                               ctx)) {
 713     goto err;
 714   }
 715
 716   if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx,
 717                         dsa->method_mont_p)) {
 718     goto err;
 719   }
 720
 721   // BN_copy(&u1,&t1);
 722   // let u1 = u1 mod q
 723   if (!BN_mod(&u1, &t1, dsa->q, ctx)) {
 724     goto err;
 725   }
 726
 727   // V is now in u1.  If the signature is correct, it will be
 728   // equal to R.
 729   *out_valid = BN_ucmp(&u1, sig->r) == 0;
 730   ret = 1;
 731
 732 err:
 733   if (ret != 1) {
 734     OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB);
 735   }
 736   BN_CTX_free(ctx);
 737   BN_free(&u1);
 738   BN_free(&u2);
 739   BN_free(&t1);
 740
 741   return ret;
 742 }
 743
 744 int DSA_sign(int type, const uint8_t *digest, size_t digest_len,
 745              uint8_t *out_sig, unsigned int *out_siglen, const DSA *dsa) {
 746   DSA_SIG *s;
 747
 748   s = DSA_do_sign(digest, digest_len, dsa);
 749   if (s == NULL) {
 750     *out_siglen = 0;
 751     return 0;
 752   }
 753
 754   *out_siglen = i2d_DSA_SIG(s, &out_sig);
 755   DSA_SIG_free(s);
 756   return 1;
 757 }
 758
 759 int DSA_verify(int type, const uint8_t *digest, size_t digest_len,
 760                const uint8_t *sig, size_t sig_len, const DSA *dsa) {
 761   int valid;
 762   if (!DSA_check_signature(&valid, digest, digest_len, sig, sig_len, dsa)) {
 763     return -1;
 764   }
 765   return valid;
 766 }
 767
 768 int DSA_check_signature(int *out_valid, const uint8_t *digest,
 769                         size_t digest_len, const uint8_t *sig, size_t sig_len,
 770                         const DSA *dsa) {
 771   DSA_SIG *s = NULL;
 772   int ret = 0;
 773   uint8_t *der = NULL;
 774
 775   s = DSA_SIG_new();
 776   if (s == NULL) {
 777     goto err;
 778   }
 779
 780   const uint8_t *sigp = sig;
 781   if (d2i_DSA_SIG(&s, &sigp, sig_len) == NULL || sigp != sig + sig_len) {
 782     goto err;
 783   }
 784
 785   // Ensure that the signature uses DER and doesn't have trailing garbage.
 786   int der_len = i2d_DSA_SIG(s, &der);
 787   if (der_len < 0 || (size_t)der_len != sig_len ||
 788       OPENSSL_memcmp(sig, der, sig_len)) {
 789     goto err;
 790   }
 791
 792   ret = DSA_do_check_signature(out_valid, digest, digest_len, s, dsa);
 793
 794 err:
 795   OPENSSL_free(der);
 796   DSA_SIG_free(s);
 797   return ret;
 798 }
 799
 800 // der_len_len returns the number of bytes needed to represent a length of |len|
 801 // in DER.
 802 static size_t der_len_len(size_t len) {
 803   if (len < 0x80) {
 804     return 1;
 805   }
 806   size_t ret = 1;
 807   while (len > 0) {
 808     ret++;
 809     len >>= 8;
 810   }
 811   return ret;
 812 }
 813
 814 int DSA_size(const DSA *dsa) {
 815   size_t order_len = BN_num_bytes(dsa->q);
 816   // Compute the maximum length of an |order_len| byte integer. Defensively
 817   // assume that the leading 0x00 is included.
 818   size_t integer_len = 1 /* tag */ + der_len_len(order_len + 1) + 1 + order_len;
 819   if (integer_len < order_len) {
 820     return 0;
 821   }
 822   // A DSA signature is two INTEGERs.
 823   size_t value_len = 2 * integer_len;
 824   if (value_len < integer_len) {
 825     return 0;
 826   }
 827   // Add the header.
 828   size_t ret = 1 /* tag */ + der_len_len(value_len) + value_len;
 829   if (ret < value_len) {
 830     return 0;
 831   }
 832   return ret;
 833 }
 834
 835 static int dsa_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv,
 836                           BIGNUM **out_r) {
 837   BN_CTX *ctx;
 838   BIGNUM k, *kinv = NULL, *r = NULL;
 839   int ret = 0;
 840
 841   if (!dsa->p || !dsa->q || !dsa->g) {
 842     OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS);
 843     return 0;
 844   }
 845
 846   BN_init(&k);
 847
 848   ctx = ctx_in;
 849   if (ctx == NULL) {
 850     ctx = BN_CTX_new();
 851     if (ctx == NULL) {
 852       goto err;
 853     }
 854   }
 855
 856   r = BN_new();
 857   kinv = BN_new();
 858   if (r == NULL || kinv == NULL ||
 859       // Get random k
 860       !BN_rand_range_ex(&k, 1, dsa->q) ||
 861       !BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p,
 862                               (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p,
 863                               ctx) ||
 864       !BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_q,
 865                               (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->q,
 866                               ctx) ||
 867       // Compute r = (g^k mod p) mod q
 868       !BN_mod_exp_mont_consttime(r, dsa->g, &k, dsa->p, ctx,
 869                                  dsa->method_mont_p) ||
 870       !BN_mod(r, r, dsa->q, ctx) ||
 871       // Compute part of 's = inv(k) (m + xr) mod q' using Fermat's Little
 872       // Theorem.
 873       !bn_mod_inverse_prime(kinv, &k, dsa->q, ctx, dsa->method_mont_q)) {
 874     goto err;
 875   }
 876
 877   BN_clear_free(*out_kinv);
 878   *out_kinv = kinv;
 879   kinv = NULL;
 880   BN_clear_free(*out_r);
 881   *out_r = r;
 882   ret = 1;
 883
 884 err:
 885   if (!ret) {
 886     OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB);
 887     if (r != NULL) {
 888       BN_clear_free(r);
 889     }
 890   }
 891
 892   if (ctx_in == NULL) {
 893     BN_CTX_free(ctx);
 894   }
 895   BN_clear_free(&k);
 896   BN_clear_free(kinv);
 897   return ret;
 898 }
 899
 900 int DSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused,
 901                          CRYPTO_EX_dup *dup_unused, CRYPTO_EX_free *free_func) {
 902   int index;
 903   if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp,
 904                                free_func)) {
 905     return -1;
 906   }
 907   return index;
 908 }
 909
 910 int DSA_set_ex_data(DSA *dsa, int idx, void *arg) {
 911   return CRYPTO_set_ex_data(&dsa->ex_data, idx, arg);
 912 }
 913
 914 void *DSA_get_ex_data(const DSA *dsa, int idx) {
 915   return CRYPTO_get_ex_data(&dsa->ex_data, idx);
 916 }
 917
 918 DH *DSA_dup_DH(const DSA *dsa) {
 919   if (dsa == NULL) {
 920     return NULL;
 921   }
 922
 923   DH *ret = DH_new();
 924   if (ret == NULL) {
 925     goto err;
 926   }
 927   if (dsa->q != NULL) {
 928     ret->priv_length = BN_num_bits(dsa->q);
 929     if ((ret->q = BN_dup(dsa->q)) == NULL) {
 930       goto err;
 931     }
 932   }
 933   if ((dsa->p != NULL && (ret->p = BN_dup(dsa->p)) == NULL) ||
 934       (dsa->g != NULL && (ret->g = BN_dup(dsa->g)) == NULL) ||
 935       (dsa->pub_key != NULL && (ret->pub_key = BN_dup(dsa->pub_key)) == NULL) ||
 936       (dsa->priv_key != NULL &&
 937        (ret->priv_key = BN_dup(dsa->priv_key)) == NULL)) {
 938     goto err;
 939   }
 940
 941   return ret;
 942
 943 err:
 944   DH_free(ret);
 945   return NULL;
 946 }