RSA

Subsection 5.5.4 RSA

Figure 5.5.4.1. Ron Rivest, Adi Shamir, and Leonard Adleman (left to right), inventors of the RSA encryption scheme.
🔗

First, we give a bit of history. Ron Rivest, Adi Shamir, and Leonard Adleman (shown in Figure 5.5.4.1) first publicly described this algorithm for public key encryption in 1978 [9].

Clifford Cocks described an equivalent system in 1973, but it was classified by the UK intelligence agency GCHQ until 1997}

🔗

They posted one of the first public-key encryption messages using a 129 digit number which later became known as RSA-129 [10].

\begin{align*} \text{RSA-129} = \amp 1143816257578888676692357799761466120102182967212\\ \amp 4236256256184293570693524573389783059712356395870\\ \amp 5058989075147599290026879543541 \\ = \amp 3490529510847650949147849619903898133417764638493\\ \amp 387843990820577\\ \cdot\amp 3276913299326670954996198819083446141317764296799\\ \amp 2942539798288533. \end{align*}

🔗

They offered a $100 prize and remarked that using technology and factoring techniques available at that time, it would take 40 quadrillion years to crack. Advances in factoring techniques and computers cracked the code in April 1994 [5] to find that the secret message was:

The Magic Words are Squeamish Ossifrage
²
According to Wikipedia, Ossifrage is an older name for the lammergeier, a scavenging vulture that is famous for dropping animal bones and live tortoises onto rocks to crack them open. It might perhaps be considered among the least squeamish of creatures.
🔗

🔗

🔗

Suppose Alice wants to send Bob an encrypted message. Bob lets her know his public key, a pair of integers $(N,e)\text{.}$

🔗

Definition 5.5.4.2.

The RSA public encryption key consists of a pair of integers $(N,e)\text{,}$ where $N$ is the product of two distinct primes $p$ and $q\text{,}$ and the encryption exponent $e$ is relatively prime to $\phi(N) = (p-1)(q-1)\text{.}$

🔗

The message space is set of integers $\{1, 2,\cdots, N\}\text{.}$ To encrypt a message $M$ from the message space, Alice computes the integer $C$ in the message space that satisfies

\begin{equation*} C \equiv M^e \pmod{N}. \end{equation*}

Notice that with fast exponentiation, this is fast.

🔗

Remark 5.5.4.3.

RSA encryption works when the messages are integers between $1$ and $N\text{.}$ As we saw in Subsection 5.2.2, ASCII encoding allows us to encode a message string into an integer. After the message is encoded as an integer, we can encrypt it with RSA encryption.

🔗

If an eavesdropper Eve captures $C$ while it is being transmitted, Eve will have a hard time computing the original message $M\text{,}$ since taking $e$ th roots is a hard problem known as the discrete log problem .

🔗

How is it any easier for Bob? The trick is that Bob has a bit of extra information. When constructing the key, Bob chooses $N$ to be a product of two distinct primes $p$ and $q\text{,}$ so that $N = pq\text{.}$ The exponent $e$ is chosen so that the greatest common divisor $\gcd(e,\phi(N))=1\text{.}$ Since Bob knows the factorization of $N\text{,}$ he can easily compute the Euler $phi$ function $\phi(N) = (p-1)(q-1)\text{.}$ Then using the Euclidean algorithm, Bob can compute an inverse to $e$ modulo $\phi(N)\text{,}$ an integer $d$ such that $ed \equiv 1 \pmod{\phi(N)}\text{.}$ By Bézout’s Theorem, there is an integer $k$ so that $ed = 1 +k\phi(N)\text{.}$ Now Euler’s generalization to Fermat’s little theorem says that if $\gcd(C,N)=1\text{,}$ we have

\begin{align*} C^d \amp \equiv (M^e)^d \pmod{N} \\ \amp \equiv M^{1+k\phi(N)} \pmod{N} \\ \amp \equiv M\cdot (M^{\phi(N)})^k \pmod{N} \\ \amp \equiv M \pmod{N}. \end{align*}

In fact, this happens even if $\gcd(C,N) \neq 1\text{.}$ We show this using Chinese Remainder Theorem> 5.4.2.1 in Theorem 5.5.4.6.

🔗

