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

Question

Update: Partial solution available on Git

EDIT: A compiled version of this is available at https://github.com/makerofthings7/Bitcoin-MessageSignerVerifier

Please note that the message to be verified must have Bitcoin Signed Message:\n as a prefix. Source1 Source2

There is something wrong in the C# implementation that I can probably correct from this Python implementation

---

It seems to have a problem with actually coming up with the correct Base 58 address.

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.

My problem is: How do I extract the key from the signature? (Edit I found the c++ code at the bottom of this post, need it in Bouncy Castle / or C#)

Message

StackOverflow test 123

Signature

IB7XjSi9TdBbB3dVUK4+Uzqf2Pqk71XkZ5PUsVUN+2gnb3TaZWJwWW2jt0OjhHc4B++yYYRy1Lg2kl+WaiF+Xsc=

Base58 Bitcoin address "hash"

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

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 signature.

Edit: 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.

Question

1. In the Signature above, what format is this signature in? PKCS10? (Answer: no, it's proprietary as described here)

2. how do I extract the public key in Bouncy Castle?

3. 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)

Prior research

This link 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 Q from the signature.

In the sample below Q is the hard coded value

  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);

---

Additional research:

THIS is the Bitcoin source that verifies a message.

After decoding the Base64 of the signature, the RecoverCompact(hash of message, signature) is called. I'm not a C++ programmer so I'm assuming I need to figure out how key.Recover works. That or key.GetPubKey

This is the C++ code that I think I need in C#, ideally in bouncy castle... but I'll take anything that works.

// 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 &hash, const unsigned char *p64, int rec)
{
    if (rec<0 || rec>=3)
        return false;
    ECDSA_SIG *sig = ECDSA_SIG_new();
    BN_bin2bn(&p64[0],  32, sig->r);
    BN_bin2bn(&p64[32], 32, sig->s);
    bool ret = ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&hash, sizeof(hash), rec, 0) == 1;
    ECDSA_SIG_free(sig);
    return ret;
}

... the code for ECDSA_SIG_recover_key_GFp is here

Custom signature format in Bitcoin

This answer says there are 4 possible public keys that can produce a signature, and this is encoded in the newer signatures.

Solution 1

After referencing BitcoinJ, it appears some of these code samples are missing proper preparation of the message, double-SHA256 hashing, and possible compressed encoding of the recovered public point that is input to the address calculation.

The following code should only need BouncyCastle (probably you'll need recent version from github, not sure). It borrows a few things from BitcoinJ, and does just does enough to get small examples working, see inline comments for message size restrictions.

It only calculates up to the RIPEMD-160 hash, and I used http://gobittest.appspot.com/Address to check the final address that results (unfortunately that website doesn't seem to support entering a compressed encoding for the public key).

    public static void CheckSignedMessage(string message, string sig64)
    {
        byte[] sigBytes = Convert.FromBase64String(sig64);
        byte[] msgBytes = FormatMessageForSigning(message);

        int first = (sigBytes[0] - 27);
        bool comp = (first & 4) != 0;
        int rec = first & 3;

        BigInteger[] sig = ParseSig(sigBytes, 1);
        byte[] msgHash = DigestUtilities.CalculateDigest("SHA-256", DigestUtilities.CalculateDigest("SHA-256", msgBytes));

        ECPoint Q = Recover(msgHash, sig, rec, true);

        byte[] qEnc = Q.GetEncoded(comp);
        Console.WriteLine("Q: " + Hex.ToHexString(qEnc));

        byte[] qHash = DigestUtilities.CalculateDigest("RIPEMD-160", DigestUtilities.CalculateDigest("SHA-256", qEnc));
        Console.WriteLine("RIPEMD-160(SHA-256(Q)): " + Hex.ToHexString(qHash));

        Console.WriteLine("Signature verified correctly: " + VerifySignature(Q, msgHash, sig));
    }

    public static BigInteger[] ParseSig(byte[] sigBytes, int sigOff)
    {
        BigInteger r = new BigInteger(1, sigBytes, sigOff, 32);
        BigInteger s = new BigInteger(1, sigBytes, sigOff + 32, 32);
        return new BigInteger[] { r, s };
    }

    public static ECPoint Recover(byte[] hash, BigInteger[] sig, int recid, bool check)
    {
        X9ECParameters x9 = SecNamedCurves.GetByName("secp256k1");

        BigInteger r = sig[0], s = sig[1];

        FpCurve curve = x9.Curve as FpCurve;
        BigInteger order = x9.N;

        BigInteger x = r;
        if ((recid & 2) != 0)
        {
            x = x.Add(order);
        }

        if (x.CompareTo(curve.Q) >= 0) throw new Exception("X too large");

        byte[] xEnc = X9IntegerConverter.IntegerToBytes(x, X9IntegerConverter.GetByteLength(curve));

        byte[] compEncoding = new byte[xEnc.Length + 1];
        compEncoding[0] = (byte)(0x02 + (recid & 1));
        xEnc.CopyTo(compEncoding, 1);
        ECPoint R = x9.Curve.DecodePoint(compEncoding);

        if (check)
        {
            //EC_POINT_mul(group, O, NULL, R, order, ctx))
            ECPoint O = R.Multiply(order);
            if (!O.IsInfinity) throw new Exception("Check failed");
        }

        BigInteger e = CalculateE(order, hash);

        BigInteger rInv = r.ModInverse(order);
        BigInteger srInv = s.Multiply(rInv).Mod(order);
        BigInteger erInv = e.Multiply(rInv).Mod(order);

        return ECAlgorithms.SumOfTwoMultiplies(R, srInv, x9.G.Negate(), erInv);
    }

    public static bool VerifySignature(ECPoint Q, byte[] hash, BigInteger[] sig)
    {
        X9ECParameters x9 = SecNamedCurves.GetByName("secp256k1");
        ECDomainParameters ec = new ECDomainParameters(x9.Curve, x9.G, x9.N, x9.H, x9.GetSeed());
        ECPublicKeyParameters publicKey = new ECPublicKeyParameters(Q, ec);
        return VerifySignature(publicKey, hash, sig);
    }

    public static bool VerifySignature(ECPublicKeyParameters publicKey, byte[] hash, BigInteger[] sig)
    {
        ECDsaSigner signer = new ECDsaSigner();
        signer.Init(false, publicKey);
        return signer.VerifySignature(hash, sig[0], sig[1]);
    }

    private static BigInteger CalculateE(
        BigInteger n,
        byte[] message)
    {
        int messageBitLength = message.Length * 8;
        BigInteger trunc = new BigInteger(1, message);

        if (n.BitLength < messageBitLength)
        {
            trunc = trunc.ShiftRight(messageBitLength - n.BitLength);
        }

        return trunc;
    }

    public static byte[] FormatMessageForSigning(String message)
    {
        MemoryStream bos = new MemoryStream();
        bos.WriteByte((byte)BITCOIN_SIGNED_MESSAGE_HEADER_BYTES.Length);
        bos.Write(BITCOIN_SIGNED_MESSAGE_HEADER_BYTES, 0, BITCOIN_SIGNED_MESSAGE_HEADER_BYTES.Length);
        byte[] messageBytes = Encoding.UTF8.GetBytes(message);

        //VarInt size = new VarInt(messageBytes.length);
        //bos.write(size.encode());
        // HACK only works for short messages (< 253 bytes)
        bos.WriteByte((byte)messageBytes.Length);

        bos.Write(messageBytes, 0, messageBytes.Length);
        return bos.ToArray();
    }

Sample output for the initial data in the question:

Q: 0283437893b491218348bf5ff149325e47eb628ce36f73a1a927ae6cb6021c7ac4
RIPEMD-160(SHA-256(Q)): cbe57ebe20ad59518d14926f8ab47fecc984af49
Signature verified correctly: True

If we plug the RIPEMD-160 value into the address checker, it returns

1Kb76YK9a4mhrif766m321AMocNvzeQxqV

as given in the question.

Solution 2

I'm afraid there are some problems with your sample data. First of all your sample Q is 61 bytes long, but Bitcoin public keys (using secp256k1 curve) should be 65 bytes in their uncompressed form. The Q you supplied does not verify the message correctly, but the Q I have calculated does seem to verify it.

I wrote code that calculates the correct public key for string "StackOverflow test 123" and verifies it using ECDsaSigner. However, the hash for this public key is 1HRDe7G7tn925iNxQaeD7R2ZkZiKowN8NW instead of 1Kb76YK9a4mhrif766m321AMocNvzeQxqV.

Can you please verify that your data is correct and maybe give the exact hash of the message string so that we could try to debug, an incorrect hash can mess things up quite bad. The code I have used is following:

using System;
using System.Text;
using System.Security.Cryptography;

using Org.BouncyCastle.Math;
using Org.BouncyCastle.Math.EC;
using Org.BouncyCastle.Asn1.X9;
using Org.BouncyCastle.Crypto.Signers;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Utilities.Encoders;

public class Bitcoin
{
  public static ECPoint Recover(byte[] hash, byte[] sigBytes, int rec)
  {
    BigInteger r = new BigInteger(1, sigBytes, 0, 32);
    BigInteger s = new BigInteger(1, sigBytes, 32, 32);
    BigInteger[] sig = new BigInteger[]{ r, s };
    ECPoint Q = ECDSA_SIG_recover_key_GFp(sig, hash, rec, true);
    return Q;
  }

  public static ECPoint ECDSA_SIG_recover_key_GFp(BigInteger[] sig, byte[] hash, int recid, bool check)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    int i = recid / 2;

    Console.WriteLine("r: "+ToHex(sig[0].ToByteArrayUnsigned()));
    Console.WriteLine("s: "+ToHex(sig[1].ToByteArrayUnsigned()));

    BigInteger order = ecParams.N;
    BigInteger field = (ecParams.Curve as FpCurve).Q;
    BigInteger x = order.Multiply(new BigInteger(i.ToString())).Add(sig[0]);
    if (x.CompareTo(field) >= 0) throw new Exception("X too large");

    Console.WriteLine("Order: "+ToHex(order.ToByteArrayUnsigned()));
    Console.WriteLine("Field: "+ToHex(field.ToByteArrayUnsigned()));

    byte[] compressedPoint = new Byte[x.ToByteArrayUnsigned().Length+1];
    compressedPoint[0] = (byte) (0x02+(recid%2));
    Buffer.BlockCopy(x.ToByteArrayUnsigned(), 0, compressedPoint, 1, compressedPoint.Length-1);
    ECPoint R = ecParams.Curve.DecodePoint(compressedPoint);

    Console.WriteLine("R: "+ToHex(R.GetEncoded()));

    if (check)
    {
      ECPoint O = R.Multiply(order);
      if (!O.IsInfinity) throw new Exception("Check failed");
    }

    int n = (ecParams.Curve as FpCurve).Q.ToByteArrayUnsigned().Length*8;
    BigInteger e = new BigInteger(1, hash);
    if (8*hash.Length > n)
    {
      e = e.ShiftRight(8-(n & 7));
    }
    e = BigInteger.Zero.Subtract(e).Mod(order);
    BigInteger rr = sig[0].ModInverse(order);
    BigInteger sor = sig[1].Multiply(rr).Mod(order);
    BigInteger eor = e.Multiply(rr).Mod(order);
    ECPoint Q = ecParams.G.Multiply(eor).Add(R.Multiply(sor));

    Console.WriteLine("n: "+n);
    Console.WriteLine("e: "+ToHex(e.ToByteArrayUnsigned()));
    Console.WriteLine("rr: "+ToHex(rr.ToByteArrayUnsigned()));
    Console.WriteLine("sor: "+ToHex(sor.ToByteArrayUnsigned()));
    Console.WriteLine("eor: "+ToHex(eor.ToByteArrayUnsigned()));
    Console.WriteLine("Q: "+ToHex(Q.GetEncoded()));

    return Q;
  }

  public static bool VerifySignature(byte[] pubkey, byte[] hash, byte[] sigBytes)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    ECDomainParameters domainParameters = new ECDomainParameters(ecParams.Curve,
                                                                 ecParams.G, ecParams.N, ecParams.H,
                                                                 ecParams.GetSeed());

    BigInteger r = new BigInteger(1, sigBytes, 0, 32);
    BigInteger s = new BigInteger(1, sigBytes, 32, 32);
    ECPublicKeyParameters publicKey = new ECPublicKeyParameters(ecParams.Curve.DecodePoint(pubkey), domainParameters);

    ECDsaSigner signer = new ECDsaSigner();
    signer.Init(false, publicKey);
    return signer.VerifySignature(hash, r, s);
  }



  public static void Main()
  {
    string msg = "StackOverflow test 123";
    string sig = "IB7XjSi9TdBbB3dVUK4+Uzqf2Pqk71XkZ5PUsVUN+2gnb3TaZWJwWW2jt0OjhHc4B++yYYRy1Lg2kl+WaiF+Xsc=";
    string pubkey = "045894609CCECF9A92533F630DE713A958E96C97CCB8F5ABB5A688A238DEED6DC2D9D0C94EBFB7D526BA6A61764175B99CB6011E2047F9F067293F57F5";

    SHA256Managed sha256 = new SHA256Managed();
    byte[] hash = sha256.ComputeHash(Encoding.UTF8.GetBytes(msg), 0, Encoding.UTF8.GetByteCount(msg));
    Console.WriteLine("Hash: "+ToHex(hash));

    byte[] tmpBytes = Convert.FromBase64String(sig);
    byte[] sigBytes = new byte[tmpBytes.Length-1];
    Buffer.BlockCopy(tmpBytes, 1, sigBytes, 0, sigBytes.Length);

    int rec = (tmpBytes[0] - 27) & ~4;
    Console.WriteLine("Rec {0}", rec);

    ECPoint Q = Recover(hash, sigBytes, rec);
    string qstr = ToHex(Q.GetEncoded());
    Console.WriteLine("Q is same as supplied: "+qstr.Equals(pubkey));

    Console.WriteLine("Signature verified correctly: "+VerifySignature(Q.GetEncoded(), hash, sigBytes));
  }

  public static string ToHex(byte[] data)
  {
    return BitConverter.ToString(data).Replace("-","");
  }
}

