Merge GH #2080 Remove use of pow_mod.h interfaces from within library

12 files changed, 202 insertions, 251 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index f198c3e63..0d5bb34cd 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -91,7 +91,6 @@
 
 #if defined(BOTAN_HAS_NUMBERTHEORY)
    #include <botan/numthry.h>
-   #include <botan/pow_mod.h>
    #include <botan/reducer.h>
    #include <botan/curve_nistp.h>
    #include <botan/internal/primality.h>
@@ -1528,9 +1527,6 @@ class Speed final : public Command
             std::unique_ptr<Timer> invmod_timer = make_timer("binext-" + bit_str);
             std::unique_ptr<Timer> monty_timer = make_timer("monty-" + bit_str);
             std::unique_ptr<Timer> ct_invmod_timer = make_timer("ct-" + bit_str);
-            std::unique_ptr<Timer> powm_timer = make_timer("powm-" + bit_str);
-
-            Botan::Fixed_Exponent_Power_Mod powm_p(p - 2, p);
 
             while(invmod_timer->under(runtime))
                {
@@ -1545,18 +1541,13 @@ class Speed final : public Command
                const Botan::BigInt x_inv3 = ct_invmod_timer->run(
                   [&] { return Botan::ct_inverse_mod_odd_modulus(x, p); });
 
-               const Botan::BigInt x_inv4 = powm_timer->run(
-                  [&] { return powm_p(x); });
-
                BOTAN_ASSERT_EQUAL(x_inv1, x_inv2, "Same result");
                BOTAN_ASSERT_EQUAL(x_inv1, x_inv3, "Same result");
-               BOTAN_ASSERT_EQUAL(x_inv1, x_inv4, "Same result");
                }
 
             record_result(invmod_timer);
             record_result(monty_timer);
             record_result(ct_invmod_timer);
-            record_result(powm_timer);
             }
          }
 
diff --git a/src/fuzzer/pow_mod.cpp b/src/fuzzer/pow_mod.cpp
index 0151609fd..28350480c 100644
--- a/src/fuzzer/pow_mod.cpp
+++ b/src/fuzzer/pow_mod.cpp
@@ -7,7 +7,6 @@
 #include "fuzzers.h"
 #include <botan/numthry.h>
 #include <botan/reducer.h>
-#include <botan/pow_mod.h>
 
 namespace {
 
diff --git a/src/lib/math/numbertheory/def_powm.h b/src/lib/math/numbertheory/def_powm.h
deleted file mode 100644
index 6b1f33835..000000000
--- a/src/lib/math/numbertheory/def_powm.h
+++ /dev/null
@@ -1,68 +0,0 @@
-/*
-* Modular Exponentiation
-* (C) 1999-2007 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_DEFAULT_MODEXP_H_
-#define BOTAN_DEFAULT_MODEXP_H_
-
-#include <botan/pow_mod.h>
-#include <botan/reducer.h>
-#include <vector>
-
-namespace Botan {
-
-/**
-* Fixed Window Exponentiator
-*/
-class Fixed_Window_Exponentiator final : public Modular_Exponentiator
-   {
-   public:
-      void set_exponent(const BigInt&) override;
-      void set_base(const BigInt&) override;
-      BigInt execute() const override;
-
-      Modular_Exponentiator* copy() const override
-         { return new Fixed_Window_Exponentiator(*this); }
-
-      Fixed_Window_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
-   private:
-      Modular_Reducer m_reducer;
-      BigInt m_exp;
-      size_t m_window_bits;
-      std::vector<BigInt> m_g;
-      Power_Mod::Usage_Hints m_hints;
-   };
-
-class Montgomery_Params;
-class Montgomery_Exponentation_State;
-
-/**
-* Montgomery Exponentiator
-*/
-class Montgomery_Exponentiator final : public Modular_Exponentiator
-   {
-   public:
-      void set_exponent(const BigInt&) override;
-      void set_base(const BigInt&) override;
-      BigInt execute() const override;
-
-      Modular_Exponentiator* copy() const override
-         { return new Montgomery_Exponentiator(*this); }
-
-      Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
-   private:
-      BigInt m_p;
-      Modular_Reducer m_mod_p;
-      std::shared_ptr<const Montgomery_Params> m_monty_params;
-      std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
-
-      BigInt m_e;
-      Power_Mod::Usage_Hints m_hints;
-   };
-
-}
-
-#endif
diff --git a/src/lib/math/numbertheory/info.txt b/src/lib/math/numbertheory/info.txt
index 0ebd1e05f..4b241c120 100644
--- a/src/lib/math/numbertheory/info.txt
+++ b/src/lib/math/numbertheory/info.txt
@@ -12,7 +12,6 @@ monty.h
 
 <header:internal>
 primality.h
-def_powm.h
 monty_exp.h
 </header:internal>
 
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 7af1d13df..a69028189 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -1,12 +1,11 @@
 /*
 * Number Theory Functions
-* (C) 1999-2011,2016,2018 Jack Lloyd
+* (C) 1999-2011,2016,2018,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/numthry.h>
-#include <botan/pow_mod.h>
 #include <botan/reducer.h>
 #include <botan/monty.h>
 #include <botan/divide.h>
@@ -427,29 +426,34 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
       return 0;
       }
 
-   Power_Mod pow_mod(mod);
+   Modular_Reducer reduce_mod(mod);
 
-   /*
-   * Calling set_base before set_exponent means we end up using a
-   * minimal window. This makes sense given that here we know that any
-   * precomputation is wasted.
-   */
+   const size_t exp_bits = exp.bits();
 
-   if(base.is_negative())
+   if(mod.is_odd())
       {
-      pow_mod.set_base(-base);
-      pow_mod.set_exponent(exp);
-      if(exp.is_even())
-         return pow_mod.execute();
-      else
-         return (mod - pow_mod.execute());
+      const size_t powm_window = 4;
+
+      auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod);
+      auto powm_base_mod = monty_precompute(monty_mod, reduce_mod.reduce(base), powm_window);
+      return monty_execute(*powm_base_mod, exp, exp_bits);
       }
-   else
+
+   /*
+   Support for even modulus is just a convenience and not considered
+   cryptographically important, so this implementation is slow ...
+   */
+   BigInt accum = 1;
+   BigInt g = reduce_mod.reduce(base);
+   BigInt t;
+
+   for(size_t i = 0; i != exp_bits; ++i)
       {
-      pow_mod.set_base(base);
-      pow_mod.set_exponent(exp);
-      return pow_mod.execute();
+      t = reduce_mod.multiply(g, accum);
+      g = reduce_mod.square(g);
+      accum.ct_cond_assign(exp.get_bit(i), t);
       }
+   return accum;
    }
 
 
diff --git a/src/lib/math/numbertheory/pow_mod.cpp b/src/lib/math/numbertheory/pow_mod.cpp
index 02434fe68..7b38fad1d 100644
--- a/src/lib/math/numbertheory/pow_mod.cpp
+++ b/src/lib/math/numbertheory/pow_mod.cpp
@@ -1,15 +1,145 @@
 /*
 * Modular Exponentiation Proxy
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2012,2018,2019 Jack Lloyd
+*     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/pow_mod.h>
-#include <botan/internal/def_powm.h>
+#include <botan/numthry.h>
+#include <botan/reducer.h>
+#include <botan/monty.h>
+#include <botan/internal/monty_exp.h>
+#include <botan/internal/rounding.h>
+#include <vector>
 
 namespace Botan {
 
+class Modular_Exponentiator
+   {
+   public:
+      virtual void set_base(const BigInt&) = 0;
+      virtual void set_exponent(const BigInt&) = 0;
+      virtual BigInt execute() const = 0;
+      virtual Modular_Exponentiator* copy() const = 0;
+
+      Modular_Exponentiator() = default;
+      Modular_Exponentiator(const Modular_Exponentiator&) = default;
+      Modular_Exponentiator & operator=(const Modular_Exponentiator&) = default;
+      virtual ~Modular_Exponentiator() = default;
+   };
+
+namespace {
+
+/**
+* Fixed Window Exponentiator
+*/
+class Fixed_Window_Exponentiator final : public Modular_Exponentiator
+   {
+   public:
+      void set_exponent(const BigInt& e) override { m_exp = e; }
+      void set_base(const BigInt&) override;
+      BigInt execute() const override;
+
+      Modular_Exponentiator* copy() const override
+         { return new Fixed_Window_Exponentiator(*this); }
+
+      Fixed_Window_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
+   private:
+      Modular_Reducer m_reducer;
+      BigInt m_exp;
+      size_t m_window_bits;
+      std::vector<BigInt> m_g;
+      Power_Mod::Usage_Hints m_hints;
+   };
+
+void Fixed_Window_Exponentiator::set_base(const BigInt& base)
+   {
+   m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints);
+
+   m_g.resize(static_cast<size_t>(1) << m_window_bits);
+   m_g[0] = 1;
+   m_g[1] = m_reducer.reduce(base);
+
+   for(size_t i = 2; i != m_g.size(); ++i)
+      m_g[i] = m_reducer.multiply(m_g[i-1], m_g[1]);
+   }
+
+BigInt Fixed_Window_Exponentiator::execute() const
+   {
+   const size_t exp_nibbles = (m_exp.bits() + m_window_bits - 1) / m_window_bits;
+
+   BigInt x = 1;
+
+   for(size_t i = exp_nibbles; i > 0; --i)
+      {
+      for(size_t j = 0; j != m_window_bits; ++j)
+         x = m_reducer.square(x);
+
+      const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
+
+      // not const time:
+      x = m_reducer.multiply(x, m_g[nibble]);
+      }
+   return x;
+   }
+
+/*
+* Fixed_Window_Exponentiator Constructor
+*/
+Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n,
+                                                       Power_Mod::Usage_Hints hints)
+   : m_reducer{Modular_Reducer(n)}, m_exp{}, m_window_bits{}, m_g{}, m_hints{hints}
+   {}
+
+class Montgomery_Exponentiator final : public Modular_Exponentiator
+   {
+   public:
+      void set_exponent(const BigInt& e) override { m_e = e; }
+      void set_base(const BigInt&) override;
+      BigInt execute() const override;
+
+      Modular_Exponentiator* copy() const override
+         { return new Montgomery_Exponentiator(*this); }
+
+      Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
+   private:
+      BigInt m_p;
+      Modular_Reducer m_mod_p;
+      std::shared_ptr<const Montgomery_Params> m_monty_params;
+      std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
+
+      BigInt m_e;
+      Power_Mod::Usage_Hints m_hints;
+   };
+
+void Montgomery_Exponentiator::set_base(const BigInt& base)
+   {
+   size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
+   m_monty = monty_precompute(m_monty_params, m_mod_p.reduce(base), window_bits);
+   }
+
+BigInt Montgomery_Exponentiator::execute() const
+   {
+   /*
+   This leaks size of e via loop iterations, not possible to fix without
+   breaking this API. Round up to avoid leaking fine details.
+   */
+   return monty_execute(*m_monty, m_e, round_up(m_e.bits(), 8));
+   }
+
+Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
+                                                   Power_Mod::Usage_Hints hints) :
+   m_p(mod),
+   m_mod_p(mod),
+   m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
+   m_hints(hints)
+   {
+   }
+
+}
+
 /*
 * Power_Mod Constructor
 */
@@ -18,6 +148,8 @@ Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints, bool disable_monty)
    set_modulus(n, hints, disable_monty);
    }
 
+Power_Mod::~Power_Mod() { /* for ~unique_ptr */ }
+
 /*
 * Power_Mod Copy Constructor
 */
diff --git a/src/lib/math/numbertheory/pow_mod.h b/src/lib/math/numbertheory/pow_mod.h
index 077f4ccf7..d179d8c85 100644
--- a/src/lib/math/numbertheory/pow_mod.h
+++ b/src/lib/math/numbertheory/pow_mod.h
@@ -12,22 +12,7 @@
 
 namespace Botan {
 
-/**
-* Modular Exponentiator Interface
-*/
-class BOTAN_PUBLIC_API(2,0) Modular_Exponentiator
-   {
-   public:
-      virtual void set_base(const BigInt&) = 0;
-      virtual void set_exponent(const BigInt&) = 0;
-      virtual BigInt execute() const = 0;
-      virtual Modular_Exponentiator* copy() const = 0;
-
-      Modular_Exponentiator() = default;
-      Modular_Exponentiator(const Modular_Exponentiator&) = default;
-      Modular_Exponentiator & operator=(const Modular_Exponentiator&) = default;
-      virtual ~Modular_Exponentiator() = default;
-   };
+class Modular_Exponentiator;
 
 /**
 * Modular Exponentiator Proxy
@@ -93,7 +78,7 @@ class BOTAN_PUBLIC_API(2,0) Power_Mod
                 Usage_Hints hints = NO_HINTS,
                 bool disable_montgomery_arith = false);
       Power_Mod(const Power_Mod&);
-      virtual ~Power_Mod() = default;
+      virtual ~Power_Mod();
    private:
       mutable std::unique_ptr<Modular_Exponentiator> m_core;
    };
diff --git a/src/lib/math/numbertheory/powm_fw.cpp b/src/lib/math/numbertheory/powm_fw.cpp
deleted file mode 100644
index c6ff169a1..000000000
--- a/src/lib/math/numbertheory/powm_fw.cpp
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
-* Fixed Window Exponentiation
-* (C) 1999-2007 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/internal/def_powm.h>
-#include <vector>
-
-namespace Botan {
-
-/*
-* Set the exponent
-*/
-void Fixed_Window_Exponentiator::set_exponent(const BigInt& e)
-   {
-   m_exp = e;
-   }
-
-/*
-* Set the base
-*/
-void Fixed_Window_Exponentiator::set_base(const BigInt& base)
-   {
-   m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints);
-
-   m_g.resize(static_cast<size_t>(1) << m_window_bits);
-   m_g[0] = 1;
-   m_g[1] = m_reducer.reduce(base);
-
-   for(size_t i = 2; i != m_g.size(); ++i)
-      m_g[i] = m_reducer.multiply(m_g[i-1], m_g[1]);
-   }
-
-/*
-* Compute the result
-*/
-BigInt Fixed_Window_Exponentiator::execute() const
-   {
-   const size_t exp_nibbles = (m_exp.bits() + m_window_bits - 1) / m_window_bits;
-
-   BigInt x = 1;
-
-   for(size_t i = exp_nibbles; i > 0; --i)
-      {
-      for(size_t j = 0; j != m_window_bits; ++j)
-         x = m_reducer.square(x);
-
-      const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
-
-      x = m_reducer.multiply(x, m_g[nibble]);
-      }
-   return x;
-   }
-
-/*
-* Fixed_Window_Exponentiator Constructor
-*/
-Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n,
-                                                       Power_Mod::Usage_Hints hints)
-      : m_reducer{Modular_Reducer(n)}, m_exp{}, m_window_bits{}, m_g{}, m_hints{hints}
-   {}
-
-}
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
deleted file mode 100644
index 99fbe9814..000000000
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ /dev/null
@@ -1,46 +0,0 @@
-/*
-* 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/def_powm.h>
-#include <botan/numthry.h>
-#include <botan/monty.h>
-#include <botan/internal/monty_exp.h>
-#include <botan/internal/rounding.h>
-
-namespace Botan {
-
-void Montgomery_Exponentiator::set_exponent(const BigInt& exp)
-   {
-   m_e = exp;
-   }
-
-void Montgomery_Exponentiator::set_base(const BigInt& base)
-   {
-   size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
-   m_monty = monty_precompute(m_monty_params, m_mod_p.reduce(base), window_bits);
-   }
-
-BigInt Montgomery_Exponentiator::execute() const
-   {
-   /*
-   This leaks size of e via loop iterations, not possible to fix without
-   breaking this API. Round up to avoid leaking fine details.
-   */
-   return monty_execute(*m_monty, m_e, round_up(m_e.bits(), 8));
-   }
-
-Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
-                                                   Power_Mod::Usage_Hints hints) :
-   m_p(mod),
-   m_mod_p(mod),
-   m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
-   m_hints(hints)
-   {
-   }
-
-}
diff --git a/src/lib/prov/pkcs11/p11_rsa.cpp b/src/lib/prov/pkcs11/p11_rsa.cpp
index 08f4115d1..1a760e1b2 100644
--- a/src/lib/prov/pkcs11/p11_rsa.cpp
+++ b/src/lib/prov/pkcs11/p11_rsa.cpp
@@ -15,7 +15,6 @@
 #include <botan/pk_ops.h>
 #include <botan/rng.h>
 #include <botan/blinding.h>
-#include <botan/pow_mod.h>
 
 namespace Botan {
 
@@ -124,9 +123,8 @@ class PKCS11_RSA_Decryption_Operation final : public PK_Ops::Decryption
                                       RandomNumberGenerator& rng)
          : m_key(key),
            m_mechanism(MechanismWrapper::create_rsa_crypt_mechanism(padding)),
-           m_powermod(m_key.get_e(), m_key.get_n()),
            m_blinder(m_key.get_n(), rng,
-                     [ this ](const BigInt& k) { return m_powermod(k); },
+                     [ this ](const BigInt& k) { return power_mod(k, m_key.get_e(), m_key.get_n()); },
                      [ this ](const BigInt& k) { return inverse_mod(k, m_key.get_n()); })
          {
          m_bits = m_key.get_n().bits() - 1;
@@ -164,7 +162,6 @@ class PKCS11_RSA_Decryption_Operation final : public PK_Ops::Decryption
       const PKCS11_RSA_PrivateKey& m_key;
       MechanismWrapper m_mechanism;
       size_t m_bits = 0;
-      Fixed_Exponent_Power_Mod m_powermod;
       Blinder m_blinder;
    };
 
diff --git a/src/lib/pubkey/dh/dh.cpp b/src/lib/pubkey/dh/dh.cpp
index 75b0db2f6..687032a69 100644
--- a/src/lib/pubkey/dh/dh.cpp
+++ b/src/lib/pubkey/dh/dh.cpp
@@ -1,13 +1,13 @@
 /*
 * Diffie-Hellman
-* (C) 1999-2007,2016 Jack Lloyd
+* (C) 1999-2007,2016,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/dh.h>
 #include <botan/internal/pk_ops_impl.h>
-#include <botan/pow_mod.h>
+#include <botan/internal/monty_exp.h>
 #include <botan/blinding.h>
 
 namespace Botan {
@@ -86,20 +86,30 @@ class DH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
       DH_KA_Operation(const DH_PrivateKey& key, const std::string& kdf, RandomNumberGenerator& rng) :
          PK_Ops::Key_Agreement_with_KDF(kdf),
          m_p(key.group_p()),
-         m_powermod_x_p(key.get_x(), m_p),
+         m_x(key.get_x()),
+         m_x_bits(m_x.bits()),
+         m_monty_p(key.get_group().monty_params_p()),
          m_blinder(m_p,
                    rng,
                    [](const BigInt& k) { return k; },
-                   [this](const BigInt& k) { return m_powermod_x_p(inverse_mod(k, m_p)); })
+                   [this](const BigInt& k) { return powermod_x_p(inverse_mod(k, m_p)); })
          {}
 
       size_t agreed_value_size() const override { return m_p.bytes(); }
 
       secure_vector<uint8_t> raw_agree(const uint8_t w[], size_t w_len) override;
    private:
-      const BigInt& m_p;
+      BigInt powermod_x_p(const BigInt& v) const
+         {
+         const size_t powm_window = 4;
+         auto powm_v_p = monty_precompute(m_monty_p, v, powm_window);
+         return monty_execute(*powm_v_p, m_x, m_x_bits);
+         }
 
-      Fixed_Exponent_Power_Mod m_powermod_x_p;
+      const BigInt& m_p;
+      const BigInt& m_x;
+      const size_t m_x_bits;
+      std::shared_ptr<const Montgomery_Params> m_monty_p;
       Blinder m_blinder;
    };
 
@@ -111,7 +121,7 @@ secure_vector<uint8_t> DH_KA_Operation::raw_agree(const uint8_t w[], size_t w_le
       throw Invalid_Argument("DH agreement - invalid key provided");
 
    v = m_blinder.blind(v);
-   v = m_powermod_x_p(v);
+   v = powermod_x_p(v);
    v = m_blinder.unblind(v);
 
    return BigInt::encode_1363(v, m_p.bytes());
diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp
index 6c2d6bccc..508ed1e8a 100644
--- a/src/lib/pubkey/elgamal/elgamal.cpp
+++ b/src/lib/pubkey/elgamal/elgamal.cpp
@@ -1,16 +1,15 @@
 /*
 * ElGamal
-* (C) 1999-2007,2018 Jack Lloyd
+* (C) 1999-2007,2018,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/elgamal.h>
 #include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/monty_exp.h>
 #include <botan/keypair.h>
-#include <botan/reducer.h>
 #include <botan/blinding.h>
-#include <botan/pow_mod.h>
 
 namespace Botan {
 
@@ -63,7 +62,7 @@ bool ElGamal_PrivateKey::check_key(RandomNumberGenerator& rng,
    if(!strong)
       return true;
 
-   return KeyPair::encryption_consistency_check(rng, *this, "EME1(SHA-256)");
+   return KeyPair::encryption_consistency_check(rng, *this, "OAEP(SHA-256)");
    }
 
 namespace {
@@ -86,15 +85,18 @@ class ElGamal_Encryption_Operation final : public PK_Ops::Encryption_with_EME
 
    private:
       const DL_Group m_group;
-      Fixed_Base_Power_Mod m_powermod_y_p;
+      std::shared_ptr<const Montgomery_Exponentation_State> m_monty_y_p;
    };
 
 ElGamal_Encryption_Operation::ElGamal_Encryption_Operation(const ElGamal_PublicKey& key,
                                                            const std::string& eme) :
    PK_Ops::Encryption_with_EME(eme),
-   m_group(key.get_group()),
-   m_powermod_y_p(key.get_y(), m_group.get_p())
+   m_group(key.get_group())
    {
+   const size_t powm_window = 4;
+   m_monty_y_p = monty_precompute(key.get_group().monty_params_p(),
+                                  key.get_y(),
+                                  powm_window);
    }
 
 secure_vector<uint8_t>
@@ -110,7 +112,7 @@ ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[], size_t msg_len,
    const BigInt k(rng, k_bits);
 
    const BigInt a = m_group.power_g_p(k, k_bits);
-   const BigInt b = m_group.multiply_mod_p(m, m_powermod_y_p(k));
+   const BigInt b = m_group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits));
 
    return BigInt::encode_fixed_length_int_pair(a, b, m_group.p_bytes());
    }
@@ -130,8 +132,17 @@ class ElGamal_Decryption_Operation final : public PK_Ops::Decryption_with_EME
 
       secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override;
    private:
+      BigInt powermod_x_p(const BigInt& v) const
+         {
+         const size_t powm_window = 4;
+         auto powm_v_p = monty_precompute(m_monty_p, v, powm_window);
+         return monty_execute(*powm_v_p, m_x, m_x_bits);
+         }
+
       const DL_Group m_group;
-      Fixed_Exponent_Power_Mod m_powermod_x_p;
+      const BigInt& m_x;
+      const size_t m_x_bits;
+      std::shared_ptr<const Montgomery_Params> m_monty_p;
       Blinder m_blinder;
    };
 
@@ -140,11 +151,13 @@ ElGamal_Decryption_Operation::ElGamal_Decryption_Operation(const ElGamal_Private
                                                            RandomNumberGenerator& rng) :
    PK_Ops::Decryption_with_EME(eme),
    m_group(key.get_group()),
-   m_powermod_x_p(key.get_x(), m_group.get_p()),
+   m_x(key.get_x()),
+   m_x_bits(m_x.bits()),
+   m_monty_p(key.get_group().monty_params_p()),
    m_blinder(m_group.get_p(),
              rng,
              [](const BigInt& k) { return k; },
-             [this](const BigInt& k) { return m_powermod_x_p(k); })
+             [this](const BigInt& k) { return powermod_x_p(k); })
    {
    }
 
@@ -164,7 +177,7 @@ ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len)
 
    a = m_blinder.blind(a);
 
-   const BigInt r = m_group.multiply_mod_p(m_group.inverse_mod_p(m_powermod_x_p(a)), b);
+   const BigInt r = m_group.multiply_mod_p(m_group.inverse_mod_p(powermod_x_p(a)), b);
 
    return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
    }