The RSA Cryptosystem

10. The RSA Cryptosystem#

10.1. Euler’s Formula#

Before we introduce a new and important public-key cryptosystem, we need some theory. We start by reviewing some facts from the chapter on powers in $\mathbb{Z}/m\mathbb{Z}$:

Definition 10.1 (The Euler $\varphi$-Function)

Given a positive integer $m$, we defined the $\varphi(m)$ as $|(\mathbb{Z}/m\mathbb{Z})^{\times}|$, i.e., the number of elements of $(\mathbb{Z}/m\mathbb{Z})^{\times}$, in other words

\[\varphi(m) = |\{a \in \{1, 2, \ldots, m-1\} \; : \; \gcd(a, m) = 1 \}|.\]

We also define $\varphi(1)$ as $1$. This function is called the Euler $\varphi$ function.

(Remember that for a set $S$, we denote by $|S|$ the number of elements in the set.)

Theorem 10.1 (Formula for $\varphi(m)$)

Let $m$ be a positive integer greater than one and

\[m = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\]

be its prime decomposition. Then

\[\varphi(m) = \left( (p_1 - 1) \cdot p^{e_1 -1} \right) \cdot \left((p_2 - 1) \cdot p_2^{e_2 - 1}\right) \cdots \left((p_k - 1) \cdot p_k^{e_k - 1}\right).\]

Theorem 10.2 (Euler’s Theorem)

Let $a$ be a unit in $\mathbb{Z}/m\mathbb{Z}$ (i.e., $\gcd(a, m) = 1$). Then $a^{\varphi(m)} = 1$ in $\mathbb{Z}/m\mathbb{Z}$ (i.e., $a^{\varphi(m)} \equiv 1 \pmod{m}$).

Proposition 10.1 (Reducing Powers)

Let $a$ in $\mathbb{Z}/m\mathbb{Z}$ and suppose that $k$ is a positive integer such that $a^k = 1$. Then, if $r \equiv s \pmod{k}$ (so, modulo $k$, and not $n$!), then $a^r = a^s$. Therefore, we can reduce exponents modulo $k$ (and not $m$).

In this chapter we will deal with a modulus $N = pq$, where $p$ and $q$ are two distinct (very large) primes. So, we have that $\varphi(N)=(p-1)(q-1)$. Then, by Euler's Theorem, we have that if $\gcd(a, N) = 1$, then $a^{(p-1)(q-1)} = 1$ in $\mathbb{Z}/N\mathbb{Z}$. But we can do better:

Theorem 10.3 (Euler’s Formula)

Let $p$ and $q$ be distinct primes, $N = pq$, and $g = \gcd((p-1), (q-1))$, and $a \in (\mathbb{Z}/N\mathbb{Z})^{\times}$. Then, $a^{(p-1)(q-1)/g} = 1$ (in $\mathbb{Z}/N\mathbb{Z}$). In particular, if both $p$ and $q$ are odd, we have that $a^{(p-1)(q-1)/2} = 1$.

Note

Note how we could reduce the power necessary to obtain $1$ from $(p-1)(q-1)$ to $(p-1)(q-1)/g$.

Proof. Since $\gcd(a, pq) = 1$ (as $a$ is a unit in $\mathbb{Z}/N\mathbb{Z}$), we have that $\gcd(a, p) = \gcd(a, q) = 1$, so $a$ (as an integer) is also a unit in $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$. Then, by Euler's Theorem, and noting the $(p-1)/g$ and $(q-1)/g$ are both integers, we have that