EDIT I see this is still not commented on or accepted, so I wrote a full test that generates a private key and a public key, then generates a valid signature using the private key. After that it recovers the public key from the signature and hash and uses that public key to verify the signature of the message. Please see below, if there are still some questions please let me know.

  public static void FullSignatureTest(byte[] hash)
  {
    X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
    ECDomainParameters domainParameters = new ECDomainParameters(ecParams.Curve,
                                                                 ecParams.G, ecParams.N, ecParams.H,
                                                                 ecParams.GetSeed());
    ECKeyGenerationParameters keyGenParams =
      new ECKeyGenerationParameters(domainParameters, new SecureRandom());

    AsymmetricCipherKeyPair keyPair;
    ECKeyPairGenerator generator = new ECKeyPairGenerator();
    generator.Init(keyGenParams);
    keyPair = generator.GenerateKeyPair();

    ECPrivateKeyParameters privateKey = (ECPrivateKeyParameters) keyPair.Private;
    ECPublicKeyParameters publicKey = (ECPublicKeyParameters) keyPair.Public;

    Console.WriteLine("Generated private key: " + ToHex(privateKey.D.ToByteArrayUnsigned()));
    Console.WriteLine("Generated public key: " + ToHex(publicKey.Q.GetEncoded()));

    ECDsaSigner signer = new ECDsaSigner();
    signer.Init(true, privateKey);
    BigInteger[] sig = signer.GenerateSignature(hash);

    int recid = -1;
    for (int rec=0; rec<4; rec++) {
      try
      {
        ECPoint Q = ECDSA_SIG_recover_key_GFp(sig, hash, rec, true);
        if (ToHex(publicKey.Q.GetEncoded()).Equals(ToHex(Q.GetEncoded())))
        {
          recid = rec;
          break;
        }
      }
      catch (Exception)
      {
        continue;
      }
    }
    if (recid < 0) throw new Exception("Did not find proper recid");

    byte[] fullSigBytes = new byte[65];
    fullSigBytes[0] = (byte) (27+recid);
    Buffer.BlockCopy(sig[0].ToByteArrayUnsigned(), 0, fullSigBytes, 1, 32);
    Buffer.BlockCopy(sig[1].ToByteArrayUnsigned(), 0, fullSigBytes, 33, 32);

    Console.WriteLine("Generated full signature: " + Convert.ToBase64String(fullSigBytes));

    byte[] sigBytes = new byte[64];
    Buffer.BlockCopy(sig[0].ToByteArrayUnsigned(), 0, sigBytes, 0, 32);
    Buffer.BlockCopy(sig[1].ToByteArrayUnsigned(), 0, sigBytes, 32, 32);

    ECPoint genQ = ECDSA_SIG_recover_key_GFp(sig, hash, recid, false);
    Console.WriteLine("Generated signature verifies: " + VerifySignature(genQ.GetEncoded(), hash, sigBytes));
  }

