Split out Montgomery exponentation state

The existing Power_Mod classes are not thread safe so can't be used
in shared contexts.

5 files changed, 204 insertions, 112 deletions

diff --git a/src/lib/math/numbertheory/def_powm.h b/src/lib/math/numbertheory/def_powm.h
index 826ffb49f..fe705bf96 100644
--- a/src/lib/math/numbertheory/def_powm.h
+++ b/src/lib/math/numbertheory/def_powm.h
@@ -36,6 +36,8 @@ class Fixed_Window_Exponentiator final : public Modular_Exponentiator
       Power_Mod::Usage_Hints m_hints;
    };
 
+class Montgomery_Exponentation_State;
+
 /**
 * Montgomery Exponentiator
 */
@@ -51,12 +53,11 @@ class Montgomery_Exponentiator final : public Modular_Exponentiator
 
       Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
    private:
-      BigInt m_exp, m_modulus, m_R_mod, m_R2_mod;
-      Modular_Reducer m_reducer;
-      word m_mod_prime;
-      size_t m_mod_words, m_exp_bits, m_window_bits;
+      std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
+      BigInt m_p;
+      Modular_Reducer m_mod_p;
+      BigInt m_e;
       Power_Mod::Usage_Hints m_hints;
-      std::vector<BigInt> m_g;
    };
 
 }
diff --git a/src/lib/math/numbertheory/info.txt b/src/lib/math/numbertheory/info.txt
index 0a386b9f3..01adb7345 100644
--- a/src/lib/math/numbertheory/info.txt
+++ b/src/lib/math/numbertheory/info.txt
@@ -12,6 +12,7 @@ reducer.h
 
 <header:internal>
 def_powm.h
+monty_exp.h
 </header:internal>
 
 <requires>
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
new file mode 100644
index 000000000..35f04fc5d
--- /dev/null
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -0,0 +1,153 @@
+/*
+* Montgomery Exponentiation
+* (C) 1999-2010,2012,2018 Jack Lloyd
+*     2016 Matthias Gierlings
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/monty_exp.h>
+#include <botan/numthry.h>
+#include <botan/reducer.h>
+#include <botan/internal/mp_core.h>
+
+namespace Botan {
+
+class Montgomery_Exponentation_State
+   {
+   public:
+      Montgomery_Exponentation_State(const BigInt& g,
+                                     const BigInt& p,
+                                     const Modular_Reducer& mod_p,
+                                     size_t window_bits);
+
+      BigInt exponentiation(const BigInt& k) const;
+   private:
+      BigInt m_p;
+      BigInt m_R_mod;
+      BigInt m_R2_mod;
+      word m_mod_prime;
+      size_t m_p_words;
+      size_t m_window_bits;
+      std::vector<BigInt> m_g;
+   };
+
+Montgomery_Exponentation_State::Montgomery_Exponentation_State(const BigInt& g,
+                                                               const BigInt& p,
+                                                               const Modular_Reducer& mod_p,
+                                                               size_t window_bits) :
+   m_p(p),
+   m_p_words(p.sig_words()),
+   m_window_bits(window_bits)
+   {
+   if(p.is_positive() == false || p.is_even())
+      throw Invalid_Argument("Cannot use Montgomery reduction on even or negative integer");
+
+   if(window_bits > 12) // really even 8 is too large ...
+      throw Invalid_Argument("Montgomery window bits too large");
+
+   m_mod_prime = monty_inverse(m_p.word_at(0));
+
+   const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
+   m_R_mod = mod_p.reduce(r);
+   m_R2_mod = mod_p.square(m_R_mod);
+
+   m_g.resize(1U << m_window_bits);
+
+   BigInt z(BigInt::Positive, 2 * (m_p_words + 1));
+   secure_vector<word> workspace(z.size());
+
+   m_g[0] = 1;
+
+   bigint_monty_mul(z, m_g[0], m_R2_mod,
+                    m_p.data(), m_p_words, m_mod_prime,
+                    workspace.data());
+   m_g[0] = z;
+
+   m_g[1] = mod_p.reduce(g);
+
+   bigint_monty_mul(z, m_g[1], m_R2_mod,
+                    m_p.data(), m_p_words, m_mod_prime,
+                    workspace.data());
+
+   m_g[1] = z;
+
+   const BigInt& x = m_g[1];
+
+   for(size_t i = 2; i != m_g.size(); ++i)
+      {
+      const BigInt& y = m_g[i-1];
+
+      bigint_monty_mul(z, x, y, m_p.data(), m_p_words, m_mod_prime,
+                       workspace.data());
+
+      m_g[i] = z;
+      m_g[i].shrink_to_fit();
+      m_g[i].grow_to(m_p_words);
+      }
+   }
+
+BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& k) const
+   {
+   const size_t exp_nibbles = (k.bits() + m_window_bits - 1) / m_window_bits;
+
+   BigInt x = m_R_mod;
+
+   const size_t z_size = 2*(m_p_words + 1);
+
+   BigInt z(BigInt::Positive, z_size);
+   secure_vector<word> workspace(z.size());
+   secure_vector<word> e(m_p_words);
+
+   for(size_t i = exp_nibbles; i > 0; --i)
+      {
+      for(size_t k = 0; k != m_window_bits; ++k)
+         {
+         bigint_monty_sqr(z, x, m_p.data(), m_p_words, m_mod_prime,
+                          workspace.data());
+
+         x = z;
+         }
+
+      const uint32_t nibble = k.get_substring(m_window_bits*(i-1), m_window_bits);
+
+      BigInt::const_time_lookup(e, m_g, nibble);
+
+      bigint_mul(z.mutable_data(), z.size(),
+                 x.data(), x.size(), x.sig_words(),
+                 e.data(), m_p_words, m_p_words,
+                 workspace.data());
+
+      bigint_monty_redc(z.mutable_data(),
+                        m_p.data(), m_p_words, m_mod_prime,
+                        workspace.data());
+
+      x = z;
+      }
+
+   x.grow_to(2*m_p_words + 1);
+
+   bigint_monty_redc(x.mutable_data(),
+                     m_p.data(), m_p_words, m_mod_prime,
+                     workspace.data());
+
+   return x;
+   }
+
+std::shared_ptr<const Montgomery_Exponentation_State>
+monty_precompute(const BigInt& g,
+                 const BigInt& p,
+                 const Modular_Reducer& mod_p,
+                 size_t window_bits)
+   {
+   return std::make_shared<const Montgomery_Exponentation_State>(g, p, mod_p, window_bits);
+   }
+
+BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
+                     const BigInt& k)
+   {
+   return precomputed_state.exponentiation(k);
+   }
+
+}
+
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
new file mode 100644
index 000000000..65fc9ce4b
--- /dev/null
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -0,0 +1,36 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_MONTY_EXP_H_
+#define BOTAN_MONTY_EXP_H_
+
+#include <memory>
+
+namespace Botan {
+
+class BigInt;
+class Modular_Reducer;
+
+class Montgomery_Exponentation_State;
+
+/*
+* Precompute for calculating values g^x mod p
+*/
+std::shared_ptr<const Montgomery_Exponentation_State>
+monty_precompute(const BigInt& g,
+                 const BigInt& p,
+                 const Modular_Reducer& mod_p,
+                 size_t window_bits);
+
+/*
+* Return g^x mod p
+*/
+BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
+                     const BigInt& k);
+
+}
+
+#endif
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index d3b5805e4..81102188b 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -1,6 +1,6 @@
 /*
 * Montgomery Exponentiation
-* (C) 1999-2010,2012 Jack Lloyd
+* (C) 1999-2010,2012,2018 Jack Lloyd
 *     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -9,131 +9,32 @@
 #include <botan/internal/def_powm.h>
 #include <botan/numthry.h>
 #include <botan/internal/mp_core.h>
+#include <botan/internal/monty_exp.h>
 
 namespace Botan {
 
-/*
-* Set the exponent
-*/
 void Montgomery_Exponentiator::set_exponent(const BigInt& exp)
    {
-   m_exp = exp;
-   m_exp_bits = exp.bits();
+   m_e = exp;
    }
 