\[\begin{split}\begin{align*} a^{((p-1)(q-1)/g} & = \left( a^{p-1} \right)^{(q-1)/g} \equiv 1^{(q-1)/g} = 1 \pmod{p} \qquad \Longrightarrow \qquad &p \mid a^{(p-1)(q-1)/g} - 1, \\[1.7ex] a^{((p-1)(q-1)/g} & = \left( a^{q-1} \right)^{(p-1)/g} \equiv 1^{(p-1)/g} = 1 \pmod{q} \qquad \Longrightarrow \qquad &q \mid a^{(p-1)(q-1)/g} - 1. \end{align*}\end{split}\]

Since $\gcd(p, q) = 1$, this means that $pq \mid a^{(p-1)(q-1)/g} - 1$, i.e., $a^{(p-1)(q-1)/g} = 1$ in $\mathbb{Z}/N\mathbb{Z}$.

Note that if $p$ and $q$ are odd, then $p-1$ and $q-1$ are even and hence $2 \mid \gcd(p - 1, q - 1) = g$. Thus, $g/2$ is an integer and hence, in $\mathbb{Z}/N\mathbb{Z}$ we have

\[ a^{(p-1)(q-1)/2} = a^{(p-1)(q-1)(g/2)/g} = \left( a^{(p-1)(q-1)/g} \right)^{g/2} = 1^{g/2} = 1.\]

10.2. Roots Modulo $N = pq$#

The security of ElGamal’s cryptosystem is based on the difficulty of solving the discrete log problem. The security of our next cryptosystem will depend on the difficulty of taking roots modulo $N = pq$, where $p$ and $q$ are distinct large primes.

Question

Given two distinct large primes $p$ and $q$, $N = pq$, $c \in \mathbb{Z}/N\mathbb{Z}$, and a positive integer $e$, how can we find $x$ such that $x^e = c$ (in $\mathbb{Z}/N\mathbb{Z}$), i.e., find the $e$-th root of $c$ (in $\mathbb{Z}/N\mathbb{Z}$)?

We start approaching a simpler problem, when the modulus is prime:

Proposition 10.2 (Roots in $\mathbb{Z}/p\mathbb{Z}$)

Let $p$ be prime, $c \in \mathbb{Z}/p\mathbb{Z}$, and $e$ a positive integer with $\gcd(e, p-1) = 1$. Then, let $d$ be the inverse of $e$ modulo $p-1$ (i.e., $ed \equiv 1 \pmod{p-1}$). Then, in $\mathbb{Z}/p\mathbb{Z}$, we have that

\[x^e = c \quad \text{if and only if} \quad x = c^d.\]

(So, $c^d$ is the only $e$-th root of $c$ in $\mathbb{Z}/p\mathbb{Z}$.)

Proof. First, note that since the modulus is prime, we have that $x=0$ if and only if any power of $x$ is zero. (This follows from Euclid's Lemma.) So, if $c=0$, then $x^e=0$ if and only if $x=0$, and $x=0$ if and only if $x^d=0$.

So, assume that $x \neq 0$ (in $\mathbb{Z}/p\mathbb{Z}$), i.e., $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$. Since $\varphi(p) = p-1$, by {name} we have that $x^{p-1} = 1$. Since $(p-1) \mid (de - 1)$, we have that $x^{de-1} = 1$, i.e., $x^{de} = x$. Since $c$ is also a unit, the same argument tells us that $c^{de} = c$.

So, if $x^e = c$, then raising both sides to the $d$-th power, we have that

\[x = x^{de} = c^d.\]

And if $x=c^d$, then raising both sides to the $e$-th power, we have that

\[x^e = c^{de} = c.\]

We can apply this to case we actually need:

Proposition 10.3 (Roots in $\mathbb{Z}/pq\mathbb{Z}$)

Let $p$ and $q$ be distinct primes, $N=pq$, $c \in \mathbb{Z}/N\mathbb{Z}$, and $e$ a positive integer with $\gcd(e, \varphi(N)) = 1$. Then, let $d$ be the inverse of $e$ modulo $\varphi(N)$ (i.e., $ed \equiv 1 \pmod{\varphi(N)}$). Then

\[x^e = c \quad \text{if and only if} \quad x = c^d.\]

(So, $c^d$ is the only $e$-th root of $c$ in $\mathbb{Z}/N\mathbb{Z}$.)

Proof. First note that since $\gcd(e, \varphi(N)) = \gcd(e, (p-1)(q-1)) = 1$, then $\gcd(e, (p-1)) = \gcd(e, (q-1)) = 1$. Also, since $ed \equiv 1 \pmod{(p-1)(q-1)}$, then $ed \equiv 1 \pmod{p-1}$ and $ed \equiv 1 \pmod{q-1}$.

So, if $x^e = c$ (in $\mathbb{Z}/N\mathbb{Z}$), by Proposition 10.2, we have

\[\begin{split}\begin{align*} x^e \equiv c \pmod{pq} \quad &\Longrightarrow \quad x^e \equiv c \pmod{p} \quad &\Longrightarrow \quad x \equiv c^d \pmod{p}, \\ x^e \equiv c \pmod{pq} \quad &\Longrightarrow \quad x^e \equiv c \pmod{q} \quad &\Longrightarrow \quad x \equiv c^d \pmod{q}, \\ \end{align*}\end{split}\]

which together, since $\gcd(p, q) = 1$, tell us that $x \equiv c^d \pmod{N}$ (as $N=pq$), i.e., $x = c^d$ in $\mathbb{Z}/N\mathbb{Z}$.

Conversely, if $x=c^d$, then raising to the $e$-th power and since $ed \equiv 1 \pmod{\varphi(N)}$, we get by Euler's Theorem and Proposition 10.1 that $x^e = (c^d)^e = c^{de} = c$ in $\mathbb{Z}/N\mathbb{Z}$.

The following proposition, gives a faster way to find roots in $\mathbb{Z}/N\mathbb{Z}$:

Proposition 10.4

Let $p$ and $q$ be distinct primes, $N = pq$, $g = \gcd(p-1, q-1)$, $e$ a positive integer, and $d$ and inverse of $e$ modulo $(p-1)(q-1)/g$. Then, for all $c \in \mathbb{Z}/N\mathbb{Z}$, we have that $x = c^d$ is such that $x^e = c$, i.e., $c^d$ is an $e$-th root of $c$ in $\mathbb{Z}/N\mathbb{Z}$.

Important

This means that when finding $d$ to find the $e$-th root of $c$ (as in Proposition 10.3), we can find an inverse in modulo $(p-1)(q-1)/g$ instead of modulo $(p-1)(g-1)$, which is likely faster (if $g>1$) and likekly yields a smaller decryption exponent.

Proof. By Theorem 10.3, if $c$ is a unit, then we have that $c^{(p-1)(q-1)/g} = 1$, so by Proposition 10.1, we have that $c^{ed} = c^1 = c$. If $c$ is not a unit, i.e., if $c=p$ or $c=q$, then an argument similar to one the in the proof of Proposition 10.3, where we look at congruences modulo $p$ and $q$ separately, gives the result. Hence, if $x = c^d$, then $x^e = c^{de} = c$.

So, if we have $N = pq$ as above, $e$ a positive integer, and $c \in (\mathbb{Z}/N\mathbb{Z})^{\times}$, and we want to solve $x^e = c$, we simply need to find and inverse of $e$ modulo $\varphi(N)$ (or modulo $(p-1)(q-1)/g$, where $g = \gcd(p-1, q-1)$). So, we need to find $\varphi(N)$ for the given $N$.

10.3. How to compute $\varphi(N)$?#

Question

How can we find $\varphi(N)$ from $N = pq$, i.e., how can we either compute $\varphi(N)$ directly or factor $N$? How hard is it to solve either problem?

We first note that the two questions are equivalent. If we know how to factor $N = pq$ to find $p$ and $q$, the we can compute $\varphi(N)$ as $(p-1)(q-1)$ (using the formula).

But suppose we have a method to find $\varphi(N)$ without using the prime factorization of $N$, i.e., without the formula of Theorem 10.1. What we get is just a number, but we know that $\varphi(N)=(p-1)(q-1) = pq - p - q + 1 = N - p - q + 1$. So, we get $p+q = N - \varphi(N) + 1$, where we know all numbers on the left, so we know the result of $p+q$. We also know the product $N = pq$. With those two in hand, we can find $p$ and $q$ themselves!

We have that

\[(x - p)(x - q) = x^2 -(p+q)x + pq = x^2 - (N - \varphi(N) + 1)x + N.\]

Finding the two roots of this quadratic equation (e.g., by using the quadratic formula), we find $p$ and $q$.

Therefore, the two problems are equivalent: if we know how to factor $N=pq$, we know how to compute $\varphi(N)$ and if we know how to compute $\varphi(N)$ (for $N=pq$), then we know how to factor $N$.

10.3.1. Example#

Suppose we have $N = 28{,}651{,}547$, a number we know that is product of two primes, say $N = pq$, and somehow we also know that $\varphi(N) = 28{,}640{,}496$. Let’s find $p$ and $q$ as described above. Make a polynomial

\[x^2 - (N - \varphi(N) + 1)x + N = x^2 - (28{,}651{,}547 - 28{,}640{,}496 + 1 )x + 28{,}651{,}547 = x^2 - 11{,}052 x + 28{,}651{,}547= 0.\]

solve(x^2 - 11052*x + 28651547 == 0, x)

[x == 4153, x == 6899]

The two solutions, $4{,}153$ and $6{,}899$ are $p$ and $q$!

is_prime(4153) and is_prime(6899) and 4153 * 6899 == 28651547

True

10.4. The RSA Cryptosystem#

In 1977 Ron Rivest, Adi Shamir, and Leonard Adleman published the public-key cryptosystem that become known as the RSA Cryptosystem. It was the first public available public-key cryptosystem (earlier than ElGamal’s), although, according to Wikipedia:

An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

While the security of ElGamal’s is based on the difficulty of computing discrete logs, RSA’s security is based on the difficulty of taking $e$-th roots in $\mathbb{Z}/N\mathbb{Z}$, where $N$ is a product of very large primes, i.e., it’s based on how hard it is to factor $N$.

The RSA Cryptosystem: In order for Bob (or anyone else) to send encrypted messages to Alice:

Set up:
1. Alice chooses two large primes $p$ and $q$, to be kept secret, and computes $N = pq$.
2. Alice chooses an encryption exponent $e$ between $2$ and $(p-1)(q-1) - 1$, with $\gcd(e, (p-1)(q-1)) = 1$.
3. Alice uses the Extended Euclidean Algorithm to compute and inverse $d$ of $e$ modulo $(p-1)(q-1)$, i.e., she finds $d$ such that $de \equiv 1 \pmod{(p-1)(q-1)}$. This $d$ is the decryption exponent and is kept secret.
4. Alice publishes $N$ and $e$.
Encryption: To send a message $m$ (a number in $\{2, 3, \ldots, N-1\}$) to Alice, Bob computes $c=m^e$ in $\mathbb{Z}/N\mathbb{Z}$, and sends $c$ to Alice.
Decryption: Alice decodes the encrypted message $c$ by computing $c^d$ in $\mathbb{Z}/N\mathbb{Z}$.

Note that we know that the decryption works, since $de \equiv 1 \pmod{(p-1)(q-1)}$ implies that

\[c^d = \left( m^e \right) ^d = m^{de} = m \quad \text{(in $\mathbb{Z}/N\mathbb{Z}$).}\]

Warning

As we will see in a later chapter, it is crucial to choose the primes $p$ and $q$ such that both $p-1$ and $q-1$ have large prime factors!

The current recommendation is that each of these primes have at least $1024$ bits, meaning that each is at least $2^{1023}$, making $N$ a $2048$-bit integer. For extra security, sometimes it is recommended to double the number of bits, with each prime being greater than or equal to $2^{2047}$.

Note

Unlike ElGamal’s cryptosystem, one cannot use someone else’s setup, as $p$ and $q$ must be kept secret.
Encrypting and decrypting are done by computing powers in $\mathbb{Z}/N\mathbb{Z}$, so Fast Powering comes handy!
It is important to have fast encryption, so using a small $e$ helps. Of course we cannot use $e=1$ and $2$ is not relatively prime to $(p-1)(q-1)$, so it is also out. So, one could use $e=3$, if it is relatively prime to $(p-1)(q-1)$. This seems to be safe, but there are some concerns. An option is to use $e = 2^{16} + 1$ (a prime!), if it is relatively prime to $(p-1)(q-1)$, as computing $m^e$ then takes only five products!
One should be careful once $d$ is found, that it is not too small. We need $d > \sqrt[4]{N}$. If that is not the case, one should choose another $e$ or $p$ and $q$.
Although we only know how to compute roots in $\mathbb{Z}/N\mathbb{Z}$ if we know how to factor $N$, it is possible that there might be a yet unknown, novel way without it. Therefore, strictly speaking, the security of the RSA relies in the difficulty in computing roots in $\mathbb{Z}/N\mathbb{Z}$ (quickly enough), and not (necessarily) on the difficulty of factoring $N$.

Homework

In your homework you will write functions to generate keys, and to encrypt and decrypt messages with the RSA cryptosystem.

Note

The RSA is still currently used, but has been mostly superseded by elliptic curve cryptography, which we will discuss later.

10.5. Example#

Let’s illustrate the process with an example. Let’s say Alice takes $p=7853847607$ and $q=3654374677$, and so $N = pq = 28700901812037847939$.

p, q = 7853847607, 3654374677
N = p * q
N

28700901812037847939

Let’s check that $p$ and $q$ are indeed prime:

is_prime(p) and is_prime(q)

True

Now, Alice can compute $\varphi(N)$:

phiN = (p - 1) * (q - 1)
phiN

28700901800529625656

Then, Alice takes the encryption exponent $e = 2^{16} + 1$. But we need to make sure it is relatively prime to $\varphi(N)$:

e = 2^16 + 1
gcd(e, phiN)

It is, so we can use this $e$. Now, Alice computes the decryption exponent:

d = ZZ(Mod(e, phiN)^(-1))
d

9919650375876169961

Alternatively, she could also use:

g = gcd(p - 1, q - 1)
d = ZZ(Mod(e, phiN // g)^(-1))
d

352683109032961409

Alice then publishes $N$ and $e$, keeping $p$, $q$, and $d$ secret.

Now Bob wants to send a message to Alice, say:

m = Mod(1001001, N)

He then computes $m^e$ and sends it to Alice:

encrypted_message = m^e
encrypted_message

20809621329455491585

Now Alice can recover the original message by raising the encrypted message to the power $d$:

encrypted_message^d

Success!

10.6. Implementation and Security Issues#

10.6.1. Quantum Computers#

As observed earlier, the RSA is not quantum-safe, since quantum computers, using Shor’s algorithm, can quickly factor very large numbers (much more efficiently than our current computers).

10.6.2. Man in the Middle#

Solving the math problem that define cryptosystems are usually unfeasible to attackers. Thus, they have to find other ways to break the security of the communication.

Suppose that Eve not only can see messages being exchanged between Bob and Alice, but can actually intercept them and replace the originals with different ones. This is what is called a man-in-the-middle attack. She then might be able to find a way to read the messages without being able to solve the underlying mathematical problem.

Let’s illustrate how this could be done with the Diffie-Hellman key exchange: Eve knows the prime $p$, $g \in \mathbb{F}_p^{\times}$, and its order $N$, as they are publicly available.

Alice chooses a secret key $a$, and sends $A = g^a$ (computed in $\mathbb{F}_p$) to Bob.
Eve intercepts $A$, chooses her own secret key $e$, and sends Bob $E = g^e$, who believes it came from Alice.
Bob chooses a secret key $b$, and sends $B = g^b$ to Alice.
Eve intercepts $B$, and send the same $E$ as above to Alice as well, who believes it came from Bob.
The secret, shared key between Alice and Bob, was supposed to be $B^a = A^b = g^{ab}$. But instead, Alice has $E^a = g^{ea}$ and what Bob has is $E^b = g^{eb}$. So, Alice and Bob actually share individual keys with Eve, while thinking that they share a key with each other.

To further illustrate the point, suppose that Alice and Bob wants to exchange secrete message by encoding them using their shared key, similar to ElGamal. So, if Bob wants to send the message $m$ to Alice, he would send $m' = A^b m$ to Alice, $A^b$ being the shared key. (So, Alice would be able to decrypt it by computing $(B^a)^{-1} m' = m$.) But, in this situation, he would send $m' = E^bm$ to Eve (intercepting it on the way to Alice). Eve then is capable of decrypting it, as she has $B^e = E^b$, and can invert it to recover $m$.

Then, Eve sends $m'' = A^e m$ to Alice, who believes it is coming from Bob. When she deciphers is, she will use the key $E^a$. Since $E^a = A^e$, she can decrypt it and obtain Bob’s original message $m$. So, Alice believes that their communication was successful, but Eve was able to read the message as well.

10.6.3. Oracle#

Suppose that Eve contacts Alice and asks her to verify that Alice is really “Alice”, i.e., the party that can decode messages encrypted with the public-keys $d$ and $N$. She may say that she will send some random message and asks Alice to decrypt it and send back the original message to Eve, so that Eve can see that Alice can indeed decode it.

Alice, in this case, would be called an oracle.

Alice might think that this would be OK. If she sees that the message is not random (say, maybe it looks like some message that Bob would send her, or a credit card number, or social security number, etc.) or suspicious, she can just not send the decrypted message back to Eve.

But imagine that Eve intercepts some message encrypted message $c = m^e \in \mathbb{Z}/N\mathbb{Z}$, using RSA with encrypting exponent $e$, from Bob to Alice. Eve can make it look random by choosing an element $k \in (\mathbb{Z}/N\mathbb{Z})^{\times}$ different from $0$ and $1$, and sending $c' = k^e c$, where $e$ is the public encrypting exponent. She can then send it to Alice to verify she can decrypt it. When she does, she computes

\[(c')^d = (k^e c)^d = (k^e m^e)^d = (km)^{ed} = km.\]

To Alice, this will look random (since it is $km$, and not $m$) and she might feel confident that she can send $km$ back to Eve, proving she can decrypt messages encoded with the public method.

But, when Eve received $km$, she can multiply it by $k^{-1}$ (the inverse in $\mathbb{Z}/N\mathbb{Z}$) and obtain $m$ back: $k^{-1} \cdot (km) = (k^{-1}k) \cdot m = 1 \cdot m = m$. Then, Eve is capable of reading Bob’s secrete message $m$, without really computing an $e$-th root in $\mathbb{Z}/N\mathbb{Z}$.

This makes it clear that Alice should not decipher any message to anyone!

10.6.4. Multiple Encrypting Exponents#

Suppose that Alice publishes two different encrypting exponents, say $e_1$ and $e_2$, for the same modulus $N$. If somehow Eve can read the same message from Bob, say $c_1 = m^{e_1}$ and $c_2 = m^{e_2}$ (in $\mathbb{Z}/N\mathbb{Z}$), using the different exponents and $\gcd(e_1, e_2) = 1$, then Even can recover $m$: using the Extended Euclidean Algorithm, Eve finds integer $u$ and $v$ such that

\[ue_1 + ve_2 = 1.\]

Then, she simply computes:

\[c_1^u \cdot c_2^v = (m^{e_1})^u \cdot (m^{e_2})^v = m^{ue_1} \cdot m^{ve_2} = m^{ue_1 + ve_2} = m^1 = m,\]

recovering the secrete message $m$.

This situation is not too far fetched: imagine that Alice is an online retailer and Bob had the send his credit card number twice, for different transactions, and Alice had to change the encryption scheme for some reason (e.g., security concerns with the former encrypting exponent) in between transactions.

The bottom line is that if Alice needs to change the encryption method, she should change the modulus $N$, and not only the encrypting/decoding exponents.

The RSA Cryptosystem

Contents

10. The RSA Cryptosystem#

10.1. Euler’s Formula#

10.2. Roots Modulo \(N = pq\)#

10.3. How to compute \(\varphi(N)\)?#

10.3.1. Example#

10.4. The RSA Cryptosystem#

10.5. Example#

10.6. Implementation and Security Issues#

10.6.1. Quantum Computers#

10.6.2. Man in the Middle#

10.6.3. Oracle#

10.6.4. Multiple Encrypting Exponents#