Comments

[makerofthings7]

@zimdanen , correct, I'm not trying to get info from an Base58 bit coin address (hash). The signature isn't a hash, but also contains enough information for me to figure out the public key, and then convert that key to a hash. I can then compare the computed hash to what I have.

[makerofthings7]

No problem. I added a clarification to prevent other speed readers from doing the same.

[Bruno]

Isn't the point of signature verification to verify the signature against a public key you already know (and trust to belong to the signer)? It seems to defeat the purpose of signing if you're going to verify the signature against the public key given at the same time (without checking for a known public key from the signer instead).

[makerofthings7]

@Bruno, yes, that point is accounted for. The embedded miniature public key, when hashed, should equal the user facing compressed public key hash. Therefore if a signature is valid, and the Extracted public key, when hashed into Base58 form is complete, then the sig is valid and from whom you expect it to be from.

[Adam McArthur]

Hi @makerofthings7, I'm startled with the lack of attention this question received. I'm working on a proper answer for you right now.

[mulllhausen]

is this question talking about extracting the public key from scriptsig?

[makerofthings7]

@mulllhausen No, that's not possible in Bitcoin. ScriptSig uses a different, older version of OpenSSL's signing algorithm. This is regarding the "message signing" feature

[mulllhausen]

@makerofthings7 thanks for clarifying!

