A simple implementation of the RSA algorithm in JavaScript

Let's go through the three phases of RSA: key generation, encryption, and decryption.

I will also show a JavaScript implementation of each step.

Note: since we will be working with very large numbers, we will be using the new JavaScript BigInt type instead of the simple number type. This means that all integers will be written with an n suffix, e.g., 191n.

Key generation

Let's first see how the receiver creates a public key and a secret key.

First, two distinct primes numbers $p$p and $q$q are chosen. These are generally very large, but for the purposes of this explanation, let's keep them small.

const p = 191n;
const q = 223n;

Then, we compute the integer $n$n as the product of $p$p and $q$q.

const n = p * q;
// 42593n

Next, we compute the value of the Euler's totient function for $n$n, denoted as $\phi(n)$ϕ(n), which represents the number of integers that are relatively prime to $n$n in the range 1 to $n$n.

Since $n$n is equal to the product of two distinct primes, it can be proven that:

Let's refer to this value using the phi variable.

const phi = (p - 1n) * (q - 1n);
// 42180n

Next, we choose the encryption exponent $e$e, such that $1 < e < \phi(n)$1<e<ϕ(n) and $e$e is relatively prime to $\phi(n)$ϕ(n), i.e., the $\gcd(e, \phi(n)) = 1$gcd(e,ϕ(n))=1.

We can pick a prime number for $e$e and then check that it does not divide $\phi(n)$ϕ(n). The number 47 is prime and does not divide 42180, so let's go with $e=47$e=47.

const e = 47n;

More generally, we can write a generateEncryptionExponent function that generates $e$e by starting with 47 and checking if it is relatively prime to $\phi(n)$ϕ(n) and incrementing it by 2 if it is not relatively prime until we get a number that is relatively prime to $\phi(n)$ϕ(n):

function generateEncryptionExponent(phi) {
  let e = 47n;

  while (gcd(e, phi) !== 1n) {
    e += 2n;
  }

  return e;
}

Now, let's compute the decryption exponent $d$d, which is the multiplicative inverse of $e$e modulo $\phi(n)$ϕ(n). That is,

It can be proven that $d$d is the coefficient of $e$e in the linear combination of $e$e and $\phi(n)$ϕ(n) that expresses the $\gcd(e, \phi(n))$gcd(e,ϕ(n)), which we can compute using the Extended Euclidean Algorithm.

So, let's assume that we have an extendedGcd function that implements the Extended Euclidean Algorithm.

This function takes two integers a and b for which we want to compute the GCD, and it returns an object that has the value of the GCD as well as the coefficients s and t in the linear combination of a and b that is equal to the GCD. That is,

So, if we compute the GCD of $e$e and $\phi(n)$ϕ(n), $d$d will correspond to the coefficient of $e$e, which will be the first one, i.e., $s$s.

Furthermore, we want the decryption exponent $d$d to be positive. So, if we get a negative value for $d$d, we can make it positive by adding $\phi(n)$ϕ(n) to it as many times as needed to make it positive.

Here's the computeDecryptionExponent function which computes $d$d:

function computeDecryptionExponent(e, phi) {
  let d = extendedGcd(e, phi).s;

  while (d < 1n) {
    d += phi;
  }

  return d;
}

The public key will be a pair that consists of the encryption exponent $e$e and the integer $n$n.

const publicKey = { e, n };

The secret key will be a pair that consists of the decryption exponent $d$d and the integer $n$n.

const secretKey = { d, n };

Encryption

When the sender wants to encrypt a message, the message first needs to be converted to an integer.

Let's say that the resulting message expressed as an integer is $m$m. It is required that:

The sender should also check that $\gcd(m, n) = 1$gcd(m,n)=1, since we don't want the GCD to equal $p$p or $q$q, which in practice almost never happens.

Next, the message $m$m is encrypted into the ciphertext $c$c using the public key by computing the remainder of $m^e$me divided by $n$n.

Here's the encrypt function that does the encryption:

function encrypt(m, publicKey) {
  const { e, n } = publicKey;

  if (m < 0n || m >= n) {
    throw new Error(`Condition 0 <= m < n not met. m = ${m}`);
  }

  if (gcd(m, n) !== 1n) {
    throw new Error("Condition gcd(m, n) = 1 not met.");
  }

  const c = m ** e % n;

  return c;
}

Decryption

The receiver can decrypt the ciphertext $c$c back to the original message $m$m using the secret key by computing the remainder of $c^d$cd divided by $n$n.

Here's the decrypt function that does the decryption:

function decrypt(c, secretKey) {
  const { d, n } = secretKey;

  const m = c ** d % n;

  return m;
}

Finally, here's the rsaExample function that puts all of this together:

function rsaExample() {
  const p = 191n;
  const q = 223n;

  const n = p * q;
  const phi = (p - 1n) * (q - 1n);

  const e = generateEncryptionExponent(phi);
  const d = computeDecryptionExponent(e, phi);

  const publicKey = { e, n };
  const secretKey = { d, n };

  const m = textToNumber("Hi");
  const c = encrypt(m, publicKey);
  const m2 = decrypt(c, secretKey);

  console.log(numberToText(m2));
  // Hi
}

Note that this is just a simple JavaScript implementation of the RSA algorithm shown for learning purposes.

If we try it with big prime numbers and long messages, we will end up with extremely large numbers that cannot even fit inside the JavaScript BigInt, and so we will get the RangeError: Maximum BigInt size exceeded error.