14 files changed, 232 insertions, 848 deletions

diff --git a/src/lib/pubkey/curve25519/donna.cpp b/src/lib/pubkey/curve25519/donna.cpp
index 9b28e412c..a0e4d249f 100644
--- a/src/lib/pubkey/curve25519/donna.cpp
+++ b/src/lib/pubkey/curve25519/donna.cpp
@@ -39,6 +39,26 @@ typedef byte u8;
 typedef u64bit limb;
 typedef limb felem[5];
 
+typedef struct
+   {
+       limb* x;
+       limb* z;
+   } fmonty_pair_t;
+
+typedef struct
+   {
+     fmonty_pair_t q;
+     fmonty_pair_t q_dash;
+     const limb* q_minus_q_dash;
+   } fmonty_in_t;
+
+typedef struct
+   {
+     fmonty_pair_t two_q;
+     fmonty_pair_t q_plus_q_dash;
+   } fmonty_out_t;
+
+
 #if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
 typedef donna128 uint128_t;
 #endif
@@ -273,44 +293,41 @@ fcontract(u8 *output, const felem input) {
 /* Input: Q, Q', Q-Q'
  * Output: 2Q, Q+Q'
  *
- *   x2 z3: long form
- *   x3 z3: long form
- *   x z: short form, destroyed
- *   xprime zprime: short form, destroyed
- *   qmqp: short form, preserved
+ *   result.two_q (2*Q): long form
+ *   result.q_plus_q_dash (Q + Q): long form
+ *   in.q: short form, destroyed
+ *   in.q_dash: short form, destroyed
+ *   in.q_minus_q_dash: short form, preserved
  */
 static void
-fmonty(limb *x2, limb *z2, /* output 2Q */
-       limb *x3, limb *z3, /* output Q + Q' */
-       limb *x, limb *z,   /* input Q */
-       limb *xprime, limb *zprime, /* input Q' */
-       const limb *qmqp /* input Q - Q' */) {
+fmonty(fmonty_out_t& result, fmonty_in_t& in)
+{
   limb origx[5], origxprime[5], zzz[5], xx[5], zz[5], xxprime[5],
-        zzprime[5], zzzprime[5];
+       zzprime[5], zzzprime[5];
 
-  copy_mem(origx, x, 5);
-  fsum(x, z);
-  fdifference_backwards(z, origx);  // does x - z
+  copy_mem(origx, in.q.x, 5);
+  fsum(in.q.x, in.q.z);
+  fdifference_backwards(in.q.z, origx);  // does x - z
 
-  copy_mem(origxprime, xprime, 5);
-  fsum(xprime, zprime);
-  fdifference_backwards(zprime, origxprime);
-  fmul(xxprime, xprime, z);
-  fmul(zzprime, x, zprime);
+  copy_mem(origxprime, in.q_dash.x, 5);
+  fsum(in.q_dash.x, in.q_dash.z);
+  fdifference_backwards(in.q_dash.z, origxprime);
+  fmul(xxprime, in.q_dash.x, in.q.z);
+  fmul(zzprime, in.q.x, in.q_dash.z);
   copy_mem(origxprime, xxprime, 5);
   fsum(xxprime, zzprime);
   fdifference_backwards(zzprime, origxprime);
-  fsquare_times(x3, xxprime, 1);
+  fsquare_times(result.q_plus_q_dash.x, xxprime, 1);
   fsquare_times(zzzprime, zzprime, 1);
-  fmul(z3, zzzprime, qmqp);
+  fmul(result.q_plus_q_dash.z, zzzprime, in.q_minus_q_dash);
 
-  fsquare_times(xx, x, 1);
-  fsquare_times(zz, z, 1);
-  fmul(x2, xx, zz);
+  fsquare_times(xx, in.q.x, 1);
+  fsquare_times(zz, in.q.z, 1);
+  fmul(result.two_q.x, xx, zz);
   fdifference_backwards(zz, xx);  // does zz = xx - zz
   fscalar_product(zzz, zz, 121665);
   fsum(zzz, xx);
-  fmul(z2, zz, zzz);
+  fmul(result.two_q.z, zz, zzz);
 }
 
 // -----------------------------------------------------------------------------
@@ -356,11 +373,10 @@ cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) {
 
       swap_conditional(nqx, nqpqx, bit);
       swap_conditional(nqz, nqpqz, bit);
-      fmonty(nqx2, nqz2,
-             nqpqx2, nqpqz2,
-             nqx, nqz,
-             nqpqx, nqpqz,
-             q);
+
+      fmonty_out_t result { nqx2, nqz2, nqpqx2, nqpqz2 };
+      fmonty_in_t in { nqx, nqz, nqpqx, nqpqz, q };
+      fmonty(result, in);
       swap_conditional(nqx2, nqpqx2, bit);
       swap_conditional(nqz2, nqpqz2, bit);
 
diff --git a/src/lib/pubkey/if_algo/if_algo.cpp b/src/lib/pubkey/if_algo/if_algo.cpp
deleted file mode 100644
index e5f3ae20f..000000000
--- a/src/lib/pubkey/if_algo/if_algo.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-/*
-* IF Scheme
-* (C) 1999-2007 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/if_algo.h>
-#include <botan/numthry.h>
-#include <botan/workfactor.h>
-#include <botan/der_enc.h>
-#include <botan/ber_dec.h>
-
-namespace Botan {
-
-size_t IF_Scheme_PublicKey::estimated_strength() const
-   {
-   return if_work_factor(m_n.bits());
-   }
-
-AlgorithmIdentifier IF_Scheme_PublicKey::algorithm_identifier() const
-   {
-   return AlgorithmIdentifier(get_oid(),
-                              AlgorithmIdentifier::USE_NULL_PARAM);
-   }
-
-std::vector<byte> IF_Scheme_PublicKey::x509_subject_public_key() const
-   {
-   return DER_Encoder()
-      .start_cons(SEQUENCE)
-         .encode(m_n)
-         .encode(m_e)
-      .end_cons()
-      .get_contents_unlocked();
-   }
-
-IF_Scheme_PublicKey::IF_Scheme_PublicKey(const AlgorithmIdentifier&,
-                                         const secure_vector<byte>& key_bits)
-   {
-   BER_Decoder(key_bits)
-      .start_cons(SEQUENCE)
-        .decode(m_n)
-        .decode(m_e)
-      .verify_end()
-      .end_cons();
-   }
-
-/*
-* Check IF Scheme Public Parameters
-*/
-bool IF_Scheme_PublicKey::check_key(RandomNumberGenerator&, bool) const
-   {
-   if(m_n < 35 || m_n.is_even() || m_e < 2)
-      return false;
-   return true;
-   }
-
-secure_vector<byte> IF_Scheme_PrivateKey::pkcs8_private_key() 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)
-      .end_cons()
-   .get_contents();
-   }
-
-IF_Scheme_PrivateKey::IF_Scheme_PrivateKey(RandomNumberGenerator& rng,
-                                           const AlgorithmIdentifier&,
-                                           const secure_vector<byte>& key_bits)
-   {
-   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)
-      .end_cons();
-
-   load_check(rng);
-   }
-
-IF_Scheme_PrivateKey::IF_Scheme_PrivateKey(RandomNumberGenerator& rng,
-                                           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 ) }
-   {
-   m_n = mod.is_nonzero() ? mod : m_p * m_q;
-   m_e = exp;
-
-   if(m_d == 0)
-      {
-      BigInt inv_for_d = lcm(m_p - 1, m_q - 1);
-      if(m_e.is_even())
-         inv_for_d >>= 1;
-
-      m_d = inverse_mod(m_e, inv_for_d);
-      }
-
-   m_d1 = m_d % (m_p - 1);
-   m_d2 = m_d % (m_q - 1);
-
-   load_check(rng);
-   }
-
-/*
-* Check IF Scheme Private Parameters
-*/
-bool IF_Scheme_PrivateKey::check_key(RandomNumberGenerator& rng,
-                                     bool strong) const
-   {
-   if(m_n < 35 || m_n.is_even() || m_e < 2 || m_d < 2 || m_p < 3 || m_q < 3 || m_p*m_q != m_n)
-      return false;
-
-   if(m_d1 != m_d % (m_p - 1) || m_d2 != m_d % (m_q - 1) || m_c != inverse_mod(m_q, m_p))
-      return false;
-
-   const size_t prob = (strong) ? 56 : 12;
-
-   if(!is_prime(m_p, rng, prob) || !is_prime(m_q, rng, prob))
-      return false;
-   return true;
-   }
-
-}
diff --git a/src/lib/pubkey/if_algo/if_algo.h b/src/lib/pubkey/if_algo/if_algo.h
deleted file mode 100644
index 46dbd51a9..000000000
--- a/src/lib/pubkey/if_algo/if_algo.h
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
-* IF Scheme
-* (C) 1999-2007 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_IF_ALGO_H__
-#define BOTAN_IF_ALGO_H__
-
-#include <botan/bigint.h>
-#include <botan/x509_key.h>
-
-namespace Botan {
-
-/**
-* This class represents public keys
-* of integer factorization based (IF) public key schemes.
-*/
-class BOTAN_DLL IF_Scheme_PublicKey : public virtual Public_Key
-   {
-   public:
-      IF_Scheme_PublicKey(const AlgorithmIdentifier& alg_id,
-                          const secure_vector<byte>& key_bits);
-
-      IF_Scheme_PublicKey(const BigInt& n, const BigInt& e) :
-         m_n(n), m_e(e) {}
-
-      bool check_key(RandomNumberGenerator& rng, bool) const override;
-
-      AlgorithmIdentifier algorithm_identifier() const override;
-
-      std::vector<byte> x509_subject_public_key() const override;
-
-      /**
-      * @return public modulus
-      */
-      const BigInt& get_n() const { return m_n; }
-
-      /**
-      * @return public exponent
-      */
-      const BigInt& get_e() const { return m_e; }
-
-      size_t max_input_bits() const override { return (m_n.bits() - 1); }
-
-      size_t estimated_strength() const override;
-
-   protected:
-      IF_Scheme_PublicKey() {}
-
-      BigInt m_n, m_e;
-   };
-
-/**
-* This class represents public keys
-* of integer factorization based (IF) public key schemes.
-*/
-class BOTAN_DLL IF_Scheme_PrivateKey : public virtual IF_Scheme_PublicKey,
-                                       public virtual Private_Key
-   {
-   public:
-
-      IF_Scheme_PrivateKey(RandomNumberGenerator& rng,
-                           const BigInt& prime1, const BigInt& prime2,
-                           const BigInt& exp, const BigInt& d_exp,
-                           const BigInt& mod);
-
-      IF_Scheme_PrivateKey(RandomNumberGenerator& rng,
-                           const AlgorithmIdentifier& alg_id,
-                           const secure_vector<byte>& key_bits);
-
-      bool check_key(RandomNumberGenerator& rng, bool) const override;
-
-      /**
-      * Get the first prime p.
-      * @return prime p
-      */
-      const BigInt& get_p() const { return m_p; }
-
-      /**
-      * Get the second prime q.
-      * @return prime q
-      */
-      const BigInt& get_q() const { return m_q; }
-
-      /**
-      * Get d with exp * d = 1 mod (p - 1, q - 1).
-      * @return d
-      */
-      const BigInt& get_d() const { return m_d; }
-
-      const BigInt& get_c() const { return m_c; }
-      const BigInt& get_d1() const { return m_d1; }
-      const BigInt& get_d2() const { return m_d2; }
-
-      secure_vector<byte> pkcs8_private_key() const override;
-
-   protected:
-      IF_Scheme_PrivateKey() {}
-
-      BigInt m_d, m_p, m_q, m_d1, m_d2, m_c;
-   };
-
-}
-
-#endif
diff --git a/src/lib/pubkey/if_algo/info.txt b/src/lib/pubkey/if_algo/info.txt
deleted file mode 100644
index 5ceec0a89..000000000
--- a/src/lib/pubkey/if_algo/info.txt
+++ /dev/null
@@ -1,9 +0,0 @@
-define IF_PUBLIC_KEY_FAMILY 20131128
-
-load_on dep
-
-<requires>
-asn1
-bigint
-numbertheory
-</requires>
diff --git a/src/lib/pubkey/nr/info.txt b/src/lib/pubkey/nr/info.txt
deleted file mode 100644
index 78ca6ef29..000000000
--- a/src/lib/pubkey/nr/info.txt
+++ /dev/null
@@ -1,8 +0,0 @@
-define NYBERG_RUEPPEL 20131128
-
-<requires>
-dl_algo
-dl_group
-keypair
-numbertheory
-</requires>
diff --git a/src/lib/pubkey/nr/nr.cpp b/src/lib/pubkey/nr/nr.cpp
deleted file mode 100644
index 5e2cb1be5..000000000
--- a/src/lib/pubkey/nr/nr.cpp
+++ /dev/null
@@ -1,192 +0,0 @@
-/*
-* Nyberg-Rueppel
-* (C) 1999-2010 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/internal/pk_utils.h>
-#include <botan/nr.h>
-#include <botan/keypair.h>
-#include <botan/reducer.h>
-#include <future>
-
-namespace Botan {
-
-NR_PublicKey::NR_PublicKey(const AlgorithmIdentifier& alg_id,
-                           const secure_vector<byte>& key_bits) :
-   DL_Scheme_PublicKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
-   {
-   }
-
-/*
-* NR_PublicKey Constructor
-*/
-NR_PublicKey::NR_PublicKey(const DL_Group& grp, const BigInt& y1)
-   {
-   m_group = grp;
-   m_y = y1;
-   }
-
-/*
-* Create a NR private key
-*/
-NR_PrivateKey::NR_PrivateKey(RandomNumberGenerator& rng,
-                             const DL_Group& grp,
-                             const BigInt& x_arg)
-   {
-   m_group = grp;
-   m_x = x_arg;
-
-   if(m_x == 0)
-      m_x = BigInt::random_integer(rng, 2, group_q() - 1);
-
-   m_y = power_mod(group_g(), m_x, group_p());
-
-   if(x_arg == 0)
-      gen_check(rng);
-   else
-      load_check(rng);
-   }
-
-NR_PrivateKey::NR_PrivateKey(const AlgorithmIdentifier& alg_id,
-                             const secure_vector<byte>& key_bits,
-                             RandomNumberGenerator& rng) :
-   DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
-   {
-   m_y = power_mod(group_g(), m_x, group_p());
-
-   load_check(rng);
-   }
-
-/*
-* Check Private Nyberg-Rueppel Parameters
-*/
-bool NR_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
-   {
-   if(!DL_Scheme_PrivateKey::check_key(rng, strong) || m_x >= group_q())
-      return false;
-
-   if(!strong)
-      return true;
-
-   return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
-   }
-
-namespace {
-
-/**
-* Nyberg-Rueppel signature operation
-*/
-class NR_Signature_Operation : public PK_Ops::Signature_with_EMSA
-   {
-   public:
-      typedef NR_PrivateKey Key_Type;
-      NR_Signature_Operation(const NR_PrivateKey& nr, const std::string& emsa) :
-         PK_Ops::Signature_with_EMSA(emsa),
-         m_q(nr.group_q()),
-         m_x(nr.get_x()),
-         m_powermod_g_p(nr.group_g(), nr.group_p()),
-         m_mod_q(nr.group_q())
-         {
-         }
-
-      size_t message_parts() const override { return 2; }
-      size_t message_part_size() const override { return m_q.bytes(); }
-      size_t max_input_bits() const override { return (m_q.bits() - 1); }
-
-      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
-                                   RandomNumberGenerator& rng) override;
-   private:
-      const BigInt& m_q;
-      const BigInt& m_x;
-      Fixed_Base_Power_Mod m_powermod_g_p;
-      Modular_Reducer m_mod_q;
-   };
-
-secure_vector<byte>
-NR_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
-                                 RandomNumberGenerator& rng)
-   {
-   rng.add_entropy(msg, msg_len);
-
-   BigInt f(msg, msg_len);
-
-   if(f >= m_q)
-      throw Invalid_Argument("NR_Signature_Operation: Input is out of range");
-
-   BigInt c, d;
-
-   while(c == 0)
-      {
-      BigInt k;
-      do
-         k.randomize(rng, m_q.bits());
-      while(k >= m_q);
-
-      c = m_mod_q.reduce(m_powermod_g_p(k) + f);
-      d = m_mod_q.reduce(k - m_x * c);
-      }
-
-   secure_vector<byte> output(2*m_q.bytes());
-   c.binary_encode(&output[output.size() / 2 - c.bytes()]);
-   d.binary_encode(&output[output.size() - d.bytes()]);
-   return output;
-   }
-
-
-/**
-* Nyberg-Rueppel verification operation
-*/
-class NR_Verification_Operation : public PK_Ops::Verification_with_EMSA
-   {
-   public:
-      typedef NR_PublicKey Key_Type;
-      NR_Verification_Operation(const NR_PublicKey& nr, const std::string& emsa) :
-         PK_Ops::Verification_with_EMSA(emsa),
-         m_q(nr.group_q()), m_y(nr.get_y()), m_powermod_g_p{Fixed_Base_Power_Mod(nr.group_g(), nr.group_p())},
-         m_powermod_y_p{Fixed_Base_Power_Mod(m_y, nr.group_p())}, m_mod_p{Modular_Reducer(nr.group_p())},
-         m_mod_q{Modular_Reducer(nr.group_q())}
-         {}
-
-      size_t message_parts() const override { return 2; }
-      size_t message_part_size() const override { return m_q.bytes(); }
-      size_t max_input_bits() const override { return (m_q.bits() - 1); }
-
-      bool with_recovery() const override { return true; }
-
-      secure_vector<byte> verify_mr(const byte msg[], size_t msg_len) override;
-   private:
-      const BigInt& m_q;
-      const BigInt& m_y;
-
-      Fixed_Base_Power_Mod m_powermod_g_p, m_powermod_y_p;
-      Modular_Reducer m_mod_p, m_mod_q;
-   };
-
-secure_vector<byte>
-NR_Verification_Operation::verify_mr(const byte msg[], size_t msg_len)
-   {
-   const BigInt& q = m_mod_q.get_modulus();
-
-   if(msg_len != 2*q.bytes())
-      throw Invalid_Argument("NR verification: Invalid signature");
-
-   BigInt c(msg, q.bytes());
-   BigInt d(msg + q.bytes(), q.bytes());
-
-   if(c.is_zero() || c >= q || d >= q)
-      throw Invalid_Argument("NR verification: Invalid signature");
-
-   auto future_y_c = std::async(std::launch::async, m_powermod_y_p, c);
-   BigInt g_d = m_powermod_g_p(d);
-
-   BigInt i = m_mod_p.multiply(g_d, future_y_c.get());
-   return BigInt::encode_locked(m_mod_q.reduce(c - i));
-   }
-}
-
-BOTAN_REGISTER_PK_SIGNATURE_OP("NR", NR_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("NR", NR_Verification_Operation);
-
-}
diff --git a/src/lib/pubkey/nr/nr.h b/src/lib/pubkey/nr/nr.h
deleted file mode 100644
index 425ad2642..000000000
--- a/src/lib/pubkey/nr/nr.h
+++ /dev/null
@@ -1,57 +0,0 @@
-/*
-* Nyberg-Rueppel
-* (C) 1999-2010 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_NYBERG_RUEPPEL_H__
-#define BOTAN_NYBERG_RUEPPEL_H__
-
-#include <botan/dl_algo.h>
-
-namespace Botan {
-
-/**
-* Nyberg-Rueppel Public Key
-*/
-class BOTAN_DLL NR_PublicKey : public virtual DL_Scheme_PublicKey
-   {
-   public:
-      std::string algo_name() const override { return "NR"; }
-
-      DL_Group::Format group_format() const override { return DL_Group::ANSI_X9_57; }
-
-      size_t message_parts() const override { return 2; }
-      size_t message_part_size() const override { return group_q().bytes(); }
-      size_t max_input_bits() const override { return (group_q().bits() - 1); }
-
-      NR_PublicKey(const AlgorithmIdentifier& alg_id,
-                   const secure_vector<byte>& key_bits);
-
-      NR_PublicKey(const DL_Group& group, const BigInt& pub_key);
-   protected:
-      NR_PublicKey() {}
-   };
-
-/**
-* Nyberg-Rueppel Private Key
-*/
-class BOTAN_DLL NR_PrivateKey : public NR_PublicKey,
-                                public virtual DL_Scheme_PrivateKey
-   {
-   public:
-      bool check_key(RandomNumberGenerator& rng, bool strong) const override;
-
-      NR_PrivateKey(const AlgorithmIdentifier& alg_id,
-                    const secure_vector<byte>& key_bits,
-                    RandomNumberGenerator& rng);
-
-      NR_PrivateKey(RandomNumberGenerator& rng,
-                    const DL_Group& group,
-                    const BigInt& x = 0);
-   };
-
-}
-
-#endif
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index 9dbde28af..ac6f4a11f 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -36,14 +36,6 @@
   #include <botan/gost_3410.h>
 #endif
 
