Avoid useless multiplication in Montgomery exponentiation

When beginning the loop we initialized a value to one (in Montgomery form)
then multiply it by the first element looked up based on the exponent.
But this will always (after Montgomery multiplication) be exactly the
value we looked up in the table. So just assign it directly and avoid
the redundant operation.

Improves RSA verification by 5% or so since the number of multiplications
is so small in that case saving even 1 in useful. For other operations
there is no measurable improvement.

3 files changed, 39 insertions, 22 deletions

diff --git a/src/lib/math/numbertheory/monty.cpp b/src/lib/math/numbertheory/monty.cpp
index 2dbcbaa95..b91560fd5 100644
--- a/src/lib/math/numbertheory/monty.cpp
+++ b/src/lib/math/numbertheory/monty.cpp
@@ -248,6 +248,19 @@ Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
       }
    }
 
+Montgomery_Int::Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
+                               const word words[], size_t len,
+                               bool redc_needed) :
+   m_params(params),
+   m_v(words, len)
+   {
+   if(redc_needed)
+      {
+      secure_vector<word> ws;
+      m_v = m_params->mul(m_v % m_params->p(), m_params->R2(), ws);
+      }
+   }
+
 void Montgomery_Int::fix_size()
    {
    const size_t p_words = m_params->p_words();
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index 23c36864e..e5ab2f9ad 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -40,6 +40,13 @@ class BOTAN_UNSTABLE_API Montgomery_Int final
                      const uint8_t bits[], size_t len,
                      bool redc_needed = true);
 
+      /**
+      * Create a Montgomery_Int
+      */
+      Montgomery_Int(std::shared_ptr<const Montgomery_Params> params,
+                     const word words[], size_t len,
+                     bool redc_needed = true);
+
       bool operator==(const Montgomery_Int& other) const;
       bool operator!=(const Montgomery_Int& other) const { return (m_v != other.m_v); }
 
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index c6a3be563..3451b1955 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -101,22 +101,20 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size
 
    const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
 
-   Montgomery_Int x(m_params, m_params->R1(), false);
+   if(exp_nibbles == 0)
+      return 1;
 
    secure_vector<word> e_bits(m_params->p_words());
    secure_vector<word> ws;
 
-   if(exp_nibbles > 0)
+   const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
+   Montgomery_Int x(m_params, e_bits.data(), e_bits.size(), false);
+
+   for(size_t i = exp_nibbles - 1; i > 0; --i)
       {
-      const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
+      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);
-
-      for(size_t i = exp_nibbles - 1; i > 0; --i)
-         {
-         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);
-         }
       }
 
    x.const_time_unpoison();
@@ -129,22 +127,21 @@ BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scal
 
    const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
 
-   Montgomery_Int x(m_params, m_params->R1(), false);
-
    secure_vector<word> ws;
 
-   if(exp_nibbles > 0)
+   if(exp_nibbles == 0)
+      return 1;
+
+   const uint32_t nibble = scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits);
+   Montgomery_Int x = m_g[nibble];
+
+   for(size_t i = exp_nibbles - 1; i > 0; --i)
       {
-      const uint32_t nibble = scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits);
-      x.mul_by(m_g[nibble], ws);
+      x.square_this_n_times(ws, m_window_bits);
 
-      for(size_t i = exp_nibbles - 1; i > 0; --i)
-         {
-         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();