Merge GH #2070 Precompute RSA Montgomery params

2 files changed, 305 insertions, 163 deletions

diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 7fd1b8d2f..5f597b811 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -1,6 +1,6 @@
 /*
 * RSA
-* (C) 1999-2010,2015,2016,2018 Jack Lloyd
+* (C) 1999-2010,2015,2016,2018,2019 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -27,9 +27,117 @@
 
 namespace Botan {
 
+class RSA_Public_Data final
+   {
+   public:
+      RSA_Public_Data(BigInt&& n, BigInt&& e) :
+         m_n(n),
+         m_e(e),
+         m_monty_n(std::make_shared<Montgomery_Params>(m_n)),
+         m_public_modulus_bits(m_n.bits()),
+         m_public_modulus_bytes(m_n.bytes())
+         {}
+
+      BigInt public_op(const BigInt& m) const
+         {
+         const size_t powm_window = 1;
+         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false);
+         return monty_execute_vartime(*powm_m_n, m_e);
+         }
+
+      const BigInt& get_n() const { return m_n; }
+      const BigInt& get_e() const { return m_e; }
+      size_t public_modulus_bits() const { return m_public_modulus_bits; }
+      size_t public_modulus_bytes() const { return m_public_modulus_bytes; }
+
+   private:
+      BigInt m_n;
+      BigInt m_e;
+      std::shared_ptr<const Montgomery_Params> m_monty_n;
+      size_t m_public_modulus_bits;
+      size_t m_public_modulus_bytes;
+   };
+
+class RSA_Private_Data final
+   {
+   public:
+      RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q,
+                       BigInt&& d1, BigInt&& d2, BigInt&& c) :
+         m_d(d),
+         m_p(p),
+         m_q(q),
+         m_d1(d1),
+         m_d2(d2),
+         m_c(c),
+         m_mod_p(m_p),
+         m_mod_q(m_q),
+         m_monty_p(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
+         m_monty_q(std::make_shared<Montgomery_Params>(m_q, m_mod_q)),
+         m_p_bits(m_p.bits()),
+         m_q_bits(m_q.bits())
+         {}
+
+      const BigInt& get_d() const { return m_d; }
+      const BigInt& get_p() const { return m_p; }
+      const BigInt& get_q() const { return m_q; }
+      const BigInt& get_d1() const { return m_d1; }
+      const BigInt& get_d2() const { return m_d2; }
+      const BigInt& get_c() const { return m_c; }
+
+   //private:
+      BigInt m_d;
+      BigInt m_p;
+      BigInt m_q;
+      BigInt m_d1;
+      BigInt m_d2;
+      BigInt m_c;
+
+      Modular_Reducer m_mod_p;
+      Modular_Reducer m_mod_q;
+      std::shared_ptr<const Montgomery_Params> m_monty_p;
+      std::shared_ptr<const Montgomery_Params> m_monty_q;
+      size_t m_p_bits;
+      size_t m_q_bits;
+   };
+
+std::shared_ptr<const RSA_Public_Data> RSA_PublicKey::public_data() const
+   {
+   return m_public;
+   }
+
+const BigInt& RSA_PublicKey::get_n() const { return m_public->get_n(); }
+const BigInt& RSA_PublicKey::get_e() const { return m_public->get_e(); }
+
+void RSA_PublicKey::init(BigInt&& n, BigInt&& e)
+   {
+   if(n.is_negative() || n.is_even() || e.is_negative() || e.is_even())
+      throw Decoding_Error("Invalid RSA public key parameters");
+   m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
+   }
+
+RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier&,
+                             const std::vector<uint8_t>& key_bits)
+   {
+   BigInt n, e;
+   BER_Decoder(key_bits)
+      .start_cons(SEQUENCE)
+      .decode(n)
+      .decode(e)
+      .end_cons();
+
+   init(std::move(n), std::move(e));
+   }
+
+RSA_PublicKey::RSA_PublicKey(const BigInt& modulus, const BigInt& exponent)
+   {
+   BigInt n = modulus;
+   BigInt e = exponent;
+   init(std::move(n), std::move(e));
+   }
+
 size_t RSA_PublicKey::key_length() const
    {
-   return m_n.bits();
+   return m_public->public_modulus_bits();
    }
 
 size_t RSA_PublicKey::estimated_strength() const
@@ -39,8 +147,7 @@ size_t RSA_PublicKey::estimated_strength() const
 
 AlgorithmIdentifier RSA_PublicKey::algorithm_identifier() const
    {
-   return AlgorithmIdentifier(get_oid(),
-                              AlgorithmIdentifier::USE_NULL_PARAM);
+   return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_NULL_PARAM);
    }
 
 std::vector<uint8_t> RSA_PublicKey::public_key_bits() const
@@ -48,85 +155,116 @@ std::vector<uint8_t> RSA_PublicKey::public_key_bits() const
    std::vector<uint8_t> output;
    DER_Encoder der(output);
    der.start_cons(SEQUENCE)
-         .encode(m_n)
-         .encode(m_e)
+         .encode(get_n())
+         .encode(get_e())
       .end_cons();
 
    return output;
    }
 
-RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier&,
-                             const std::vector<uint8_t>& key_bits)
-   {
-   BER_Decoder(key_bits)
-      .start_cons(SEQUENCE)
-        .decode(m_n)
-        .decode(m_e)
-      .end_cons();
-   }
-
 /*
 * Check RSA Public Parameters
 */
 bool RSA_PublicKey::check_key(RandomNumberGenerator&, bool) const
    {
-   if(m_n < 35 || m_n.is_even() || m_e < 3 || m_e.is_even())
+   if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even())
       return false;
    return true;
    }
 
+std::shared_ptr<const RSA_Private_Data> RSA_PrivateKey::private_data() const
+   {
+   return m_private;
+   }
+
 secure_vector<uint8_t> RSA_PrivateKey::private_key_bits() const
    {
    return DER_Encoder()
       .start_cons(SEQUENCE)
          .encode(static_cast<size_t>(0))
-         .encode(m_n)
-         .encode(m_e)
-         .encode(m_d)
-         .encode(m_p)
-         .encode(m_q)
-         .encode(m_d1)
-         .encode(m_d2)
-         .encode(m_c)
+         .encode(get_n())
+         .encode(get_e())
+         .encode(get_d())
+         .encode(get_p())
+         .encode(get_q())
+         .encode(get_d1())
+         .encode(get_d2())
+         .encode(get_c())
       .end_cons()
    .get_contents();
    }
 
+const BigInt& RSA_PrivateKey::get_p() const { return m_private->get_p(); }
+const BigInt& RSA_PrivateKey::get_q() const { return m_private->get_q(); }
+const BigInt& RSA_PrivateKey::get_d() const { return m_private->get_d(); }
+const BigInt& RSA_PrivateKey::get_c() const { return m_private->get_c(); }
+const BigInt& RSA_PrivateKey::get_d1() const { return m_private->get_d1(); }
+const BigInt& RSA_PrivateKey::get_d2() const { return m_private->get_d2(); }
+
+void RSA_PrivateKey::init(BigInt&& d, BigInt&& p, BigInt&& q,
+                          BigInt&& d1, BigInt&& d2, BigInt&& c)
+   {
+   m_private = std::make_shared<RSA_Private_Data>(
+      std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
+   }
+
 RSA_PrivateKey::RSA_PrivateKey(const AlgorithmIdentifier&,
                                const secure_vector<uint8_t>& key_bits)
    {
+   BigInt n, e, d, p, q, d1, d2, c;
+
    BER_Decoder(key_bits)
       .start_cons(SEQUENCE)
          .decode_and_check<size_t>(0, "Unknown PKCS #1 key format version")
-         .decode(m_n)
-         .decode(m_e)
-         .decode(m_d)
-         .decode(m_p)
-         .decode(m_q)
-         .decode(m_d1)
-         .decode(m_d2)
-         .decode(m_c)
+         .decode(n)
+         .decode(e)
+         .decode(d)
+         .decode(p)
+         .decode(q)
+         .decode(d1)
+         .decode(d2)
+         .decode(c)
       .end_cons();
+
+   RSA_PublicKey::init(std::move(n), std::move(e));
+
+   RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
+                        std::move(d1), std::move(d2), std::move(c));
    }
 
 RSA_PrivateKey::RSA_PrivateKey(const BigInt& prime1,
                                const BigInt& prime2,
                                const BigInt& exp,
                                const BigInt& d_exp,
-                               const BigInt& mod) :
-   m_d{ d_exp }, m_p{ prime1 }, m_q{ prime2 }, m_d1{}, m_d2{}, m_c{ inverse_mod( m_q, m_p ) }
+                               const BigInt& mod)
    {
-   m_n = mod.is_nonzero() ? mod : m_p * m_q;
-   m_e = exp;
+   BigInt p = prime1;
+   BigInt q = prime2;
+   BigInt n = mod;
+   if(n.is_zero())
+      n = p * q;
 
-   if(m_d == 0)
+   BigInt e = exp;
+
+   BigInt d = d_exp;
+
+   const BigInt p_minus_1 = p - 1;
+   const BigInt q_minus_1 = q - 1;
+
+   if(d.is_zero())
       {
-      const BigInt phi_n = lcm(m_p - 1, m_q - 1);
-      m_d = inverse_mod(m_e, phi_n);
+      const BigInt phi_n = lcm(p_minus_1, q_minus_1);
+      d = inverse_mod(e, phi_n);
       }
 
-   m_d1 = ct_modulo(m_d, m_p - 1);
-   m_d2 = ct_modulo(m_d, m_q - 1);
+   BigInt d1 = ct_modulo(d, p_minus_1);
+   BigInt d2 = ct_modulo(d, q_minus_1);
+   BigInt c = inverse_mod(q, p);
+
+   RSA_PublicKey::init(std::move(n), std::move(e));
+
+   RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
+                        std::move(d1), std::move(d2), std::move(c));
    }
 
 /*
@@ -141,25 +279,36 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
    if(exp < 3 || exp % 2 == 0)
       throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
 
-   m_e = exp;
+   BigInt n, e, d, p, q, d1, d2, c;
+
+   e = exp;
 
    const size_t p_bits = (bits + 1) / 2;
    const size_t q_bits = bits - p_bits;
 
    do
       {
-      m_p = generate_rsa_prime(rng, rng, p_bits, m_e);
-      m_q = generate_rsa_prime(rng, rng, q_bits, m_e);
-      m_n = m_p * m_q;
-      } while(m_n.bits() != bits);
+      // TODO could generate primes in thread pool
+      p = generate_rsa_prime(rng, rng, p_bits, e);
+      q = generate_rsa_prime(rng, rng, q_bits, e);
+      n = p * q;
+      } while(n.bits() != bits);
+
+   const BigInt p_minus_1 = p - 1;
+   const BigInt q_minus_1 = q - 1;
 
-   // FIXME: lcm calls gcd which is not const time
-   const BigInt phi_n = lcm(m_p - 1, m_q - 1);
+   // FIXME: lcm calls gcd which is not completely const time
+   const BigInt phi_n = lcm(p_minus_1, q_minus_1);
    // FIXME: this uses binary ext gcd because phi_n is even
-   m_d = inverse_mod(m_e, phi_n);
-   m_d1 = ct_modulo(m_d, m_p - 1);
-   m_d2 = ct_modulo(m_d, m_q - 1);
-   m_c = inverse_mod(m_q, m_p);
+   d = inverse_mod(e, phi_n);
+   d1 = ct_modulo(d, p_minus_1);
+   d2 = ct_modulo(d, q_minus_1);
+   c = inverse_mod(q, p); // p odd, so uses const time algorithm
+
+   RSA_PublicKey::init(std::move(n), std::move(e));
+
+   RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
+                        std::move(d1), std::move(d2), std::move(c));
    }
 
 /*
@@ -167,23 +316,32 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
 */
 bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    {
-   if(m_n < 35 || m_n.is_even() || m_e < 3 || m_e.is_even())
+   if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even())
+      return false;
+
+   if(get_d() < 2 || get_p() < 3 || get_q() < 3)
       return false;
 
-   if(m_d < 2 || m_p < 3 || m_q < 3 || m_p*m_q != m_n)
+   if(get_p() * get_q() != get_n())
       return false;
 
-   if(m_d1 != ct_modulo(m_d, m_p - 1) || m_d2 != ct_modulo(m_d, m_q - 1) || m_c != inverse_mod(m_q, m_p))
+   if(get_d1() != ct_modulo(get_d(), get_p() - 1))
+      return false;
+   if(get_d2() != ct_modulo(get_d(), get_q() - 1))
+      return false;
+   if(get_c() != inverse_mod(get_q(), get_p()))
       return false;
 
    const size_t prob = (strong) ? 128 : 12;
 
-   if(!is_prime(m_p, rng, prob) || !is_prime(m_q, rng, prob))
+   if(!is_prime(get_p(), rng, prob))
+      return false;
+   if(!is_prime(get_q(), rng, prob))
       return false;
 
    if(strong)
       {
-      if(ct_modulo(m_e * m_d, lcm(m_p - 1, m_q - 1)) != 1)
+      if(ct_modulo(get_e() * get_d(), lcm(get_p() - 1, get_q() - 1)) != 1)
          return false;
 
       return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)");
@@ -200,54 +358,48 @@ namespace {
 class RSA_Private_Operation
    {
    protected:
-      size_t get_max_input_bits() const { return (m_mod_bits - 1); }
-
-      const size_t exp_blinding_bits = 64;
+      size_t public_modulus_bits() const { return m_public->public_modulus_bits(); }
+      size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); }
 
       explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
-         m_key(rsa),
-         m_mod_p(m_key.get_p()),
-         m_mod_q(m_key.get_q()),
-         m_monty_p(std::make_shared<Montgomery_Params>(m_key.get_p(), m_mod_p)),
-         m_monty_q(std::make_shared<Montgomery_Params>(m_key.get_q(), m_mod_q)),
-         m_monty_n(std::make_shared<Montgomery_Params>(m_key.get_n())),
-         m_blinder(m_key.get_n(),
-                   rng,
-                   [this](const BigInt& k) { return public_op(k); },
-                   [this](const BigInt& k) { return inverse_mod(k, m_key.get_n()); }),
+         m_public(rsa.public_data()),
+         m_private(rsa.private_data()),
+         m_blinder(m_public->get_n(), rng,
+                   [this](const BigInt& k) { return m_public->public_op(k); },
+                   [this](const BigInt& k) { return inverse_mod(k, m_public->get_n()); }),
          m_blinding_bits(64),
-         m_mod_bytes(m_key.get_n().bytes()),
-         m_mod_bits(m_key.get_n().bits()),
-         m_max_d1_bits(m_key.get_p().bits() + m_blinding_bits),
-         m_max_d2_bits(m_key.get_q().bits() + m_blinding_bits)
+         m_max_d1_bits(m_private->m_p_bits + m_blinding_bits),
+         m_max_d2_bits(m_private->m_q_bits + m_blinding_bits)
          {
          }
 
-      BigInt public_op(const BigInt& m) const
+      secure_vector<uint8_t> raw_op(const uint8_t input[], size_t input_len)
          {
-         const size_t powm_window = 1;
-         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false);
-         return monty_execute_vartime(*powm_m_n, m_key.get_e());
-         }
-
-      BigInt blinded_private_op(const BigInt& m) const
-         {
-         if(m >= m_key.get_n())
+         const BigInt input_bn(input, input_len);
+         if(input_bn >= m_public->get_n())
             throw Invalid_Argument("RSA private op - input is too large");
 
-         return m_blinder.unblind(private_op(m_blinder.blind(m)));
+         // TODO: This should be a function on blinder
+         // BigInt Blinder::run_blinded_function(std::function<BigInt, BigInt> fn, const BigInt& input);
+
+         const BigInt recovered = m_blinder.unblind(rsa_private_op(m_blinder.blind(input_bn)));
+         BOTAN_ASSERT(input_bn == m_public->public_op(recovered), "RSA consistency check");
+         return BigInt::encode_1363(recovered, m_public->public_modulus_bytes());
          }
 
-      BigInt private_op(const BigInt& m) const
+   private:
+
+      BigInt rsa_private_op(const BigInt& m) const
          {
          /*
          TODO
-           Consider using Montgomery reduction instead of Barrett, using
-           the "Smooth RSA-CRT" method. https://eprint.iacr.org/2007/039.pdf
+         Consider using Montgomery reduction instead of Barrett, using
+         the "Smooth RSA-CRT" method. https://eprint.iacr.org/2007/039.pdf
          */
 
          const size_t powm_window = 4;
 
+         // Compute this in main thread to avoid racing on the rng
          const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
 
 #if defined(BOTAN_TARGET_OS_HAS_THREADS) && !defined(BOTAN_HAS_VALGRIND)
@@ -264,9 +416,9 @@ class RSA_Private_Operation
 
          auto future_j1 = std::async(std::launch::async, [this, &m, &d1_mask, powm_window]() {
 #endif
-         const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
-         auto powm_d1_p = monty_precompute(m_monty_p, m_mod_p.reduce(m), powm_window);
-         BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
+            const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1));
+            auto powm_d1_p = monty_precompute(m_private->m_monty_p, m_private->m_mod_p.reduce(m), powm_window);
+            BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
 
 #if defined(BOTAN_RSA_USE_ASYNC)
          return j1;
@@ -274,8 +426,8 @@ class RSA_Private_Operation
 #endif
 
          const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
-         const BigInt masked_d2 = m_key.get_d2() + (d2_mask * (m_key.get_q() - 1));
-         auto powm_d2_q = monty_precompute(m_monty_q, m_mod_q.reduce(m), powm_window);
+         const BigInt masked_d2 = m_private->get_d2() + (d2_mask * (m_private->get_q() - 1));
+         auto powm_d2_q = monty_precompute(m_private->m_monty_q, m_private->m_mod_q.reduce(m), powm_window);
          const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
 
 #if defined(BOTAN_RSA_USE_ASYNC)
@@ -295,35 +447,27 @@ class RSA_Private_Operation
          * this may still underflow if p and q are imbalanced in size.
          */
 
-         j1 = m_mod_p.multiply(m_mod_p.reduce((m_key.get_p() + j1) - j2), m_key.get_c());
-         return mul_add(j1, m_key.get_q(), j2);
+         j1 = m_private->m_mod_p.multiply(m_private->m_mod_p.reduce((m_private->get_p() + j1) - j2), m_private->get_c());
+         return mul_add(j1, m_private->get_q(), j2);
          }
 
-      const RSA_PrivateKey& m_key;
-
-      // TODO these could all be computed once and stored in the key object
-      Modular_Reducer m_mod_p;
-      Modular_Reducer m_mod_q;
-      std::shared_ptr<const Montgomery_Params> m_monty_p;
-      std::shared_ptr<const Montgomery_Params> m_monty_q;
-      std::shared_ptr<const Montgomery_Params> m_monty_n;
+      std::shared_ptr<const RSA_Public_Data> m_public;
+      std::shared_ptr<const RSA_Private_Data> m_private;
 
+      // XXX could the blinder starting pair be shared?
       Blinder m_blinder;
       const size_t m_blinding_bits;
-      const size_t m_mod_bytes;
-      const size_t m_mod_bits;
       const size_t m_max_d1_bits;
       const size_t m_max_d2_bits;
    };
 
 class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,
-                                private RSA_Private_Operation
+                                      private RSA_Private_Operation
    {
    public:
+      size_t max_input_bits() const override { return public_modulus_bits() - 1; }
 
-      size_t max_input_bits() const override { return get_max_input_bits(); }
-
-      size_t signature_length() const override { return m_key.get_n().bytes(); }
+      size_t signature_length() const override { return public_modulus_bytes(); }
 
       RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa, RandomNumberGenerator& rng) :
          PK_Ops::Signature_with_EMSA(emsa),
@@ -331,19 +475,15 @@ class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,
          {
          }
 
-      secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
-                                   RandomNumberGenerator&) override
+      secure_vector<uint8_t> raw_sign(const uint8_t input[], size_t input_len,
+                                      RandomNumberGenerator&) override
          {
-         const BigInt m(msg, msg_len);
-         const BigInt x = blinded_private_op(m);
-         const BigInt c = public_op(x);
-         BOTAN_ASSERT(m == c, "RSA sign consistency check");
-         return BigInt::encode_1363(x, m_mod_bytes);
+         return raw_op(input, input_len);
          }
    };
 
 class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME,
-                                 private RSA_Private_Operation
+                                       private RSA_Private_Operation
    {
    public:
 
@@ -353,20 +493,16 @@ class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME,
          {
          }
 
-      size_t plaintext_length(size_t) const override { return m_mod_bytes; }
+      size_t plaintext_length(size_t) const override { return public_modulus_bytes(); }
 
-      secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override
+      secure_vector<uint8_t> raw_decrypt(const uint8_t input[], size_t input_len) override
          {
-         const BigInt m(msg, msg_len);
-         const BigInt x = blinded_private_op(m);
-         const BigInt c = public_op(x);
-         BOTAN_ASSERT(m == c, "RSA decrypt consistency check");
-         return BigInt::encode_1363(x, m_mod_bytes);
+         return raw_op(input, input_len);
          }
    };
 
 class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KDF,
-                                     private RSA_Private_Operation
+                                           private RSA_Private_Operation
    {
    public:
 
@@ -380,11 +516,7 @@ class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KD
       secure_vector<uint8_t>
       raw_kem_decrypt(const uint8_t encap_key[], size_t len) override
          {
-         const BigInt m(encap_key, len);
-         const BigInt x = blinded_private_op(m);
-         const BigInt c = public_op(x);
-         BOTAN_ASSERT(m == c, "RSA KEM consistency check");
-         return BigInt::encode_1363(x, m_mod_bytes);
+         return raw_op(encap_key, len);
          }
    };
 
@@ -395,14 +527,13 @@ class RSA_Public_Operation
    {
    public:
       explicit RSA_Public_Operation(const RSA_PublicKey& rsa) :
-         m_n(rsa.get_n()),
-         m_e(rsa.get_e()),
-         m_monty_n(std::make_shared<Montgomery_Params>(m_n))
+         m_public(rsa.public_data())
          {}
 
-      size_t get_max_input_bits() const
+         size_t get_max_input_bits() const
          {
-         const size_t n_bits = m_n.bits();
+         const size_t n_bits = m_public->public_modulus_bits();
+
          /*
          Make Coverity happy that n_bits - 1 won't underflow
 
@@ -415,20 +546,17 @@ class RSA_Public_Operation
    protected:
       BigInt public_op(const BigInt& m) const
          {
-         if(m >= m_n)
+         if(m >= m_public->get_n())
             throw Invalid_Argument("RSA public op - input is too large");
 
-         const size_t powm_window = 1;
-
-         auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false);
-         return monty_execute_vartime(*powm_m_n, m_e);
+         return m_public->public_op(m);
          }
 
-      const BigInt& get_n() const { return m_n; }
+      size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); }
+
+      const BigInt& get_n() const { return m_public->get_n(); }
 
-      const BigInt& m_n;
-      const BigInt& m_e;
-      std::shared_ptr<Montgomery_Params> m_monty_n;
+      std::shared_ptr<const RSA_Public_Data> m_public;
    };
 
 class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
@@ -442,15 +570,15 @@ class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
          {
          }
 
-      size_t ciphertext_length(size_t) const override { return m_n.bytes(); }
+      size_t ciphertext_length(size_t) const override { return public_modulus_bytes(); }
 
       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,
+      secure_vector<uint8_t> raw_encrypt(const uint8_t input[], size_t input_len,
                                          RandomNumberGenerator&) override
          {
-         BigInt m(msg, msg_len);
-         return BigInt::encode_1363(public_op(m), m_n.bytes());
+         BigInt input_bn(input, input_len);
+         return BigInt::encode_1363(public_op(input_bn), public_modulus_bytes());
          }
    };
 
@@ -469,10 +597,10 @@ class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA,
 
       bool with_recovery() const override { return true; }
 
-      secure_vector<uint8_t> verify_mr(const uint8_t msg[], size_t msg_len) override
+      secure_vector<uint8_t> verify_mr(const uint8_t input[], size_t input_len) override
          {
-         BigInt m(msg, msg_len);
-         return BigInt::encode_locked(public_op(m));
+         BigInt input_bn(input, input_len);
+         return BigInt::encode_locked(public_op(input_bn));
          }
    };
 
diff --git a/src/lib/pubkey/rsa/rsa.h b/src/lib/pubkey/rsa/rsa.h
index 696f01608..2a02c89d5 100644
--- a/src/lib/pubkey/rsa/rsa.h
+++ b/src/lib/pubkey/rsa/rsa.h
@@ -11,10 +11,14 @@
 #include <botan/pk_keys.h>
 #include <botan/bigint.h>
 #include <string>
+#include <memory>
 #include <vector>
 
 namespace Botan {
 
+class RSA_Public_Data;
+class RSA_Private_Data;
+
 /**
 * RSA Public Key
 */
@@ -34,8 +38,7 @@ class BOTAN_PUBLIC_API(2,0) RSA_PublicKey : public virtual Public_Key
       * @arg n the modulus
       * @arg e the exponent
       */
-      RSA_PublicKey(const BigInt& n, const BigInt& e) :
-         m_n(n), m_e(e) {}
+      RSA_PublicKey(const BigInt& n, const BigInt& e);
 
       std::string algo_name() const override { return "RSA"; }
 
@@ -48,16 +51,19 @@ class BOTAN_PUBLIC_API(2,0) RSA_PublicKey : public virtual Public_Key
       /**
       * @return public modulus
       */
-      const BigInt& get_n() const { return m_n; }
+      const BigInt& get_n() const;
 
       /**
       * @return public exponent
       */
-      const BigInt& get_e() const { return m_e; }
+      const BigInt& get_e() const;
 
       size_t key_length() const override;
       size_t estimated_strength() const override;
 
+      // internal functions:
+      std::shared_ptr<const RSA_Public_Data> public_data() const;
+
       std::unique_ptr<PK_Ops::Encryption>
          create_encryption_op(RandomNumberGenerator& rng,
                               const std::string& params,
@@ -75,7 +81,9 @@ class BOTAN_PUBLIC_API(2,0) RSA_PublicKey : public virtual Public_Key
    protected:
       RSA_PublicKey() = default;
 
-      BigInt m_n, m_e;
+      void init(BigInt&& n, BigInt&& e);
+
+      std::shared_ptr<const RSA_Public_Data> m_public;
    };
 
 /**
@@ -122,26 +130,29 @@ class BOTAN_PUBLIC_API(2,0) RSA_PrivateKey final : public Private_Key, public RS
       * Get the first prime p.
       * @return prime p
       */
-      const BigInt& get_p() const { return m_p; }
+      const BigInt& get_p() const;
 
       /**
       * Get the second prime q.
       * @return prime q
       */
-      const BigInt& get_q() const { return m_q; }
+      const BigInt& get_q() const;
 
       /**
       * Get d with exp * d = 1 mod (p - 1, q - 1).
       * @return d
       */
-      const BigInt& get_d() const { return m_d; }
+      const BigInt& get_d() const;
 
-      const BigInt& get_c() const { return m_c; }
-      const BigInt& get_d1() const { return m_d1; }
-      const BigInt& get_d2() const { return m_d2; }
+      const BigInt& get_c() const;
+      const BigInt& get_d1() const;
+      const BigInt& get_d2() const;
 
       secure_vector<uint8_t> private_key_bits() const override;
 
+      // internal functions:
+      std::shared_ptr<const RSA_Private_Data> private_data() const;
+
       std::unique_ptr<PK_Ops::Decryption>
          create_decryption_op(RandomNumberGenerator& rng,
                               const std::string& params,
@@ -158,7 +169,10 @@ class BOTAN_PUBLIC_API(2,0) RSA_PrivateKey final : public Private_Key, public RS
                              const std::string& provider) const override;
 
    private:
-      BigInt m_d, m_p, m_q, m_d1, m_d2, m_c;
+
+      void init(BigInt&& d, BigInt&& p, BigInt&& q, BigInt&& d1, BigInt&& d2, BigInt&& c);
+
+      std::shared_ptr<const RSA_Private_Data> m_private;
    };
 
 }