Merge GH #479 Add ECGDSA signature scheme

16 files changed, 615 insertions, 14 deletions

diff --git a/src/build-data/policy/bsi.txt b/src/build-data/policy/bsi.txt
index f66dda215..b8d47a5fd 100644
--- a/src/build-data/policy/bsi.txt
+++ b/src/build-data/policy/bsi.txt
@@ -30,6 +30,7 @@ dh
 rsa
 dsa
 ecdsa
+ecgdsa
 ecdh
 
 # rng
diff --git a/src/lib/asn1/oid_lookup/default.cpp b/src/lib/asn1/oid_lookup/default.cpp
index fe7a42748..9e16cfc0b 100644
--- a/src/lib/asn1/oid_lookup/default.cpp
+++ b/src/lib/asn1/oid_lookup/default.cpp
@@ -30,6 +30,9 @@ const char* default_oid_list()
       "1.2.840.10045.2.1 = ECDSA" "\n"
       "1.3.132.1.12 = ECDH" "\n"
 
+      // ecgPublicKey (see https://www.teletrust.de/projekte/oid/)
+      "1.3.36.3.3.2.5.2.1 = ECGDSA" "\n"
+
       "1.2.643.2.2.19 = GOST-34.10" "\n"
 
       // Block ciphers
@@ -112,6 +115,13 @@ const char* default_oid_list()
       "1.2.840.10045.4.3.3 = ECDSA/EMSA1(SHA-384)" "\n"
       "1.2.840.10045.4.3.4 = ECDSA/EMSA1(SHA-512)" "\n"
 
+      "1.3.36.3.3.2.5.4.1 = ECGDSA/EMSA1(RIPEMD-160)" "\n"
+      "1.3.36.3.3.2.5.4.2 = ECGDSA/EMSA1(SHA-160)" "\n"
+      "1.3.36.3.3.2.5.4.3 = ECGDSA/EMSA1(SHA-224)" "\n"
+      "1.3.36.3.3.2.5.4.4 = ECGDSA/EMSA1(SHA-256)" "\n"
+      "1.3.36.3.3.2.5.4.5 = ECGDSA/EMSA1(SHA-384)" "\n"
+      "1.3.36.3.3.2.5.4.6 = ECGDSA/EMSA1(SHA-512)" "\n"
+
       "1.2.643.2.2.3 = GOST-34.10/EMSA1(GOST-R-34.11-94)" "\n"
 
       "1.3.6.1.4.1.25258.2.1.1.1 = RW/EMSA2(RIPEMD-160)" "\n"
diff --git a/src/lib/math/numbertheory/mp_numth.cpp b/src/lib/math/numbertheory/mp_numth.cpp
index 6eb938286..3373b9ee7 100644
--- a/src/lib/math/numbertheory/mp_numth.cpp
+++ b/src/lib/math/numbertheory/mp_numth.cpp
@@ -71,4 +71,18 @@ BigInt sub_mul(const BigInt& a, const BigInt& b, const BigInt& c)
    return r;
    }
 
+/*
+* Multiply-Subtract Operation
+*/
+BigInt mul_sub(const BigInt& a, const BigInt& b, const BigInt& c)
+   {
+   if(c.is_negative() || c.is_zero())
+      throw Invalid_Argument("mul_sub: Third argument must be > 0");
+
+   BigInt r = a;
+   r *= b;
+   r -= c;
+   return r;
+   }
+
 }
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index e1e6c65f6..591b61f6a 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -37,6 +37,17 @@ BigInt BOTAN_DLL sub_mul(const BigInt& a,
                          const BigInt& c);
 
 /**
+* Fused multiply-subtract
+* @param a an integer
+* @param b an integer
+* @param c an integer
+* @return (a*b)-c
+*/
+BigInt BOTAN_DLL mul_sub(const BigInt& a,
+                         const BigInt& b,
+                         const BigInt& c);
+
+/**
 * Return the absolute value
 * @param n an integer
 * @return absolute value of n
diff --git a/src/lib/pubkey/ecc_key/ecc_key.cpp b/src/lib/pubkey/ecc_key/ecc_key.cpp
index 2dca20725..befc2cc4c 100644
--- a/src/lib/pubkey/ecc_key/ecc_key.cpp
+++ b/src/lib/pubkey/ecc_key/ecc_key.cpp
@@ -33,7 +33,10 @@ EC_PublicKey::EC_PublicKey(const EC_Group& dom_par,
    }
 
 EC_PublicKey::EC_PublicKey(const AlgorithmIdentifier& alg_id,
-                           const secure_vector<byte>& key_bits) : m_domain_params{EC_Group(alg_id.parameters)}, m_public_key{OS2ECP(key_bits, domain().get_curve())}, m_domain_encoding{EC_DOMPAR_ENC_EXPLICIT}
+                           const secure_vector<byte>& key_bits) :
+   m_domain_params{EC_Group(alg_id.parameters)},
+   m_public_key{OS2ECP(key_bits, domain().get_curve())},
+   m_domain_encoding{EC_DOMPAR_ENC_EXPLICIT}
    {}
 
 bool EC_PublicKey::check_key(RandomNumberGenerator&,
@@ -80,17 +83,23 @@ const BigInt& EC_PrivateKey::private_value() const
 */
 EC_PrivateKey::EC_PrivateKey(RandomNumberGenerator& rng,
                              const EC_Group& ec_group,
-                             const BigInt& x)
+                             const BigInt& x,
+                             bool with_modular_inverse)
    {
    m_domain_params = ec_group;
    m_domain_encoding = EC_DOMPAR_ENC_EXPLICIT;
 
    if(x == 0)
+      {
       m_private_key = BigInt::random_integer(rng, 1, domain().get_order());
+      }
    else
+      {
       m_private_key = x;
+      }
 
-   m_public_key = domain().get_base_point() * m_private_key;
+   m_public_key = domain().get_base_point() *
+                  ((with_modular_inverse) ? inverse_mod(m_private_key, m_domain_params.get_order()) : m_private_key);
 
    BOTAN_ASSERT(m_public_key.on_the_curve(),
                 "Generated public key point was on the curve");
@@ -108,7 +117,8 @@ secure_vector<byte> EC_PrivateKey::pkcs8_private_key() const
    }
 
 EC_PrivateKey::EC_PrivateKey(const AlgorithmIdentifier& alg_id,
-                             const secure_vector<byte>& key_bits)
+                             const secure_vector<byte>& key_bits,
+                             bool with_modular_inverse)
    {
    m_domain_params = EC_Group(alg_id.parameters);
    m_domain_encoding = EC_DOMPAR_ENC_EXPLICIT;
@@ -129,7 +139,8 @@ EC_PrivateKey::EC_PrivateKey(const AlgorithmIdentifier& alg_id,
 
    if(public_key_bits.empty())
       {
-      m_public_key = domain().get_base_point() * m_private_key;
+      m_public_key = domain().get_base_point() *
+                     ((with_modular_inverse) ? inverse_mod(m_private_key, m_domain_params.get_order()) : m_private_key);
 
       BOTAN_ASSERT(m_public_key.on_the_curve(),
                    "Public point derived from loaded key was on the curve");
diff --git a/src/lib/pubkey/ecc_key/ecc_key.h b/src/lib/pubkey/ecc_key/ecc_key.h
index 3f93a908c..a8e77b895 100644
--- a/src/lib/pubkey/ecc_key/ecc_key.h
+++ b/src/lib/pubkey/ecc_key/ecc_key.h
@@ -96,12 +96,30 @@ class BOTAN_DLL EC_PrivateKey : public virtual EC_PublicKey,
                                 public virtual Private_Key
    {
    public:
-     EC_PrivateKey(RandomNumberGenerator& rng,
-                   const EC_Group& domain,
-                   const BigInt& private_key);
-
+      /*
+      * If x=0, creates a new private key in the domain
+      * using the given rng. If with_modular_inverse is set,
+      * the public key will be calculated by multiplying
+      * the base point with the modular inverse of
+      * x (as in ECGDSA and ECKCDSA), otherwise by
+      * multiplying directly with x (as in ECDSA).
+      */
+      EC_PrivateKey(RandomNumberGenerator& rng,
+                    const EC_Group& domain,
+                    const BigInt& x,
+                    bool with_modular_inverse=false);
+
+      /*
+      * Creates a new private key object from the given
+      * key_bits. If with_modular_inverse is set,
+      * the public key will be calculated by multiplying
+      * the base point with the modular inverse of
+      * x (as in ECGDSA and ECKCDSA), otherwise by
+      * multiplying directly with x (as in ECDSA).
+      */
       EC_PrivateKey(const AlgorithmIdentifier& alg_id,
-                    const secure_vector<byte>& key_bits);
+                    const secure_vector<byte>& key_bits,
+                    bool with_modular_inverse=false);
 
       secure_vector<byte> pkcs8_private_key() const override;
 
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index 1eb41a4b9..eed09afe6 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -78,7 +78,7 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
       * 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 ney random key)
+      * @param x the private key (if zero, generate a new random key)
       */
       ECDSA_PrivateKey(RandomNumberGenerator& rng,
                        const EC_Group& domain,
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
new file mode 100644
index 000000000..b28e3fe96
--- /dev/null
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -0,0 +1,148 @@
+/*
+* ECGDSA (BSI-TR-03111, version 2.0)
+* (C) 2016 René Korthaus
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/pk_utils.h>
+#include <botan/ecgdsa.h>
+#include <botan/keypair.h>
+
+namespace Botan {
+
+bool ECGDSA_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 {
+
+/**
+* ECGDSA signature operation
+*/
+class ECGDSA_Signature_Operation : public PK_Ops::Signature_with_EMSA
+   {
+   public:
+      typedef ECGDSA_PrivateKey Key_Type;
+
+      ECGDSA_Signature_Operation(const ECGDSA_PrivateKey& ecgdsa,
+                                const std::string& emsa) :
+         PK_Ops::Signature_with_EMSA(emsa),
+         m_order(ecgdsa.domain().get_order()),
+         m_base_point(ecgdsa.domain().get_base_point(), m_order),
+         m_x(ecgdsa.private_value()),
+         m_mod_order(m_order)
+         {
+         }
+
+      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(); }
+
+   private:
+      const BigInt& m_order;
+      Blinded_Point_Multiply m_base_point;
+      const BigInt& m_x;
+      Modular_Reducer m_mod_order;
+   };
+
+secure_vector<byte>
+ECGDSA_Signature_Operation::raw_sign(const byte msg[], size_t msg_len,
+                                     RandomNumberGenerator& rng)
+   {
+   const BigInt m(msg, msg_len);
+
+   BigInt k = BigInt::random_integer(rng, 1, m_order);
+
+   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
+   const BigInt s = m_mod_order.multiply(m_x, mul_sub(k, r, m));
+
+   // With overwhelming probability, a bug rather than actual zero r/s
+   BOTAN_ASSERT(s != 0, "invalid s");
+   BOTAN_ASSERT(r != 0, "invalid r");
+
+   secure_vector<byte> output(2*m_order.bytes());
+   r.binary_encode(&output[output.size() / 2 - r.bytes()]);
+   s.binary_encode(&output[output.size() - s.bytes()]);
+   return output;
+   }
+
+/**
+* ECGDSA verification operation
+*/
+class ECGDSA_Verification_Operation : public PK_Ops::Verification_with_EMSA
+   {
+   public:
+      typedef ECGDSA_PublicKey Key_Type;
+
+      ECGDSA_Verification_Operation(const ECGDSA_PublicKey& ecgdsa,
+                                   const std::string& emsa) :
+         PK_Ops::Verification_with_EMSA(emsa),
+         m_base_point(ecgdsa.domain().get_base_point()),
+         m_public_point(ecgdsa.public_point()),
+         m_order(ecgdsa.domain().get_order()),
+         m_mod_order(m_order)
+         {
+         }
+
+      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;
+   };
+
+bool ECGDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
+                                           const byte sig[], size_t sig_len)
+   {
+   if(sig_len != m_order.bytes()*2)
+      return false;
+
+   BigInt e(msg, msg_len);
+
+   BigInt r(sig, sig_len / 2);
+   BigInt s(sig + sig_len / 2, sig_len / 2);
+
+   if(r <= 0 || r >= m_order || s <= 0 || s >= m_order)
+      return false;
+
+   BigInt w = inverse_mod(r, m_order);
+
+   const BigInt u1 = m_mod_order.reduce(e * w);
+   const BigInt u2 = m_mod_order.reduce(s * w);
+   const PointGFp R = multi_exponentiate(m_base_point, u1, m_public_point, u2);
+
+   if(R.is_zero())
+      return false;
+
+   const BigInt v = m_mod_order.reduce(R.get_affine_x());
+   return (v == r);
+   }
+
+BOTAN_REGISTER_PK_SIGNATURE_OP("ECGDSA", ECGDSA_Signature_Operation);
+BOTAN_REGISTER_PK_VERIFY_OP("ECGDSA", ECGDSA_Verification_Operation);
+
+}
+
+}
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.h b/src/lib/pubkey/ecgdsa/ecgdsa.h
new file mode 100644
index 000000000..518adeeab
--- /dev/null
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.h
@@ -0,0 +1,91 @@
+/*
+* ECGDSA (BSI-TR-03111, version 2.0)
+* (C) 2016 René Korthaus
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_ECGDSA_KEY_H__
+#define BOTAN_ECGDSA_KEY_H__
+
+#include <botan/ecc_key.h>
+
+namespace Botan {
+
+/**
+* This class represents ECGDSA public keys.
+*/
+class BOTAN_DLL ECGDSA_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
+      */
+      ECGDSA_PublicKey(const EC_Group& dom_par,
+                      const PointGFp& public_point) :
+         EC_PublicKey(dom_par, public_point) {}
+
+      ECGDSA_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 "ECGDSA"; }
+
+      /**
+      * 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:
+      ECGDSA_PublicKey() {}
+   };
+
+/**
+* This class represents ECGDSA private keys.
+*/
+class BOTAN_DLL ECGDSA_PrivateKey : public ECGDSA_PublicKey,
+                                    public EC_PrivateKey
+   {
+   public:
+
+      /**
+      * Load a private key
+      * @param alg_id the X.509 algorithm identifier
+      * @param key_bits PKCS #8 structure
+      */
+      ECGDSA_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)
+      */
+      ECGDSA_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/ecgdsa/info.txt b/src/lib/pubkey/ecgdsa/info.txt
new file mode 100644
index 000000000..6c18a1440
--- /dev/null
+++ b/src/lib/pubkey/ecgdsa/info.txt
@@ -0,0 +1,11 @@
+define ECGDSA 20160301
+
+<requires>
+asn1
+bigint
+ec_group
+ecc_key
+keypair
+numbertheory
+rng
+</requires>
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index 689237a84..d2947b0c0 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -24,6 +24,10 @@
   #include <botan/ecdsa.h>
 #endif
 
