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, y2=x3+ax+by^2=x^3+ax+b, together with OO, the “point of infinity”. The point of 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 PP on the curve, P+O=PP+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.

{(x,y)Ry2=x3+ax+b,4a3+27b20}{O}\{(x,y) \in \mathbb{R} \mid y^2 = x^3+ ax+b, 4a^3+27b^2 \neq 0\} \cup \{O\}

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-01.svg

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 AA and BB belong to the set of points on the curve, A+BA+B will also belong to that set

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

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

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

  5. Existence of Inverse: Every element AA has an inverse BB such that A+B=OA+B=O. On elliptic curves, the inverse of AA 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,P,Q,R, their sum is always P+Q+R=OP+Q+R=O (i.e., the point of infinity). Consequently, P+Q=RP+Q=−R. Let us take a look at the graph below to better understand what this looks like.

elliptic-02.svg

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

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

1. What if P=O(orQ=O)P=O (or Q=O)? By definition of OO, P+O=PP+O=P and Q+O=QQ+O=Q.

2. What if PP and QQ are aligned vertically? Since PP reflects QQ about the x-axis, P=QP=−Q. Hence, P+Q=OP+Q=O.

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

4. What if the line PQPQ 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 PP or QQ). To discern between the two cases, we check the slope of PQPQ.

  • If PQPQ is tangent to PP, then 2P+Q=O2P+Q=O. Hence, P+Q=PP+Q=−P.

  • Else, PQPQ is tangent to QQ, and 2Q+P=O2Q+P=O. Hence, P+Q=QP+Q=−Q.

elliptic-05.svg

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

Let us first consider the generic case, PQP≠Q.

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

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

  3. Else if x1=x2:P+Q=Ox_1=x_2: P+Q=O

  4. Else: let the line PQPQ be y=mx+cy=mx+c.
    m=(y1y2)/(x1x2)m=(y_1−y_2)/(x_1−x_2)
    c=y1mx1c=y_1−mx_1
    • Then, x3=m2x1x2x_3=m_2−x_1−x_2 and y3=m(x1x3)y1y_3=m(x_1−x_3)−y_1.

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

  1. If y1=0:P+P=Oy_1=0:P+P=O

  2. Else:
    • The slope m=3x2+a2ym=\dfrac{3x^2+a}{2y}
    x3=m22x1x_3=m^2−2x_1
    y3=m(x1x3)y1y_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 2P2P is given by extrapolating the line tangent to PP. This is called point doubling, which is the basis of scalar multiplication. Scalar multiplication is notated like mPmP, where PP is added m1m−1 times onto itself. For instance, if we were to calculate 5P5P, we could compute P+P+P+P+PP+P+P+P+P.

However, this naive approach to computing mPmP can be unduly expensive as that effectively requires m1pointadditionsm−1 point additions. For a 256-bit scalar value (like the ones in Ethereum), this could mean up to 225612^{256}−1 point additions, which could take a modern computer approximately 106410^{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 113P113P.

  1. Express 113 in powers of 2: 113=26+25+24+20113=2^6+2^5+2^4+2^0.

  2. Recursively pre-compute values of 2iP2i⋅P.
    2P:=P+P2P:=P+P
    4P:=2P+2P4P:=2P+2P
    8P:=4P+4P8P:=4P+4P
    16P:=8P+8P16P:=8P+8P
    32P:=16P+16P32P:=16P+16P
    64P:=32P+32P64P:=32P+32P

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

Every natural number can be written as a sum of distinct powers of 2. Just think about how integers are represented in binary!

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

Generally, to compute mm, the double-and-add algorithm:

  1. Expresses m in powers of 2.

  2. Recursively pre-compute values of 2iP2iP.

  3. Uses pre-computed values to calculate mPmP.

Algorithmically, to remove the need to maintain an array of multiples of P, we could interweave steps 2 and 3.

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 pp, where pp is a prime number. For prime fields, notated Fp\mathbb{F}_p, we define operations to be modulo arithmetic, where we append arithmetic equations with modp\bmod p.

For instance, F70,1,2,3,4,5,6\mathbb{F}_7≡{0,1,2,3,4,5,6}. Results of addition, subtraction, multiplication, and division are all reduced modulo 7. So, for example, 5+64(modp)5+6≡4 \pmod{p}.

Restricting the Curve

So far, we have assumed that elliptic curves are defined over real numbers, where xx and yy coordinates are real numbers, and arithmetic operations (+,,,/+, −, ∗, /) 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 Fp\mathbb{F}_p To do so, we have to redefine arithmetic to be modulo arithmetic. For example, x+yx+y must be intepreted as x+y(modp)x+y \pmod p. Mathematically, the set of points on the curve would be:

{(x,y)(Fp)2y2x3+ax+b(modp),4a3+27b2≢0}{O}\{(x,y) \in (\mathbb{F_p})^2 \mid y^2 \equiv x^3+ ax+b \pmod{p}, 4a^3+27b^2 \not\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 PP and integer kk, we can compute kPkP. Let us now consider the inverse problem. Given points PP and QQ, what is k such that Q=kPQ = 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, PP and Q=kPQ = kP for some unknown kk. Let us see how we can compute a valid kk.

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

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

(k,kP=Q)    (kn,kP=Q)(\exists k, kP = Q) \implies (\exists k' \leq n, k'P = Q)

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

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 kk.

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

  • Then, kk can be re-expressed as im+j,0i,jmim + j, 0 \leq i, j \leq m for some values of ii and jj.

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

imPQ=jP\therefore imP - Q = -jP

We now use Giant-step Baby-step to find ii and jj, which consequently gives us kk.

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

  2. Then, we execute the Giant-step. For each possible value of 0i<m0 \leq i < m:
    • Compute imPQimP - Q
    • Search the result against the look-up table
    • If we have found a search hit, we have found valid values of ii and jj

Why is this faster? Naive brute force requires at most nn iterations, but Giant-step Baby-step requires n\sqrt{n} iterations. However, this is still a ridiculous amount of time when nn is extremely large. For instance, Ethereum's elliptic curve has slightly less than 22562^{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 kk in the problem Q=kPQ = kP they find kk such that b=ak(modp)b = a^k \pmod{p}.

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 kk 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...

Theoretical Quest

Introduction to Elliptic Curves

What strange markings, what do they mean?