Support recovering ECDSA public key from message/signature pair

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

Closes #664

6 files changed, 232 insertions, 2 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 647e8bd8c..57206a1fa 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -109,6 +109,10 @@
    #include <botan/mceliece.h>
 #endif
 
+#if defined(BOTAN_HAS_ECDSA)
+   #include <botan/ecdsa.h>
+#endif
+
 #if defined(BOTAN_HAS_NEWHOPE)
    #include <botan/newhope.h>
 #endif
@@ -451,9 +455,16 @@ class Speed final : public Command
             throw CLI_Usage_Error("Unknown --format type '" + format + "'");
 
          if(ecc_groups.empty())
+            {
             ecc_groups = { "secp256r1", "brainpool256r1",
                            "secp384r1", "brainpool384r1",
                            "secp521r1", "brainpool512r1" };
+            }
+         else if(ecc_groups.size() == 1 && ecc_groups[0] == "all")
+            {
+            auto all = Botan::EC_Group::known_named_groups();
+            ecc_groups.assign(all.begin(), all.end());
+            }
 
          std::vector<std::string> algos = get_arg_list("algos");
 
@@ -544,6 +555,10 @@ class Speed final : public Command
                {
                bench_ecdsa(ecc_groups, provider, msec);
                }
+            else if(algo == "ecdsa_recovery")
+               {
+               bench_ecdsa_recovery(ecc_groups, provider, msec);
+               }
 #endif
 #if defined(BOTAN_HAS_SM2)
             else if(algo == "SM2")
@@ -1831,6 +1846,42 @@ class Speed final : public Command
          {
          return bench_pk_sig_ecc("ECDSA", "EMSA1(SHA-256)", provider, groups, msec);
          }
+
+      void bench_ecdsa_recovery(const std::vector<std::string>& groups,
+                                const std::string&,
+                                std::chrono::milliseconds msec)
+         {
+         for(std::string group_name : groups)
+            {
+            Botan::EC_Group group(group_name);
+            std::unique_ptr<Timer> recovery_timer = make_timer("ECDSA recovery " + group_name);
+
+            while(recovery_timer->under(msec))
+               {
+               Botan::ECDSA_PrivateKey key(rng(), group);
+
+               std::vector<uint8_t> message(group.get_order_bytes());
+               rng().randomize(message.data(), message.size());
+
+               Botan::PK_Signer signer(key, rng(), "Raw");
+               signer.update(message);
+               std::vector<uint8_t> signature = signer.signature(rng());
+
+               Botan::BigInt r(signature.data(), signature.size()/2);
+               Botan::BigInt s(signature.data() + signature.size()/2, signature.size()/2);
+               const uint8_t v = key.recovery_param(message, r, s);
+
+               recovery_timer->run([&]() {
+                  Botan::ECDSA_PublicKey pubkey(group, message, r, s, v);
+                  BOTAN_ASSERT(pubkey.public_point() == key.public_point(), "Recovered public key");
+                  });
+               }
+
+            record_result(recovery_timer);
+            }
+
+         }
+
 #endif
 
 #if defined(BOTAN_HAS_ECKCDSA)
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;
diff --git a/src/scripts/test_cli.py b/src/scripts/test_cli.py
index 239c05175..99447e6d4 100755
--- a/src/scripts/test_cli.py
+++ b/src/scripts/test_cli.py
@@ -655,7 +655,9 @@ def cli_speed_tests():
         if format_re.match(line) is None:
             logging.error("Unexpected line %s", line)
 
