RSA II

$ \def\ZZ{\mathbb{Z}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} $

From the Last Lecture

We want to sample $(e, d)$ such that $e \cdot d = 1 \pmod{\phi(n)}$.

Inverse relationship

If you think about it, it holds that \[ d = e^{-1} \bmod{\phi(n)}.\]

So, it's easy to sample $(e, d)$:

Choose a random number $e$.
Compute $d = e^{-1} \bmod{\phi(n)}.$

There is a catch

When does $a^{-1} \bmod {m}$ exist?

When a and m are relatively prime.

This implies that $e$ and $\bmod{\phi(n)}$ should be relatively prime. So, the above algorithm is slightly fixed accordingly.

Sampling algorithm for $(e, d)$

Choose a random number $e$.
If $gcd( e, \phi(n) )$ is not 1, go back to step 1.
Compute $d = e^{-1} \bmod{\phi(n)}.$
Output $(e, d)$.

Big big warning: very common pitfall

For some reason, whenever I give a problem about RSA, more than half of the students are confused about the following:

TRUE/FALSE: It should hold that $d = e^{-1}$ $ \bmod n$.

The answer is FALSE. It should be $d = e^{-1}$ $\bmod{\phi(n)}$.

Plain RSA

The Plain RSA encryption scheme is described as follows:

$ {\sf Gen}() $:
1. Choose two exponentially large prime numbers $ p $ and $ q $, and compute $ n = p \cdot q $. note $ \phi(n) = (p-1)(q-1) $.
2. Choose a random number $e$ such that $gcd( e, \phi(n) ) = 1$.
3. Compute $ d = e^{-1} \bmod{ \phi(n) } $. That is, $e \cdot d \bmod \phi(n) = 1$.
4. The public key is $ pk = (n, e) $, and the private key is $ sk = (n, d) $.
$ {\sf Enc}_{pk}(M) $:
1. Parse $ pk = (n, e) $.
2. Compute and output $ C = M^{e} \bmod n $.
$ {\sf Dec}_{sk}(C) $:
1. Parse $ sk = (n, d) $.
2. Output $ C^d \bmod n $.

To see correctness of the scheme:

$ C^d \bmod n = (M^e)^d \bmod n = M^{ed} \bmod n = M^{ed \mod \phi(n)} \bmod n = M^1 \bmod n = M $.

Example

Key generation: With $ n = 11 \cdot 13 = 143 $, we have $ \phi(n) = 120 $. Choose $ e $ co-prime to $\phi(n)$ so that $e \in \ZZ_{\phi(n)}^*$ and has its inverse modulo $\phi(n)$. For example, say $ e = 7 $, then we have $ d = e^{-1} \bmod {\phi(n)} = 7^{-1} \bmod 120 = 103 $.
We have the public key $pk = (n, e) = (143, 7)$ and the secret key $sk = (n, d) = (143, 103)$.
Encryption: Let $ M = 8 $. Then, the ciphertext is $ {\sf Enc}_{pk}(M) = M^7 \bmod 143 = 8^{7} \bmod 143 = 57 $
Decryption: $ {\sf Dec}_{sk}(C) = C^d \bmod n = 57^{103} \bmod 143 = 8 $.

Hardness of Inverting RSA Problem

The RSA encryption is a bit similar to Discrete Logarithm in the sense that they are both dealing with modular exponentiation. However, they are difference in which parts are a problem and which part is the solution.

	Discrete Logarithm	RSA
What's known	$g, p$	$e, n$
Problem instance	$y$	$c$
Solution	$x$	$m$
Condition	$y = g^x \bmod p$	$c = m^e \bmod n$

As the following chart shows, the RSA encryption outputs numbers that looks random.

Hardness of Inverting RSA Problem (Common Belief)

There is no polynomial time algorithm that solves the Inverting RSA problem.

Indeed, the hardness of Inverting RSA is related to many other hardness problems. See the picture below:

Fig 1. Hardness of Inverting RSA

Hardness of Factoring (Common Belief)

Suppose $n = pq$ where $p$ and $q$ are randomly chosen large numbers. Then, given only $n$ as input, no polynomial time algorithm can factor it.

The above picture shows that if the adversary can factor $n$, then he can completely break RSA.

Message Space

One easily convert any binary data into a number (and vice versa). See the class notes 3 for more detail.

Catch?

Recall the following condition:

For any positive integer $n$, for any $m \in \ZZ_n^*$, and for any integer $x$, it holds  m^x \bmod n = m^{r} \bmod n, where $r = x \bmod{\phi(n)}$.

In particular, focus on the condition $m \in \ZZ_n^*$. The condition implies that the correctness of RSA encryption holds only when $m$ and $n$ are co-prime.

When $n$ is small (like homework problems or toy programs), it matters. Make sure to choose $m$ from $\ZZ_n^*$.
In actual setting, it doesn't matter. If $gcd(m, n) > 1$, then you actually factor $n$. So, it won't happen.

Security

Deterministic Encryption

Note that Plain RSA is a deterministic encryption scheme. Encryption is a simple modular exponentiation. No randomness is involved what so ever.

The plain RSA is not IND-CPA secure.

Recall the IND-CPA game. The adversary chooses two messages. If the adversary, encrypts the messages, due to the deterministic behavior, one of the encryption must match the target ciphertext. So, the adversary can always make the perfectly good guess.

Long History of Attacks on RSA Assumption

Moreover, there have been a long history of attacks, telling us that a tiny tweak of parameters for efficiency improvement may turn the system vulnerable. You have to follow the parameters very carefully.

Boosting Plain RSA to achieve IND-CPA Security

We won't go into detail about the actual scheme that is IND-CPA secure. We refer you to the standard: PKCS #1 v2.0. However, we explain the main idea here.

Randomize the encryption algorithm by adding a random padding $ r $ to the message and perform $ {\sf Enc}_{pk}( r \| M ) $. Now, when decryption, one can take off the random padding to recover the message correctly. Of course, the message space will be shrunk, but it achieves IND-CPA security.

Achieving IND-CCA Security

The PKCS also gives an IND-CCA secure encryption scheme called RSA-OAEP, that is, Plain RSA encryption along with OAEP (optimal asymmetric encryption padding). Refer to the standard above or the wiki page. RSA-OAEP is used in TLS and SSH.

	Discrete Logarithm	RSA
What's known	\(g, p\)	\(e, n\)
Problem instance	\(y\)	\(c\)
Solution	\(x\)	\(m\)
Condition	\(y = g^x \bmod p\)	\(c = m^e \bmod n\)