A Complete Explanation of RSA Asymmetric Encryption

14 min readJan 12, 2023

Check out my email 📩 newsletter for engineers that care about delivery, business impact, and career growth ➡️ http://bit.ly/dev-dispatch

Today we’re going head-first into the weeds of one of the most important and popular asymmetric encryption mechanisms: RSA.

Previously we evaluated the challenges faced in cryptography in the digital age, and how asymmetric encryption can help.

In the past few months we’ve explored a number of topics in Number Theory. Now we can put those to good use as we learn how the RSA asymmetric encryption algorithm works.

Table of Content

Asymmetric Encryption: A History

Mathematical Concepts

2. Modular Arithmetic: A Refresher

3. The Modular Multiplicative Inverse

4. The Euclidean Algorithm

5. Bézout Identity

6. Extended Euclidean Algorithm

7. Carmichael Function

Application

8. The RSA Process

9. Why does that work?

10. Why it’s hard to crack

11. RSA in the wild

Asymmetric Encryption: A History

First, a little history. Before asymmetric encryption, symmetric algorithms were the only option. This required that key be shared across some “secure channel”. This was limiting to say the least, and would be unworkable today. A secure channel might have involved physically swapping portable storage devices containing keys, or trusting a shared local network.

Asymmetric encryption was floated as a solution to these issues, and a proposed approach was offered in 1976. This was the Diffie-Helman algorithm which is still used today. That algorithm is a topic ofr another day.

A year after the Diffie-Helman algorithm, 2 computer scientists & a mathematician avoided a bar and a bad joke, instead developing the RSA algorithm. RSA is one of the most popular methods of public key cryptography to this day. Rivest, Shamir & Adleman, whose initials give the method its name, published their work and launched a new world for cryptography.

Modular Arithmetic: A Refresher

The basis of essentially all modern cryptography is modular arithmetic. A modulus is a mathematical operation, just like addition, multiplication etc. We use this symbol to denote a modulus operation: %.

The modulus operation asks what the remainder is when one integer divides another. For example 12 % 5 asks, when 12 is divided by 5, what is the remainder: 12 % 5 = 2.

14 % 5 = 4
18 % 6 = 0
25 % 4 = 1

The reason that modular arithmetic is so useful for cryptography is that its output behaves like a clock. It’s output is capped by the modulus. Once the input equals that number, the output returns to 0 and then begins increasing again.

0 % 7 = 0
1 % 7 = 1
2 % 7 = 2
....
6 % 7 = 6
7 % 7 = 0
8 % 7 = 1

This makes the output of modulus operations irreversible. Given the output 1, and the modulus 7, the input could have been 1, 8, 15 etc. The output is not distinct.

We use the ≡ symbol, which means “congruent” often with modular notation. We might say for example that 8 ≡ 15 (mod 7). This means that 8 & 15 output the same number when moduloed by 7. “8 is congruent to 15, mod 7”.

The modulus operation can also be worked with algebraically. That means if you do to one side what you do to the other, the outcomes are valid.

Addition

8 ≡ 15 (mod 7)
> now +1 to both sides
9 ≡ 16 (mod 7)
> still valid

Multiplication

21 ≡ 39 (mod 9)
> x5 both sides
105 ≡ 195 (mod 9)
> remains correct

Exponents

18 ≡ 42 (mod 4)
> cube both
5832 ≡ 74088 (mod 4)

For a more detailed exploration of some more nuanced rules of modular arithmetic take a look at the 4 Important Rules of Modular Arithmetic which we wrote about here.

The Modular Multiplicative Inverse

We’ve refreshed our memories on modular arithmetic, so now we can start to apply it to learn how RSA works. The first things we are going to cover is the modular multiplicative inverse, or MMI.

If x % y = z then the MMI of this equation is the integer we need to multiply x by in order for the result to be 1. For example:

93 % 7 = 2
(93 x 4) % 7 = 1
> The MMI of 93 (mod 7) is 4

More generally:

> where
a % n = c

> MMI = m
(a * m) % n = 1

The MMI “inverts” the effect of a with respect to (mod n).

a will only have an MMI if a is coprime to n: they share no common factors larger than 1.

We need to find the MMI as part of the RSA process. MMI is central to creating a pair of complimentary keys for RSA.

We need an algorithm that tells us firstly whether two numbers are coprime, and if so what their MMI is. Thankfully, there is such an algorithm.

The Euclidean Algorithm

We want to know if a & m are coprime. As we saw in our discussion of the Euclidean Algorithm, it can tell us exactly that. The Euclidean Algorithm can find the greatest common divisor (GCD) of any two integers. It works like this:

Define a & b as the two numbers for which we want to find the GCD. Then:

Step 1) If a is 0 then b is the GCD.
Step 2) Else, set a = b % a. and set b = previous a. Repeat these steps until a is 0. b is your GCD.

