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