-#if defined(BOTAN_HAS_NYBERG_RUEPPEL)
-  #include <botan/nr.h>
-#endif
-
-#if defined(BOTAN_HAS_RW)
-  #include <botan/rw.h>
-#endif
-
 #if defined(BOTAN_HAS_ELGAMAL)
   #include <botan/elgamal.h>
 #endif
@@ -74,11 +66,6 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
       return new RSA_PublicKey(alg_id, key_bits);
 #endif
 
-#if defined(BOTAN_HAS_RW)
-   if(alg_name == "RW")
-      return new RW_PublicKey(alg_id, key_bits);
-#endif
-
 #if defined(BOTAN_HAS_DSA)
    if(alg_name == "DSA")
       return new DSA_PublicKey(alg_id, key_bits);
@@ -89,11 +76,6 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
       return new DH_PublicKey(alg_id, key_bits);
 #endif
 
-#if defined(BOTAN_HAS_NYBERG_RUEPPEL)
-   if(alg_name == "NR")
-      return new NR_PublicKey(alg_id, key_bits);
-#endif
-
 #if defined(BOTAN_HAS_ELGAMAL)
    if(alg_name == "ElGamal")
       return new ElGamal_PublicKey(alg_id, key_bits);
@@ -150,11 +132,6 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id,
       return new RSA_PrivateKey(alg_id, key_bits, rng);
 #endif
 
