1 /* 2 * Copyright 1995-2019 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 #include <stdio.h> 11 #include <time.h> 12 #include "internal/cryptlib.h" 13 #include "bn_lcl.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 22 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 23 const BIGNUM *a1_odd, int k, BN_CTX *ctx, 24 BN_MONT_CTX *mont); 25 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods); 26 static int probable_prime_dh_safe(BIGNUM *rnd, int bits, 27 const BIGNUM *add, const BIGNUM *rem, 28 BN_CTX *ctx); 29 30 int BN_GENCB_call(BN_GENCB *cb, int a, int b) 31 { 32 /* No callback means continue */ 33 if (!cb) 34 return 1; 35 switch (cb->ver) { 36 case 1: 37 /* Deprecated-style callbacks */ 38 if (!cb->cb.cb_1) 39 return 1; 40 cb->cb.cb_1(a, b, cb->arg); 41 return 1; 42 case 2: 43 /* New-style callbacks */ 44 return cb->cb.cb_2(a, b, cb); 45 default: 46 break; 47 } 48 /* Unrecognised callback type */ 49 return 0; 50 } 51 52 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, 53 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) 54 { 55 BIGNUM *t; 56 int found = 0; 57 int i, j, c1 = 0; 58 BN_CTX *ctx = NULL; 59 prime_t *mods = NULL; 60 int checks = BN_prime_checks_for_size(bits); 61 62 if (bits < 2) { 63 /* There are no prime numbers this small. */ 64 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); 65 return 0; 66 } else if (bits == 2 && safe) { 67 /* The smallest safe prime (7) is three bits. */ 68 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); 69 return 0; 70 } 71 72 mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); 73 if (mods == NULL) 74 goto err; 75 76 ctx = BN_CTX_new(); 77 if (ctx == NULL) 78 goto err; 79 BN_CTX_start(ctx); 80 t = BN_CTX_get(ctx); 81 if (t == NULL) 82 goto err; 83 loop: 84 /* make a random number and set the top and bottom bits */ 85 if (add == NULL) { 86 if (!probable_prime(ret, bits, mods)) 87 goto err; 88 } else { 89 if (safe) { 90 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx)) 91 goto err; 92 } else { 93 if (!bn_probable_prime_dh(ret, bits, add, rem, ctx)) 94 goto err; 95 } 96 } 97 98 if (!BN_GENCB_call(cb, 0, c1++)) 99 /* aborted */ 100 goto err; 101 102 if (!safe) { 103 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); 104 if (i == -1) 105 goto err; 106 if (i == 0) 107 goto loop; 108 } else { 109 /* 110 * for "safe prime" generation, check that (p-1)/2 is prime. Since a 111 * prime is odd, We just need to divide by 2 112 */ 113 if (!BN_rshift1(t, ret)) 114 goto err; 115 116 for (i = 0; i < checks; i++) { 117 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); 118 if (j == -1) 119 goto err; 120 if (j == 0) 121 goto loop; 122 123 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); 124 if (j == -1) 125 goto err; 126 if (j == 0) 127 goto loop; 128 129 if (!BN_GENCB_call(cb, 2, c1 - 1)) 130 goto err; 131 /* We have a safe prime test pass */ 132 } 133 } 134 /* we have a prime :-) */ 135 found = 1; 136 err: 137 OPENSSL_free(mods); 138 BN_CTX_end(ctx); 139 BN_CTX_free(ctx); 140 bn_check_top(ret); 141 return found; 142 } 143 144 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 145 BN_GENCB *cb) 146 { 147 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); 148 } 149 150 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 151 int do_trial_division, BN_GENCB *cb) 152 { 153 int i, j, ret = -1; 154 int k; 155 BN_CTX *ctx = NULL; 156 BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */ 157 BN_MONT_CTX *mont = NULL; 158 159 /* Take care of the really small primes 2 & 3 */ 160 if (BN_is_word(a, 2) || BN_is_word(a, 3)) 161 return 1; 162 163 /* Check odd and bigger than 1 */ 164 if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0) 165 return 0; 166 167 if (checks == BN_prime_checks) 168 checks = BN_prime_checks_for_size(BN_num_bits(a)); 169 170 /* first look for small factors */ 171 if (do_trial_division) { 172 for (i = 1; i < NUMPRIMES; i++) { 173 BN_ULONG mod = BN_mod_word(a, primes[i]); 174 if (mod == (BN_ULONG)-1) 175 goto err; 176 if (mod == 0) 177 return BN_is_word(a, primes[i]); 178 } 179 if (!BN_GENCB_call(cb, 1, -1)) 180 goto err; 181 } 182 183 if (ctx_passed != NULL) 184 ctx = ctx_passed; 185 else if ((ctx = BN_CTX_new()) == NULL) 186 goto err; 187 BN_CTX_start(ctx); 188 189 A1 = BN_CTX_get(ctx); 190 A3 = BN_CTX_get(ctx); 191 A1_odd = BN_CTX_get(ctx); 192 check = BN_CTX_get(ctx); 193 if (check == NULL) 194 goto err; 195 196 /* compute A1 := a - 1 */ 197 if (!BN_copy(A1, a) || !BN_sub_word(A1, 1)) 198 goto err; 199 /* compute A3 := a - 3 */ 200 if (!BN_copy(A3, a) || !BN_sub_word(A3, 3)) 201 goto err; 202 203 /* write A1 as A1_odd * 2^k */ 204 k = 1; 205 while (!BN_is_bit_set(A1, k)) 206 k++; 207 if (!BN_rshift(A1_odd, A1, k)) 208 goto err; 209 210 /* Montgomery setup for computations mod a */ 211 mont = BN_MONT_CTX_new(); 212 if (mont == NULL) 213 goto err; 214 if (!BN_MONT_CTX_set(mont, a, ctx)) 215 goto err; 216 217 for (i = 0; i < checks; i++) { 218 /* 1 < check < a-1 */ 219 if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2)) 220 goto err; 221 222 j = witness(check, a, A1, A1_odd, k, ctx, mont); 223 if (j == -1) 224 goto err; 225 if (j) { 226 ret = 0; 227 goto err; 228 } 229 if (!BN_GENCB_call(cb, 1, i)) 230 goto err; 231 } 232 ret = 1; 233 err: 234 if (ctx != NULL) { 235 BN_CTX_end(ctx); 236 if (ctx_passed == NULL) 237 BN_CTX_free(ctx); 238 } 239 BN_MONT_CTX_free(mont); 240 241 return ret; 242 } 243 244 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 245 const BIGNUM *a1_odd, int k, BN_CTX *ctx, 246 BN_MONT_CTX *mont) 247 { 248 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ 249 return -1; 250 if (BN_is_one(w)) 251 return 0; /* probably prime */ 252 if (BN_cmp(w, a1) == 0) 253 return 0; /* w == -1 (mod a), 'a' is probably prime */ 254 while (--k) { 255 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ 256 return -1; 257 if (BN_is_one(w)) 258 return 1; /* 'a' is composite, otherwise a previous 'w' 259 * would have been == -1 (mod 'a') */ 260 if (BN_cmp(w, a1) == 0) 261 return 0; /* w == -1 (mod a), 'a' is probably prime */ 262 } 263 /* 264 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and 265 * it is neither -1 nor +1 -- so 'a' cannot be prime 266 */ 267 bn_check_top(w); 268 return 1; 269 } 270 271 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods) 272 { 273 int i; 274 BN_ULONG delta; 275 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 276 char is_single_word = bits <= BN_BITS2; 277 278 again: 279 /* TODO: Not all primes are private */ 280 if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) 281 return 0; 282 /* we now have a random number 'rnd' to test. */ 283 for (i = 1; i < NUMPRIMES; i++) { 284 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 285 if (mod == (BN_ULONG)-1) 286 return 0; 287 mods[i] = (prime_t) mod; 288 } 289 /* 290 * If bits is so small that it fits into a single word then we 291 * additionally don't want to exceed that many bits. 292 */ 293 if (is_single_word) { 294 BN_ULONG size_limit; 295 296 if (bits == BN_BITS2) { 297 /* 298 * Shifting by this much has undefined behaviour so we do it a 299 * different way 300 */ 301 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd); 302 } else { 303 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; 304 } 305 if (size_limit < maxdelta) 306 maxdelta = size_limit; 307 } 308 delta = 0; 309 loop: 310 if (is_single_word) { 311 BN_ULONG rnd_word = BN_get_word(rnd); 312 313 /*- 314 * In the case that the candidate prime is a single word then 315 * we check that: 316 * 1) It's greater than primes[i] because we shouldn't reject 317 * 3 as being a prime number because it's a multiple of 318 * three. 319 * 2) That it's not a multiple of a known prime. We don't 320 * check that rnd-1 is also coprime to all the known 321 * primes because there aren't many small primes where 322 * that's true. 323 */ 324 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { 325 if ((mods[i] + delta) % primes[i] == 0) { 326 delta += 2; 327 if (delta > maxdelta) 328 goto again; 329 goto loop; 330 } 331 } 332 } else { 333 for (i = 1; i < NUMPRIMES; i++) { 334 /* 335 * check that rnd is not a prime and also that gcd(rnd-1,primes) 336 * == 1 (except for 2) 337 */ 338 if (((mods[i] + delta) % primes[i]) <= 1) { 339 delta += 2; 340 if (delta > maxdelta) 341 goto again; 342 goto loop; 343 } 344 } 345 } 346 if (!BN_add_word(rnd, delta)) 347 return 0; 348 if (BN_num_bits(rnd) != bits) 349 goto again; 350 bn_check_top(rnd); 351 return 1; 352 } 353 354 int bn_probable_prime_dh(BIGNUM *rnd, int bits, 355 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) 356 { 357 int i, ret = 0; 358 BIGNUM *t1; 359 360 BN_CTX_start(ctx); 361 if ((t1 = BN_CTX_get(ctx)) == NULL) 362 goto err; 363 364 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) 365 goto err; 366 367 /* we need ((rnd-rem) % add) == 0 */ 368 369 if (!BN_mod(t1, rnd, add, ctx)) 370 goto err; 371 if (!BN_sub(rnd, rnd, t1)) 372 goto err; 373 if (rem == NULL) { 374 if (!BN_add_word(rnd, 1)) 375 goto err; 376 } else { 377 if (!BN_add(rnd, rnd, rem)) 378 goto err; 379 } 380 381 /* we now have a random number 'rand' to test. */ 382 383 loop: 384 for (i = 1; i < NUMPRIMES; i++) { 385 /* check that rnd is a prime */ 386 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 387 if (mod == (BN_ULONG)-1) 388 goto err; 389 if (mod <= 1) { 390 if (!BN_add(rnd, rnd, add)) 391 goto err; 392 goto loop; 393 } 394 } 395 ret = 1; 396 397 err: 398 BN_CTX_end(ctx); 399 bn_check_top(rnd); 400 return ret; 401 } 402 403 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 404 const BIGNUM *rem, BN_CTX *ctx) 405 { 406 int i, ret = 0; 407 BIGNUM *t1, *qadd, *q; 408 409 bits--; 410 BN_CTX_start(ctx); 411 t1 = BN_CTX_get(ctx); 412 q = BN_CTX_get(ctx); 413 qadd = BN_CTX_get(ctx); 414 if (qadd == NULL) 415 goto err; 416 417 if (!BN_rshift1(qadd, padd)) 418 goto err; 419 420 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) 421 goto err; 422 423 /* we need ((rnd-rem) % add) == 0 */ 424 if (!BN_mod(t1, q, qadd, ctx)) 425 goto err; 426 if (!BN_sub(q, q, t1)) 427 goto err; 428 if (rem == NULL) { 429 if (!BN_add_word(q, 1)) 430 goto err; 431 } else { 432 if (!BN_rshift1(t1, rem)) 433 goto err; 434 if (!BN_add(q, q, t1)) 435 goto err; 436 } 437 438 /* we now have a random number 'rand' to test. */ 439 if (!BN_lshift1(p, q)) 440 goto err; 441 if (!BN_add_word(p, 1)) 442 goto err; 443 444 loop: 445 for (i = 1; i < NUMPRIMES; i++) { 446 /* check that p and q are prime */ 447 /* 448 * check that for p and q gcd(p-1,primes) == 1 (except for 2) 449 */ 450 BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); 451 BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); 452 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) 453 goto err; 454 if (pmod == 0 || qmod == 0) { 455 if (!BN_add(p, p, padd)) 456 goto err; 457 if (!BN_add(q, q, qadd)) 458 goto err; 459 goto loop; 460 } 461 } 462 ret = 1; 463 464 err: 465 BN_CTX_end(ctx); 466 bn_check_top(p); 467 return ret; 468 } 469