1 /* 2 * Copyright 1995-2020 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_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 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, int safe, prime_t *mods); 26 static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, 27 const BIGNUM *add, const BIGNUM *rem, 28 BN_CTX *ctx); 29 30 #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) 31 32 int BN_GENCB_call(BN_GENCB *cb, int a, int b) 33 { 34 /* No callback means continue */ 35 if (!cb) 36 return 1; 37 switch (cb->ver) { 38 case 1: 39 /* Deprecated-style callbacks */ 40 if (!cb->cb.cb_1) 41 return 1; 42 cb->cb.cb_1(a, b, cb->arg); 43 return 1; 44 case 2: 45 /* New-style callbacks */ 46 return cb->cb.cb_2(a, b, cb); 47 default: 48 break; 49 } 50 /* Unrecognised callback type */ 51 return 0; 52 } 53 54 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, 55 const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) 56 { 57 BIGNUM *t; 58 int found = 0; 59 int i, j, c1 = 0; 60 BN_CTX *ctx = NULL; 61 prime_t *mods = NULL; 62 int checks = BN_prime_checks_for_size(bits); 63 64 if (bits < 2) { 65 /* There are no prime numbers this small. */ 66 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); 67 return 0; 68 } else if (add == NULL && safe && bits < 6 && bits != 3) { 69 /* 70 * The smallest safe prime (7) is three bits. 71 * But the following two safe primes with less than 6 bits (11, 23) 72 * are unreachable for BN_rand with BN_RAND_TOP_TWO. 73 */ 74 BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL); 75 return 0; 76 } 77 78 mods = OPENSSL_zalloc(sizeof(*mods) * NUMPRIMES); 79 if (mods == NULL) 80 goto err; 81 82 ctx = BN_CTX_new(); 83 if (ctx == NULL) 84 goto err; 85 BN_CTX_start(ctx); 86 t = BN_CTX_get(ctx); 87 if (t == NULL) 88 goto err; 89 loop: 90 /* make a random number and set the top and bottom bits */ 91 if (add == NULL) { 92 if (!probable_prime(ret, bits, safe, mods)) 93 goto err; 94 } else { 95 if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx)) 96 goto err; 97 } 98 99 if (!BN_GENCB_call(cb, 0, c1++)) 100 /* aborted */ 101 goto err; 102 103 if (!safe) { 104 i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); 105 if (i == -1) 106 goto err; 107 if (i == 0) 108 goto loop; 109 } else { 110 /* 111 * for "safe prime" generation, check that (p-1)/2 is prime. Since a 112 * prime is odd, We just need to divide by 2 113 */ 114 if (!BN_rshift1(t, ret)) 115 goto err; 116 117 for (i = 0; i < checks; i++) { 118 j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); 119 if (j == -1) 120 goto err; 121 if (j == 0) 122 goto loop; 123 124 j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); 125 if (j == -1) 126 goto err; 127 if (j == 0) 128 goto loop; 129 130 if (!BN_GENCB_call(cb, 2, c1 - 1)) 131 goto err; 132 /* We have a safe prime test pass */ 133 } 134 } 135 /* we have a prime :-) */ 136 found = 1; 137 err: 138 OPENSSL_free(mods); 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, int safe, prime_t *mods) 273 { 274 int i; 275 BN_ULONG delta; 276 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 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 if (safe && !BN_set_bit(rnd, 1)) 283 return 0; 284 /* we now have a random number 'rnd' to test. */ 285 for (i = 1; i < NUMPRIMES; i++) { 286 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 287 if (mod == (BN_ULONG)-1) 288 return 0; 289 mods[i] = (prime_t) mod; 290 } 291 delta = 0; 292 loop: 293 for (i = 1; i < NUMPRIMES; i++) { 294 /* 295 * check that rnd is a prime and also that 296 * gcd(rnd-1,primes) == 1 (except for 2) 297 * do the second check only if we are interested in safe primes 298 * in the case that the candidate prime is a single word then 299 * we check only the primes up to sqrt(rnd) 300 */ 301 if (bits <= 31 && delta <= 0x7fffffff 302 && square(primes[i]) > BN_get_word(rnd) + delta) 303 break; 304 if (safe ? (mods[i] + delta) % primes[i] <= 1 305 : (mods[i] + delta) % primes[i] == 0) { 306 delta += safe ? 4 : 2; 307 if (delta > maxdelta) 308 goto again; 309 goto loop; 310 } 311 } 312 if (!BN_add_word(rnd, delta)) 313 return 0; 314 if (BN_num_bits(rnd) != bits) 315 goto again; 316 bn_check_top(rnd); 317 return 1; 318 } 319 320 static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, 321 const BIGNUM *add, const BIGNUM *rem, 322 BN_CTX *ctx) 323 { 324 int i, ret = 0; 325 BIGNUM *t1; 326 BN_ULONG delta; 327 BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; 328 329 BN_CTX_start(ctx); 330 if ((t1 = BN_CTX_get(ctx)) == NULL) 331 goto err; 332 333 if (maxdelta > BN_MASK2 - BN_get_word(add)) 334 maxdelta = BN_MASK2 - BN_get_word(add); 335 336 again: 337 if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) 338 goto err; 339 340 /* we need ((rnd-rem) % add) == 0 */ 341 342 if (!BN_mod(t1, rnd, add, ctx)) 343 goto err; 344 if (!BN_sub(rnd, rnd, t1)) 345 goto err; 346 if (rem == NULL) { 347 if (!BN_add_word(rnd, safe ? 3u : 1u)) 348 goto err; 349 } else { 350 if (!BN_add(rnd, rnd, rem)) 351 goto err; 352 } 353 354 if (BN_num_bits(rnd) < bits 355 || BN_get_word(rnd) < (safe ? 5u : 3u)) { 356 if (!BN_add(rnd, rnd, add)) 357 goto err; 358 } 359 360 /* we now have a random number 'rnd' to test. */ 361 for (i = 1; i < NUMPRIMES; i++) { 362 BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); 363 if (mod == (BN_ULONG)-1) 364 goto err; 365 mods[i] = (prime_t) mod; 366 } 367 delta = 0; 368 loop: 369 for (i = 1; i < NUMPRIMES; i++) { 370 /* check that rnd is a prime */ 371 if (bits <= 31 && delta <= 0x7fffffff 372 && square(primes[i]) > BN_get_word(rnd) + delta) 373 break; 374 /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */ 375 if (safe ? (mods[i] + delta) % primes[i] <= 1 376 : (mods[i] + delta) % primes[i] == 0) { 377 delta += BN_get_word(add); 378 if (delta > maxdelta) 379 goto again; 380 goto loop; 381 } 382 } 383 if (!BN_add_word(rnd, delta)) 384 goto err; 385 ret = 1; 386 387 err: 388 BN_CTX_end(ctx); 389 bn_check_top(rnd); 390 return ret; 391 } 392