Add generalized KEM interface

Convert McEliece KEM to use it

Add RSA-KEM

17 files changed, 494 insertions, 116 deletions

diff --git a/doc/news.rst b/doc/news.rst
index 3e7d59c96..e340033c4 100644
--- a/doc/news.rst
+++ b/doc/news.rst
@@ -26,6 +26,14 @@ Version 1.11.26, Not Yet Released
   random number generation, RSA key generation, and signing are
   supported. Tested using Trousers and an ST TPM
 
+* Add generalized interface for KEM (key encapsulation) techniques. Convert
+  McEliece KEM to use it. The previous interfaces McEliece_KEM_Encryptor and
+  McEliece_KEM_Decryptor have been removed. The new KEM interface now uses a KDF
+  to hash the resulting keys; to get the same output as previously provided by
+  McEliece_KEM_Encryptor, use "KDF1(SHA-512)" and request exactly 64 bytes.
+
+* Add support for RSA-KEM from ISO 18033-2
+
 * Avoid calling memcpy, memset, or memmove with a length of zero to
   avoid undefined behavior, as calling these functions with an invalid
   or null pointer, even with a length of zero, is invalid. Often there
diff --git a/src/lib/pubkey/mce/info.txt b/src/lib/pubkey/mce/info.txt
index 1e9b848dd..bb0f06764 100644
--- a/src/lib/pubkey/mce/info.txt
+++ b/src/lib/pubkey/mce/info.txt
@@ -1,7 +1,6 @@
 define MCELIECE 20150922
 
 <header:public>
-mce_kem.h
 mceliece.h
 polyn_gf2m.h
 gf2m_small_m.h
diff --git a/src/lib/pubkey/mce/mce_kem.cpp b/src/lib/pubkey/mce/mce_kem.cpp
index dede67731..b2cefaab2 100644
--- a/src/lib/pubkey/mce/mce_kem.cpp
+++ b/src/lib/pubkey/mce/mce_kem.cpp
@@ -1,51 +1,74 @@
 /**
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#include <botan/mce_kem.h>
+* (C) 2014 cryptosource GmbH
+* (C) 2014 Falko Strenzke [email protected]
+* (C) 2015 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*
+*/
+
 #include <botan/internal/mce_internal.h>
-#include <botan/sha2_64.h>
+#include <botan/internal/pk_ops_impl.h>
+#include <botan/internal/pk_utils.h>
 
 namespace Botan {
 
-McEliece_KEM_Encryptor::McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key) :
-   m_key(public_key)
+class MCE_KEM_Encryptor : public PK_Ops::KEM_Encryption_with_KDF
    {
-   }
+   public:
+      typedef McEliece_PublicKey Key_Type;
 
-std::pair<secure_vector<byte>, secure_vector<byte>>
-McEliece_KEM_Encryptor::encrypt(RandomNumberGenerator& rng)
-   {
-   const secure_vector<byte> plaintext = m_key.random_plaintext_element(rng);
+      MCE_KEM_Encryptor(const McEliece_PublicKey& key,
+                        const std::string& kdf) :
+         KEM_Encryption_with_KDF(kdf), m_key(key) {}
+
+   private:
+      void raw_kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                           secure_vector<byte>& raw_shared_key,
+                           Botan::RandomNumberGenerator& rng) override
+         {
+         secure_vector<byte> plaintext = m_key.random_plaintext_element(rng);
 
-   secure_vector<byte> ciphertext, error_mask;
-   mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
+         secure_vector<byte> ciphertext, error_mask;
+         mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
 
-   SHA_512 hash;
-   hash.update(plaintext);
-   hash.update(error_mask);
-   secure_vector<byte> sym_key = hash.final();
+         raw_shared_key.clear();
+         raw_shared_key += plaintext;
+         raw_shared_key += error_mask;
 
-   return std::make_pair(ciphertext, sym_key);
-   }
+         out_encapsulated_key.swap(ciphertext);
+         }
 
-McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& key) : m_key(key) { }
+      const McEliece_PublicKey& m_key;
+   };
 
