- Public Key Cryptography
- Signing and Verification
- Verification in depth
- Programming Signature Verification
- Signing in depth
- Programming Message Signing

This is the second part of our primer on elliptic curve cryptography in Clojure (here's part one), where we dive into the basics of public key cryptography, the advantages of using elliptic curves for these operations, and how we can sign and verify signatures in the Bitcoin protocol.Let's get started!

Cryptography has been used to share secrets since Ancient Greek times, but since then, it has expanded from hiding messages from adversaries to enabling people to prove that they know a secret without revealing the secret itself.

In the context of Bitcoin, we don't care about the encryption that cryptographic methods afford, but rather this second notion of proving the knowledge of a secret without revealing the secret to external parties. Ownership of bitcoin is established through the possession of a secret number, also known as a private key, that allows for the decentralized nature and security model of the protocol.

When digitally transacting with fiat currencies, provenance of your funds is attested to by the financial institution, which has custody over your assets. In these scenarios, you are at the mercy of the financial institution, which you and the party you are transacting with have to trust as being legitimate. In contrast, with Bitcoin, the private key (secret) you hold, is what gives you access to your funds and allows you to transact with others on the network. This allows for the trust-minimized transactions that Bitcoin is touted for pioneering.

Private keys are generated adjacent to the Bitcoin protocol and can be stored in a file or in a digital "wallet" that keeps track of your funds and acts as an interface to make transactions with others. Think of it like your checking account. For a transaction to be included into the Bitcoin blockchain, the transferring party must provide a digital signature that can only be generated by this secret private key. And thus, anyone who has a copy of the secret key has access to the bitcoin associated with it. This digital signature is also called a witness, which acts as an attestation to the ownership of the bitcoin being spent.

Each private key comes with an associated public key, which is shared freely online. The public key acts as a bank account number that you provide to someone who wants to transfer you funds. And the complimentary private key acts as the secret PIN on your debit card, which allows you to control your money.

When you spend your bitcoin, you present your public key, and your digital signature (which is made anew each time you sign, but is generated from the same private key you hold) in a transaction that specifies the recipient. This transaction is then broadcast to the other nodes in the bitcoin network, and through this presentation of public key and associated signature, all participating nodes can verify that the transaction is valid, confirming it and allowing it to be included in the blockchain.

Elliptic curve cryptography is how we generate these digital signatures and ensure that they can be verified quickly, easily, and securely. Before the maths behind elliptic curves were applied as a means for public key cryptography, the principle approach was called Diffie-Hellman, from which elliptic curve cryptography was born.

Diffie-Hellman, similarly, uses the discrete logarithm problem as its central asymmetric operation, which is easy to compute in one direction, and intractable in the other. To recap, the discrete logarithm problem concerns finding a logarithm of a number within a finite field using modulo arithmetic, like we introduced earlier. And as discussed before, prime fields are of particular interest for cryptography because, over a prime field, exponentiation turns out to be a relatively easy operation, while the inverse, computing the logarithm, is very difficult.

To generate a key pair in the discrete logarithm system you calculate $$P = g^e \mod p$$ where $$p$$ is a large prime $$P$$ is the public key, and $$e$$ is the private key. The discrete log problem using the equation above is simply finding $$e$$ given $$P$$, $$g$$, and $$p$$. And it turns out that for large enough $$p$$ values this is extremely difficult to do because this equation gets rapidly more difficult as key length increases, even though finding $$g$$ given the rest is trivial.

Elliptic curve cryptography also uses a discrete logarithm problem but with the finite cyclic groups we covered in the last part that impart greater security than Diffie-Hellman for a given key size. They are slightly more complicated, but mathematically more efficient for cryptography because the discrete logarithm problem that it is representative of is a bit harder to solve than other methods and so elliptic curves enable shorter key sizes and less computation when calculating the points—a 256 bit elliptic curve key gives you the same security as a 3000 bit Diffie-Hellman key. Given the immutable nature of blockchains, and the hard block size limit in Bitcoin, it is no surprise that elliptic curve cryptography is the preferred method given its efficiencies.

To prove ownership of the private key, we must do some operation that can prove we know a secret number without revealing the secret itself, and that can be verified by third parties without requiring interaction. This is done by coming up with a target number, and including this target number in a calculation with our secret, which results in the target number. This is based on the finite cyclic group mathematics that posit without knowing the secret number included in the calculation, being able to hit the target number would be computationally infeasible.

This calculation is based on the digital signature algorithm, which in the case of Bitcoin is the Elliptic Curve Digital Signature Algorithm (ECDSA). And the secret in our case is the variable $$e$$, which satisfies the equation $$eG = P$$, where $$e$$ is the private key, $$P$$ is the public key, and $$G$$ is the generator point for the finite cyclic group.

The target number we propose to hit is the $$x$$-coordinate of a point on the elliptic curve that is generated through multiplying a random 256-bit number that we denote with the variable $$k$$ and the generator point $$G$$. The point is represented by the variable $$R$$, so $$kG = R$$, and the coordinate of interest, $$x$$, is represented by the lower-case $$r$$.

Now, we claim that solving the following equivalent to the discrete log problem: $$uG + vP = kG$$ where $$k$$ was chosen randomly, $$u, v \ne 0$$ are scalar multiples that can be chosen by the signer, and $$G$$ and $$P$$ are publicly available. This is due to the fact that $$uG + vP = kG$$ implies $$vP = (k-u)G$$ and we can further reduce this equation by dividing by $$v$$: $$P = ((k - u)/v)G$$

And if we know $$e$$, we have: $$eG = ((k-u)/v)G$$ or $$e = (k-u)/v$$ which means that any $$(u, v)$$ that satisfies the preceding equation will work. But if we don't know $$e$$ we have to adjust $$(u, v)$$ until we satisfy $$e = (k-u)/v$$, but solving this means we have solved $$P = eG$$ without knowing $$e$$, which implies we would be breaking the discrete logarithm problem.

So to provide a correct $$u$$ and $$v$$, you either have to break the discrete logarithm problem or know the secret $$e$$, and since we can assume the discrete logarithm problem is unbreakable with current techniques, it is safe to assume that whoever came up with $$u$$ and $$v$$ must also know $$e$$.

Now we have to incorporate the contract that gets fulfilled as a result of calculating the target into the calculation itself. This is called the signature hash, which is a deterministic function that takes arbitrary data of any size and transforms it into data of fixed size. The hash acts as a fingerprint of the message being signed, which contains the target $$r$$, which anyone verifying the message knows.

We can denote the signature hash with the variable $$z$$, and is incorporated into our $$uG + vP$$ calculation like so $$u = z/s$$, where $$s$$ is determined by an equation we will cover in just a bit. We also posit that $$v = r/s$$. And since $$r$$ is used in the calculation of $$v$%, we now have our target and signature hash mixed into our calculation.

This is the basis of the signature algorithm and the two numbers in a signature are $$r$$ and $$s$$.

To make the equation work, we can calculate $$s$$ by simple algebraic substitution.

$$uG + vP = R = kG$$

$$uG + veG = kG$$

$$u + ve = k$$

$$z/s + re/s = k$$

$$(z + re)/s = k$$

$$s = (z + re)/k$$

Verification is then a straightforward, where we we use similar substitution rules to find $$kG$$, and thus the target, ascertaining that the signature being presented can only have been made by the possessor of the private key $$e$$:

$$uG + vP$$

$$= (z/s)G +(re/s)G$$

$$ = ((z + re)/s)G$$

$$= ((z + re)/((z + re)/k))G $$

$$= kG$$

$$= R$$

While it seems easier to just reveal $$k$$, instead of just $$r$$, if we were to reveal $$k$$, then you can calculate $$e$$ like this:

$$uG + vP = R$$

$$uG + veG = kG$$

$$kG - uG = veG$$

$$(k - u)G = veG$$

$$k - u = ve$$

$$(k - u)/v = e$$

This would defeat the whole purpose of the signature, but we can reveal $$R$$ as it is too difficult to separate $$k$$ from $$G$$ owing to the discrete logarithm problem. Moreover, we should only be using true random numbers for $$k$$ because even accidentally revealing $$k$$ of a known signature is effectively revealing our private key and losing sole control of the associated bitcoin.

Signatures sign a fixed-length value, which in Bitcoin's case, is 256 bits (32 bytes), which is not a coincidence as the thing we will be signing is a scalar for the generator point $$G$$. To guarantee we are signing 32 bytes, we hash the document first with Bitcoin's hashing function, hash256 (two rounds of sha256) guaranteeing the thing that will be signed is exactly 32 bytes. The result of the hash is called the **signature hash** or $$z$$ as discussed above.

The signature we are verifying has two components $$(r, s)$$, where $$r$$ is the $$x$$-coordinate of the random target point $$R$$, and the formula for $$s$$ is as above $$s = (z + re)/k$$. Keep in mind that, as the signer, we alone know $$e$$, $$k$$, and $$z$$.

We will now construct $$R = uG + vP$$ by defining $$u$$ and $$v$$ this way like we did before: $$uG + vP = ((z + re) / ((z + re)/k))G = kG = R$$. Thus we now have chosen $$u$$ and $$v$$ such that they generate $$R$$ as intended, and we used $$r$$ in the calculation of $$v$$, proving we knew what $$R$$ would be And we know that the only way to know the details of $$R$$ before hand is to know $$e$$.

So here is how we would verify a signature. Given $$(r, s)$$ as the signature, $$z$$ as the hash of the thing being signed, and $$P$$ as the public key of the signer, wee calculate $$u = z/s$$, $$v = r/s$$ and then calculate $$uG + vP = R$$ and if our resultant $$R$$'s $$x$$ coordinate equals the $$r$$ in the signature, we know we have a valid signature.

With the algebra in place, we now can program a signature verification algorithm. We will get back to the creation of signatures shortly, don't worry! First let's make a record to house our signatures:

```
(defrecord Signature [r s])
```

Next we will make a function that takes in the public key, the variable `z`

and the signature as arguments and returns true if the signature is valid, and false if it is not. We can use Fermat's Little Theorem to derive `1/s`

because our `n`

is prime. Then we calculate `u`

and `v`

with their respective formulas under modulo arithmetic and then we derive `R`

by adding `uG`

to `vP`

, and the last step is to check if the `x`

-coordinate of the calculated `R`

is the same as the 'r` revealed.

```
(defn verify-signature [p z {:keys [r s]}]
(let [s_inv (mod-expt s (- N 2) N)
u (mod (* z s_inv) N)
v (mod (* r s_inv) N)
total (+ (* u G) (* v p))]
(= r (:num (:x total)))))
```

So given a public key that is a point on the secp256k1 curve and a signature hash $$z$$ we can verify whether a signature is valid or not. Now let's move onto creating signatures.

Since we know how verification works, signing is simple, we just have to figure out what $$k$$ and thus $$R = kG$$ to use, and we do this by choosing a random $$k$$.

So with $$z$$ (which we will compute later) and possession of the private key $$e$$,such that $$eG = P$$, we choose a random 256-bit number $$k$$, calculate $$R = kG$$ to get $$r$$, and finally calculate $$s = (z + re)/k$$ to get our signature, which is $$(r, s)$$

It is important to note that along with the public key $$P$$, $$z$$ must also be known by the verifier

To program message signing we first define a record, `PrivateKey`

that will be used to host our secret number. We also need a constructor function that creates private keys by multiplying our secret number by our generator point `G`

which we defined in part one.

```
(defrecord PrivateKey [secret point])
(defn ->PrivateKey [s]
(PrivateKey. s (* s G)))
```

Next we need to find a secure way to come up with a random unique `k`

for each signature that cannot be reused since, as we proved earlier, revealing `k`

is equivalent to revealing your secret. Pseudorandom number generators found in standard libraries are not secure enough for use in cryptographic applications that need to ensure that no one can find out your secret.

To combat this, there is a deterministic `k`

generation standard that uses the secret and `z`

to create a unique, deterministic `k`

for every new signature. The specification is found in RFC 6979 and one possible implementation written in Clojure looks like this:

```
(ns programming-bitcoin.ecc
...
(:require ...
[buddy.core.mac :as mac]])
(:import ...
(java.math BigInteger))
(defn num->bytes [length n]
(let [a (.toByteArray (biginteger n))
l (count a)
zeros (repeat (- length l) (byte 0))]
(if (> l length)
(byte-array (drop (- l length) (seq a)))
(byte-array (concat zeros a)))))
(defn bytes->num [bs]
(->> bs
(into [0])
byte-array
BigInteger.))
(defn hmac [key message]
(-> (mac/hash message {:key key :alg :hmac+sha256})))
(defn deterministic-k [secret z]
(let [k (byte-array 32 (byte 0))
v (byte-array 32 (byte 1))
z (if (> z N) (- z N) z)
z-bytes (num->bytes 32 z)
secret-bytes (num->bytes 32 secret)
k (hmac k (byte-array (concat v [0] secret-bytes z-bytes)))
v (hmac k v)
k (hmac k (byte-array (concat v [1] secret-bytes z-bytes)))
v (hmac k v)]
(loop [k k
v v]
(let [v (hmac k v)
candidate (bytes->num v)]
(if (and (<= 1 candidate) (< candidate N))
candidate
(recur (hmac k (byte-array (concat v [0])))
(hmac k v)))))))
```

The specifics of how this algorithm works to ensure a unique `k`

each time is beyond the scope of this article. One topic of interest is that it makes use of an HMAC—hash-based message authentication code—a specific type of message authentication code involving a hash function and a secret key to verify the data integrity. To learn more about HMAC's work, Computerphile has a great video.

With our `deterministic-k`

function to protect us from accidentally revealing our secret, we have all the ingredients we need to make our `sign`

function:

```
(defn sign [{:keys [secret point]} z]
(let [k (deterministic-k secret z)
r (:num (:x (* k G)))
k_inv (mod-expt k (- N 2) N)
s (mod (* k_inv (+ z (* secret r))) N)]
(->Signature r s)))
```

And there we have it. We have now created the ability to both sign and verify a transaction. We can now test it with a `rand-256`

function that returns a random number that we can use for our secret and `z`

to input into the signing algorithm:

```
(ns programming-bitcoin.ecc-test
(:refer-clojure :exclude [+ - * /])
(:require
[buddy.core.nonce :as nonce]
[clojure.test :refer :all]
[programming-bitcoin.ecc :refer :all]))
(defn rand-256 []
(bytes->num (nonce/random-bytes 32)))
(deftest signature-verification
(testing "verifying private key signature"
(let [pk (->PrivateKey (rand-256))
z (rand-256)
sig (sign pk z)
p (:point pk)]
(is (true? (verify-sig p z sig)))))
```

If you've reached this point, congratulations! You now know how to implement a fundamental part of Bitcoin's protocol. The next thing we need to cover is serialization, which helps us transmit data across the network. See you there!