Reduce the input base |a| in BN_mod_exp_mont_consttime for RSAZ.

Note that this adds new non-constant-time code into the RSAZ-based
code path.

Change-Id: Ibca3bc523ede131b55c70ac5066c0014df1f5a70
Reviewed-on: https://boringssl-review.googlesource.com/12525
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/bn/exponentiation.c b/crypto/bn/exponentiation.c
index 2d68808..e384c3a 100644
--- a/crypto/bn/exponentiation.c
+++ b/crypto/bn/exponentiation.c
@@ -876,6 +876,7 @@
   int powerbufLen = 0;
   unsigned char *powerbuf = NULL;
   BIGNUM tmp, am;
+  BIGNUM *new_a = NULL;
 
   if (!BN_is_odd(m)) {
     OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
@@ -903,6 +904,15 @@
     mont = new_mont;
   }
 
+  if (a->neg || BN_ucmp(a, m) >= 0) {
+    new_a = BN_new();
+    if (new_a == NULL ||
+        !BN_nnmod(new_a, a, m, ctx)) {
+      goto err;
+    }
+    a = new_a;
+  }
+
 #ifdef RSAZ_ENABLED
   /* If the size of the operands allow it, perform the optimized
    * RSAZ exponentiation. For further information see
@@ -991,12 +1001,9 @@
   }
 
   /* prepare a^1 in Montgomery domain */
-  if (a->neg || BN_ucmp(a, m) >= 0) {
-    if (!BN_nnmod(&am, a, m, ctx) ||
-        !BN_to_montgomery(&am, &am, mont, ctx)) {
-      goto err;
-    }
-  } else if (!BN_to_montgomery(&am, a, mont, ctx)) {
+  assert(!a->neg);
+  assert(BN_ucmp(a, m) < 0);
+  if (!BN_to_montgomery(&am, a, mont, ctx)) {
     goto err;
   }
 
@@ -1190,6 +1197,7 @@
 
 err:
   BN_MONT_CTX_free(new_mont);
+  BN_clear_free(new_a);
   if (powerbuf != NULL) {
     OPENSSL_cleanse(powerbuf, powerbufLen);
     OPENSSL_free(powerbufFree);