-#if defined(BOTAN_HAS_RW)
-   if(alg_name == "RW")
-      return new RW_PrivateKey(alg_id, key_bits, rng);
-#endif
-
 #if defined(BOTAN_HAS_DSA)
    if(alg_name == "DSA")
       return new DSA_PrivateKey(alg_id, key_bits, rng);
@@ -165,11 +142,6 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id,
       return new DH_PrivateKey(alg_id, key_bits, rng);
 #endif
 
-#if defined(BOTAN_HAS_NYBERG_RUEPPEL)
-   if(alg_name == "NR")
-      return new NR_PrivateKey(alg_id, key_bits, rng);
-#endif
-
 #if defined(BOTAN_HAS_ELGAMAL)
    if(alg_name == "ElGamal")
       return new ElGamal_PrivateKey(alg_id, key_bits, rng);
diff --git a/src/lib/pubkey/rsa/info.txt b/src/lib/pubkey/rsa/info.txt
index 91eec565a..6df380696 100644
--- a/src/lib/pubkey/rsa/info.txt
+++ b/src/lib/pubkey/rsa/info.txt
@@ -1,7 +1,6 @@
-define RSA 20131128
+define RSA 20160730
 
 <requires>
-if_algo
 keypair
 numbertheory
 emsa_pssr
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 6a645ec88..7f72ba210 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -1,6 +1,6 @@
 /*
 * RSA
-* (C) 1999-2010,2015 Jack Lloyd
+* (C) 1999-2010,2015,2016 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -11,10 +11,118 @@
 #include <botan/keypair.h>
 #include <botan/blinding.h>
 #include <botan/reducer.h>
+#include <botan/workfactor.h>
+#include <botan/der_enc.h>
+#include <botan/ber_dec.h>
 #include <future>
 
 namespace Botan {
 
+size_t RSA_PublicKey::estimated_strength() const
+   {
+   return if_work_factor(m_n.bits());
+   }
+
+AlgorithmIdentifier RSA_PublicKey::algorithm_identifier() const
+   {
+   return AlgorithmIdentifier(get_oid(),
+                              AlgorithmIdentifier::USE_NULL_PARAM);
+   }
+
+std::vector<byte> RSA_PublicKey::x509_subject_public_key() const
+   {
+   return DER_Encoder()
+      .start_cons(SEQUENCE)
+         .encode(m_n)
+         .encode(m_e)
+      .end_cons()
+      .get_contents_unlocked();
+   }
+
+RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier&,
+                                         const secure_vector<byte>& key_bits)
+   {
+   BER_Decoder(key_bits)
+      .start_cons(SEQUENCE)
+        .decode(m_n)
+        .decode(m_e)
+      .verify_end()
+      .end_cons();
+   }
+
+/*
+* Check RSA Public Parameters
+*/
+bool RSA_PublicKey::check_key(RandomNumberGenerator&, bool) const
+   {
+   if(m_n < 35 || m_n.is_even() || m_e < 2)
+      return false;
+   return true;
+   }
+
+secure_vector<byte> RSA_PrivateKey::pkcs8_private_key() 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)
+      .end_cons()
+   .get_contents();
+   }
+
+RSA_PrivateKey::RSA_PrivateKey(const AlgorithmIdentifier&,
+                               const secure_vector<byte>& key_bits,
+                               RandomNumberGenerator& rng)
+   {
+   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)
+      .end_cons();
+
+   load_check(rng);
+   }
+
+RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
+                               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 ) }
+   {
+   m_n = mod.is_nonzero() ? mod : m_p * m_q;
+   m_e = exp;
+
+   if(m_d == 0)
+      {
+      BigInt inv_for_d = lcm(m_p - 1, m_q - 1);
+      if(m_e.is_even())
+         inv_for_d >>= 1;
+
+      m_d = inverse_mod(m_e, inv_for_d);
+      }
+
+   m_d1 = m_d % (m_p - 1);
+   m_d2 = m_d % (m_q - 1);
+
+   load_check(rng);
+   }
+
 /*
 * Create a RSA private key
 */
