# Toy ECC in TypeScript (Part 3, ECDSA)

This is the third article in my Toy ECC series. In [the first article](https://hackmd.io/@sp1derca7/crypto-ecc-1), I introduced the basic concepts of [Elliptic Curves over Real Numbers](https://en.wikipedia.org/wiki/Elliptic_curve#Elliptic_curves_over_the_real_numbers) and the rules for Point addition. In [the second article](https://hackmd.io/@sp1derca7/crypto-ecc-2), I first introduced the basic concepts of [Group](https://en.wikipedia.org/wiki/Group_(mathematics)) and [Field](https://en.wikipedia.org/wiki/Field_(mathematics)), then talked about [Elliptic Curves over Finite Fields](https://en.wikipedia.org/wiki/Elliptic_curve#Elliptic_curves_over_finite_fields), and also wrote a toy library using TypeScript. In this article, I will introduce the widely used [Elliptic Curve Digital Signature Algorithm](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) (abbreviated as ECDSA).

First, we need to briefly review the mathematical knowledge behind Elliptic Curves. Then, I will introduce the famous [Discrete Logarithm Problem](https://en.wikipedia.org/wiki/Discrete_logarithm) (abbreviated as DLP) and the [Secp256k1](https://en.bitcoin.it/wiki/Secp256k1) curve, as well as ECC key generation and ECDSA signature and verification algorithms. Finally, we will use the previously prepared EC library to write a toy ECC library that implements the ECDSA signature and verification algorithms, and provide a practical example in conjunction with the [Ethereum](https://ethereum.org/en/) blockchain and its [ethers.js](https://github.com/ethers-io/ethers.js/) library.

This article mainly references two books: "[Programming Bitcoin](https://github.com/jimmysong/programmingbitcoin)" and "[Serious Cryptography, Second Edition](https://nostarch.com/serious-cryptography-2nd-edition)". These two books are highly recommended for readers who are interested in cryptography and blockchain.

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

## A Brief Recap of Elliptic Curves

Let's briefly review the mathematical basics behind elliptic curves that were introduced in the first two articles:

* The set of real numbers forms a Group under addition and a Field under both addition and multiplication.
* Integers modulo p (where p is Prime Number) form a [Finite Group](https://en.wikipedia.org/wiki/Finite_group) under modular addition and a [Finite Field](https://en.wikipedia.org/wiki/Finite_field) under both modular addition and multiplication.
* An Elliptic Curve over Real Numbers refers to a curve in the Cartesian coordinate system of the form $y^2=x^3+ax+b$. For points on such a curve, we have defined an addition rule that fully complies with the properties of real number addition, thus forming a Group.
* Elliptic Curves can actually work under any Field, including Finite Fields. Therefore, by replacing real numbers with integers modulo p, we obtain Elliptic Curves over Finite Fields, which are defined as: $y^2≡x^3+ax+b \pmod p$.
* The number of points on an Elliptic Curve over Finite Fields is finite, forming a Finite Group under addition. If we choose one of the points as a Generator, it can generate a [Cyclic Subgroup](https://en.wikipedia.org/wiki/Cyclic_group).

## The Discrete Logarithm Problem

We know that every asymmetric encryption algorithm relies on a [Trapdoor Function](), grounded in a hard problem. While this problem is relatively easy to construct, it is extremely difficult to solve. For [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)), the problem is [Integer Factorization](). For ECC, it's the [Discrete Logarithm Problem](https://en.wikipedia.org/wiki/Discrete_logarithm) (abbreviated as DLP).

In my [Toy RSA](https://hackmd.io/@sp1derca7?utm_source=preview-mode&utm_medium=rec&tags=%5B%22RSA%22%5D) series of articles, I have introduced the prime factorization problem. Simply put, given two very large prime numbers `p` and `q`, it is very easy to calculate their product `n`, but knowing `n` and wanting to find out `p` and `q` is extremely difficult:
$$
p×q=n
$$
In the previous two articles, we have devoted some space to introducing Group theory. As discussed earlier, we know that integers modulo p (where p is a prime number) form a Finite Group under modular addition. In fact, integers modulo p also form a Finite Group under modular multiplication. Suppose there is such a Finite Group based on modular multiplication, whose modulus is some prime number `p`. Select an integer `a` in this group, and let it multiply itself `k` times to obtain another integer `b`. We can use exponential notation to abbreviate the operation of continuously multiplying a number by itself, so we can write this equation as:
$$
a^k ≡ b \pmod p
$$
If `a` and `k` are particularly large, the computation described above is relatively easy. However, conversely, determining `k` given `a` and `b` is extremely difficult. This is the DLP Problem. Since the inverse operation of exponentiation is logarithms, we express the solution to this equation using logarithmic notation:
$$
k ≡ log_a b \pmod p
$$

For an Elliptic Curve over Finite Fields, the points on it form a Finite Group under point addition. The DLP problem described above is also applicable in this group, with multiplication being replaced by point addition. Given such a curve and a point `P` on it, adding `P` to itself `k` times (scalar multiplication) yields another point `Q`. We can express this relationship as:
$$
k⋅P=Q
$$

If the order of the group and `k` are very large, the above calculation is relatively easy. However, conversely, knowing `P` and `Q`, finding `k` is extremely difficult. This is the ECDLP (Elliptic Curve DLP) problem. The following table summarizes the DLP and ECDLP problems:

| Group | Group Operation | DLP | Problem |
| -------------------------------- | ---------------------- | ----------------- | --------------------------- |
| Integers Modulo p | Modular Multiplication | `a^k ≡ (b mod p)` | Given `a` and `b`, find `k` |
| Elliptic Curve over Finite Field | Points Addition | `k⋅P=Q` | Given `P` and `Q`, find `k` |

## Secp256k1

According to the summary above, given parameters `a`, `b`, and `p` (where `p` is a prime number), a unique Elliptic Curve over a Finite Field can be determined. To construct the ECC algorithm, we also need to select a point `G(x, y)` on the curve to serve as the [Generator](https://en.wikipedia.org/wiki/Generating_set_of_a_group) and need to know the [Order](https://en.wikipedia.org/wiki/Order_(group_theory)) `n` of the Cyclic Subgroup it generates (usually, `n` is also a prime number). Determining all these parameters is a specialized discipline and is beyond the scope of this article. In any case, we should never attempt to determine these parameters ourselves. Cryptographers have defined many sets of such parameters and have named these specific curves. We should only use these widely accepted curves.

In this article, we focus on the [Secp256k1](https://en.bitcoin.it/wiki/Secp256k1) curve, because blockchains such as [Bitcoin](https://github.com/bitcoin-core/secp256k1) and [Ethereum](https://github.com/ethereum/go-ethereum/blob/master/crypto/secp256k1/secp256.go) use this curve. Other well-known curves include [Secp256r1](https://neuromancer.sk/std/secg/secp256r1), [Curve25519](https://en.wikipedia.org/wiki/Curve25519) etc. Below are the parameters of the Secp256k1 curve:

| Param | Value |
| ----- | ------------------------------------------------------------ |
| a | `0` |
| b | `7` |
| p | `0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f` |
| Gx | `0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798` |
| Gy | `0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8` |
| n | `0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141` |

The equation of this curve is very simple: `y^2=x^3 + 7`. The following figure shows what this curve looks like over the real numbers (left) and integers modulo 103 (right). Note that `p` (`2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1`) and `n` are both very close to `2^256`, and `n` is a prime number.


## KeyGen

The process of generating key pairs for ECC is very straightforward. As we have discussed, the three parameters `a`, `b`, and `p` determine an elliptic curve over a finite field. Additionally, we require a point `G(x, y)` on the curve to serve as a generator, which can generate a cyclic subgroup of order `n`. Thus, `a`, `b`, `p`, `G`, and `n` together specify a cryptographic curve. Taking the curve Secp256k1 as an example, we generate the key pair through the following process:

* Generate a 256-bit random number `d`, which serves as the Private Key.
* Add `G` to itself `d` times to compute a point `P`; in other words, `P = d⋅G`. This point is the Public Key.

The ECC key generation process is shown in the following figure:


## ECDSA

The ECDSA signature generation and verification algorithms appear to be a bit more complex. Let's first take a look at the signature generation algorithm. Suppose the message to be signed is denotated as `m`; we follow these steps to generate the signature:

- First, we compute the digest `h` of `m` using a cryptographic hash algorithm (such as SHA-256), where `h` is in the range `(0, n-1)`.
- Next, we generate another random number `k`, which is also in the range `(1, n-1)`.
- Then, we calculate the point `Q(x, y) = k⋅G` and take `r = x mod n`.
- After that, we compute `s = (h + rd) / k mod n`.
- Finally, the pair `(r, s)` constitutes the desired signature.

The ECDSA signature generation algorithm can be represented by the following figure:


Next, we examine the signature verification algorithm, given the signature `(r, s)`:

- First, we calculate the multiplicative inverse of `s`, `w`. Since `s = (h + rd)/k mod n`, we have `w = k / (h + rd) mod n`.
- Then, we compute `u = hw mod n` and `v = rw mod n`.
- Finally, we calculate `uG + vP`, which must equal `kG`.

Because we know that:
$$
\begin{align*}
u + vd &= wh + wrd \\
&= hk÷(h+rd) + drk÷(h+rd) \\
&= (hk+drk)÷(h+dr) \\
&= k(h+dr)÷(h+dr) \\
&= k
\end{align*}
$$

So we have:

$$
\begin{align*}
uG + vP &= uG + vdG \\
&= (u + vd)G \\
&= kG
\end{align*}
$$

The ECDSA signature verification algorithm can be represented by the following figure:


## Toy Library

In the previous article, we wrote a toy library in TypeScript that implemented elliptic curves over finite fields and point addition. In this section, we'll use this library to create a toy ECC library, implementing key pair generation, signature generation, and signature verification algorithms. Since it's a toy library, I'll still omit some necessary checks. Please see the main code of this toy library below:

import { randomBytes } from 'crypto';
import { ECoverFF, Point } from './ec_ff';
import { expmod } from './math';

export class ECC {

  readonly C: ECoverFF;    // curve
  readonly G: Point;       // generator
  readonly N: bigint;      // order
  readonly keyLen: number; // in bytes

  constructor(c: ECoverFF, g: Point, n: bigint, keyLen=32) {
    this.C = c;
    this.G = g;
    this.N = n;
    this.keyLen = keyLen;
  }

  mulG(x: bigint): Point {
    return this.C.mul(x % this.N, this.G);
  }

  keyGen(): [bigint, Point] { ... }
  sign(privKey: bigint, h: bigint, k?: bigint): Signature { ... }
  verifySig(pubKey: Point, h: bigint, sig: Signature): boolean { ... }

}

The `mulG()` helper function assists us in calculating the multiplication of a scalar `x` and the generator point `G`. The `keyGen()` method randomly generates a key pair, and its code is as follows:

  keyGen(): [bigint, Point] {
    const d = BigInt('0x' + randomBytes(this.keyLen).toString('hex'));
    const P = this.mulG(d);
    return [d, P];
  }

The `sign()` method generates a signature using the private key `d`, message digest `h`, and a random number `k`. Below is the code:

  sign(privKey: bigint, h: bigint, k?: bigint): Signature {
    const d = privKey;
    const {N} = this;
    k = k || BigInt('0x' + randomBytes(this.keyLen).toString('hex'));

    const {x:r, y} = this.mulG(k!)!;   // kG
    const k_inv = expmod(k!, N-2n, N); // k^-1
    let s = (h + r*d) * k_inv % N;     // (h+rd)/k mod n 
    if (s > N/2n) { s = N - s; }
    return {r, s};
  }

The `verifySig()` method verifies the signature `sig` based on the public key `P` and message digest `h`. The code is as follows:

  verifySig(pubKey: Point, h: bigint, sig: Signature): boolean {
    const P = pubKey;
    const {C, G, N} = this;
    const {r, s} = sig;
    const w = expmod(s, N-2n, N);  // s^-1
    const u = h * w % N;           // u
    const v = r * w % N;           // v
    const uG = C.mul(u, G);        // uG
    const vP = C.mul(v, P);        // vP
    const {x, y} = C.add(uG, vP)!; // uG + vP
    return x == r;
  }

We define a type to represent a signature, which includes two fields: `r` and `s`. The code is as follows:

export type Signature = {
  readonly r: bigint;
  readonly s: bigint;
}

Lastly, we instantiate a curve with the parameters of the Secp256k1 curve, which we'll naturally name `secp256k1`. The code is as follows:

export const secp256k1 = new ECC(
  new ECoverFF(0n, 7n, 2n**256n - 2n**32n - 977n),
  {
    x: 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798n,
    y: 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8n,
  },
  0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141n,
  32, // keyLen
);

## A Practical Example

In this section, we'll examine a practical example. First, we'll use Ethereum's [ethers.js](https://github.com/ethers-io/ethers.js/) library to generate a Secp256k1 key pair and print them out. Next, we'll use this library to compute the digest of a message (Ethereum's main hash function is [Keccak256](https://en.wikipedia.org/wiki/SHA-3)) and print it out. Finally, we'll use this library to sign the same message and print the resulting signature. Below is the test code:

function testSign() {
  const wallet = ethers.Wallet.createRandom();
  console.log('privKey:', wallet.privateKey);
  console.log('pubKey :', wallet.publicKey);

  const msg = 'Toy ECC in TypeScript';
  const digest = ethers.hashMessage(msg);
  console.log('digest:', digest);

  const sig = wallet.signMessageSync(msg);
  console.log('sig:', sig);
}

Running the above test prints out:

privKey: 0x57a690411e3afd01e619cc83a10436c236970eca25ecce10b6f15c2bc8cc0958
pubKey : 0x0207ebe23895d254ef44d79226938aa21daef6afdeb572852ef44bc8b4cbb61f88
digest: 0xa83362a93e6fc3cc85612bb150f00072d474820cd7348754f0b268b2659956a4
sig: 0xf02e0bda2e165d139d7cf4271182588014bf2fb844e6d42b889af617002827e9097a7ddd4330b99eb90a2e9cf19da975124d753bee2512b2979ca93cfec052b31c

In the output above, the private key is a 32-byte random number, as expected. However, observe the public key (a point on the curve)—it's not 64 bytes (for both x and y coordinates) but 33 bytes. This is because Ethereum adopts Bitcoin's public key compression format, recording only the x-coordinate, from which the y-coordinate can be derived. As we know, elliptic curves are horizontally symmetrical, yielding two possible y-coordinates given an x-coordinate. If it's an Elliptic Curve over Real Numbers, one y-coordinate will be positive and the other negative. If it's an Elliptic Curve over Finite Fields, one y-coordinate will be odd and the other even. Since we are talking about finite fields, the public key has an extra byte prefix: 02 indicates that the y-coordinate is even, and 03 indicates that it is odd. For more discussion on compressed public keys, please refer to [this question](https://ethereum.stackexchange.com/questions/103482/what-is-the-difference-between-compressed-and-uncompressed-public-key).

The situation with signatures is similar. We know that an ECDSA signature consists of two 32-byte integers, `r` and `s`. Ethereum's signature concatenates `r` and `s`, and then adds a 1-byte suffix `v`, making it a total of 65 bytes. Given the message digest and the signature, in addition to verification, we can also compute the corresponding public key from the signature. Similarly, this public key has two possible forms, which are horizontally symmetric. The suffix `v` can help us determine whether the y-coordinate of the public key is odd or even. For more information on `r`, `s`, and `v`, please refer to [this question](https://ethereum.stackexchange.com/questions/15766/what-does-v-r-s-in-eth-gettransactionbyhash-mean).

Based on the data printed out by the test and the discussions above, we can obtain the private key (`d`), the public key's x-coordinate (`px`), the message digest (`h`), and the signature (`r` and `s`). We can then use our toy library to verify the signature, as shown in the following code:

function testVerify() {
  const d = 0x57a690411e3afd01e619cc83a10436c236970eca25ecce10b6f15c2bc8cc0958n;
  const px = 0x07ebe23895d254ef44d79226938aa21daef6afdeb572852ef44bc8b4cbb61f88n;
  const h = 0xa83362a93e6fc3cc85612bb150f00072d474820cd7348754f0b268b2659956a4n
  const sig = {
    r: 0xf02e0bda2e165d139d7cf4271182588014bf2fb844e6d42b889af617002827e9n,
    s: 0x097a7ddd4330b99eb90a2e9cf19da975124d753bee2512b2979ca93cfec052b3n,
  };

  const P = secp256k1.mulG(d);
  assert.equal(P?.x, px, 'x');

  assert.ok(secp256k1.verifySig(P, h, sig));
}

## Summary

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

- Asymmetric encryption algorithms depend on a trapdoor function, which is an easy-to-construct but extremely challenging problem to solve. For RSA, this problem involves prime factorization. For ECC, it is the ECDLP problem.
- To utilize ECC, one must select a curve (defined by parameters `a`, `b`, `p`), identify a generator point `P` on this curve, and understand the order `n` of the cyclic group it generates. Cryptographers have established some parameter sets for these specific curves, with Secp256k1, used by both Bitcoin and Ethereum, highlighted in this article.
- We explored ECC key pair generation, signature generation, and signature verification algorithms, and wrote a toy ECC library in TypeScript.
- Additionally, we employed the ethers.js library from the Ethereum blockchain to generate a real key pair, produce a digital signature, and verify it using our toy library.

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

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`