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 /doc/man3/BN_cmp.pod | |
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 'doc/man3/BN_cmp.pod')
-rw-r--r-- | doc/man3/BN_cmp.pod | 14 |
1 files changed, 13 insertions, 1 deletions
diff --git a/doc/man3/BN_cmp.pod b/doc/man3/BN_cmp.pod index f302818f21..e9ddf8fa2d 100644 --- a/doc/man3/BN_cmp.pod +++ b/doc/man3/BN_cmp.pod @@ -2,7 +2,8 @@ =head1 NAME -BN_cmp, BN_ucmp, BN_is_zero, BN_is_one, BN_is_word, BN_abs_is_word, BN_is_odd - BIGNUM comparison and test functions +BN_cmp, BN_ucmp, BN_is_zero, BN_is_one, BN_is_word, BN_abs_is_word, BN_is_odd, BN_are_coprime +- BIGNUM comparison and test functions =head1 SYNOPSIS @@ -17,6 +18,8 @@ BN_cmp, BN_ucmp, BN_is_zero, BN_is_one, BN_is_word, BN_abs_is_word, BN_is_odd - int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w); int BN_is_odd(const BIGNUM *a); + int BN_are_coprime(BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); + =head1 DESCRIPTION BN_cmp() compares the numbers I<a> and I<b>. BN_ucmp() compares their @@ -26,6 +29,10 @@ BN_is_zero(), BN_is_one(), BN_is_word() and BN_abs_is_word() test if I<a> equals 0, 1, I<w>, or E<verbar>I<w>E<verbar> respectively. BN_is_odd() tests if I<a> is odd. +BN_are_coprime() determines if B<a> and B<b> are coprime. +B<ctx> is used internally for storing temporary variables. +The values of B<a> and B<b> and B<ctx> must not be NULL. + =head1 RETURN VALUES BN_cmp() returns -1 if I<a> E<lt> I<b>, 0 if I<a> == I<b> and 1 if @@ -35,11 +42,16 @@ of I<a> and I<b>. BN_is_zero(), BN_is_one() BN_is_word(), BN_abs_is_word() and BN_is_odd() return 1 if the condition is true, 0 otherwise. +BN_are_coprime() returns 1 if the B<BIGNUM>'s are coprime, otherwise it +returns 0. + =head1 HISTORY Prior to OpenSSL 1.1.0, BN_is_zero(), BN_is_one(), BN_is_word(), BN_abs_is_word() and BN_is_odd() were macros. +The function BN_are_coprime() was added in OpenSSL 3.1. + =head1 COPYRIGHT Copyright 2000-2021 The OpenSSL Project Authors. All Rights Reserved. |