Elliptic Curve Cryptography

By: Bryan Wee

Up until now, we have dealt with the math behind elliptic curves, without any insight into their practical use cases. Enough with the math, let us see how elliptic curves can be used in public key cryptography, specifically in blockchains.

Elliptic Curve Key Pairs

Elliptic curves can be easily extended to implement public key cryptography. We start by defining what a private-public key pair constitutes. Let private key $q$ be an unsigned integer. Then, we fix a point on the curve and call it the generator point $G$. The public key $Q$ is a point on the curve, calculated like so:

$Q=qG$

To understand why it is reasonable to define our keys this way, we revisit the discrete logarithm problem.

• Scalar multiplication is easy: Given an integer $q$ and generator point $G$, it is easy to solve for $Q$.

• The inverse is almost impossible: Given curve points $Q$ and $G$, it is computationally infeasible to solve for $q$.
  

In other words, private key owners can calculate their public keys. But they cannot infer someone else's private key, even if given the corresponding public key. This implementation of private-public key pair is powerful and can be extended to implement complex cryptographic schemes.

Elliptic Curve Digital Signature Algorithm

Among the many schemes elliptic curve cryptography supports, Elliptic Curve Digital Signature Algorithm (ECDSA) is easily the most ubiquitous in the realm of blockchains.

But before plunging into ECDSA, maybe we should first ask ourselves...

What is a Digital Signature?

Digital signatures are cryptographic proofs that can be attached to some data to authenticate its origin. For instance, say Alice wants to publish an authenticated message to a network. She can append a signature to the initial message. After which, anyone in the network can process the signature and verify that the message indeed originates from Alice.

Ideally, signatures must be:

• Unforgeable. No one else can produce Alice's signature.

• Publicly verifiable. Anyone can verify that the signature belongs to Alice.
  

Bear these in mind. We will soon convince ourselves why elliptic curves can create signatures that embody these properties.

A deep dive into ECDSA

ECDSA is essentially an implementation of digital signatures that uses elliptic curves. It takes in a message alongside a private key, and outputs a digital signature.

Let us jump straight into the algorithm. Alice has a message $m$ that she would like to authenticate. She also has her private key $q$ and public key $Q$that is associated with some elliptic curve over a finite field. To calculate her signature, Alice will:

1. Generate a random number $k$.

2. Then, calculate the elliptic curve point $R$, and let $r$ be the x-coordinate of $R$.
   • $R=kG$
   • $r=R.x$
   

3. Next, calculate the signature proof $s$.
   $s\equiv k^{-1}\cdot \left[hash\right(m)+qr]\left(modp\right)$

4. Her final signature is given by $\{r,s\}$.
   

Why is this a signature? To see why, we revisit the two important properties of digital signatures.

Firstly, the signature is unforgeable as there is no way to compute $\{r,s\}$ without Alice's private key. Her public key alone cannot derive $\{r,s\}$ because of the discrete logarithm problem!

Secondly, the signature is also publicly verifiable. Anyone with message $m$ and signature $\{r,s\}$ can calculate the signer's public key $Q$.

1. Plug in $r$ into the elliptic curve equation to infer $R$. There should only be up to two possible candidates of $R$ (See diagram below).

2. For each possible value of $R$, recover public key $Q$.
   $Q=r^{-1}\cdot (s\cdot R-hash(m)\cdot G)$

3. Check that either of the candidate public keys belongs to Alice.

Simple algebra reveals why our recovery formula works.

$s\cdot R-hash\left(m\right)\cdot G=sk\cdot G-hash\left(m\right)\cdot G$
$=(sk-hash(m\left)\right)\cdot G$
$=rq\cdot G$
$=r\cdot Q$
$\therefore Q=r^{-1}\cdot (s\cdot R-hash(m)\cdot G)$

The ability to recover public keys allows Alice to embed her identity into her signature. Since there are two candidate points $R$ (i.e., higher or lower) to choose from, which leads to two different public keys, she will need to specify which of the two is hers. This can be done by prepending the signature with a single boolean byte $v$. In all, the new signature format will be $\{v,r,s\}$.

Cryptographic Curves

Before ECDSA can be used, participants must agree upon the curve parameters (namely, $a$, $b$, $p$, and $G$). It turns out that certain parameters are more secure than others. For instance, if $G$ is poorly chosen, or $p$ is a small prime, the resultant elliptic curve will be easier to break.

Over the years, a few standards have proven themselves worthy. To name a few, there are secp256k1, NIST P-384, and Curve25519.

ECDSA in Blockchains

Elliptic curve signatures underpin identity authentication in blockchains like Ethereum and Bitcoin, where a transaction is accompanied by a signature that authenticates its sender.

Ethereum and Bitcoin use the secp256k1 curve.

$y^2=x^3+7\left(modp\right)$

where $p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$.

The generator point $G$, represented in hexadecimal, is as follows.

secp256k1 operates with 256-bit integers, much like its sibling NIST P-256. However, the latter is more widely used as it has some special properties that allow slightly faster computation. The reason why secp256k1 might be preferred in blockchains is a very interesting piece of cryptographic history, involving governments and espionage. So do give it a search if you are interested!

Conclusion

It seems as if we have hiked along the mystical elliptic curve and back. In our trodden journey, we have unearthed the curve and its properties, restricted it to a finite field, transformed it onto a projective space, and put it to cryptographic use.

For the uninitiated, all this math might have been a little dizzying. Nevertheless, the elliptic curve has an undeniable presence in the world of cryptography and cryptocurrency. Its use extends beyond signatures, finding use from hybrid encryption schemes to zk-proofs. As research in cryptography continues to advance, it is clear that elliptic curves will have a vital place in this forage for years to come.