crypto/dsa/dsa_gen.c

   1 /* crypto/dsa/dsa_gen.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 /*
  60  * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
  61  * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB
  62  * 180-1)
  63  */
  64 #define xxxHASH    EVP_sha1()
  65
  66 #include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */
  67
  68 #include <stdio.h>
  69 #include "internal/cryptlib.h"
  70 #include <openssl/evp.h>
  71 #include <openssl/bn.h>
  72 #include <openssl/rand.h>
  73 #include <openssl/sha.h>
  74
  75 #include "dsa_locl.h"
  76
  77 int DSA_generate_parameters_ex(DSA *ret, int bits,
  78                                const unsigned char *seed_in, int seed_len,
  79                                int *counter_ret, unsigned long *h_ret,
  80                                BN_GENCB *cb)
  81 {
  82     if (ret->meth->dsa_paramgen)
  83         return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len,
  84                                        counter_ret, h_ret, cb);
  85     else {
  86         const EVP_MD *evpmd;
  87         size_t qbits = bits >= 2048 ? 256 : 160;
  88
  89         if (bits >= 2048) {
  90             qbits = 256;
  91             evpmd = EVP_sha256();
  92         } else {
  93             qbits = 160;
  94             evpmd = EVP_sha1();
  95         }
  96
  97         return dsa_builtin_paramgen(ret, bits, qbits, evpmd,
  98                                     seed_in, seed_len, NULL, counter_ret,
  99                                     h_ret, cb);
 100     }
 101 }
 102
 103 int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits,
 104                          const EVP_MD *evpmd, const unsigned char *seed_in,
 105                          size_t seed_len, unsigned char *seed_out,
 106                          int *counter_ret, unsigned long *h_ret, BN_GENCB *cb)
 107 {
 108     int ok = 0;
 109     unsigned char seed[SHA256_DIGEST_LENGTH];
 110     unsigned char md[SHA256_DIGEST_LENGTH];
 111     unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH];
 112     BIGNUM *r0, *W, *X, *c, *test;
 113     BIGNUM *g = NULL, *q = NULL, *p = NULL;
 114     BN_MONT_CTX *mont = NULL;
 115     int i, k, n = 0, m = 0, qsize = qbits >> 3;
 116     int counter = 0;
 117     int r = 0;
 118     BN_CTX *ctx = NULL;
 119     unsigned int h = 2;
 120
 121     if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH &&
 122         qsize != SHA256_DIGEST_LENGTH)
 123         /* invalid q size */
 124         return 0;
 125
 126     if (evpmd == NULL)
 127         /* use SHA1 as default */
 128         evpmd = EVP_sha1();
 129
 130     if (bits < 512)
 131         bits = 512;
 132
 133     bits = (bits + 63) / 64 * 64;
 134
 135     if (seed_in != NULL) {
 136         if (seed_len < (size_t)qsize)
 137             return 0;
 138         if (seed_len > (size_t)qsize) {
 139             /* Only consume as much seed as is expected. */
 140             seed_len = qsize;
 141         }
 142         memcpy(seed, seed_in, seed_len);
 143     }
 144
 145     if ((mont = BN_MONT_CTX_new()) == NULL)
 146         goto err;
 147
 148     if ((ctx = BN_CTX_new()) == NULL)
 149         goto err;
 150
 151     BN_CTX_start(ctx);
 152
 153     r0 = BN_CTX_get(ctx);
 154     g = BN_CTX_get(ctx);
 155     W = BN_CTX_get(ctx);
 156     q = BN_CTX_get(ctx);
 157     X = BN_CTX_get(ctx);
 158     c = BN_CTX_get(ctx);
 159     p = BN_CTX_get(ctx);
 160     test = BN_CTX_get(ctx);
 161
 162     if (!BN_lshift(test, BN_value_one(), bits - 1))
 163         goto err;
 164
 165     for (;;) {
 166         for (;;) {              /* find q */
 167             int use_random_seed = (seed_in == NULL);
 168
 169             /* step 1 */
 170             if (!BN_GENCB_call(cb, 0, m++))
 171                 goto err;
 172
 173             if (use_random_seed) {
 174                 if (RAND_bytes(seed, qsize) <= 0)
 175                     goto err;
 176             } else {
 177                 /* If we come back through, use random seed next time. */
 178                 seed_in = NULL;
 179             }
 180             memcpy(buf, seed, qsize);
 181             memcpy(buf2, seed, qsize);
 182             /* precompute "SEED + 1" for step 7: */
 183             for (i = qsize - 1; i >= 0; i--) {
 184                 buf[i]++;
 185                 if (buf[i] != 0)
 186                     break;
 187             }
 188
 189             /* step 2 */
 190             if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL))
 191                 goto err;
 192             if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL))
 193                 goto err;
 194             for (i = 0; i < qsize; i++)
 195                 md[i] ^= buf2[i];
 196
 197             /* step 3 */
 198             md[0] |= 0x80;
 199             md[qsize - 1] |= 0x01;
 200             if (!BN_bin2bn(md, qsize, q))
 201                 goto err;
 202
 203             /* step 4 */
 204             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 205                                         use_random_seed, cb);
 206             if (r > 0)
 207                 break;
 208             if (r != 0)
 209                 goto err;
 210
 211             /* do a callback call */
 212             /* step 5 */
 213         }
 214
 215         if (!BN_GENCB_call(cb, 2, 0))
 216             goto err;
 217         if (!BN_GENCB_call(cb, 3, 0))
 218             goto err;
 219
 220         /* step 6 */
 221         counter = 0;
 222         /* "offset = 2" */
 223
 224         n = (bits - 1) / 160;
 225
 226         for (;;) {
 227             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 228                 goto err;
 229
 230             /* step 7 */
 231             BN_zero(W);
 232             /* now 'buf' contains "SEED + offset - 1" */
 233             for (k = 0; k <= n; k++) {
 234                 /*
 235                  * obtain "SEED + offset + k" by incrementing:
 236                  */
 237                 for (i = qsize - 1; i >= 0; i--) {
 238                     buf[i]++;
 239                     if (buf[i] != 0)
 240                         break;
 241                 }
 242
 243                 if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL))
 244                     goto err;
 245
 246                 /* step 8 */
 247                 if (!BN_bin2bn(md, qsize, r0))
 248                     goto err;
 249                 if (!BN_lshift(r0, r0, (qsize << 3) * k))
 250                     goto err;
 251                 if (!BN_add(W, W, r0))
 252                     goto err;
 253             }
 254
 255             /* more of step 8 */
 256             if (!BN_mask_bits(W, bits - 1))
 257                 goto err;
 258             if (!BN_copy(X, W))
 259                 goto err;
 260             if (!BN_add(X, X, test))
 261                 goto err;
 262
 263             /* step 9 */
 264             if (!BN_lshift1(r0, q))
 265                 goto err;
 266             if (!BN_mod(c, X, r0, ctx))
 267                 goto err;
 268             if (!BN_sub(r0, c, BN_value_one()))
 269                 goto err;
 270             if (!BN_sub(p, X, r0))
 271                 goto err;
 272
 273             /* step 10 */
 274             if (BN_cmp(p, test) >= 0) {
 275                 /* step 11 */
 276                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 277                 if (r > 0)
 278                     goto end;   /* found it */
 279                 if (r != 0)
 280                     goto err;
 281             }
 282
 283             /* step 13 */
 284             counter++;
 285             /* "offset = offset + n + 1" */
 286
 287             /* step 14 */
 288             if (counter >= 4096)
 289                 break;
 290         }
 291     }
 292  end:
 293     if (!BN_GENCB_call(cb, 2, 1))
 294         goto err;
 295
 296     /* We now need to generate g */
 297     /* Set r0=(p-1)/q */
 298     if (!BN_sub(test, p, BN_value_one()))
 299         goto err;
 300     if (!BN_div(r0, NULL, test, q, ctx))
 301         goto err;
 302
 303     if (!BN_set_word(test, h))
 304         goto err;
 305     if (!BN_MONT_CTX_set(mont, p, ctx))
 306         goto err;
 307
 308     for (;;) {
 309         /* g=test^r0%p */
 310         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 311             goto err;
 312         if (!BN_is_one(g))
 313             break;
 314         if (!BN_add(test, test, BN_value_one()))
 315             goto err;
 316         h++;
 317     }
 318
 319     if (!BN_GENCB_call(cb, 3, 1))
 320         goto err;
 321
 322     ok = 1;
 323  err:
 324     if (ok) {
 325         BN_free(ret->p);
 326         BN_free(ret->q);
 327         BN_free(ret->g);
 328         ret->p = BN_dup(p);
 329         ret->q = BN_dup(q);
 330         ret->g = BN_dup(g);
 331         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 332             ok = 0;
 333             goto err;
 334         }
 335         if (counter_ret != NULL)
 336             *counter_ret = counter;
 337         if (h_ret != NULL)
 338             *h_ret = h;
 339         if (seed_out)
 340             memcpy(seed_out, seed, qsize);
 341     }
 342     if (ctx)
 343         BN_CTX_end(ctx);
 344     BN_CTX_free(ctx);
 345     BN_MONT_CTX_free(mont);
 346     return ok;
 347 }
 348
 349 /*
 350  * This is a parameter generation algorithm for the DSA2 algorithm as
 351  * described in FIPS 186-3.
 352  */
 353
 354 int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N,
 355                           const EVP_MD *evpmd, const unsigned char *seed_in,
 356                           size_t seed_len, int idx, unsigned char *seed_out,
 357                           int *counter_ret, unsigned long *h_ret,
 358                           BN_GENCB *cb)
 359 {
 360     int ok = -1;
 361     unsigned char *seed = NULL, *seed_tmp = NULL;
 362     unsigned char md[EVP_MAX_MD_SIZE];
 363     int mdsize;
 364     BIGNUM *r0, *W, *X, *c, *test;
 365     BIGNUM *g = NULL, *q = NULL, *p = NULL;
 366     BN_MONT_CTX *mont = NULL;
 367     int i, k, n = 0, m = 0, qsize = N >> 3;
 368     int counter = 0;
 369     int r = 0;
 370     BN_CTX *ctx = NULL;
 371     EVP_MD_CTX mctx;
 372     unsigned int h = 2;
 373
 374     EVP_MD_CTX_init(&mctx);
 375
 376     if (evpmd == NULL) {
 377         if (N == 160)
 378             evpmd = EVP_sha1();
 379         else if (N == 224)
 380             evpmd = EVP_sha224();
 381         else
 382             evpmd = EVP_sha256();
 383     }
 384
 385     mdsize = M_EVP_MD_size(evpmd);
 386     /* If unverificable g generation only don't need seed */
 387     if (!ret->p || !ret->q || idx >= 0) {
 388         if (seed_len == 0)
 389             seed_len = mdsize;
 390
 391         seed = OPENSSL_malloc(seed_len);
 392
 393         if (seed_out)
 394             seed_tmp = seed_out;
 395         else
 396             seed_tmp = OPENSSL_malloc(seed_len);
 397
 398         if (!seed || !seed_tmp)
 399             goto err;
 400
 401         if (seed_in)
 402             memcpy(seed, seed_in, seed_len);
 403
 404     }
 405
 406     if ((ctx = BN_CTX_new()) == NULL)
 407         goto err;
 408
 409     if ((mont = BN_MONT_CTX_new()) == NULL)
 410         goto err;
 411
 412     BN_CTX_start(ctx);
 413     r0 = BN_CTX_get(ctx);
 414     g = BN_CTX_get(ctx);
 415     W = BN_CTX_get(ctx);
 416     X = BN_CTX_get(ctx);
 417     c = BN_CTX_get(ctx);
 418     test = BN_CTX_get(ctx);
 419
 420     /* if p, q already supplied generate g only */
 421     if (ret->p && ret->q) {
 422         p = ret->p;
 423         q = ret->q;
 424         if (idx >= 0)
 425             memcpy(seed_tmp, seed, seed_len);
 426         goto g_only;
 427     } else {
 428         p = BN_CTX_get(ctx);
 429         q = BN_CTX_get(ctx);
 430     }
 431
 432     if (!BN_lshift(test, BN_value_one(), L - 1))
 433         goto err;
 434     for (;;) {
 435         for (;;) {              /* find q */
 436             unsigned char *pmd;
 437             /* step 1 */
 438             if (!BN_GENCB_call(cb, 0, m++))
 439                 goto err;
 440
 441             if (!seed_in) {
 442                 if (RAND_bytes(seed, seed_len) <= 0)
 443                     goto err;
 444             }
 445             /* step 2 */
 446             if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 447                 goto err;
 448             /* Take least significant bits of md */
 449             if (mdsize > qsize)
 450                 pmd = md + mdsize - qsize;
 451             else
 452                 pmd = md;
 453
 454             if (mdsize < qsize)
 455                 memset(md + mdsize, 0, qsize - mdsize);
 456
 457             /* step 3 */
 458             pmd[0] |= 0x80;
 459             pmd[qsize - 1] |= 0x01;
 460             if (!BN_bin2bn(pmd, qsize, q))
 461                 goto err;
 462
 463             /* step 4 */
 464             r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx,
 465                                         seed_in ? 1 : 0, cb);
 466             if (r > 0)
 467                 break;
 468             if (r != 0)
 469                 goto err;
 470             /* Provided seed didn't produce a prime: error */
 471             if (seed_in) {
 472                 ok = 0;
 473                 DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME);
 474                 goto err;
 475             }
 476
 477             /* do a callback call */
 478             /* step 5 */
 479         }
 480         /* Copy seed to seed_out before we mess with it */
 481         if (seed_out)
 482             memcpy(seed_out, seed, seed_len);
 483
 484         if (!BN_GENCB_call(cb, 2, 0))
 485             goto err;
 486         if (!BN_GENCB_call(cb, 3, 0))
 487             goto err;
 488
 489         /* step 6 */
 490         counter = 0;
 491         /* "offset = 1" */
 492
 493         n = (L - 1) / (mdsize << 3);
 494
 495         for (;;) {
 496             if ((counter != 0) && !BN_GENCB_call(cb, 0, counter))
 497                 goto err;
 498
 499             /* step 7 */
 500             BN_zero(W);
 501             /* now 'buf' contains "SEED + offset - 1" */
 502             for (k = 0; k <= n; k++) {
 503                 /*
 504                  * obtain "SEED + offset + k" by incrementing:
 505                  */
 506                 for (i = seed_len - 1; i >= 0; i--) {
 507                     seed[i]++;
 508                     if (seed[i] != 0)
 509                         break;
 510                 }
 511
 512                 if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL))
 513                     goto err;
 514
 515                 /* step 8 */
 516                 if (!BN_bin2bn(md, mdsize, r0))
 517                     goto err;
 518                 if (!BN_lshift(r0, r0, (mdsize << 3) * k))
 519                     goto err;
 520                 if (!BN_add(W, W, r0))
 521                     goto err;
 522             }
 523
 524             /* more of step 8 */
 525             if (!BN_mask_bits(W, L - 1))
 526                 goto err;
 527             if (!BN_copy(X, W))
 528                 goto err;
 529             if (!BN_add(X, X, test))
 530                 goto err;
 531
 532             /* step 9 */
 533             if (!BN_lshift1(r0, q))
 534                 goto err;
 535             if (!BN_mod(c, X, r0, ctx))
 536                 goto err;
 537             if (!BN_sub(r0, c, BN_value_one()))
 538                 goto err;
 539             if (!BN_sub(p, X, r0))
 540                 goto err;
 541
 542             /* step 10 */
 543             if (BN_cmp(p, test) >= 0) {
 544                 /* step 11 */
 545                 r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb);
 546                 if (r > 0)
 547                     goto end;   /* found it */
 548                 if (r != 0)
 549                     goto err;
 550             }
 551
 552             /* step 13 */
 553             counter++;
 554             /* "offset = offset + n + 1" */
 555
 556             /* step 14 */
 557             if (counter >= (int)(4 * L))
 558                 break;
 559         }
 560         if (seed_in) {
 561             ok = 0;
 562             DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS);
 563             goto err;
 564         }
 565     }
 566  end:
 567     if (!BN_GENCB_call(cb, 2, 1))
 568         goto err;
 569
 570  g_only:
 571
 572     /* We now need to generate g */
 573     /* Set r0=(p-1)/q */
 574     if (!BN_sub(test, p, BN_value_one()))
 575         goto err;
 576     if (!BN_div(r0, NULL, test, q, ctx))
 577         goto err;
 578
 579     if (idx < 0) {
 580         if (!BN_set_word(test, h))
 581             goto err;
 582     } else
 583         h = 1;
 584     if (!BN_MONT_CTX_set(mont, p, ctx))
 585         goto err;
 586
 587     for (;;) {
 588         static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e };
 589         if (idx >= 0) {
 590             md[0] = idx & 0xff;
 591             md[1] = (h >> 8) & 0xff;
 592             md[2] = h & 0xff;
 593             if (!EVP_DigestInit_ex(&mctx, evpmd, NULL))
 594                 goto err;
 595             if (!EVP_DigestUpdate(&mctx, seed_tmp, seed_len))
 596                 goto err;
 597             if (!EVP_DigestUpdate(&mctx, ggen, sizeof(ggen)))
 598                 goto err;
 599             if (!EVP_DigestUpdate(&mctx, md, 3))
 600                 goto err;
 601             if (!EVP_DigestFinal_ex(&mctx, md, NULL))
 602                 goto err;
 603             if (!BN_bin2bn(md, mdsize, test))
 604                 goto err;
 605         }
 606         /* g=test^r0%p */
 607         if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))
 608             goto err;
 609         if (!BN_is_one(g))
 610             break;
 611         if (idx < 0 && !BN_add(test, test, BN_value_one()))
 612             goto err;
 613         h++;
 614         if (idx >= 0 && h > 0xffff)
 615             goto err;
 616     }
 617
 618     if (!BN_GENCB_call(cb, 3, 1))
 619         goto err;
 620
 621     ok = 1;
 622  err:
 623     if (ok == 1) {
 624         if (p != ret->p) {
 625             BN_free(ret->p);
 626             ret->p = BN_dup(p);
 627         }
 628         if (q != ret->q) {
 629             BN_free(ret->q);
 630             ret->q = BN_dup(q);
 631         }
 632         BN_free(ret->g);
 633         ret->g = BN_dup(g);
 634         if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {
 635             ok = -1;
 636             goto err;
 637         }
 638         if (counter_ret != NULL)
 639             *counter_ret = counter;
 640         if (h_ret != NULL)
 641             *h_ret = h;
 642     }
 643     OPENSSL_free(seed);
 644     if (seed_out != seed_tmp)
 645         OPENSSL_free(seed_tmp);
 646     if (ctx)
 647         BN_CTX_end(ctx);
 648     BN_CTX_free(ctx);
 649     BN_MONT_CTX_free(mont);
 650     EVP_MD_CTX_cleanup(&mctx);
 651     return ok;
 652 }
 653
 654 int dsa_paramgen_check_g(DSA *dsa)
 655 {
 656     BN_CTX *ctx;
 657     BIGNUM *tmp;
 658     BN_MONT_CTX *mont = NULL;
 659     int rv = -1;
 660     ctx = BN_CTX_new();
 661     if (!ctx)
 662         return -1;
 663     BN_CTX_start(ctx);
 664     if (BN_cmp(dsa->g, BN_value_one()) <= 0)
 665         return 0;
 666     if (BN_cmp(dsa->g, dsa->p) >= 0)
 667         return 0;
 668     tmp = BN_CTX_get(ctx);
 669     if (!tmp)
 670         goto err;
 671     if ((mont = BN_MONT_CTX_new()) == NULL)
 672         goto err;
 673     if (!BN_MONT_CTX_set(mont, dsa->p, ctx))
 674         goto err;
 675     /* Work out g^q mod p */
 676     if (!BN_mod_exp_mont(tmp, dsa->g, dsa->q, dsa->p, ctx, mont))
 677         goto err;
 678     if (!BN_cmp(tmp, BN_value_one()))
 679         rv = 1;
 680     else
 681         rv = 0;
 682  err:
 683     BN_CTX_end(ctx);
 684     BN_MONT_CTX_free(mont);
 685     BN_CTX_free(ctx);
 686     return rv;
 687
 688 }