| 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 | }
|
|---|
