aboutsummaryrefslogtreecommitdiffstats
path: root/crypto/bn/bn_prime.c
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/bn/bn_prime.c')
-rw-r--r--crypto/bn/bn_prime.c201
1 files changed, 60 insertions, 141 deletions
diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 6d74da26d3c7..d0cf3779fa50 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -1,5 +1,5 @@
/*
- * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
*
* Licensed under the OpenSSL license (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
@@ -22,10 +22,12 @@
static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
const BIGNUM *a1_odd, int k, BN_CTX *ctx,
BN_MONT_CTX *mont);
-static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods);
-static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
- const BIGNUM *add, const BIGNUM *rem,
- BN_CTX *ctx);
+static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods);
+static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
+ const BIGNUM *add, const BIGNUM *rem,
+ BN_CTX *ctx);
+
+#define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x))
int BN_GENCB_call(BN_GENCB *cb, int a, int b)
{
@@ -87,16 +89,11 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
loop:
/* make a random number and set the top and bottom bits */
if (add == NULL) {
- if (!probable_prime(ret, bits, mods))
+ if (!probable_prime(ret, bits, safe, mods))
goto err;
} else {
- if (safe) {
- if (!probable_prime_dh_safe(ret, bits, add, rem, ctx))
- goto err;
- } else {
- if (!bn_probable_prime_dh(ret, bits, add, rem, ctx))
- goto err;
- }
+ if (!probable_prime_dh(ret, bits, safe, mods, add, rem, ctx))
+ goto err;
}
if (!BN_GENCB_call(cb, 0, c1++))
@@ -272,17 +269,18 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
return 1;
}
-static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
+static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods)
{
int i;
BN_ULONG delta;
BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
- char is_single_word = bits <= BN_BITS2;
again:
/* TODO: Not all primes are private */
if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD))
return 0;
+ if (safe && !BN_set_bit(rnd, 1))
+ return 0;
/* we now have a random number 'rnd' to test. */
for (i = 1; i < NUMPRIMES; i++) {
BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
@@ -290,61 +288,25 @@ static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
return 0;
mods[i] = (prime_t) mod;
}
- /*
- * If bits is so small that it fits into a single word then we
- * additionally don't want to exceed that many bits.
- */
- if (is_single_word) {
- BN_ULONG size_limit;
-
- if (bits == BN_BITS2) {
- /*
- * Shifting by this much has undefined behaviour so we do it a
- * different way
- */
- size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);
- } else {
- size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;
- }
- if (size_limit < maxdelta)
- maxdelta = size_limit;
- }
delta = 0;
loop:
- if (is_single_word) {
- BN_ULONG rnd_word = BN_get_word(rnd);
-
- /*-
- * In the case that the candidate prime is a single word then
- * we check that:
- * 1) It's greater than primes[i] because we shouldn't reject
- * 3 as being a prime number because it's a multiple of
- * three.
- * 2) That it's not a multiple of a known prime. We don't
- * check that rnd-1 is also coprime to all the known
- * primes because there aren't many small primes where
- * that's true.
+ for (i = 1; i < NUMPRIMES; i++) {
+ /*
+ * check that rnd is a prime and also that
+ * gcd(rnd-1,primes) == 1 (except for 2)
+ * do the second check only if we are interested in safe primes
+ * in the case that the candidate prime is a single word then
+ * we check only the primes up to sqrt(rnd)
*/
- for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {
- if ((mods[i] + delta) % primes[i] == 0) {
- delta += 2;
- if (delta > maxdelta)
- goto again;
- goto loop;
- }
- }
- } else {
- for (i = 1; i < NUMPRIMES; i++) {
- /*
- * check that rnd is not a prime and also that gcd(rnd-1,primes)
- * == 1 (except for 2)
- */
- if (((mods[i] + delta) % primes[i]) <= 1) {
- delta += 2;
- if (delta > maxdelta)
- goto again;
- goto loop;
- }
+ if (bits <= 31 && delta <= 0x7fffffff
+ && square(primes[i]) > BN_get_word(rnd) + delta)
+ break;
+ if (safe ? (mods[i] + delta) % primes[i] <= 1
+ : (mods[i] + delta) % primes[i] == 0) {
+ delta += safe ? 4 : 2;
+ if (delta > maxdelta)
+ goto again;
+ goto loop;
}
}
if (!BN_add_word(rnd, delta))
@@ -355,16 +317,23 @@ static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
return 1;
}
-int bn_probable_prime_dh(BIGNUM *rnd, int bits,
- const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
+static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods,
+ const BIGNUM *add, const BIGNUM *rem,
+ BN_CTX *ctx)
{
int i, ret = 0;
BIGNUM *t1;
+ BN_ULONG delta;
+ BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
BN_CTX_start(ctx);
if ((t1 = BN_CTX_get(ctx)) == NULL)
goto err;
+ if (maxdelta > BN_MASK2 - BN_get_word(add))
+ maxdelta = BN_MASK2 - BN_get_word(add);
+
+ again:
if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
goto err;
@@ -375,98 +344,48 @@ int bn_probable_prime_dh(BIGNUM *rnd, int bits,
if (!BN_sub(rnd, rnd, t1))
goto err;
if (rem == NULL) {
- if (!BN_add_word(rnd, 1))
+ if (!BN_add_word(rnd, safe ? 3u : 1u))
goto err;
} else {
if (!BN_add(rnd, rnd, rem))
goto err;
}
- /* we now have a random number 'rand' to test. */
+ if (BN_num_bits(rnd) < bits
+ || BN_get_word(rnd) < (safe ? 5u : 3u)) {
+ if (!BN_add(rnd, rnd, add))
+ goto err;
+ }
- loop:
+ /* we now have a random number 'rnd' to test. */
for (i = 1; i < NUMPRIMES; i++) {
- /* check that rnd is a prime */
BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
if (mod == (BN_ULONG)-1)
goto err;
- if (mod <= 1) {
- if (!BN_add(rnd, rnd, add))
- goto err;
- goto loop;
- }
- }
- ret = 1;
-
- err:
- BN_CTX_end(ctx);
- bn_check_top(rnd);
- return ret;
-}
-
-static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
- const BIGNUM *rem, BN_CTX *ctx)
-{
- int i, ret = 0;
- BIGNUM *t1, *qadd, *q;
-
- bits--;
- BN_CTX_start(ctx);
- t1 = BN_CTX_get(ctx);
- q = BN_CTX_get(ctx);
- qadd = BN_CTX_get(ctx);
- if (qadd == NULL)
- goto err;
-
- if (!BN_rshift1(qadd, padd))
- goto err;
-
- if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
- goto err;
-
- /* we need ((rnd-rem) % add) == 0 */
- if (!BN_mod(t1, q, qadd, ctx))
- goto err;
- if (!BN_sub(q, q, t1))
- goto err;
- if (rem == NULL) {
- if (!BN_add_word(q, 1))
- goto err;
- } else {
- if (!BN_rshift1(t1, rem))
- goto err;
- if (!BN_add(q, q, t1))
- goto err;
+ mods[i] = (prime_t) mod;
}
-
- /* we now have a random number 'rand' to test. */
- if (!BN_lshift1(p, q))
- goto err;
- if (!BN_add_word(p, 1))
- goto err;
-
+ delta = 0;
loop:
for (i = 1; i < NUMPRIMES; i++) {
- /* check that p and q are prime */
- /*
- * check that for p and q gcd(p-1,primes) == 1 (except for 2)
- */
- BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);
- BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);
- if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1)
- goto err;
- if (pmod == 0 || qmod == 0) {
- if (!BN_add(p, p, padd))
- goto err;
- if (!BN_add(q, q, qadd))
- goto err;
+ /* check that rnd is a prime */
+ if (bits <= 31 && delta <= 0x7fffffff
+ && square(primes[i]) > BN_get_word(rnd) + delta)
+ break;
+ /* rnd mod p == 1 implies q = (rnd-1)/2 is divisible by p */
+ if (safe ? (mods[i] + delta) % primes[i] <= 1
+ : (mods[i] + delta) % primes[i] == 0) {
+ delta += BN_get_word(add);
+ if (delta > maxdelta)
+ goto again;
goto loop;
}
}
+ if (!BN_add_word(rnd, delta))
+ goto err;
ret = 1;
err:
BN_CTX_end(ctx);
- bn_check_top(p);
+ bn_check_top(rnd);
return ret;
}