Much cleaning up in ECDSA, though it's still rather a mess (and 50x slower

than OpenSSL... that's a problem for another branch though).

7 files changed, 112 insertions, 166 deletions

diff --git a/src/cert/x509/x509_ca.cpp b/src/cert/x509/x509_ca.cpp
index 48ec0bd1c..a4159ad2b 100644
--- a/src/cert/x509/x509_ca.cpp
+++ b/src/cert/x509/x509_ca.cpp
@@ -21,8 +21,6 @@
 #include <memory>
 #include <set>
 
-#include <stdio.h>
-
 namespace Botan {
 
 /*
@@ -251,7 +249,6 @@ PK_Signer* choose_sig_format(const Private_Key& key,
                              AlgorithmIdentifier& sig_algo)
    {
    std::string padding;
-   Signature_Format format;
 
    const std::string algo_name = key.algo_name();
 
@@ -260,29 +257,20 @@ PK_Signer* choose_sig_format(const Private_Key& key,
       throw Algorithm_Not_Found(hash_fn);
 
    if(key.max_input_bits() < proto_hash->OUTPUT_LENGTH*8)
-      {
-      printf("%d %d\n", key.max_input_bits(), proto_hash->OUTPUT_LENGTH*8);
       throw Invalid_Argument("Key is too small for chosen hash function");
-      }
 
    if(algo_name == "RSA")
-      {
       padding = "EMSA3";
-      format = IEEE_1363;
-      }
    else if(algo_name == "DSA")
-      {
       padding = "EMSA1";
-      format = DER_SEQUENCE;
-      }
    else if(algo_name == "ECDSA")
-      {
       padding = "EMSA1_BSI";
-      format = IEEE_1363;
-      }
    else
       throw Invalid_Argument("Unknown X.509 signing key type: " + algo_name);
 
+   Signature_Format format =
+      (key.message_parts() > 1) ? DER_SEQUENCE : IEEE_1363;
+
    padding = padding + '(' + proto_hash->name() + ')';
 
    sig_algo.oid = OIDS::lookup(algo_name + "/" + padding);
diff --git a/src/pubkey/ecdsa/ecdsa.cpp b/src/pubkey/ecdsa/ecdsa.cpp
index ea2c35a19..9d352c70f 100644
--- a/src/pubkey/ecdsa/ecdsa.cpp
+++ b/src/pubkey/ecdsa/ecdsa.cpp
@@ -34,6 +34,29 @@ ECDSA_PrivateKey::ECDSA_PrivateKey(RandomNumberGenerator& rng,
    m_ecdsa_core = ECDSA_Core(*mp_dom_pars, m_private_value, *mp_public_point);
    }
 
+ECDSA_PrivateKey::ECDSA_PrivateKey(const EC_Domain_Params& domain,
+                                   const BigInt& x)
+   {
+   mp_dom_pars = std::auto_ptr<EC_Domain_Params>(new EC_Domain_Params(domain));
+
+   m_private_value = x;
+   mp_public_point = std::auto_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point()));
+   mp_public_point->mult_this_secure(m_private_value,
+                                     mp_dom_pars->get_order(),
+                                     mp_dom_pars->get_order()-1);
+
+   try
+      {
+      mp_public_point->check_invariants();
+      }
+   catch(Illegal_Point& e)
+      {
+      throw Invalid_State("ECDSA key generation failed");
+      }
+
+   m_ecdsa_core = ECDSA_Core(*mp_dom_pars, m_private_value, *mp_public_point);
+   }
+
 /*
 * ECDSA_PublicKey
 */
@@ -100,31 +123,12 @@ const ECDSA_PublicKey& ECDSA_PublicKey::operator=(const ECDSA_PublicKey& rhs)
    return *this;
    }
 