@@ -49,16 +157,26 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
 */
 bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    {
-   if(!IF_Scheme_PrivateKey::check_key(rng, strong))
+   if(m_n < 35 || m_n.is_even() || m_e < 2 || m_d < 2 || m_p < 3 || m_q < 3 || m_p*m_q != m_n)
       return false;
 
-   if(!strong)
-      return true;
+   if(m_d1 != m_d % (m_p - 1) || m_d2 != m_d % (m_q - 1) || m_c != inverse_mod(m_q, m_p))
+      return false;
+
+   const size_t prob = (strong) ? 56 : 12;
 
-   if((m_e * m_d) % lcm(m_p - 1, m_q - 1) != 1)
+   if(!is_prime(m_p, rng, prob) || !is_prime(m_q, rng, prob))
       return false;
 
-   return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)");
+   if(strong)
+      {
+      if((m_e * m_d) % lcm(m_p - 1, m_q - 1) != 1)
+         return false;
+
+      return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)");
+      }
+
+   return true;
    }
 
 namespace {
diff --git a/src/lib/pubkey/rsa/rsa.h b/src/lib/pubkey/rsa/rsa.h
index 4a57b9f63..85bd7ce58 100644
--- a/src/lib/pubkey/rsa/rsa.h
+++ b/src/lib/pubkey/rsa/rsa.h
@@ -1,6 +1,6 @@
 /*
 * RSA
-* (C) 1999-2008 Jack Lloyd
+* (C) 1999-2008,2016 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -8,23 +8,19 @@
 #ifndef BOTAN_RSA_H__
 #define BOTAN_RSA_H__
 
-#include <botan/if_algo.h>
-
+#include <botan/bigint.h>
+#include <botan/x509_key.h>
 
 namespace Botan {
 
 /**
 * RSA Public Key
 */
-class BOTAN_DLL RSA_PublicKey : public virtual IF_Scheme_PublicKey
+class BOTAN_DLL RSA_PublicKey : public virtual Public_Key
    {
    public:
-      std::string algo_name() const override { return "RSA"; }
-
       RSA_PublicKey(const AlgorithmIdentifier& alg_id,
-                    const secure_vector<byte>& key_bits) :
-         IF_Scheme_PublicKey(alg_id, key_bits)
-         {}
+                    const secure_vector<byte>& key_bits);
 
       /**
       * Create a RSA_PublicKey
@@ -32,26 +28,45 @@ class BOTAN_DLL RSA_PublicKey : public virtual IF_Scheme_PublicKey
       * @arg e the exponent
       */
       RSA_PublicKey(const BigInt& n, const BigInt& e) :
-         IF_Scheme_PublicKey(n, e)
-         {}
+         m_n(n), m_e(e) {}
+
+      std::string algo_name() const override { return "RSA"; }
+
+      bool check_key(RandomNumberGenerator& rng, bool) const override;
+
+      AlgorithmIdentifier algorithm_identifier() const override;
+
+      std::vector<byte> x509_subject_public_key() const override;
+
+      /**
+      * @return public modulus
+      */
+      const BigInt& get_n() const { return m_n; }
+
+      /**
+      * @return public exponent
+      */
+      const BigInt& get_e() const { return m_e; }
+
+      size_t max_input_bits() const override { return (m_n.bits() - 1); }
+
+      size_t estimated_strength() const override;
 
    protected:
       RSA_PublicKey() {}
+
+      BigInt m_n, m_e;
    };
 
 /**
 * RSA Private Key
 */