[Adam McArthur]

Good observations, but this doesn't answer the question?

[juhovh]

@AdamMcArthur I understood the latest question to be: "My problem is: How do I extract the key from the signature? (Edit I found the c++ code at the bottom of this post, need it in Bouncy Castle / or C#)" I basically converted the C++ code in question to BouncyCastle & C#, BouncyCastle uses a lot of different names for crypto parameters than the sample OpenSSL code. Which question are you answering?

[Adam McArthur]

Apologies, I didn't see your "edit". I've been going through the Bitcoin source code though, and I found that it's not actually possible to retrieve a public key from the signature?

[juhovh]

@AdamMcArthur As mentioned on the link, it indeed IS possible to retrieve a public key from the MESSAGE SIGNATURE, it contains the 2-bit information about which point is the correct public key. In the latter edited part of my code I am also showing how that 2-bit information is calculated, translated directly from the Bitcoin sources.

[juhovh]

@AdamMcArthur For more information, see the source code github.com/bitcoin/bitcoin/blob/… and differences between "CKey::Sign" and "CKey::SignCompact" and also "CPubKey::Verify" and "CPubKey::VerifyCompact". The Compact versions are the special signatures for messages that support key recovery, the sign and verify versions are usual DER encoded signatures used widely around the net.

[Adam McArthur]

Thanks @juhovh, I'll check it out.

[makerofthings7]

Sorry for the delay in accepting and awarding the bounty. I'm accepting and awarding on the faith that this works and will be testing as soon as I get back (unexpected travel inconveniently on the same day a the end of the bounty). I am very curious how you learned the OpenSSL terminology and BC's to such a level that you can "translate" one to another.

[juhovh]

No problem, if you find problems with my code just let me know, I'm not going anywhere. There might be some corner cases to check, but I can help with that, just run as much data through it as you can and try to break it. And one thing I forgot to mention is that Bitcoin verifies the signature differently. It seems to recover the public key from the signature and compare it to a known public key. This doesn't work in your case, because you do not know the public key, only the hash. So you need to verify the public key matches the hash, and then verify the signature "traditionally".

[juhovh]

Earlier I used several months to write a SSL/TLS library from scratch using C#, and during the process studied quite much OpenSSL code and used BC for all my local ECC related testing. I also wrote a bit of actual ECC code for for fun, so I got more familiar with the parameters. So I just happened to know the two libraries.

[makerofthings7]

I would be very interested in seeing the SSL/TLS library, if you're open to sharing it.

[makerofthings7]

There seems to be an issue converting the Public key back into a Bas58 address. In the question above, I included the full code to convert your extracted public key Q value into a Base58 hash.

[makerofthings7]

Here is an interactive URL that works exactly like my code in the answer above. When I paste the extracted key, the data doesn't match the expected pubkey hash gobittest.appspot.com/Address

[makerofthings7]

A full version of this is available at github.com/makerofthings7/Bitcoin-MessageSignerVerifier Any assistance is appreciated.

[makerofthings7]

hmmm perhaps this has to do with "compressed keys". I'm not sure what they are github.com/nanotube/supybot-bitcoin-marketmonitor/commit/… and here is a description of compressed keys in general bitcoin.stackexchange.com/a/11301/1878

[juhovh]

Sorry, I didn't get email notifications about these from stackoverflow, I need to check my settings. I will look into this ASAP.

[makerofthings7]

This code is fantastic, and works perfectly with the QT clients. I'm having trouble creating a signature that is able to be verified by this code. Would you assist me with this?