Here’s an example:

Find the GCD of a = 273, b = 399

a is not 0
a₁ = 126 (399 % 273)
b₁ = 273

a₁ is not 0
a₂ = 21 (273 % 126)
b₂ = 126

a₂ is not 0
a₃ = 0(126 % 21)
b₃ = 21

a₃ is 0
GCD is 21 (value of b₃)

And we can verify that 21 is a divisor of both 462 & 1071:

273 % 21 = 0
399 % 21 = 0

To see why that works you can take a look at this full explanation of the Euclidean Algorithm including a visual & algebraic proof of this process.

That is the Euclidean Algorithm. We can use it to determine what the greatest common divisor of two numbers is, and for our purposes, whether two numbers are coprime.

If we can determine that two numbers are coprime then we know that they have an MMI. Now we need to find out what that value is.

Bézout Identity

Bézout’s identity states that for two integers a & b there are integers x & y such that ax + by = GCD. By rearranging this, we can learn something very useful in our pursuit of MMIs.

ax + by = GCD

> subtract GCD, subtract by
ax - GCD = -by

ax - GCD = (-y)b
> this tells us that ax - GCD is a multiple of b

> so
ax % b = GCD

Remember, if a & b are coprime then GCD = 1.

> where a & b are comprime
ax % b = 1
> looks just like the MMI formula

So given any two coprimes, we know that the Bézout Identity can provide us with the MMI. How do we find the Bézout Identities?

Extended Euclidean Algorithm

The Extended Euclidean algorithm takes us further than just finding the GCD of our integers: it gleans the Bézout Identities too. In a single algorithm we can determine whether two integers are coprime, and if so what their MMI value is.

In a recent post we covered in detail how & why the Extended Euclidean Algorithm works. We don’t have time to cover the ins & outs of it here, so I encourage you to go and discover why it is that this works at all.

Performing the Extended Euclidean Algorithm

Define r₀ & r₁, as the two integers you want to solve for.
Define x₀ & x₁ as 1 & 0 respectively.
Define y₀ & y₁ as 0 & 1 respectively.

And begin…

If aᵢ = 0, stop. The GCD is rᵢ₋₁. The Bézout coefficients are xᵢ₋₁ & yᵢ₋₁. This is the eventual base-case.
Find the new quotient, qᵢ = quotient(rᵢ₋₁ / rᵢ)
Find the next value of r, rᵢ₊₁ = rᵢ₋₁ — (qᵢ * rᵢ).
Find the next value of x, xᵢ₊₁ = xᵢ₋₁ — (qᵢ * xᵢ).
Find the next value of y, yᵢ₊₁ = yᵢ₋₁ — (qᵢ * yᵢ).
Return to Step #1 and repeat.

That’s it. Repeat until we hit aᵢ = 0.

> define our values
r₀ = a = 7
r₁ = b = 93

x₀ = 1
x₁ = 0

y₀ = 0
y₁ = 1

> AND begin!
i = 1
r₁ is not 0
q₁ = 0  (quotient of 7/93)
r₂ = 7  (7 - 0 * 93)
x₂ = 1  (1 - 0 * 0)
y₂ = 0  (0 - 0 * 1)

i = 2
r₂ is not 0
q₂ = 13  (quotient of 93 / 7)
r₃ = 2   (93 - 13 * 7)
x₃ = -13 (0 - 13 * 1)
y₃ = 1   (1 - 13 * 0)

i = 3
r₃ is not 0
q₃ = 3  (quotient 7 / 2)
r₄ = 1  (7 - 3 * 2)
x₄ = 40 (1 - 3 * -13)
y₄ = -3 (0 - 3 * 1)

i = 4
r₄ is not 0
q₄ = 2   (quotient 2 / 1)
r₅ = 0   (2 - 2 * 1)
x₅ = -93 (-13 - 2 * 40)
y₅ = 7   (1 - 2 * -3)

i = 5
r₅ IS 0
x = 40  (x₄)
y = -3  (y₄)
GCD = 1 (r₄)

There we have it. We’ve found the GCD & Bézout Coefficients for our values. GCD = 1 proves they’re coprime.

We can verify our coefficients

> ax + by = GCD
(7 * 40) + (93 * -3)
= 280 - 279
= 1

…and show that x works as our MMI.

7 % 93 = 7
(7 * 40) % 93 = 1

If you wonder why all of this works, you should dive into our discussion on The hows & whys of the [Extended] Euclidean Algorithm.

Returning to Modular Multiplicative Inverses

We set out to find the modular multiplicative of two integers. Using Bézout’s Identity we can now do that. This is a fundamental part of the RSA algorithm.

Next, we need to cover another function common in number theory: Carmichael’s Function.

Carmichael Function

A previous post covered Carmichael’s Function in some depth. If you’d like to know more about it, go take a look.

Carmichael’s Function takes an integer as input. It outputs the smallest number raised to which all of its smaller coprimes, moduloed by the input integer, gives 1. For example:

n = 8

> Carmichael Function of n
> Written 𝝀(n)

> Find all coprimes of 8, between 1 and 8
1, 3, 5, 7

> What number, as exponent of each of these, mod n, gives 1?
> We need to satisfy:
1ᵐ ≡ 1 (mod 8)
3ᵐ ≡ 1 (mod 8)
5ᵐ ≡ 1 (mod 8)
7ᵐ ≡ 1 (mod 8)

> where "a" is the smallest value which satisfies all statements
> for n = 8 the answer -> m = 2
1² % 8 = 1
3² % 8 = 1
5² % 8 = 1
7² % 8 = 1

𝝀(8) = 2

Solving Carmichael’s Function requires differing processes for primes, powers of odd & even primes, and all other numbers. You can learn more about each case in our dedicated post on Carmichael’s Function.

For our purposes here we only need to solve two cases. First are prime numbers. The Carmichael value of any prime, p, is p - 1. eg 𝝀(7) = 6.

The second case is non-prime, non-prime powers. Given an integer with unique prime factor, Carmichael’s Function is found by finding the Lowest Common Multiple (LCM) of the Carmichael’s Function of those factors. For example:

> Find
𝝀(35)

35 = 7 x 5

𝝀(7) = 7 - 1 = 6
𝝀(5) = 5 - 1 = 4

lcm(6, 4) = 12

𝝀(35) = 12

As always, I encourage you to strive to understand why these things work. For more on Carmichael’s Function, check out our discussion here.

The RSA Process

That’s all the theory we need. If you think you’ve got a grasp of everything we covered there, then we can begin to apply it all to the RSA algorithm.

Step 1: Choose some primes

The first step to generate RSA keys is to select 2 primes. In practice these primes will be exceedingly large, at least 100 decimal digits in length. We’ll name these primes p & q.

Step 2: Calculate `n`

n = pq

We multiply the primes together to get a new value, n.

Step 3: Find `𝝀(n)`

Next we find the Carmichael Function value of n.

Remember, to solve Carmichael’s Function for a non-prime number, take the lowest common multiple (LCM) of the Carmichael Function values of its prime factors. n is the product of 2 prime factors, p & q.

𝝀(n) = LCM( 𝝀(p),  𝝀(q) )

p & q are primes, so their Carmichael values are one less than themselves.

𝝀(p) = p - 1
𝝀(q) = q - 1

This allows us to find 𝝀(n).

𝝀(n) = lcm(p — 1, q — 1)

Step 4: Pick `e`

e is another randomly selected prime value. It must be less than & coprime to 𝝀(n).

Step 5: Find `d`

d is the Modular Multiplicative Inverse (MMI) of e (mod 𝝀(n)). We can use the Extended Euclidean Algorithm to find it.

Remember that the MMI, d, is such that:

ed % 𝝀(n) = 1

Step 6: Distribute Public Key

We’ve generated all the values we need. Time to share our public key.

The public key is made up of two parts: the values n & e.

The values d, p, & q are kept secret.

Step 7: Encrypting with the public key

With the public key we can encrypt data. They might want to send some text, perhaps the word hello.

Data must be encoded into an integer. We could use the ascii codes to encode text.

Once we have our integer message, we can encrypt it. We have the e & n values sent in the public key. We raise the message, m to the power of e, then mod n. This gives us our encrypted message, x.

mᵉ % n = x

Step 8: Decrypting with the private key

When we receive a message encrypted with the public key, we’ll want to decrypt it. The private key is formed of the values d, n.

To decrypt x and derive the original message, m, we raise the x to the power d, then mod n.

xᵈ % n = m

We’ve decrypted our message.

An Example

Let’s pick two random primes: p = 73, q = 101. These are trivially small primes for example purposes only. True implementations would use primes that run into hundreds of digits long.

n = pq = 73 * 101 = 7373

𝝀(7373) = lcm(73 — 1, 101 — 1) = lcm(72, 100)

𝝀(7373) = 1800

We choose another prime, e which must be smaller than 1800 & coprime to it.

e = 23

d is the MMI of 23 (mod 1800). We can use the Extended Euclidean Algorithm d.

So our public key comprises e = 23, n = 7373.

Our private key values are d = 1487, n = 7373.

Given some encoded message, m = 19, let’s give it a try. Someone with the public key can encrypt a message.

mᵉ % n = x

19²³ % 7373 = 5609

Our encrypted message is 5609. We can transmit this in the open. Nobody apart from the person with the private key can decrypt it.

With the private key, it can be decrypted like this:

