How RSA cryptosystem works?

2023-07-23

21 minute read

Cryptography

cryptography

Introduction

The RSA (Rivest-Shamir-Adleman) is one of the oldest public-key cryptosystems that is widely used for secure data transmission. Its name comes from the last names of three cryptographers that invented it. It’s the best cryptosystem to learn about the assymetric cryptography.

RSA is heavily based on number theory, but bear with me. I will try to explain everything with examples, so hopefully by the end of this article you’ll have a good understanding of how RSA works.

Before we talk about RSA, we will first cover basic theorems from the number theory that the RSA cryptosystem is based on. In this blog post, we will talk about:

What problem RSA solves?
What is Euler’s totient function?
What’s Euler’s Theorem?
What’s the idea in the RSA cryptosystem?
Why is Euler’s Theorem important for RSA?
How to find exponents?
Why RSA needs two prime numbers?
How hard is factorization of a number, and what this means for RSA?
How to find two large prime numbers?
What’s the time complexity of various operations?

Let’s get started.

What problem RSA solves?

RSA (or any cryptosystem) tries to provide a secure way for two people to communicate over insecure channel. In its most basic form, two people, usually Alice and Bob, want to send secret messages to each other. However, a villain called Oscar tries to intercept and read their messages.

We usually talk about three types of cryptosystems.

Secret-key cryptosystem

We refer to the secret-key cryptosystem as symmetric cryptography because Alice and Bob use the same secret key to encrypt and decrypt messages.

Symmetric cryptography is usually fast, but the disadvantage is that the secret key must be exchanged over a secure channel ahead of time, e.g. by meeting in person.

Public-key cryptosystem

We refer to the public-key cryptosystem as assymetric cryptography because Alice and Bob use different keys to encrypt and decrypt messages. The key used for encrypting messages is public, which means everyone has access to it. On the other hand, the key used for decrypting messages is private.

For example, both Alice and Bob have a different pair of public and private keys. Alice can encrypt messages using Bob’s public-key that only Bob can decrypt using his private-key.

The advantage of assymetric cryptography is that Alice and Bob don’t have to exchange anything ahead of time, which is very useful if they live far from each other. The downside is that assymetric cryptography is usually very slow.

RSA is an assymetric cryptosystem.

Hybrid cryptosystem

Hybrid cryptosystem uses both symmetric and assymetric cryptosystems to get the best of both worlds. The idea is to use the assymetric cryptosystem to exchange the secret-key, then use the symmetric cryptosystem to exchange messages. As a result, the hybrid cryptosystem allows Alice and Bob to securely exchange the secret key even though they haven’t met in person, while still getting the speed benefits from using the symmetric cryptography.

Euler totient’s function

The fundamental idea in the RSA cryptosystem comes from Euler’s totient function and Euler’s theorem. So, before we dive deep into how RSA works, let’s explain these concepts.

Just in case you don’t remember, let’s start with prime numbers. A number is called prime if it can only be divided by itself and 1. For example, 7 is a prime number because it can only be divided by 1 and 7 without remainder.

Also, we say that two numbers $a$ and $b$ are relatively prime (or coprime) if their greatest common divisor is 1 (we write $GCD(a, b) = 1$). For example, 3 and 8 are relatively prime because $GCD(3, 8) = 1$. On the other hand, 3 and 9 are not relatively prime because $GCD(3, 9) = 3$.

With that out of the way, let’s define the Euler’s totient function. The Euler’s totient function for a number $n$ counts how many positive integer numbers, up to the number $n$, are relatively prime to $n$. This function is written using the Greek letter $\varphi$.

Let’s see an example for number 9:

1, 2, 4, 5, 7, and 8 are relatively prime to 9 because GCD for each of these numbers and 9 is 1.
3, 6, and 9 are not relatively prime to 9 because GCD of each of these numbers and 9 is 3.

Therefore, $\varphi(9) = 6$.

Also, note that $\varphi(1) = 1$ because 1 is relatively prime with any integer number.

What if $n$ is a prime number? Say that $n=71$. Any positive number smaller than $n$ is relatively prime to $n$, so for any prime number $n: \varphi(n) = n - 1$.

Euler’s theorem

Okay, now that we know what Euler’s totient function is, what can we do with it? This is where Euler’s theorem comes in.

Euler’s theorem says that if $n$ and $a$ are relatively prime positive integers, and $\varphi(n)$ is Euler’s totient function, then

$$ a^{\varphi(n)} \equiv 1 \mod{n} $$

Let’s see an example. We already know that the $\varphi(9) = 6$. If we pick a number that is relatively prime to $n$, for example 5, then the theorem says that:

$$ 5^6 \equiv 1 \mod{9} $$

To verify this, you can raise 5 to the power of 6:

$$ 5^6=15625 $$

Dividing 15625 by 9 gives us 1736 and a remainder of 1.

We are not going to prove this theorem since our focus is on the RSA cryptosystem, but this is the fundamental idea that we will use to construct a public-key cryptosystem.

The idea in RSA cryptosystem

Let’s see how to do that. We would like to have an encryption function that encrypts a number $x$ by raising it to the power of $a$ and then taking the result modulo $n$:

$$ e(x) = x^a \bmod{n} $$

Let’s say that we want to encrypt a number 11, and we chose numbers $a = 3$ and $n = 200$. The encryption function produces a number 131:

$$ e(11) = 11^3 \bmod{200} = 1331 \bmod{200} = 131 $$

We would use the same encryption function for any number $x$. This doesn’t justify the need for Euler’s theorem yet, but we’ll get there soon.

So, how can we decrypt the result? How can we get a number 11 given 131? We need to reverse the process somehow. The idea for this trick comes from the number theory where, in some cases, it is possible to raise the encrypted result to the power of some number $b$ modulo $n$ to get back the original number.

For example, we could raise the number 131 to the power of 27, which gives us the following (very big) number:

$$ 131^{27} \bmod{200} = 1466644921315630774981772539386673512245551625996966660411 \bmod{200} = 11 $$

With this idea in mind, the decryption function could potentially be as simple as:

$$ d(y) = y^b \bmod{n} $$

Relationship between Exponents and Euler’s Theorem

I think this is amazing, but can we choose such number $b$ that can reverse the process for any number $x$?

For this to work in all cases, we need to show that decrypting the encrypted value of $x$ gives us back $x$:

$$ d(e(x)) = (x^a)^b \bmod{n} = x^{ab} \bmod{n} = x \bmod{n} $$

We will refer to this equation as encryption-decryption equation. The key part of the equaition that we will focus on is:

$$ x^{ab} \equiv x \mod{n} $$

This is where the rest of the Euler’s Theorem comes into play.

We know that $x^{\varphi(n)} \equiv 1 \mod{n}$ when $GCD(x, n) = 1$. We can multiply each side with $x^{\varphi(n)}$:

$$ x^{\varphi(n)} x^{\varphi(n)} \equiv x^{\varphi(n)} \mod{n} $$

which shows that $x^{2 \varphi(n)} \equiv 1 \mod{n}$. We can repeat this process multiple times, which shows that $x^{k \varphi(n)} \equiv 1 \mod{n}$ for any positive integer $k$.

Why is this relevant? Well, this equation kind of looks like the encryption-decryption equation. We have $x$ as the base and a multiplication of two numbers as an exponent in both equations. The only difference is that the encryption-decryption equation expects $x$ on the right-hand side.

Let’s multiply both sides with $x$ to get a similar-looking equation:

$$ x^{k \varphi(n) + 1} \equiv x \mod{n} $$

The new equation says that if we can find $a$ and $b$ such that $ab=k \cdot \varphi(n) + 1$, then we’d be able to decrypt the message.

Let’s substitute $ab$ with $k \cdot \varphi(n) + 1$ in the encryption-decryption equation to show one more time that it results in $x \bmod n$:

$$ d(e(x)) = x^{ab} \bmod{n} = x^{k \cdot \varphi(n) + 1} \bmod{n} = x^{k \cdot \varphi(n)} \cdot x \bmod{n} = x \bmod{n} $$

Okay, this was probably a lot of math, but I hope that you can at least get a sense for why RSA works this way.

First recap

We’ve covered a lot, so this is probably a good moment to take a break and recap what we’ve learned so far:

