Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

migrated from Oct 3 '13 at 15:55

This question came from our site for information security professionals.

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.

share|improve this answer

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.