Support recovering ECDSA public key from message/signature pair

See http://www.secg.org/sec1-v2.pdf section 4.1.6

Closes #664

2 files changed, 107 insertions, 0 deletions

diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 5d89cc198..70196f55b 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -29,6 +29,94 @@
 
 namespace Botan {
 
+namespace {
+
+PointGFp recover_ecdsa_public_key(const EC_Group& group,
+                                  const std::vector<uint8_t>& msg,
+                                  const BigInt& r,
+                                  const BigInt& s,
+                                  uint8_t v)
+   {
+   if(group.get_cofactor() != 1)
+      throw Invalid_Argument("ECDSA public key recovery only supported for prime order groups");
+
+   if(v > 4)
+      throw Invalid_Argument("Unexpected v param for ECDSA public key recovery");
+
+   const uint8_t y_odd = v % 2;
+   const uint8_t add_order = v >> 1;
+
+   const BigInt& group_order = group.get_order();
+   const size_t p_bytes = group.get_p_bytes();
+
+   try
+      {
+      const BigInt e(msg.data(), msg.size(), group.get_order_bits());
+      const BigInt r_inv = group.inverse_mod_order(r);
+
+      BigInt x = r + add_order*group_order;
+
+      std::vector<uint8_t> X(p_bytes + 1);
+
+      X[0] = 0x02 | y_odd;
+      BigInt::encode_1363(&X[1], p_bytes, x);
+
+      const PointGFp R = group.OS2ECP(X);
+
+      if((R*group_order).is_zero() == false)
+         throw Decoding_Error("Unable to recover ECDSA public key");
+
+      // Compute r_inv * (s*R - eG)
+      PointGFp_Multi_Point_Precompute RG_mul(R, group.get_base_point());
+      const BigInt ne = group.mod_order(group_order - e);
+      return r_inv * RG_mul.multi_exp(s, ne);
+      }
+   catch(Illegal_Point&)
+      {
+      // continue on and throw
+      }
+   catch(Decoding_Error&)
+      {
+      // continue on and throw
+      }
+
+   throw Decoding_Error("Failed to recover ECDSA public key from signature/msg pair");
+   }
+
+}
+
+ECDSA_PublicKey::ECDSA_PublicKey(const EC_Group& group,
+                                 const std::vector<uint8_t>& msg,
+                                 const BigInt& r,
+                                 const BigInt& s,
+                                 uint8_t v) :
+   EC_PublicKey(group, recover_ecdsa_public_key(group, msg, r, s, v)) {}
+
+
+uint8_t ECDSA_PublicKey::recovery_param(const std::vector<uint8_t>& msg,
+                                        const BigInt& r,
+                                        const BigInt& s) const
+   {
+   for(uint8_t v = 0; v != 4; ++v)
+      {
+      try
+         {
+         PointGFp R = recover_ecdsa_public_key(this->domain(), msg, r, s, v);
+
+         if(R == this->public_point())
+            {
+            return v;
+            }
+         }
+      catch(Decoding_Error&)
+         {
+         // try the next v
+         }
+      }
+
+   throw Internal_Error("Could not determine ECDSA recovery parameter");
+   }
+
 bool ECDSA_PrivateKey::check_key(RandomNumberGenerator& rng,
                                  bool strong) const
    {
diff --git a/src/lib/pubkey/ecdsa/ecdsa.h b/src/lib/pubkey/ecdsa/ecdsa.h
index 2929059c5..8423a9c20 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.h
+++ b/src/lib/pubkey/ecdsa/ecdsa.h
@@ -40,6 +40,21 @@ class BOTAN_PUBLIC_API(2,0) ECDSA_PublicKey : public virtual EC_PublicKey
          EC_PublicKey(alg_id, key_bits) {}
 
       /**
+      * Recover a public key from a signature/msg pair
+      * See SEC section 4.6.1
+      * @param group the elliptic curve group
+      * @param msg the message
+      * @param r the r paramter of the signature
+      * @param s the s paramter of the signature
+      * @param v the recovery ID
+      */
+      ECDSA_PublicKey(const EC_Group& group,
+                      const std::vector<uint8_t>& msg,
+                      const BigInt& r,
+                      const BigInt& s,
+                      uint8_t v);
+
+      /**
       * Get this keys algorithm name.
       * @result this keys algorithm name ("ECDSA")
       */
@@ -50,6 +65,10 @@ class BOTAN_PUBLIC_API(2,0) ECDSA_PublicKey : public virtual EC_PublicKey
       size_t message_part_size() const override
          { return domain().get_order().bytes(); }
 
+      uint8_t recovery_param(const std::vector<uint8_t>& msg,
+                             const BigInt& r,
+                             const BigInt& s) const;
+
       std::unique_ptr<PK_Ops::Verification>
          create_verification_op(const std::string& params,
                                 const std::string& provider) const override;