4 files changed, 22 insertions, 13 deletions
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index b32a7ab4c..b5336ef14 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -23,7 +23,7 @@ class Montgomery_Exponentation_State
                                      size_t window_bits,
                                      bool const_time);
 
-      BigInt exponentiation(const BigInt& k) const;
+      BigInt exponentiation(const BigInt& k, size_t max_k_bits) const;
 
       BigInt exponentiation_vartime(const BigInt& k) const;
    private:
@@ -71,8 +71,8 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c
 namespace {
 
 void const_time_lookup(secure_vector<word>& output,
-                        const std::vector<Montgomery_Int>& g,
-                        size_t nibble)
+                       const std::vector<Montgomery_Int>& g,
+                       size_t nibble)
    {
    const size_t words = output.size();
 
@@ -94,10 +94,12 @@ void const_time_lookup(secure_vector<word>& output,
 
 }
 
-BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) const
+BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
    {
-   const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
-   CT::unpoison(exp_nibbles);
+   BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
+   // TODO add a const-time implementation of above assert and use it in release builds
+
+   const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
 
    Montgomery_Int x(m_params, m_params->R1(), false);
 
@@ -159,9 +161,9 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params,
    }
 
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
-                     const BigInt& k)
+                     const BigInt& k, size_t max_k_bits)
    {
-   return precomputed_state.exponentiation(k);
+   return precomputed_state.exponentiation(k, max_k_bits);
    }
 
 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
index 61da258cc..632d7f7d6 100644
--- a/src/lib/math/numbertheory/monty_exp.h
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -28,13 +28,14 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params_p,
                  bool const_time = true);
 
 /*
-* Return g^x mod p
+* Return g^k mod p
 */
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
-                     const BigInt& k);
+                     const BigInt& k, size_t max_k_bits);
 
 /*
-* Return g^x mod p taking variable time
+* Return g^k mod p taking variable time depending on k
+* @warning only use this if k is public
 */
 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
                              const BigInt& k);
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index a5c7a40ab..593abb6a7 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -524,6 +524,7 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
    const BigInt n_minus_1 = n - 1;
    const size_t s = low_zero_bits(n_minus_1);
    const BigInt nm1_s = n_minus_1 >> s;
+   const size_t n_bits = n.bits();
 
    const Modular_Reducer mod_n(n);
    auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
@@ -536,7 +537,7 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
 
       auto powm_a_n = monty_precompute(monty_n, a, powm_window);
 
-      BigInt y = monty_execute(*powm_a_n, nm1_s);
+      BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits);
 
       if(mr_witness(std::move(y), mod_n, n_minus_1, s))
          return false;
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index 5da91796f..8cb3f6a08 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -10,6 +10,7 @@
 #include <botan/numthry.h>
 #include <botan/monty.h>
 #include <botan/internal/monty_exp.h>
+#include <botan/internal/rounding.h>
 
 namespace Botan {
 
@@ -26,7 +27,11 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
 
 BigInt Montgomery_Exponentiator::execute() const
    {
-   return monty_execute(*m_monty, m_e);
+   /*
+   This leaks size of e via loop iterations, not possible to fix without
+   breaking this API. Round up to avoid leaking fine details.
+   */
+   return monty_execute(*m_monty, m_e, round_up(m_e.bits(), 8));
    }
 
 Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,