4.4 The RSA Cryptosystem

Rivest–Shamir–Adleman (RSA) Cryptosystem

RSA is a public-key scheme that turns a pair of large primes into a trapdoor for modular exponentiation.

Let $p$ and $q$ be distinct 512-bit (or larger) primes that are kept secret and set $N=pq$. Also, let $e$ be any number that is relatively prime to $\phi (N)=(p-1)(q-1)$, such that $\gcd (e,\phi (N))=1$. Then the public key is the tuple $(N,e)$, and the private key is the inverse $d\equiv e^{-1}(\mathrm{mod}\phi (N))$. Note that $d$ is guaranteed to exist since $p$ and $q$ are coprime.

With the keys in place, RSA communication reduces to two mirror-image steps:

• The sender encrypts a message $0\le x\le N-1$ as the ciphertext $E(x)\equiv x^e(\mathrm{mod}N)$.
• The receiver decrypts $y=E(x)$ by computing $D(y)\equiv y^d(\mathrm{mod}N)$.

The security of RSA hinges upon the fact that $p$ and $q$ are kept private by the correspondents. Given only $N,e$, and $y\equiv x^e(\mathrm{mod}N)$, there is no efficient algorithm to compute $d(\mathrm{mod}\phi (N))$.

Correctness

The premise of RSA boils down to one simple fact:

• For every possible message $x\in \{0,1,\dots ,N-1\}$, it holds that $D(E(x))\equiv x(\mathrm{mod}N)$.
  We will now go ahead and prove this fact using Fermat’s Little Theorem, described in 4.2. We restate it here for convenience:
• Fermat’ Little Theorem: For all primes $p$, $a^{p-1}(\mathrm{mod}p)\equiv 1$ if $a\ne 0$, and $a^p\equiv a(\mathrm{mod}p)$ for all $a$.

Examples

(Very Easy) RSA Warm-Up

Consider an RSA scheme with modulus $N=pq$, where $p$ and $q$ are distinct prime numbers larger than $3$.

What is wrong with using the exponent $e=2$ in an RSA public key? A value $e=2$ will not be relatively prime to $(p-1)(q-1)$, which is necessarily even for all $p,q>3$, and therefore an inverse $d$ will not exist for the private key.

Now suppose that $p=5$, $q=17$, and $e=3$.

What is the public key and private key? $N=5\cdot 17=85$. Then, the public key is $(85,3)$, whereas we find private key using a quick application of EGCD, such that $d\equiv 43(\mathrm{mod}64)$.

We have

Alice wants to send a message $x=10$ to Bob. What is the encrypted message $E(x)$ she sends using the public key? We have that $E(x)\equiv 10^3\equiv 65(\mathrm{mod}85)$.

Suppose Bob receives the message $y=19$ from Alice. What equation would he use to decrypt the message? What is the decrypted message? He would use $D(y)\equiv 19^{43}\equiv 59(\mathrm{mod}85)$.

In RSA, we rely on the hardness of two different problems in order to guarantee the security of the scheme. Which two problems are these? If their hardness is not guaranteed, what goes wrong?

(Easy) RSA Security with Multiple Keys

A secret society repeatedly sends the same secret $x$ (with $0\le x<N_i$) using RSA keys $(N_i,e)$ that all share the same exponent $e$ but have pair-wise distinct moduli $N_i$. Eve hears every ciphertext and the public keys; she knows the RSA setup but cannot factor large numbers.

Eve observes two keys $(p_1{q}_1,7)$ and $(p_1{q}_2,7)$ and their own distinct messages $x_1$ and $x_2$, where $p_1,q_1,q_2$ are 1024-bit primes.

Can this information alone let her recover $x$? Since Eve knows that $p_1$ is a factor in both $N_1$ and $N_2$, she computes $\gcd (N_1,N_2)=p_1$. Then she divides both moduli by $p_1$, such that $N_1/p_1=q_1$ and $N_2/p_1=q_2$. Knowing the primes, she can construct the private keys $d_1$ and $d_2$ and recovers the secret.

The secret society sniffs Eve out and switches to a new word and to three keys $(p_1{q}_1,3)$, $(p_2{q}_2,3)$, $(p_3{q}_3,3)$ with six distinct primes and three distinct messages $x_i$. 