The Euler’s totient function for a number $n$ counts how many positive integer numbers, up to the number $n$, are relatively prime to $n$.
The Euler’s Theorem says that $a^{\varphi(n)} \equiv 1 \mod{n}$ when $GCD(a, n) = 1$.
Encryption function in RSA is $e(x) = x^a \bmod{n}$.
Decryption function in RSA is $d(y) = y^b \bmod{n}$.
Decrypting the encrypted value is the same as raising $x$ to the power of $ab$ modulo $n$: $d(e(x)) = x^{ab} \bmod{n}$.
If the equation $ab = k \varphi(n) + 1$ is satisfied, then we can reverse the encryption process.

Let’s continue.

How to calculate exponents

Let’s go back to our example where $n=200$ and $a=3$. Before we can compute $b$, we need to know the value of $\varphi(200)$. We can write a simple program that iterates over all integers from 1 to 200 and count how many are relative prime to 200, and we get:

$$ \varphi(200) = 80 $$

Next step is to find an integer (positive or negative) $k$ that satisfies the equation $ab=k \varphi(n) + 1$. We know the values for $a$ and $\varphi(n)$, so we need to find a solution for

$$ 3b = 80k + 1 \Leftrightarrow 3b - 80k = 1 $$

One way to find the answer is to iterate over each integer $k$ until we find a solution to the above equation:

For $k=0$ we get $3b=1 \implies b$ can’t be an integer.
For $k=1$ we get $3b - 80 = 1 \implies b = 27$.

This works for our example and we have found the number 27 that we can use in the decryption function. We have already seen that 27 is the solution for our example, and now we know how we got to that number.

In practice, it won’t be feasible to iterate over each integer $k$ to find a solution. Fortunately, we can use the extended euclidean algorithm to efficiently find the solution for equations of the form $tx + zy = GCD(t,z)$.

In our example, we would use $t=a=3$ and $z=\varphi(n)=80$:

$$ a \cdot x + \varphi(n) \cdot y = GCD(a, \varphi(n)) $$ $$ 3x + 80y = 1 $$

We can now use the extended euclidean algorithm to get $x=27$ and $y=-1$. The value $x$ is our exponent $b$.

We will cover the extended euclidean algorithm in another blog post.

Notice that this adds additional constraint to the number $a$, i.e. $GCD(a, \varphi(n)) = 1$. If this wasn’t the case, the above equation wouldn’t have integer solutions.

Also, since we can reverse the process, as long as we find number $b$ that satisfies the above equation, then the encryption function must produce different ciphertexts for different inputs:

$$ m_1 \neq m_2 \implies e(m_1) \neq e(m_2) $$

Why do we need two prime numbers?

This all looks great so far, but can we actually use this in practice? In a public-key cryptosystem, everyone must be able to encrypt a function which means that everyone must know numbers $a$ and $n$. Since $b$ is used in the decryption function only, we can keep it private:

Public-key are numbers $(a, n)$;
Private-key is number $b$.

However, if everyone knows $n$, can’t they use the same approach to find the number $b$? Of course they can. This is why we have to make it infesiable for everyone to calculate $b$ even though $n$ and $a$ are public, while doing something clever to make it easy for us to do so. How can we do that?

The core problem is that if someone knows $\varphi(n)$ then they can compute the private-key, as we’ve shown above. Therefore, we need to make it infesiable for anyone to compute $\varphi(n)$ given the public-key.

Fortunately, there’s another trick that we can use. We know that $\varphi(p) = p - 1$ when $p$ is a prime number. A nice property of the Euler totient’s function is that it is multiplicative, which means $\varphi(xy) = \varphi(x) \varphi(y)$.

For example, we can calculate Euler’s totient function for e.g. 40000 as follows:

$$ \varphi(40000) = \varphi(200) \cdot \varphi(200) = 80 \cdot 80 = 6400 $$

For two prime numbers $p$ and $q$, we can calculate: $\varphi(pq) = (p - 1) (q - 1)$.

If we choose $n = p \cdot q$, then it’s easy for us to calculate Euler’s totient function for $n$: it’s just the product of Euler’s totient functons of its prime factors. We will keep $p$ and $q$ private so that everyone else would have to go through a more complex process to calculate $\varphi(n)$.

How hard is it to factorize $n$ into $p$ and $q$?

Given only the public-key, the best way to find Euler’s totient function is to factorize number $n$ and then use a formula to calculate $\varphi(n)$. The most efficient classical algorithm know for factoring large numbers is called general number field sieve (GNFS).

If anyone can find factors $p$ and $q$, then they would break the RSA cryptosystem. Clearly, we can’t just pick any two prime numbers. So, how can we choose the right ones?

If we choose very large prime numbers that are hundreds of digits long, then it would be very hard for anyone to compute them if they know their product $n=p \cdot q$. Fortunately, there is no known way to calculate $\varphi(n)$ with today’s algorithms in a practical amount of time - you should try it yourself. This may change in the future when quantum computers become a thing.

Today, factoring algorithms are able to factor RSA modulo having up to 1024 bits in their binary representation. It is currently recommended that, to be on the safe side, one should choose both $p$ and $q$ to be at least 1024-bit primes, meaning the modulus will be at least 2048 bits long. Factoring a number of this size is well beyond the capability of the best factoring algorithms today.

Notice that $p$ and $q$ should be different and far apart. If they are the same, then the attacker can calculate them using square root, which is easy to compute even for very large numbers:

$$ p = q = \sqrt{n} $$

On the other hand, if $p$ and $q$ are close to each other, the attacker could try dividing $n$ with prime numbers starting at $\sqrt{n}$ and going down, until they find the one that divides $n$.

An interesting example is an article from the Scientific American that stated it would take a million years to break a new kind of cipher (RSA, which uses a product of two large prime numbers to generate secret and public keys). The article presented a challenge which was solved 17 years later (in April 1994). The statement referred to how long it would take to run the best factoring algorithm in 1977 on the fastest computer at that time. However, the computers got faster and better factoring algorithms were found in the meantime.

Second recap

Now is a good time to recap what we’ve learned about RSA:

Encryption function is $e(x) = x^a \bmod{n}$.
Decryption function is $d(y) = y^b \bmod{n}$.
Modulo $n$ is chosen as a product of two very large prime numbers $p$ and $q$ that are far from each other: $n = p \cdot q$.
Exponent $a$ is chosen at random such that $GCD(a, \varphi(n)) = 1$ and $1 < a < \varphi(n)$.
Exponent $b$ is computed using the Extended Euclidean algorithm given the $a$ and $n$.
Public-key $(a, n)$ is shared with everyone, and it’s used to encrypt any plaintext.
Private-key $b$ is kept as a secret, and it’s used to decrypt any ciphertext.
Today, the most efficient factoring algorithms still can’t find prime factors of $n$ in a practical amount of time.

There are a couple of things that are not obvious:

How to find two very large prime numbers?
Can we efficiently implement encryption and decryption functions when dealing with large numbers?

How to find two large prime numbers?

We can choose a large number at random, then check if it’s prime. If it’s a prime, we keep it. Otherwise, pick another large number at random until we it’s prime. We can repeat the process to find the second number such that both prime numbers are large and far from each other.

Primality test

That sounds easy, but how do we check if a given number is prime?

There are many algorithms that test if a number is prime or not. The most commonly used one is called Miller-Rabin primality test. This is a probabilistic algorithm which determines whether a given number is likely to be prime. The longer the algorithm runs, the higher probability that the answer is correct. I will cover the Miller-Rabin primality test in another blog post.

Convergence

Ok, we know how to test whether a number is prime or not, but how long would it take to choose one at random?

As per the Prime Number Theorem, the probability that a random number not greater than $N$ is prime is very close to $\frac{1}{log(N)}$. This means that for a random number that is 1024 bits long, the chance of it being prime is around 1 every 1000. Therefore, it would take 1000 attempts on average to guess a prime number.

Can we efficiently implement encryption and decryption functions?

Assuming we have a public and prive keys, how long would it take to run encryption and decryption functions? We can use elementary school arithmetics to find the upper bound on the amount of time to perform various operations of two numbers. Let’s say that we have two numbers $x$ and $y$ with $k$ and $l$ bits respectively. We can assume that $k >= l$ without loss of generality.

Basic arithmetics:

$x + y$ can be computed in $O(k)$.
$x - y$ has the same time complexity as addition.
$x * y$ can be computed in $O(k * l)$.
$frac{x}{}y$ has the same time complexity as multiplication.
$GCD(x, y)$ can be computed in $O(gcd–iterations \cdot num–divisions) = O(k^3)$ because the GCD algorithm performs a division in each iteration, which is $O(k^2)$ and it runs in $O(log_2{x}) = O(k)$. In fact, it can be shown that the complexity is actually $O(k^2)$ since the numbers in the GCD algorithm have fewer bits in later iterations.

Modulo arithmetics (assuming $n$ has $k$ bits):

$(x + y) \bmod n$ can be computed in $O(k)$.
$(x - y) \bmod n$ has the same time complexity as modular addition.
$(x \cdot y) \bmod n$ can be computed in $O(k^2)$.
Modular inverse $x^{-1}$ can be computed in $O(k^3)$.
$x^e \bmod n$ can be computed in $O(log e) \cdot k^2)$.

Most of these are easy to prove. The first three can be done by doing an integer operation and then performing a single reduction modulo n.

The multiplicative inverse algorithm remains the same, but it needs to account for arithmetic operations of large numbers.

Finally, computing modular exponent $x^e \bmod n$ which both encryption and decryption operations need can be done using $e-1$ modular multiplications. However, this would be very slow if $e$ is large, which it almost certainly will be (hundreds of digits). We can use square and multiply algorithms where we can achieve this in $O(log(e))$ iterations. The idea is that for an even number $e$ we can reduce the problem to computing the power of $\frac{e}{2}$ then computing the square of that number: $x^e = (x^{e/2})^2$. When $e$ is an odd number, we can reduce the problem to the previous one with a single multiplication: $x^e = x \cdot x^{e-1}$.

This means that we can compute the encryption and decryption functions in $~O(k^3)$. In practice, there are other tricks that improve the performance of these functions using Chinese Remainder Theorem, but this is out of scope for this blog post.

Example: Step by Step

Let’s go through an example. We will write python code to generate private and public keys, then assert that we can encrypt and decrypt the value.

Our first step is to generate public and private key. To do that, we need a way to generate a random number of a given length, and a function that tests if the number is prime. I’m going to use a library to do that:

import secrets
import miller_rabin


def is_probably_prime(x, rounds=40):
    return miller_rabin.miller_rabin(x, rounds)


def generate_random_number(bits):
    return secrets.randbits(bits)

Next, let’s create a function to generate a large prime:

def generate_large_prime(bits=1024, attempts=10000):
    for _ in range(attempts):
        candidate = generate_random_number(bits)
        if is_probably_prime(candidate):
            return candidate

    raise f"Failed to generate probably prime number of length {bits} in {attempts} attempts."

We are now ready to generate two large prime numbers $p$ and $q$. We want these two numbers to be far apart as well.

def generate_prime_factors(factor_bits=1024, min_factor_delta_bits=256, attempts=10000):
    while True:
        p = generate_large_prime(factor_bits, attempts)
        q = generate_large_prime(factor_bits, attempts)
        if abs(p - q).bit_length() >= min_factor_delta_bits:
            return p, q
    raise f"Failed to generate two prime factors in {attempts} attempts."

Now we can generate $p$ and $q$ by calling generate_prime_factors. Since I can’t fit a 2048-bit number on the screen, I’m going to use fewer bits.

p, q = generate_prime_factors(factor_bits=128, min_factor_delta_bits=32)
n = p * q

If we print these numbers, we get:

p =  300402231603268109600817921956024624563
q =  32279404710915459154939683395845971491
n =  9696805209984049441526961126202724725630856942567849211871620019459276333433

Next step is to generate a public exponent. We will keep generating a random number $a$ until $1 < a < \varphi(n)$ and $GCD(a, \varphi(n))=1$. I’m using egcd library that implements the Extended Euclidean Algorithm.

def generate_public_exponent(p, q, attempts=1000):
    euler_totient = (p - 1) * (q - 1)

    # Choose a random number [a] such that GCD(a, phi(n)) = 1 and 1 < a < phi(n).
    # Additionally, let's make sure that [a] is at least [min_bits_for_exponent] long.
    for _ in range(attempts):
        a = generate_random_number(euler_totient.bit_length())

        if a <= 1 or a >= euler_totient:
            continue

        # We only need GCD, but we can also run Extended GCD since that library is already available.
        gcd, _, _ = egcd.egcd(a, euler_totient)
        if gcd == 1:
            return a

    raise f"Failed to generate public exponent for p={p} and q={q}. Attempted {attempts} times."

