Public / Private Keys and Signing

It’s common knowledge today that a blockchain is a form of a distributed ledger that holds transactions. These transactions are collected in a block and added to the ledger with a reference to the previous block by means of hashes so that a block, once added, can no longer be changed. Well, in theory, a block could change, but given the computing power necessary to calculate a hash for a block and the fact that blockchain is distributed it’s extremely difficult. You would need to have 51% of the computing power to do so (https://learncryptography.com/cryptocurrency/51-attack).

This process of calculating a hash for a block is one part in keeping the blockchain trusted. However, what is stopping users from submitting transactions on funds that they don’t actually own? How is it, that I cannot simply publish a transaction that says “transfer 1000 of this cryptocurrency to someone else”.

To understand what’s stopping us from doing so, we need to look at a second part of blockchain technology: public/private key pairs and using them for signatures.

We will be using C# code and .NET Core to work our way through this concept.

Public/private key pair

Asymmetrical cryptography is a technique that uses pairs of keys:

1. A public key, visible to anyone.
2. A private key, only known to the owner.

The private key is essentially a randomly generated number. The public key can be derived from that public key using what’s called Elliptic Curve Cryptography. We can use ECC for encryption, digital signatures, pseudo-random generators and other tasks. Bitcoin uses a specific elliptic curve called secp256k1 over the finite (prime) field of (2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1) number of elements, using the generator point (on the curve) G=(x, y) where (in hexadecimal):

x=79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y=483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Don’t worry, we will not dive any further into the mathematical details of these ECC algorithms. If you want to know more, check out this article: https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography

In simple code, this is what we do to get the public key from a (random) private key:

string privateKey = "123456789";

string publicKey = GetPublicKeyFromPrivateKey(privateKey);

Console.WriteLine(publicKey);

The method GetPublicKeyFromPrivateKey looks like this:

private static string GetPublicKeyFromPrivateKey(string privateKey)

{

    var p = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.HexNumber);

    var b = (BigInteger)7;

    var a = BigInteger.Zero;

    var Gx = BigInteger.Parse("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", NumberStyles.HexNumber);

    var Gy = BigInteger.Parse("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", NumberStyles.HexNumber);


 
    CurveFp curve256 = new CurveFp(p, a, b);

    Point generator256 = new Point(curve256, Gx, Gy);


 
    var secret = BigInteger.Parse(privateKey, NumberStyles.HexNumber);

    var pubkeyPoint = generator256 * secret;

    return pubkeyPoint.X.ToString("X") + pubkeyPoint.Y.ToString("X");

}

The classes CurveFp and Point can be found in the Github repository for this article: https://github.com/sander-/working-with-digital-signatures

If you run this code, you will get following output:

5004D7D9C2A3B2D675ADA618D9CEDA55D1F6A9FDF263E24DAA8CBEA586AF2B2BF1A40DB729D5E9E1B9CE60D4CE8F8F62A12C72E341EB3015B9D349805CD876CCB

Obviously, having 123456789 as a private key is not particularly safe. But from the public key, there is no way to derive the value of the private key.

Signatures

The process of signing a message entails that you generate a hash that is based on your private key. As you know, hashing is a one-way process, so there’s no way to derive the private key from this hash. However, it is possible to verify whether this hash is accurate if you have the public key of the signer. A digital signature scheme typically consists of 3 algorithms:

1. A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key.
2. A signing algorithm that, given a message and a private key, produces a signature.
3. A signature verifying algorithm that, given the message, public key and signature, either accepts or rejects the message’s claim to authenticity.