-secure_vector<Botan::byte> McEliece_KEM_Decryptor::decrypt(const byte msg[], size_t msg_len)
+class MCE_KEM_Decryptor : public PK_Ops::KEM_Decryption_with_KDF
    {
-   secure_vector<byte> plaintext, error_mask;
-   mceliece_decrypt(plaintext, error_mask, msg, msg_len, m_key);
+   public:
+      typedef McEliece_PrivateKey Key_Type;
+
+      MCE_KEM_Decryptor(const McEliece_PrivateKey& key,
+                        const std::string& kdf) :
+         KEM_Decryption_with_KDF(kdf), m_key(key) {}
+
+   private:
+      secure_vector<byte>
+      raw_kem_decrypt(const byte encap_key[], size_t len) override
+         {
+         secure_vector<byte> plaintext, error_mask;
+         mceliece_decrypt(plaintext, error_mask, encap_key, len, m_key);
+
+         secure_vector<byte> output;
+         output.reserve(plaintext.size() + error_mask.size());
+         output.insert(output.end(), plaintext.begin(), plaintext.end());
+         output.insert(output.end(), error_mask.begin(), error_mask.end());
+         return output;
+         }
 
-   SHA_512 hash;
-   hash.update(plaintext);
-   hash.update(error_mask);
+      const McEliece_PrivateKey& m_key;
+   };
 
-   secure_vector<byte> sym_key = hash.final();
-   return sym_key;
-   }
+BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP("McEliece", MCE_KEM_Encryptor);
+BOTAN_REGISTER_PK_KEM_DECRYPTION_OP("McEliece", MCE_KEM_Decryptor);
 
 }
diff --git a/src/lib/pubkey/mce/mce_kem.h b/src/lib/pubkey/mce/mce_kem.h
deleted file mode 100644
index cd899d568..000000000
--- a/src/lib/pubkey/mce/mce_kem.h
+++ /dev/null
@@ -1,55 +0,0 @@
-/**
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#ifndef BOTAN_MCE_KEM_H__
-#define BOTAN_MCE_KEM_H__
-
-#include <botan/mceliece.h>
-#include <utility>
-
-namespace Botan {
-
-class BOTAN_DLL McEliece_KEM_Encryptor
-   {
-   public:
-      McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key);
-
-      /**
-      * returns the pair (mceliece ciphertext, symmetric key)
-      */
-      std::pair<secure_vector<byte>, secure_vector<byte>> encrypt(RandomNumberGenerator& rng);
-
-   private:
-      const McEliece_PublicKey& m_key;
-   };
-
-class BOTAN_DLL McEliece_KEM_Decryptor
-   {
-    public:
-      McEliece_KEM_Decryptor(const McEliece_PrivateKey& mce_key);
-
-      /**
-      * returns the derived 512-bit symmetric key
-      */
-      secure_vector<Botan::byte> decrypt(const byte msg[], size_t msg_len);
-
-      /**
-      * returns the derived 512-bit symmetric key
-      */
-      template<typename Alloc>
-      secure_vector<Botan::byte> decrypt_vec(const std::vector<byte, Alloc>& v)
-         {
-         return decrypt(v.data(), v.size());
-         }
-
-   private:
-      const McEliece_PrivateKey& m_key;
-  };
-}
-
-#endif
diff --git a/src/lib/pubkey/mceies/mceies.cpp b/src/lib/pubkey/mceies/mceies.cpp
index e83fa257e..0af71719a 100644
--- a/src/lib/pubkey/mceies/mceies.cpp
+++ b/src/lib/pubkey/mceies/mceies.cpp
@@ -8,7 +8,7 @@
 #include <botan/mceies.h>
 #include <botan/aead.h>
 #include <botan/mceliece.h>
