# Introduction to Elliptic Curves

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 of infinity](https://trustica.cz/2018/03/29/elliptic-curves-point-at-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 $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.

$$\{(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 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 of 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 of 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$ (or $Q = 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 also 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 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 \neq Q$.

1. If $P = O$ or $Q = O$, then: $P+Q$ is $Q$ or $P$ respectively.
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 - mx_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 : 2P = O$
2. Else:
* The slope $m = \dfrac{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 of computing $mP$ can be unduly expensive as that effectively requires $m - 1$ point additions. 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 in 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
$$

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

2. Recursively pre-compute values of $2^i \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/doubling. Conversely, our new approach merely requires $9$ point additions/doubling.

Generally, to compute $m$, the double-and-add algorithm:
1. Expresses $m$ in powers of $2$.
2. Recursively pre-compute values of $2^i \cdot P$.
3. Uses pre-computed values to calculate $mP$.

> 💡 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 $\mathbb{R}$, 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 $\mathbb{F}_p$, we define operations to be modulo arithmetic, where we append arithmetic equations with $\bmod p$

For instance, $\mathbb{F}_7 \equiv \{0, 1, 2, 3, 4, 5, 6\}$. Results of addition, subtraction, multiplication, and division are all reduced modulo $7$. So, $5+6$ is given by $5 + 6 \equiv 4 \pmod{p}$.

### Restricting the Curve

So far, we have assumed that ellptic curves are defined **over real numbers**, where $x$ and $y$ 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 out 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 $\mathbb{F}_p$. To do so, we have to redefine arithmetic to be **modulo arithmetic**. For example, $x + y$ must be intepreted as $x + y \pmod p$. Mathematically, the set of points on the curve would be:

$$
\{(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.

## Elliptic Curve Discrete Logarithm Problem

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

$$
P, 2P, 3P, ...
$$

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

$$
(\exists k, kP = Q) \implies (\exists k' \leq n, k'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 \leq k \leq 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 \leq i, j \leq 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 \leq j \leq m\}$ into a look-up table. This is the baby-step.
2. Then, we execute the Giant-step. For each possible values of $0 \leq i < m$:
* 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 is slightly less than $2^{256}$, 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 \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 $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...

---

## Questions:

1. In an elliptic curve, $O$ notates the point of infinity. Select all statements that are true.
- [x] $P + O$ = O$ for any $P$ on the elliptic curve.
- [ ] $P + Q+ R = O$ for any $P, Q, R$ on the elliptic curve.
- [ ] If $P = Q$, then $P + Q = O$.
- [x] $O + O = O$.

2. Given a point $P$ on the elliptic curve, use the double-and-add algorithm to calculate $180P$. How many instances of point addition/doubling will the algorithm require?

- [x] 4 point additions, 7 point doubling.
- [ ] 5 point additions, 8 point doubling.
- [ ] 7 point additions, 7 point doubling.
- [ ] 3 point additions, 5 point doubling.

3. Which of the following are reasons elliptic curves over real numbers are not entirely computable?

- [x] The curve has an infinite number of points, which cannot be represented by a computer with finite memory.
- [ ] The discrete logarithm problem is easy to solve for real numbers.
- [x] Real numbers are subjected to rounding errors.
- [ ] There is no such thing as elliptic curves over real numbers.

4. Consider the elements in the field $\mathbb{F}_7$, which of the following equations are correct?

- [ ] $6 + 4 = 10$
- [x] $8 * 10 = 3$
- [ ] $3 + 4 = 7$
- [x] $3 - 6 = 2$

5. Which of the following statements is true about the Giant-step Baby-step algorithm?

- [x] The algorithm solves the discrete logarithm problem.
- [ ] The algorithm runs in polynomial time with respect to the number of bits of $k$.
- [x] The algorithm splits $k$ into $im + j$, and brute forces for possible values of $i$ and $j$.
- [ ] The algorithm requires the pre-computation of a baby-step list, which will be looked up when iterating through the giant-step.

6. Which of the following statements is true about the discrete logarithm problem?

- [x] ECDLP is a variant of the discrete logarithm problem.
- [x] The hardness of the problem justifies why scalar multiplication is difficult to reverse.
- [ ] The hardness of the problem justifies why point doubling is difficult to reverse.
- [x] ECDLP is harder than other discrete logarithm problems, making elliptic curve cryptography more secure than other public-key cryptography schemes.

7. Point operations on the elliptic curve are defined geometrically. Let points $P$, $Q$, and $R$ be unique points on the elliptic curve. Which of the following statements is false?

- [x] If line $PQ$ intersects $R$, the $R + P = -Q$.
- [x] If $P$ and $Q$ share the same x-coordinate, then $P + Q$ is the point of infinity.
- [ ] If $P + Q = R$, then $P$, $Q$, and $R$ are collinear.
- [ ] If $P$ and $Q$ share the same y-coordinate, then $P + Q$ is the point of infinity.

8. Let $P$, $Q$ be points on the elliptic curve, where neither is the point of infinity. The line $PQ$ does not intersect any point on the curve. Which of these are possible values of $P + Q$?

- [ ] The point of infinity $O$.
- [ ] $-P$
- [ ] $-Q$
- [x] $P$