In blockchain, the signature algorithm is the Elliptic Curve Digital Signature Algorithm or ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm). We are not diving into the mathematics of this algorithm. We are, however, going to borrow functions from the BouncyCastle framework (https://www.bouncycastle.org/) to work with ECDSA.

The steps to create a signature for a message are simple.

1. Write the message to be signed.
2. Create a public/private key pair; to generate the public key from the private key we use the secp256k1 algorithm from before.
3. Generate the signature for the message using a signer object.

Strictly speaking, to sign a message we only need a private key. However, signing a message and not giving anyone the public key to verify the signature is pretty pointless.

In code, that reads as follows.

// Step 1

var message = "Hello World!";


 
// Step 2

var privateKey = "68040878110175628235481263019639686";

var publicKey = GetPublicKeyFromPrivateKeyEx(privateKey);


 
// Step 3

var signature = GetSignature(privateKey, message);

Let’s first look at our new method for generating a public key.

public static string GetPublicKeyFromPrivateKeyEx(string privateKey)

{

    var curve = SecNamedCurves.GetByName("secp256k1");

    var domain = new ECDomainParameters(curve.Curve, curve.G, curve.N, curve.H);


 
    var d = new BC.Math.BigInteger(privateKey);

    var q = domain.G.Multiply(d);


 
    var publicKey = new BC.Crypto.Parameters.ECPublicKeyParameters(q, domain);

    return Base58Encoding.Encode(publicKey.Q.GetEncoded());

}

For the sake of readability, the return value of the method is base58 encoded (https://en.wikipedia.org/wiki/Base58).

If we call this method we get our public key, based on the private key we gave as input. So, our public/private key pair contains these values respectively:

Public key: Nr6MbFUfMovKCX4vd5YpQnRYsN4rq6pNPEEBKmicAEwwuYLpJrt5LsRvfvR2G8pJ5rMchEMWDYJ7rdYGY7PjxHEa

Private key: 68040878110175628235481263019639686

The method GetSignature is this.

public static string GetSignature(string privateKey, string message)

{

    var curve = SecNamedCurves.GetByName("secp256k1");

    var domain = new ECDomainParameters(curve.Curve, curve.G, curve.N, curve.H);


 
    var keyParameters = new

            BC.Crypto.Parameters.ECPrivateKeyParameters(new BC.Math.BigInteger(privateKey),

            domain);


 
    ISigner signer = SignerUtilities.GetSigner("SHA-256withECDSA");


 
    signer.Init(true, keyParameters);

    signer.BlockUpdate(Encoding.ASCII.GetBytes(message), 0, message.Length);

    var signature = signer.GenerateSignature();

    return Base58Encoding.Encode(signature);

}

The outcome of this method is again base58 encoded to make it easier to read.

AN1rKpbUR7H24S46uQBuf4tY6saBQgV4tY6dk6K9LdkW7sQ4qvyJwXkRTvxJVKY9vCPaTaEzBVc2T5RQeugiwTAsXXagHC2eZ

 

We can pass this message signature to someone else. The other party will obviously not have the private key to recreate that signature. But we can also publish the public key and thereby allow the other party to do two things.

1. The other party can verify that the message was signed by the keeper of the private key that belongs to or pairs with the public key.
2. The other party can also verify that the message was not changed by someone else that didn’t have this private key.

Either a change in the message or in the public key would immediately be recognized as the signature would no longer match. Only the original creator of the message together with his private key can make it so the signature is valid.

To verify the signature, we use this code.

public static bool VerifySignature(string message, string publicKey, string signature)

{

    var curve = SecNamedCurves.GetByName("secp256k1");

    var domain = new ECDomainParameters(curve.Curve, curve.G, curve.N, curve.H);


 
    var publicKeyBytes = Base58Encoding.Decode(publicKey);


 
    var q = curve.Curve.DecodePoint(publicKeyBytes);


 
    var keyParameters = new

            BC.Crypto.Parameters.ECPublicKeyParameters(q,

            domain);


 
    ISigner signer = SignerUtilities.GetSigner("SHA-256withECDSA");


 
    signer.Init(false, keyParameters);

    signer.BlockUpdate(Encoding.ASCII.GetBytes(message), 0, message.Length);


 
    var signatureBytes = Base58Encoding.Decode(signature);


 
    return signer.VerifySignature(signatureBytes);

}

As you can see, nowhere do we specify the private key. The BouncyCastle framework does most if not all of the heavy lifting here in providing a signer object that uses ECDSA.

Transactions in the blockchain

The fact that we can have messages from a known source and that these messages cannot be altered by a third party is essential to transactions in a blockchain. Instead of an unstructured message, transactions have a clear structure. This structure looks something like this:

class Transaction

{

    public string FromPublicKey { get; internal set; }

    public string ToPublicKey { get; internal set; }

    public int Amount { get; internal set; }

    public string Signature { get; internal set; }


 
    public override string ToString()

    {

        return $"{this.Amount}:{this.FromPublicKey}:{this.ToPublicKey}";

    }

}

The From and To properties of the transaction are not simple addresses. They are public keys that help verify the sender and the content of the transaction. The transaction and its signature can be created like this.

var privateKey = "68040878110175628235481263019639686";

var publicKey = GetPublicKeyFromPrivateKeyEx(privateKey);

var transaction = new Transaction();

transaction.FromPublicKey = publicKey;

transaction.ToPublicKey = "QrSNX7KxzGnQqauPiXKxP58nhukU252RKAmSqg17L8h7BpU984g4mxHck6cLzhArADz2p1xo3BwAsbiaLhQaziyu";

transaction.Amount = 10;

transaction.Signature = GetSignature(privateKey, transaction.ToString());

Following this code, you can see that the message is signed by the owner of the private key that pairs with the public key. By verifying the signature, you can prove that:

1. The creator of the transaction is the holder of the private key belonging to the sender/creator of the transaction.
2. The receiver is the original intended receiver.
3. The amount has not been altered.

Changing any of the parameters (FromPublicKey, ToPublicKey or Amount) would invalidate the signature and therefore make the entire transaction invalid. Verifying the transaction is simple.

bool isValidTransaction = VerifySignature(transaction.ToString(), publicKey, transaction.Signature);

In summary

Signing is a good way to know something is being done by the correct person. This means we can trust that someone is actually doing what they say they are. In the real world signatures can be faked. The digital ones cannot. Digital signatures act like electronic “fingerprints.” In the form of a coded message, the digital signature securely associates a signer with a message in a recorded transaction. If you want to know person A sent something, make them sign it before moving forward. If there’s any dispute, check the signature. This is a vital part of the blockchain.

The source code for this post can be found at: https://github.com/sander-/working-with-digital-signatures.