-#include <botan/mce_kem.h>
+#include <botan/pubkey.h>
 
 namespace Botan {
 
@@ -36,11 +36,10 @@ mceies_encrypt(const McEliece_PublicKey& pubkey,
                RandomNumberGenerator& rng,
                const std::string& algo)
    {
-   McEliece_KEM_Encryptor kem_op(pubkey);
+   PK_KEM_Encryptor kem_op(pubkey, "KDF1(SHA-512)");
 
-   const std::pair<secure_vector<byte>,secure_vector<byte>> mce_ciphertext__key = kem_op.encrypt(rng);
-   const secure_vector<byte>& mce_ciphertext = mce_ciphertext__key.first;
-   const secure_vector<byte>& mce_key = mce_ciphertext__key.second;
+   secure_vector<byte> mce_ciphertext, mce_key;
+   kem_op.encrypt(mce_ciphertext, mce_key, 64, rng);
 
    const size_t mce_code_bytes = (pubkey.get_code_length() + 7) / 8;
 
@@ -75,7 +74,7 @@ mceies_decrypt(const McEliece_PrivateKey& privkey,
    {
    try
       {
-      McEliece_KEM_Decryptor kem_op(privkey);
+      PK_KEM_Decryptor kem_op(privkey, "KDF1(SHA-512)");
 
       const size_t mce_code_bytes = (privkey.get_code_length() + 7) / 8;
 
@@ -88,7 +87,7 @@ mceies_decrypt(const McEliece_PrivateKey& privkey,
       if(ct_len < mce_code_bytes + nonce_len + aead->tag_size())
          throw Exception("Input message too small to be valid");
 
-      const secure_vector<byte> mce_key = kem_op.decrypt(ct, mce_code_bytes);
+      const secure_vector<byte> mce_key = kem_op.decrypt(ct, mce_code_bytes, 64);
 
       aead->set_key(aead_key(mce_key, *aead));
       aead->set_associated_data(ad, ad_len);
diff --git a/src/lib/pubkey/pk_ops.cpp b/src/lib/pubkey/pk_ops.cpp
index bc421eb90..81b087894 100644
--- a/src/lib/pubkey/pk_ops.cpp
+++ b/src/lib/pubkey/pk_ops.cpp
@@ -129,4 +129,47 @@ bool PK_Ops::Verification_with_EMSA::is_valid_signature(const byte sig[], size_t
       }
    }
 
+void PK_Ops::KEM_Encryption_with_KDF::kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                                                  secure_vector<byte>& out_shared_key,
+                                                  size_t desired_shared_key_len,
+                                                  Botan::RandomNumberGenerator& rng,
+                                                  const uint8_t salt[],
+                                                  size_t salt_len)
+   {
+   secure_vector<byte> raw_shared;
+   this->raw_kem_encrypt(out_encapsulated_key, raw_shared, rng);
+
+   out_shared_key = m_kdf->derive_key(desired_shared_key_len,
+                                      raw_shared.data(), raw_shared.size(),
+                                      salt, salt_len);
+   }
+
+PK_Ops::KEM_Encryption_with_KDF::KEM_Encryption_with_KDF(const std::string& kdf)
+   {
+   m_kdf.reset(get_kdf(kdf));
+   }
+
+PK_Ops::KEM_Encryption_with_KDF::~KEM_Encryption_with_KDF() {}
+
+secure_vector<byte>
+PK_Ops::KEM_Decryption_with_KDF::kem_decrypt(const byte encap_key[],
+                                             size_t len,
+                                             size_t desired_shared_key_len,
+                                             const uint8_t salt[],
+                                             size_t salt_len)
+   {
+   secure_vector<byte> raw_shared = this->raw_kem_decrypt(encap_key, len);
+
+   return m_kdf->derive_key(desired_shared_key_len,
+                            raw_shared.data(), raw_shared.size(),
+                            salt, salt_len);
+   }
+
+PK_Ops::KEM_Decryption_with_KDF::KEM_Decryption_with_KDF(const std::string& kdf)
+   {
+   m_kdf.reset(get_kdf(kdf));
+   }
+
+PK_Ops::KEM_Decryption_with_KDF::~KEM_Decryption_with_KDF() {}
+
 }
diff --git a/src/lib/pubkey/pk_ops.h b/src/lib/pubkey/pk_ops.h
index 3a2a8bdb5..6fc21ea4a 100644
--- a/src/lib/pubkey/pk_ops.h
+++ b/src/lib/pubkey/pk_ops.h
@@ -47,11 +47,13 @@ typedef PK_Spec<Private_Key> PK_Spec_Private_Key;
 class BOTAN_DLL Encryption
    {
    public:
+      typedef PK_Spec_Public_Key Spec;
+
       virtual size_t max_input_bits() const = 0;
 
-      virtual secure_vector<byte> encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator& rng) = 0;
-
-      typedef PK_Spec_Public_Key Spec;
+      virtual secure_vector<byte> encrypt(const byte msg[],
+                                          size_t msg_len,
+                                          RandomNumberGenerator& rng) = 0;
 
       virtual ~Encryption() {}
    };
@@ -164,6 +166,38 @@ class BOTAN_DLL Key_Agreement
       virtual ~Key_Agreement() {}
    };
 
+/**
+* KEM (key encapsulation)
+*/
+class BOTAN_DLL KEM_Encryption
+   {
+   public:
+      typedef PK_Spec_Public_Key Spec;
+
+      virtual void kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                               secure_vector<byte>& out_shared_key,
+                               size_t desired_shared_key_len,
+                               Botan::RandomNumberGenerator& rng,
+                               const uint8_t salt[],
+                               size_t salt_len) = 0;
+
+      virtual ~KEM_Encryption() {}
+   };
+
+class BOTAN_DLL KEM_Decryption
+   {
+   public:
+      typedef PK_Spec_Private_Key Spec;
+
+      virtual secure_vector<byte> kem_decrypt(const byte encap_key[],
+                                              size_t len,
+                                              size_t desired_shared_key_len,
+                                              const uint8_t salt[],
+                                              size_t salt_len) = 0;
+
+      virtual ~KEM_Decryption() {}
+   };
+
 }
 
 }
