# Toy RSA in TypeScript (Part 1, Basic Concepts)

The importance of [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) for Blockchains, the Crypto world, and even the entire Internet goes without saying, and this [blog](https://doctrina.org/The-3-Seminal-Events-In-Cryptography.html) has a great summary. The author also wrote a two-part series that is very good, detailing [how](https://doctrina.org/How-RSA-Works-With-Examples.html) and [why](https://doctrina.org/Why-RSA-Works-Three-Fundamental-Questions-Answered.html) RSA works. But I still feel that his explanation is a bit complicated and could be simpler. So I wrote this article, trying to explain RSA clearly with the least amount of mathematical knowledge and an appropriate amount of TypeScript code. I hope I can achieve this goal without making a mistake. Wish me luck!

## A Little Math

I have two pieces of news to tell the readers, one bad and one good. The bad news is that some basic mathematical knowledge is essential to understand RSA and to follow this article. The good news is that we don't need to delve into highly advanced mathematics; just some simple knowledge about [Integers](https://en.wikipedia.org/wiki/Integer) will suffice. I believe that most readers can understand this knowledge. We don't even need to worry too much about negative integers. In the following discussion, unless specifically stated otherwise, all integers refer to **positive integers**. Let's get started!

### Greatest Common Divisor

Let's first review the integer [division](https://en.wikipedia.org/wiki/Division_(mathematics)) we learned from primary school. Suppose there are four integers `a`, `b`, `c`, and `r` that satisfy the following **equation 1.1**. We know that `a` is called the **dividend**, `b` is called the **divisor**, `c` is called the **quotient**, and `r` is called the **remainder**.
$$
a \div b = c \dots r
$$
Given three integers `a`, `b`, and `c`, if `c` can divide both `a` and `b` without leaving a remainder, then `c` is called a **Common Divisor** of `a` and `b`. Among all the `c` we can find, the largest one is called the **[Greatest Common Divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)** of `a` and `b`, abbreviated as **GCD**. For example, if `a=8` and `b=12`, the integers that can divide both of them are: `1`, `2`, `4`, so `4` is the GCD.

#### Euclidean Algorithm

Given two integers `a` and `b`, we can use the [Euclidean Algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) to calculate their GCD. This algorithm is very simple, and I won't introduce it in detail here. I will implement the `gcd` function in TypeScript, and here is its code:

function gcd(a: bigint, b: bigint): bigint {
  if (b == 0n) { return a; }
  return gcd(b, a%b);
}

Here are some test cases:

function testGCD() {
  assert.equal(gcd(8n, 12n), 4n);
  assert.equal(gcd(54n, 24n), 6n);
  assert.equal(gcd(42n, 56n), 14n);
  assert.equal(gcd(180n, 48n), 12n);
  assert.equal(gcd(18n, 48n), 6n);
}

#### Extended Euclidean Algorithm

Given two integers `a` and `b`, the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) can not only find their GCD, but also find two other integers `x` and `y` such that the following **equation 1.2** holds:
$$
a⋅x + b⋅y = gcd(a, b)
$$
The Extended Euclidean Algorithm is also quite simple, so I will still directly provide the code for the TypeScript function here:

function xgcd(a: bigint, b: bigint): [bigint, bigint, bigint] {
  if (b == 0n) { return [1n, 0n, a]; }
  const [x, y, d] = xgcd(b, a%b);
  return [y, x-y*(a/b), d];
}

Here are some test cases:

function testXGCD() {
  assert.deepEqual(xgcd(240n, 46n), [ -9n, 47n, 2n ]);
  assert.deepEqual(xgcd(46n, 240n), [ 47n, -9n, 2n ]);
  assert.deepEqual(xgcd(11n, 26n), [ -7n, 3n, 1n ]);
  assert.deepEqual(xgcd(26n, 11n), [ 3n, -7n, 1n ]);
}

#### Coprime Integers

