Drop some trial-division primes for 1024-bit candidates.
This is helpful at smaller sizes because the benefits of an unlikely hit
by trival-division are smaller.
The full set of kPrimes eliminates about 94.3% of random numbers. The
first quarter eliminates about 93.2% of them. But the little extra power
of the full set seems to be borderline for RSA 3072 and clearly positive
for RSA 4096.
Did 316 RSA 2048 key-gen operations in 30035598us (10.5 ops/sec)
min: 19423us, median: 80448us, max: 394265us
Change-Id: Iee53f721329674ae7a08fabd85b4f645c24e119d
Reviewed-on: https://boringssl-review.googlesource.com/26944
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index d2dfc2c..a18d377 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -119,10 +119,8 @@
// Zimmermann's, as implemented in PGP. I have had a read of his comments and
// implemented my own version.
-#define NUMPRIMES 2048
-
-// primes contains all the primes that fit into a uint16_t.
-static const uint16_t primes[NUMPRIMES] = {
+// kPrimes contains the first 2048 primes.
+static const uint16_t kPrimes[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
@@ -343,6 +341,16 @@
return 28;
}
+// num_trial_division_primes returns the number of primes to try with trial
+// division before using more expensive checks. For larger numbers, the value
+// of excluding a candidate with trial division is larger.
+static size_t num_trial_division_primes(const BIGNUM *n) {
+ if (n->width * BN_BITS2 > 1024) {
+ return OPENSSL_ARRAY_SIZE(kPrimes);
+ }
+ return OPENSSL_ARRAY_SIZE(kPrimes) / 4;
+}
+
// BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time
// primality test. See |BN_primality_test| for details. This number is selected
// so that, for a candidate N-bit RSA prime, picking |BN_PRIME_CHECKS_BLINDED|
@@ -592,9 +600,10 @@
}
static int bn_trial_division(uint16_t *out, const BIGNUM *bn) {
- for (int i = 1; i < NUMPRIMES; i++) {
- if (bn_mod_u16_consttime(bn, primes[i]) == 0) {
- *out = primes[i];
+ const size_t num_primes = num_trial_division_primes(bn);
+ for (size_t i = 1; i < num_primes; i++) {
+ if (bn_mod_u16_consttime(bn, kPrimes[i]) == 0) {
+ *out = kPrimes[i];
return 1;
}
}
@@ -805,7 +814,8 @@
return ret;
}
-int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) {
+int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx,
+ BN_GENCB *cb) {
return BN_is_prime_fasttest_ex(candidate, checks, ctx, 0, cb);
}
@@ -959,10 +969,10 @@
}
static int probable_prime(BIGNUM *rnd, int bits) {
- int i;
- uint16_t mods[NUMPRIMES];
+ uint16_t mods[OPENSSL_ARRAY_SIZE(kPrimes)];
+ const size_t num_primes = num_trial_division_primes(rnd);
BN_ULONG delta;
- BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];
+ BN_ULONG maxdelta = BN_MASK2 - kPrimes[num_primes - 1];
char is_single_word = bits <= BN_BITS2;
again:
@@ -971,8 +981,8 @@
}
// we now have a random number 'rnd' to test.
- for (i = 1; i < NUMPRIMES; i++) {
- mods[i] = bn_mod_u16_consttime(rnd, primes[i]);
+ for (size_t i = 1; i < num_primes; i++) {
+ mods[i] = bn_mod_u16_consttime(rnd, kPrimes[i]);
}
// If bits is so small that it fits into a single word then we
// additionally don't want to exceed that many bits.
@@ -996,15 +1006,15 @@
// 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
+ // 1) It's greater than kPrimes[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 && primes[i] < rnd_word; i++) {
- if ((mods[i] + delta) % primes[i] == 0) {
+ for (size_t i = 1; i < num_primes && kPrimes[i] < rnd_word; i++) {
+ if ((mods[i] + delta) % kPrimes[i] == 0) {
delta += 2;
if (delta > maxdelta) {
goto again;
@@ -1013,10 +1023,10 @@
}
}
} else {
- for (i = 1; i < NUMPRIMES; i++) {
+ for (size_t i = 1; i < num_primes; 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) {
+ if (((mods[i] + delta) % kPrimes[i]) <= 1) {
delta += 2;
if (delta > maxdelta) {
goto again;
@@ -1038,7 +1048,7 @@
static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,
const BIGNUM *rem, BN_CTX *ctx) {
- int i, ret = 0;
+ int ret = 0;
BIGNUM *t1;
BN_CTX_start(ctx);
@@ -1069,10 +1079,11 @@
}
// we now have a random number 'rand' to test.
+ const size_t num_primes = num_trial_division_primes(rnd);
loop:
- for (i = 1; i < NUMPRIMES; i++) {
+ for (size_t i = 1; i < num_primes; i++) {
// check that rnd is a prime
- if (bn_mod_u16_consttime(rnd, primes[i]) <= 1) {
+ if (bn_mod_u16_consttime(rnd, kPrimes[i]) <= 1) {
if (!BN_add(rnd, rnd, add)) {
goto err;
}
@@ -1089,7 +1100,7 @@
static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
const BIGNUM *rem, BN_CTX *ctx) {
- int i, ret = 0;
+ int ret = 0;
BIGNUM *t1, *qadd, *q;
bits--;
@@ -1139,13 +1150,14 @@
goto err;
}
+ const size_t num_primes = num_trial_division_primes(p);
loop:
- for (i = 1; i < NUMPRIMES; i++) {
+ for (size_t i = 1; i < num_primes; i++) {
// check that p and q are prime
// check that for p and q
// gcd(p-1,primes) == 1 (except for 2)
- if (bn_mod_u16_consttime(p, primes[i]) == 0 ||
- bn_mod_u16_consttime(q, primes[i]) == 0) {
+ if (bn_mod_u16_consttime(p, kPrimes[i]) == 0 ||
+ bn_mod_u16_consttime(q, kPrimes[i]) == 0) {
if (!BN_add(p, p, padd)) {
goto err;
}
