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)

2 files changed, 46 insertions, 9 deletions

diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c
index 91ad76a161..519bb4e951 100644
--- a/crypto/bn/bn_gcd.c
+++ b/crypto/bn/bn_gcd.c
@@ -534,6 +534,37 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
     return rv;
 }
 
+/*
+ * The numbers a and b are coprime if the only positive integer that is a
+ * divisor of both of them is 1.
+ * i.e. gcd(a,b) = 1.
+ *
+ * Coprimes have the property: b has a multiplicative inverse modulo a
+ * i.e there is some value x such that bx = 1 (mod a).
+ *
+ * Testing the modulo inverse is currently much faster than the constant
+ * time version of BN_gcd().
+ */
+int BN_are_coprime(BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
+{
+    int ret = 0;
+    BIGNUM *tmp;
+
+    BN_CTX_start(ctx);
+    tmp = BN_CTX_get(ctx);
+    if (tmp == NULL)
+        goto end;
+
+    ERR_set_mark();
+    BN_set_flags(a, BN_FLG_CONSTTIME);
+    ret = (BN_mod_inverse(tmp, a, b, ctx) != NULL);
+    /* Clear any errors (an error is returned if there is no inverse) */
+    ERR_pop_to_mark();
+end:
+    BN_CTX_end(ctx);
+    return ret;
+}
+
 /*-
  * This function is based on the constant-time GCD work by Bernstein and Yang:
  * https://eprint.iacr.org/2019/266
diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c
index 770ae4d1fa..e3a2ad76af 100644
--- a/crypto/bn/bn_rsa_fips186_4.c
+++ b/crypto/bn/bn_rsa_fips186_4.c
@@ -286,14 +286,20 @@ int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
             goto err;
     }
 
+    /*
+     * (Step 1) GCD(2r1, r2) = 1.
+     *    Note: This algorithm was doing a gcd(2r1, r2)=1 test before doing an
+     *    mod_inverse(2r1, r2) which are effectively the same operation.
+     *    (The algorithm assumed that the gcd test would be faster). Since the
+     *    mod_inverse is currently faster than calling the constant time
+     *    BN_gcd(), the call to BN_gcd() has been omitted. The inverse result
+     *    is used further down.
+     */
     if (!(BN_lshift1(r1x2, r1)
-            /* (Step 1) GCD(2r1, r2) = 1 */
-            && BN_gcd(tmp, r1x2, r2, ctx)
-            && BN_is_one(tmp)
+            && (BN_mod_inverse(tmp, r1x2, r2, ctx) != NULL)
             /* (Step 2) R = ((r2^-1 mod 2r1) * r2) - ((2r1^-1 mod r2)*2r1) */
-            && BN_mod_inverse(R, r2, r1x2, ctx)
+            && (BN_mod_inverse(R, r2, r1x2, ctx) != NULL)
             && BN_mul(R, R, r2, ctx) /* R = (r2^-1 mod 2r1) * r2 */
-            && BN_mod_inverse(tmp, r1x2, r2, ctx)
             && BN_mul(tmp, tmp, r1x2, ctx) /* tmp = (2r1^-1 mod r2)*2r1 */
             && BN_sub(R, R, tmp)
             /* Calculate 2r1r2 */
@@ -305,7 +311,8 @@ int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
 
     /*
      * In FIPS 186-4 imax was set to 5 * nlen/2.
-     * Analysis by Allen Roginsky (See https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf
+     * Analysis by Allen Roginsky
+     * (See https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf
      * page 68) indicates this has a 1 in 2 million chance of failure.
      * The number has been updated to 20 * nlen/2 as used in
      * FIPS186-5 Appendix B.9 Step 9.
@@ -337,10 +344,9 @@ int ossl_bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin,
 
             /* (Step 7) If GCD(Y-1) == 1 & Y is probably prime then return Y */
             if (BN_copy(y1, Y) == NULL
-                    || !BN_sub_word(y1, 1)
-                    || !BN_gcd(tmp, y1, e, ctx))
+                    || !BN_sub_word(y1, 1))
                 goto err;
-            if (BN_is_one(tmp)) {
+            if (BN_are_coprime(y1, e, ctx)) {
                 int rv = BN_check_prime(Y, ctx, cb);
 
                 if (rv > 0)