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.

4 files changed, 54 insertions, 8 deletions

diff --git a/news.rst b/news.rst
index ca3ec8607..73f691462 100644
--- a/news.rst
+++ b/news.rst
@@ -6,7 +6,8 @@ Version 2.6.0, Not Yet Released
 
 * Add support for OAEP labels (GH #1508)
 
-* RSA signing optimizations, about 15% faster (GH #1523)
+* RSA signing is about 15% faster (GH #1523) and RSA verification is
+  about 50% faster.
 
 * Add exponent blinding to RSA (GH #1523)
 
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
 */
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index fd95f187f..69d7052dc 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -341,7 +341,9 @@ class RSA_Public_Operation
    {
    public:
       explicit RSA_Public_Operation(const RSA_PublicKey& rsa) :
-         m_n(rsa.get_n()), m_powermod_e_n(rsa.get_e(), rsa.get_n())
+         m_n(rsa.get_n()),
+         m_e(rsa.get_e()),
+         m_monty_n(std::make_shared<Montgomery_Params>(m_n))
          {}
 
       size_t get_max_input_bits() const { return (m_n.bits() - 1); }
@@ -351,17 +353,22 @@ class RSA_Public_Operation
          {
          if(m >= m_n)
             throw Invalid_Argument("RSA public op - input is too large");
-         return m_powermod_e_n(m);
+
+         const size_t powm_window = 1;
+
+         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window);
+         return monty_execute_vartime(*powm_m_n, m_e);
          }
 
       const BigInt& get_n() const { return m_n; }
 
       const BigInt& m_n;
-      Fixed_Exponent_Power_Mod m_powermod_e_n;
+      const BigInt& m_e;
+      std::shared_ptr<Montgomery_Params> m_monty_n;
    };
 
 class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
-                                 private RSA_Public_Operation
+                                       private RSA_Public_Operation
    {
    public:
 
@@ -374,7 +381,7 @@ class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
       size_t max_raw_input_bits() const override { return get_max_input_bits(); }
 
       secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len,
-                                      RandomNumberGenerator&) override
+                                         RandomNumberGenerator&) override
          {
          BigInt m(msg, msg_len);
          return BigInt::encode_1363(public_op(m), m_n.bytes());
@@ -382,7 +389,7 @@ class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
    };
 
 class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA,
-                             private RSA_Public_Operation
+                                   private RSA_Public_Operation
    {
    public:
 
@@ -404,7 +411,7 @@ class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA,
    };
 
 class RSA_KEM_Encryption_Operation final : public PK_Ops::KEM_Encryption_with_KDF,
-                                     private RSA_Public_Operation
+                                           private RSA_Public_Operation
    {
    public: