Add ECKCDSA signature algorithm

3 files changed, 305 insertions, 0 deletions

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>