diff --git a/src/lib/pubkey/pk_ops_impl.h b/src/lib/pubkey/pk_ops_impl.h
index f27de4af4..0acceb53c 100644
--- a/src/lib/pubkey/pk_ops_impl.h
+++ b/src/lib/pubkey/pk_ops_impl.h
@@ -139,6 +139,46 @@ class Key_Agreement_with_KDF : public Key_Agreement
       std::unique_ptr<KDF> m_kdf;
    };
 
+class KEM_Encryption_with_KDF : public KEM_Encryption
+   {
+   public:
+      void kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                       secure_vector<byte>& out_shared_key,
+                       size_t desired_shared_key_len,
+                       Botan::RandomNumberGenerator& rng,
+                       const uint8_t salt[],
+                       size_t salt_len) override;
+
+   protected:
+      virtual void raw_kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                                   secure_vector<byte>& raw_shared_key,
+                                   Botan::RandomNumberGenerator& rng) = 0;
+
+      KEM_Encryption_with_KDF(const std::string& kdf);
+      ~KEM_Encryption_with_KDF();
+   private:
+      std::unique_ptr<KDF> m_kdf;
+   };
+
+class KEM_Decryption_with_KDF : public KEM_Decryption
+   {
+   public:
+      secure_vector<byte> kem_decrypt(const byte encap_key[],
+                                      size_t len,
+                                      size_t desired_shared_key_len,
+                                      const uint8_t salt[],
+                                      size_t salt_len);
+
+   protected:
+      virtual secure_vector<byte>
+      raw_kem_decrypt(const byte encap_key[], size_t len) = 0;
+
+      KEM_Decryption_with_KDF(const std::string& kdf);
+      ~KEM_Decryption_with_KDF();
+   private:
+      std::unique_ptr<KDF> m_kdf;
+   };
+
 }
 
 }
diff --git a/src/lib/pubkey/pk_utils.h b/src/lib/pubkey/pk_utils.h
index 326a6ea68..04a0bf5ca 100644
--- a/src/lib/pubkey/pk_utils.h
+++ b/src/lib/pubkey/pk_utils.h
@@ -32,6 +32,9 @@ OP* make_pk_op(const typename T::Spec& spec)
 #define BOTAN_REGISTER_PK_VERIFY_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Verification, NAME, TYPE)
 #define BOTAN_REGISTER_PK_KEY_AGREE_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::Key_Agreement, NAME, TYPE)
 
+#define BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::KEM_Encryption, NAME, TYPE)
+#define BOTAN_REGISTER_PK_KEM_DECRYPTION_OP(NAME, TYPE) BOTAN_REGISTER_PK_OP(PK_Ops::KEM_Decryption, NAME, TYPE)
+
 }
 
 #endif
diff --git a/src/lib/pubkey/pubkey.cpp b/src/lib/pubkey/pubkey.cpp
index b9923f54b..e870dfdec 100644
--- a/src/lib/pubkey/pubkey.cpp
+++ b/src/lib/pubkey/pubkey.cpp
@@ -59,6 +59,46 @@ secure_vector<byte> PK_Decryptor_EME::dec(const byte msg[], size_t length) const
    return m_op->decrypt(msg, length);
    }
 
+PK_KEM_Encryptor::PK_KEM_Encryptor(const Public_Key& key,
+                                   const std::string& param,
+                                   const std::string& provider)
+   {
+   m_op.reset(get_pk_op<PK_Ops::KEM_Encryption>("KEM", key, param, provider));
+   }
+
+void PK_KEM_Encryptor::encrypt(secure_vector<byte>& out_encapsulated_key,
+                               secure_vector<byte>& out_shared_key,
+                               size_t desired_shared_key_len,
+                               Botan::RandomNumberGenerator& rng,
+                               const uint8_t salt[],
+                               size_t salt_len)
+   {
+   m_op->kem_encrypt(out_encapsulated_key,
+                     out_shared_key,
+                     desired_shared_key_len,
+                     rng,
+                     salt,
+                     salt_len);
+   }
+
+PK_KEM_Decryptor::PK_KEM_Decryptor(const Private_Key& key,
+                                   const std::string& param,
+                                   const std::string& provider)
+   {
+   m_op.reset(get_pk_op<PK_Ops::KEM_Decryption>("KEM", key, param, provider));
+   }
+
+secure_vector<byte> PK_KEM_Decryptor::decrypt(const byte encap_key[],
+                                              size_t encap_key_len,
+                                              size_t desired_shared_key_len,
+                                              const uint8_t salt[],
+                                              size_t salt_len)
+   {
+   return m_op->kem_decrypt(encap_key, encap_key_len,
+                            desired_shared_key_len,
+                            salt, salt_len);
+   }
+
 PK_Key_Agreement::PK_Key_Agreement(const Private_Key& key, const std::string& kdf)
    {
    m_op.reset(get_pk_op<PK_Ops::Key_Agreement>("Key agreement", key, kdf));
diff --git a/src/lib/pubkey/pubkey.h b/src/lib/pubkey/pubkey.h
index 637e522e4..a8caf58ac 100644
--- a/src/lib/pubkey/pubkey.h
+++ b/src/lib/pubkey/pubkey.h
@@ -438,6 +438,87 @@ class BOTAN_DLL PK_Decryptor_EME : public PK_Decryptor
       std::unique_ptr<PK_Ops::Decryption> m_op;
    };
 
