Minor optimization for Montgomery exponentiation

The loop started off by squaring the result value, but at that
point it is always one (or the Montgomery representation thereof).
Avoiding those squarings does not leak any information about the
exponent, because we haven't even looked at the exponent at that point.

Improves RSA verify performance by about 5%, everything else ~1% speedup

3 files changed, 26 insertions, 17 deletions

diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index 0560cc59e..2dbcbaa95 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -375,6 +375,13 @@ Montgomery_Int& Montgomery_Int::operator*=(const secure_vector<word>& other)
    return mul_by(other, ws);
    }
 
+Montgomery_Int& Montgomery_Int::square_this_n_times(secure_vector<word>& ws, size_t n)
+   {
+   for(size_t i = 0; i != n; ++i)
+      m_params->square_this(m_v, ws);
+   return (*this);
+   }
+
 Montgomery_Int& Montgomery_Int::square_this(secure_vector<word>& ws)
    {
    m_params->square_this(m_v, ws);
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index 7586b634f..23c36864e 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -94,6 +94,8 @@ class BOTAN_UNSTABLE_API Montgomery_Int final
 
       Montgomery_Int& square_this(secure_vector<word>& ws);
 
+      Montgomery_Int& square_this_n_times(secure_vector<word>& ws, size_t n);
+
       Montgomery_Int multiplicative_inverse() const;
 
       Montgomery_Int additive_inverse() const;
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index b5336ef14..c6a3be563 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -106,18 +106,17 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size
    secure_vector<word> e_bits(m_params->p_words());
    secure_vector<word> ws;
 
-   for(size_t i = exp_nibbles; i > 0; --i)
+   if(exp_nibbles > 0)
       {
-      for(size_t j = 0; j != m_window_bits; ++j)
+      const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
+      x.mul_by(e_bits, ws);
+
+      for(size_t i = exp_nibbles - 1; i > 0; --i)
          {
-         x.square_this(ws);
+         x.square_this_n_times(ws, m_window_bits);
+         const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits));
+         x.mul_by(e_bits, ws);
          }
-
-      const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
-
-      const_time_lookup(e_bits, m_g, nibble);
-
-      x.mul_by(e_bits, ws);
       }
 
    x.const_time_unpoison();
@@ -134,17 +133,18 @@ BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scal
 
    secure_vector<word> ws;
 
-   for(size_t i = exp_nibbles; i > 0; --i)
+   if(exp_nibbles > 0)
       {
-      for(size_t j = 0; j != m_window_bits; ++j)
+      const uint32_t nibble = scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits);
+      x.mul_by(m_g[nibble], ws);
+
+      for(size_t i = exp_nibbles - 1; i > 0; --i)
          {
-         x.square_this(ws);
+         x.square_this_n_times(ws, m_window_bits);
+         const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
+         if(nibble > 0)
+            x.mul_by(m_g[nibble], ws);
          }
-
-      const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
-
-      if(nibble > 0)
-         x.mul_by(m_g[nibble], ws);
       }
 
    x.const_time_unpoison();