xᵈ % n = m
5609¹⁴⁸⁷ % 7373 = 19

We’ve decrypted our message, deriving the original value, 19.

Why does that work?

Cool. But why on earth did that work?

What are the keys made of?

To understand, let’s remind ourselves how the keys are generated.

n is the product of p & q, two large primes.

𝝀(n) is the Carmichael Function value of n. Any coprime of n raised to the value 𝝀(n), mod n, will return 1.

e is another random prime, coprime to & smaller than 𝝀(n).

d is the MMI of e (mod 𝝀(n)). ed % 𝝀(n) = 1.

Why RSA works

When we take our message integer, to the power of e (mod n), we get a value that is not reversible using any values from the public key. Knowing e & n is not helpful because mod n ensures an outcome which is not distinct to the value of the message. There are many many values which would give the same result.

However, with the values in the private key we are able to return to m, by completing a complementary second process. Raising the encrypted message to exponent d, then mod n, returns the original message.

So we can encapsulate the whole encryption-decryption with the following equation:

(mᵉ % n)ᵈ % n = m

Why is this the case? Using everything we’ve learned, we can show exactly why.

We discussed how we can operate on modulus operations algebraically.

> a truism
mᵉ ≡ mᵉ (mod n)

> this changes nothing
mᵉ ≡ (mᵉ % n) (mod n)

> raise both sides to the power `d`
mᵉᵈ ≡ (mᵉ % n)ᵈ (mod n)

> substitute this into our original RSA equation
(mᵉ % n)ᵈ % n = m
> becomes
mᵉᵈ % n = m

We’ve simplified the RSA equation down to: mᵉᵈ % n = m.

This encapsulates the full RSA process of encrypting & then decrypting the message m.

Remember that d & e were selected because they are MMIs mod 𝝀(n), so ed % 𝝀(n) = 1.

> if
ed % 𝝀(n) = 1

> then
(ed - 1) % 𝝀(n) = 0

ed - 1 is some multiple of 𝝀(n), given that they divide evenly.

> where is `k` is an unknown integer
ed - 1 = k𝝀(n)
ed = 1 + k𝝀(n)

We can substitute this valuation of ed into our RSA equation.

ed = 1 + k𝝀(n)

> for simplicity, let
U = 𝝀(n)
ed = 1 + kU

> substitute into our equation
mᵉᵈ % n = m
m¹⁺ᵏᵁ % n = m

> separate additive powers
m(mᵏᵁ) % n = m

> and multiplicative powers
m(mᵁ)ᵏ % n = m

Because n is the product of 2 primes, n & m are coprime.

We defined U = 𝝀(n). So a coprime of n, raised to the power of its Carmichael Function value, must be 1. That’s the definition of the Carmichael Function. Therefore mᵁ % n = 1.

> picking up where we left off
m(mᵁ)ᵏ % n = m

> if
mᵁ ≡ 1 (mod n)

> then
m(1)ᵏ % n = m

1 raised to k or any power is always 1.

m(1) % n = m

> so
m % n = m

And of course m % n = m is true.

There we go. We encapsulated the whole process of the RSA algorithm into a single equation:

(mᵉ % n)ᵈ % n

Then, by understanding how the keys are derived, and their relationships to one another in the context of the number theory we studied over the course of this lesson, we were able to show exactly why it works.

Why is it hard to crack?

The secret piece is the number d, MMI to e, mod 𝝀(n). That is the missing piece from the public message & the key to decrypting messages.

But d is hard to derive without certain information. Particularly, d can’t be derived without knowing the modulus involved: 𝝀(n).

n is shared publicly, but 𝝀(n) is hard to derive. We were able to do it because we knew the values p & q, n’s prime factors. This enabled us to use the lowest common multiplier method for solving the Carmichael Function for n.

p & q remain secret. Despite n being public, it is very difficult to derive the prime factors of a very large number. In practice, RSA uses extremely large numbers.

Without p & q, 𝝀(n) can’t be found. Without 𝝀(n), the MMI d can’t be found. Without d we can’t decrypt messages encrypted using e.

That is why, by mathematical methods known at the time of writing, and using all computing power currently available, cracking modern implementations of RSA asymmetric encryption would take many thousands of years.

RSA in the wild

RSA is the original & most popular asymmetric encryption scheme. It is used everywhere. Encryption on the web depends upon it. The TLS standard which HTTPs depends upon uses RSA. It really is everywhere.

To find out more about the maths on which RSA relies, take a look at some of these articles we put together to explain the basics of all of the concepts included in this discussion.

Happy learning :)

More ?

I write the world’s shortest newsletter. One quick thing I’ve learned or seen or read in the week, each Wednesday.

I want it to be the most accessible, to-the-point newsletter you receive.

It might be worth giving a try. Unsubscribing is easy too.

It’s called <One More Thing>. See you there!