Alice

Oct 05 2020 at 20:30 GMT

In the **RSA cryptosystem**, the receiver of messages has a *public key*, which is publicly shared, and a *secret key*, which is kept private.

The sender of a message uses the public key to encrypt the message. Then, the receiver is able to decrypt the message using the private key.

Could someone explain how this works in more detail and provide a simple JavaScript implementation?

Tom

Oct 05 2020 at 22:13 GMT

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`

.

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

First, two distinct primes numbers $p$ and $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$ as the product of $p$ and $q$.

```
const n = p * q;
// 42593n
```

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

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

$\phi(n) = (p - 1)(q - 1)$

Let's refer to this value using the `phi`

variable.

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

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

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

`const e = 47n;`

More generally, we can write a `generateEncryptionExponent`

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

```
function generateEncryptionExponent(phi) {
let e = 47n;
while (gcd(e, phi) !== 1n) {
e += 2n;
}
return e;
}
```

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

$ed \equiv 1 \pmod{\phi(n)}$

It can be proven that $d$ is the coefficient of $e$ in the linear combination of $e$ and $\phi(n)$ that expresses the $\gcd(e, \phi(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,

$\gcd(a, b) = sa + tb \ \text{ for some } s,t$

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

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

Here's the `computeDecryptionExponent`

function which computes $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$ and the integer $n$.

`const publicKey = { e, n };`

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

`const secretKey = { d, n };`

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$. It is required that:

$0 \le m < n$

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

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

$c = \text{rem}(m^e, 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;
}
```

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

$m = \text{rem}(c^d, 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.