155714Skris/* crypto/dsa/dsa_gen.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 8280297Sjkim * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15280297Sjkim * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 22280297Sjkim * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 37280297Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40280297Sjkim * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 52280297Sjkim * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 5855714Skris 5955714Skris#undef GENUINE_DSA 6055714Skris 6155714Skris#ifdef GENUINE_DSA 62280297Sjkim/* 63280297Sjkim * Parameter generation follows the original release of FIPS PUB 186, 64280297Sjkim * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) 65280297Sjkim */ 66280297Sjkim# define HASH EVP_sha() 6755714Skris#else 68280297Sjkim/* 69280297Sjkim * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186, 70280297Sjkim * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB 71280297Sjkim * 180-1) 72280297Sjkim */ 73280297Sjkim# define HASH EVP_sha1() 74280297Sjkim#endif 7555714Skris 76160814Ssimon#include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */ 77160814Ssimon 78109998Smarkm#ifndef OPENSSL_NO_SHA 7959191Skris 80280297Sjkim# include <stdio.h> 81280297Sjkim# include "cryptlib.h" 82280297Sjkim# include <openssl/evp.h> 83280297Sjkim# include <openssl/bn.h> 84280297Sjkim# include <openssl/rand.h> 85280297Sjkim# include <openssl/sha.h> 86280297Sjkim# include "dsa_locl.h" 8755714Skris 88280297Sjkim# ifdef OPENSSL_FIPS 89290207Sjkim/* Workaround bug in prototype */ 90290207Sjkim# define fips_dsa_builtin_paramgen2 fips_dsa_paramgen_bad 91280297Sjkim# include <openssl/fips.h> 92280297Sjkim# endif 93194206Ssimon 94160814Ssimonint DSA_generate_parameters_ex(DSA *ret, int bits, 95280297Sjkim const unsigned char *seed_in, int seed_len, 96280297Sjkim int *counter_ret, unsigned long *h_ret, 97280297Sjkim BN_GENCB *cb) 98280297Sjkim{ 99280297Sjkim# ifdef OPENSSL_FIPS 100280297Sjkim if (FIPS_mode() && !(ret->meth->flags & DSA_FLAG_FIPS_METHOD) 101280297Sjkim && !(ret->flags & DSA_FLAG_NON_FIPS_ALLOW)) { 102280297Sjkim DSAerr(DSA_F_DSA_GENERATE_PARAMETERS_EX, DSA_R_NON_FIPS_DSA_METHOD); 103280297Sjkim return 0; 104280297Sjkim } 105280297Sjkim# endif 106280297Sjkim if (ret->meth->dsa_paramgen) 107280297Sjkim return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len, 108280297Sjkim counter_ret, h_ret, cb); 109280297Sjkim# ifdef OPENSSL_FIPS 110280297Sjkim else if (FIPS_mode()) { 111280297Sjkim return FIPS_dsa_generate_parameters_ex(ret, bits, 112280297Sjkim seed_in, seed_len, 113280297Sjkim counter_ret, h_ret, cb); 114280297Sjkim } 115280297Sjkim# endif 116280297Sjkim else { 117291719Sjkim const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1(); 118291719Sjkim size_t qbits = EVP_MD_size(evpmd) * 8; 119238405Sjkim 120280297Sjkim return dsa_builtin_paramgen(ret, bits, qbits, evpmd, 121280297Sjkim seed_in, seed_len, NULL, counter_ret, 122280297Sjkim h_ret, cb); 123280297Sjkim } 124280297Sjkim} 125160814Ssimon 126238405Sjkimint dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, 127280297Sjkim const EVP_MD *evpmd, const unsigned char *seed_in, 128280297Sjkim size_t seed_len, unsigned char *seed_out, 129280297Sjkim int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) 130280297Sjkim{ 131280297Sjkim int ok = 0; 132280297Sjkim unsigned char seed[SHA256_DIGEST_LENGTH]; 133280297Sjkim unsigned char md[SHA256_DIGEST_LENGTH]; 134280297Sjkim unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; 135280297Sjkim BIGNUM *r0, *W, *X, *c, *test; 136280297Sjkim BIGNUM *g = NULL, *q = NULL, *p = NULL; 137280297Sjkim BN_MONT_CTX *mont = NULL; 138280297Sjkim int i, k, n = 0, m = 0, qsize = qbits >> 3; 139280297Sjkim int counter = 0; 140280297Sjkim int r = 0; 141280297Sjkim BN_CTX *ctx = NULL; 142280297Sjkim unsigned int h = 2; 14355714Skris 144280297Sjkim if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH && 145280297Sjkim qsize != SHA256_DIGEST_LENGTH) 146280297Sjkim /* invalid q size */ 147280297Sjkim return 0; 14855714Skris 149280297Sjkim if (evpmd == NULL) 150280297Sjkim /* use SHA1 as default */ 151280297Sjkim evpmd = EVP_sha1(); 152238405Sjkim 153280297Sjkim if (bits < 512) 154280297Sjkim bits = 512; 155238405Sjkim 156280297Sjkim bits = (bits + 63) / 64 * 64; 157238405Sjkim 158280297Sjkim /* 159280297Sjkim * NB: seed_len == 0 is special case: copy generated seed to seed_in if 160280297Sjkim * it is not NULL. 161280297Sjkim */ 162280297Sjkim if (seed_len && (seed_len < (size_t)qsize)) 163280297Sjkim seed_in = NULL; /* seed buffer too small -- ignore */ 164280297Sjkim if (seed_len > (size_t)qsize) 165280297Sjkim seed_len = qsize; /* App. 2.2 of FIPS PUB 186 allows larger 166280297Sjkim * SEED, but our internal buffers are 167280297Sjkim * restricted to 160 bits */ 168280297Sjkim if (seed_in != NULL) 169280297Sjkim memcpy(seed, seed_in, seed_len); 17055714Skris 171291719Sjkim if ((mont = BN_MONT_CTX_new()) == NULL) 172280297Sjkim goto err; 17355714Skris 174291719Sjkim if ((ctx = BN_CTX_new()) == NULL) 175280297Sjkim goto err; 17655714Skris 177280297Sjkim BN_CTX_start(ctx); 178291719Sjkim 179280297Sjkim r0 = BN_CTX_get(ctx); 180280297Sjkim g = BN_CTX_get(ctx); 181280297Sjkim W = BN_CTX_get(ctx); 182280297Sjkim q = BN_CTX_get(ctx); 183280297Sjkim X = BN_CTX_get(ctx); 184280297Sjkim c = BN_CTX_get(ctx); 185280297Sjkim p = BN_CTX_get(ctx); 186280297Sjkim test = BN_CTX_get(ctx); 18755714Skris 188306198Sjkim if (test == NULL) 189306198Sjkim goto err; 190306198Sjkim 191280297Sjkim if (!BN_lshift(test, BN_value_one(), bits - 1)) 192280297Sjkim goto err; 19355714Skris 194280297Sjkim for (;;) { 195280297Sjkim for (;;) { /* find q */ 196280297Sjkim int seed_is_random; 19759191Skris 198280297Sjkim /* step 1 */ 199280297Sjkim if (!BN_GENCB_call(cb, 0, m++)) 200280297Sjkim goto err; 20155714Skris 202291719Sjkim if (!seed_len || !seed_in) { 203306198Sjkim if (RAND_bytes(seed, qsize) <= 0) 204284283Sjkim goto err; 205280297Sjkim seed_is_random = 1; 206280297Sjkim } else { 207280297Sjkim seed_is_random = 0; 208280297Sjkim seed_len = 0; /* use random seed if 'seed_in' turns out to 209280297Sjkim * be bad */ 210280297Sjkim } 211280297Sjkim memcpy(buf, seed, qsize); 212280297Sjkim memcpy(buf2, seed, qsize); 213280297Sjkim /* precompute "SEED + 1" for step 7: */ 214280297Sjkim for (i = qsize - 1; i >= 0; i--) { 215280297Sjkim buf[i]++; 216280297Sjkim if (buf[i] != 0) 217280297Sjkim break; 218280297Sjkim } 21955714Skris 220280297Sjkim /* step 2 */ 221280297Sjkim if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 222280297Sjkim goto err; 223280297Sjkim if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 224280297Sjkim goto err; 225280297Sjkim for (i = 0; i < qsize; i++) 226280297Sjkim md[i] ^= buf2[i]; 22755714Skris 228280297Sjkim /* step 3 */ 229280297Sjkim md[0] |= 0x80; 230280297Sjkim md[qsize - 1] |= 0x01; 231280297Sjkim if (!BN_bin2bn(md, qsize, q)) 232280297Sjkim goto err; 23355714Skris 234280297Sjkim /* step 4 */ 235280297Sjkim r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, 236280297Sjkim seed_is_random, cb); 237280297Sjkim if (r > 0) 238280297Sjkim break; 239280297Sjkim if (r != 0) 240280297Sjkim goto err; 24159191Skris 242280297Sjkim /* do a callback call */ 243280297Sjkim /* step 5 */ 244280297Sjkim } 24555714Skris 246280297Sjkim if (!BN_GENCB_call(cb, 2, 0)) 247280297Sjkim goto err; 248280297Sjkim if (!BN_GENCB_call(cb, 3, 0)) 249280297Sjkim goto err; 25055714Skris 251280297Sjkim /* step 6 */ 252280297Sjkim counter = 0; 253280297Sjkim /* "offset = 2" */ 25455714Skris 255280297Sjkim n = (bits - 1) / 160; 25655714Skris 257280297Sjkim for (;;) { 258280297Sjkim if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 259280297Sjkim goto err; 26059191Skris 261280297Sjkim /* step 7 */ 262280297Sjkim BN_zero(W); 263280297Sjkim /* now 'buf' contains "SEED + offset - 1" */ 264280297Sjkim for (k = 0; k <= n; k++) { 265280297Sjkim /* 266280297Sjkim * obtain "SEED + offset + k" by incrementing: 267280297Sjkim */ 268280297Sjkim for (i = qsize - 1; i >= 0; i--) { 269280297Sjkim buf[i]++; 270280297Sjkim if (buf[i] != 0) 271280297Sjkim break; 272280297Sjkim } 27355714Skris 274280297Sjkim if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) 275280297Sjkim goto err; 27655714Skris 277280297Sjkim /* step 8 */ 278280297Sjkim if (!BN_bin2bn(md, qsize, r0)) 279280297Sjkim goto err; 280280297Sjkim if (!BN_lshift(r0, r0, (qsize << 3) * k)) 281280297Sjkim goto err; 282280297Sjkim if (!BN_add(W, W, r0)) 283280297Sjkim goto err; 284280297Sjkim } 28555714Skris 286280297Sjkim /* more of step 8 */ 287280297Sjkim if (!BN_mask_bits(W, bits - 1)) 288280297Sjkim goto err; 289280297Sjkim if (!BN_copy(X, W)) 290280297Sjkim goto err; 291280297Sjkim if (!BN_add(X, X, test)) 292280297Sjkim goto err; 29355714Skris 294280297Sjkim /* step 9 */ 295280297Sjkim if (!BN_lshift1(r0, q)) 296280297Sjkim goto err; 297280297Sjkim if (!BN_mod(c, X, r0, ctx)) 298280297Sjkim goto err; 299280297Sjkim if (!BN_sub(r0, c, BN_value_one())) 300280297Sjkim goto err; 301280297Sjkim if (!BN_sub(p, X, r0)) 302280297Sjkim goto err; 30355714Skris 304280297Sjkim /* step 10 */ 305280297Sjkim if (BN_cmp(p, test) >= 0) { 306280297Sjkim /* step 11 */ 307280297Sjkim r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 308280297Sjkim if (r > 0) 309280297Sjkim goto end; /* found it */ 310280297Sjkim if (r != 0) 311280297Sjkim goto err; 312280297Sjkim } 31355714Skris 314280297Sjkim /* step 13 */ 315280297Sjkim counter++; 316280297Sjkim /* "offset = offset + n + 1" */ 31755714Skris 318280297Sjkim /* step 14 */ 319280297Sjkim if (counter >= 4096) 320280297Sjkim break; 321280297Sjkim } 322280297Sjkim } 323280297Sjkim end: 324280297Sjkim if (!BN_GENCB_call(cb, 2, 1)) 325280297Sjkim goto err; 32655714Skris 327280297Sjkim /* We now need to generate g */ 328280297Sjkim /* Set r0=(p-1)/q */ 329280297Sjkim if (!BN_sub(test, p, BN_value_one())) 330280297Sjkim goto err; 331280297Sjkim if (!BN_div(r0, NULL, test, q, ctx)) 332280297Sjkim goto err; 33355714Skris 334280297Sjkim if (!BN_set_word(test, h)) 335280297Sjkim goto err; 336280297Sjkim if (!BN_MONT_CTX_set(mont, p, ctx)) 337280297Sjkim goto err; 33855714Skris 339280297Sjkim for (;;) { 340280297Sjkim /* g=test^r0%p */ 341280297Sjkim if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 342280297Sjkim goto err; 343280297Sjkim if (!BN_is_one(g)) 344280297Sjkim break; 345280297Sjkim if (!BN_add(test, test, BN_value_one())) 346280297Sjkim goto err; 347280297Sjkim h++; 348280297Sjkim } 34955714Skris 350280297Sjkim if (!BN_GENCB_call(cb, 3, 1)) 351280297Sjkim goto err; 35255714Skris 353280297Sjkim ok = 1; 354280297Sjkim err: 355280297Sjkim if (ok) { 356280297Sjkim if (ret->p) 357280297Sjkim BN_free(ret->p); 358280297Sjkim if (ret->q) 359280297Sjkim BN_free(ret->q); 360280297Sjkim if (ret->g) 361280297Sjkim BN_free(ret->g); 362280297Sjkim ret->p = BN_dup(p); 363280297Sjkim ret->q = BN_dup(q); 364280297Sjkim ret->g = BN_dup(g); 365280297Sjkim if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 366280297Sjkim ok = 0; 367280297Sjkim goto err; 368280297Sjkim } 369280297Sjkim if (counter_ret != NULL) 370280297Sjkim *counter_ret = counter; 371280297Sjkim if (h_ret != NULL) 372280297Sjkim *h_ret = h; 373280297Sjkim if (seed_out) 374280297Sjkim memcpy(seed_out, seed, qsize); 375280297Sjkim } 376280297Sjkim if (ctx) { 377280297Sjkim BN_CTX_end(ctx); 378280297Sjkim BN_CTX_free(ctx); 379280297Sjkim } 380280297Sjkim if (mont != NULL) 381280297Sjkim BN_MONT_CTX_free(mont); 382280297Sjkim return ok; 383280297Sjkim} 384290207Sjkim 385290207Sjkim# ifdef OPENSSL_FIPS 386290207Sjkim# undef fips_dsa_builtin_paramgen2 387290207Sjkimextern int fips_dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, 388290207Sjkim const EVP_MD *evpmd, 389290207Sjkim const unsigned char *seed_in, 390290207Sjkim size_t seed_len, int idx, 391290207Sjkim unsigned char *seed_out, 392290207Sjkim int *counter_ret, unsigned long *h_ret, 393290207Sjkim BN_GENCB *cb); 394290207Sjkim# endif 395290207Sjkim 396290207Sjkim/* 397290207Sjkim * This is a parameter generation algorithm for the DSA2 algorithm as 398290207Sjkim * described in FIPS 186-3. 399290207Sjkim */ 400290207Sjkim 401290207Sjkimint dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, 402290207Sjkim const EVP_MD *evpmd, const unsigned char *seed_in, 403290207Sjkim size_t seed_len, int idx, unsigned char *seed_out, 404290207Sjkim int *counter_ret, unsigned long *h_ret, 405290207Sjkim BN_GENCB *cb) 406290207Sjkim{ 407290207Sjkim int ok = -1; 408290207Sjkim unsigned char *seed = NULL, *seed_tmp = NULL; 409290207Sjkim unsigned char md[EVP_MAX_MD_SIZE]; 410290207Sjkim int mdsize; 411290207Sjkim BIGNUM *r0, *W, *X, *c, *test; 412290207Sjkim BIGNUM *g = NULL, *q = NULL, *p = NULL; 413290207Sjkim BN_MONT_CTX *mont = NULL; 414290207Sjkim int i, k, n = 0, m = 0, qsize = N >> 3; 415290207Sjkim int counter = 0; 416290207Sjkim int r = 0; 417290207Sjkim BN_CTX *ctx = NULL; 418290207Sjkim EVP_MD_CTX mctx; 419290207Sjkim unsigned int h = 2; 420290207Sjkim 421290207Sjkim# ifdef OPENSSL_FIPS 422290207Sjkim 423290207Sjkim if (FIPS_mode()) 424290207Sjkim return fips_dsa_builtin_paramgen2(ret, L, N, evpmd, 425290207Sjkim seed_in, seed_len, idx, 426290207Sjkim seed_out, counter_ret, h_ret, cb); 427290207Sjkim# endif 428290207Sjkim 429290207Sjkim EVP_MD_CTX_init(&mctx); 430290207Sjkim 431290207Sjkim if (evpmd == NULL) { 432290207Sjkim if (N == 160) 433290207Sjkim evpmd = EVP_sha1(); 434290207Sjkim else if (N == 224) 435290207Sjkim evpmd = EVP_sha224(); 436290207Sjkim else 437290207Sjkim evpmd = EVP_sha256(); 438290207Sjkim } 439290207Sjkim 440290207Sjkim mdsize = EVP_MD_size(evpmd); 441290207Sjkim /* If unverificable g generation only don't need seed */ 442290207Sjkim if (!ret->p || !ret->q || idx >= 0) { 443290207Sjkim if (seed_len == 0) 444290207Sjkim seed_len = mdsize; 445290207Sjkim 446290207Sjkim seed = OPENSSL_malloc(seed_len); 447290207Sjkim 448290207Sjkim if (seed_out) 449290207Sjkim seed_tmp = seed_out; 450290207Sjkim else 451290207Sjkim seed_tmp = OPENSSL_malloc(seed_len); 452290207Sjkim 453290207Sjkim if (!seed || !seed_tmp) 454290207Sjkim goto err; 455290207Sjkim 456290207Sjkim if (seed_in) 457290207Sjkim memcpy(seed, seed_in, seed_len); 458290207Sjkim 459290207Sjkim } 460290207Sjkim 461290207Sjkim if ((ctx = BN_CTX_new()) == NULL) 462290207Sjkim goto err; 463290207Sjkim 464290207Sjkim if ((mont = BN_MONT_CTX_new()) == NULL) 465290207Sjkim goto err; 466290207Sjkim 467290207Sjkim BN_CTX_start(ctx); 468290207Sjkim r0 = BN_CTX_get(ctx); 469290207Sjkim g = BN_CTX_get(ctx); 470290207Sjkim W = BN_CTX_get(ctx); 471290207Sjkim X = BN_CTX_get(ctx); 472290207Sjkim c = BN_CTX_get(ctx); 473290207Sjkim test = BN_CTX_get(ctx); 474290207Sjkim 475290207Sjkim /* if p, q already supplied generate g only */ 476290207Sjkim if (ret->p && ret->q) { 477290207Sjkim p = ret->p; 478290207Sjkim q = ret->q; 479290207Sjkim if (idx >= 0) 480290207Sjkim memcpy(seed_tmp, seed, seed_len); 481290207Sjkim goto g_only; 482290207Sjkim } else { 483290207Sjkim p = BN_CTX_get(ctx); 484290207Sjkim q = BN_CTX_get(ctx); 485290207Sjkim } 486290207Sjkim 487290207Sjkim if (!BN_lshift(test, BN_value_one(), L - 1)) 488290207Sjkim goto err; 489290207Sjkim for (;;) { 490290207Sjkim for (;;) { /* find q */ 491290207Sjkim unsigned char *pmd; 492290207Sjkim /* step 1 */ 493290207Sjkim if (!BN_GENCB_call(cb, 0, m++)) 494290207Sjkim goto err; 495290207Sjkim 496290207Sjkim if (!seed_in) { 497306198Sjkim if (RAND_bytes(seed, seed_len) <= 0) 498290207Sjkim goto err; 499290207Sjkim } 500290207Sjkim /* step 2 */ 501290207Sjkim if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) 502290207Sjkim goto err; 503290207Sjkim /* Take least significant bits of md */ 504290207Sjkim if (mdsize > qsize) 505290207Sjkim pmd = md + mdsize - qsize; 506290207Sjkim else 507290207Sjkim pmd = md; 508290207Sjkim 509290207Sjkim if (mdsize < qsize) 510290207Sjkim memset(md + mdsize, 0, qsize - mdsize); 511290207Sjkim 512290207Sjkim /* step 3 */ 513290207Sjkim pmd[0] |= 0x80; 514290207Sjkim pmd[qsize - 1] |= 0x01; 515290207Sjkim if (!BN_bin2bn(pmd, qsize, q)) 516290207Sjkim goto err; 517290207Sjkim 518290207Sjkim /* step 4 */ 519290207Sjkim r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, 520290207Sjkim seed_in ? 1 : 0, cb); 521290207Sjkim if (r > 0) 522290207Sjkim break; 523290207Sjkim if (r != 0) 524290207Sjkim goto err; 525290207Sjkim /* Provided seed didn't produce a prime: error */ 526290207Sjkim if (seed_in) { 527290207Sjkim ok = 0; 528290207Sjkim DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME); 529290207Sjkim goto err; 530290207Sjkim } 531290207Sjkim 532290207Sjkim /* do a callback call */ 533290207Sjkim /* step 5 */ 534290207Sjkim } 535290207Sjkim /* Copy seed to seed_out before we mess with it */ 536290207Sjkim if (seed_out) 537290207Sjkim memcpy(seed_out, seed, seed_len); 538290207Sjkim 539290207Sjkim if (!BN_GENCB_call(cb, 2, 0)) 540290207Sjkim goto err; 541290207Sjkim if (!BN_GENCB_call(cb, 3, 0)) 542290207Sjkim goto err; 543290207Sjkim 544290207Sjkim /* step 6 */ 545290207Sjkim counter = 0; 546290207Sjkim /* "offset = 1" */ 547290207Sjkim 548290207Sjkim n = (L - 1) / (mdsize << 3); 549290207Sjkim 550290207Sjkim for (;;) { 551290207Sjkim if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 552290207Sjkim goto err; 553290207Sjkim 554290207Sjkim /* step 7 */ 555290207Sjkim BN_zero(W); 556290207Sjkim /* now 'buf' contains "SEED + offset - 1" */ 557290207Sjkim for (k = 0; k <= n; k++) { 558290207Sjkim /* 559290207Sjkim * obtain "SEED + offset + k" by incrementing: 560290207Sjkim */ 561290207Sjkim for (i = seed_len - 1; i >= 0; i--) { 562290207Sjkim seed[i]++; 563290207Sjkim if (seed[i] != 0) 564290207Sjkim break; 565290207Sjkim } 566290207Sjkim 567290207Sjkim if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) 568290207Sjkim goto err; 569290207Sjkim 570290207Sjkim /* step 8 */ 571290207Sjkim if (!BN_bin2bn(md, mdsize, r0)) 572290207Sjkim goto err; 573290207Sjkim if (!BN_lshift(r0, r0, (mdsize << 3) * k)) 574290207Sjkim goto err; 575290207Sjkim if (!BN_add(W, W, r0)) 576290207Sjkim goto err; 577290207Sjkim } 578290207Sjkim 579290207Sjkim /* more of step 8 */ 580290207Sjkim if (!BN_mask_bits(W, L - 1)) 581290207Sjkim goto err; 582290207Sjkim if (!BN_copy(X, W)) 583290207Sjkim goto err; 584290207Sjkim if (!BN_add(X, X, test)) 585290207Sjkim goto err; 586290207Sjkim 587290207Sjkim /* step 9 */ 588290207Sjkim if (!BN_lshift1(r0, q)) 589290207Sjkim goto err; 590290207Sjkim if (!BN_mod(c, X, r0, ctx)) 591290207Sjkim goto err; 592290207Sjkim if (!BN_sub(r0, c, BN_value_one())) 593290207Sjkim goto err; 594290207Sjkim if (!BN_sub(p, X, r0)) 595290207Sjkim goto err; 596290207Sjkim 597290207Sjkim /* step 10 */ 598290207Sjkim if (BN_cmp(p, test) >= 0) { 599290207Sjkim /* step 11 */ 600290207Sjkim r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 601290207Sjkim if (r > 0) 602290207Sjkim goto end; /* found it */ 603290207Sjkim if (r != 0) 604290207Sjkim goto err; 605290207Sjkim } 606290207Sjkim 607290207Sjkim /* step 13 */ 608290207Sjkim counter++; 609290207Sjkim /* "offset = offset + n + 1" */ 610290207Sjkim 611290207Sjkim /* step 14 */ 612290207Sjkim if (counter >= (int)(4 * L)) 613290207Sjkim break; 614290207Sjkim } 615290207Sjkim if (seed_in) { 616290207Sjkim ok = 0; 617290207Sjkim DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); 618290207Sjkim goto err; 619290207Sjkim } 620290207Sjkim } 621290207Sjkim end: 622290207Sjkim if (!BN_GENCB_call(cb, 2, 1)) 623290207Sjkim goto err; 624290207Sjkim 625290207Sjkim g_only: 626290207Sjkim 627290207Sjkim /* We now need to generate g */ 628290207Sjkim /* Set r0=(p-1)/q */ 629290207Sjkim if (!BN_sub(test, p, BN_value_one())) 630290207Sjkim goto err; 631290207Sjkim if (!BN_div(r0, NULL, test, q, ctx)) 632290207Sjkim goto err; 633290207Sjkim 634290207Sjkim if (idx < 0) { 635290207Sjkim if (!BN_set_word(test, h)) 636290207Sjkim goto err; 637290207Sjkim } else 638290207Sjkim h = 1; 639290207Sjkim if (!BN_MONT_CTX_set(mont, p, ctx)) 640290207Sjkim goto err; 641290207Sjkim 642290207Sjkim for (;;) { 643290207Sjkim static const unsigned char ggen[4] = { 0x67, 0x67, 0x65, 0x6e }; 644290207Sjkim if (idx >= 0) { 645290207Sjkim md[0] = idx & 0xff; 646290207Sjkim md[1] = (h >> 8) & 0xff; 647290207Sjkim md[2] = h & 0xff; 648290207Sjkim if (!EVP_DigestInit_ex(&mctx, evpmd, NULL)) 649290207Sjkim goto err; 650290207Sjkim if (!EVP_DigestUpdate(&mctx, seed_tmp, seed_len)) 651290207Sjkim goto err; 652290207Sjkim if (!EVP_DigestUpdate(&mctx, ggen, sizeof(ggen))) 653290207Sjkim goto err; 654290207Sjkim if (!EVP_DigestUpdate(&mctx, md, 3)) 655290207Sjkim goto err; 656290207Sjkim if (!EVP_DigestFinal_ex(&mctx, md, NULL)) 657290207Sjkim goto err; 658290207Sjkim if (!BN_bin2bn(md, mdsize, test)) 659290207Sjkim goto err; 660290207Sjkim } 661290207Sjkim /* g=test^r0%p */ 662290207Sjkim if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 663290207Sjkim goto err; 664290207Sjkim if (!BN_is_one(g)) 665290207Sjkim break; 666290207Sjkim if (idx < 0 && !BN_add(test, test, BN_value_one())) 667290207Sjkim goto err; 668290207Sjkim h++; 669290207Sjkim if (idx >= 0 && h > 0xffff) 670290207Sjkim goto err; 671290207Sjkim } 672290207Sjkim 673290207Sjkim if (!BN_GENCB_call(cb, 3, 1)) 674290207Sjkim goto err; 675290207Sjkim 676290207Sjkim ok = 1; 677290207Sjkim err: 678290207Sjkim if (ok == 1) { 679290207Sjkim if (p != ret->p) { 680290207Sjkim if (ret->p) 681290207Sjkim BN_free(ret->p); 682290207Sjkim ret->p = BN_dup(p); 683290207Sjkim } 684290207Sjkim if (q != ret->q) { 685290207Sjkim if (ret->q) 686290207Sjkim BN_free(ret->q); 687290207Sjkim ret->q = BN_dup(q); 688290207Sjkim } 689290207Sjkim if (ret->g) 690290207Sjkim BN_free(ret->g); 691290207Sjkim ret->g = BN_dup(g); 692290207Sjkim if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 693290207Sjkim ok = -1; 694290207Sjkim goto err; 695290207Sjkim } 696290207Sjkim if (counter_ret != NULL) 697290207Sjkim *counter_ret = counter; 698290207Sjkim if (h_ret != NULL) 699290207Sjkim *h_ret = h; 700290207Sjkim } 701290207Sjkim if (seed) 702290207Sjkim OPENSSL_free(seed); 703290207Sjkim if (seed_out != seed_tmp) 704290207Sjkim OPENSSL_free(seed_tmp); 705290207Sjkim if (ctx) { 706290207Sjkim BN_CTX_end(ctx); 707290207Sjkim BN_CTX_free(ctx); 708290207Sjkim } 709290207Sjkim if (mont != NULL) 710290207Sjkim BN_MONT_CTX_free(mont); 711290207Sjkim EVP_MD_CTX_cleanup(&mctx); 712290207Sjkim return ok; 713290207Sjkim} 714290207Sjkim 715290207Sjkimint dsa_paramgen_check_g(DSA *dsa) 716290207Sjkim{ 717290207Sjkim BN_CTX *ctx; 718290207Sjkim BIGNUM *tmp; 719290207Sjkim BN_MONT_CTX *mont = NULL; 720290207Sjkim int rv = -1; 721290207Sjkim ctx = BN_CTX_new(); 722290207Sjkim if (!ctx) 723290207Sjkim return -1; 724290207Sjkim BN_CTX_start(ctx); 725290207Sjkim if (BN_cmp(dsa->g, BN_value_one()) <= 0) 726290207Sjkim return 0; 727290207Sjkim if (BN_cmp(dsa->g, dsa->p) >= 0) 728290207Sjkim return 0; 729290207Sjkim tmp = BN_CTX_get(ctx); 730290207Sjkim if (!tmp) 731290207Sjkim goto err; 732290207Sjkim if ((mont = BN_MONT_CTX_new()) == NULL) 733290207Sjkim goto err; 734290207Sjkim if (!BN_MONT_CTX_set(mont, dsa->p, ctx)) 735290207Sjkim goto err; 736290207Sjkim /* Work out g^q mod p */ 737290207Sjkim if (!BN_mod_exp_mont(tmp, dsa->g, dsa->q, dsa->p, ctx, mont)) 738290207Sjkim goto err; 739290207Sjkim if (!BN_cmp(tmp, BN_value_one())) 740290207Sjkim rv = 1; 741290207Sjkim else 742290207Sjkim rv = 0; 743290207Sjkim err: 744290207Sjkim BN_CTX_end(ctx); 745290207Sjkim if (mont) 746290207Sjkim BN_MONT_CTX_free(mont); 747290207Sjkim BN_CTX_free(ctx); 748290207Sjkim return rv; 749290207Sjkim 750290207Sjkim} 751160814Ssimon#endif 752