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, 66 insertions, 0 deletions

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: