Elliptic Curves and the Discrete Log Problem

Two weeks ago I started reading Programming Bitcoin by Jimmy Song with a goal to build a utility library alongside learning. The first few chapters cover the basic mathematics that underpins the asymmetric cryptographic scheme — elliptic curve cryptography (ECC) — that bitcoin uses. This is a cryptographic system that is based on elliptic curves over finite fields where a randomly selected private key is used to easily generate a public key but where the converse is computationally difficult/impossible.

But what are elliptic curves? What are finite fields? Why is ECC used in bitcoin?

Eliiptic Curve

To answer these questions, I need a better understanding of the foundational mathematics used in ECC. In this article I summarized what I learned about the following: elliptic curves, finite fields, groups, group law, and finite cyclic groups, the discrete logarithm problem (DLP) and elliptic curve discrete logarithm problem (ECDLP).

Elliptic Curves

One way to think about the equation that describes an elliptic curve is to consider a stack of oranges arranged in such a way that each level contains a square matrix of oranges forming a pyramid. For example, level 4 at the base of the stack will contain (4 x 4) = 16 oranges, level 3 will contain (3 x 3) = 9 oranges, level 2 will have (2 x 2) = 4 oranges, and level 1 (1 x 1) = 1 orange. Consider an interesting problem of rearranging an n-level stack of oranges into a single square matrix. Would it be possible to have a square matrix if there were 3 levels in the stack? To find out if this is possible we have to take the sum of the square of each level and then compute the square root. If the square root is an integer then we have a solution.

The equations above represents an elliptic curve. Given the knowledge of two points on the curve, the third can be found by the intersection of the elliptic curve and the straight line passing through the two known points.

Why is this equation and finding its solution important? To answer this we must understand what finite fields and groups are.

Finite Fields

A thing is said to be finite if it has definable/definite limits. Thus, finite fields are any fields (abstraction of numbers) with a finite set of elements. This means that there is a countable number of elements in the set representing the size/order of the set. Finite fields also have mathematically operations (addition and multiplication) that can be performed on the elements in the set such that the results of these operations are closed, i.e. are in the set. The following must hold true for finite fields:

1. These operators, addition (+) and multiplication (.), perform binary operations
2. The result of adding element c and d must be in the set, making addition closed.
3. There exists a neutral element 0 such that 0 + c = c
4. There exists the identity element 1 such that 1.c = c
5. There exist -c such that -c + c = 0
6. There exists the inverse of c such that

7. There exist prime fields where the order of the finite field is a prime number p where the elements in the set (mod p) of this field are {0, 1, 2, …, p — 1}

These conditions hold true because of modulo arithmetic that allow oversized results to wrapped around the divisor with the remainder falling within the boundary defined by the divisor. The snippet below shows how to implement a finite field element in Python.

Python implementation of a finite field element

Groups, Group Law, and Cyclic Groups

The combination of a finite field and an elliptic curve over this field gives rise to an interesting entity — a group. If you have a finite field and an elliptic curve defined over the field such that the rules for the addition of two points on the curve results in a third, on the same curve, then we have a group.

Groups typically have one law, which is point addition (+) that extends the necessary conditions of a finite field operation. These conditions are:

Additive Identity: Given a point P(x,y) on the elliptic curve, there exists an identity element 0(x,y) such that 0 + P = P. This identity element is known as the point at infinity.

Additive Inverse: Given a point P(x,y) on the curve, there exists another point P(x,-y) such that -P + P = 0 .

Point Addition: Given two points P₁(x₁, y₁) and P₂(x₂, y₂) on the elliptic curve, the third point P₃(x₃, y₃) is computed by calculating the slope (m) through P₁ and P₂, and substituting into the equation of the line that passes through either P₁ or P₂ and P₃. The equations are as shown below and hold true for cases where P₁ is not P₂.

Point Doubling: When P₁ = P₂, doubling is said to occur. Here P₁ + P₂ = P₁ + P₁ = 2P₁. The line formed is tangent to the point P₂ and passes through the third (technically second) point. The slope for this line is found by taken the derivative of the elliptic curve equation. The equation to compute y₃ remains unchanged however, the slope and x₃ equations change as shown below.

Scalar multiplication: What point doubling shows us is that we can perform a new kind of operation called scalar multiplication where P + P = 2P and 2 is a scalar multiple. This property is nonlinear and gives rise to two important considerations: finite cyclic groups and the discrete log problem.

Finite Cyclic Groups:

At some scalar multiple (n) of a select P, we compute the point at infinity nP = 0. For the select P, this means that there exists a finite set of multiples of P called a finite cyclic group. And plot of {P, 2P, 3P, 4P, …, nP} over a finite field is a scattershot of points showing the non-linearity of point addition in finite cyclic groups. This non-linearity is a great property in cryptographic systems because computing the scalar multiple of a select point is easy but predicting the value of the scalar given a point is quite difficult. This is the discrete logarithm problem (DLP).

A point on a simplified elliptic curve y² = x³ + ax + b can be implemented in Python as shown below.

Discrete Logarithm Problem

The generalized discrete logarithm problem in a finite field is one that defines the difficulty of finding an integer x within the range of 1 and p — 1 if there exists:

1. A finite cyclic group with an order of p — 1
2. A primitive element (α) which belongs to the finite cyclic group
3. A derivative element (β) such that αˣ = β

Computing the value of x is very hard if the parameters (p, α, β) are sufficiently large, even though computing the value of β is much easier.

Extending this, a DLP can be constructed with elliptic curves. Formally, the elliptic curve discrete logarithm problem (ECDLP) is the problem of finding an integer value e within the bounds of 1 and the number of points on the elliptic curve (which ~= the order of the finite cyclic group), such that the scalar multiplication of a primitive element G with e, i.e. eG, produces another point P on the elliptic curve.

In cryptographic systems e represents the uniformly selected random number that is the private key, G represents the generator point, P the derived public key.

Bringing it all together

Elliptic curves and the DLP are important because they form the primitives of ECC. With sufficiently large values for the order of the finite cyclic group (n), the generator point (G), and the order of a finite field (p), an elliptic curve discrete logarithm problem can be implemented for security- and privacy-conscious systems. The values bitcoin uses (see Programming Bitcoin, Chapter 3, Page 59) large enough to not have a successful attack against and known to provide long-term security with a time span of decades.

ECC, when compared with schemes in the same asymmetric algorithm family, provides the same security level with significantly smaller key lengths. For example, to achieve a security level of 128 bits, ECC requires 256-bit long keys, while 3072 bits is the minimum requirement for the same security level in others. Handling key lengths of 256 bits is much practical with better speeds than 3072 length keys.

Note:

1. If you are interested in the implementation of field and group operations in Python, here is a link to the code base for Programming Bitcoin. An implementation in C++ is contained in Chapter 9 of Pro Cryptography and Cryptanalysis.
2. If the resources above are too exhaustive, you can check out my repository. It has a much smaller footprint and contains code written alongside learning from Programming Bitcoin.

References

1. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch O’Reilly Media.
2. Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to elliptic curve cryptography Springer.
3. Paar, C., & Pelzl, J. (2010). Understanding cryptography (2. corr. printing ed.). Springer.
4. Mihailescu, M., Iulian, & Nita, S., Loredana. (2021). Pro cryptography and cryptanalysis with C++20: Creating and programming advanced algorithms Apress.