Thus, to decrypt the message, Bob does not need to take an $e$ th root of $C$ modulo $N\text{.}$ Instead, he can raise $C$ to the $d$ th power and achieve the same result. Thank you, Euler! Again, with fast exponentiation, this is fast.

🔗

Note that if Eve can factor $N\text{,}$ then she can also decrypt the message. For that reason, Bob must choose $p$ and $q$ “large” enough.

🔗

Definition 5.5.4.4.

A positive integer $d$ is a decryption exponent for RSA public key $(N,e)\text{,}$ $d$ is an inverse of $e$ modulo $\phi(N)\text{.}$

🔗

Before proving that RSA works in general, let’s look at a small example.

🔗

Example 5.5.4.5.

Suppose Bob has public key $(N,e) = (55,3)\text{.}$ For the purposes of this example, pretend $55$ is so large that Eve cannot factor it. Then Alice can encrypt any number from $1$ to $55\text{.}$ Suppose Alice wants to send $M = 18\text{.}$ She computes

\begin{equation*} C = M^e \bmod{N} = 18^3 \bmod{55} = 2. \end{equation*}

🔗

How does Bob decrypt $C\text{?}$ He knows that $\phi(55) = 40\text{,}$ since he created the key. The decryption exponent $d$ is the inverse if $e$ modulo $\phi(N)\text{,}$ so it satisfies $ed \equiv 1 \pmod{\phi(N)}\text{.}$ Bob can compute $d\equiv -13 \pmod{40}$ by Extended Euclidean Algorithm

\begin{equation*} \begin{array}{r r r r} q\amp r\amp s\amp t\\\hline \amp 40 \amp 1 \amp 0\\ 13 \amp 3 \amp 0 \amp 1\\ 3 \amp 1 \amp 1 \amp -13\\ \amp 0 \amp -3 \amp 40\\ \end{array} \end{equation*}

or by observing that $3 \cdot 13 = 39 \equiv -1 \pmod{40}\text{.}$ Thus $d = -13 \bmod{40} = 27\text{.}$

🔗

To decrypt $C = 2\text{,}$ Bob computes

\begin{equation*} M = C^d \bmod{N} = 2^{27} \bmod{55} = 18. \end{equation*}

🔗

What are some of the problems with this example? that is , What kind of attacks should Eve try to decrypt the message?

🔗

First, the value $N = 55$ is too easy to factor. Once Eve knows $55 = 5 \cdot 11\text{,}$ Chinese Remainder Theorem> 5.4.2.1 tells her that

\begin{equation*} \phi(55) = \phi(5)\phi(11) = (5-1)(11-1) =40. \end{equation*}

Then she can compute $d$ using Euclidean algorithm just as Bob did to decrypt any intercepted message.

🔗

Next, the message space is too small. Notice that if Eve could solve $x^3\equiv 2 \pmod{55}\text{,}$ she can find Alice’s message. The message space $\set{1,2,\dots,55}$ is small enough that Eve could just compute $x^3 \bmod{55}$ for several values of $x$ and quickly find an answer.

🔗

Theorem 5.5.4.6.

Let $p$ and $q$ be prime numbers with $\gcd(p,q)=1\text{.}$

🔗

Then for all integers $C$ and for all $a\in\{0,\dots,pq-1\}$ we have $a^{1+C(p-1)(q-1)}\bmod pq=a\text{.}$

🔗

Proof.

We distinguish three cases.

Case I: $p\mid a$ and $\gcd(a,q)=1$ 🔗: By Fermat’s Little Theorem 5.4.3.1 $a^{(q-1)}\bmod q=1\text{.}$ Hence

\begin{equation*} a^{1+C(p-1)(q-1)} \bmod q=a\cdot \left(a^{q-1}\right)^{C(p-1)}=a. \end{equation*}

Furthermore it follows from $a \bmod p=0$ that $a^{1+C(p-1)(q-1)}\bmod p=0\text{.}$

🔗

By the Chinese Remainder Theorem> 5.4.2.1 $a^{1+C(p-1)(q-1)} \bmod pq$ is determined uniquely. Therefore $a^{1+C(p-1)(q-1)} \bmod pq =a\text{.}$
🔗
Case II: $q\mid a$ and $\gcd(a,p)=1$ 🔗: Swap $p$ and $q$ in Case I.
🔗
Case III: $\gcd(a,pq)=1$ 🔗: By Fermat’s Little Theorem 5.4.3.1 we have $a^{1+C(p-1)(q-1)}\bmod p=a$ and $a^{1+C(p-1)(q-1)}\mod q=a\text{.}$ The statement follows with the Chinese Remainder Theorem> 5.4.2.1.
🔗