If the GCD of two numbers `a` and `b` is 1, we say that these two numbers are [coprime](https://en.wikipedia.org/wiki/Coprime_integers), or relatively prime, or mutually prime. In other words, `a` and `b` are coprime integers if `GCD(a, b) = 1`. If we want to write an `isCoprime()` function, its code is also very simple, as shown below:

function isCoprime(a: bigint, b: bigint): boolean {
  return gcd(a, b) == 1n;
}

#### Euler's Totient Function

Given an integer `n`, we can find all integers that are coprime to it. Sometimes we are only interested in the number of coprime integers to `n`. In mathematics, the function that finds this number is called [Euler's Totient Function](https://en.wikipedia.org/wiki/Euler%27s_totient_function), usually denoted as `φ(n)`. In this article, we are not concerned with the details of `φ(n)`. We just assume that there is a function that can calculate `φ(n)`, such as the following function:

function φ(n: bigint): bigint {
  ...
}

However, there is a particularly important property of `φ(n)` that we must know. Suppose the GCD of two integers `a` and `b` is 1, that is to say, `a` and `b` are coprime, then **equation 1.3** holds:
$$
\begin{align*}
gcd(a, b) &= 1 \Rightarrow \\
φ(a⋅b) &= φ(a)⋅φ(b)
\end{align*}
$$

### Prime Number

If an integer `n` greater than 1 is divisible only by 1 and itself, we say that this integer is a [Prime Number](https://en.wikipedia.org/wiki/Prime_number). In other words, given a prime number `p` and an integer `x` that satisfies the condition `1 <= x < p `, then `GCD(x, p) = 1`. Therefore, for some prime number `p`, we can quickly obtain its `φ(p)`, using **equation 1.4**:
$$
\begin{align*}
isPrime(p) \Rightarrow \\
φ(p) = p - 1
\end{align*}
$$
Based on this, we can slightly optimize the previous `φ()` function, and the updated code is as follows:

function φ(n: bigint): bigint {
  if (isPrime(n)) {
    return n - 1n;
  }
  ...
}

#### Factoring Problem

If an integer `n` is not a prime number, then we can factor it into the product of several prime numbers, a process called [Integer Factorization](https://en.wikipedia.org/wiki/Integer_factorization). For example, 30 is not a prime number, so we can factor it as `2 × 3 × 5`. Here I introduce a [hard](https://en.wikipedia.org/wiki/Computational_hardness_assumption) problem, called the [Prime Factorization Problem](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic).

Given two very large prime numbers `p` and `q`, it is easy to calculate their product `n = p × q`. However, if we only know the product `n` and want to factor out `p` and `q`, it is quite difficult. Please note that this hard problem is very important; it is the cornerstone of the entire RSA system.

#### Primality Test

Next, let's consider a relatively simple question: Given an integer `n`, how can we [determine](https://en.wikipedia.org/wiki/Primality_test) whether it is a prime number? Generally speaking, there are two types of methods. The first type can give an exact answer, such as the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). Although this method is precise, it is very slow for large integers `n`. The second type can only give a correct answer with a sufficiently high probability, but it is very fast. For example, the [Miller-Rabin](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) or the [Fermat](https://en.wikipedia.org/wiki/Fermat_primality_test) method.

How to determine prime numbers is not the focus of this article, so we will not discuss these methods in depth here, and we assume that there is such a function to help us make judgments:

function isPrime(n: bigint): boolean {
  ...
}

#### Random Prime Number Generation

What we really care about is how to randomly generate a very large prime number. One feasible method is: first generate a sufficiently large random number (note that you must use a cryptographically secure [random number generator](https://en.wikipedia.org/wiki/Random_number_generation)), and then determine whether it is a prime number. If not, increase it by 1 until a prime number is obtained.

Fortunately, Node.js comes with a `generatePrimeSync()` function that we can use directly. The following function can help us generate a random prime number of given size in bits:

import { generatePrimeSync } from 'crypto';

function genRandomPrime(bits: number): bigint {
  const arrBuf = generatePrimeSync(bits);
  return BigInt('0x' + Buffer.from(arrBuf).toString('hex'));
}

### Modular Arithmetic

At the beginning of the article, we recalled the integer division operation we learned as children. If we are only concerned with the remainder and not the quotient, we arrive at the [modulo operation](https://en.wikipedia.org/wiki/Modular_arithmetic), commonly known as the mod operation. Given four integers `a`, `m`, `x`, `b`, and the division equation `a ÷ m = x ... b`, we can convert it into a mod operation, which is **equation 1.5**:
$$
a \bmod m = b
$$
In mathematics and cryptography, if two integers `a` and `b` satisfy the following **equation 1.6**:
$$
a \bmod m = b \bmod m
$$
Then we can write this equation in a special form (you need some time to get used to it), which is the following **equation 1.7**:
$$
a ≡ b \pmod m
$$

#### Basic Properties

The modulo operation has some basic [properties](https://en.wikipedia.org/wiki/Modular_arithmetic#Basic_properties) that we need to grasp in order to understand RSA, which I will briefly introduce here. Based on the definitions above, we can immediately obtain the following **equation 1.8** (which is obvious):
$$
a ≡ a \bmod m \pmod m
$$
If there are two integers `a` and `b` that satisfy equation 1.7, then for any integer `k`, the following **equation 1.9** and **equation 1.10** hold true:
$$
\begin{align*}
k⋅a &≡ k⋅b \pmod m \\
a^k &≡ b^k \pmod m
\end{align*}
$$
But, under normal circumstances, the following **equation 1.11** does not hold:
$$
k^a ≡ k^b \pmod m
$$
However, if the integers `a`, `b`, `m`, `k` satisfy the following condition, then equation 1.11 above holds. Here `φ` is Euler's Totient function, and `gcd` is the Greatest Common Divisor.
$$
\begin{align*}
a ≡ b \pmod{φ(m)} \\
gcd(k, m) = 1
\end{align*}
$$
Please note that these properties of the modulo operation are very important. We will use these equations to prove that RSA encryption/decryption works.

#### Multiplicative Inverse

In multiplication, given a number `a`, if another number `b` satisfies `a × b = 1`, we call `b` the [Multiplicative Inverse](https://en.wikipedia.org/wiki/Multiplicative_inverse) of `a`. This definition also holds true for mod operations. For integers `a`, `b`, and `m`, if the following **equation 1.12** holds, we call `b` the [Modular Multiplicative Inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of `a`.
$$
a⋅b = 1 \pmod m
$$
Now, the question arises: given `a` and `m`, how can we find `b`? In this article, we focus solely on the scenario where `a` and `m` are coprime integers, meaning `GCD(a, m) = 1`. In this case, we can use the Extended Euclidean Algorithm to find `x` and `y` such that the following **equation 1.13** holds:
$$
a⋅x + m⋅y = gcd(a, m) = 1
$$
In this context, we can disregard `y`, and `x` is precisely the `b` we seek. Please note that the value of `x` we obtain could be negative, so we must employ a modulo operation to convert it into a positive number. With this knowledge, we can write an `inverse()` function, as illustrated below:

function inverse(a: bigint, m: bigint): bigint {
  const [x, _y, d] = xgcd(a, m);
  assert.equal(d, 1n);
  return x < 0n ? x + m : x;
}

Alright, this is all the mathematical knowledge we need. Next, I will introduce the basic idea of RSA.

## The Basic Idea

The basic idea of RSA is both clever and simple. We need to find three very large integers: `e`, `d`, and `n`, such that the following two equations hold:
$$
\begin{align*}
E(x, e, n) = x^e \bmod n = y \\
D(y, d, n) = y^d \bmod n = x
\end{align*}
$$
In [Asymmetric Cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography), we refer to `(e, n)` as the **Public Key**, `(d, n)` as the **Private Key** (or **Secret Key**), `E()` as the **Encryption Function**, `D()` as the **Decryption Function**, `x` as the **Plaintext**, and `y` as the **Ciphertext**. We use the public key to encrypt plaintext and the private key to decrypt ciphertext. Now I will introduce how to find such three very large integers.

Step 1: Randomly generate two very large prime numbers: `p` and `q`, then calculate `n = p * q`. We have already discussed how to generate very large random prime numbers in previous sections, and we have also written a function to do this.

Step 2: Calculate Euler's Totient Function for `n`, that is, `φ(n)`. Since `n = p * q`, and both `p` and `q` are prime numbers, we can easily compute `φ(n)` according to equations 1.3 and 1.4. However, it is very difficult for others to do so; therefore, both `p` and `q` must also be kept secret along with `d`. (Remember? Factoring `n` into `p` and `q` is very difficult.)
$$
\begin{align*}
φ(n) &= φ(p⋅q) \\
&= φ(p)⋅φ(q) \\
&= (p-1)⋅(q-1)
\end{align*}
$$
Step 3: Choose a prime number `e` (`1 < e < φ(n)`, typically 65537), such that:
$$
gcd(e, φ(n)) = 1
$$

Step 4: Calculate the multiplicative inverse of `e`, which is `d`. In other words, find `d` such that the following equation holds. We can use the Extended Euclidean Algorithm to compute `d`.
$$
d⋅e ≡ 1 \pmod{φ(n)}
$$
Now that we have obtained the public key `(e, n)` and the private key `(d, n)`, let's look at the encryption function. Given the plaintext `m`, after encryption, we get the ciphertext `c`:
$$
\begin{align*}
E(m) &= m^e \bmod n \\
&= c
\end{align*}
$$
And now comes the most important part, let's prove that the ciphertext can indeed be decrypted back to the plaintext. Clearly:
$$
\begin{align*}
D(c) &= c^d \bmod n \\
&= (m^e \bmod n)^d \bmod n \\
\end{align*}
$$

According to equations 1.8 and 1.10, we can further derive:
$$
\begin{align*}
D(c) &= c^d \bmod n \\
&= (m^e \bmod n)^d \bmod n \\
&= (m^e)^d \bmod n \\
&= m^{d⋅e} \bmod n \\
\end{align*}
$$
Since `d⋅e ≡ 1 (mod φ(n))`, and `gcd(m, n) = 1`, according to equation 1.11, we can finally conclude that:
$$
\begin{align*}
D(c) &= c^d \bmod n \\
&= (m^e \bmod n)^d \bmod n \\
&= (m^e)^d \bmod n \\
&= m^{d⋅e} \bmod n \\
&= m^1 \bmod n \\
&= m
\end{align*}
$$
The basic working principle of RSA is shown in the following figure:

## The Toy Implementation

It's time to translate the knowledge we've learned into code. I will use TypeScript to write a toy RSA implementation. However, I must remind readers that, apart from toys, **you should never attempt to implement RSA or any cryptographic algorithm on your own**. Let's start by defining two types to represent the public and private key pair:

type RsaPubKey = { e: bigint, n: bigint };
type RsaPrivKey = { d: bigint; n: bigint; }

Given two very large prime numbers `p` and `q`, we calculate the public and private keys through the function `calcRsaKey()`. It requires the use of our previously implemented `inverse()` function, as shown in the code below:

function calcRsaKey(p: bigint, q: bigint, e=65537n): [RsaPubKey, RsaPrivKey] {
  const n = p * q; // modulus
  const phi = (p - 1n) * (q - 1n); // φ(n)
  const d = inverse(e, phi); // e^-1
  const pubKey = {e, n};
  const privKey = {d, n};
  return [pubKey, privKey];
}

We have also introduced how to randomly generate very large prime numbers before, so we can also randomly generate a RSA key pair, as shown in the code below:

function genRandomRsaKey(bits: number): [RsaPubKey, RsaPrivKey] {
  const p = genRandomPrime(bits);
  const q = genRandomPrime(bits);
  return calcRsaKey(p, q);
}

Next, we will implement the encryption and decryption functions, which are also quite simple, as shown in the code below. However, one thing to note is that directly calculating the power of two very large integers can lead to overflow. Therefore, we need to use the `powerMod()` function instead of the built-in `**` operator in TypeScript. The code for this function is provided at the end of the article.

function rsaEncrypt(m: bigint, pubKey: RsaPubKey): bigint {
  return powerMod(m, pubKey.e, pubKey.n);
}

function rsaDecrypt(c: bigint, privKey: RsaPrivKey): bigint {
  return powerMod(c, privKey.d, privKey.n);
}

That's it! Let's write a test (using the example from the [blog](https://doctrina.org/How-RSA-Works-With-Examples.html#final-example-rsa-from-scratch) I mentioned in the beginning of this article) to prove that our toy RSA implementation indeed works:

function testCalcRsaKey() {
  const p = 12131072439211271897323671531612440428472427633701410925634549312301964373042085619324197365322416866541017057361365214171711713797974299334871062829803541n;
  const q = 12027524255478748885956220793734512128733387803682075433653899983955179850988797899869146900809131611153346817050832096022160146366346391812470987105415233n;
  const e = 65537n;
  const n = p * q;
  const d = 89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713n;
  const m = 1976620216402300889624482718775150n

  const [pubKey, privKey] = calcRsaKey(p, q);
  assert.deepEqual([pubKey, privKey], [{e, n}, {d, n}]);
  assert.equal(m, rsaDecrypt(rsaEncrypt(m, pubKey), privKey));
}

## A Practical Example

In this section, I will analyze a practical example. In fact, Node.js has already provided a `generateKeyPairSync()` method that can be used to generate a pair of random RSA keys. For our convenience in observation, we can obtain the public and private keys in [JWT](https://jwt.io/) format through the `export()` method. The test code is shown below:

import { generateKeyPairSync } from 'crypto';

function testGenRsaKeyPair() {
  const { publicKey, privateKey } = generateKeyPairSync('rsa', {modulusLength: 512});
  console.log('pubKey:', publicKey.export({ format: 'jwk' }));
  console.log('privKey:', privateKey.export({ format: 'jwk' }));
}

I executed the above code and obtained a pair of RSA keys, which looked like this:

pubKey: {
  kty: 'RSA',
  n: '4WjG4XBzOUdjo-4c3HQj9AfeojyYyGtF-ps6P9NQIFyhZxnETDSH10QObqH0yXNDLe46IUZ5xpt_KNZhNu0BnQ',
  e: 'AQAB'
}
privKey: {
  kty: 'RSA',
  n: '4WjG4XBzOUdjo-4c3HQj9AfeojyYyGtF-ps6P9NQIFyhZxnETDSH10QObqH0yXNDLe46IUZ5xpt_KNZhNu0BnQ',
  e: 'AQAB',
  d: 'Wiy6c3GzBtUibXBSp3bm8zc6v5iSXotbwXfcA7Cbu3XSwP-ubvd1kLGqlkH_X3SXNSSU2vbn1uDWtbB2wVQdwQ',
  p: '_MBRcrwHIBtroFUOGKqSuqsxY-a7AkLmecN-zM6CpSU',
  q: '5E59VZ5qLESNi4e7hqY_3YBqciEy9J3ZaCWM42woDRk',
  dp: 'J7oe0zbks9I7h3b3AT-GUprn53jzufZD_a2Rt6VZ-ZU',
  dq: 'RgclPovWuTlVyUSa6pQ35rMq81LnlEyOkPljm6ZjKpE',
  qi: '4uT2nh1B-L0c6FtFR2otTvEcFiI7uFPH8XDYGK7dZMs'
}

Since JWT uses [Base64URL](https://www.rfc-editor.org/rfc/rfc4648#section-5) encoding for field values, we must decode them. Below are all the integers decoded, represented in hexadecimal form:

p: 0xfcc05172bc07201b6ba0550e18aa92baab3163e6bb0242e679c37eccce82a525
q: 0xe44e7d559e6a2c448d8b87bb86a63fdd806a722132f49dd968258ce36c280d19
n: 0xe168c6e17073394763a3ee1cdc7423f407dea23c98c86b45fa9b3a3fd350205ca16719c44c3487d7440e6ea1f4c973432dee3a214679c69b7f28d66136ed019d
e: 0x010001（65537）
d: 0x5a2cba7371b306d5226d7052a776e6f3373abf98925e8b5bc177dc03b09bbb75d2c0ffae6ef77590b1aa9641ff5f7497352494daf6e7d6e0d6b5b076c1541dc1

Let's write a test to verify that these large integers indeed meet the requirements:

function testGeneratedKey() {
  const p = 0xfcc05172bc07201b6ba0550e18aa92baab3163e6bb0242e679c37eccce82a525n;
  const q = 0xe44e7d559e6a2c448d8b87bb86a63fdd806a722132f49dd968258ce36c280d19n;
  const n = 0xe168c6e17073394763a3ee1cdc7423f407dea23c98c86b45fa9b3a3fd350205ca16719c44c3487d7440e6ea1f4c973432dee3a214679c69b7f28d66136ed019dn;
  const e = 0x010001n;
  const d = 0x5a2cba7371b306d5226d7052a776e6f3373abf98925e8b5bc177dc03b09bbb75d2c0ffae6ef77590b1aa9641ff5f7497352494daf6e7d6e0d6b5b076c1541dc1n;
  const phi = (p - 1n) * (q - 1n);
  
  assert.equal(p * q, n);
  assert.equal(e * d % phi, 1n);
}

## Summary

RSA is awesome! In this article, I first introduced all the mathematical prerequisites for understanding RSA. Then, I outlined the fundamental concept of RSA and its working principle. Following that, I used TypeScript to implement a toy version of RSA. To conclude, I generated an actual random RSA key pair via Node.js and dissected all the large integers involved.

Of course, this article only scratches the surface of RSA's principles. We've focused on key generation, encryption, and decryption, leaving digital signatures unexplored. Moreover, the intricacies of RSA in real-world applications far exceed what's covered here. I plan to delve into these complexities in future articles.

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

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`

## Appendix

Here is the complete code for the `powerMod()` function, from [this question](https://stackoverflow.com/questions/75386820/typescript-bigint-exceeds-non-specified-maximum-rangeerror-maximum-bigint-s):

function powerMod(base: bigint, exp: bigint, p: bigint): bigint {
  let result = 1n;
  while (exp !== 0n) {
    if (exp % 2n === 1n) result = result * base % p;
    base = base * base % p;
    exp >>= 1n;
  }
  return result;
}