title: How do I get an ECDSA public key from just a Bitcoin signature? ... SEC1 4.1.6 key recovery for curves over (mod p)-fields
body: <blockquote>
    <p><strong>Update:</strong> Partial solution available on Git</p>
  </blockquote>
  
  <p>EDIT: A compiled version of this is available at <a href="https://github.com/makerofthings7/Bitcoin-MessageSignerVerifier" rel="nofollow noreferrer">https://github.com/makerofthings7/Bitcoin-MessageSignerVerifier</a>  </p>
  
  <p>Please note that the message to be verified must have <code>Bitcoin Signed Message:\n</code> as a prefix.  <a href="https://github.com/bitcoin/bitcoin/blob/0.8.6/src/main.cpp" rel="nofollow noreferrer">Source1</a> <a href="https://github.com/nanotube/supybot-bitcoin-marketmonitor/blob/master/GPG/local/bitcoinsig.py" rel="nofollow noreferrer">Source2</a></p>
  
  <p>There is something wrong in the C# implementation that I can probably correct from <a href="https://github.com/nanotube/supybot-bitcoin-marketmonitor/blob/master/GPG/local/bitcoinsig.py" rel="nofollow noreferrer">this Python implementation</a> </p>
  
  <hr>
  
  <p>It seems to have a problem with actually coming up with the correct Base 58 address.</p>
  
  <p>I have the following message, signature, and Base58 address below.  I intend to extract the key from the signature, hash that key, and compare the Base58 hashes.</p>
  
  <p>My problem is: How do I extract the key from the signature?  (Edit <a href="https://github.com/bitcoin/bitcoin/blob/9b1200c23bbced3a78b58067c1f6414103653795/src/key.cpp#L56" rel="nofollow noreferrer">I found the c++ code</a> at the bottom of this post, need it in Bouncy Castle / or C#) </p>
  
  <p><em>Message</em></p>
  
  <pre><code>StackOverflow test 123
  </code></pre>
  
  <p><em>Signature</em></p>
  
  <pre><code>IB7XjSi9TdBbB3dVUK4+Uzqf2Pqk71XkZ5PUsVUN+2gnb3TaZWJwWW2jt0OjhHc4B++yYYRy1Lg2kl+WaiF+Xsc=
  </code></pre>
  
  <p><em>Base58 Bitcoin address "hash"</em></p>
  
  <pre><code>1Kb76YK9a4mhrif766m321AMocNvzeQxqV
  </code></pre>
  
  <p>Since the Base58 Bitcoin address is just a hash, I can't use it for validation of a Bitcoin message.  However, it is possible to extract the public key from a <em>signature.</em></p>
  
  <p><em>Edit:</em> I'm emphasizing that I'm deriving the Public key from the signature itself, and not from the Base58 public key hash.  If I want to (and I actually do want to) I should be able to convert these public key bits into the Base58 hash.  I don't need assistance in doing this, I just need help in extracting the public key bits and verifying the signature.</p>
  
  <p><strong>Question</strong></p>
  
  <ol>
  <li><p>In the Signature above, what format is this signature in? PKCS10?  (Answer: no, it's proprietary <a href="https://bitcoin.stackexchange.com/q/14263/1878">as described here</a>) </p></li>
  <li><p>how do I extract the public key in Bouncy Castle?</p></li>
  <li><p>What is the correct way to verify the signature?  (assume that I already know how to convert the Public Key bits into a hash that equals the Bitcoin hash above)</p></li>
  </ol>
  
  <p><strong>Prior research</strong></p>
  
  <p><a href="http://www.bouncycastle.org/wiki/display/JA1/Elliptic+Curve+Key+Pair+Generation+and+Key+Factories" rel="nofollow noreferrer">This link</a> describes how to use ECDSA curves, and the following code will allow me to convert a public key into a BC object, but I'm unsure on how to get the point <code>Q</code> from the signature.  </p>
  
  <p>In the sample below Q is the hard coded value</p>
  
  <pre><code>  Org.BouncyCastle.Asn1.X9.X9ECParameters ecp = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    ECDomainParameters params = new ECDomainParameters(ecp.Curve, ecp.G, ecp.N, ecp.H);
    ECPublicKeySpec pubKeySpec = new ECPublicKeySpec(
    ecp .curve.decodePoint(Hex.decode("045894609CCECF9A92533F630DE713A958E96C97CCB8F5ABB5A688A238DEED6DC2D9D0C94EBFB7D526BA6A61764175B99CB6011E2047F9F067293F57F5")), // Q
          params);
    PublicKey  pubKey = f.generatePublic(pubKeySpec);
  
  
   var signer = SignerUtilities.GetSigner("ECDSA"); // possibly similar to SHA-1withECDSA
   signer.Init(false, pubKey);
   signer.BlockUpdate(plainTextAsBytes, 0, plainTextAsBytes.Length);
   return signer.VerifySignature(signature);
  </code></pre>
  
  <hr>
  
  <p><strong>Additional research:</strong></p>
  
  <p><a href="https://github.com/bitcoin/bitcoin/blob/9d580b82c591c8bd3439f84fb1038e975af5c3ac/src/rpcwallet.cpp#L375" rel="nofollow noreferrer">THIS</a> is the Bitcoin source that verifies a message.</p>
  
  <p>After decoding the Base64 of the signature, the <a href="https://github.com/bitcoin/bitcoin/blob/9b1200c23bbced3a78b58067c1f6414103653795/src/key.cpp#L446" rel="nofollow noreferrer">RecoverCompact(hash of message, signature)</a> is called.  I'm not a C++ programmer so I'm assuming I need to figure out how <code>key.Recover</code> works.  That or <code>key.GetPubKey</code></p>
  
  <p>This is the C++ code that I think I need in C#, ideally in bouncy castle... but I'll take anything that works.</p>
  
  <pre><code>// reconstruct public key from a compact signature
  // This is only slightly more CPU intensive than just verifying it.
  // If this function succeeds, the recovered public key is guaranteed to be valid
  // (the signature is a valid signature of the given data for that key)
  bool Recover(const uint256 &amp;hash, const unsigned char *p64, int rec)
  {
      if (rec&lt;0 || rec&gt;=3)
          return false;
      ECDSA_SIG *sig = ECDSA_SIG_new();
      BN_bin2bn(&amp;p64[0],  32, sig-&gt;r);
      BN_bin2bn(&amp;p64[32], 32, sig-&gt;s);
      bool ret = ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&amp;hash, sizeof(hash), rec, 0) == 1;
      ECDSA_SIG_free(sig);
      return ret;
  }
  </code></pre>
  
  <p>... the code for <a href="https://github.com/bitcoin/bitcoin/blob/9b1200c23bbced3a78b58067c1f6414103653795/src/key.cpp#L56" rel="nofollow noreferrer">ECDSA_SIG_recover_key_GFp  is here</a></p>
  
  <p><strong>Custom signature format in Bitcoin</strong></p>
  
  <p><a href="https://bitcoin.stackexchange.com/q/14263/1878">This answer says there are 4 possible</a> public keys that can produce a signature, and this is encoded in the newer signatures.</p>