Remove LCM dependency from RSA_check_key.

Instead of checking d * e = 1 (mod lcm(p-1, q-1)), we can separately
check d * e = 1 (mod p-1) and d * e = 1 (mod q-1). This drops an LCM
dependency from key import and is 2x faster.

(Our constant-time LCM implementation can probably be faster if we
tried, but now it's only used in RSA keygen, so it doesn't matter much.
It's also using the unoptimized constant-time division, which is
probably the next target if we decide we care about speeding this up.)

Before:
Did 6768 RSA 2048 checking operations in 3015824us (2244.2 ops/sec)
Did 5610 RSA 2048 signing operations in 3033396us (1849.4 ops/sec)
Did 1953 RSA 4096 checking operations in 3060828us (638.1 ops/sec)
Did 817 RSA 4096 signing operations in 3021092us (270.4 ops/sec)
After:
Did 13175 RSA 2048 checking operations in 3090576us (4263.0 ops/sec)
Did 5610 RSA 2048 signing operations in 3032966us (1849.7 ops/sec)
Did 3720 RSA 4096 checking operations in 3085971us (1205.5 ops/sec)
Did 820 RSA 4096 signing operations in 3027312us (270.9 ops/sec)

Bug: 316
Change-Id: Ie29554c02d31f586dd0f8bdee03a227f1d5dc916
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40146
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>

crypto/fipsmodule/rsa/rsa.c

diff --git a/crypto/fipsmodule/rsa/rsa.c b/crypto/fipsmodule/rsa/rsa.c
index a7fb7ae..2929673 100644
--- a/crypto/fipsmodule/rsa/rsa.c
+++ b/crypto/fipsmodule/rsa/rsa.c
@@ -655,7 +655,12 @@
 }
 
 static int check_mod_inverse(int *out_ok, const BIGNUM *a, const BIGNUM *ainv,
-                             const BIGNUM *m, int check_reduced, BN_CTX *ctx) {
+                             const BIGNUM *m, BN_CTX *ctx) {
+  if (BN_is_negative(ainv) || BN_cmp(ainv, m) >= 0) {
+    *out_ok = 0;
+    return 1;
+  }
+
   BN_CTX_start(ctx);
   BIGNUM *tmp = BN_CTX_get(ctx);
   int ret = tmp != NULL &&
@@ -663,19 +668,12 @@
             bn_div_consttime(NULL, tmp, tmp, m, ctx);
   if (ret) {
     *out_ok = BN_is_one(tmp);
-    if (check_reduced && (BN_is_negative(ainv) || BN_cmp(ainv, m) >= 0)) {
-      *out_ok = 0;
-    }
   }
   BN_CTX_end(ctx);
   return ret;
 }
 
 int RSA_check_key(const RSA *key) {
-  BIGNUM n, pm1, qm1, lcm, dmp1, dmq1, iqmp_times_q;
-  BN_CTX *ctx;
-  int ok = 0, has_crt_values;
-
   if (RSA_is_opaque(key)) {
     // Opaque keys can't be checked.
     return 1;
@@ -697,50 +695,53 @@
     return 1;
   }
 
-  ctx = BN_CTX_new();
+  BN_CTX *ctx = BN_CTX_new();
   if (ctx == NULL) {
     OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
     return 0;
   }
 
-  BN_init(&n);
+  BIGNUM tmp, de, pm1, qm1, dmp1, dmq1;
+  int ok = 0;
+  BN_init(&tmp);
+  BN_init(&de);
   BN_init(&pm1);
   BN_init(&qm1);
-  BN_init(&lcm);
   BN_init(&dmp1);
   BN_init(&dmq1);
-  BN_init(&iqmp_times_q);
-
-  int d_ok;
-  if (!bn_mul_consttime(&n, key->p, key->q, ctx) ||
-      // lcm = lcm(p, q)
-      !bn_usub_consttime(&pm1, key->p, BN_value_one()) ||
-      !bn_usub_consttime(&qm1, key->q, BN_value_one()) ||
-      !bn_lcm_consttime(&lcm, &pm1, &qm1, ctx) ||
-      // Other implementations use the Euler totient rather than the Carmichael
-      // totient, so allow unreduced |key->d|.
-      !check_mod_inverse(&d_ok, key->e, key->d, &lcm,
-                         0 /* don't require reduced */, ctx)) {
+  if (!bn_mul_consttime(&tmp, key->p, key->q, ctx)) {
     OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
     goto out;
   }
 
-  if (BN_cmp(&n, key->n) != 0) {
+  if (BN_cmp(&tmp, key->n) != 0) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_N_NOT_EQUAL_P_Q);
     goto out;
   }
 
-  if (!d_ok) {
-    OPENSSL_PUT_ERROR(RSA, RSA_R_D_E_NOT_CONGRUENT_TO_1);
-    goto out;
-  }
-
   if (BN_is_negative(key->d) || BN_cmp(key->d, key->n) >= 0) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_D_OUT_OF_RANGE);
     goto out;
   }
 
-  has_crt_values = key->dmp1 != NULL;
+  // d must be an inverse of e mod the Carmichael totient, lcm(p-1, q-1), but it
+  // may be unreduced because other implementations use the Euler totient. We
+  // simply check that d * e is one mod p-1 and mod q-1.
+  if (!bn_usub_consttime(&pm1, key->p, BN_value_one()) ||
+      !bn_usub_consttime(&qm1, key->q, BN_value_one()) ||
+      !bn_mul_consttime(&de, key->d, key->e, ctx) ||
+      !bn_div_consttime(NULL, &tmp, &de, &pm1, ctx) ||
+      !bn_div_consttime(NULL, &de, &de, &qm1, ctx)) {
+    OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
+    goto out;
+  }
+
+  if (!BN_is_one(&tmp) || !BN_is_one(&de)) {
+    OPENSSL_PUT_ERROR(RSA, RSA_R_D_E_NOT_CONGRUENT_TO_1);
+    goto out;
+  }
+
+  int has_crt_values = key->dmp1 != NULL;
   if (has_crt_values != (key->dmq1 != NULL) ||
       has_crt_values != (key->iqmp != NULL)) {
     OPENSSL_PUT_ERROR(RSA, RSA_R_INCONSISTENT_SET_OF_CRT_VALUES);
@@ -749,12 +750,9 @@
 
   if (has_crt_values) {
     int dmp1_ok, dmq1_ok, iqmp_ok;
-    if (!check_mod_inverse(&dmp1_ok, key->e, key->dmp1, &pm1,
-                           1 /* check reduced */, ctx) ||
-        !check_mod_inverse(&dmq1_ok, key->e, key->dmq1, &qm1,
-                           1 /* check reduced */, ctx) ||
-        !check_mod_inverse(&iqmp_ok, key->q, key->iqmp, key->p,
-                           1 /* check reduced */, ctx)) {
+    if (!check_mod_inverse(&dmp1_ok, key->e, key->dmp1, &pm1, ctx) ||
+        !check_mod_inverse(&dmq1_ok, key->e, key->dmq1, &qm1, ctx) ||
+        !check_mod_inverse(&iqmp_ok, key->q, key->iqmp, key->p, ctx)) {
       OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
       goto out;
     }
@@ -768,13 +766,12 @@
   ok = 1;
 
 out:
-  BN_free(&n);
+  BN_free(&tmp);
+  BN_free(&de);
   BN_free(&pm1);
   BN_free(&qm1);
-  BN_free(&lcm);
   BN_free(&dmp1);
   BN_free(&dmq1);
-  BN_free(&iqmp_times_q);
   BN_CTX_free(ctx);
 
   return ok;