1/* 2 * Copyright 1995-2022 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (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#include <stdio.h> 11#include <time.h> 12#include "internal/cryptlib.h" 13#include "bn_local.h" 14 15/* 16 * The quick sieve algorithm approach to weeding out primes is Philip 17 * Zimmermann's, as implemented in PGP. I have had a read of his comments 18 * and implemented my own version. 19 */ 20#include "bn_prime.h" 21 22static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, 23 BN_CTX *ctx); 24static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, 25 const BIGNUM *add, const BIGNUM *rem, 26 BN_CTX *ctx); 27static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, 28 int do_trial_division, BN_GENCB *cb); 29 30#define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) 31 32#if BN_BITS2 == 64 33# define BN_DEF(lo, hi) (BN_ULONG)hi<<32|lo 34#else 35# define BN_DEF(lo, hi) lo, hi 36#endif 37 38/* 39 * See SP800 89 5.3.3 (Step f) 40 * The product of the set of primes ranging from 3 to 751 41 * Generated using process in test/bn_internal_test.c test_bn_small_factors(). 42 * This includes 751 (which is not currently included in SP 800-89). 43 */ 44static const BN_ULONG small_prime_factors[] = { 45 BN_DEF(0x3ef4e3e1, 0xc4309333), BN_DEF(0xcd2d655f, 0x71161eb6), 46 BN_DEF(0x0bf94862, 0x95e2238c), BN_DEF(0x24f7912b, 0x3eb233d3), 47 BN_DEF(0xbf26c483, 0x6b55514b), BN_DEF(0x5a144871, 0x0a84d817), 48 BN_DEF(0x9b82210a, 0x77d12fee), BN_DEF(0x97f050b3, 0xdb5b93c2), 49 BN_DEF(0x4d6c026b, 0x4acad6b9), BN_DEF(0x54aec893, 0xeb7751f3), 50 BN_DEF(0x36bc85c4, 0xdba53368), BN_DEF(0x7f5ec78e, 0xd85a1b28), 51 BN_DEF(0x6b322244, 0x2eb072d8), BN_DEF(0x5e2b3aea, 0xbba51112), 52 BN_DEF(0x0e2486bf, 0x36ed1a6c), BN_DEF(0xec0c5727, 0x5f270460), 53 (BN_ULONG)0x000017b1 54}; 55 56#define BN_SMALL_PRIME_FACTORS_TOP OSSL_NELEM(small_prime_factors) 57static const BIGNUM _bignum_small_prime_factors = { 58 (BN_ULONG *)small_prime_factors, 59 BN_SMALL_PRIME_FACTORS_TOP, 60 BN_SMALL_PRIME_FACTORS_TOP, 61 0, 62 BN_FLG_STATIC_DATA 63}; 64 65const BIGNUM *ossl_bn_get0_small_factors(void) 66{ 67 return &_bignum_small_prime_factors; 68} 69 70/* 71 * Calculate the number of trial divisions that gives the best speed in 72 * combination with Miller-Rabin prime test, based on the sized of the prime. 73 */ 74static int calc_trial_divisions(int bits) 75{ 76 if (bits <= 512) 77 return 64; 78 else if (bits <= 1024) 79 return 128; 80 else if (bits <= 2048) 81 return 384; 82 else if (bits <= 4096) 83 return 1024; 84 return NUMPRIMES; 85} 86 87/* 88 * Use a minimum of 64 rounds of Miller-Rabin, which should give a false 89 * positive rate of 2^-128. If the size of the prime is larger than 2048 90 * the user probably wants a higher security level than 128, so switch 91 * to 128 rounds giving a false positive rate of 2^-256. 92 * Returns the number of rounds. 93 */ 94static int bn_mr_min_checks(int bits) 95{ 96 if (bits > 2048) 97 return 128; 98 return 64; 99} 100 101int BN_GENCB_call(BN_GENCB *cb, int a, int b) 102{ 103 /* No callback means continue */ 104 if (!cb) 105 return 1; 106 switch (cb->ver) { 107 case 1: 108 /* Deprecated-style callbacks */ 109 if (!cb->cb.cb_1) 110 return 1; 111 cb->cb.cb_1(a, b, cb->arg); 112 return 1; 113 case 2: 114 /* New-style callbacks */ 115 return cb->cb.cb_2(a, b, cb); 116 default: 117 break; 118 } 119 /* Unrecognised callback type */ 120 return 0; 121} 122 123int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe, 124 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb, 125 BN_CTX *ctx) 126{ 127 BIGNUM *t; 128 int found = 0; 129 int i, j, c1 = 0; 130 prime_t *mods = NULL; 131 int checks = bn_mr_min_checks(bits); 132 133 if (bits < 2) { 134 /* There are no prime numbers this small. */ 135 ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); 136 return 0; 137 } else if (add == NULL && safe && bits < 6 && bits != 3) { 138 /* 139 * The smallest safe prime (7) is three bits. 140 * But the following two safe primes with less than 6 bits (11, 23) 141 * are unreachable for BN_rand with BN_RAND_TOP_TWO. 142 */ 143 ERR_raise(ERR_LIB_BN, BN_R_BITS_TOO_SMALL); 144 return 0; 145 } 146 147 mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); 148 if (mods == NULL) { 149 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 150 return 0; 151 } 152 153 BN_CTX_start(ctx); 154 t = BN_CTX_get(ctx); 155 if (t == NULL) 156 goto err; 157 loop: 158 /* make a random number and set the top and bottom bits */ 159 if (add == NULL) { 160 if (!probable_prime(ret, bits, safe, mods, ctx)) 161 goto err; 162 } else { 163 if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx)) 164 goto err; 165 } 166 167 if (!BN_GENCB_call(cb, 0, c1++)) 168 /* aborted */ 169 goto err; 170 171 if (!safe) { 172 i = bn_is_prime_int(ret, checks, ctx, 0, cb); 173 if (i == -1) 174 goto err; 175 if (i == 0) 176 goto loop; 177 } else { 178 /* 179 * for "safe prime" generation, check that (p-1)/2 is prime. Since a 180 * prime is odd, We just need to divide by 2 181 */ 182 if (!BN_rshift1(t, ret)) 183 goto err; 184 185 for (i = 0; i < checks; i++) { 186 j = bn_is_prime_int(ret, 1, ctx, 0, cb); 187 if (j == -1) 188 goto err; 189 if (j == 0) 190 goto loop; 191 192 j = bn_is_prime_int(t, 1, ctx, 0, cb); 193 if (j == -1) 194 goto err; 195 if (j == 0) 196 goto loop; 197 198 if (!BN_GENCB_call(cb, 2, c1 - 1)) 199 goto err; 200 /* We have a safe prime test pass */ 201 } 202 } 203 /* we have a prime :-) */ 204 found = 1; 205 err: 206 OPENSSL_free(mods); 207 BN_CTX_end(ctx); 208 bn_check_top(ret); 209 return found; 210} 211 212#ifndef FIPS_MODULE 213int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, 214 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) 215{ 216 BN_CTX *ctx = BN_CTX_new(); 217 int retval; 218 219 if (ctx == NULL) 220 return 0; 221 222 retval = BN_generate_prime_ex2(ret, bits, safe, add, rem, cb, ctx); 223 224 BN_CTX_free(ctx); 225 return retval; 226} 227#endif 228 229#ifndef OPENSSL_NO_DEPRECATED_3_0 230int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 231 BN_GENCB *cb) 232{ 233 return ossl_bn_check_prime(a, checks, ctx_passed, 0, cb); 234} 235 236int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx, 237 int do_trial_division, BN_GENCB *cb) 238{ 239 return ossl_bn_check_prime(w, checks, ctx, do_trial_division, cb); 240} 241#endif 242 243/* Wrapper around bn_is_prime_int that sets the minimum number of checks */ 244int ossl_bn_check_prime(const BIGNUM *w, int checks, BN_CTX *ctx, 245 int do_trial_division, BN_GENCB *cb) 246{ 247 int min_checks = bn_mr_min_checks(BN_num_bits(w)); 248 249 if (checks < min_checks) 250 checks = min_checks; 251 252 return bn_is_prime_int(w, checks, ctx, do_trial_division, cb); 253} 254 255int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb) 256{ 257 return ossl_bn_check_prime(p, 0, ctx, 1, cb); 258} 259 260/* 261 * Tests that |w| is probably prime 262 * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. 263 * 264 * Returns 0 when composite, 1 when probable prime, -1 on error. 265 */ 266static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, 267 int do_trial_division, BN_GENCB *cb) 268{ 269 int i, status, ret = -1; 270#ifndef FIPS_MODULE 271 BN_CTX *ctxlocal = NULL; 272#else 273 274 if (ctx == NULL) 275 return -1; 276#endif 277 278 /* w must be bigger than 1 */ 279 if (BN_cmp(w, BN_value_one()) <= 0) 280 return 0; 281 282 /* w must be odd */ 283 if (BN_is_odd(w)) { 284 /* Take care of the really small prime 3 */ 285 if (BN_is_word(w, 3)) 286 return 1; 287 } else { 288 /* 2 is the only even prime */ 289 return BN_is_word(w, 2); 290 } 291 292 /* first look for small factors */ 293 if (do_trial_division) { 294 int trial_divisions = calc_trial_divisions(BN_num_bits(w)); 295 296 for (i = 1; i < trial_divisions; i++) { 297 BN_ULONG mod = BN_mod_word(w, primes[i]); 298 if (mod == (BN_ULONG)-1) 299 return -1; 300 if (mod == 0) 301 return BN_is_word(w, primes[i]); 302 } 303 if (!BN_GENCB_call(cb, 1, -1)) 304 return -1; 305 } 306#ifndef FIPS_MODULE 307 if (ctx == NULL && (ctxlocal = ctx = BN_CTX_new()) == NULL) 308 goto err; 309#endif 310 311 if (!ossl_bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status)) { 312 ret = -1; 313 goto err; 314 } 315 ret = (status == BN_PRIMETEST_PROBABLY_PRIME); 316err: 317#ifndef FIPS_MODULE 318 BN_CTX_free(ctxlocal); 319#endif 320 return ret; 321} 322 323/* 324 * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test. 325 * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero). 326 * The Step numbers listed in the code refer to the enhanced case. 327 * 328 * if enhanced is set, then status returns one of the following: 329 * BN_PRIMETEST_PROBABLY_PRIME 330 * BN_PRIMETEST_COMPOSITE_WITH_FACTOR 331 * BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME 332 * if enhanced is zero, then status returns either 333 * BN_PRIMETEST_PROBABLY_PRIME or 334 * BN_PRIMETEST_COMPOSITE 335 * 336 * returns 0 if there was an error, otherwise it returns 1. 337 */ 338int ossl_bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx, 339 BN_GENCB *cb, int enhanced, int *status) 340{ 341 int i, j, a, ret = 0; 342 BIGNUM *g, *w1, *w3, *x, *m, *z, *b; 343 BN_MONT_CTX *mont = NULL; 344 345 /* w must be odd */ 346 if (!BN_is_odd(w)) 347 return 0; 348 349 BN_CTX_start(ctx); 350 g = BN_CTX_get(ctx); 351 w1 = BN_CTX_get(ctx); 352 w3 = BN_CTX_get(ctx); 353 x = BN_CTX_get(ctx); 354 m = BN_CTX_get(ctx); 355 z = BN_CTX_get(ctx); 356 b = BN_CTX_get(ctx); 357 358 if (!(b != NULL 359 /* w1 := w - 1 */ 360 && BN_copy(w1, w) 361 && BN_sub_word(w1, 1) 362 /* w3 := w - 3 */ 363 && BN_copy(w3, w) 364 && BN_sub_word(w3, 3))) 365 goto err; 366 367 /* check w is larger than 3, otherwise the random b will be too small */ 368 if (BN_is_zero(w3) || BN_is_negative(w3)) 369 goto err; 370 371 /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */ 372 a = 1; 373 while (!BN_is_bit_set(w1, a)) 374 a++; 375 /* (Step 2) m = (w-1) / 2^a */ 376 if (!BN_rshift(m, w1, a)) 377 goto err; 378 379 /* Montgomery setup for computations mod a */ 380 mont = BN_MONT_CTX_new(); 381 if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx)) 382 goto err; 383 384 if (iterations == 0) 385 iterations = bn_mr_min_checks(BN_num_bits(w)); 386 387 /* (Step 4) */ 388 for (i = 0; i < iterations; ++i) { 389 /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */ 390 if (!BN_priv_rand_range_ex(b, w3, 0, ctx) 391 || !BN_add_word(b, 2)) /* 1 < b < w-1 */ 392 goto err; 393 394 if (enhanced) { 395 /* (Step 4.3) */ 396 if (!BN_gcd(g, b, w, ctx)) 397 goto err; 398 /* (Step 4.4) */ 399 if (!BN_is_one(g)) { 400 *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; 401 ret = 1; 402 goto err; 403 } 404 } 405 /* (Step 4.5) z = b^m mod w */ 406 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) 407 goto err; 408 /* (Step 4.6) if (z = 1 or z = w-1) */ 409 if (BN_is_one(z) || BN_cmp(z, w1) == 0) 410 goto outer_loop; 411 /* (Step 4.7) for j = 1 to a-1 */ 412 for (j = 1; j < a ; ++j) { 413 /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */ 414 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) 415 goto err; 416 /* (Step 4.7.3) */ 417 if (BN_cmp(z, w1) == 0) 418 goto outer_loop; 419 /* (Step 4.7.4) */ 420 if (BN_is_one(z)) 421 goto composite; 422 } 423 /* At this point z = b^((w-1)/2) mod w */ 424 /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */ 425 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) 426 goto err; 427 /* (Step 4.10) */ 428 if (BN_is_one(z)) 429 goto composite; 430 /* (Step 4.11) x = b^(w-1) mod w */ 431 if (!BN_copy(x, z)) 432 goto err; 433composite: 434 if (enhanced) { 435 /* (Step 4.1.2) g = GCD(x-1, w) */ 436 if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx)) 437 goto err; 438 /* (Steps 4.1.3 - 4.1.4) */ 439 if (BN_is_one(g)) 440 *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME; 441 else 442 *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR; 443 } else { 444 *status = BN_PRIMETEST_COMPOSITE; 445 } 446 ret = 1; 447 goto err; 448outer_loop: ; 449 /* (Step 4.1.5) */ 450 if (!BN_GENCB_call(cb, 1, i)) 451 goto err; 452 } 453 /* (Step 5) */ 454 *status = BN_PRIMETEST_PROBABLY_PRIME; 455 ret = 1; 456err: 457 BN_clear(g); 458 BN_clear(w1); 459 BN_clear(w3); 460 BN_clear(x); 461 BN_clear(m); 462 BN_clear(z); 463 BN_clear(b); 464 BN_CTX_end(ctx); 465 BN_MONT_CTX_free(mont); 466 return ret; 467} 468 469/* 470 * Generate a random number of |bits| bits that is probably prime by sieving. 471 * If |safe| != 0, it generates a safe prime. 472 * |mods| is a preallocated array that gets reused when called again. 473 * 474 * The probably prime is saved in |rnd|. 475 * 476 * Returns 1 on success and 0 on error. 477 */ 478static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, 479 BN_CTX *ctx) 480{ 481 int i; 482 BN_ULONG delta; 483 int trial_divisions = calc_trial_divisions(bits); 484 BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; 485 486 again: 487 if (!BN_priv_rand_ex(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD, 0, 488 ctx)) 489 return 0; 490 if (safe && !BN_set_bit(rnd, 1)) 491 return 0; 492 /* we now have a random number 'rnd' to test. */ 493 for (i = 1; i < trial_divisions; i++) { 494 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 495 if (mod == (BN_ULONG)-1) 496 return 0; 497 mods[i] = (prime_t) mod; 498 } 499 delta = 0; 500 loop: 501 for (i = 1; i < trial_divisions; i++) { 502 /* 503 * check that rnd is a prime and also that 504 * gcd(rnd-1,primes) == 1 (except for 2) 505 * do the second check only if we are interested in safe primes 506 * in the case that the candidate prime is a single word then 507 * we check only the primes up to sqrt(rnd) 508 */ 509 if (bits <= 31 && delta <= 0x7fffffff 510 && square(primes[i]) > BN_get_word(rnd) + delta) 511 break; 512 if (safe ? (mods[i] + delta) % primes[i] <= 1 513 : (mods[i] + delta) % primes[i] == 0) { 514 delta += safe ? 4 : 2; 515 if (delta > maxdelta) 516 goto again; 517 goto loop; 518 } 519 } 520 if (!BN_add_word(rnd, delta)) 521 return 0; 522 if (BN_num_bits(rnd) != bits) 523 goto again; 524 bn_check_top(rnd); 525 return 1; 526} 527 528/* 529 * Generate a random number |rnd| of |bits| bits that is probably prime 530 * and satisfies |rnd| % |add| == |rem| by sieving. 531 * If |safe| != 0, it generates a safe prime. 532 * |mods| is a preallocated array that gets reused when called again. 533 * 534 * Returns 1 on success and 0 on error. 535 */ 536static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, 537 const BIGNUM *add, const BIGNUM *rem, 538 BN_CTX *ctx) 539{ 540 int i, ret = 0; 541 BIGNUM *t1; 542 BN_ULONG delta; 543 int trial_divisions = calc_trial_divisions(bits); 544 BN_ULONG maxdelta = BN_MASK2 - primes[trial_divisions - 1]; 545 546 BN_CTX_start(ctx); 547 if ((t1 = BN_CTX_get(ctx)) == NULL) 548 goto err; 549 550 if (maxdelta > BN_MASK2 - BN_get_word(add)) 551 maxdelta = BN_MASK2 - BN_get_word(add); 552 553 again: 554 if (!BN_rand_ex(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD, 0, ctx)) 555 goto err; 556 557 /* we need ((rnd-rem) % add) == 0 */ 558 559 if (!BN_mod(t1, rnd, add, ctx)) 560 goto err; 561 if (!BN_sub(rnd, rnd, t1)) 562 goto err; 563 if (rem == NULL) { 564 if (!BN_add_word(rnd, safe ? 3u : 1u)) 565 goto err; 566 } else { 567 if (!BN_add(rnd, rnd, rem)) 568 goto err; 569 } 570 571 if (BN_num_bits(rnd) < bits 572 || BN_get_word(rnd) < (safe ? 5u : 3u)) { 573 if (!BN_add(rnd, rnd, add)) 574 goto err; 575 } 576 577 /* we now have a random number 'rnd' to test. */ 578 for (i = 1; i < trial_divisions; i++) { 579 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 580 if (mod == (BN_ULONG)-1) 581 goto err; 582 mods[i] = (prime_t) mod; 583 } 584 delta = 0; 585 loop: 586 for (i = 1; i < trial_divisions; i++) { 587 /* check that rnd is a prime */ 588 if (bits <= 31 && delta <= 0x7fffffff 589 && square(primes[i]) > BN_get_word(rnd) + delta) 590 break; 591 /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */ 592 if (safe ? (mods[i] + delta) % primes[i] <= 1 593 : (mods[i] + delta) % primes[i] == 0) { 594 delta += BN_get_word(add); 595 if (delta > maxdelta) 596 goto again; 597 goto loop; 598 } 599 } 600 if (!BN_add_word(rnd, delta)) 601 goto err; 602 ret = 1; 603 604 err: 605 BN_CTX_end(ctx); 606 bn_check_top(rnd); 607 return ret; 608} 609