+class BOTAN_DLL PK_KEM_Encryptor
+   {
+   public:
+      PK_KEM_Encryptor(const Public_Key& key,
+                       const std::string& kem_param = "",
+                       const std::string& provider = "");
+
+      void encrypt(secure_vector<byte>& out_encapsulated_key,
+                   secure_vector<byte>& out_shared_key,
+                   size_t desired_shared_key_len,
+                   Botan::RandomNumberGenerator& rng,
+                   const uint8_t salt[],
+                   size_t salt_len);
+
+      template<typename Alloc>
+         void encrypt(secure_vector<byte>& out_encapsulated_key,
+                      secure_vector<byte>& out_shared_key,
+                      size_t desired_shared_key_len,
+                      Botan::RandomNumberGenerator& rng,
+                      const std::vector<uint8_t, Alloc>& salt)
+         {
+         this->encrypt(out_encapsulated_key,
+                       out_shared_key,
+                       desired_shared_key_len,
+                       rng,
+                       salt.data(), salt.size());
+         }
+
+      void encrypt(secure_vector<byte>& out_encapsulated_key,
+                   secure_vector<byte>& out_shared_key,
+                   size_t desired_shared_key_len,
+                   Botan::RandomNumberGenerator& rng)
+         {
+         this->encrypt(out_encapsulated_key,
+                       out_shared_key,
+                       desired_shared_key_len,
+                       rng,
+                       nullptr,
+                       0);
+         }
+
+   private:
+      std::unique_ptr<PK_Ops::KEM_Encryption> m_op;
+   };
+
+class BOTAN_DLL PK_KEM_Decryptor
+   {
+   public:
+      PK_KEM_Decryptor(const Private_Key& key,
+                       const std::string& kem_param = "",
+                       const std::string& provider = "");
+
+      secure_vector<byte> decrypt(const byte encap_key[],
+                                  size_t encap_key_len,
+                                  size_t desired_shared_key_len,
+                                  const uint8_t salt[],
+                                  size_t salt_len);
+
+      secure_vector<byte> decrypt(const byte encap_key[],
+                                  size_t encap_key_len,
+                                  size_t desired_shared_key_len)
+         {
+         return this->decrypt(encap_key, encap_key_len,
+                              desired_shared_key_len,
+                              nullptr, 0);
+         }
+
+      template<typename Alloc1, typename Alloc2>
+         secure_vector<byte> decrypt(const std::vector<byte, Alloc1>& encap_key,
+                                     size_t desired_shared_key_len,
+                                     const std::vector<byte, Alloc2>& salt)
+         {
+         return this->decrypt(encap_key.data(), encap_key.size(),
+                              desired_shared_key_len,
+                              salt.data(), salt.size());
+         }
+
+   private:
+      std::unique_ptr<PK_Ops::KEM_Decryption> m_op;
+   };
+
 }
 
 #endif
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 5804d0034..d18843315 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -1,6 +1,6 @@
 /*
 * RSA
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -13,6 +13,8 @@
 #include <botan/reducer.h>
 #include <future>
 
+#include <iostream>
+
 namespace Botan {
 
 /*
@@ -156,11 +158,34 @@ class RSA_Decryption_Operation : public PK_Ops::Decryption_with_EME,
          const BigInt m(msg, msg_len);
          const BigInt x = blinded_private_op(m);
          const BigInt c = m_powermod_e_n(x);
-         BOTAN_ASSERT(m == c, "RSA sign consistency check");
+         BOTAN_ASSERT(m == c, "RSA decrypt consistency check");
          return BigInt::encode_locked(x);
          }
    };
 
+class RSA_KEM_Decryption_Operation : public PK_Ops::KEM_Decryption_with_KDF,
+                                     private RSA_Private_Operation
+   {
+   public:
+      typedef RSA_PrivateKey Key_Type;
+
+      RSA_KEM_Decryption_Operation(const RSA_PrivateKey& key,
+                                   const std::string& kdf) :
+         PK_Ops::KEM_Decryption_with_KDF(kdf),
+         RSA_Private_Operation(key)
+         {}
+
+      secure_vector<byte>
+      raw_kem_decrypt(const byte encap_key[], size_t len) override
+         {
+         const BigInt m(encap_key, len);
+         const BigInt x = blinded_private_op(m);
+         const BigInt c = m_powermod_e_n(x);
+         BOTAN_ASSERT(m == c, "RSA KEM consistency check");
+         return BigInt::encode_1363(x, n.bytes());
+         }
+   };
+
 /**
 * RSA public (encrypt/verify) operation
 */
