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.

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.

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 »