diff options
author | slontis <shane.lontis@oracle.com> | 2022-11-02 12:01:34 +1000 |
---|---|---|
committer | Tomas Mraz <tomas@openssl.org> | 2022-11-21 11:20:38 +0100 |
commit | 1136c4dc39150a89754827285787b0dd48562e0a (patch) | |
tree | f4336788db9bcd5eec382b58626265d893983dd2 /test/bntest.c | |
parent | 6f6f413312934e5ab8250741e2535293e1d7b237 (diff) |
Improve FIPS RSA keygen performance.
FIPS 186-4 has 5 different algorithms for key generation,
and all of them rely on testing GCD(a,n) == 1 many times.
Cachegrind was showing that during a RSA keygen operation,
the function BN_gcd() was taking a considerable percentage
of the total cycles.
The default provider uses multiprime keygen, which seemed to
be much faster. This is because it uses BN_mod_inverse()
instead.
For a 4096 bit key, the entropy of a key that was taking a
long time to generate was recorded and fed back into subsequent
runs. Roughly 40% of the cycle time was BN_gcd() with most of the
remainder in the prime testing. Changing to use the inverse
resulted in the cycle count being 96% in the prime testing.
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/19578)
(cherry picked from commit dd1d7bcb69994d81662e709b0ad838880b943870)
Diffstat (limited to 'test/bntest.c')
-rw-r--r-- | test/bntest.c | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/test/bntest.c b/test/bntest.c index 00b9b8cfd8..a91ba7f4d1 100644 --- a/test/bntest.c +++ b/test/bntest.c @@ -38,6 +38,7 @@ typedef struct mpitest_st { static const int NUM0 = 100; /* number of tests */ static const int NUM1 = 50; /* additional tests for some functions */ +static const int NUM_PRIME_TESTS = 20; static BN_CTX *ctx; /* @@ -2588,6 +2589,25 @@ static int test_ctx_consttime_flag(void) return st; } +static int test_coprime(void) +{ + BIGNUM *a = NULL, *b = NULL; + int ret = 0; + + ret = TEST_ptr(a = BN_new()) + && TEST_ptr(b = BN_new()) + && TEST_true(BN_set_word(a, 66)) + && TEST_true(BN_set_word(b, 99)) + && TEST_int_eq(BN_are_coprime(a, b, ctx), 0) + && TEST_int_eq(BN_are_coprime(b, a, ctx), 0) + && TEST_true(BN_set_word(a, 67)) + && TEST_int_eq(BN_are_coprime(a, b, ctx), 1) + && TEST_int_eq(BN_are_coprime(b, a, ctx), 1); + BN_free(a); + BN_free(b); + return ret; +} + static int test_gcd_prime(void) { BIGNUM *a = NULL, *b = NULL, *gcd = NULL; @@ -2600,11 +2620,12 @@ static int test_gcd_prime(void) if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL))) goto err; - for (i = 0; i < NUM0; i++) { + for (i = 0; i < NUM_PRIME_TESTS; i++) { if (!TEST_true(BN_generate_prime_ex(b, 1024, 0, NULL, NULL, NULL)) || !TEST_true(BN_gcd(gcd, a, b, ctx)) - || !TEST_true(BN_is_one(gcd))) + || !TEST_true(BN_is_one(gcd)) + || !TEST_true(BN_are_coprime(a, b, ctx))) goto err; } @@ -3081,6 +3102,7 @@ int setup_tests(void) ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes)); ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes)); ADD_TEST(test_gcd_prime); + ADD_TEST(test_coprime); ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests)); ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests)); ADD_TEST(test_mod_exp2_mont); |