1 /* 2 * Copyright 1995-2018 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 if (ctx != NULL) 139 BN_CTX_end(ctx); 140 BN_CTX_free(ctx); 141 bn_check_top(ret); 142 return found; 143 } 144 145 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 146 BN_GENCB *cb) 147 { 148 return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); 149 } 150 151 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, 152 int do_trial_division, BN_GENCB *cb) 153 { 154 int i, j, ret = -1; 155 int k; 156 BN_CTX *ctx = NULL; 157 BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */ 158 BN_MONT_CTX *mont = NULL; 159 160 /* Take care of the really small primes 2 & 3 */ 161 if (BN_is_word(a, 2) || BN_is_word(a, 3)) 162 return 1; 163 164 /* Check odd and bigger than 1 */ 165 if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0) 166 return 0; 167 168 if (checks == BN_prime_checks) 169 checks = BN_prime_checks_for_size(BN_num_bits(a)); 170 171 /* first look for small factors */ 172 if (do_trial_division) { 173 for (i = 1; i < NUMPRIMES; i++) { 174 BN_ULONG mod = BN_mod_word(a, primes[i]); 175 if (mod == (BN_ULONG)-1) 176 goto err; 177 if (mod == 0) 178 return BN_is_word(a, primes[i]); 179 } 180 if (!BN_GENCB_call(cb, 1, -1)) 181 goto err; 182 } 183 184 if (ctx_passed != NULL) 185 ctx = ctx_passed; 186 else if ((ctx = BN_CTX_new()) == NULL) 187 goto err; 188 BN_CTX_start(ctx); 189 190 A1 = BN_CTX_get(ctx); 191 A3 = BN_CTX_get(ctx); 192 A1_odd = BN_CTX_get(ctx); 193 check = BN_CTX_get(ctx); 194 if (check == NULL) 195 goto err; 196 197 /* compute A1 := a - 1 */ 198 if (!BN_copy(A1, a) || !BN_sub_word(A1, 1)) 199 goto err; 200 /* compute A3 := a - 3 */ 201 if (!BN_copy(A3, a) || !BN_sub_word(A3, 3)) 202 goto err; 203 204 /* write A1 as A1_odd * 2^k */ 205 k = 1; 206 while (!BN_is_bit_set(A1, k)) 207 k++; 208 if (!BN_rshift(A1_odd, A1, k)) 209 goto err; 210 211 /* Montgomery setup for computations mod a */ 212 mont = BN_MONT_CTX_new(); 213 if (mont == NULL) 214 goto err; 215 if (!BN_MONT_CTX_set(mont, a, ctx)) 216 goto err; 217 218 for (i = 0; i < checks; i++) { 219 /* 1 < check < a-1 */ 220 if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2)) 221 goto err; 222 223 j = witness(check, a, A1, A1_odd, k, ctx, mont); 224 if (j == -1) 225 goto err; 226 if (j) { 227 ret = 0; 228 goto err; 229 } 230 if (!BN_GENCB_call(cb, 1, i)) 231 goto err; 232 } 233 ret = 1; 234 err: 235 if (ctx != NULL) { 236 BN_CTX_end(ctx); 237 if (ctx_passed == NULL) 238 BN_CTX_free(ctx); 239 } 240 BN_MONT_CTX_free(mont); 241 242 return ret; 243 } 244 245 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, 246 const BIGNUM *a1_odd, int k, BN_CTX *ctx, 247 BN_MONT_CTX *mont) 248 { 249 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */ 250 return -1; 251 if (BN_is_one(w)) 252 return 0; /* probably prime */ 253 if (BN_cmp(w, a1) == 0) 254 return 0; /* w == -1 (mod a), 'a' is probably prime */ 255 while (--k) { 256 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */ 257 return -1; 258 if (BN_is_one(w)) 259 return 1; /* 'a' is composite, otherwise a previous 'w' 260 * would have been == -1 (mod 'a') */ 261 if (BN_cmp(w, a1) == 0) 262 return 0; /* w == -1 (mod a), 'a' is probably prime */ 263 } 264 /* 265 * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and 266 * it is neither -1 nor +1 -- so 'a' cannot be prime 267 */ 268 bn_check_top(w); 269 return 1; 270 } 271 272 static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods) 273 { 274 int i; 275 BN_ULONG delta; 276 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 277 char is_single_word = bits <= BN_BITS2; 278 279 again: 280 /* TODO: Not all primes are private */ 281 if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) 282 return 0; 283 /* we now have a random number 'rnd' to test. */ 284 for (i = 1; i < NUMPRIMES; i++) { 285 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 286 if (mod == (BN_ULONG)-1) 287 return 0; 288 mods[i] = (prime_t) mod; 289 } 290 /* 291 * If bits is so small that it fits into a single word then we 292 * additionally don't want to exceed that many bits. 293 */ 294 if (is_single_word) { 295 BN_ULONG size_limit; 296 297 if (bits == BN_BITS2) { 298 /* 299 * Shifting by this much has undefined behaviour so we do it a 300 * different way 301 */ 302 size_limit = ~((BN_ULONG)0) - BN_get_word(rnd); 303 } else { 304 size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1; 305 } 306 if (size_limit < maxdelta) 307 maxdelta = size_limit; 308 } 309 delta = 0; 310 loop: 311 if (is_single_word) { 312 BN_ULONG rnd_word = BN_get_word(rnd); 313 314 /*- 315 * In the case that the candidate prime is a single word then 316 * we check that: 317 * 1) It's greater than primes[i] because we shouldn't reject 318 * 3 as being a prime number because it's a multiple of 319 * three. 320 * 2) That it's not a multiple of a known prime. We don't 321 * check that rnd-1 is also coprime to all the known 322 * primes because there aren't many small primes where 323 * that's true. 324 */ 325 for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { 326 if ((mods[i] + delta) % primes[i] == 0) { 327 delta += 2; 328 if (delta > maxdelta) 329 goto again; 330 goto loop; 331 } 332 } 333 } else { 334 for (i = 1; i < NUMPRIMES; i++) { 335 /* 336 * check that rnd is not a prime and also that gcd(rnd-1,primes) 337 * == 1 (except for 2) 338 */ 339 if (((mods[i] + delta) % primes[i]) <= 1) { 340 delta += 2; 341 if (delta > maxdelta) 342 goto again; 343 goto loop; 344 } 345 } 346 } 347 if (!BN_add_word(rnd, delta)) 348 return 0; 349 if (BN_num_bits(rnd) != bits) 350 goto again; 351 bn_check_top(rnd); 352 return 1; 353 } 354 355 int bn_probable_prime_dh(BIGNUM *rnd, int bits, 356 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) 357 { 358 int i, ret = 0; 359 BIGNUM *t1; 360 361 BN_CTX_start(ctx); 362 if ((t1 = BN_CTX_get(ctx)) == NULL) 363 goto err; 364 365 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) 366 goto err; 367 368 /* we need ((rnd-rem) % add) == 0 */ 369 370 if (!BN_mod(t1, rnd, add, ctx)) 371 goto err; 372 if (!BN_sub(rnd, rnd, t1)) 373 goto err; 374 if (rem == NULL) { 375 if (!BN_add_word(rnd, 1)) 376 goto err; 377 } else { 378 if (!BN_add(rnd, rnd, rem)) 379 goto err; 380 } 381 382 /* we now have a random number 'rand' to test. */ 383 384 loop: 385 for (i = 1; i < NUMPRIMES; i++) { 386 /* check that rnd is a prime */ 387 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 388 if (mod == (BN_ULONG)-1) 389 goto err; 390 if (mod <= 1) { 391 if (!BN_add(rnd, rnd, add)) 392 goto err; 393 goto loop; 394 } 395 } 396 ret = 1; 397 398 err: 399 BN_CTX_end(ctx); 400 bn_check_top(rnd); 401 return ret; 402 } 403 404 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, 405 const BIGNUM *rem, BN_CTX *ctx) 406 { 407 int i, ret = 0; 408 BIGNUM *t1, *qadd, *q; 409 410 bits--; 411 BN_CTX_start(ctx); 412 t1 = BN_CTX_get(ctx); 413 q = BN_CTX_get(ctx); 414 qadd = BN_CTX_get(ctx); 415 if (qadd == NULL) 416 goto err; 417 418 if (!BN_rshift1(qadd, padd)) 419 goto err; 420 421 if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) 422 goto err; 423 424 /* we need ((rnd-rem) % add) == 0 */ 425 if (!BN_mod(t1, q, qadd, ctx)) 426 goto err; 427 if (!BN_sub(q, q, t1)) 428 goto err; 429 if (rem == NULL) { 430 if (!BN_add_word(q, 1)) 431 goto err; 432 } else { 433 if (!BN_rshift1(t1, rem)) 434 goto err; 435 if (!BN_add(q, q, t1)) 436 goto err; 437 } 438 439 /* we now have a random number 'rand' to test. */ 440 if (!BN_lshift1(p, q)) 441 goto err; 442 if (!BN_add_word(p, 1)) 443 goto err; 444 445 loop: 446 for (i = 1; i < NUMPRIMES; i++) { 447 /* check that p and q are prime */ 448 /* 449 * check that for p and q gcd(p-1,primes) == 1 (except for 2) 450 */ 451 BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); 452 BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); 453 if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) 454 goto err; 455 if (pmod == 0 || qmod == 0) { 456 if (!BN_add(p, p, padd)) 457 goto err; 458 if (!BN_add(q, q, qadd)) 459 goto err; 460 goto loop; 461 } 462 } 463 ret = 1; 464 465 err: 466 BN_CTX_end(ctx); 467 bn_check_top(p); 468 return ret; 469 } 470