@@ -181,6 +206,8 @@ class RSA_Public_Operation
          return powermod_e_n(m);
          }
 
+      const BigInt& get_n() const { return n; }
+
       const BigInt& n;
       Fixed_Exponent_Power_Mod powermod_e_n;
    };
@@ -230,11 +257,42 @@ class RSA_Verify_Operation : public PK_Ops::Verification_with_EMSA,
          }
    };
 
+class RSA_KEM_Encryption_Operation : public PK_Ops::KEM_Encryption_with_KDF,
+                                     private RSA_Public_Operation
+   {
+   public:
+      typedef RSA_PublicKey Key_Type;
+
+      RSA_KEM_Encryption_Operation(const RSA_PublicKey& key,
+                                   const std::string& kdf) :
+         PK_Ops::KEM_Encryption_with_KDF(kdf),
+         RSA_Public_Operation(key) {}
+
+   private:
+      void raw_kem_encrypt(secure_vector<byte>& out_encapsulated_key,
+                           secure_vector<byte>& raw_shared_key,
+                           Botan::RandomNumberGenerator& rng) override
+         {
+         const BigInt r = BigInt::random_integer(rng, 1, get_n());
+         std::cout << "R = " << r << "\n";
+         const BigInt c = public_op(r);
+         std::cout << "C0 = " << c << "\n";
+
+         out_encapsulated_key = BigInt::encode_locked(c);
+         raw_shared_key = BigInt::encode_locked(r);
+         }
+   };
+
+
 BOTAN_REGISTER_PK_ENCRYPTION_OP("RSA", RSA_Encryption_Operation);
 BOTAN_REGISTER_PK_DECRYPTION_OP("RSA", RSA_Decryption_Operation);
+
 BOTAN_REGISTER_PK_SIGNATURE_OP("RSA", RSA_Signature_Operation);
 BOTAN_REGISTER_PK_VERIFY_OP("RSA", RSA_Verify_Operation);
 
+BOTAN_REGISTER_PK_KEM_ENCRYPTION_OP("RSA", RSA_KEM_Encryption_Operation);
+BOTAN_REGISTER_PK_KEM_DECRYPTION_OP("RSA", RSA_KEM_Decryption_Operation);
+
 }
 
 }
diff --git a/src/tests/data/pubkey/rsa_kem.vec b/src/tests/data/pubkey/rsa_kem.vec
new file mode 100644
index 000000000..6fb76fcfe
--- /dev/null
+++ b/src/tests/data/pubkey/rsa_kem.vec
@@ -0,0 +1,25 @@
+
+# RSA-KEM tests vectors from ISO-18033-2
+# http://www.shoup.net/iso/std4.pdf
+
+# R values here are -1 from the actual desired value to account for
+# some logic in random_integer wrt the bounds
+
+# Test C.6.2
+E = 65537
+P = 74100103850091296168511028051948833436338123529747970640732238422269665602829
+Q = 79461607023043824134896992211543210236933205105414344240218914846895267687977
+R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA3
+C0 = 4603E5324CAB9CEF8365C817052D954D44447B1667099EDC69942D32CD594E4FFCF268AE3836E2C35744AAA53AE201FE499806B67DEDAA26BF72ECBD117A6FC0
+KDF = KDF2(SHA-1)
+K = 0E6A26EB7B956CCB8B3BDC1CA975BC57C3989E8FBAD31A224655D800C46954840F
+
+# Test C.6.4
+
+E = 65537
+P = 74100103850091296168511028051948833436338123529747970640732238422269665602829
+Q = 79461607023043824134896992211543210236933205105414344240218914846895267687977
+R = 032E45326FA859A72EC235ACFF929B15D1372E30B207255F0611B8F785D764374152E0AC009E509E7BA30CD2F1778E113B64E135CF4E2292C75EFE5288EDFDA3
+C0 = 4603E5324CAB9CEF8365C817052D954D44447B1667099EDC69942D32CD594E4FFCF268AE3836E2C35744AAA53AE201FE499806B67DEDAA26BF72ECBD117A6FC0
+KDF = KDF2(SHA-256)
+K = 10a2403db42a8743cb989de86e668d168cbe6046
diff --git a/src/tests/test_mceliece.cpp b/src/tests/test_mceliece.cpp
index d3c646504..5bbe7161a 100644
--- a/src/tests/test_mceliece.cpp
+++ b/src/tests/test_mceliece.cpp
@@ -11,7 +11,6 @@
 #if defined(BOTAN_HAS_MCELIECE)
 
 #include <botan/mceliece.h>