+#if defined(BOTAN_HAS_ECGDSA)
+  #include <botan/ecgdsa.h>
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
   #include <botan/gost_3410.h>
 #endif
@@ -96,6 +100,11 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
       return new ECDSA_PublicKey(alg_id, key_bits);
 #endif
 
+#if defined(BOTAN_HAS_ECGDSA)
+   if(alg_name == "ECGDSA")
+      return new ECGDSA_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);
@@ -162,6 +171,11 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id,
       return new ECDSA_PrivateKey(alg_id, key_bits);
 #endif
 
+#if defined(BOTAN_HAS_ECGDSA)
+   if(alg_name == "ECGDSA")
+      return new ECGDSA_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/tests/data/pubkey/ecgdsa.vec b/src/tests/data/pubkey/ecgdsa.vec
new file mode 100644
index 000000000..5f3a7b55c
--- /dev/null
+++ b/src/tests/data/pubkey/ecgdsa.vec
@@ -0,0 +1,98 @@
+
+# The Digital Signature Scheme ECGDSA, Erwin Hess, Marcus Schafheutle, and Pascale Serf, Siemens AG, October 24, 2006
+# https://www.teletrust.de/fileadmin/files/oid/ecgdsa_final.pdf
+
+# 2.4.1 ECGDSA over GF(p) with RIPEMD-160
+
+Group = brainpool192r1
+X = 0x80F2425E89B4F585F27F3536ED834D68E3E492DE08FE84B9
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e20524950454d442d313630
+Hash = RIPEMD-160
+Nonce = 22C17C2A367DD85AB8A365ED06F19C43F9ED18349A9BC044
+Signature = 2D017BE7F117FF994ED6FC63CA5B4C7A0430E9FA095DAFC4C02B5CC5C51D5411060BF0245049F824839F671D78A1BBF1
+
+Group = brainpool256r1
+X = 0x47B3A27862DEF03749ACF0D600E69F9B851D01EDAEFA531F4D168E787307F4D8
+Nonce = 908E3099776261A4558FF7A9FA6DFFE0CA6BB3F9CB35C2E4E1DC73FD5E8C08A3
+Signature = 62CCD1D291E62F6A4FFBD966C66C85AABA990BB6AB0C087DBD54A456CCC84E4C9119719B08EEA0D6BC56E4D1D37369BCF3768445EF65CAE4A37BF6D43BD01646
+
+Group = brainpool320r1
+X = 0x486835945A3A284FFC52629AD48D8F37F4B2E9939C52BC72362A996140192AEF7D2AAFF0C73A51C5
+Nonce = C70BC00A77AD78725D36CEEC27D6F956FB546EEF6DC90E3531452BD87ECE8A4A7AD730ADC299D81B
+Signature = 3C925969FAB22F7AE7B8CC5D50CB0867DFDB2CF4FADA3D490DF75D72F7563186419494C98F9C82A606AB5250B31A8E935619489461733200E4FD5C1275C0AB37E7E411495BAAE14541DF6DE666B8CA56
+
+
+# 2.4.2 ECGDSA over GF(p) with SHA-1
+
+Group = brainpool192r1
+X = 0x80F2425E89B4F585F27F3536ED834D68E3E492DE08FE84B9
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e205348412d31
+Hash = SHA-1
+Nonce = 22C17C2A367DD85AB8A365ED06F19C43F9ED18349A9BC044
+Signature = 2D017BE7F117FF994ED6FC63CA5B4C7A0430E9FA095DAFC418FD604E5F00F55B3585C0528C319A2B05B8F2DDEE9CF1A6
+
+
+# 2.4.3 ECGDSA over GF(p) with SHA-224
+
+Group = brainpool256r1
+X = 0x47B3A27862DEF03749ACF0D600E69F9B851D01EDAEFA531F4D168E787307F4D8
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e205348412d323234
+Hash = SHA-224
+Nonce = 908E3099776261A4558FF7A9FA6DFFE0CA6BB3F9CB35C2E4E1DC73FD5E8C08A3
+Signature = 62CCD1D291E62F6A4FFBD966C66C85AABA990BB6AB0C087DBD54A456CCC84E4C6F029D921CBD25526EDCCF1C45E3CBF7B7A5D8D4E005F0C41C49B052DECB04EA
+
+Group = brainpool320r1
+X = 0x486835945A3A284FFC52629AD48D8F37F4B2E9939C52BC72362A996140192AEF7D2AAFF0C73A51C5
+Nonce = C70BC00A77AD78725D36CEEC27D6F956FB546EEF6DC90E3531452BD87ECE8A4A7AD730ADC299D81B
+Signature = 3C925969FAB22F7AE7B8CC5D50CB0867DFDB2CF4FADA3D490DF75D72F7563186419494C98F9C82A66EA191CA0D468AC3E95687689338357C7D0BACB3F1D87E0DEC05F635B7ADB84275AA008660F812CF
+
+
+# 2.4.4 ECGDSA over GF(p) with SHA-256
+
+Group = brainpool256r1
+X = 0x47B3A27862DEF03749ACF0D600E69F9B851D01EDAEFA531F4D168E787307F4D8
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e205348412d323536
+Hash = SHA-256
+Nonce = 908E3099776261A4558FF7A9FA6DFFE0CA6BB3F9CB35C2E4E1DC73FD5E8C08A3
+Signature = 62CCD1D291E62F6A4FFBD966C66C85AABA990BB6AB0C087DBD54A456CCC84E4C1DD53F822F8BE769F601FC5826B10AB603898374B8501B53D6976BA1AAE17A45
+
+Group = brainpool320r1
+X = 0x486835945A3A284FFC52629AD48D8F37F4B2E9939C52BC72362A996140192AEF7D2AAFF0C73A51C5
+Nonce = C70BC00A77AD78725D36CEEC27D6F956FB546EEF6DC90E3531452BD87ECE8A4A7AD730ADC299D81B
+Signature = 3C925969FAB22F7AE7B8CC5D50CB0867DFDB2CF4FADA3D490DF75D72F7563186419494C98F9C82A624370797A9D11717BBBB2B762E08ECD07DD7E033F544E47CBF3C6D16FD90B51DCC2E4DD8E6ECD8CD
+
+Group = brainpool384r1
+X = 0x60BABEC49D0A4E36328879591B1A598F339F7971E8A1AD35788486EB081C838B5612F6DEBD6B38A0BA720BD857AB2354
+Nonce = 43E01A2A95EE7695955334410F32C73BD1394BBF2CD7B8A18656B447A951342C82F52E833FFB3B74612679437C13ACB5
+Signature = 2A2676EFF87A75EE9ECBA1FDD7A5437697294166063C8CD90F8AEBA399BF450FFA244C0EE69B3E1FFCA395CD27AFFC6156F6A18906455867EB51EBE46049A11D79AEED1500D1D1A43D876E422C9234ED6F59AB7D336BCE12CED3D7ECBC09CAE3
+
+
+# 2.4.5 ECGDSA over GF(p) with SHA-384
+
+Group = brainpool384r1
+X = 0x60BABEC49D0A4E36328879591B1A598F339F7971E8A1AD35788486EB081C838B5612F6DEBD6B38A0BA720BD857AB2354
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e205348412d333834
+Hash = SHA-384
+Nonce = 43E01A2A95EE7695955334410F32C73BD1394BBF2CD7B8A18656B447A951342C82F52E833FFB3B74612679437C13ACB5
+Signature = 2A2676EFF87A75EE9ECBA1FDD7A5437697294166063C8CD90F8AEBA399BF450FFA244C0EE69B3E1FFCA395CD27AFFC61733F4E370AF3F9A2DF9499F9953E091D7BD28CA8E80FB3B4AAEB1FF324CCDF6E4D7F6B4576071321D8B34C20CAF0CD01
+
+Group = brainpool512r1
+X = 0x92006A988AF96D9157AADCF8627169627CE2ECC4C58ECE5C1A0A864211AB764C04236FA0160857A78E71CCAE4D79D52E5A69A4578AF506581F598FA9B4F7DA68
+Nonce = 6942B01D5901BEC1506BB8749618E22EC0FCD7F35159D51ED53BA77A78752128A58232AD8E0E021AFDE1477FF4C74FDFFE88AE2D15D89B56F6D73C0377631D2B
+Signature = 0104918B2B32B1A549BD43C30092953B4164CA01A1A97B5B0756EA063AC16B41B88A1BAB4538CD7D8466180B3E3F5C8646AC4A45F564E9B68FEE72ED00C7AC483D233E9FD9EB152E889F4F7CF325B4640894E5EA44C5144354305CD4BF70D2348257C2DBE06C554492CE9FDD6861A56577B53E5EE80E606231A4CF068FA1EC21
+
+
+# 2.4.5 ECGDSA over GF(p) with SHA-512
+
+Group = brainpool512r1
+X = 0x92006A988AF96D9157AADCF8627169627CE2ECC4C58ECE5C1A0A864211AB764C04236FA0160857A78E71CCAE4D79D52E5A69A4578AF506581F598FA9B4F7DA68
+
+Msg = 4578616d706c65206f662045434744534120776974682074686520686173682066756e6374696f6e205348412d353132
+Hash = SHA-512
+Nonce = 6942B01D5901BEC1506BB8749618E22EC0FCD7F35159D51ED53BA77A78752128A58232AD8E0E021AFDE1477FF4C74FDFFE88AE2D15D89B56F6D73C0377631D2B
+Signature = 0104918B2B32B1A549BD43C30092953B4164CA01A1A97B5B0756EA063AC16B41B88A1BAB4538CD7D8466180B3E3F5C8646AC4A45F564E9B68FEE72ED00C7AC4817A011F8DD7B56652B27AA6D6E7BDF3C7C23B5FA32910FBAA107E6270E1CA8A7A263F6618E6098A0D6CD6BA1C03544C5425875ECB3418AF5A3EE3F32143E48D2
diff --git a/src/tests/test_ecgdsa.cpp b/src/tests/test_ecgdsa.cpp
new file mode 100644
index 000000000..7fbdaccc5
--- /dev/null
+++ b/src/tests/test_ecgdsa.cpp
@@ -0,0 +1,78 @@
+/*
+* (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_ECGDSA)
+  #include "test_pubkey.h"
+  #include <botan/ecgdsa.h>
+  #include <botan/oids.h>
+#endif
+
+namespace Botan_Tests {
+
+namespace {
+
+#if defined(BOTAN_HAS_ECGDSA)
+
+class ECGDSA_Signature_KAT_Tests : public PK_Signature_Generation_Test
+   {
+   public:
+      ECGDSA_Signature_KAT_Tests() : PK_Signature_Generation_Test(
+         "ECGDSA",
+         "pubkey/ecgdsa.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::ECGDSA_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
+         {
+         // ecgdsa signature generation extracts more random than just the nonce,
+         // but the nonce is extracted first
+         return new Fixed_Output_Position_RNG(nonce, 1);
+         }
+   };
+
+class ECGDSA_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);
+         std::unique_ptr<Botan::Private_Key> key(new Botan::ECGDSA_PrivateKey(rng, group));
+         return key;
+         }
+   };
+
+BOTAN_REGISTER_TEST("ecgdsa", ECGDSA_Signature_KAT_Tests);
+BOTAN_REGISTER_TEST("ecgdsa_keygen", ECGDSA_Keygen_Tests);
+
+#endif
+
+}
+
+}
diff --git a/src/tests/test_pubkey.cpp b/src/tests/test_pubkey.cpp
index 4d795ae1d..2f6de639d 100644
--- a/src/tests/test_pubkey.cpp
+++ b/src/tests/test_pubkey.cpp
@@ -113,7 +113,7 @@ PK_Signature_Generation_Test::run_one_test(const std::string&, const VarMap& var
       std::unique_ptr<Botan::RandomNumberGenerator> rng;
       if(vars.count("Nonce"))
          {
-         rng.reset(new Fixed_Output_RNG(get_req_bin(vars, "Nonce")));
+         rng.reset(test_rng(get_req_bin(vars, "Nonce")));
          }
 
       const std::vector<uint8_t> generated_signature =
diff --git a/src/tests/test_pubkey.h b/src/tests/test_pubkey.h
index 086c0bea1..b5a79bf55 100644
--- a/src/tests/test_pubkey.h
+++ b/src/tests/test_pubkey.h
@@ -9,6 +9,8 @@
 
 #include "tests.h"
 
+#include "test_rng.h"
+
 #if defined(BOTAN_HAS_PUBLIC_KEY_CRYPTO)
 
 #include <botan/pubkey.h>
@@ -30,6 +32,12 @@ class PK_Signature_Generation_Test : public Text_Based_Test
          }
 
       virtual std::unique_ptr<Botan::Private_Key> load_private_key(const VarMap& vars) = 0;
+
+      virtual Botan::RandomNumberGenerator* test_rng(const std::vector<uint8_t>& nonce) const
+         {
+            return new Fixed_Output_RNG(nonce);
+         }
+
    private:
       Test::Result run_one_test(const std::string&, const VarMap& vars) override;
    };
diff --git a/src/tests/test_rng.h b/src/tests/test_rng.h
index f7b0bf6fe..c14ed7fb7 100644
--- a/src/tests/test_rng.h
+++ b/src/tests/test_rng.h
@@ -1,5 +1,6 @@
 /*
 * (C) 2009 Jack Lloyd
+* (C) 2016 René Korthaus, Sirrix AG
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -12,15 +13,27 @@
 #include <string>
 #include <botan/rng.h>
 #include <botan/hex.h>
+#include <botan/exceptn.h>
+
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+  #include <botan/system_rng.h>
+#else
+  #include <botan/auto_rng.h>
+#endif
+
 
 namespace Botan_Tests {
 
+/**
+ * RNG that outputs only a given set of fixed bytes, throws otherwise.
+ * Useful for test vectors with fixed nonces, where the algorithm consumes only the fixed nonce.
+ */
 class Fixed_Output_RNG : public Botan::RandomNumberGenerator
    {
    public:
       bool is_seeded() const override { return !m_buf.empty(); }
 
-      uint8_t random()
+      virtual uint8_t random()
          {
          if(!is_seeded())
             throw Test_Error("Fixed output RNG ran out of bytes, test bug?");
@@ -63,10 +76,85 @@ class Fixed_Output_RNG : public Botan::RandomNumberGenerator
       Fixed_Output_RNG() {}
    protected:
       size_t remaining() const { return m_buf.size(); }
-   private:
+
       std::deque<uint8_t> m_buf;
    };
 
+/**
+ * RNG that outputs a given set of fixed bytes for a specific request count, outputs random otherwise.
+ * Useful for test vectors with fixed nonces, where the algorithm consumes more random than just the fixed nonce.
+ */
+class Fixed_Output_Position_RNG : public Fixed_Output_RNG
+   {
+   public:
+      bool is_seeded() const override { return !m_buf.empty() || m_rng->is_seeded(); }
+
+      uint8_t random() override
+         {
+         if(m_buf.empty())
+            {
+            throw Test_Error("Fixed output RNG ran out of bytes, test bug?");
+            }
+
+         uint8_t out = m_buf.front();
+         m_buf.pop_front();
+         return out;
+         }
+
+      void randomize(uint8_t out[], size_t len) override
+         {
+         ++m_requests;
+
+         if(m_requests == m_pos)
+            { // return fixed output
+            for(size_t j = 0; j != len; j++)
+               {
+               out[j] = random();
+               }
+            }
+         else
+            { // return random
+               m_rng->randomize(out,len);
+            }
+         }
+
+      void add_entropy(const uint8_t*, size_t) override
+         {
+         throw Botan::Exception("add_entropy() not supported by this RNG, test bug?");
+         }
+
+      std::string name() const override { return "Fixed_Output_Position_RNG"; }
+
+      explicit Fixed_Output_Position_RNG(const std::vector<uint8_t>& in, uint32_t pos) :
+            Fixed_Output_RNG(in),
+            m_pos(pos),
+            m_rng{}
+         {
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+   m_rng.reset(new Botan::System_RNG);
+#else
+   m_rng.reset(new Botan::AutoSeeded_RNG);
+#endif
+         }
+
+      explicit Fixed_Output_Position_RNG(const std::string& in_str, uint32_t pos) :
+            Fixed_Output_RNG(in_str),
+            m_pos(pos),
+            m_rng{}
+         {
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+   m_rng.reset(new Botan::System_RNG);
+#else
+   m_rng.reset(new Botan::AutoSeeded_RNG);
+#endif
+         }
+
+   private:
+      uint32_t m_pos = 0;
+      uint32_t m_requests = 0;
+      std::unique_ptr<RandomNumberGenerator> m_rng;
+   };
+
 }
 
 #endif