]> git.ipfire.org Git - thirdparty/openssl.git/commit - util/libcrypto.num
Improve FIPS RSA keygen performance.
authorslontis <shane.lontis@oracle.com>
Wed, 2 Nov 2022 02:01:34 +0000 (12:01 +1000)
committerTomas Mraz <tomas@openssl.org>
Mon, 21 Nov 2022 10:17:59 +0000 (11:17 +0100)
commitdd1d7bcb69994d81662e709b0ad838880b943870
treef24c3ce03aa4d0bd374ce4cba03d0968cd886b9c
parent88113f5dc6828694820d39612c3a760e386a0aa5
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)
crypto/bn/bn_gcd.c
crypto/bn/bn_rsa_fips186_4.c
doc/man3/BN_cmp.pod
include/openssl/bn.h
test/bntest.c
util/libcrypto.num