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 qq be an unsigned integer. Then, we fix a point on the curve and call it the generator point GG. The public key QQ is a point on the curve, calculated like so:

Q=qGQ = 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 qq and generator point GG, it is easy to solve for QQ.

  • The inverse is almost impossible: Given curve points QQ and GG, it is computationally infeasible to solve for qq.

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 mm that she would like to authenticate. She also has her private key qq and public key QQ that is associated with some elliptic curve over a finite field. To calculate her signature, Alice will:

  1. Generate a random number kk.

  2. Then, calculate the elliptic curve point RR, and let rr be the x-coordinate of RR.
    R=kGR = kG
    r=R.xr = R.x

  3. Next, calculate the signature proof ss.
    sk1[hash(m)+qr](modp)s \equiv k^{-1} \cdot [hash(m) + qr] \pmod p

  4. Her final signature is given by {r,s}\{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}\{r, s\} without Alice's private key. Her public key alone cannot derive {r,s}\{r, s\} because of the discrete logarithm problem!

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

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

  2. For each possible value of RR, recover public key QQ.
    Q=r1(sRhash(m)G)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.

sRhash(m)G=skGhash(m)Gs \cdot R - hash(m) \cdot G = sk \cdot G - hash(m) \cdot G
=(skhash(m))G=(sk - hash(m)) \cdot G
=rqG=rq \cdot G
=rQ=r \cdot Q
Q=r1(sRhash(m)G)\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 RR (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 vv. In all, the new signature format will be {v,r,s}\{v, r, s\}.

Cryptographic Curves

Before ECDSA can be used, participants must agree upon the curve parameters (namely, aa, bb, pp, and GG). It turns out that certain parameters are more secure than others. For instance, if GG is poorly chosen, or pp 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.

y2=x3+7(modp)y^2 = x^3 + 7 \pmod{p}

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

The generator point GG, represented in hexadecimal, is as follows.

x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

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!


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.

Theoretical Quest

Elliptic Curve Cryptography

It's all starting to come together...