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. 8280304Sjkim * 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). 15280304Sjkim * 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. 22280304Sjkim * 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 :-). 37280304Sjkim * 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)" 40280304Sjkim * 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. 52280304Sjkim * 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 62280304Sjkim/* 63280304Sjkim * Parameter generation follows the original release of FIPS PUB 186, 64280304Sjkim * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) 65280304Sjkim */ 66280304Sjkim# define HASH EVP_sha() 6755714Skris#else 68280304Sjkim/* 69280304Sjkim * Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186, 70280304Sjkim * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in FIPS PUB 71280304Sjkim * 180-1) 72280304Sjkim */ 73280304Sjkim# define HASH EVP_sha1() 74280304Sjkim#endif 7555714Skris 76160814Ssimon#include <openssl/opensslconf.h> /* To see if OPENSSL_NO_SHA is defined */ 77160814Ssimon 78109998Smarkm#ifndef OPENSSL_NO_SHA 7959191Skris 80280304Sjkim# include <stdio.h> 81280304Sjkim# include "cryptlib.h" 82280304Sjkim# include <openssl/evp.h> 83280304Sjkim# include <openssl/bn.h> 84280304Sjkim# include <openssl/rand.h> 85280304Sjkim# include <openssl/sha.h> 86280304Sjkim# include "dsa_locl.h" 8755714Skris 88280304Sjkim# ifdef OPENSSL_FIPS 89280304Sjkim# include <openssl/fips.h> 90280304Sjkim# endif 91194206Ssimon 92160814Ssimonint DSA_generate_parameters_ex(DSA *ret, int bits, 93280304Sjkim const unsigned char *seed_in, int seed_len, 94280304Sjkim int *counter_ret, unsigned long *h_ret, 95280304Sjkim BN_GENCB *cb) 96280304Sjkim{ 97280304Sjkim# ifdef OPENSSL_FIPS 98280304Sjkim if (FIPS_mode() && !(ret->meth->flags & DSA_FLAG_FIPS_METHOD) 99280304Sjkim && !(ret->flags & DSA_FLAG_NON_FIPS_ALLOW)) { 100280304Sjkim DSAerr(DSA_F_DSA_GENERATE_PARAMETERS_EX, DSA_R_NON_FIPS_DSA_METHOD); 101280304Sjkim return 0; 102280304Sjkim } 103280304Sjkim# endif 104280304Sjkim if (ret->meth->dsa_paramgen) 105280304Sjkim return ret->meth->dsa_paramgen(ret, bits, seed_in, seed_len, 106280304Sjkim counter_ret, h_ret, cb); 107280304Sjkim# ifdef OPENSSL_FIPS 108280304Sjkim else if (FIPS_mode()) { 109280304Sjkim return FIPS_dsa_generate_parameters_ex(ret, bits, 110280304Sjkim seed_in, seed_len, 111280304Sjkim counter_ret, h_ret, cb); 112280304Sjkim } 113280304Sjkim# endif 114280304Sjkim else { 115291721Sjkim const EVP_MD *evpmd = bits >= 2048 ? EVP_sha256() : EVP_sha1(); 116291721Sjkim size_t qbits = EVP_MD_size(evpmd) * 8; 117238405Sjkim 118280304Sjkim return dsa_builtin_paramgen(ret, bits, qbits, evpmd, 119280304Sjkim seed_in, seed_len, NULL, counter_ret, 120280304Sjkim h_ret, cb); 121280304Sjkim } 122280304Sjkim} 123160814Ssimon 124238405Sjkimint dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, 125280304Sjkim const EVP_MD *evpmd, const unsigned char *seed_in, 126280304Sjkim size_t seed_len, unsigned char *seed_out, 127280304Sjkim int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) 128280304Sjkim{ 129280304Sjkim int ok = 0; 130280304Sjkim unsigned char seed[SHA256_DIGEST_LENGTH]; 131280304Sjkim unsigned char md[SHA256_DIGEST_LENGTH]; 132280304Sjkim unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; 133280304Sjkim BIGNUM *r0, *W, *X, *c, *test; 134280304Sjkim BIGNUM *g = NULL, *q = NULL, *p = NULL; 135280304Sjkim BN_MONT_CTX *mont = NULL; 136280304Sjkim int i, k, n = 0, m = 0, qsize = qbits >> 3; 137280304Sjkim int counter = 0; 138280304Sjkim int r = 0; 139280304Sjkim BN_CTX *ctx = NULL; 140280304Sjkim unsigned int h = 2; 14155714Skris 142280304Sjkim if (qsize != SHA_DIGEST_LENGTH && qsize != SHA224_DIGEST_LENGTH && 143280304Sjkim qsize != SHA256_DIGEST_LENGTH) 144280304Sjkim /* invalid q size */ 145280304Sjkim return 0; 14655714Skris 147280304Sjkim if (evpmd == NULL) 148280304Sjkim /* use SHA1 as default */ 149280304Sjkim evpmd = EVP_sha1(); 150238405Sjkim 151280304Sjkim if (bits < 512) 152280304Sjkim bits = 512; 153238405Sjkim 154280304Sjkim bits = (bits + 63) / 64 * 64; 155238405Sjkim 156280304Sjkim /* 157280304Sjkim * NB: seed_len == 0 is special case: copy generated seed to seed_in if 158280304Sjkim * it is not NULL. 159280304Sjkim */ 160280304Sjkim if (seed_len && (seed_len < (size_t)qsize)) 161280304Sjkim seed_in = NULL; /* seed buffer too small -- ignore */ 162280304Sjkim if (seed_len > (size_t)qsize) 163280304Sjkim seed_len = qsize; /* App. 2.2 of FIPS PUB 186 allows larger 164280304Sjkim * SEED, but our internal buffers are 165280304Sjkim * restricted to 160 bits */ 166280304Sjkim if (seed_in != NULL) 167280304Sjkim memcpy(seed, seed_in, seed_len); 16855714Skris 169291721Sjkim if ((mont = BN_MONT_CTX_new()) == NULL) 170280304Sjkim goto err; 17155714Skris 172291721Sjkim if ((ctx = BN_CTX_new()) == NULL) 173280304Sjkim goto err; 17455714Skris 175280304Sjkim BN_CTX_start(ctx); 176291721Sjkim 177280304Sjkim r0 = BN_CTX_get(ctx); 178280304Sjkim g = BN_CTX_get(ctx); 179280304Sjkim W = BN_CTX_get(ctx); 180280304Sjkim q = BN_CTX_get(ctx); 181280304Sjkim X = BN_CTX_get(ctx); 182280304Sjkim c = BN_CTX_get(ctx); 183280304Sjkim p = BN_CTX_get(ctx); 184280304Sjkim test = BN_CTX_get(ctx); 18555714Skris 186280304Sjkim if (!BN_lshift(test, BN_value_one(), bits - 1)) 187280304Sjkim goto err; 18855714Skris 189280304Sjkim for (;;) { 190280304Sjkim for (;;) { /* find q */ 191280304Sjkim int seed_is_random; 19259191Skris 193280304Sjkim /* step 1 */ 194280304Sjkim if (!BN_GENCB_call(cb, 0, m++)) 195280304Sjkim goto err; 19655714Skris 197291721Sjkim if (!seed_len || !seed_in) { 198284285Sjkim if (RAND_pseudo_bytes(seed, qsize) < 0) 199284285Sjkim goto err; 200280304Sjkim seed_is_random = 1; 201280304Sjkim } else { 202280304Sjkim seed_is_random = 0; 203280304Sjkim seed_len = 0; /* use random seed if 'seed_in' turns out to 204280304Sjkim * be bad */ 205280304Sjkim } 206280304Sjkim memcpy(buf, seed, qsize); 207280304Sjkim memcpy(buf2, seed, qsize); 208280304Sjkim /* precompute "SEED + 1" for step 7: */ 209280304Sjkim for (i = qsize - 1; i >= 0; i--) { 210280304Sjkim buf[i]++; 211280304Sjkim if (buf[i] != 0) 212280304Sjkim break; 213280304Sjkim } 21455714Skris 215280304Sjkim /* step 2 */ 216280304Sjkim if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL)) 217280304Sjkim goto err; 218280304Sjkim if (!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) 219280304Sjkim goto err; 220280304Sjkim for (i = 0; i < qsize; i++) 221280304Sjkim md[i] ^= buf2[i]; 22255714Skris 223280304Sjkim /* step 3 */ 224280304Sjkim md[0] |= 0x80; 225280304Sjkim md[qsize - 1] |= 0x01; 226280304Sjkim if (!BN_bin2bn(md, qsize, q)) 227280304Sjkim goto err; 22855714Skris 229280304Sjkim /* step 4 */ 230280304Sjkim r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, 231280304Sjkim seed_is_random, cb); 232280304Sjkim if (r > 0) 233280304Sjkim break; 234280304Sjkim if (r != 0) 235280304Sjkim goto err; 23659191Skris 237280304Sjkim /* do a callback call */ 238280304Sjkim /* step 5 */ 239280304Sjkim } 24055714Skris 241280304Sjkim if (!BN_GENCB_call(cb, 2, 0)) 242280304Sjkim goto err; 243280304Sjkim if (!BN_GENCB_call(cb, 3, 0)) 244280304Sjkim goto err; 24555714Skris 246280304Sjkim /* step 6 */ 247280304Sjkim counter = 0; 248280304Sjkim /* "offset = 2" */ 24955714Skris 250280304Sjkim n = (bits - 1) / 160; 25155714Skris 252280304Sjkim for (;;) { 253280304Sjkim if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) 254280304Sjkim goto err; 25559191Skris 256280304Sjkim /* step 7 */ 257280304Sjkim BN_zero(W); 258280304Sjkim /* now 'buf' contains "SEED + offset - 1" */ 259280304Sjkim for (k = 0; k <= n; k++) { 260280304Sjkim /* 261280304Sjkim * obtain "SEED + offset + k" by incrementing: 262280304Sjkim */ 263280304Sjkim for (i = qsize - 1; i >= 0; i--) { 264280304Sjkim buf[i]++; 265280304Sjkim if (buf[i] != 0) 266280304Sjkim break; 267280304Sjkim } 26855714Skris 269280304Sjkim if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) 270280304Sjkim goto err; 27155714Skris 272280304Sjkim /* step 8 */ 273280304Sjkim if (!BN_bin2bn(md, qsize, r0)) 274280304Sjkim goto err; 275280304Sjkim if (!BN_lshift(r0, r0, (qsize << 3) * k)) 276280304Sjkim goto err; 277280304Sjkim if (!BN_add(W, W, r0)) 278280304Sjkim goto err; 279280304Sjkim } 28055714Skris 281280304Sjkim /* more of step 8 */ 282280304Sjkim if (!BN_mask_bits(W, bits - 1)) 283280304Sjkim goto err; 284280304Sjkim if (!BN_copy(X, W)) 285280304Sjkim goto err; 286280304Sjkim if (!BN_add(X, X, test)) 287280304Sjkim goto err; 28855714Skris 289280304Sjkim /* step 9 */ 290280304Sjkim if (!BN_lshift1(r0, q)) 291280304Sjkim goto err; 292280304Sjkim if (!BN_mod(c, X, r0, ctx)) 293280304Sjkim goto err; 294280304Sjkim if (!BN_sub(r0, c, BN_value_one())) 295280304Sjkim goto err; 296280304Sjkim if (!BN_sub(p, X, r0)) 297280304Sjkim goto err; 29855714Skris 299280304Sjkim /* step 10 */ 300280304Sjkim if (BN_cmp(p, test) >= 0) { 301280304Sjkim /* step 11 */ 302280304Sjkim r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); 303280304Sjkim if (r > 0) 304280304Sjkim goto end; /* found it */ 305280304Sjkim if (r != 0) 306280304Sjkim goto err; 307280304Sjkim } 30855714Skris 309280304Sjkim /* step 13 */ 310280304Sjkim counter++; 311280304Sjkim /* "offset = offset + n + 1" */ 31255714Skris 313280304Sjkim /* step 14 */ 314280304Sjkim if (counter >= 4096) 315280304Sjkim break; 316280304Sjkim } 317280304Sjkim } 318280304Sjkim end: 319280304Sjkim if (!BN_GENCB_call(cb, 2, 1)) 320280304Sjkim goto err; 32155714Skris 322280304Sjkim /* We now need to generate g */ 323280304Sjkim /* Set r0=(p-1)/q */ 324280304Sjkim if (!BN_sub(test, p, BN_value_one())) 325280304Sjkim goto err; 326280304Sjkim if (!BN_div(r0, NULL, test, q, ctx)) 327280304Sjkim goto err; 32855714Skris 329280304Sjkim if (!BN_set_word(test, h)) 330280304Sjkim goto err; 331280304Sjkim if (!BN_MONT_CTX_set(mont, p, ctx)) 332280304Sjkim goto err; 33355714Skris 334280304Sjkim for (;;) { 335280304Sjkim /* g=test^r0%p */ 336280304Sjkim if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) 337280304Sjkim goto err; 338280304Sjkim if (!BN_is_one(g)) 339280304Sjkim break; 340280304Sjkim if (!BN_add(test, test, BN_value_one())) 341280304Sjkim goto err; 342280304Sjkim h++; 343280304Sjkim } 34455714Skris 345280304Sjkim if (!BN_GENCB_call(cb, 3, 1)) 346280304Sjkim goto err; 34755714Skris 348280304Sjkim ok = 1; 349280304Sjkim err: 350280304Sjkim if (ok) { 351280304Sjkim if (ret->p) 352280304Sjkim BN_free(ret->p); 353280304Sjkim if (ret->q) 354280304Sjkim BN_free(ret->q); 355280304Sjkim if (ret->g) 356280304Sjkim BN_free(ret->g); 357280304Sjkim ret->p = BN_dup(p); 358280304Sjkim ret->q = BN_dup(q); 359280304Sjkim ret->g = BN_dup(g); 360280304Sjkim if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { 361280304Sjkim ok = 0; 362280304Sjkim goto err; 363280304Sjkim } 364280304Sjkim if (counter_ret != NULL) 365280304Sjkim *counter_ret = counter; 366280304Sjkim if (h_ret != NULL) 367280304Sjkim *h_ret = h; 368280304Sjkim if (seed_out) 369280304Sjkim memcpy(seed_out, seed, qsize); 370280304Sjkim } 371280304Sjkim if (ctx) { 372280304Sjkim BN_CTX_end(ctx); 373280304Sjkim BN_CTX_free(ctx); 374280304Sjkim } 375280304Sjkim if (mont != NULL) 376280304Sjkim BN_MONT_CTX_free(mont); 377280304Sjkim return ok; 378280304Sjkim} 379160814Ssimon#endif 380