Our previous article covered elliptic curves over real numbers. However, cryptographic applications like ECDSA signatures and zero-knowledge proof systems require working over finite fields.
This article will explore elliptic curves over finite fields, how these discrete curves form cyclic groups, their homomorphic properties, and how the discrete logarithm problem provides cryptographic security.
Now that point addition and scalar point multiplication have been defined for elliptic curves over real numbers, let's repeat this exercise while considering elliptic curves over finite fields, where the $x$ and $y$ coordinates are from a finite field $\mathbb{F_p}$ where $p$ must to be prime to form a field.
This is what the elliptic curve points are, specifically, an elliptic curve over the finite set of integers modulo $p=19$, or $\mathbb{F}_{19}$:
Or, plotted on a curve:
There are $(p-1)$ possible values for $x$ and $(p-1)$ possible values for $y$. Therefore, each coordinate $x$ and $y$ on the elliptic curve is an element of this set of $p-1$ elements.
Notice how, as with elliptic curves over real numbers, the plot is symmetrical about the x-axis. However, this plot is now discrete rather than continuous (individual, disconnected points, not a continuous line). This is because the field $\mathbb{F}_{19}$ is discrete since the field elements are integers modulo $19$ rather than real numbers.
Point addition on elliptic curves over finite fields follows the same algebraic formulas as curves over real numbers. The connect, intersect, and reflect (CIR) framework describes the underlying mathematics, but over finite fields $\mathbb{F}_p$, this happens algebraically rather than geometrically.
To add two points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$:
The group properties also still hold:
Since these properties hold, elliptic curves over finite fields also form Abelian groups. However, in some instances, the group is also cyclic.
In the case of elliptic curves over finite fields, when the order (the number of points) of the elliptic curve is a prime number (let's call it $n$ to distinguish it from the prime field modulus $p$ in $\mathbb{F_p}$):
$$P = kG$$
For example, with a curve of order $19$, we can generate all $19$ points by computing $G$, $2G$, $3G$, ..., $18G$ from the generator point $G$ plus the point at infinity $\mathcal{O}$.
The ECDLP is a version of the discrete logarithm problem (DLP) that considers elliptic curve points with the point addition operator.
The DLP asks: Given a generator $g$ and an element $h$, find an integer $x$ such that applying the group operation $x$ times to $g$ results in $h$.
In a finite multiplicative cyclic group, this means finding $x$ such that:
$$h = g^x \pmod{p}$$
where exponentiation is repeated multiplication.
The ECDLP is the DLP for an elliptic curve group: the set of elliptic curve points over a finite field, equipped with the point addition binary operator.
The ECDLP is the problem of determining a scalar $x$, such that:
$$P = xG$$
Where:
Remember, this is scalar multiplication, so repeated point addition.
The ECDLP states that finding the scalar $x$ is computationally infeasible.
While point addition is computationally efficient, if the elliptic curve order $n$ is large enough, reversing this operation (i.e., finding $x$ given $P=xG$) is a problem for which no efficient algorithm is known. There is no direct formula for "scalar division."
Given a point $P$, it is unknown which scalar $x$ was used to compute it, to find $x$, you’d have to try many of the possibilities until you find the correct one (using an algorithm like Pollard’s Rho algorithm which is an optimized brute force approach, or exhaustice search, that reduces the number of calculations to ~$\sqrt{n}$). Algorithms like this becomes infeasible when the group order $n$ (number of elements in the group) is large.
This is why $n$ must be large: to ensure that the space of possible $x$ values is enormous, making exhaustive search computationally impractical.
To understand why the ECDLP is hard, consider a small curve over $\mathbb{F}_5$ with the equation $y^2 = x^3 + 2x + 1 \mod 5$.
Suppose we pick $G = (0,1)$ as our generator. We can compute scalar multiples:
If you are given $P = (3,3)$, to solve for $x$ in $xG = P$, you can try each multiple:
Thus, $x = 3$.
In this example, brute-forcing $x$ is easy because there are very few possibilities. But on real-world curves where $n$ (the elliptic curve order) is, for example, for the BN254 curve, approximately $2^{256}$, this approach becomes completely infeasible.
Elliptic curves exhibit important homomorphic properties that make them useful for cryptography:
Scalar multiplication creates a homomorphism from the additive group $\mathbb{Z}_{n}$ (integers modulo the curve order) to the elliptic curve group over a finite field $\mathbb{F_p}$.
Additive homomorphism: for any integers $a$ and $b$ modulo the curve order $n$ and generator point $G$, addition in $\mathbb{Z}_{n}$ maps to point addition on the curve:
$$(a + b)G = aG + bG$$
Distributive property: for any integer $k$ modulo the curve order $n$ and points $P$ and $Q$, scalar multiplication distributes over elliptic curve point addition:
$$k(P + Q) = kP + kQ$$
Therefore, we can transform private values into elliptic curve points through scalar multiplication with a generator point $G$.
The resulting points maintain mathematical relationships corresponding to operations on the original values while making it computationally infeasible (due to ECDLP) to recover the original values.
For example, if we have a private value $x$ and generate the point $P = xG$, we can perform operations on $P$ that correspond to operations on $x$, without revealing $x$ itself.
The point $P = xG$ acts as a "cryptographic representation" of $x$.
Operations on these representations correspond to operations on the underlying values, but the discrete logarithm problem makes it computationally infeasible to extract $x$ from $P$.
This property is fundamental to many cryptographic protocols, including digital signatures, key exchange, and zero-knowledge proofs.
The key concepts covered in this article include:
The combination of efficient computation and computational hardness makes elliptic curves over finite fields the foundation of modern public-key cryptography.
