1// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15#include <openssl/bn.h> 16 17#include <openssl/err.h> 18#include <openssl/mem.h> 19 20#include "../../internal.h" 21#include "internal.h" 22 23 24// kPrimes contains the first 1024 primes. 25static const uint16_t kPrimes[] = { 26 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 27 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 28 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 29 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 30 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 31 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 32 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 33 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 34 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 35 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 36 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 37 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 38 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 39 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 40 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 41 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 42 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 43 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 44 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 45 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 46 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 47 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 48 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 49 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 50 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 51 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 52 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 53 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 54 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 55 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 56 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 57 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 58 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 59 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 60 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 61 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 62 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 63 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 64 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 65 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 66 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 67 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 68 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 69 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 70 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 71 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 72 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 73 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 74 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 75 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 76 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 77 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 78 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 79 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 80 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 81 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 82 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 83 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 84 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 85 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 86 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 87 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 88 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 89 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 90 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 91 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 92 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 93 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 94 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 95 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 96 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 97 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 98 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 99 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 100 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 101 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 102 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 103 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 104 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 105 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 106 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 107 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 108 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 109 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 110 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 111 8117, 8123, 8147, 8161, 112}; 113 114// BN_prime_checks_for_size returns the number of Miller-Rabin iterations 115// necessary for generating a 'bits'-bit candidate prime. 116// 117// 118// This table is generated using the algorithm of FIPS PUB 186-4 119// Digital Signature Standard (DSS), section F.1, page 117. 120// (https://doi.org/10.6028/NIST.FIPS.186-4) 121// The following magma script was used to generate the output: 122// securitybits:=125; 123// k:=1024; 124// for t:=1 to 65 do 125// for M:=3 to Floor(2*Sqrt(k-1)-1) do 126// S:=0; 127// // Sum over m 128// for m:=3 to M do 129// s:=0; 130// // Sum over j 131// for j:=2 to m do 132// s+:=(RealField(32)!2)^-(j+(k-1)/j); 133// end for; 134// S+:=2^(m-(m-1)*t)*s; 135// end for; 136// A:=2^(k-2-M*t); 137// B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S; 138// pkt:=2.00743*Log(2)*k*2^-k*(A+B); 139// seclevel:=Floor(-Log(2,pkt)); 140// if seclevel ge securitybits then 141// printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M; 142// break; 143// end if; 144// end for; 145// if seclevel ge securitybits then break; end if; 146// end for; 147// 148// It can be run online at: http://magma.maths.usyd.edu.au/calc 149// And will output: 150// k: 1024, security: 129 bits (t: 6, M: 23) 151// k is the number of bits of the prime, securitybits is the level we want to 152// reach. 153// prime length | RSA key size | # MR tests | security level 154// -------------+--------------|------------+--------------- 155// (b) >= 6394 | >= 12788 | 3 | 256 bit 156// (b) >= 3747 | >= 7494 | 3 | 192 bit 157// (b) >= 1345 | >= 2690 | 4 | 128 bit 158// (b) >= 1080 | >= 2160 | 5 | 128 bit 159// (b) >= 852 | >= 1704 | 5 | 112 bit 160// (b) >= 476 | >= 952 | 5 | 80 bit 161// (b) >= 400 | >= 800 | 6 | 80 bit 162// (b) >= 347 | >= 694 | 7 | 80 bit 163// (b) >= 308 | >= 616 | 8 | 80 bit 164// (b) >= 55 | >= 110 | 27 | 64 bit 165// (b) >= 6 | >= 12 | 34 | 64 bit 166static int BN_prime_checks_for_size(int bits) { 167 if (bits >= 3747) { 168 return 3; 169 } 170 if (bits >= 1345) { 171 return 4; 172 } 173 if (bits >= 476) { 174 return 5; 175 } 176 if (bits >= 400) { 177 return 6; 178 } 179 if (bits >= 347) { 180 return 7; 181 } 182 if (bits >= 308) { 183 return 8; 184 } 185 if (bits >= 55) { 186 return 27; 187 } 188 return 34; 189} 190 191// num_trial_division_primes returns the number of primes to try with trial 192// division before using more expensive checks. For larger numbers, the value 193// of excluding a candidate with trial division is larger. 194static size_t num_trial_division_primes(const BIGNUM *n) { 195 if (n->width * BN_BITS2 > 1024) { 196 return OPENSSL_ARRAY_SIZE(kPrimes); 197 } 198 return OPENSSL_ARRAY_SIZE(kPrimes) / 2; 199} 200 201// BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time 202// primality test. See |BN_primality_test| for details. This number is selected 203// so that, for a candidate N-bit RSA prime, picking |BN_PRIME_CHECKS_BLINDED| 204// random N-bit numbers will have at least |BN_prime_checks_for_size(N)| values 205// in range with high probability. 206// 207// The following Python script computes the blinding factor needed for the 208// corresponding iteration count. 209/* 210import math 211 212# We choose candidate RSA primes between sqrt(2)/2 * 2^N and 2^N and select 213# witnesses by generating random N-bit numbers. Thus the probability of 214# selecting one in range is at least sqrt(2)/2. 215p = math.sqrt(2) / 2 216 217# Target around 2^-8 probability of the blinding being insufficient given that 218# key generation is a one-time, noisy operation. 219epsilon = 2**-8 220 221def choose(a, b): 222 r = 1 223 for i in xrange(b): 224 r *= a - i 225 r /= (i + 1) 226 return r 227 228def failure_rate(min_uniform, iterations): 229 """ Returns the probability that, for |iterations| candidate witnesses, fewer 230 than |min_uniform| of them will be uniform. """ 231 prob = 0.0 232 for i in xrange(min_uniform): 233 prob += (choose(iterations, i) * 234 p**i * (1-p)**(iterations - i)) 235 return prob 236 237for min_uniform in (3, 4, 5, 6, 8, 13, 19, 28): 238 # Find the smallest number of iterations under the target failure rate. 239 iterations = min_uniform 240 while True: 241 prob = failure_rate(min_uniform, iterations) 242 if prob < epsilon: 243 print min_uniform, iterations, prob 244 break 245 iterations += 1 246 247Output: 248 3 9 0.00368894873911 249 4 11 0.00363319494662 250 5 13 0.00336215573898 251 6 15 0.00300145783158 252 8 19 0.00225214119331 253 13 27 0.00385610026955 254 19 38 0.0021410539126 255 28 52 0.00325405801769 256 25716 iterations suffices for 400-bit primes and larger (6 uniform samples needed), 258which is already well below the minimum acceptable key size for RSA. 259*/ 260#define BN_PRIME_CHECKS_BLINDED 16 261 262static int probable_prime(BIGNUM *rnd, int bits); 263static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 264 const BIGNUM *rem, BN_CTX *ctx); 265static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, 266 const BIGNUM *rem, BN_CTX *ctx); 267 268BN_GENCB *BN_GENCB_new(void) { 269 return reinterpret_cast<BN_GENCB *>(OPENSSL_zalloc(sizeof(BN_GENCB))); 270} 271 272void BN_GENCB_free(BN_GENCB *callback) { OPENSSL_free(callback); } 273 274void BN_GENCB_set(BN_GENCB *callback, 275 int (*f)(int event, int n, struct bn_gencb_st *), void *arg) { 276 callback->callback = f; 277 callback->arg = arg; 278} 279 280int BN_GENCB_call(BN_GENCB *callback, int event, int n) { 281 if (!callback) { 282 return 1; 283 } 284 285 return callback->callback(event, n, callback); 286} 287 288void *BN_GENCB_get_arg(const BN_GENCB *callback) { return callback->arg; } 289 290int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, 291 const BIGNUM *rem, BN_GENCB *cb) { 292 BIGNUM *t; 293 int i, j, c1 = 0; 294 int checks = BN_prime_checks_for_size(bits); 295 296 if (bits < 2) { 297 // There are no prime numbers this small. 298 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL); 299 return 0; 300 } else if (bits == 2 && safe) { 301 // The smallest safe prime (7) is three bits. 302 OPENSSL_PUT_ERROR(BN, BN_R_BITS_TOO_SMALL); 303 return 0; 304 } 305 306 bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new()); 307 if (ctx == nullptr) { 308 return 0; 309 } 310 bssl::BN_CTXScope scope(ctx.get()); 311 t = BN_CTX_get(ctx.get()); 312 if (!t) { 313 return 0; 314 } 315 316loop: 317 // make a random number and set the top and bottom bits 318 if (add == NULL) { 319 if (!probable_prime(ret, bits)) { 320 return 0; 321 } 322 } else { 323 if (safe) { 324 if (!probable_prime_dh_safe(ret, bits, add, rem, ctx.get())) { 325 return 0; 326 } 327 } else { 328 if (!probable_prime_dh(ret, bits, add, rem, ctx.get())) { 329 return 0; 330 } 331 } 332 } 333 334 if (!BN_GENCB_call(cb, BN_GENCB_GENERATED, c1++)) { 335 // aborted 336 return 0; 337 } 338 339 if (!safe) { 340 i = BN_is_prime_fasttest_ex(ret, checks, ctx.get(), 0, cb); 341 if (i == -1) { 342 return 0; 343 } else if (i == 0) { 344 goto loop; 345 } 346 } else { 347 // for "safe prime" generation, check that (p-1)/2 is prime. Since a prime 348 // is odd, We just need to divide by 2 349 if (!BN_rshift1(t, ret)) { 350 return 0; 351 } 352 353 // Interleave |ret| and |t|'s primality tests to avoid paying the full 354 // iteration count on |ret| only to quickly discover |t| is composite. 355 // 356 // TODO(davidben): This doesn't quite work because an iteration count of 1 357 // still runs the blinding mechanism. 358 for (i = 0; i < checks; i++) { 359 j = BN_is_prime_fasttest_ex(ret, 1, ctx.get(), 0, NULL); 360 if (j == -1) { 361 return 0; 362 } else if (j == 0) { 363 goto loop; 364 } 365 366 j = BN_is_prime_fasttest_ex(t, 1, ctx.get(), 0, NULL); 367 if (j == -1) { 368 return 0; 369 } else if (j == 0) { 370 goto loop; 371 } 372 373 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i)) { 374 return 0; 375 } 376 // We have a safe prime test pass 377 } 378 } 379 380 // we have a prime :-) 381 return 1; 382} 383 384static int bn_trial_division(uint16_t *out, const BIGNUM *bn) { 385 const size_t num_primes = num_trial_division_primes(bn); 386 for (size_t i = 1; i < num_primes; i++) { 387 // During RSA key generation, |bn| may be secret, but only if |bn| was 388 // prime, so it is safe to leak failed trial divisions. 389 if (constant_time_declassify_int(bn_mod_u16_consttime(bn, kPrimes[i]) == 390 0)) { 391 *out = kPrimes[i]; 392 return 1; 393 } 394 } 395 return 0; 396} 397 398int bn_odd_number_is_obviously_composite(const BIGNUM *bn) { 399 uint16_t prime; 400 return bn_trial_division(&prime, bn) && !BN_is_word(bn, prime); 401} 402 403int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont, 404 BN_CTX *ctx) { 405 // This function corresponds to steps 1 through 3 of FIPS 186-4, C.3.1. 406 const BIGNUM *w = &mont->N; 407 // Note we do not call |BN_CTX_start| in this function. We intentionally 408 // allocate values in the containing scope so they outlive this function. 409 miller_rabin->w1 = BN_CTX_get(ctx); 410 miller_rabin->m = BN_CTX_get(ctx); 411 miller_rabin->one_mont = BN_CTX_get(ctx); 412 miller_rabin->w1_mont = BN_CTX_get(ctx); 413 if (miller_rabin->w1 == NULL || // 414 miller_rabin->m == NULL || // 415 miller_rabin->one_mont == NULL || // 416 miller_rabin->w1_mont == NULL) { 417 return 0; 418 } 419 420 // See FIPS 186-4, C.3.1, steps 1 through 3. 421 if (!bn_usub_consttime(miller_rabin->w1, w, BN_value_one())) { 422 return 0; 423 } 424 miller_rabin->a = BN_count_low_zero_bits(miller_rabin->w1); 425 if (!bn_rshift_secret_shift(miller_rabin->m, miller_rabin->w1, 426 miller_rabin->a, ctx)) { 427 return 0; 428 } 429 miller_rabin->w_bits = BN_num_bits(w); 430 431 // Precompute some values in Montgomery form. 432 if (!bn_one_to_montgomery(miller_rabin->one_mont, mont, ctx) || 433 // w - 1 is -1 mod w, so we can compute it in the Montgomery domain, -R, 434 // with a subtraction. (|one_mont| cannot be zero.) 435 !bn_usub_consttime(miller_rabin->w1_mont, w, miller_rabin->one_mont)) { 436 return 0; 437 } 438 439 return 1; 440} 441 442int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin, 443 int *out_is_possibly_prime, const BIGNUM *b, 444 const BN_MONT_CTX *mont, BN_CTX *ctx) { 445 // This function corresponds to steps 4.3 through 4.5 of FIPS 186-4, C.3.1. 446 bssl::BN_CTXScope scope(ctx); 447 448 // Step 4.3. We use Montgomery-encoding for better performance and to avoid 449 // timing leaks. 450 const BIGNUM *w = &mont->N; 451 BIGNUM *z = BN_CTX_get(ctx); 452 crypto_word_t is_possibly_prime; 453 if (z == NULL || 454 !BN_mod_exp_mont_consttime(z, b, miller_rabin->m, w, ctx, mont) || 455 !BN_to_montgomery(z, z, mont, ctx)) { 456 return 0; 457 } 458 459 // is_possibly_prime is all ones if we have determined |b| is not a composite 460 // witness for |w|. This is equivalent to going to step 4.7 in the original 461 // algorithm. To avoid timing leaks, we run the algorithm to the end for prime 462 // inputs. 463 is_possibly_prime = 0; 464 465 // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still 466 // possibly prime. 467 is_possibly_prime = BN_equal_consttime(z, miller_rabin->one_mont) | 468 BN_equal_consttime(z, miller_rabin->w1_mont); 469 is_possibly_prime = 0 - is_possibly_prime; // Make it all zeros or all ones. 470 471 // Step 4.5. 472 // 473 // To avoid leaking |a|, we run the loop to |w_bits| and mask off all 474 // iterations once |j| = |a|. 475 for (int j = 1; j < miller_rabin->w_bits; j++) { 476 if (constant_time_declassify_w(constant_time_eq_int(j, miller_rabin->a) & 477 ~is_possibly_prime)) { 478 // If the loop is done and we haven't seen z = 1 or z = w-1 yet, the 479 // value is composite and we can break in variable time. 480 break; 481 } 482 483 // Step 4.5.1. 484 if (!BN_mod_mul_montgomery(z, z, z, mont, ctx)) { 485 return 0; 486 } 487 488 // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite 489 // witness. 490 crypto_word_t z_is_w1_mont = BN_equal_consttime(z, miller_rabin->w1_mont); 491 z_is_w1_mont = 0 - z_is_w1_mont; // Make it all zeros or all ones. 492 is_possibly_prime |= z_is_w1_mont; // Go to step 4.7 if |z_is_w1_mont|. 493 494 // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z 495 // was not -1. There are no non-trivial square roots of 1 modulo a prime, so 496 // w is composite and we may exit in variable time. 497 if (constant_time_declassify_w( 498 BN_equal_consttime(z, miller_rabin->one_mont) & 499 ~is_possibly_prime)) { 500 break; 501 } 502 } 503 504 *out_is_possibly_prime = constant_time_declassify_w(is_possibly_prime) & 1; 505 return 1; 506} 507 508int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, int checks, 509 BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) { 510 // This function's secrecy and performance requirements come from RSA key 511 // generation. We generate RSA keys by selecting two large, secret primes with 512 // rejection sampling. 513 // 514 // We thus treat |w| as secret if turns out to be a large prime. However, if 515 // |w| is composite, we treat this and |w| itself as public. (Conversely, if 516 // |w| is prime, that it is prime is public. Only the value is secret.) This 517 // is fine for RSA key generation, but note it is important that we use 518 // rejection sampling, with each candidate prime chosen independently. This 519 // would not work for, e.g., an algorithm which looked for primes in 520 // consecutive integers. These assumptions allow us to discard composites 521 // quickly. We additionally treat |w| as public when it is a small prime to 522 // simplify trial decryption and some edge cases. 523 // 524 // One RSA key generation will call this function on exactly two primes and 525 // many more composites. The overall cost is a combination of several factors: 526 // 527 // 1. Checking if |w| is divisible by a small prime is much faster than 528 // learning it is composite by Miller-Rabin (see below for details on that 529 // cost). Trial division by p saves 1/p of Miller-Rabin calls, so this is 530 // worthwhile until p exceeds the ratio of the two costs. 531 // 532 // 2. For a random (i.e. non-adversarial) candidate large prime and candidate 533 // witness, the probability of false witness is very low. (This is why FIPS 534 // 186-4 only requires a few iterations.) Thus composites not discarded by 535 // trial decryption, in practice, cost one Miller-Rabin iteration. Only the 536 // two actual primes cost the full iteration count. 537 // 538 // 3. A Miller-Rabin iteration is a modular exponentiation plus |a| additional 539 // modular squares, where |a| is the number of factors of two in |w-1|. |a| 540 // is likely small (the distribution falls exponentially), but it is also 541 // potentially secret, so we loop up to its log(w) upper bound when |w| is 542 // prime. When |w| is composite, we break early, so only two calls pay this 543 // cost. (Note that all calls pay the modular exponentiation which is, 544 // itself, log(w) modular multiplications and squares.) 545 // 546 // 4. While there are only two prime calls, they multiplicatively pay the full 547 // costs of (2) and (3). 548 // 549 // 5. After the primes are chosen, RSA keys derive some values from the 550 // primes, but this cost is negligible in comparison. 551 552 *out_is_probably_prime = 0; 553 554 if (BN_cmp(w, BN_value_one()) <= 0) { 555 return 1; 556 } 557 558 if (!BN_is_odd(w)) { 559 // The only even prime is two. 560 *out_is_probably_prime = BN_is_word(w, 2); 561 return 1; 562 } 563 564 // Miller-Rabin does not work for three. 565 if (BN_is_word(w, 3)) { 566 *out_is_probably_prime = 1; 567 return 1; 568 } 569 570 if (do_trial_division) { 571 // Perform additional trial division checks to discard small primes. 572 uint16_t prime; 573 if (bn_trial_division(&prime, w)) { 574 *out_is_probably_prime = BN_is_word(w, prime); 575 return 1; 576 } 577 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, -1)) { 578 return 0; 579 } 580 } 581 582 if (checks == BN_prime_checks_for_generation) { 583 checks = BN_prime_checks_for_size(BN_num_bits(w)); 584 } 585 586 bssl::UniquePtr<BN_CTX> new_ctx; 587 if (ctx == nullptr) { 588 new_ctx.reset(BN_CTX_new()); 589 if (new_ctx == nullptr) { 590 return 0; 591 } 592 ctx = new_ctx.get(); 593 } 594 595 // See C.3.1 from FIPS 186-4. 596 bssl::BN_CTXScope scope(ctx); 597 BIGNUM *b = BN_CTX_get(ctx); 598 bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new_consttime(w, ctx)); 599 BN_MILLER_RABIN miller_rabin; 600 crypto_word_t uniform_iterations = 0; 601 if (b == nullptr || mont == nullptr || 602 // Steps 1-3. 603 !bn_miller_rabin_init(&miller_rabin, mont.get(), ctx)) { 604 return 0; 605 } 606 607 // The following loop performs in inner iteration of the Miller-Rabin 608 // Primality test (Step 4). 609 // 610 // The algorithm as specified in FIPS 186-4 leaks information on |w|, the RSA 611 // private key. Instead, we run through each iteration unconditionally, 612 // performing modular multiplications, masking off any effects to behave 613 // equivalently to the specified algorithm. 614 // 615 // We also blind the number of values of |b| we try. Steps 4.1–4.2 say to 616 // discard out-of-range values. To avoid leaking information on |w|, we use 617 // |bn_rand_secret_range| which, rather than discarding bad values, adjusts 618 // them to be in range. Though not uniformly selected, these adjusted values 619 // are still usable as Miller-Rabin checks. 620 // 621 // Miller-Rabin is already probabilistic, so we could reach the desired 622 // confidence levels by just suitably increasing the iteration count. However, 623 // to align with FIPS 186-4, we use a more pessimal analysis: we do not count 624 // the non-uniform values towards the iteration count. As a result, this 625 // function is more complex and has more timing risk than necessary. 626 // 627 // We count both total iterations and uniform ones and iterate until we've 628 // reached at least |BN_PRIME_CHECKS_BLINDED| and |iterations|, respectively. 629 // If the latter is large enough, it will be the limiting factor with high 630 // probability and we won't leak information. 631 // 632 // Note this blinding does not impact most calls when picking primes because 633 // composites are rejected early. Only the two secret primes see extra work. 634 635 // Using |constant_time_lt_w| seems to prevent the compiler from optimizing 636 // this into two jumps. 637 for (int i = 1; constant_time_declassify_w( 638 (i <= BN_PRIME_CHECKS_BLINDED) | 639 constant_time_lt_w(uniform_iterations, checks)); 640 i++) { 641 // Step 4.1-4.2 642 int is_uniform; 643 if (!bn_rand_secret_range(b, &is_uniform, 2, miller_rabin.w1)) { 644 return 0; 645 } 646 uniform_iterations += is_uniform; 647 648 // Steps 4.3-4.5 649 int is_possibly_prime = 0; 650 if (!bn_miller_rabin_iteration(&miller_rabin, &is_possibly_prime, b, 651 mont.get(), ctx)) { 652 return 0; 653 } 654 655 if (!is_possibly_prime) { 656 // Step 4.6. We did not see z = w-1 before z = 1, so w must be composite. 657 *out_is_probably_prime = 0; 658 return 1; 659 } 660 661 // Step 4.7 662 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) { 663 return 0; 664 } 665 } 666 667 declassify_assert(uniform_iterations >= (crypto_word_t)checks); 668 *out_is_probably_prime = 1; 669 return 1; 670} 671 672int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, 673 BN_GENCB *cb) { 674 return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb); 675} 676 677int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx, 678 int do_trial_division, BN_GENCB *cb) { 679 int is_probably_prime; 680 if (!BN_primality_test(&is_probably_prime, a, checks, ctx, do_trial_division, 681 cb)) { 682 return -1; 683 } 684 return is_probably_prime; 685} 686 687int BN_enhanced_miller_rabin_primality_test( 688 enum bn_primality_result_t *out_result, const BIGNUM *w, int checks, 689 BN_CTX *ctx, BN_GENCB *cb) { 690 // Enhanced Miller-Rabin is only valid on odd integers greater than 3. 691 if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) { 692 OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT); 693 return 0; 694 } 695 696 if (checks == BN_prime_checks_for_generation) { 697 checks = BN_prime_checks_for_size(BN_num_bits(w)); 698 } 699 700 bssl::BN_CTXScope scope(ctx); 701 BIGNUM *w1 = BN_CTX_get(ctx); 702 if (w1 == nullptr || !BN_copy(w1, w) || !BN_sub_word(w1, 1)) { 703 return 0; 704 } 705 706 // Write w1 as m*2^a (Steps 1 and 2). 707 int a = 0; 708 while (!BN_is_bit_set(w1, a)) { 709 a++; 710 } 711 BIGNUM *m = BN_CTX_get(ctx); 712 if (m == nullptr || !BN_rshift(m, w1, a)) { 713 return 0; 714 } 715 716 BIGNUM *b = BN_CTX_get(ctx); 717 BIGNUM *g = BN_CTX_get(ctx); 718 BIGNUM *z = BN_CTX_get(ctx); 719 BIGNUM *x = BN_CTX_get(ctx); 720 BIGNUM *x1 = BN_CTX_get(ctx); 721 if (b == nullptr || g == nullptr || z == nullptr || x == nullptr || 722 x1 == nullptr) { 723 return 0; 724 } 725 726 // Montgomery setup for computations mod w 727 bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new_for_modulus(w, ctx)); 728 if (mont == nullptr) { 729 return 0; 730 } 731 732 // The following loop performs in inner iteration of the Enhanced Miller-Rabin 733 // Primality test (Step 4). 734 for (int i = 1; i <= checks; i++) { 735 // Step 4.1-4.2 736 if (!BN_rand_range_ex(b, 2, w1)) { 737 return 0; 738 } 739 740 // Step 4.3-4.4 741 if (!BN_gcd(g, b, w, ctx)) { 742 return 0; 743 } 744 if (BN_cmp_word(g, 1) > 0) { 745 *out_result = bn_composite; 746 return 1; 747 } 748 749 // Step 4.5 750 if (!BN_mod_exp_mont(z, b, m, w, ctx, mont.get())) { 751 return 0; 752 } 753 754 // Step 4.6 755 if (BN_is_one(z) || BN_cmp(z, w1) == 0) { 756 goto loop; 757 } 758 759 // Step 4.7 760 for (int j = 1; j < a; j++) { 761 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) { 762 return 0; 763 } 764 if (BN_cmp(z, w1) == 0) { 765 goto loop; 766 } 767 if (BN_is_one(z)) { 768 goto composite; 769 } 770 } 771 772 // Step 4.8-4.9 773 if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) { 774 return 0; 775 } 776 777 // Step 4.10-4.11 778 if (!BN_is_one(z) && !BN_copy(x, z)) { 779 return 0; 780 } 781 782 composite: 783 // Step 4.12-4.14 784 if (!BN_copy(x1, x) || !BN_sub_word(x1, 1) || !BN_gcd(g, x1, w, ctx)) { 785 return 0; 786 } 787 if (BN_cmp_word(g, 1) > 0) { 788 *out_result = bn_composite; 789 } else { 790 *out_result = bn_non_prime_power_composite; 791 } 792 793 return 1; 794 795 loop: 796 // Step 4.15 797 if (!BN_GENCB_call(cb, BN_GENCB_PRIME_TEST, i - 1)) { 798 return 0; 799 } 800 } 801 802 *out_result = bn_probably_prime; 803 return 1; 804} 805 806static int probable_prime(BIGNUM *rnd, int bits) { 807 do { 808 if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) { 809 return 0; 810 } 811 } while (bn_odd_number_is_obviously_composite(rnd)); 812 return 1; 813} 814 815static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, 816 const BIGNUM *rem, BN_CTX *ctx) { 817 bssl::BN_CTXScope scope(ctx); 818 BIGNUM *t1; 819 if ((t1 = BN_CTX_get(ctx)) == nullptr) { 820 return 0; 821 } 822 823 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) { 824 return 0; 825 } 826 827 // we need ((rnd-rem) % add) == 0 828 if (!BN_mod(t1, rnd, add, ctx)) { 829 return 0; 830 } 831 if (!BN_sub(rnd, rnd, t1)) { 832 return 0; 833 } 834 if (rem == nullptr) { 835 if (!BN_add_word(rnd, 1)) { 836 return 0; 837 } 838 } else { 839 if (!BN_add(rnd, rnd, rem)) { 840 return 0; 841 } 842 } 843 // we now have a random number 'rand' to test. 844 845 size_t num_primes = num_trial_division_primes(rnd); 846loop: 847 for (size_t i = 1; i < num_primes; i++) { 848 // check that rnd is a prime 849 if (bn_mod_u16_consttime(rnd, kPrimes[i]) <= 1) { 850 if (!BN_add(rnd, rnd, add)) { 851 return 0; 852 } 853 goto loop; 854 } 855 } 856 857 return 1; 858} 859 860static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 861 const BIGNUM *rem, BN_CTX *ctx) { 862 bits--; 863 bssl::BN_CTXScope scope(ctx); 864 BIGNUM *t1 = BN_CTX_get(ctx); 865 BIGNUM *q = BN_CTX_get(ctx); 866 BIGNUM *qadd = BN_CTX_get(ctx); 867 if (qadd == NULL) { 868 return 0; 869 } 870 871 if (!BN_rshift1(qadd, padd)) { 872 return 0; 873 } 874 875 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) { 876 return 0; 877 } 878 879 // we need ((rnd-rem) % add) == 0 880 if (!BN_mod(t1, q, qadd, ctx)) { 881 return 0; 882 } 883 884 if (!BN_sub(q, q, t1)) { 885 return 0; 886 } 887 888 if (rem == NULL) { 889 if (!BN_add_word(q, 1)) { 890 return 0; 891 } 892 } else { 893 if (!BN_rshift1(t1, rem)) { 894 return 0; 895 } 896 if (!BN_add(q, q, t1)) { 897 return 0; 898 } 899 } 900 901 // we now have a random number 'rand' to test. 902 if (!BN_lshift1(p, q)) { 903 return 0; 904 } 905 if (!BN_add_word(p, 1)) { 906 return 0; 907 } 908 909 size_t num_primes = num_trial_division_primes(p); 910loop: 911 for (size_t i = 1; i < num_primes; i++) { 912 // check that p and q are prime 913 // check that for p and q 914 // gcd(p-1,primes) == 1 (except for 2) 915 if (bn_mod_u16_consttime(p, kPrimes[i]) == 0 || 916 bn_mod_u16_consttime(q, kPrimes[i]) == 0) { 917 if (!BN_add(p, p, padd)) { 918 return 0; 919 } 920 if (!BN_add(q, q, qadd)) { 921 return 0; 922 } 923 goto loop; 924 } 925 } 926 927 return 1; 928} 929