BTC#: Digital Signature Code

Series: BTC# – Learning to Program Bitcoin in C#

« Previous: Digital Signatures

Next: BTC#: Endianness »

Programming Bitcoin tackles verification first and signing second. I wrote my code in the opposite order because that’s what made sense to me.

SignatureDataFlow

The book’s Python code has a class called PrivateKey.. I created a class called KeyPair that does much the same thing. The constructor takes the secret and generates a public key from it.

public KeyPair(BigInteger secret)
{
    PrivateKey = secret;
    PublicKey = new PublicKey(PrivateKey * Secp256k1.G);
}

At this stage, the PublicKey class is just a wrapper for a point on the elliptic curve. Later we’ll add verification and serialisation methods.

public class PublicKey
{
    public EllipticCurveFiniteFieldPoint Point { get; }

    public PublicKey(EllipticCurveFiniteFieldPoint point)
    {
        Point = point;
    }
}

The unit test for the constructor takes some private and public key values from Chapter 4 of Mastering Bitcoin.

The next piece of data we need to generate is the document hash.

var z = Hash.DoubleSha256("my message").ToUnsignedBigInteger();

I’ve needed to create two helper methods here: one to do the double hashing and the other to convert the byte array into the BigInteger that the signing code expects. These go into a Hash class.

public static class Hash
{
    public static byte[] DoubleSha256(byte[] buffer)
    {
        var sha256 = SHA256.Create();
        var round1 = sha256.ComputeHash(buffer);
        return sha256.ComputeHash(round1);
    }

    public static byte[] DoubleSha256(string message)
    {
        return DoubleSha256(Encoding.UTF8.GetBytes(message));
    }
}

I’ve used the .NET framework’s built in SHA-256 algorithm from the System.Security.Cryptography namespace. Bitcoin requires the data to be double-hashed to protect against a collision attack. I’ve added an overload that takes a string parameter, assumes it to be UTF-8 encoded, and uses that as the byte sequence to hash.

The second helper method that I’ve written takes the result of the hashing algorithm, a sequence of 32 bytes, and turns it into a BigInteger. BigInteger has a constructor that takes an array of bytes. There are a couple of wrinkles, however. The first is that, similar to when we create BigIntegers from a hexadecimal string, we need to get the sign right by making the most significant bit zero. The second is that the byte-array constructor assumes that the bytes arrive least-significant byte first, whereas the result of the hashing operation comes out most-significant byte first. The helper method reverses the byte array and bolts a zero on the end.

public static class ByteArrayExtension
{
    public static BigInteger ToUnsignedBigInteger(this byte[] buffer)
    {
        //Little-endian byte order.
        return new BigInteger(buffer.Reverse().Concat(new byte[] { 0 }).ToArray());
    }
}

With those pieces in place, it’s easy to create the Signature class using the formulae provided in the book.

public Signature(KeyPair kp, BigInteger documentHash, BigInteger ephemeralPrivateKey)
{
    R = (ephemeralPrivateKey * Secp256k1.G).X.Value;
    var kInv = BigInteger.ModPow(ephemeralPrivateKey, Secp256k1.N - 2, Secp256k1.N);
    S = ((documentHash + R * kp.PrivateKey) * kInv).Mod(Secp256k1.N);
    //S = s > Secp256k1.N / 2 ? Secp256k1.N - s : s; //Low-s malleability
}

The code provided in the book contains a line to switch high-s values to low-s values if they’re on the top half of the curve. (Remember that the curve is symmetric around N/2.) At the moment I have this commented out as the sample values given earlier in the chapter, which I’m using in my unit tests, don’t take account of this.

[TestMethod]
public void constructor_createFromKeyAndHash()
{
    //Values from Programming Bitcoin Ch 3.
    //"Brain wallet". Don't do this.
    var secret = Hash.DoubleSha256("my secret").ToUnsignedBigInteger();
    var kp = new KeyPair(secret);
    var z = Hash.DoubleSha256("my message").ToUnsignedBigInteger();
    var k = new BigInteger(1234567890); //Fixed to get a known result
    var r = BigInteger.Parse("002b698a0f0a4041b77e63488ad48c23e8e8838dd1fb7520408b121697b782ef22", NumberStyles.AllowHexSpecifier);
    var s = BigInteger.Parse("00bb14e602ef9e3f872e25fad328466b34e6734b7a0fcd58b1eb635447ffae8cb9", NumberStyles.AllowHexSpecifier);

    var sig = new Signature(kp, z, k);

    Assert.AreEqual(r, sig.R);
    Assert.AreEqual(s, sig.S);
}

We can use a public key to verify that a signature is valid.

SignatureEquation

The derivation of these formulae is described in the book and the implementation is quite straightforward. We define

u = z / s; v = r / s

and solve for R

public bool Verify(Signature sig, BigInteger documentHash)
{
    var sInv = BigInteger.ModPow(sig.S, Secp256k1.N - 2, Secp256k1.N); //Fermat's Little Theorem
    var u = (documentHash * sInv).Mod(Secp256k1.N);
    var v = (sig.R * sInv).Mod(Secp256k1.N);
    var total = u * Secp256k1.G + v * Point;
    return total.X.Value == sig.R;
}

The return value of the Verify method is a boolean indicating whether the signature is valid for the supplied signature and document hash.

« Previous: Digital Signatures

Next: BTC#: Endianness »

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s