🔗

We use Theorem 5.5.4.6 above to encrypt a message represented as an integer $M$ as an integer $X$ and decrypt $X$ as shown in Figure 5.5.4.7.

🔗

Figure 5.5.4.7. The RSA Cryptosystem. Bob creates a key pair consisting of a private and a public key (top right) and the makes the public key available, for example in a public key directory (top left). To send Bob a secret message Alice obtains Bob’s public key and uses it to encrypts a message (bottom left). Bob decrypts the message using his private key (bottom right).
🔗

Remark 5.5.4.8.

Bob’s decription $X^d\bmod N$ in Figure 5.5.4.7 works because $(e\cdot d) \bmod \bigl((p-1)(q-1)\bigr)=1$ and $0\le M\lt N$ and because by Theorem 5.5.4.6 we have

\begin{align*} X^d \bmod n\amp =(m^e)^d \bmod N\\ \amp= M^{ed}\bmod N\\ \amp= M^{1+k(p-1)(q-1)} \bmod N = M \end{align*}

for some non negative integer $k$

🔗

Why is RSA secure? What numbers should I pick? The encryption exponent $e$ is typically chosen to be $e = 2^{16} + 1 = 65537\text{.}$ This is not for security, but for speed. Because of our fast powering algorithm, this choice of $e$ allows encryption to be done even more quickly.

🔗

If $p$ and $q$ are chosen to be large primes (for today’s technology 100-200 digit primes are large enough), then the claim is that this encryption is secure. To decrypt a message, we either have to be able to take $e$ th roots ( that is , solve $x^e \equiv C \pmod{N}$), or compute $d\text{.}$ The first problem is hard, and one of the main ways to try to solve it is via finding $d\text{.}$ In order to find $d\text{,}$ we must know $\phi(N)\text{.}$ As long as Bob keeps the factors $p$ and $q$ secret then computing $\phi(N)$ is hard.

🔗

In the days of early commercial cryptography, many companies offered “challenges” to measure the state of progress in practical cryptanalysis. RSA used a Factoring Challenge. More information can be found at https://en.wikipedia.org/wiki/RSA_Factoring_Challenge.

🔗

They posted a set of eight challenge numbers, ranging in size from 576 bits (174 decimal digits) to 2048 bits (617 decimal digits) that made up the challenge

The RSA numbers were generated on a computer with no network connection of any kind. The computer’s hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge. Not even the people at RSA knew the factorizations.

. Each number is the product of two large primes, similar to the modulus of an RSA key pair. The first person to submit a correct factorization for any of the challenge numbers was eligible for a cash prize. To date, only four of the eight challenge numbers have been factored.

🔗

A reasonable RSA key to use is 1024 bits. Their RSA-1024 has 309 decimal digits.

\begin{align*} N = \amp 135066410865995223349603216278805969938881475605667027524485 \\ \amp 143851526510604859533833940287150571909441798207282164471551 \\ \amp 373680419703964191743046496589274256239341020864383202110372 \\ \amp 958725762358509643110564073501508187510676594629205563685529 \\ \amp 475213500852879416377328533906109750544334999811150056977236 \\ \amp 890927563 \end{align*}

🔗

Just how large is $N\text{?}$ There is a nice video by Vsauce explaining to see how large $52!$ is. If you don’t have 20 minutes, skip to around the 15:56 minute mark. Even then, we are not done, since $52!$ is MUCH smaller than $N\text{.}$ In fact,

\begin{equation*} N \gt (52!)^4, \end{equation*}

so if we repeat the process $52!$ times, then repeat all of that $52!$ times, then repeat all of that $52!$ times, we are still not done. https://www.youtube.com/watch?v=ObiqJzfyACM

🔗

Figure 5.5.4.9. Security. (`https://xkcd.com/538/`) Actual actual reality: nobody cares about his secrets. (Also, I would be hard-pressed to find that wrench for \$5.)
🔗

🔗

Prev Top Next