Now that we have the public exponent, we can use the Extended Euclidean Algorithm to compute the private exponent. Before we can do that, we need to calculate $phi(n)$, and fortunately for us that’s easy.

def compute_private_exponent(a, p, q):
    phi = (p - 1) * (q - 1)
    # The Extended Euclidean Algorithm solves: tx + zy = GCD(t, z)
    # In our case: t=a and z=phi.
    # The solution for [x] is the private exponent.
    gcd, b, _ = egcd.egcd(a, phi)
    assert(abs(gcd) == 1)

    # EEA may return a negative number, but we need a remainder, so we convert it to the positive number.
    if b < 0:
        return b + phi
    return b

Let’s run these two functions to generate public and private exponents.

a = generate_public_exponent(p, q)
b = compute_private_exponent(a, p, q)

If we print all the numbers we have so far, we get:

p =  110048843095422197087071757611329503833
q =  113176829162524124401163314225963653241
n =  12454979114544020547972318036531202282281996899056077916592845019112592372753
a =  9555536198971257872315549745690616564802756410986833210548959912717075484843
b =  1304212785790701980999567760768489760055206957755884280677310226964974661827

Public Key:
  n=12454979114544020547972318036531202282281996899056077916592845019112592372753
  a=9555536198971257872315549745690616564802756410986833210548959912717075484843

Private Key: 
  p=110048843095422197087071757611329503833
  q=113176829162524124401163314225963653241
  b=1304212785790701980999567760768489760055206957755884280677310226964974661827

All that’s left is to test if this can really encrypt an arbitrary number, then decrypt it. Before we can implement encryption and decryption functions, we need a function to calculate modular exponent. We can implement this recursively using the square and multiply algorithm:

def modular_exponent(x, a, n):
    if a == 0:
        return 1
    elif a % 2 == 1:
        return x * modular_exponent(x, a - 1, n) % n
    else:
        half = modular_exponent(x, a // 2, n)
        return half * half % n

The implementation of encryption and decryption functions is now trivial:

def encrypt(x, a, n):
    return modular_exponent(x, a, n)


def decrypt(y, b, n):
    return modular_exponent(y, b, n)

Let’s test this by encrypting an arbitrary number. I’ve chosen x = 1234567890.

x = 1234567890
y = encrypt(x, a, n)
decrypted = decrypt(y, b, n)

print(f"Encrypted value: {y}")
print(f"Decrypted value: {decrypted}")
assert(x == decrypted)

And volla, this works indeed!

p =  110048843095422197087071757611329503833
q =  113176829162524124401163314225963653241
n =  12454979114544020547972318036531202282281996899056077916592845019112592372753
a =  9555536198971257872315549745690616564802756410986833210548959912717075484843
b =  1304212785790701980999567760768489760055206957755884280677310226964974661827

Public Key:
  n=12454979114544020547972318036531202282281996899056077916592845019112592372753
  a=9555536198971257872315549745690616564802756410986833210548959912717075484843

Private Key: 
  p=110048843095422197087071757611329503833
  q=113176829162524124401163314225963653241
  b=1304212785790701980999567760768489760055206957755884280677310226964974661827

Let's encrypt a number: 1234567890
Encrypted: 2873374296088141558403205193380890278565591138238668833903038265370880941659
Decrypted: 1234567890

You can find the full source code on my GitHub here.

Conclusions

I hope you’ve learned something new today. This post only covers the basics of RSA, but there is a lot more detail and subtleties around security. This is why you should never implement RSA yourself unless you are an expert in cryptography. Even then, you should use an existing library.

RSA cryptosystem is probably one of the simplest one to learn, but it’s still widely used. However, people are slowly moving to other cryptosystems such as Eliptic-Curves cryptography because it provides better security guarantees for the same length keys. We will cover Eliptic-Curves in another blog post.

Also, don’t forget to subscribe and share this post if you’ve liked it.