-bool ECDSA_PublicKey::verify(const byte message[],
-                             u32bit mess_len,
-                             const byte signature[],
-                             u32bit sig_len) const
+bool ECDSA_PublicKey::verify(const byte msg[], u32bit msg_len,
+                             const byte sig[], u32bit sig_len) const
    {
    affirm_init();
 
-   BigInt r, s;
-
-   BER_Decoder(signature, sig_len)
-      .start_cons(SEQUENCE)
-      .decode(r)
-      .decode(s)
-      .end_cons()
-      .verify_end();
-
-   u32bit enc_len = std::max(r.bytes(), s.bytes());
-
-   SecureVector<byte> sv_plain_sig;
-
-   sv_plain_sig.append(BigInt::encode_1363(r, enc_len));
-   sv_plain_sig.append(BigInt::encode_1363(s, enc_len));
-
-   return m_ecdsa_core.verify(sv_plain_sig, sv_plain_sig.size(),
-                              message, mess_len);
+   return m_ecdsa_core.verify(msg, msg_len, sig, sig_len);
    }
 
 ECDSA_PublicKey::ECDSA_PublicKey(const EC_Domain_Params& dom_par,
@@ -192,38 +196,26 @@ ECDSA_PrivateKey::ECDSA_PrivateKey(ECDSA_PrivateKey const& other)
    set_all_values(other);
    }
 
-
 const ECDSA_PrivateKey& ECDSA_PrivateKey::operator=(const ECDSA_PrivateKey& rhs)
    {
    set_all_values(rhs);
    return *this;
    }
 
-SecureVector<byte> ECDSA_PrivateKey::sign(const byte message[],
-                                          u32bit mess_len,
+SecureVector<byte> ECDSA_PrivateKey::sign(const byte msg[],
+                                          u32bit msg_len,
                                           RandomNumberGenerator& rng) const
    {
    affirm_init();
 
-   SecureVector<byte> sv_sig = m_ecdsa_core.sign(message, mess_len, rng);
-
-   if(sv_sig.size() % 2 != 0)
-      throw Invalid_Argument("Erroneous length of signature");
-
-   u32bit rs_len = sv_sig.size() / 2;
-   SecureVector<byte> sv_r, sv_s;
-   sv_r.set(sv_sig.begin(), rs_len);
-   sv_s.set(&sv_sig[rs_len], rs_len);
+   const BigInt& n = mp_dom_pars->get_order();
 
-   BigInt r = BigInt::decode(sv_r, sv_r.size());
-   BigInt s = BigInt::decode(sv_s, sv_s.size());
+   BigInt k;
+   do
+      k.randomize(rng, n.bits()-1);
+   while(k >= n);
 
-   return DER_Encoder()
-      .start_cons(SEQUENCE)
-      .encode(r)
-      .encode(s)
-      .end_cons()
-      .get_contents();
+   return m_ecdsa_core.sign(msg, msg_len, k);
    }
 
 }
diff --git a/src/pubkey/ecdsa/ecdsa.h b/src/pubkey/ecdsa/ecdsa.h
index a6a77f3e6..ce8c185a5 100644
--- a/src/pubkey/ecdsa/ecdsa.h
+++ b/src/pubkey/ecdsa/ecdsa.h
@@ -37,6 +37,11 @@ class BOTAN_DLL ECDSA_PublicKey : public virtual EC_PublicKey,
       */
       u32bit max_input_bits() const;
 
+      u32bit message_parts() const { return 2; }
+
+      u32bit message_part_size() const
+         { return mp_dom_pars->get_order().bytes(); }
+
       /**
       * Verify a message with this key.
       * @param message the byte array containing the message
@@ -113,6 +118,13 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
       ECDSA_PrivateKey(RandomNumberGenerator& rng,
                        const EC_Domain_Params& domain);
 
+      /**
+      * Load a private key
+      * @param domain parameters
+      * @param x the private key
+      */
+      ECDSA_PrivateKey(const EC_Domain_Params& domain, const BigInt& x);
+
       ECDSA_PrivateKey(const ECDSA_PrivateKey& other);
       ECDSA_PrivateKey const& operator=(const ECDSA_PrivateKey& rhs);
 
