Add ECKCDSA signature algorithm

23 files changed, 545 insertions, 26 deletions

diff --git a/src/lib/asn1/oid_lookup/default.cpp b/src/lib/asn1/oid_lookup/default.cpp
index 9e16cfc0b..1f107ec86 100644
--- a/src/lib/asn1/oid_lookup/default.cpp
+++ b/src/lib/asn1/oid_lookup/default.cpp
@@ -33,6 +33,9 @@ const char* default_oid_list()
       // ecgPublicKey (see https://www.teletrust.de/projekte/oid/)
       "1.3.36.3.3.2.5.2.1 = ECGDSA" "\n"
 
+      // EC-KCDSA mechanism (Elliptic Curve KCDSA)
+      "1.0.14888.3.0.5 = ECKCDSA" "\n"
+
       "1.2.643.2.2.19 = GOST-34.10" "\n"
 
       // Block ciphers
diff --git a/src/lib/pk_pad/emsa.cpp b/src/lib/pk_pad/emsa.cpp
index 3b8641357..91bf44cf8 100644
--- a/src/lib/pk_pad/emsa.cpp
+++ b/src/lib/pk_pad/emsa.cpp
@@ -45,6 +45,19 @@ EMSA* get_emsa(const std::string& algo_spec)
    throw Algorithm_Not_Found(algo_spec);
    }
 
+std::string hash_for_emsa(const std::string& algo_spec)
+   {
+   SCAN_Name emsa_name(algo_spec);
+
+   if(emsa_name.arg_count() > 0)
+      {
+      const std::string pos_hash = emsa_name.arg(0);
+      return pos_hash;
+      }
+
+   return "SHA-512"; // safe default if nothing we understand
+   }
+
 #define BOTAN_REGISTER_EMSA_NAMED_NOARGS(type, name) \
    BOTAN_REGISTER_NAMED_T(EMSA, name, type, make_new_T<type>)
 
diff --git a/src/lib/pk_pad/emsa.h b/src/lib/pk_pad/emsa.h
index d4fd146da..f4697d100 100644
--- a/src/lib/pk_pad/emsa.h
+++ b/src/lib/pk_pad/emsa.h
@@ -59,16 +59,27 @@ class BOTAN_DLL EMSA
                           size_t key_bits) = 0;
 
       virtual ~EMSA();
+
+      virtual EMSA* clone() = 0;
    };
 
 /**
 * Factory method for EMSA (message-encoding methods for signatures
 * with appendix) objects
-* @param algo_spec the name of the EME to create
+* @param algo_spec the name of the EMSA to create
 * @return pointer to newly allocated object of that type
 */
 BOTAN_DLL EMSA* get_emsa(const std::string& algo_spec);
 
+/**
+* Returns the hash function used in the given EMSA scheme
+* If the hash function is not specified or not understood,
+* returns "SHA-512"
+* @param algo_spec the name of the EMSA
+* @return hash function used in the given EMSA scheme
+*/
+BOTAN_DLL std::string hash_for_emsa(const std::string& algo_spec);
+
 }
 
 #endif
diff --git a/src/lib/pk_pad/emsa1/emsa1.cpp b/src/lib/pk_pad/emsa1/emsa1.cpp
index 0031bf263..67f8ab21f 100644
--- a/src/lib/pk_pad/emsa1/emsa1.cpp
+++ b/src/lib/pk_pad/emsa1/emsa1.cpp
@@ -40,6 +40,11 @@ secure_vector<byte> emsa1_encoding(const secure_vector<byte>& msg,
 
 }
 
+EMSA* EMSA1::clone()
+   {
+   return new EMSA1(m_hash->clone());
+   }
+
 void EMSA1::update(const byte input[], size_t length)
    {
    m_hash->update(input, length);
diff --git a/src/lib/pk_pad/emsa1/emsa1.h b/src/lib/pk_pad/emsa1/emsa1.h
index e346167da..5a4b4b372 100644
--- a/src/lib/pk_pad/emsa1/emsa1.h
+++ b/src/lib/pk_pad/emsa1/emsa1.h
@@ -25,8 +25,13 @@ class BOTAN_DLL EMSA1 : public EMSA
       */
       explicit EMSA1(HashFunction* hash) : m_hash(hash) {}
 
+      EMSA* clone() override;
+
    protected:
       size_t hash_output_length() const { return m_hash->output_length(); }
+
+      std::unique_ptr<HashFunction> m_hash;
+
    private:
       void update(const byte[], size_t) override;
       secure_vector<byte> raw_data() override;
@@ -39,7 +44,6 @@ class BOTAN_DLL EMSA1 : public EMSA
                   const secure_vector<byte>& raw,
                   size_t key_bits) override;
 
