Elliptical Curve Encryption and Signature - A practical introduction for programmers

This post gives a hands-on tutorial on the basic concepts of elliptical curves needed to implement public key encryption and signature from first principles. I pick a specific curve, secp256k1, to keep things simple and concrete.

This post is created to show that basic operations are really simple once the preliminaries are out of the way. For example:

A private key is nothing but a 256 bit integer.
A key exchange is just combining a private key and a public key: \(S = \rho_a H_b\)
A digital signature is as simple as calculating one number and sending it along with message: \(s = \frac{1}{k} (h + P_x \rho)\)

A First Look at Curve Secp256k1

An elliptical curve is defined by the equation

\begin{equation} y^2 = x^3 + ax + b, \text{ where } a=0 \text{ and } b=7. \end{equation}

Furthermore, the following constants will be used to define the abelian group that is key to all cryptographic computations.

p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
G_x = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
G_y = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
h = 1

\(p\) defines field of integers modulo \(p\). \(G\) is the base point of the subgroup that I will describe shortly. \(n\) is the subgroup order and \(h\) the cofactor. See this page for more details. Because I am working with the special case of Secp256k1 curve in this post, I ignore the discussions on many potential vulnerabilities due to singularities, non-prime order, etc. Not all elliptical curves are secure choices.

Group Construction from the Elliptical Curve

We want to use the curve equation and constants to define a cyclic abelian group that we can used for cryptography computations.

I don’t think it is necessary, but if you want to, here is a good reference to refresh your group theory basics.

Group elements

Every (x, y) pair is an element in the group if the point is on the curve, and x and y are integer modulo p. That is,
\begin{align*} B := \{ (x, y) \: | \: & y^2 = x^3 + 7 \; (mod \; p) \\ & x,y \in \mathbb{F}_p \} \end{align*}
where \(\mathbb{F}_p\) is the set of integers modulo \(p\). Note that I use \(B\) to denote this parent group.o
The identity element is the point at infinity, denoted by \(0\), such that for every \(x \in B, 0x = 0\).
The inverse of \(P=(P_x, P_y)\) is \(-P=(P_x, -P_y)\). Geometrically, \(-P\) is the mirror point across the x-axis.

Group operation

I will use \(+\) to denote the binary operation. It is convenient called addition as well. The rule of addition is defined by one rule: \(P + Q + R = 0\) if all three points are aligned. That is, if we draw a line on the graph, the three points that it touches add up to zero. Note that an inverse element, i.e. \(-R\), is already defined. We can turn this geometric rule into algebraic form. Let \(T = P + Q\). Let \(m\) be the slope of the line formed by \(P\) and \(Q\). We have

\begin{equation} m = \frac{P_y - Q_y}{P_x - Q_x}. \end{equation}

Note that the slope could be computed by taking the limit if P and Q are the same; in other words, we get the slope by computing \(dy/dx\) from the curve equation,

\begin{equation} m = \frac{3P_x^2}{2P_y}. \end{equation}

The point \(T = (T_x, T_y) = (m^2 - P_x - Q_x, m(P_x - T_x) - P_y)\). These calculations are much easier to visualize if you draw a straight line on an curve. You can use Wolfram Alpha if you are lazy.

The rule of multiplication rule is a notation convenience, where \(nP := P + ... + P\) with \(n\)-many repetitions. The straightforward way of multiplying through pointwise addition is not computationally efficient. There are alternatives such as double-and-add and windowed method.

Subgroup

I did not show why the set \(B\) and the binary operation addition forms an abelian group. One could check the group laws easily. I am not going to show how the following base point is chosen, but note that the base point is chosen so that the cofactor is 1. The base point \(G = (G_x, G_y)\) is

G_x = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
G_y = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8

I abuse notation and use \(G\) to denote the cyclic subgroup generated by G. Note that \(nG = 0\) and \((n+1) G = G\). The subgroup contains all the point of the parent group. The group order is n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141.

So far, I have defined the group and the binary operation. We are set to do cryptography computation. This group is special because the for any \(\rho \in \{ 0, 1, \cdots, n - 1 \}\) and \(H = \rho G\). The discrete log problem of recovering \(\rho\) when \(H\) is known to be computationally hard.

Public Key Encryption through Diffie-Hellman (ECDH)

Keys

A private key is random integer, \(\rho \in \{ 0, 1, \cdots , n - 1 \}\). It is 32 bytes in length.
The associated public key (\(H\)) is the curve point associated with \(\rho\). That is, \(H = \rho G\). A public key could be written in two coordinates, each with 32 bytes. It could also convenient encoded with 32 bytes + 1 bit, or roughly 33 bytes. Note that one coordinate could be derived from another using the curve equation, and the extra bit denotes the quadrant.

Key exchange

Alice see \(\rho_a\), \(H_a\), and \(H_b\). The shared secret is
\begin{equation} S = \rho_a H_b = \rho_a (\rho_b G). \end{equation}
Bob see \(\rho_b\), \(H_a\), and \(H_b\). The shared secret is
\begin{equation} S = \rho_b H_a = \rho_b (\rho_a G). \end{equation}
Alice and Bob use the private secret \(S\) to to encrypt and decrypt via an symmetric algorithm such as AES. Note that the private keys could be ephemeral. For example, when elliptical curve is used in TLS, \(\rho_a\) and \(\rho_b\) are generated for each connection. They are discarded as soon as the shared secret \(S\) is generated for that session.

Digital Signature Algorithm (ECDSA)

Signing

Alice has the private key \(\rho\), publishes the public key \(H = \rho G\), and she wants to signs the message \(m\). Let \(h = hash(m)\) be the hahs of the message. The hash function does not need to be cryptographically strong. The purpose of the hash is to uniquely represent the message as an integer. The hash function is common knowledge.

Alice generates a random \(k \in \{ 0, 1, \cdots, n - 1 \}\). Let \((P_x, P_y) := kG\). Alice calculates the signature as

\begin{equation} s = \frac{1}{k} (h + P_x \rho) \end{equation}

Alice sends the signed message as \((m, s, P)\). Note that \(P\) is 33 bytes, and \(s\) is 32 bytes. The signature part is about 65 bytes long.

Verification

Bob receives the signed message \((m, s, P)\). It is worth noting that it must be established a priori as common knowledge that \(H\) is Alice’s public key. If \(H\) is part of the signed message, then anyone could act as a man in the middle and fake any signed message one prefers.

Bob calculates \(Q = \frac{1}{s} (h G + P_x H)\). The message is verified if and only if \(Q = P\).

Here is a short proof of the verification requirement.

\begin{eqnarray*} Q &=& \frac{1}{s} ( h G + P_x H ) \\ &=& \frac{1}{s} ( h G + P_x \rho G) \\ &=& \frac{1}{s} ( h + P_x \rho) G \\ &=& \frac{1}{s} (h + P_x \rho) G \\ &=& \frac{k}{(h + P_x \rho)} (h + P_x \rho) G \;\;\;\;\;\;\;\;\text{substituting } s\\ &=& kG = P \end{eqnarray*}

Note that we could just send \(P_x\) instead of \(P\) and only verified \(P_x=Q_x\).

Security and Key Length

Given the public key \(H\), how hard is it to brute force search for \(\rho\), where \(H = \rho G\)?

The private key is any number less than \(n\), \(0 < \rho < n\), where

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

Ignoring some technicalities that there are some invalid number less than \(2^{256}\), a private key has bit length of 256 bit long. Here is an cost estimation of brute forcing a 256 bit key. It costs much more than any nation’s GDP.

However, there are more efficient algorithms to solve the discrete log problem than the brute force search. For examples, baby-step giant-step, index calculus, or Pollard’s rho. The computation complexity of elliptic curve discrete logarithm problem (ECDLP) is an active area of research. See GG16 for a recent literature review.

The best record have been based on variants of Pollard’s rho algorithm, in the order of \(\sqrt{n}\). The security of a 256 key EC private key is roughly equivalent to a 128 bit key that does not have any special structure to exploit. This keylength site compiles tables on the security strength of the popular encryption schemes.

The Shor’s algorithm using quantum qubits could be used to break elliptical curve’s discrete log problem. See KLM07 for a fun introduction to quantum computing.

Citations

Steven Galbraith and Pierrick Gaudry. Recent progress on the elliptic curve discrete logarithm problem. Designs, Codes and Cryptography, 78:51–72, 2016. ¹
Phillip Kaye, Raymond Laflamme, and Michele Mosca. An Introduction to Quantum Computing. Oxford University Press, 2007. ¹

Elliptical Curve Encryption and Signature
A practical introduction for programmers