# Toy ECC in TypeScript (Part 4, Edwards Curves)

This is the fourth installment in my Toy ECC series. In [the first article](https://hackmd.io/@sp1derca7/crypto-ecc-1), I introduced [Elliptic Curves](https://en.wikipedia.org/wiki/Elliptic_curve) over Real Numbers and the rules governing point addition. Building on this foundational knowledge, [the second article](https://hackmd.io/@sp1derca7/crypto-ecc-2) delved into Elliptic Curves over Finite Fields, accompanied by the development of a toy EC library in TypeScript. In [the third article](https://hackmd.io/@sp1derca7/crypto-ecc-3), I explored the [ECDSA](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) digital signature algorithm and its verification process, leveraging our toy EC library to create a corresponding toy ECDSA library.

In this article, I will introduce [Edwards Curves](https://en.wikipedia.org/wiki/Edwards_curve). Given our familiarity with Elliptic Curves, discussing Edwards Curves will be relatively straightforward. Once the basic mathematical concepts of Edwards Curves have been covered, I will proceed to develop a toy library. This understanding of Edwards Curves, along with the toy library, will lay the groundwork for our exploration of [EdDSA](https://en.wikipedia.org/wiki/EdDSA) in the subsequent article.

Having introduced EdDSA, I intend to move on to [ECDH](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman) and [ECIES](https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme). Below is the roadmap for this series of articles, outlining our current position:


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

## Edwards Curve

Firstly, let us review the Elliptic Curves that have been discussed in the previous articles. We will start by focusing on Elliptic Curves over Real Numbers, and the equation of such curves is shown below.
$$
y^2 = x^3 + ax + b
$$

This type of equation is called a Weierstrass equation, and said to be in Weierstrass form, or Weierstrass normal form. Given a pair of real numbers `a` and `b`, a unique elliptic curve can be determined. For instance, when `a=3` and `b=10`, `a=-8` and `b=20`, and `a=-1` and `b=1`, these three curves are shown in the figure below (generated via [desmos.com](https://www.desmos.com/calculator)):


Edwards Curves also fall within the realm of Elliptic Curves. According to [Wikipedia](https://en.wikipedia.org/wiki/Edwards_curve):

>In [mathematics](https://en.wikipedia.org/wiki/Mathematics), the **Edwards curves** are a family of [elliptic curves](https://en.wikipedia.org/wiki/Elliptic_curve) studied by [Harold Edwards](https://en.wikipedia.org/wiki/Harold_Edwards_(mathematician)) in 2007. The concept of elliptic curves over [finite fields](https://en.wikipedia.org/wiki/Finite_fields) is widely used in [elliptic curve cryptography](https://en.wikipedia.org/wiki/Elliptic_curve_cryptography). Applications of Edwards curves to [cryptography](https://en.wikipedia.org/wiki/Cryptography) were developed by [Daniel J. Bernstein](https://en.wikipedia.org/wiki/Daniel_J._Bernstein) and [Tanja Lange](https://en.wikipedia.org/wiki/Tanja_Lange): they pointed out several advantages of the Edwards form in comparison to the more well known [Weierstrass form](https://en.wikipedia.org/wiki/Weierstrass_form).
>
>Every Edwards curve is [birationally equivalent](https://en.wikipedia.org/wiki/Birationally_equivalent) to an elliptic curve in [Montgomery form](https://en.wikipedia.org/wiki/Montgomery_curve), and thus admits an algebraic group law once one chooses a point to serve as a neutral element.

Like Elliptic Curves, let's first focus on Edwards Curves over Real Numbers, the equation for which is as follows:
$$
x^2 + y^2 = 1+d⋅x^2y^2
$$

Given a real number `d`, a unique curve of this type can be determined. For instance, taking `d = 0.3` and `d = 3` respectively, the two curves are depicted in the figure below. It appears that Edwards Curves are symmetric both horizontally and vertically. And if we rotate the curve 90 degrees around the origin, it will overlap with the original curve.


Just like ordinary Elliptic Curves, if we replace Real Numbers with Finite Fields, we obtain Edwards Curves over Finite Fields. The equation is as follows, where `p` is a prime number:

$$
x^{2} + y^{2} ≡ 1 + d⋅x^{2}y^{2} \pmod p
$$
For example, taking `d = 97` and `p = 103`, the "curve" appears as shown below (image generated via [graui.de](https://graui.de/code/ffplot/)):


We already know that point addition for ordinary Elliptic Curves needs to be handled in four different cases. However, for Edwards Curves, only one formula is required:

$$
(x_1,y_1)+(x_2,y_2)=(\frac{x_1y_2+y_1x_2}{1+dx_1x_2y_1y_2}, \frac{y_1y_2-x_1x_2}{1-dx_1x_2y_1y_2})
$$

Additionally, in the point addition of ordinary Elliptic Curves, the Identity point is the special Infinity. However, in the point addition of Edwards Curves, the [Identity](https://en.wikipedia.org/wiki/Additive_identity) point is `(0, 1)`. Moreover, in ordinary Elliptic Curves, the negative of a point `(x, y)` is `(x, -y)`. But in Edwards curves, it is `(-x, y)`.

## Twisted Edwards Curve

We have discussed Edwards Curves, but EdDSA is based on a type of curve called [Twisted Edwards Curves](https://en.wikipedia.org/wiki/Twisted_Edwards_curve). Below is the equation for Twisted Edwards Curves over Real Numbers:
$$
a⋅x^2+y^2 = 1 + d⋅x^2y^2
$$
It is easy to see that Edwards Curves are actually a special form of Twisted Edwards Curves. In the equation above, if we set `d` to be 1, we obtain Edwards Curves. Given any two real numbers `a` and `d`, a unique Twisted Edwards Curve can be determined. For instance, if we take `a=2`, `d=0.3`, and `a=10`, `d=6`, we get two curves that look like what is shown below. It seems that Twisted Edwards Curves are still symmetrical along both the x-axis and y-axis; however, rotating them 90 degrees around the origin no longer results in an overlap with the original curve.


By replacing Real Numbers with Finite Fields, we obtain Twisted Edwards Curves over Finite Fields. Below is the corresponding equation, where `p` denotes a prime number:
$$
a⋅x^{2} + y^{2} ≡ 1 + d⋅x^{2}y^{2} \pmod p
$$
By taking `a=10`, `d=6`, and `p=103`, we can obtain a specific Twisted Edwards Curve over a Finite Field, which looks like this:


By making slight modifications to the point addition formula for Edwards Curves, we can derive the point addition formula for Twisted Edwards Curves as shown below. Observant readers may have already spotted that an additional factor of `a` is multiplied with the $x_1x_2$ term in the upper right corner of the formula:
$$
(x_1,y_1)+(x_2,y_2)=(\frac{x_1y_2+y_1x_2}{1+dx_1x_2y_1y_2}, \frac{y_1y_2-ax_1x_2}{1-dx_1x_2y_1y_2})
$$

Like Edwards Curves, the Identity point of Twisted Edwards Curves is also `(0, 1)`, and the negative of a point is obtained by negating its x-coordinate. Note that the points on a (Twisted) Edwards Curve also form a [Group](https://en.wikipedia.org/wiki/Group_(mathematics)) under the addition rule, and the points on a (Twisted) Edwards Curve over a Finite Field form a [Finite Group](https://en.wikipedia.org/wiki/Finite_group) under the addition rule.

The following table is a brief summary of ordinary Elliptic Curves (in Weierstrass form), Edwards Curves and Twisted Edwards Curves:

| Elliptic Curves over Real Numbers | Equation | Identity Point | Negative of (x, y) |
| --------------------------------- | ----------------------------- | -------------- | ------------------ |
| In Weierstrass form | `y^2 = x^3 + a⋅x + b` | `Infinity` | `(x, -y)` |
| Edwards Curves | `x^2 + y^2 = 1 + d⋅x^2⋅y^2` | `(0, 1)` | `(-x, y)` |
| Twisted Edwards Curves | `a⋅x^2 + y^2 = 1 + d⋅x^2⋅y^2` | `(0, 1)` | `(-x, y)` |

## Toy Library

Now that we have a basic understanding of Twisted Edwards Curves and the point addition rules on these curves, it is time to create our toy library. First, we define a `Point` type, which is simpler than its Weierstrass counterpart because we do not need to deal with the special Identity point (we instantiate and name it `ZERO`):

export const ZERO: Point = {x: 0n, y: 1n};

export type Point = {
  readonly x: bigint,
  readonly y: bigint,
};

Then, we'll proceed to write the `EDoverFF` class, whose framework is outlined below. As with the rest of the code in this series, since it's merely a toy implementation, I'll skip most of the sanity checks and focus solely on the essential logic.

// a⋅x^2 + y^2 = 1 + d⋅x^2⋅y^2 (mod p)
export class EDoverFF {

  readonly a: bigint;
  readonly d: bigint;
  readonly f: FiniteField;

  constructor(a: bigint, d: bigint, p: bigint) {
    this.a = mod(a, p);
    this.d = mod(d, p);
    this.f = new FiniteField(p);
  }

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

}

The `includes()` method determines whether a certain point lies on the curve, and the code is shown below:

  includes(p: Point): boolean {
    const _add = (a: bigint, b: bigint) => this.f.add(a, b);
    const _mul = (a: bigint, b: bigint) => this.f.mul(a, b);
    const _pow = (a: bigint, b: bigint) => this.f.pow(a, b);

    const {x, y} = p;
    const {a, d} = this;
    const xx = _pow(x, 2n);
    const yy = _pow(y, 2n);

    const left = _add(_mul(a, xx), yy);
    const right = _add(1n, _mul(d, _mul(xx, yy)));
    return left == right;
  }

The `add()` method is the core of the entire class, implementing the point addition algorithm, and the code is shown below:

  add(p1: Point, p2: Point): Point {
    const _add = (a: bigint, b: bigint) => this.f.add(a, b);
    const _sub = (a: bigint, b: bigint) => this.f.sub(a, b);
    const _mul = (a: bigint, b: bigint) => this.f.mul(a, b);
    const _div = (a: bigint, b: bigint) => this.f.div(a, b);
    const [a, d, x1, y1, x2, y2] = [this.a, this.d, p1.x, p1.y, p2.x, p2.y];

    const x1y2 = _mul(x1, y2);
    const y1x2 = _mul(y1, x2);
    const y1y2 = _mul(y1, y2);
    const x1x2 = _mul(x1, x2);
    const ax1x2 = _mul(a, x1x2);
    const dx1x2y1y2 = _mul(d, _mul(x1x2, y1y2));
    const x = _div(_add(x1y2, y1x2), _add(1n, dx1x2y1y2));
    const y = _div(_sub(y1y2, ax1x2), _sub(1n, dx1x2y1y2));

    return {x, y};
  }

The `mul()` method calculates the multiplication of a scalar and a point (that is, adding a certain point to itself multiple times), and its code can be copied verbatim from [the previous article]():

  mul(n: bigint, p: Point): 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 already know that for ECDSA, cryptographers have designed many curves and given them names, such as [secp256k1](https://neuromancer.sk/std/secg/secp256k1). The same is true for EdDSA; cryptographers have also designed many Twisted Edwards Curves and named them, like [ed25519](https://neuromancer.sk/std/other/Ed25519). The next article will go into detail about the ed25519 curve, while in this article, we simply use it to test our toy library. Below is the test code:

  it('ed25519', function () {
    const p = 2n ** 255n - 19n;
    const f = new FiniteField(p);
    const a = f.neg(1n); // -1
    const d = f.neg(f.div(121665n, 121666n)); // -121665/121666
    const c = new EDoverFF(a, d, p);

    expect(p).to.equal(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffedn);
    expect(a).to.equal(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffecn);
    expect(d).to.equal(0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3n);
    expect(c.includes(ZERO)).to.be.true;

    const n = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3edn;
    const g = {
      x: 0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51An,
      y: 0x6666666666666666666666666666666666666666666666666666666666666658n,
    };
    expect(c.includes(g)).to.be.true;
    expect(c.mul(n, g)).to.deep.equal(ZERO);

    for (let i = 0n; i <= 10n; i++) {
      expect(c.includes(c.mul(i, g))).to.be.true;
    }
  });

## Summary

Let's briefly summarize the key points discussed in this article:

* The Elliptic Curves discussed in our previous articles, also known as Weierstrass form, have the equation: $y^2 = x^3 + ax + b$
* There is another family of Elliptic Curves called Edwards Curves, whose equation is: $x^2 + y^2 = 1 + d \cdot x^2y^2$
* Edwards Curves are a special case of Twisted Edwards Curves, with the equation: $a \cdot x^2 + y^2 = 1 + d \cdot x^2y^2$
* The points on a (Twisted) Edwards Curve also form a Group under the addition rule, and the points on a (Twisted) Edwards Curve over a Finite Field form a Finite Group under the addition rule.
* For Twisted Edwards Curves over Finite Fields, we have written a toy library in TypeScript and conducted simple tests using the parameters of ed25519.

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

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`