-    math_ops = ['mp_mul', 'mp_div', 'modexp', 'random_prime', 'inverse_mod', 'rfc3394', 'fpe_fe1',
+    # these all have a common output format
+    math_ops = ['mp_mul', 'mp_div', 'mp_div10', 'modexp', 'random_prime', 'inverse_mod',
+                'rfc3394', 'fpe_fe1', 'ecdsa_recovery',
                 'bn_redc', 'nistp_redc', 'ecc_mult', 'ecc_ops', 'os2ecp', 'primality_test',
                 'bcrypt', 'passhash9']
 
@@ -728,7 +730,11 @@ def main(args=None):
 
     test_regex = None
     if len(args) == 3:
-        test_regex = re.compile(args[2])
+        try:
+            test_regex = re.compile(args[2])
+        except re.error as e:
+            logging.error("Invalid regex: %s", str(e))
+            return 1
 
     start_time = time.time()
 
diff --git a/src/tests/data/pubkey/ecdsa_key_recovery.vec b/src/tests/data/pubkey/ecdsa_key_recovery.vec
new file mode 100644
index 000000000..c753d0bdb
--- /dev/null
+++ b/src/tests/data/pubkey/ecdsa_key_recovery.vec
@@ -0,0 +1,16 @@
+
+Group = secp256k1
+R = 0xE30F2E6A0F705F4FB5F8501BA79C7C0D3FAC847F1AD70B873E9797B17B89B390
+S = 0x81F1A4457589F30D76AB9F89E748A68C8A94C30FE0BAC8FB5C0B54EA70BF6D2F
+Msg = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+V = 0
+PubkeyX = 0xF3F8BB913AA68589A2C8C607A877AB05252ADBD963E1BE846DDEB8456942AEDC
+PubkeyY = 0xA2ED51F08CA3EF3DAC0A7504613D54CD539FC1B3CBC92453CD704B6A2D012B2C
+
+Group = secp256r1
+R = 0x2AC979EB6C7502A49CACC0995A2B9C50192F334B742573767ADD6DCB01343D50
+S = 0xF444D29AFCA529A0A96467DAA5E881B1C60C73273E099DF7C910BD4EED0502D6
+V = 1
+Msg = 3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E3E
+PubkeyX = 0x89F5662F5D9DE780184E3A2E1D170D6D30FF28F03E030C9CA99F3DB670E5DBB8
+PubkeyY = 0xEDDB57C7ACA9711D3CF67A2699792F76EE15A8129449D8A450D371CEFF2E00C7
diff --git a/src/tests/test_ecdsa.cpp b/src/tests/test_ecdsa.cpp
index 68369fe1e..e1819fe1a 100644
--- a/src/tests/test_ecdsa.cpp
+++ b/src/tests/test_ecdsa.cpp
@@ -152,6 +152,56 @@ class ECDSA_Keygen_Tests final : public PK_Key_Generation_Test
          }
    };
 
+#if defined(BOTAN_HAS_EMSA_RAW)
+
+class ECDSA_Key_Recovery_Tests final : public Text_Based_Test
+   {
+   public:
+      ECDSA_Key_Recovery_Tests() :
+         Text_Based_Test("pubkey/ecdsa_key_recovery.vec", "Group,Msg,R,S,V,PubkeyX,PubkeyY") {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override
+         {
+         Test::Result result("ECDSA key recovery");
+
+         const std::string group_id = vars.get_req_str("Group");
+         Botan::EC_Group group(group_id);
+
+         const BigInt R = vars.get_req_bn("R");
+         const BigInt S = vars.get_req_bn("S");
+         const uint8_t V = vars.get_req_u8("V");
+         const std::vector<uint8_t> msg = vars.get_req_bin("Msg");
+         const BigInt pubkey_x = vars.get_req_bn("PubkeyX");
+         const BigInt pubkey_y = vars.get_req_bn("PubkeyY");
+
+         try
+            {
+            Botan::ECDSA_PublicKey pubkey(group, msg, R, S, V);
+            result.test_eq("Pubkey X coordinate", pubkey.public_point().get_affine_x(), pubkey_x);
+            result.test_eq("Pubkey Y coordinate", pubkey.public_point().get_affine_y(), pubkey_y);
+
+            const uint8_t computed_V = pubkey.recovery_param(msg, R, S);
+            result.test_eq("Recovery param is correct", static_cast<size_t>(computed_V), static_cast<size_t>(V));
+
+            Botan::PK_Verifier verifier(pubkey, "Raw");
+
+            auto sig = Botan::BigInt::encode_fixed_length_int_pair(R, S, group.get_order_bytes());
+
+            result.confirm("Signature verifies", verifier.verify_message(msg, sig));
+            }
+         catch(Botan::Exception& e)
+            {
+            result.test_failure("Failed to recover ECDSA public key", e.what());
+            }
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("ecdsa_key_recovery", ECDSA_Key_Recovery_Tests);
+
+#endif
+
 class ECDSA_Invalid_Key_Tests final : public Text_Based_Test
    {
    public: