Introduction to Elliptic Curves

By: Cailyn Yong and Bryan Wee

The elliptic curve has rooted itself into the cryptographic universe, although its math still remains an enigma to the average layman. The history of the curve dates as far back as the 3rd century, when Diophantus of Alexandria explored cubic plane equations in his celebrated work, Arithmetica. But research on elliptic curves only took off in the last few centuries, and has since found importance in fields like public key cryptography, and integer factorization. Today, elliptic curves define the signature schemes that underpin blockchain security.

In this article, we hope to shed some light on curve, and establish the impetus required to develop insight into its use cases.

Basic Math of Elliptic Curves

What is an Elliptic Curve?

An elliptic curve is the set of points that lies on the curve, $y^2=x^3+ax+b$, together with $O$, the “point at infinity”. The point at infinity is an artificial point on the curve that acts as an ideal point on the projective space of elliptic curves. In other words, it is the point that lies at the ends of all lines parallel to the y-axis.

For practical purposes, we define a rule where for any point $P$ on the curve, $P+O=P$. With this rule, the set of points on elliptic curves becomes an algebraic closure, meaning any point obtained from applying an algebraic operation on any 2 points on the curve will still belong to the elliptic curve.

Note that the curve is required to be non-singular, so the discriminant of the curve should not be 0. Geometrically, this means the curve should have no cusps nor self-intersections.

$\left\{\right(x,y)\in R\mid y^2=x^3+ax+b,4a^3+27b^2\ne 0\}\cup \left\{O\right\}$

The above cubic equation is called the Weierstrass normal form of elliptic curves. If we look at a few examples of Weierstrass elliptic curves, we can see that there are no cusps nor self-intersecting points.

Elliptic Curve Properties

The points on the curve, along with point addition (which we will define soon), forms an abelian group. In other words, they adhere to the following properties:

1. Closure under operation: If points $A$ and $B$ belong to the set of points on the curve, $A+B$ will also belong to that set

2. Associativity under operation: $(A+B)+C=A+(B+C)$

3. Commutativity under operation: $A+B=B+A$

4. Existence of Identity Element: $A+O=A$ (note that $O$ here is the point at infinity)

5. Existence of Inverse: Every element $A$ has an inverse $B$ such that $A+B=O$. On elliptic curves, the inverse of $A$ is the point symmetric about the x-axis.

Elliptic Curve Point Addition

Point addition in elliptic curves is defined geometrically, and expressed with a simple rule: given any three collinear points on the curve,$P,Q,R,$ their sum is always $P+Q+R=O$ (i.e., the point at infinity). Consequently, $P+Q=-R$. Let us take a look at the graph below to better understand what this looks like.

This gives us an intuition on how we can sum two elliptic curve points, $P$ and $Q$. By connecting the two points and extrapolating the line, a third point $R$ is obtained. Reflecting $R$ across the x-axis, we find $-R$ (i.e., the sum).

However, this definition does not address a few edge cases:

1. What if $P=O(orQ=O)$? By definition of $O$, $P+O=P$ and $Q+O=Q$.

2. What if $P$ and $Q$ are aligned vertically? Since $P$ reflects $Q$ about the x-axis, $P=-Q$. Hence, $P+Q=O$.

3. What if $P=Q$? This case is termed point doubling, since $P+Q=2P$. In this case, we define the line $PQ$ to be tangent to $P$. Extrapolating this line will give us $-2P$.

4. What if the line $PQ$ does not intersect a third point? In this case, we can assume that we are in a point doubling scenario (i.e., the third collinear point is either $P$ or $Q$). To discern between the two cases, we check the slope of $PQ$.

• If $PQ$ is tangent to $P$, then $2P+Q=O$. Hence, $P+Q=-P$.

• Else, $PQ$ is tangent to $Q$, and $2Q+P=O$. Hence, $P+Q=-Q$.

After defining point addition geometrically, let us try to express it algebraically. If $P=(x_1,y_1)$ and $Q=(x_2,y_2)$, how can we express $P+Q=(x_3,y_3)$?

Let us first consider the generic case, $P\ne Q$.

1. If $P=O:P+Q=Q$

2. Else if $Q=O:P+Q=P$

3. Else if $x_1=x_2:P+Q=O$

4. Else: let the line $PQ$ be $y=mx+c$.
   • $m=(y_1-y_2)/(x_1-x_2)$
   • $c=y_1-m{x}_1$
   • Then, $x_3=m_2-x_1-x_2$ and $y_3=m(x_1-x_3)-y_1$.

Next, let us consider the case where $P=Q$ (i.e., point doubling).

1. If $y_1=0:P+P=O$

2. Else:
   • The slope $m=\frac{3x^2+a}{2y}$
   • $x_3=m^2-2x_1$
   • $y_3=m(x_1-x_3)-y_1$

Elliptic Curve Scalar Multiplication

Other than addition, another operation that comes in handy is scalar multiplication. Recall that $2P$ is given by extrapolating the line tangent to $P$. This is called point doubling, which is the basis of scalar multiplication. Scalar multiplication is notated like $mP$, where $P$ is added $m-1$ times onto itself. For instance, if we were to calculate $5P$, we could compute $P+P+P+P+P$.

However, this naive approach to computing $mP$ can be unduly expensive as that effectively requires $m-1pointadditions$. For a 256-bit scalar value (like the ones in Ethereum), this could mean up to $2^{256}-1$ point additions, which could take a modern computer approximately $10^{64}$ years. That is more time than the age of the universe, multiplied by the number of atoms on Earth…

Fortunately, there is a better way. The double-and-add algorithm employs simple memoization to make computation far more efficient. The algorithm is better explained with an example. Take $113P$.

1. Express 113 in powers of 2: $113=2^6+2^5+2^4+2^0$.
   

2. Recursively pre-compute values of $2i\cdot P$.
   $2P:=P+P$
   $4P:=2P+2P$
   $8P:=4P+4P$
   $16P:=8P+8P$
   $32P:=16P+16P$
   $64P:=32P+32P$
   

3. Since $113P=(2^6+2^5+2^4+2^0)P$, we can use our pre-computed values to calculate $113P$.
   $113P:=64P+32P+16P+P$
   

Computing $113P$ naively requires 112 point additions. Contrastly, our new approach merely requires 9 point additions.

Generally, to compute $m$, the double-and-add algorithm:

1. Expresses m in powers of 2.

2. Recursively pre-compute values of $2iP$.

3. Uses pre-computed values to calculate $mP$.

Elliptic Curves over Finite Fields

The elliptic curve we have seen has an infinite number of points. For a computer with finite memory, this might be problematic due to rounding errors and an incapacity to represent an infinite set with a limited number of bits. Thus, elliptic curves must first be restricted to a finite field before they can be computed.

What are Finite Fields?

A field is a set of elements with defined operations for addition, subtraction, multiplication, and division. The defined operations must respect the basic rules of arithmetic. An example of a field is the set of real numbers, where the operations are defined by standard arithmetic.

A finite field, as the name suggests, is a field with a finite set of elements. One example of a finite field is a prime field, a set of integers under modulo $p$, where $p$ is a prime number. For prime fields, notated $F_p$, we define operations to be modulo arithmetic, where we append arithmetic equations with $<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>p$.

For instance, $F_7\equiv 0,1,2,3,4,5,6$. Results of addition, subtraction, multiplication, and division are all reduced modulo 7. So, for example, $5+6\equiv 4\left(modp\right)$.

Restricting the Curve

So far, we have assumed that elliptic curves are defined over real numbers, where $x$ and $y$ coordinates are real numbers, and arithmetic operations ($+,-,\ast ,/$) are the standard ones we are all familiar with. It turns out that elliptic curves can be restricted to other fields, so long as we redefine our arithmetic operations!

To make a curve computable, we want to limit the number of points on the curve to a finite set. This can be achieved by limiting the coordinates to a prime field $F_p$ To do so, we have to redefine arithmetic to be modulo arithmetic. For example, $x+y$ must be intepreted as $x+y\left(modp\right)$. Mathematically, the set of points on the curve would be:

$\left\{\right(x,y)\in (F_p{)}^2\mid y^2\equiv x^3+ax+b\left(modp\right),4a^3+27b^2\equiv ̸0\}\cup \{O\}$

Note that elliptic curves over prime fields are still abelian groups, and respect the same properties and formulae as the ones mentioned above. The only difference is that in calculations, standard arithmetic is replaced with modulo arithmetic.

As we have learned, given point $P$ and integer $k$, we can compute $kP$. Let us now consider the inverse problem. Given points $P$ and $Q$, what is k such that $Q=kP$?

This problem is called the discrete logarithm problem for elliptic curves and is considered to be computationally hard to solve since it cannot be solved by any known polynomial time algorithm that runs on a computer.

Solving ECDLP

Take two points on an elliptic curve over a finite field, $P$ and $Q=kP$ for some unknown $k$. Let us see how we can compute a valid $k$.

Let $n$ be the order of the elliptic curve or the number of unique points on the curve. Consider the sequence $P,2P,3P,...$

Since addition is closed, each point in the infinite sequence belongs to the elliptic curve. Hence, it should take at most $n$ iterations before we find a repeated element in the sequence. This also means that the sequence must be cyclic, where the cycle length is $\le n$. With that, we can infer the following.

$(\exists k,kP=Q)⟹(\exists k^{\prime }\le n,k^{\prime }P=Q)$

In English, this means if $kP=Q$ for some unknown $k$, then there exists a valid value of $k$ that is less than or equal to $n$. Hence to find $k$, we can use brute force and iterate through $1\le k\le n$ to find a valid value of $k$.

There are some well-known algorithms to improve this search. The most popular among them is likely Daniel Shank's Baby-step Giant-step algorithm.

We start by re-expressing $k$.

• Let $m=\lceil \sqrt{n}\rceil$.

• Then, $k$ can be re-expressed as $im+j,0\le i,j\le m$ for some values of $i$ and $j$.

$kP=(im+j)P=Q$

$\therefore imP-Q=-jP$

We now use Giant-step Baby-step to find $i$ and $j$, which consequently gives us $k$.

1. We first pre-compute all possible values of $\{-jP,0\le j\le m\}$ into a look-up table. This is the baby-step.

2. Then, we execute the Giant-step. For each possible value of :
   • Compute $imP-Q$
   • Search the result against the look-up table
   • If we have found a search hit, we have found valid values of $i$ and $j$
   

Why is this faster? Naive brute force requires at most $n$ iterations, but Giant-step Baby-step requires $\sqrt{n}$ iterations. However, this is still a ridiculous amount of time when $n$ is extremely large. For instance, Ethereum's elliptic curve has slightly less than $2^{256}$ points, which as seen, is an unfathomably large number.

Asymmetric Computational Effort

As we have observed, scalar multiplication of elliptic curve points is easy to compute. Comparatively, the inverse operation is computationally infeasible. This asymmetric relationship is extremely valuable to public key cryptography. Intuitively, by using elliptic curves over finite fields to implement public key cryptography, we can make it easy to infer public key from private key, but not vice versa.

A variant of the discrete logarithm problem also crops up in other cryptographic schemes such as Digital Signature Algorithm (DSA), ElGamal encryption, and Diffie-Hellman key exchange. The difference is that while elliptic curves uses scalar multiplication, the others uses basic modulo arithmetic. In addition, instead of finding $k$ in the problem $Q=kP$ they find $k$ such that $b=a^k\left(modp\right)$.

As of today, the discrete logarithm problem for elliptic curves is harder to solve compared to that of the other cryptographic schemes. This makes elliptic curve cryptography more secure than its other cousins, where we need fewer bits of $k$ to achieve the same level of security. For instance, a 256-bit private key in elliptic curve cryptography is just as secure as a 3072-bit DSA private key.

Conclusion

We have peered into the elliptic curve and glimpsed over its many properties. We have also toyed with elliptic curve operations: point addition and scalar manipulation, and restricted the curve to a finite field. Lastly, we were introduced to the discrete logarithm problem and gained an intuition on why the elliptic curve is useful in public key cryptography.

Next, we dive a little deeper into elliptic curve math and study how the use of projective spaces can make elliptic curve arithmetic even more efficient...