Explain briefly why Eve’s previous method no longer works. $N_i,N_j$) such that $i\ne j$, $\gcd (N_i,N_j)=1$ since all primes are distinct and therefore no pair shares a common factor. As such, Eve's method no longer works.

For all pairs (

Now, assume the secret $x$ stays the same and the public exponent is still $e=3$.

The group keeps using the three public keys from part (b) but sends only that single repeated ciphertext. Explain how Eve can recover $x$. Eve observes the following system of equations: $\{\begin{array}{l}{E}_1(x)\equiv x^3(\mathrm{mod}{p}_1{q}_1)\\ E_2(x)\equiv x^3(\mathrm{mod}{p}_2{q}_2)\\ E_3(x)\equiv x^3(\mathrm{mod}{p}_3{q}_3).\end{array}$ She must find $N_i^{-1}$, and use CRT to compute $x^3(\mathrm{mod}{N}_1{N}_2{N}_3)$. Since $x^3<\min (N_i)$, then $x^3=x^3(\mathrm{mod}{N}_1{N}_2{N}_3)$, and therefore she can simply take the cube root to recover $x$.

(Medium) RSA for Concert Tickets

Alice’s concert ticket number is an integer $m\in [0,100]$. She wishes to tell Bob this number over an insecure channel that Eve can monitor, but she does not want Eve to learn $m$.

Bob first announces his RSA public key, which consists of a 512-bit modulus $N=pq$ and an exponent $e$. Alice encrypts her ticket number $m$ with $(N,e)$ and transmits the resulting ciphertext to Bob. Eve sees the encrypted message, and she is able to deduce $m$.

Explain the method that allows Eve to recover $m$ under these conditions. Eve uses brute force to find a number in the small interval $[0,100]$ that, paired with the public key $(N,e)$, results in $E(x)$.

Alice now adopts a more elaborate approach. She chooses a random 256-bit integer $r$ that is coprime to $N$. She then sends Bob two separate ciphertexts, both encrypted with the same public key as before $(N,e)$. The first ciphertext is $C_1\equiv r^e(\mathrm{mod}N)$, and the second ciphertext is $C_2\equiv (rm{)}^e(\mathrm{mod}N)$. Eve knows the protocol in use and can observe both $C_1$ and $C_2,$ but she does not know the value of $r$.

Describe how Eve can nevertheless determine the ticket number $m$. Eve can define $(rm{)}^e\equiv C_1{m}^e(\mathrm{mod}N)$. In other words, $C_1{m}^e\equiv C_2(\mathrm{mod}N)$, and since $\gcd (C_1,N)=1$ there exists a modular inverse such that $m^e\equiv C_1^{-1}{C}_2(\mathrm{mod}N)$. Then, Eve can use the brute force method explained in the previous part to deduce $m$.

(Hard) RSA with CRT Optimization

Alice wants to decrypt faster, so after generating an ordinary RSA key $(pq,e)$ with private exponent $d$, she pre-computes the reduced exponents:
$\begin{array}{r}{d}_p\equiv d(\mathrm{mod}p-1),\\ d_q\equiv d(\mathrm{mod}q-1).\end{array}$  Given a ciphertext $c\equiv m^e(\mathrm{mod}N)$ from Bob, she also forms the expressions:
$\begin{array}{r}x\equiv c^{d_p}(\mathrm{mod}p),\\ x\equiv c^{d_q}(\mathrm{mod}q).\end{array}$

Show that this algorithm is correct, i.e. that $x\equiv m(\mathrm{mod}N)$ is the only solution to the modular system.

a

Example

a

Assuming $g_1\not\equiv 1(\mathrm{mod}q)$, demonstrate how anyone with access to the private key can recover $p$ and $q$.

Start out by expressing $d\equiv e^{-1}(\mathrm{mod}(p-1)(q-1))$, and per CRT there is a unique $d$ such that $d\equiv d_p(\mathrm{mod}p-1)$ and $d\equiv d_q(\mathrm{mod}q-1)$.

Similarly, we can express $c\equiv m^e(\mathrm{mod}pq)$ which is recovered using $x\equiv m^{ed}(\mathrm{mod}pq)$, and per CRT this becomes $x\equiv c_1(\mathrm{mod}p)$ and $x\equiv c_2(\mathrm{mod}q)$,

Now, to evaluate $k$ and $j$, notice that

RSA with Just One Prime