Understanding RSA (Draft)

RSA is one of the first public-key encryption algorithms ever used. For this reason, it serves well as a pedagogical example for readers curious about cryptography.

In this post, I’ll explore the mathematical foundations of the system, with a focus on number theory.

Although this article leans toward the mathematical side, it’s written to invite coders and curious readers to engage with the concepts.

A basic understanding of arithmetic and modular arithmetic will be helpful. I'll link to external resources where appropriate, rather than covering every concept in depth.

For a more technical and programmer-oriented point of view, there are other resources out there. Here I've linked some basic implementations in JavaScript.

In mathematics, it's often useful to begin with simple cases to build intuition. For example, prime numbers can be understood at varying levels of complexity.

I’ll start with the most familiar definition, using basic examples to illustrate key ideas.

Another valuable habit is to revisit concepts multiple times. The more deeply you internalize them, the more naturally you’ll be able to apply them later on.

Let’s begin by understanding the system.

RSA relies on a pair of keys: one public, which can be shared openly, and one private, which must be kept secret by its owner.

The standard example involves Bob and Alice exchanging messages.
Since they want to encrypt their communication using RSA, each of them has such a key pair.

Confident in the system, Alice wants to send a message to Bob. She uses Bob’s public key to encrypt the message.

At this point, Bob (and Bob only) can decrypt the message using his private key.

The security of this system relies on the fact that Bob's private key is known only to him.

Using this private key, Bob can decrypt messages that were encrypted with his corresponding public key through a fascinating mathematical process based on modular arithmetic.

Key Generation

Generating such public/private key pairs involves fundamental number theory concepts, particularly prime numbers.
You may recall that a prime number is a positive integer greater than 1, divisible only by 1 and itself.

Prime numbers are the atoms of the integers. Every positive integer can be constructed as a product of primes (factorization).

This is formalized in a famous result known as the Fundamental Theorem of Arithmetic, or Unique Factorization Theorem (UFT).

Another example of prime factorization:

Now let’s return to RSA and the key generation process.
Bob can generate a pair of keys using the following steps:

Some of these steps rely on concepts we haven’t yet defined.
Let’s walk through them one by one.

Step 1: Choose two primes

Bob first chooses two distinct prime numbers: $p$ and $q$.

These primes should be large enough (at least 20 digits) to ensure the system’s security.
It is notoriously difficult to factor the product of two large primes and this is the basis of RSA’s strength.

Step 2: Compute $n = p \times q$

This is straightforward.

Step 3: Compute $\phi(n) = (p − 1)(q − 1)$

Here we introduce $\phi(n)$, the Euler's totient function.

But what does “coprime” mean?

Two positive integers are coprime if they have no common prime factors other than 1.

In particular, if $n$ is a prime number, then $\phi(n) = n - 1$. Why?

It also follows that when $p$ and $q$ are coprime (distinct primes are coprime) $\phi(n) = (p − 1)(q − 1)$.

Note: computing $\phi(n)$ from just $n$ would require factoring $n$, which is copmputationlly hard (recall step 1) if you don't know $p$ and $q$.

Step 4: Choose $e$ such that $1 < e < \phi(n)$ where $e$ is coprime to $\phi(n)$ ($gcd(e, \phi(n)) = 1$)

Now Bob must choose an exponent $e$.

It should satisfy:

• $1 < e < \phi(n)$
• $e$ is coprime to $\phi(n)$ or, algorithmically, $gcd(e, \phi(n)) = 1$

A common choice is $e = 2^{16} + 1$ (65,537); large enough for security, small enough for efficiency.

To check whether $e$ and $\phi(n)$ are coprime, Bob can use the greatest common divisor (gcd).

To compute the gcd, Bob can use the Euclidean algorithm, one of the oldest known algorithms (from Elements, c. 300 BC). The algorithm is based on the following principle:

It's extremely easy top write the algorithm in javascript:

1. Let $a$ and $b$ be two positive integers (swap if $b > a$)
2. If $b = 0$, then $\gcd(a, b) = a$
3. Otherwise, replace $a$ with $b$, and $b$ with $r$
4. Repeat until $b = 0$

$r$ is the reminder computed using javascript remainder operator %. The last non-zero remainder is the gcd.

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

Notice the nice recursion! Now, Bob can algorithmically determine whether two integers are coprime:

Step 5: Find $d$ such that $e \times d \equiv 1 \pmod{\phi(n)}$

The equation $e \times d = 1 \mod \phi(n)$ must be read as $e \times d$ is congruent $1$ modulo $\phi(n)$.

We now delve into modular arithmetic, starting with its foundation: modular congruence.

Nothe: $b$ is the remainder when dividing $a$ by $m$.

JavaScript doesn’t have a true mod operator, only a remainder operator %, which behaves slightly differently for negative numbers.
(See this StackOverflow post).

There is anyway a proposal.

Now, the equation

can be rewritten as:

That is: $d$ is the modular inverse of $e$ modulo $\phi(n)$.

Such a modular inverse exists only if $e$ and $\phi(n)$ are coprime (and by step 4 they are).

To compute $d$, Bob can use the Extended Euclidean Algorithm, a standard method for finding modular inverses.

• Here’s a nice explanation
• Or see this one on Brilliant

For theoretical reasons, I'll introduce a more elegant method based on Euler's Theorem, which provides deeper insight into why RSA encryption\decription works so smootlhy.

Since Bob knows $\phi(n)$, he can use Euler's Theorem to compute $e^{-1}$:

This implies:

So Bob can compute:

to obtain the modular inverse.

$e^{\phi(n) - 1}$ is calculated through the fast exponentiation algorithm (also known as exponentiation by squaring or binary exponentiation)

Encryption/Decritpion

Encryption

Now Bob have already shared his public-key $(e,n)$ to Alice.

Alice will be able to send a message to Bob in the following way:

• She converts the message into a series of chuncks, each of wich is represented by an integer $m$ ranging from $1$ to $n$
• To encrypt each chunk $c$, she compute $$c = m^{e} \pmod n$$

Decritpion

Bob can decrypt each received chunk using the formula:

Remember that $d$ is the modular inverse ($e^{-1}$) of $e$. Thus $de \equiv 1 \pmod{\phi(n)}$, and the equation becomes:

By definition of modular congruence, $1 \pmod {\phi(n)}$ can be written as $1 + k \times \phi(n)$ for some $k$:

Using the power properties:

We introduced Euler's Theorem for a reason. In fact, in number theory it's used every time when dealing with powers as it simplifies the problem significantly. Euler tells us that $m^{\phi(n)} = 1 \pmod n$, thus:

Thus for Bob, recovering the message for each chunk $c$ will simply evaluate to:

Exercise: Rewrite the encryption and decryption process by yourself, focusing only on one chunk as explained.

Conclusion

I hope to have explained the theoretical part of RSA for generating keys and encryption/decryption. For users encountering this concept for the first time, it will certainly be overwhelming and that's normal. Hopefully, you can come back to this while learning the basic concepts.