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
In the Signature above, what format is this signature in? PKCS10? (Answer: no, it's proprietary as described here)
how do I extract the public key in Bouncy Castle?
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.
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.