Avoid doing a variable time division during Montgomery setup

Instead require the inputs be reduced already. For RSA-CRT use
Barrett which is const time already. For SRP6 inputs were not reduced,
use the Barrett hook available in DL_Group.

5 files changed, 25 insertions, 14 deletions

diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index f3d85e44c..f2a31d8e1 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -230,8 +230,9 @@ Montgomery_Int::Montgomery_Int(const std::shared_ptr<const Montgomery_Params> pa
       }
    else
       {
+      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
       secure_vector<word> ws;
-      m_v = m_params->mul(v % m_params->p(), m_params->R2(), ws);
+      m_v = m_params->mul(v, m_params->R2(), ws);
       }
    }
 
@@ -243,8 +244,9 @@ Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
    {
    if(redc_needed)
       {
+      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
       secure_vector<word> ws;
-      m_v = m_params->mul(m_v % m_params->p(), m_params->R2(), ws);
+      m_v = m_params->mul(m_v, m_params->R2(), ws);
       }
    }
 
@@ -256,8 +258,9 @@ Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
    {
    if(redc_needed)
       {
+      BOTAN_ASSERT_NOMSG(m_v < m_params->p());
       secure_vector<word> ws;
-      m_v = m_params->mul(m_v % m_params->p(), m_params->R2(), ws);
+      m_v = m_params->mul(m_v, m_params->R2(), ws);
       }
    }
 
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index 7590005a0..cc415815d 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -41,6 +41,8 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c
    m_window_bits(window_bits == 0 ? 4 : window_bits),
    m_const_time(const_time)
    {
+   BOTAN_ARG_CHECK(g < m_params->p(), "Montygomery base too big");
+
    if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ...
       throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");
 
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index 8cb3f6a08..99fbe9814 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -22,7 +22,7 @@ void Montgomery_Exponentiator::set_exponent(const BigInt& exp)
 void Montgomery_Exponentiator::set_base(const BigInt& base)
    {
    size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
-   m_monty = monty_precompute(m_monty_params, base, window_bits);
+   m_monty = monty_precompute(m_monty_params, m_mod_p.reduce(base), window_bits);
    }
 
 BigInt Montgomery_Exponentiator::execute() const
diff --git a/src/lib/misc/srp6/srp6.cpp b/src/lib/misc/srp6/srp6.cpp
index 0ec4fd2bb..825c38589 100644
--- a/src/lib/misc/srp6/srp6.cpp
+++ b/src/lib/misc/srp6/srp6.cpp
@@ -103,7 +103,8 @@ srp6_client_agree(const std::string& identifier,
 
    const BigInt x = compute_x(hash_id, identifier, password, salt);
 
-   const BigInt S = power_mod((B - (k * power_mod(g, x, p))) % p, (a + (u * x)), p);
+   const BigInt S = power_mod(group.mod_p(B - (k * power_mod(g, x, p))),
+                              group.mod_p(a + (u * x)), p);
 
    const SymmetricKey Sk(BigInt::encode_1363(S, p_bytes));
 
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 9334ff4cd..9f14b9d6a 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -238,21 +238,26 @@ class RSA_Private_Operation
 
          const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
 
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
+#if defined(BOTAN_TARGET_OS_HAS_THREADS) && !defined(BOTAN_HAS_VALGRIND)
+   #define BOTAN_RSA_USE_ASYNC
+#endif
+
+
+#if defined(BOTAN_RSA_USE_ASYNC)
          auto future_j1 = std::async(std::launch::async, [this, &m, &d1_mask, powm_window]() {
-               const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
-               auto powm_d1_p = monty_precompute(m_monty_p, m, powm_window);
-               return monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
-            });
-#else
+#endif
          const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
-         auto powm_d1_p = monty_precompute(m_monty_p, m, powm_window);
+         auto powm_d1_p = monty_precompute(m_monty_p, m_mod_p.reduce(m), powm_window);
          BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
+
+#if defined(BOTAN_RSA_USE_ASYNC)
+         return j1;
+         });
 #endif
 
          const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
          const BigInt masked_d2 = m_key.get_d2() + (d2_mask * (m_key.get_q() - 1));
-         auto powm_d2_q = monty_precompute(m_monty_q, m, powm_window);
+         auto powm_d2_q = monty_precompute(m_monty_q, m_mod_q.reduce(m), powm_window);
          const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
 
          /*
@@ -263,7 +268,7 @@ class RSA_Private_Operation
          * m = j2 + h*q
          */
 
-#if defined(BOTAN_TARGET_OS_HAS_THREADS)
+#if defined(BOTAN_RSA_USE_ASYNC)
          BigInt j1 = future_j1.get();
 #endif