-      std::unique_ptr<HashFunction> m_hash;
    };
 
 }
diff --git a/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.cpp b/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.cpp
index 5fc96da8d..24f10b07e 100644
--- a/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.cpp
+++ b/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.cpp
@@ -10,6 +10,12 @@
 
 namespace Botan {
 
+EMSA* EMSA1_BSI::clone()
+   {
+   return new EMSA1_BSI(m_hash->clone());
+   }
+
+
 /*
 * EMSA1 BSI Encode Operation
 */
diff --git a/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.h b/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.h
index a7fae6c23..ac351cd2f 100644
--- a/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.h
+++ b/src/lib/pk_pad/emsa1_bsi/emsa1_bsi.h
@@ -25,6 +25,8 @@ class BOTAN_DLL EMSA1_BSI final : public EMSA1
       * @param hash the hash object to use
       */
       explicit EMSA1_BSI(HashFunction* hash) : EMSA1(hash) {}
+
+      EMSA* clone() override;
    private:
       secure_vector<byte> encoding_of(const secure_vector<byte>&, size_t,
                                      RandomNumberGenerator& rng) override;
diff --git a/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.h b/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.h
index 9d5bc7829..0773ed2c4 100644
--- a/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.h
+++ b/src/lib/pk_pad/emsa_pkcs1/emsa_pkcs1.h
@@ -28,6 +28,8 @@ class BOTAN_DLL EMSA_PKCS1v15 final : public EMSA
       */
       explicit EMSA_PKCS1v15(HashFunction* hash);
 
+      EMSA* clone() override { return new EMSA_PKCS1v15(m_hash->clone()); }
+
       void update(const byte[], size_t) override;
 
       secure_vector<byte> raw_data() override;
@@ -50,6 +52,8 @@ class BOTAN_DLL EMSA_PKCS1v15 final : public EMSA
 class BOTAN_DLL EMSA_PKCS1v15_Raw final : public EMSA
    {
    public:
+      EMSA* clone() override { return new EMSA_PKCS1v15_Raw(); }
+
       void update(const byte[], size_t) override;
 
       secure_vector<byte> raw_data() override;
diff --git a/src/lib/pk_pad/emsa_pssr/pssr.h b/src/lib/pk_pad/emsa_pssr/pssr.h
index ee234b0b6..9b39417a5 100644
--- a/src/lib/pk_pad/emsa_pssr/pssr.h
+++ b/src/lib/pk_pad/emsa_pssr/pssr.h
@@ -31,6 +31,8 @@ class BOTAN_DLL PSSR final : public EMSA
       */
       PSSR(HashFunction* hash, size_t salt_size);
 
+      EMSA* clone() override { return new PSSR(m_hash->clone(), m_SALT_SIZE); }
+
       static PSSR* make(const Spec& spec);
    private:
       void update(const byte input[], size_t length) override;
diff --git a/src/lib/pk_pad/emsa_raw/emsa_raw.h b/src/lib/pk_pad/emsa_raw/emsa_raw.h
index 272d34b0e..cc2d5d63a 100644
--- a/src/lib/pk_pad/emsa_raw/emsa_raw.h
+++ b/src/lib/pk_pad/emsa_raw/emsa_raw.h
@@ -18,6 +18,9 @@ namespace Botan {
 */
 class BOTAN_DLL EMSA_Raw final : public EMSA
    {
+   public:
+      EMSA* clone() override { return new EMSA_Raw(); }
+
    private:
       void update(const byte[], size_t) override;
       secure_vector<byte> raw_data() override;
diff --git a/src/lib/pk_pad/emsa_x931/emsa_x931.h b/src/lib/pk_pad/emsa_x931/emsa_x931.h
index 400042a86..56754d3b1 100644
--- a/src/lib/pk_pad/emsa_x931/emsa_x931.h
+++ b/src/lib/pk_pad/emsa_x931/emsa_x931.h
@@ -25,6 +25,8 @@ class BOTAN_DLL EMSA_X931 final : public EMSA
       * @param hash the hash object to use
       */
       explicit EMSA_X931(HashFunction* hash);
+
+      EMSA* clone() override { return new EMSA_X931(m_hash->clone()); }
    private:
       void update(const byte[], size_t) override;
       secure_vector<byte> raw_data() override;
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index c7d44c73a..6e0618fa2 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -13,6 +13,7 @@
 #include <botan/reducer.h>
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
   #include <botan/rfc6979.h>
+  #include <botan/emsa.h>
 #endif
 #include <future>
 
@@ -115,7 +116,7 @@ DSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
       i -= m_q;
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
-   const BigInt k = generate_rfc6979_nonce(m_x, m_q, i, hash_for_deterministic_signature(m_emsa));
+   const BigInt k = generate_rfc6979_nonce(m_x, m_q, i, hash_for_emsa(m_emsa));
 #else
    const BigInt k = BigInt::random_integer(rng, 1, m_q);
 #endif
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 53b5982e0..14f902c13 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -13,6 +13,7 @@
 #include <botan/keypair.h>
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
   #include <botan/rfc6979.h>
+  #include <botan/emsa.h>
 #endif
 
 namespace Botan {
@@ -72,7 +73,7 @@ ECDSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
    const BigInt m(msg, msg_len);
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
-   const BigInt k = generate_rfc6979_nonce(m_x, m_order, m, hash_for_deterministic_signature(m_emsa));
+   const BigInt k = generate_rfc6979_nonce(m_x, m_order, m, hash_for_emsa(m_emsa));
 #else
    const BigInt k = BigInt::random_integer(rng, 1, m_order);
 #endif
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
new file mode 100644
index 000000000..83439332e
--- /dev/null
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
@@ -0,0 +1,201 @@
+/*
+* ECKCDSA (ISO/IEC 14888-3:2006/Cor.2:2009)
+* (C) 2016 René Korthaus, Sirrix AG
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/pk_utils.h>
+#include <botan/eckcdsa.h>
+#include <botan/keypair.h>
+#include <botan/emsa.h>
+#include <botan/hash.h>
+
+namespace Botan {
+
+bool ECKCDSA_PrivateKey::check_key(RandomNumberGenerator& rng,
+                                 bool strong) const
+   {
+   if(!public_point().on_the_curve())
+      {
+      return false;
+      }
+
+   if(!strong)
+      {
+      return true;
+      }
+
+   return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)");
+   }
+
+namespace {
+
+/**
+* ECKCDSA signature operation
+*/
+class ECKCDSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
+   {
+   public:
+      typedef ECKCDSA_PrivateKey Key_Type;
+
+      ECKCDSA_Signature_Operation(const ECKCDSA_PrivateKey& eckcdsa,
+                                const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
+         m_order(eckcdsa.domain().get_order()),
+         m_base_point(eckcdsa.domain().get_base_point(), m_order),
+         m_x(eckcdsa.private_value()),
+         m_mod_order(m_order),
+         m_prefix()
+         {
+         const BigInt public_point_x = eckcdsa.public_point().get_affine_x();
+         const BigInt public_point_y = eckcdsa.public_point().get_affine_y();
+
+         m_prefix.resize(public_point_x.bytes() + public_point_y.bytes());
+         public_point_x.binary_encode(m_prefix.data());
+         public_point_y.binary_encode(&m_prefix[public_point_x.bytes()]);
+         m_prefix.resize(HashFunction::create(hash_for_signature())->hash_block_size()); // use only the "hash input block size" leftmost bits
+         }
+
+      secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
+                                   RandomNumberGenerator& rng) override;
+
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return m_order.bytes(); }
+      size_t max_input_bits() const override { return m_order.bits(); }
+
+      bool has_prefix() override { return true; }
+      secure_vector<byte> message_prefix() const override { return m_prefix; }
+
+   private:
+      const BigInt& m_order;
+      Blinded_Point_Multiply m_base_point;
+      const BigInt& m_x;
+      Modular_Reducer m_mod_order;
+      secure_vector<byte> m_prefix;
+   };
+
+secure_vector<byte>
+ECKCDSA_Signature_Operation::raw_sign(const byte msg[], size_t,
+                                     RandomNumberGenerator& rng)
+   {
+   const BigInt k = BigInt::random_integer(rng, 1, m_order);
+   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const BigInt k_times_P_x = k_times_P.get_affine_x();
+
+   secure_vector<byte> to_be_hashed(k_times_P_x.bytes());
+   k_times_P_x.binary_encode(to_be_hashed.data());
+
+   std::unique_ptr<EMSA> emsa(m_emsa->clone());
+   emsa->update(to_be_hashed.data(), to_be_hashed.size());
+   secure_vector<byte> c = emsa->raw_data();
+   c = emsa->encoding_of(c, max_input_bits(), rng);
+
+   const BigInt r(c.data(), c.size());
+
+   xor_buf(c, msg, c.size());
+   BigInt w(c.data(), c.size());
+   w = m_mod_order.reduce(w);
+
+   const BigInt s = m_mod_order.multiply(m_x, k - w);
+   BOTAN_ASSERT(s != 0, "invalid s");
+
+   secure_vector<byte> signature(r.bytes() + s.bytes());
+   r.binary_encode(signature.data());
+   s.binary_encode(&signature[r.bytes()]);
+   return signature;
+   }
+
+/**
+* ECKCDSA verification operation
+*/
+class ECKCDSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
+   {
+   public:
+      typedef ECKCDSA_PublicKey Key_Type;
+
+      ECKCDSA_Verification_Operation(const ECKCDSA_PublicKey& eckcdsa,
+                                   const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
+         m_base_point(eckcdsa.domain().get_base_point()),
+         m_public_point(eckcdsa.public_point()),
+         m_order(eckcdsa.domain().get_order()),
+         m_mod_order(m_order),
+         m_prefix()
+         {
+         const BigInt public_point_x = m_public_point.get_affine_x();
+         const BigInt public_point_y = m_public_point.get_affine_y();
+
+         m_prefix.resize(public_point_x.bytes() + public_point_y.bytes());
+         public_point_x.binary_encode(&m_prefix[0]);
+         public_point_y.binary_encode(&m_prefix[public_point_x.bytes()]);
+         m_prefix.resize(HashFunction::create(hash_for_signature())->hash_block_size()); // use only the "hash input block size" leftmost bits
+         }
+
+      bool has_prefix() override { return true; }
+      secure_vector<byte> message_prefix() const override { return m_prefix; }
+
+      size_t message_parts() const override { return 2; }
+      size_t message_part_size() const override { return m_order.bytes(); }
+      size_t max_input_bits() const override { return m_order.bits(); }
+
+      bool with_recovery() const override { return false; }
+
+      bool verify(const byte msg[], size_t msg_len,
+                  const byte sig[], size_t sig_len) override;
+   private:
+      const PointGFp& m_base_point;
+      const PointGFp& m_public_point;
+      const BigInt& m_order;
+      // FIXME: should be offered by curve
+      Modular_Reducer m_mod_order;
+      secure_vector<byte> m_prefix;
+   };
+
+bool ECKCDSA_Verification_Operation::verify(const byte msg[], size_t,
+                                           const byte sig[], size_t sig_len)
+   {
+   // check that bit length of r is equal to output bit length of employed hash function h
+   const std::unique_ptr<HashFunction> hash = HashFunction::create(hash_for_signature());
+
+   // no way to know size of r in sig, so check that we have at least hash->output_length()+1
+   // bytes in sig, enough for r and an arbitrary size s
+   if(sig_len <= hash->output_length())
+      {
+      return false;
+      }
+
+   secure_vector<byte> r(sig, sig + hash->output_length());
+
+   // check that 0 < s < q
+   const BigInt s(sig + hash->output_length(), sig_len - hash->output_length());
+
+   if(s <= 0 || s >= m_order)
+      {
+      return false;
+      }
+
+   secure_vector<byte> r_xor_e(r);
+   xor_buf(r_xor_e, msg, r.size());
+   BigInt w(r_xor_e.data(), r_xor_e.size());
+   w = m_mod_order.reduce(w);
+
+   const PointGFp q = (m_base_point * w) + (m_public_point * s);
+   const BigInt q_x = q.get_affine_x();
+   secure_vector<byte> c(q_x.bytes());
+   q_x.binary_encode(c.data());
+   std::unique_ptr<EMSA> emsa(m_emsa->clone());
+   emsa->update(c.data(), c.size());
+   secure_vector<byte> v = emsa->raw_data();
+   Null_RNG rng;
+   v = emsa->encoding_of(v, max_input_bits(), rng);
+
+   return (v == r);
+   }
+
+BOTAN_REGISTER_PK_SIGNATURE_OP("ECKCDSA", ECKCDSA_Signature_Operation);
+BOTAN_REGISTER_PK_VERIFY_OP("ECKCDSA", ECKCDSA_Verification_Operation);
+
+}
+
+}
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.h b/src/lib/pubkey/eckcdsa/eckcdsa.h
new file mode 100644
index 000000000..b85c4025e
--- /dev/null
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.h
@@ -0,0 +1,91 @@
+/*
+* ECKCDSA (ISO/IEC 14888-3:2006/Cor.2:2009)
+* (C) 2016 René Korthaus, Sirrix AG
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_ECKCDSA_KEY_H__
+#define BOTAN_ECKCDSA_KEY_H__
+
+#include <botan/ecc_key.h>
+
+namespace Botan {
+
+/**
+* This class represents ECKCDSA public keys.
+*/
+class BOTAN_DLL ECKCDSA_PublicKey : public virtual EC_PublicKey
+   {
+   public:
+
+      /**
+      * Construct a public key from a given public point.
+      * @param dom_par the domain parameters associated with this key
+      * @param public_point the public point defining this key
+      */
+      ECKCDSA_PublicKey(const EC_Group& dom_par,
+                      const PointGFp& public_point) :
+         EC_PublicKey(dom_par, public_point) {}
+
+      ECKCDSA_PublicKey(const AlgorithmIdentifier& alg_id,
+                      const secure_vector<byte>& key_bits) :
+         EC_PublicKey(alg_id, key_bits) {}
+
+      /**
+      * Get this keys algorithm name.
+      * @result this keys algorithm name ("ECGDSA")
+      */
+      std::string algo_name() const override { return "ECKCDSA"; }
+
+      /**
+      * Get the maximum number of bits allowed to be fed to this key.
+      * This is the bitlength of the order of the base point.
+      * @result the maximum number of input bits
+      */
+      size_t max_input_bits() const override
+         { return domain().get_order().bits(); }
+
+      size_t message_parts() const override { return 2; }
+
+      size_t message_part_size() const override
+         { return domain().get_order().bytes(); }
+
+   protected:
+      ECKCDSA_PublicKey() {}
+   };
+
+/**
+* This class represents ECKCDSA private keys.
+*/
+class BOTAN_DLL ECKCDSA_PrivateKey : public ECKCDSA_PublicKey,
+                                    public EC_PrivateKey
+   {
+   public:
+
+      /**
+      * Load a private key
+      * @param alg_id the X.509 algorithm identifier
+      * @param key_bits PKCS #8 structure
+      */
+      ECKCDSA_PrivateKey(const AlgorithmIdentifier& alg_id,
+                       const secure_vector<byte>& key_bits) :
+         EC_PrivateKey(alg_id, key_bits, true) {}
+
+      /**
+      * Generate a new private key
+      * @param rng a random number generator
+      * @param domain parameters to used for this key
+      * @param x the private key (if zero, generate a new random key)
+      */
+      ECKCDSA_PrivateKey(RandomNumberGenerator& rng,
+                       const EC_Group& domain,
+                       const BigInt& x = 0) :
+         EC_PrivateKey(rng, domain, x, true) {}
+
+      bool check_key(RandomNumberGenerator& rng, bool) const override;
+   };
+
+}
+
+#endif
diff --git a/src/lib/pubkey/eckcdsa/info.txt b/src/lib/pubkey/eckcdsa/info.txt
new file mode 100644
index 000000000..d3df354b1
--- /dev/null
+++ b/src/lib/pubkey/eckcdsa/info.txt
@@ -0,0 +1,13 @@
+define ECKCDSA 20160413
+
+<requires>
+asn1
+bigint
+ec_group
+ecc_key
+hash
+keypair
+numbertheory
+pk_pad
+rng
+</requires>
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index d2947b0c0..9dbde28af 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -28,6 +28,10 @@
   #include <botan/ecgdsa.h>
 #endif
 
+#if defined(BOTAN_HAS_ECKCDSA)
+  #include <botan/eckcdsa.h>
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
   #include <botan/gost_3410.h>
 #endif
@@ -105,6 +109,11 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
       return new ECGDSA_PublicKey(alg_id, key_bits);
 #endif
 
+#if defined(BOTAN_HAS_ECKCDSA)
+   if(alg_name == "ECKCDSA")
+      return new ECKCDSA_PublicKey(alg_id, key_bits);
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
    if(alg_name == "GOST-34.10")
       return new GOST_3410_PublicKey(alg_id, key_bits);
@@ -176,6 +185,11 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id,
       return new ECGDSA_PrivateKey(alg_id, key_bits);
 #endif
 
+#if defined(BOTAN_HAS_ECKCDSA)
+   if(alg_name == "ECKCDSA")
+      return new ECKCDSA_PrivateKey(alg_id, key_bits);
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
    if(alg_name == "GOST-34.10")
       return new GOST_3410_PrivateKey(alg_id, key_bits);
diff --git a/src/lib/pubkey/pk_ops.cpp b/src/lib/pubkey/pk_ops.cpp
index 654b68255..1017518a7 100644
--- a/src/lib/pubkey/pk_ops.cpp
+++ b/src/lib/pubkey/pk_ops.cpp
@@ -76,9 +76,12 @@ secure_vector<byte> PK_Ops::Key_Agreement_with_KDF::agree(size_t key_len,
    return z;
   }
 
-PK_Ops::Signature_with_EMSA::Signature_with_EMSA(const std::string& emsa)
+PK_Ops::Signature_with_EMSA::Signature_with_EMSA(const std::string& emsa) :
+   Signature(),
+   m_emsa(get_emsa(emsa)),
+   m_hash(hash_for_emsa(emsa)),
+   m_prefix_used(false)
    {
-   m_emsa.reset(get_emsa(emsa));
    if(!m_emsa)
       throw Algorithm_Not_Found(emsa);
    }
@@ -87,19 +90,29 @@ PK_Ops::Signature_with_EMSA::~Signature_with_EMSA() {}
 
 void PK_Ops::Signature_with_EMSA::update(const byte msg[], size_t msg_len)
    {
+   if(has_prefix() && !m_prefix_used)
+      {
+      m_prefix_used = true;
+      secure_vector<byte> prefix = message_prefix();
+      m_emsa->update(prefix.data(), prefix.size());
+      }
    m_emsa->update(msg, msg_len);
    }
 
 secure_vector<byte> PK_Ops::Signature_with_EMSA::sign(RandomNumberGenerator& rng)
    {
+   m_prefix_used = false;
    const secure_vector<byte> msg = m_emsa->raw_data();
    const auto padded = m_emsa->encoding_of(msg, this->max_input_bits(), rng);
    return raw_sign(padded.data(), padded.size(), rng);
    }
 
-PK_Ops::Verification_with_EMSA::Verification_with_EMSA(const std::string& emsa)
+PK_Ops::Verification_with_EMSA::Verification_with_EMSA(const std::string& emsa) :
+   Verification(),
+   m_emsa(get_emsa(emsa)),
+   m_hash(hash_for_emsa(emsa)),
+   m_prefix_used(false)
    {
-   m_emsa.reset(get_emsa(emsa));
    if(!m_emsa)
       throw Algorithm_Not_Found(emsa);
    }
@@ -108,11 +121,18 @@ PK_Ops::Verification_with_EMSA::~Verification_with_EMSA() {}
 
 void PK_Ops::Verification_with_EMSA::update(const byte msg[], size_t msg_len)
    {
+   if(has_prefix() && !m_prefix_used)
+      {
+      m_prefix_used = true;
+      secure_vector<byte> prefix = message_prefix();
+      m_emsa->update(prefix.data(), prefix.size());
+      }
    m_emsa->update(msg, msg_len);
    }
 
 bool PK_Ops::Verification_with_EMSA::is_valid_signature(const byte sig[], size_t sig_len)
    {
+   m_prefix_used = false;
    const secure_vector<byte> msg = m_emsa->raw_data();
 
    if(with_recovery())
diff --git a/src/lib/pubkey/pk_ops_impl.h b/src/lib/pubkey/pk_ops_impl.h
index 81637a81c..9d02de5e5 100644
--- a/src/lib/pubkey/pk_ops_impl.h
+++ b/src/lib/pubkey/pk_ops_impl.h
@@ -58,12 +58,25 @@ class Verification_with_EMSA : public Verification
       bool do_check(const secure_vector<byte>& msg,
                     const byte sig[], size_t sig_len);
 
+      std::string hash_for_signature() { return m_hash; }
    protected:
 
       explicit Verification_with_EMSA(const std::string& emsa);
       ~Verification_with_EMSA();
 
       /**
+      * @return boolean specifying if this signature scheme uses
+      * a message prefix returned by message_prefix()
+      */
+      virtual bool has_prefix() { return false; }
+
+      /**
+      * @return the message prefix if this signature scheme uses
+      * a message prefix, signaled via has_prefix()
+      */
+      virtual secure_vector<byte> message_prefix() const { throw Exception( "No prefix" ); }
+
+      /**
       * @return boolean specifying if this key type supports message
       * recovery and thus if you need to call verify() or verify_mr()
       */
@@ -95,8 +108,11 @@ class Verification_with_EMSA : public Verification
          throw Invalid_State("Message recovery not supported");
          }
 
-   private:
       std::unique_ptr<EMSA> m_emsa;
+
+   private:
+      const std::string m_hash;
+      bool m_prefix_used;
    };
 
 class Signature_with_EMSA : public Signature
@@ -108,6 +124,22 @@ class Signature_with_EMSA : public Signature
    protected:
       explicit Signature_with_EMSA(const std::string& emsa);
       ~Signature_with_EMSA();
+
+      std::string hash_for_signature() { return m_hash; }
+
+      /**
+      * @return boolean specifying if this signature scheme uses
+      * a message prefix returned by message_prefix()
+      */
+      virtual bool has_prefix() { return false; }
+
+      /**
+      * @return the message prefix if this signature scheme uses
+      * a message prefix, signaled via has_prefix()
+      */
+      virtual secure_vector<byte> message_prefix() const { throw Exception( "No prefix" ); }
+
+      std::unique_ptr<EMSA> m_emsa;
    private:
 
       /**
@@ -122,7 +154,8 @@ class Signature_with_EMSA : public Signature
       virtual secure_vector<byte> raw_sign(const byte msg[], size_t msg_len,
                                            RandomNumberGenerator& rng) = 0;
 
-      std::unique_ptr<EMSA> m_emsa;
+      const std::string m_hash;
+      bool m_prefix_used;
    };
 
 class Key_Agreement_with_KDF : public Key_Agreement
diff --git a/src/lib/pubkey/rfc6979/rfc6979.cpp b/src/lib/pubkey/rfc6979/rfc6979.cpp
index f749b039f..0b26aadb5 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.cpp
+++ b/src/lib/pubkey/rfc6979/rfc6979.cpp
@@ -8,23 +8,9 @@
 #include <botan/rfc6979.h>
 #include <botan/hmac_drbg.h>
 #include <botan/mac.h>
-#include <botan/scan_name.h>
 
 namespace Botan {
 
-std::string hash_for_deterministic_signature(const std::string& emsa)
-   {
-   SCAN_Name emsa_name(emsa);
-
-   if(emsa_name.arg_count() > 0)
-      {
-      const std::string pos_hash = emsa_name.arg(0);
-      return pos_hash;
-      }
-
-   return "SHA-512"; // safe default if nothing we understand
-   }
-
 RFC6979_Nonce_Generator::RFC6979_Nonce_Generator(const std::string& hash,
                                                  const BigInt& order,
                                                  const BigInt& x) :
diff --git a/src/lib/pubkey/rfc6979/rfc6979.h b/src/lib/pubkey/rfc6979/rfc6979.h
index 5b3dee8ef..32728befb 100644
--- a/src/lib/pubkey/rfc6979/rfc6979.h
+++ b/src/lib/pubkey/rfc6979/rfc6979.h
@@ -46,8 +46,6 @@ BigInt BOTAN_DLL generate_rfc6979_nonce(const BigInt& x,
                                         const BigInt& h,
                                         const std::string& hash);
 
-std::string hash_for_deterministic_signature(const std::string& emsa);
-
 }
 
 #endif
diff --git a/src/tests/data/pubkey/eckcdsa.vec b/src/tests/data/pubkey/eckcdsa.vec
new file mode 100644
index 000000000..d9bd659e2
--- /dev/null
+++ b/src/tests/data/pubkey/eckcdsa.vec
@@ -0,0 +1,29 @@
+
+# Taken from Korean TTA Standard TTAK.KO-12.0015/R2
+# "Digital Signature Mechanism with Appendix - Part 3: Korean Certificate-based Digitial Signature Algorithm using Elliptic Curves (EC-KCDSA)"
+# http://www.tta.or.kr/include/Download.jsp?filename=stnfile/TTAK.KO-12.0015_R2.pdf
+
+Group = secp224r1
+X = 0x562A6F64E162FFCB51CD4707774AE36681B6CEF205FE5D43912956A2
+
+Msg = 5468697320697320612073616D706C65206D65737361676520666F722045432D4B4344534120696D706C656D656E746174696F6E2076616C69646174696F6E2E
+Hash = SHA-224
+Nonce = 76A0AFC18646D1B620A079FB223865A7BCB447F3C03A35D878EA4CDA
+Signature = EEA58C91E0CDCEB5799B00D2412D928FDD23122A1C2BDF43C2F8DAFAAEBAB53C7A44A8B22F35FDB9DE265F23B89F65A69A8B7BD4061911A6
+
+Group = secp256r1
+X = 0x9051A275AA4D98439EDDED13FA1C6CBBCCE775D8CC9433DEE69C59848B3594DF
+
+Hash = SHA-256
+Nonce = 71B88F398916DA9C90F555F1B5732B7DC636B49C638150BAC11BF05CFE16596A
+Signature = 0EDDF680601266EE1DA83E55A6D9445FC781DAEB14C765E7E5D0CDBAF1F14A689B333457661C7CF741BDDBC0835553DFBB37EE74F53DB699E0A17780C7B6F1D0
+
+# Taken from ISO/IEC 14888-3:2006, with corrections from ISO/IEC 14888-3:2006/Cor.2:2009
+
+Group = secp192r1
+X = 0x444811A323E03C28A34CD859EE2FF1A34D1AAF3CB0B5603B
+
+Msg = 616263
+Hash = SHA-1
+Nonce = 4B19A0725424CD3310B02D8C8416C98D64C618BFE935597D
+Signature = 3CA29800D425FCAA51CCB209B4ED5D6C352108223143B2EA5A0E8644CE8F768A6FA4D193C726AD08019788E5
\ No newline at end of file
diff --git a/src/tests/test_eckcdsa.cpp b/src/tests/test_eckcdsa.cpp
new file mode 100644
index 000000000..96c28383a
--- /dev/null
+++ b/src/tests/test_eckcdsa.cpp
@@ -0,0 +1,77 @@
+/*
+* (C) 2016 René Korthaus, Sirrix AG
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "tests.h"
+
+#include "test_rng.h"
+
+#if defined(BOTAN_HAS_ECKCDSA)
+  #include "test_pubkey.h"
+  #include <botan/eckcdsa.h>
+  #include <botan/oids.h>
+#endif
+
+namespace Botan_Tests {
+
+namespace {
+
+#if defined(BOTAN_HAS_ECKCDSA)
+
+class ECKCDSA_Signature_KAT_Tests : public PK_Signature_Generation_Test
+   {
+   public:
+      ECKCDSA_Signature_KAT_Tests() : PK_Signature_Generation_Test(
+         "ECKCDSA",
+         "pubkey/eckcdsa.vec",
+         {"Group", "X", "Hash", "Msg", "Nonce", "Signature"})
+         {}
+
+      bool clear_between_callbacks() const override { return false; }
+
+      std::unique_ptr<Botan::Private_Key> load_private_key(const VarMap& vars) override
+         {
+         const std::string group_id = get_req_str(vars, "Group");
+         const BigInt x = get_req_bn(vars, "X");
+         Botan::EC_Group group(Botan::OIDS::lookup(group_id));
+
+         std::unique_ptr<Botan::Private_Key> key(new Botan::ECKCDSA_PrivateKey(Test::rng(), group, x));
+         return key;
+         }
+
+      std::string default_padding(const VarMap& vars) const override
+         {
+         return "EMSA1(" + get_req_str(vars, "Hash") + ")";
+         }
+
+      Botan::RandomNumberGenerator* test_rng(const std::vector<uint8_t>& nonce) const override
+         {
+         // eckcdsa signature generation extracts more random than just the nonce,
+         // but the nonce is extracted first
+         return new Fixed_Output_Position_RNG(nonce, 1);
+         }
+   };
+
+class ECKCDSA_Keygen_Tests : public PK_Key_Generation_Test
+   {
+   public:
+      std::vector<std::string> keygen_params() const override { return { "secp256r1", "secp384r1", "secp521r1" }; }
+
+      std::unique_ptr<Botan::Private_Key> make_key(Botan::RandomNumberGenerator& rng,
+                                                   const std::string& param) const override
+         {
+         Botan::EC_Group group(param);
+         return std::unique_ptr<Botan::Private_Key>(new Botan::ECKCDSA_PrivateKey(rng, group));
+         }
+   };
+
+BOTAN_REGISTER_TEST("eckcdsa", ECKCDSA_Signature_KAT_Tests);
+BOTAN_REGISTER_TEST("eckcdsa_keygen", ECKCDSA_Keygen_Tests);
+
+#endif
+
+}
+
+}