-class BOTAN_DLL RSA_PrivateKey : public RSA_PublicKey,
-                                 public IF_Scheme_PrivateKey
+class BOTAN_DLL RSA_PrivateKey : public Private_Key, public RSA_PublicKey
    {
    public:
-      bool check_key(RandomNumberGenerator& rng, bool) const override;
-
       RSA_PrivateKey(const AlgorithmIdentifier& alg_id,
                      const secure_vector<byte>& key_bits,
-                     RandomNumberGenerator& rng) :
-         IF_Scheme_PrivateKey(rng, alg_id, key_bits) {}
+                     RandomNumberGenerator& rng);
 
       /**
       * Construct a private key from the specified parameters.
@@ -68,8 +83,7 @@ class BOTAN_DLL RSA_PrivateKey : public RSA_PublicKey,
       RSA_PrivateKey(RandomNumberGenerator& rng,
                      const BigInt& p, const BigInt& q,
                      const BigInt& e, const BigInt& d = 0,
-                     const BigInt& n = 0) :
-         IF_Scheme_PrivateKey(rng, p, q, e, d, n) {}
+                     const BigInt& n = 0);
 
       /**
       * Create a new private key with the specified bit length
@@ -79,6 +93,34 @@ class BOTAN_DLL RSA_PrivateKey : public RSA_PublicKey,
       */
       RSA_PrivateKey(RandomNumberGenerator& rng,
                      size_t bits, size_t exp = 65537);