-#include <botan/mce_kem.h>
 #include <botan/pubkey.h>
 #include <botan/oids.h>
 #include <botan/hmac_drbg.h>
@@ -81,13 +80,17 @@ class McEliece_Keygen_Encrypt_Test : public Text_Based_Test
          rng.clear();
          rng.add_entropy(encrypt_seed.data(), encrypt_seed.size());
 
-         Botan::McEliece_KEM_Encryptor kem_enc(mce_priv);
-         Botan::McEliece_KEM_Decryptor kem_dec(mce_priv);
+         Botan::PK_KEM_Encryptor kem_enc(mce_priv, "KDF1(SHA-512)");
+         Botan::PK_KEM_Decryptor kem_dec(mce_priv, "KDF1(SHA-512)");
 
-         const auto kem = kem_enc.encrypt(rng);
-         result.test_eq("ciphertext", kem.first, ciphertext);
-         result.test_eq("encrypt shared", kem.second, shared_key);
-         result.test_eq("decrypt shared", kem_dec.decrypt_vec(kem.first), shared_key);
+         Botan::secure_vector<byte> encap_key, prod_shared_key;
+         kem_enc.encrypt(encap_key, prod_shared_key, 64, rng);
+
+         Botan::secure_vector<byte> dec_shared_key = kem_dec.decrypt(encap_key.data(), encap_key.size(), 64);
+
+         result.test_eq("ciphertext", encap_key, ciphertext);
+         result.test_eq("encrypt shared", prod_shared_key, shared_key);
+         result.test_eq("decrypt shared", dec_shared_key, shared_key);
          return result;
          }
 
@@ -176,18 +179,19 @@ class McEliece_Tests : public Test
          {
          Test::Result result("McEliece KEM");
 
-         Botan::McEliece_KEM_Encryptor pub_op(pk);
-         Botan::McEliece_KEM_Decryptor priv_op(sk);
+         Botan::PK_KEM_Encryptor enc_op(pk, "KDF2(SHA-256)");
+         Botan::PK_KEM_Decryptor dec_op(sk, "KDF2(SHA-256)");
 
          for(size_t i = 0; i <= Test::soak_level(); i++)
             {
-            const std::pair<Botan::secure_vector<byte>,Botan::secure_vector<byte> > ciphertext__sym_key = pub_op.encrypt(Test::rng());
-            const Botan::secure_vector<byte>& ciphertext = ciphertext__sym_key.first;
-            const Botan::secure_vector<byte>& sym_key_encr = ciphertext__sym_key.second;
+            Botan::secure_vector<byte> salt = Test::rng().random_vec(i);
+
+            Botan::secure_vector<byte> encap_key, shared_key;
+            enc_op.encrypt(encap_key, shared_key, 64, Test::rng(), salt);
 
-            const Botan::secure_vector<byte> sym_key_decr = priv_op.decrypt(ciphertext.data(), ciphertext.size());
+            Botan::secure_vector<byte> shared_key2 = dec_op.decrypt(encap_key, 64, salt);
 
-            result.test_eq("same key", sym_key_decr, sym_key_encr);
+            result.test_eq("same key", shared_key, shared_key2);
             }
          return result;
          }
diff --git a/src/tests/test_pubkey.cpp b/src/tests/test_pubkey.cpp
index 89d79bec8..a596824a7 100644
--- a/src/tests/test_pubkey.cpp
+++ b/src/tests/test_pubkey.cpp
@@ -249,6 +249,46 @@ PK_Encryption_Decryption_Test::run_one_test(const std::string&, const VarMap& va
    return result;
    }
 