diff --git a/src/pubkey/ecdsa/ecdsa_core.cpp b/src/pubkey/ecdsa/ecdsa_core.cpp
index 93808ccd5..0be186fb4 100644
--- a/src/pubkey/ecdsa/ecdsa_core.cpp
+++ b/src/pubkey/ecdsa/ecdsa_core.cpp
@@ -7,10 +7,7 @@
 */
 
 #include <botan/ecdsa_core.h>
-#include <botan/numthry.h>
 #include <botan/pk_engine.h>
-#include <botan/parsing.h>
-#include <algorithm>
 
 namespace Botan {
 
@@ -26,10 +23,10 @@ bool ECDSA_Core::verify(const byte signature[], u32bit sig_len,
 
 SecureVector<byte> ECDSA_Core::sign(const byte message[],
                                     u32bit mess_len,
-                                    RandomNumberGenerator& rng) const
+                                    const BigInt& k) const
    {
    //assert(op.get());
-   return op->sign(message, mess_len, rng);
+   return op->sign(message, mess_len, k);
    }
 
 ECDSA_Core& ECDSA_Core::operator=(const ECDSA_Core& core)
diff --git a/src/pubkey/ecdsa/ecdsa_core.h b/src/pubkey/ecdsa/ecdsa_core.h
index ceccc940e..c6583a86f 100644
--- a/src/pubkey/ecdsa/ecdsa_core.h
+++ b/src/pubkey/ecdsa/ecdsa_core.h
@@ -10,7 +10,6 @@
 #define BOTAN_ECDSA_CORE_H__
 
 #include <botan/ecdsa_op.h>
-#include <botan/blinding.h>
 #include <botan/ec_dompar.h>
 
 namespace Botan {
@@ -25,7 +24,7 @@ class BOTAN_DLL ECDSA_Core
                   const byte message[], u32bit mess_len) const;
 
       SecureVector<byte> sign(const byte message[], u32bit mess_len,
-                              RandomNumberGenerator& rng) const;
+                              const BigInt& k) const;
 
       ECDSA_Core& operator=(const ECDSA_Core&);
 
diff --git a/src/pubkey/ecdsa/ecdsa_op.cpp b/src/pubkey/ecdsa/ecdsa_op.cpp
index 986043ed6..afa7d52bd 100644
--- a/src/pubkey/ecdsa/ecdsa_op.cpp
+++ b/src/pubkey/ecdsa/ecdsa_op.cpp
@@ -1,7 +1,7 @@
 /*
 * ECDSA Operation
 * (C) 2007 FlexSecure GmbH
-*     2008 Jack Lloyd
+*     2008-2009 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -9,121 +9,82 @@
 #include <botan/ecdsa_op.h>
 #include <botan/numthry.h>
 
+#include <stdio.h>
+#include <iostream>
+
 namespace Botan {
 
-bool Default_ECDSA_Op::verify(const byte signature[], u32bit sig_len,
-                              const byte message[], u32bit mess_len) const
+Default_ECDSA_Op::Default_ECDSA_Op(const EC_Domain_Params& domain,
+                                   const BigInt& priv,
+                                   const PointGFp& pub) :
+   dom_pars(domain), pub_key(pub), priv_key(priv)
    {
-   if(sig_len % 2 != 0)
-      throw Invalid_Argument("Erroneous length of signature");
+   }
 
-   //NOTE: it is not checked whether the public point is set
-   if(m_dom_pars.get_curve().get_p() == 0)
-      throw Internal_Error("domain parameters not set");
+bool Default_ECDSA_Op::verify(const byte msg[], u32bit msg_len,
+                              const byte sig[], u32bit sig_len) const
+   {
+   const BigInt& n = dom_pars.get_order();
+
+   if(sig_len != n.bytes()*2)
+      return false;
 
-   BigInt e(message, mess_len);
+   // NOTE: it is not checked whether the public point is set
+   if(dom_pars.get_curve().get_p() == 0)
+      throw Internal_Error("domain parameters not set");
 
-   u32bit rs_len = sig_len/2;
-   SecureVector<byte> sv_r;
-   SecureVector<byte> sv_s;
-   sv_r.set(signature, rs_len);
-   sv_s.set(signature+rs_len, rs_len);
-   BigInt r = BigInt::decode ( sv_r, sv_r.size());
-   BigInt s = BigInt::decode (sv_s, sv_s.size());
+   BigInt e(msg, msg_len);
 
-   if(r < 0 || r >= m_dom_pars.get_order())
-      throw Invalid_Argument("r in ECDSA signature has an illegal value");
+   BigInt r(sig, sig_len / 2);
+   BigInt s(sig + sig_len / 2, sig_len / 2);
 
-   if(s < 0 || s >= m_dom_pars.get_order())
-      throw Invalid_Argument("s in ECDSA signature has an illegal value");
+   if(r < 0 || r >= n || s < 0 || s >= n)
+      return false;
 
-   BigInt w = inverse_mod(s, m_dom_pars.get_order());
+   BigInt w = inverse_mod(s, n);
 
-   PointGFp R = w*(e*m_dom_pars.get_base_point() + r*m_pub_key);
+   PointGFp R = w * (e * dom_pars.get_base_point() + r*pub_key);
    if(R.is_zero())
       return false;
 
    BigInt x = R.get_affine_x().get_value();
-   bool result = (x % m_dom_pars.get_order() == r);
-   return result;
+
+   return (x % n == r);
    }
 
-SecureVector<byte> Default_ECDSA_Op::sign(const byte message[],
-                                          u32bit mess_len,
-                                          RandomNumberGenerator& rng) const
+SecureVector<byte> Default_ECDSA_Op::sign(const byte msg[], u32bit msg_len,
+                                          const BigInt& k) const
    {
-   if(m_priv_key == 0)
+   if(priv_key == 0)
       throw Internal_Error("Default_ECDSA_Op::sign(): no private key");
 
-   if(m_dom_pars.get_curve().get_p() == 0)
+   const BigInt& n = dom_pars.get_order();
+
+   if(n == 0)
       throw Internal_Error("Default_ECDSA_Op::sign(): domain parameters not set");
 
-   BigInt e(message, mess_len);
-
-   // generate k
-   BigInt k;
-   BigInt r(0);
-   const BigInt n(m_dom_pars.get_order());
-   while(r == 0)
-      {
-      k = BigInt::random_integer(rng, 1, n);
-
-      PointGFp k_times_P(m_dom_pars.get_base_point());
-      k_times_P.mult_this_secure(k, n, n-1);
-      k_times_P.check_invariants();
-      r =  k_times_P.get_affine_x().get_value() % n;
-      }
-   BigInt k_inv = inverse_mod(k, n);
+   BigInt e(msg, msg_len);
 
-   // use randomization against attacks on s:
-   // a = k_inv * (r*(d + x) + e) mod n
-   // b = k_inv * r * x mod n
-   // s = a - b mod n
-   // where x is a random integer
-
-#if defined(CMS_RAND)
-   BigInt x = BigInt::random_integer(0, n);
-   BigInt s = m_priv_key + x; // obscure the secret from the beginning
-   // all following operations thus are randomized
-   s *= r;
-   s += e;
-   s *= k_inv;
-   s %= n;
+   PointGFp k_times_P(dom_pars.get_base_point());
+   k_times_P.mult_this_secure(k, n, n-1);
+   k_times_P.check_invariants();
+   BigInt r = k_times_P.get_affine_x().get_value() % n;
+
+   if(r == 0)
+      throw Internal_Error("Default_ECDSA_Op::sign: r was zero");
+
+   BigInt k_inv = inverse_mod(k, n);
 
-   BigInt b = x; // again, start with the random number
-   b *= r;
-   b *= k_inv;
-   b %= n;
-   s -= b; // s = a - b
-   if(s <= 0) // s %= n
-      {
-      s += n;
-      }
-#else // CMS_RAND
-   // no countermeasure here
    BigInt s(r);
-   s *= m_priv_key;
+   s *= priv_key;
    s += e;
    s *= k_inv;
    s %= n;
 
-#endif // CMS_RAND
-
-   SecureVector<byte> sv_r = BigInt::encode_1363 ( r, m_dom_pars.get_order().bytes() );
-   SecureVector<byte> sv_s = BigInt::encode_1363 ( s, m_dom_pars.get_order().bytes() );
-
-   SecureVector<byte> result(sv_r);
-   result.append(sv_s);
-   return result;
-   }
-
-Default_ECDSA_Op::Default_ECDSA_Op(const EC_Domain_Params& dom_pars, const BigInt& priv_key, const PointGFp& pub_key)
-   : m_dom_pars(dom_pars),
-     m_pub_key(pub_key),
-     m_priv_key(priv_key)
-   {
-
+   SecureVector<byte> output(2*n.bytes());
+   r.binary_encode(output + (output.size() / 2 - r.bytes()));
+   s.binary_encode(output + (output.size() - s.bytes()));
+   return output;
    }
 
 }
-
diff --git a/src/pubkey/ecdsa/ecdsa_op.h b/src/pubkey/ecdsa/ecdsa_op.h
index 25831a9d4..c203905f9 100644
--- a/src/pubkey/ecdsa/ecdsa_op.h
+++ b/src/pubkey/ecdsa/ecdsa_op.h
@@ -10,7 +10,6 @@
 #define BOTAN_ECDSA_OPERATIONS_H__
 
 #include <botan/ec_dompar.h>
-#include <botan/rng.h>
 
 namespace Botan {
 
@@ -20,30 +19,28 @@ namespace Botan {
 class BOTAN_DLL ECDSA_Operation
    {
    public:
-      virtual bool verify(const byte sig[], u32bit sig_len,
-                          const byte msg[], u32bit msg_len) const = 0;
+      virtual bool verify(const byte msg[], u32bit msg_len,
+                          const byte sig[], u32bit sig_len) const = 0;
 
-      virtual SecureVector<byte> sign(const byte message[],
-                                      u32bit mess_len,
-                                      RandomNumberGenerator&) const = 0;
+      virtual SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                                      const BigInt& k) const = 0;
 
       virtual ECDSA_Operation* clone() const = 0;
 
       virtual ~ECDSA_Operation() {}
    };
 
-
 /*
 * Default ECDSA operation
 */
 class BOTAN_DLL Default_ECDSA_Op : public ECDSA_Operation
    {
    public:
-      bool verify(const byte signature[], u32bit sig_len,
-                  const byte message[], u32bit mess_len) const;
+      bool verify(const byte sig[], u32bit sig_len,
+                  const byte msg[], u32bit msg_len) const;
 
-      SecureVector<byte> sign(const byte message[], u32bit mess_len,
-                              RandomNumberGenerator& rng) const;
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              const BigInt& k) const;
 
       ECDSA_Operation* clone() const
          {
@@ -54,9 +51,9 @@ class BOTAN_DLL Default_ECDSA_Op : public ECDSA_Operation
                        const BigInt& priv_key,
                        const PointGFp& pub_key);
    private:
-      EC_Domain_Params m_dom_pars;
-      PointGFp m_pub_key;
-      BigInt m_priv_key;
+      EC_Domain_Params dom_pars;
+      PointGFp pub_key;
+      BigInt priv_key;
    };
 
 }