+
+      bool check_key(RandomNumberGenerator& rng, bool) const override;
+
+      /**
+      * Get the first prime p.
+      * @return prime p
+      */
+      const BigInt& get_p() const { return m_p; }
+
+      /**
+      * Get the second prime q.
+      * @return prime q
+      */
+      const BigInt& get_q() const { return m_q; }
+
+      /**
+      * Get d with exp * d = 1 mod (p - 1, q - 1).
+      * @return d
+      */
+      const BigInt& get_d() const { return m_d; }
+
+      const BigInt& get_c() const { return m_c; }
+      const BigInt& get_d1() const { return m_d1; }
+      const BigInt& get_d2() const { return m_d2; }
+
+      secure_vector<byte> pkcs8_private_key() const override;
+   private:
+      BigInt m_d, m_p, m_q, m_d1, m_d2, m_c;
    };
 
 }
diff --git a/src/lib/pubkey/rw/info.txt b/src/lib/pubkey/rw/info.txt
deleted file mode 100644
index 7cf1d1780..000000000
--- a/src/lib/pubkey/rw/info.txt
+++ /dev/null
@@ -1,7 +0,0 @@
-define RW 20131128
-
-<requires>
-if_algo
-keypair
-numbertheory
-</requires>
diff --git a/src/lib/pubkey/rw/rw.cpp b/src/lib/pubkey/rw/rw.cpp
deleted file mode 100644
index bf6b647a1..000000000
--- a/src/lib/pubkey/rw/rw.cpp
+++ /dev/null
@@ -1,182 +0,0 @@
-/*
-* Rabin-Williams
-* (C) 1999-2008 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/internal/pk_utils.h>
-#include <botan/rw.h>
-#include <botan/keypair.h>
-#include <botan/parsing.h>
-#include <botan/reducer.h>
-#include <botan/blinding.h>
-#include <algorithm>
-#include <future>
-
-namespace Botan {
-
-/*
-* Create a Rabin-Williams private key
-*/
-RW_PrivateKey::RW_PrivateKey(RandomNumberGenerator& rng,
-                             size_t bits, size_t exp)
-   {
-   if(bits < 1024)
-      throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
-                             std::to_string(bits) + " bits long");
-   if(exp < 2 || exp % 2 == 1)
-      throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
-
-   m_e = exp;
-
-   do
-      {
-      m_p = random_prime(rng, (bits + 1) / 2, m_e / 2, 3, 4);
-      m_q = random_prime(rng, bits - m_p.bits(), m_e / 2, ((m_p % 8 == 3) ? 7 : 3), 8);
-      m_n = m_p * m_q;
-      } while(m_n.bits() != bits);
-
-   m_d = inverse_mod(m_e, lcm(m_p - 1, m_q - 1) >> 1);
-   m_d1 = m_d % (m_p - 1);
-   m_d2 = m_d % (m_q - 1);
-   m_c = inverse_mod(m_q, m_p);
-
-   gen_check(rng);
-   }
-
-/*
-* Check Private Rabin-Williams Parameters
-*/
-bool RW_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
-   {
-   if(!IF_Scheme_PrivateKey::check_key(rng, strong))
-      return false;
-
-   if(!strong)
-      return true;
-
-   if((m_e * m_d) % (lcm(m_p - 1, m_q - 1) / 2) != 1)
-      return false;
-
-   return KeyPair::signature_consistency_check(rng, *this, "EMSA2(SHA-1)");
-   }
-
-namespace {
-
-/**
-* Rabin-Williams Signature Operation
-*/
-class RW_Signature_Operation : public PK_Ops::Signature_with_EMSA
-   {
-   public:
-      typedef RW_PrivateKey Key_Type;
-
-      RW_Signature_Operation(const RW_PrivateKey& rw,
-                             const std::string& emsa) :
-         PK_Ops::Signature_with_EMSA(emsa),
-         m_n(rw.get_n()),
-         m_e(rw.get_e()),
-         m_q(rw.get_q()),
-         m_c(rw.get_c()),
-         m_powermod_d1_p(rw.get_d1(), rw.get_p()),
-         m_powermod_d2_q(rw.get_d2(), rw.get_q()),
-         m_mod_p(rw.get_p()),
-         m_blinder(m_n,
-                 [this](const BigInt& k) { return power_mod(k, m_e, m_n); },
-                 [this](const BigInt& k) { return inverse_mod(k, m_n); })
-         {
-         }
-
-      size_t max_input_bits() const override { return (m_n.bits() - 1); }
-
-      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
-                                   RandomNumberGenerator& rng) override;
-   private:
-      const BigInt& m_n;
-      const BigInt& m_e;
-      const BigInt& m_q;
-      const BigInt& m_c;
-
-      Fixed_Exponent_Power_Mod m_powermod_d1_p, m_powermod_d2_q;
-      Modular_Reducer m_mod_p;
-      Blinder m_blinder;
-   };
-
-secure_vector<byte>
-RW_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
-                                 RandomNumberGenerator&)
-   {
-   BigInt i(msg, msg_len);
-
-   if(i >= m_n || i % 16 != 12)
-      throw Invalid_Argument("Rabin-Williams: invalid input");
-
-   if(jacobi(i, m_n) != 1)
-      i >>= 1;
-
-   i = m_blinder.blind(i);
-
-   auto future_j1 = std::async(std::launch::async, m_powermod_d1_p, i);
-   const BigInt j2 = m_powermod_d2_q(i);
-   BigInt j1 = future_j1.get();
-
-   j1 = m_mod_p.reduce(sub_mul(j1, j2, m_c));
-
-   const BigInt r = m_blinder.unblind(mul_add(j1, m_q, j2));
-
-   return BigInt::encode_1363(std::min(r, m_n - r), m_n.bytes());
-   }
-
-/**
-* Rabin-Williams Verification Operation
-*/
-class RW_Verification_Operation : public PK_Ops::Verification_with_EMSA
-   {
-   public:
-      typedef RW_PublicKey Key_Type;
-
-      RW_Verification_Operation(const RW_PublicKey& rw, const std::string& emsa) :
-         PK_Ops::Verification_with_EMSA(emsa),
-         m_n(rw.get_n()), m_powermod_e_n(rw.get_e(), rw.get_n())
-         {}
-
-      size_t max_input_bits() const override { return (m_n.bits() - 1); }
-      bool with_recovery() const override { return true; }
-
-      secure_vector<byte> verify_mr(const byte msg[], size_t msg_len) override;
-
-   private:
-      const BigInt& m_n;
-      Fixed_Exponent_Power_Mod m_powermod_e_n;
-   };
-
-secure_vector<byte>
-RW_Verification_Operation::verify_mr(const byte msg[], size_t msg_len)
-   {
-   BigInt m(msg, msg_len);
-
-   if((m > (m_n >> 1)) || m.is_negative())
-      throw Invalid_Argument("RW signature verification: m > n / 2 || m < 0");
-
-   BigInt r = m_powermod_e_n(m);
-   if(r % 16 == 12)
-      return BigInt::encode_locked(r);
-   if(r % 8 == 6)
-      return BigInt::encode_locked(2*r);
-
-   r = m_n - r;
-   if(r % 16 == 12)
-      return BigInt::encode_locked(r);
-   if(r % 8 == 6)
-      return BigInt::encode_locked(2*r);
-
-   throw Invalid_Argument("RW signature verification: Invalid signature");
-   }
-
-BOTAN_REGISTER_PK_SIGNATURE_OP("RW", RW_Signature_Operation);
-BOTAN_REGISTER_PK_VERIFY_OP("RW", RW_Verification_Operation);
-
-}
-
-}
diff --git a/src/lib/pubkey/rw/rw.h b/src/lib/pubkey/rw/rw.h
deleted file mode 100644
index 2a010441e..000000000
--- a/src/lib/pubkey/rw/rw.h
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
-* Rabin-Williams
-* (C) 1999-2007 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_RW_H__
-#define BOTAN_RW_H__
-
-#include <botan/if_algo.h>
-
-namespace Botan {
-
-/**
-* Rabin-Williams Public Key
-*/
-class BOTAN_DLL RW_PublicKey : public virtual IF_Scheme_PublicKey
-   {
-   public:
-      std::string algo_name() const override { return "RW"; }
-
-      RW_PublicKey(const AlgorithmIdentifier& alg_id,
-                   const secure_vector<byte>& key_bits) :
-         IF_Scheme_PublicKey(alg_id, key_bits)
-         {}
-
-      RW_PublicKey(const BigInt& mod, const BigInt& exponent) :
-         IF_Scheme_PublicKey(mod, exponent)
-         {}
-
-   protected:
-      RW_PublicKey() {}
-   };
-
-/**
-* Rabin-Williams Private Key
-*/
-class BOTAN_DLL RW_PrivateKey : public RW_PublicKey,
-                                public IF_Scheme_PrivateKey
-   {
-   public:
-      RW_PrivateKey(const AlgorithmIdentifier& alg_id,
-                    const secure_vector<byte>& key_bits,
-                    RandomNumberGenerator& rng) :
-         IF_Scheme_PrivateKey(rng, alg_id, key_bits) {}
-
-      RW_PrivateKey(RandomNumberGenerator& rng,
-                    const BigInt& p, const BigInt& q,
-                    const BigInt& e, const BigInt& d = 0,
-                    const BigInt& n = 0) :
-         IF_Scheme_PrivateKey(rng, p, q, e, d, n) {}
-
-      RW_PrivateKey(RandomNumberGenerator& rng, size_t bits, size_t = 2);
-
-      bool check_key(RandomNumberGenerator& rng, bool) const override;
-   };
-
-}
-
-#endif