# Toy ECC in TypeScript (Part 1, Elliptic Curves over Real Numbers)

[RSA (Rivest–Shamir–Adleman)](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) and [ECC (Elliptic-Curve Cryptography)](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography) are currently the two most widely used [Public-Key Cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography) systems. I have written [some articles](https://hackmd.io/@sp1derca7?tags=%5B%22RSA%22%5D) to introduce RSA, and in this new series, I will introduce ECC. Like most of my previous blogs, the articles in this series are also meant to repay technical debts. My main purpose is to deepen my understanding of technologies such as RSA and ECC by writing articles, so I will not delve too deeply into the details, but will include some TypeScript code.

This article marks the beginning of the ECC series. In the first section, I will guide readers through a review of Real Numbers and addition, concepts we learned in our childhood. The second section will introduce the Elliptic Curve over Real Numbers, along with the Points Addition rules defined on it. In the third section, I will write a toy Elliptic Curve implementation using TypeScript. With this article as a precursor, I'll introduce Elliptic Curves over Finite Fields in the next one.

⚠️Warning: Apart from toys, **never** attempt to implement any cryptographic algorithm on your own! Always use cryptographic libraries written by professional cryptographers.

## Real Numbers and Addition

Let's start by reviewing elementary school mathematics, beginning with the simplest numbers and addition. When we first started school, we learned about [Natural Numbers](https://en.wikipedia.org/wiki/Natural_number) and basic arithmetic operations. Soon after, we were introduced to [Decimals](https://en.wikipedia.org/wiki/Decimal), that is, [Real Numbers](https://en.wikipedia.org/wiki/Real_number). In mathematics, the set of all natural numbers is usually denoted by $\mathbb N$, and the set of all real numbers is denoted by $\mathbb R$. We can also represent the entire set of real numbers as a horizontal straight line called the [Number Line](https://en.wikipedia.org/wiki/Number_line). The number line is infinitely long, centered at `0`, with each point on it corresponding to a real number, as shown below (the graphs in this article are generated by [Desmos](https://www.desmos.com/calculator)):


In this article, we are only concerned with the [addition](https://en.wikipedia.org/wiki/Addition) of real numbers. We know that the sum of two real numbers is another real number. Specifically, on the number line, this can be thought of as adding two points to get another point. Here I present several very basic and important properties of real number addition:

[**Closed**](https://en.wikipedia.org/wiki/Closure_(mathematics)): Since there are infinitely many real numbers, it is obvious that the sum of two real numbers is also a real number. In other words, given any two real numbers `a` and `b`, `a+b` is also a real number. Let's express this in mathematical language:
$$
\forall a,b ∈ \mathbb R: a+b ∈ \mathbb R
$$
**Identity**: For the addition of real numbers, `0` (Zero) acts as the [Identity Element](https://en.wikipedia.org/wiki/Identity_element). We know that for any real number `a`, `a+0=a`. Let's express this in mathematical language:
$$
\forall a ∈ \mathbb R: a + 0 = a
$$
**Inverse**: Given any two real numbers `a` and `b`, if `a+b=0`, we say that `b` is the [Additive Inverse](https://en.wikipedia.org/wiki/Additive_inverse) of `a`, and we can write `b` as `-a`. Since the real number line is symmetrical with `0` as the midpoint, every real number `a` has its inverse, which is `-a`. Moreover, it is clear that the inverse of `0` (and only `0`) is itself.
$$
\forall a ∈ \mathbb R: a + (-a) = 0
$$
Having introduced the additive inverse, we can say that subtraction is essentially also addition:
$$
a - b = a + (-b)
$$
[**Commutative**](https://en.wikipedia.org/wiki/Commutative_property): For any two real numbers `a` and `b`, the order in which their sum is taken does not affect the result. Let's express this in mathematical language:
$$
\forall a,b ∈ \mathbb R: a+b = b+a
$$
[**Associative**](https://en.wikipedia.org/wiki/Associative_property): We can slightly extend the commutative law to state that for any three real numbers `a`, `b`, and `c`, the order in which their sum is taken does not affect the result. Let's express this in mathematical language:
$$
\forall a,b,c ∈ \mathbb R: (a+b)+c = a+(b+c)
$$

Incidentally, since the addition of real numbers possesses the aforementioned properties, particularly Commutative, the entire set of real numbers forms an [Abelian Group](https://en.wikipedia.org/wiki/Abelian_group) under addition.

Here I will elaborate a bit more on the multiplication of real numbers and natural numbers. Multiplication is essentially a form of repeated addition. Given a real number `a` and a natural number `n`, we can express multiplication in terms of addition, that is, `a×n=a+a+...+a` (n times). Let's express this in mathematical language:
$$
\forall a ∈ \mathbb R, n ∈ \mathbb N: a × n = \sum_1^n a
$$

Obviously, there is an exception here: any real number `a` multiplied by `0` equals `0`:
$$
\forall a ∈ \mathbb R: a × 0=0
$$
OK, let's end this brief but wonderful elementary school math course and quickly move on to junior high.

## Elliptic Curves over Real Numbers

Let's leave the one-dimensional linear world behind and enter the two-dimensional plane world to review some knowledge of [Analytic Geometry](https://en.wikipedia.org/wiki/Analytic_geometry). Remember? In the [Cartesian Coordinate System](https://en.wikipedia.org/wiki/Cartesian_coordinate_system), we can use an equation to represent a straight line or a curve. An [Elliptic Curve](https://en.wikipedia.org/wiki/Elliptic_curve) is a curve that satisfies the following equation, where `a` and `b` can be any real numbers.
$$
y^2 = x^3 + ax + b
$$

For example, if we take `a=-5` and `b=9`, the concrete curve $y^2=x^3-5x+9$ looks like [the one below](https://www.desmos.com/calculator/8rsex5xipy). It is not difficult to see that the elliptic curve is symmetrical about the x-axis.


Given two real numbers `a` and `b`, they can uniquely determine an elliptic curve, which we denote as `C(a, b)`. Like a straight line, this curve also contains infinitely many points. We denote any point on the plane as `P(x, y)`. If a certain point `P` lies on the curve `C`, then it must satisfy the equation of the curve `C`. Let's express this in mathematical language:
$$
P(x, y) ∈ C(a, b) \Leftrightarrow y^2 = x^3 + ax + b
$$

Now, let's consider the x-axis of the Cartesian coordinate system as the real number line, which can be represented by the equation `y = 0`. As we have discussed before, every point on the x-axis corresponds to a unique real number, and the sum of two points (real numbers) is another point (real number). In other words, we can think of it as performing addition on the points of the x-axis.

Interestingly, just like addition of real numbers on the x-axis, we can construct a similar type of [addition](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) using points on an elliptic curve. Given a certain curve `C`, and any three points `P1`, `P2`, `P3` on `C`, as well as a special identity point `O`, this addition fully satisfies the six properties that we have previously discussed regarding real number addition:
$$
\begin{align*}
\forall P_1, P_2, P_3 &∈ C: \\
P_1 + P_2 &∈ C \\
P_1 + O &= P_1 \\
P_1 + (-P_1) &= O \\
P_1 + P_2 &= P_2 + P_1 \\
(P_1 + P_2) + P_3 &= P_1 + (P_2 + P_3)
\end{align*}
$$

Now I will describe the rules for this addition, starting with the most general case. Given a certain curve `C`, and two different points on it, `P1(x1, y1)` and `P2(x2, y2)`, with `x1 ≠ x2`. Draw a straight line through `P1` and `P2`, and this line will necessarily intersect the curve at another point `P3'`. We take the x-axis symmetric point `P3(x3, y3)` of `P3'` as the sum of `P1` and `P2` (Why do we need to flip `P3'`? Please refer to [this article](https://www.rareskills.io/post/elliptic-curve-addition#:~:text=Why%20elliptic%20curve%20addition%20flips%20over%20the%20x%20axis)). The following figure illustrates a concrete example.


Perhaps the reader's question is, for any two points `P1` and `P2` that satisfy the above conditions, is there definitely a `P3` that we are looking for? The answer is yes. Moreover, we can provide a formula to directly calculate `P3` based on `P1` and `P2`. I will not go into the detailed derivation process here, the formula is as follows (where s represents the [Slope](https://en.wikipedia.org/wiki/Slope) of line `P1P2`):

$$
\begin{align*}
s &= \frac{y_2 - y_1}{x_2 - x_1} \\
x_3 &= s^2 - x_1 - x_2 \\
y_3 &= s(x_1 - x_3) - y_1
\end{align*}
$$
But if the x-coordinates of the two points are the same, then the straight line passing through them and the curve will not intersect at a third point. In this case, we can assume that the intersection point lies at infinity (y=∞). We regard this imaginary point as the Identity and denote it as `O` (which resembles zero). The following figure illustrates a concrete example.


Wow, we not only resolved this special case, but also introduced the Identity `O`. Additionally, by definition, for any point `P` on the curve `C`, we can easily find its inverse `-P` simply by changing the sign of its y-coordinate. That is to say, if a point `P` has coordinates `(x, y)`, then the coordinates of `-P` are `(x, -y)`. Therefore:

$$
\begin{align*}
\forall P_1(x, y), P_2(x, -y) &∈ C: \\
P_1 + P_2 &= O
\end{align*}
$$
Now let's consider the case where `P1=P2`, which is when a point `P` on the curve adds to itself. We can consider the two points to be infinitely close, so we need to draw a tangent line to the curve `C` through point `P`, so that we can find another intersection point. The following figure illustrates a concrete example.


Using knowledge from [Calculus](https://en.wikipedia.org/wiki/Calculus), we can calculate the slope of the tangent line to the curve `C` at point `P` by taking its [derivative](https://en.wikipedia.org/wiki/Derivative). Then, we can calculate the x and y coordinates in the usual manner. Below is the formula for calculating the sum of a point P with itself:
$$
\begin{align*}
s &= \frac{3{x_1}^2 + a}{2y_1} \\
x_3 &= s^2 – 2x_1 \\
y_3 &= s(x_1 – x_3) – y_1
\end{align*}
$$

We have one last special case to address, which is when the point `P` on the x-axis adds to itself. Here is an example:


Obviously, the tangent line to the curve `C` at point `P` is vertical, so we expect the other intersection point to be at infinity, that is, point `O`. That is to say:

$$
\begin{align*}
P(x, 0) &∈ C: \\
P + P &= O
\end{align*}
$$

According to our definition of addition for points on the curve, the commutative law is very obvious. However, the associative law is not so obvious, but I won't prove it here. Interested readers can search for relevant information.The following figure summarizes the four cases of point addition:


## Toy Implementation

Alright, with just some knowledge of elementary and junior high school mathematics, as well as a bit of college calculus, we can fully understand the Elliptic Curve over Real Numbers and the addition of Points. Now comes the easiest step, writing a Toy implementation in TypeScript. We first define the special point `O` and the `Point` type, as shown in the code below:

const ZERO: Point = null;

type Point = null | {
  readonly x: number,
  readonly y: number,
};

Next, we define the `ECoverRN` type, which has two fields: `a` and `b`. We also need to define two methods for it, one for calculating the sum of two points, and the other for calculating the product of a point and a natural number. For ease of reading, these two methods are left blank for now, but will be provided shortly.

class ECoverRN {

  readonly a: number;
  readonly b: number;

  constructor(a: number, b: number) {
    this.a = a;
    this.b = b;
  }

  add(p1: Point, p2: Point) { ... }
  mul(p: Point, n: bigint): Point { ... }

}

We translate the addition formulas (a total of four cases) introduced in the previous section into TypeScript code, which looks like the following. Note that in order to make the code as concise as possible, I have omitted some necessary checks (such as whether the parameters `p1` and `p2` are actually on the curve).

  add(p1: Point, p2: Point): Point {
    if (p1 == ZERO) { return p2; }
    if (p2 == ZERO) { return p1; }

    const [a, x1, y1, x2, y2] = [this.a, p1!.x, p1!.y, p2!.x, p2!.y];

    let s; // slope
    if (x1 == x2) {
      if (y1 != y2 || y1 == 0 && y2 == 0) {
        return ZERO;
      }

      s = (3 * x1**2 + a) / (2 * y1);
    } else {
      s = (y2 - y1) / (x2 - x1);
    }

    const x = s**2 - x1 - x2;
    const y = s * (x1 - x) - y1;
    return {x, y};
  }

The implementation of multiplication between a point and a scalar is also quite simple, and it might look like the following:

  mul(p: Point, n: bigint): Point {
    let result = ZERO;
    for (let i = 0; i < n; i++) {
      result = this.add(result, p);
    }
    return result;
  }

However, when `n` is particularly large, the above implementation is extremely inefficient. Fortunately, it is also easy to [optimize](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_multiplication). Here I have borrowed the "binary expansion" technique introduced in the exclent book [Programming Bitcoin](https://github.com/jimmysong/programmingbitcoin/blob/master/ch03.asciidoc#coding-scalar-multiplication), and the optimized method looks like the following:

  mul(p: Point, n: bigint): Point {
    let coef = n;
    let current = p;
    let result = ZERO;
    while (coef) {
      if (coef & 1n) {
        result = this.add(result, current);
      }
      current = this.add(current, current);
      coef >>= 1n
    }
    return result;
  }

We're almost done! Finally, let's write some tests to see if our toy works. Here I am still using the examples and exercises from the book [Programming Bitcoin](https://github.com/jimmysong/programmingbitcoin/blob/master/ch02.asciidoc). Please look at the test code:

function testA5B7() {
  const a5b7 = new ECoverRN(5, 7);
  assert.deepEqual(a5b7.add(null, {x: 18, y: 77}), {x: 18, y: 77});
  assert.deepEqual(a5b7.add({x: 18, y: 77}, null), {x: 18, y: 77});
  assert.deepEqual(a5b7.add({x: 18, y: 77}, {x: 18, y: -77}), null);
  assert.deepEqual(a5b7.add({x: 2, y: 5}, {x: -1, y: -1}), {x: 3, y: -7});
  assert.deepEqual(a5b7.add({x: -1, y: -1}, {x: -1, y: -1}), {x: 18, y: 77});
  assert.deepEqual(a5b7.add({x: -1, y: 1}, {x: -1, y: 1}), {x: 18, y: -77});

  const p = {x: 2, y: 5};
  assert.deepEqual(a5b7.mul(p, 0n), null);
  assert.deepEqual(a5b7.mul(p, 1n), p);
  assert.deepEqual(a5b7.mul(p, 2n), a5b7.add(p, p));
  assert.deepEqual(a5b7.mul(p, 3n), a5b7.add(a5b7.add(p, p), p));
};

## Summary

The addition of real numbers can be considered as the addition of points on the one-dimensional real number line. Similarly, cryptographers have constructed point addition with the same rules on two-dimensional elliptic curves, which is the basis of the widely used ECC technology.

In this article, I introduced the Elliptic Curve over Real Numbers and the rules of point addition, and wrote a toy implementation in TypeScript. In the next article, I will introduce the Elliptic Curve over Finite Fields and make corresponding modifications to our toy code.

Buy me a cup of coffee if this article has been helpful to you:

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`