Add a Montgomery exponentiation that takes variable time

In the case of RSA encryption/verification the public exponent is...
public. So we don't need to carefully guard against side channels
that leak the exponent.

Improves RSA verification performance by 50% or more.

2 files changed, 38 insertions, 0 deletions

diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index 18fb6d081..4bf281fa9 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -23,6 +23,8 @@ class Montgomery_Exponentation_State
                                      size_t window_bits);
 
       BigInt exponentiation(const BigInt& k) const;
+
+      BigInt exponentiation_vartime(const BigInt& k) const;
    private:
       std::shared_ptr<const Montgomery_Params> m_params;
       std::vector<Montgomery_Int> m_g;
@@ -112,6 +114,30 @@ BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) cons
    return x.value();
    }
 
+BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const
+   {
+   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;
+
+   for(size_t i = exp_nibbles; i > 0; --i)
+      {
+      for(size_t j = 0; j != m_window_bits; ++j)
+         {
+         x.square_this(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);
+      }
+
+   return x.value();
+   }
+
 std::shared_ptr<const Montgomery_Exponentation_State>
 monty_precompute(std::shared_ptr<const Montgomery_Params> params,
                  const BigInt& g,
@@ -126,6 +152,12 @@ BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
    return precomputed_state.exponentiation(k);
    }
 
+BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
+                             const BigInt& k)
+   {
+   return precomputed_state.exponentiation_vartime(k);
+   }
+
 BigInt monty_multi_exp(std::shared_ptr<const Montgomery_Params> params_p,
                        const BigInt& x_bn,
                        const BigInt& z1,
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
index 6eeec8bb4..6eeb88e7f 100644
--- a/src/lib/math/numbertheory/monty_exp.h
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -32,6 +32,12 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params_p,
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
                      const BigInt& k);
 
+/*
+* Return g^x mod p taking variable time
+*/
+BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
+                             const BigInt& k);
+
 /**
 * Return (x^z1 * y^z2) % p
 */