-/*
-* Set the base
-*/
 void Montgomery_Exponentiator::set_base(const BigInt& base)
    {
-   m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints);
-
-   m_g.resize(1U << m_window_bits);
-
-   BigInt z(BigInt::Positive, 2 * (m_mod_words + 1));
-   secure_vector<word> workspace(z.size());
-
-   m_g[0] = 1;
-
-   bigint_monty_mul(z, m_g[0], m_R2_mod,
-                    m_modulus.data(), m_mod_words, m_mod_prime,
-                    workspace.data());
-   m_g[0] = z;
-
-   m_g[1] = m_reducer.reduce(base);
-
-   bigint_monty_mul(z, m_g[1], m_R2_mod,
-                    m_modulus.data(), m_mod_words, m_mod_prime,
-                    workspace.data());
-
-   m_g[1] = z;
-
-   const BigInt& x = m_g[1];
-
-   for(size_t i = 2; i != m_g.size(); ++i)
-      {
-      const BigInt& y = m_g[i-1];
-
-      bigint_monty_mul(z, x, y, m_modulus.data(), m_mod_words, m_mod_prime,
-                       workspace.data());
-
-      m_g[i] = z;
-      m_g[i].shrink_to_fit();
-      m_g[i].grow_to(m_mod_words);
-      }
+   size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
+   m_monty = monty_precompute(base, m_p, m_mod_p, window_bits);
    }
 
-/*
-* Compute the result
-*/
 BigInt Montgomery_Exponentiator::execute() const
    {
-   const size_t exp_nibbles = (m_exp_bits + m_window_bits - 1) / m_window_bits;
-
-   BigInt x = m_R_mod;
-
-   const size_t z_size = 2*(m_mod_words + 1);
-
-   BigInt z(BigInt::Positive, z_size);
-   secure_vector<word> workspace(z.size());
-   secure_vector<word> e(m_mod_words);
-
-   for(size_t i = exp_nibbles; i > 0; --i)
-      {
-      for(size_t k = 0; k != m_window_bits; ++k)
-         {
-         bigint_monty_sqr(z, x, m_modulus.data(), m_mod_words, m_mod_prime,
-                          workspace.data());
-
-         x = z;
-         }
-
-      const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
-
-      BigInt::const_time_lookup(e, m_g, nibble);
-
-      bigint_mul(z.mutable_data(), z.size(),
-                 x.data(), x.size(), x.sig_words(),
-                 e.data(), m_mod_words, m_mod_words,
-                 workspace.data());
-
-      bigint_monty_redc(z.mutable_data(),
-                        m_modulus.data(), m_mod_words, m_mod_prime,
-                        workspace.data());
-
-      x = z;
-      }
-
-   x.grow_to(2*m_mod_words + 1);
-
-   bigint_monty_redc(x.mutable_data(),
-                     m_modulus.data(), m_mod_words, m_mod_prime,
-                     workspace.data());
-
-   return x;
+   return monty_execute(*m_monty, m_e);
    }
 
-/*
-* Montgomery_Exponentiator Constructor
-*/
 Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
                                                    Power_Mod::Usage_Hints hints) :
-   m_modulus(mod),
-   m_reducer(m_modulus),
-   m_mod_words(m_modulus.sig_words()),
-   m_window_bits(1),
+   m_p(mod),
+   m_mod_p(mod),
    m_hints(hints)
    {
-   // Montgomery reduction only works for positive odd moduli
-   if(!m_modulus.is_positive() || m_modulus.is_even())
-      throw Invalid_Argument("Montgomery_Exponentiator: invalid modulus");
-
-   m_mod_prime = monty_inverse(mod.word_at(0));
-
-   const BigInt r = BigInt::power_of_2(m_mod_words * BOTAN_MP_WORD_BITS);
-   m_R_mod = m_reducer.reduce(r);
-   m_R2_mod = m_reducer.square(m_R_mod);
-   m_exp_bits = 0;
    }
 
 }