RSA encryption exponent

Question

In RSA public-key material (e, N), why must the encryption exponent e be relatively prime to $\phi(N)$? Why must any public key encryption algorithm resist CPA?

Answer 1

why must the encryption exponent e be relatively prime to $\phi(N)$

If it's not, then the decryption will not be unique. That is, there will be multiple messages $M_1 \ne M_2$ such that $M_1^e \bmod N = M_2^e \bmod N$; hence if the decryptor receives that common value, he will not be able to determine if the original message was $M_1$ or $M_2$

Why must any public key encryption algorithm resist CPA

When we're analyzing the security of a public key algorithm, we assume that an attacker has the public key (after all, we assume that we can give it out freely, so it is not unreasonable that the attacker can get a copy). With that public key, the attacker can pick list of message he wants, and encrypt those messages. Hence, a public key encryption algorithm must resist CPA because, practically speaking, an attacker can actually perform that attack.

Answer 2

CPA means Chosen-Plaintext Attack: it means a type of attack where the attacker chooses the plaintexts, obtains the corresponding ciphertexts, and tries to work out the key from that information. Asymmetric encryption uses the public key, which is public, and therefore known to everybody, including the attacker. In other words, the "CPA" attack scenario is always applicable to RSA encryption; so RSA had better resist it.

For the public exponent: if $e$ is not prime to $\phi(n)$, then several distinct messages will "encrypt" to the same integer modulo $n$, and the decryption will be ambiguous. This is not good. It could be fixed by enforcing a sufficiently redundant padding so that, upon decryption, the "correct" message can be recovered (that's what happens with Rabin's cryptosystem, which uses $e = 2$, which is not prime to $\phi(n)$). However, that's cumbersome, and it is much simpler to simply require that $e$ is prime to $\phi(n)$. This makes $e$-th power exponentiation a permutation of the set of integers modulo $n$.