+Test::Result PK_KEM_Test::run_one_test(const std::string&, const VarMap& vars)
+   {
+   const std::vector<uint8_t> K = get_req_bin(vars, "K");
+   const std::vector<uint8_t> C0 = get_req_bin(vars, "C0");
+   const std::vector<uint8_t> salt = get_opt_bin(vars, "Salt");
+   const std::string kdf = get_req_str(vars, "KDF");
+
+   Test::Result result(algo_name() + "/" + kdf + " KEM");
+
+   std::unique_ptr<Botan::Private_Key> privkey = load_private_key(vars);
+
+   const size_t desired_key_len = K.size();
+
+   Botan::PK_KEM_Encryptor enc(*privkey, kdf);
+
+   Fixed_Output_RNG fixed_output_rng(get_req_bin(vars, "R"));
+
+   Botan::secure_vector<byte> produced_encap_key, shared_key;
+   enc.encrypt(produced_encap_key,
+               shared_key,
+               desired_key_len,
+               fixed_output_rng,
+               salt);
+
+   result.test_eq("C0 matches", produced_encap_key, C0);
+   result.test_eq("K matches", shared_key, K);
+
+   Botan::PK_KEM_Decryptor dec(*privkey, kdf);
+
+   const Botan::secure_vector<uint8_t> decr_shared_key =
+      dec.decrypt(C0.data(), C0.size(),
+                  desired_key_len,
+                  salt.data(),
+                  salt.size());
+
+   result.test_eq("decrypted K matches", decr_shared_key, K);
+
+   return result;
+   }
+
 Test::Result PK_Key_Agreement_Test::run_one_test(const std::string&, const VarMap& vars)
    {
    const std::vector<uint8_t> shared = get_req_bin(vars, "K");
diff --git a/src/tests/test_pubkey.h b/src/tests/test_pubkey.h
index edb36f07b..beb1b2ea2 100644
--- a/src/tests/test_pubkey.h
+++ b/src/tests/test_pubkey.h
@@ -87,6 +87,22 @@ class PK_Key_Agreement_Test : public Text_Based_Test
       Test::Result run_one_test(const std::string& header, const VarMap& vars) override;
    };
 
+class PK_KEM_Test : public Text_Based_Test
+   {
+   public:
+      //using Text_Based_Test::Text_Based_Test;
+
+      PK_KEM_Test(const std::string& algo,
+                  const std::string& test_src,
+                  const std::vector<std::string>& required_keys,
+                  const std::vector<std::string>& optional_keys = {}) :
+         Text_Based_Test(algo, test_src, required_keys, optional_keys) {}
+
+      virtual std::unique_ptr<Botan::Private_Key> load_private_key(const VarMap& vars) = 0;
+   private:
+      Test::Result run_one_test(const std::string& header, const VarMap& vars) override;
+   };
+
 class PK_Key_Generation_Test : public Test
    {
    protected:
diff --git a/src/tests/test_rsa.cpp b/src/tests/test_rsa.cpp
index 2720ae49a..6c89a5b29 100644
--- a/src/tests/test_rsa.cpp
+++ b/src/tests/test_rsa.cpp
@@ -38,6 +38,25 @@ class RSA_ES_KAT_Tests : public PK_Encryption_Decryption_Test
          }
    };
 
+class RSA_KEM_Tests : public PK_KEM_Test
+   {
+   public:
+      RSA_KEM_Tests() : PK_KEM_Test("RSA", "pubkey/rsa_kem.vec",
+                                    {"E", "P", "Q", "R", "C0", "KDF", "OutLen", "K"})
+         {}
+
+      std::unique_ptr<Botan::Private_Key> load_private_key(const VarMap& vars) override
+         {
+         const BigInt p = get_req_bn(vars, "P");
+         const BigInt q = get_req_bn(vars, "Q");
+         const BigInt e = get_req_bn(vars, "E");
+
+         std::unique_ptr<Botan::Private_Key> key(new Botan::RSA_PrivateKey(Test::rng(), p, q, e));
+         return key;
+         }
+
+   };
+
 class RSA_Signature_KAT_Tests : public PK_Signature_Generation_Test
    {
    public:
@@ -100,6 +119,7 @@ class RSA_Keygen_Tests : public PK_Key_Generation_Test
 BOTAN_REGISTER_TEST("rsa_encrypt", RSA_ES_KAT_Tests);
 BOTAN_REGISTER_TEST("rsa_sign", RSA_Signature_KAT_Tests);
 BOTAN_REGISTER_TEST("rsa_verify", RSA_Signature_Verify_Tests);
+BOTAN_REGISTER_TEST("rsa_kem", RSA_KEM_Tests);
 BOTAN_REGISTER_TEST("rsa_keygen", RSA_Keygen_Tests);
 
 #endif