# In RSA, why is it important to choose e so that it is coprime to φ(n)?

When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$.

I know that a common choice is to have $e = 3$ (which requires a good padding scheme) or $e=65537$, which is slower but safer.

I also know that for two primes $p,q$, we have $\phi(pq) = (p - 1) (q - 1)$

Now, let me give a (simple) example:

Say I choose $e = 3$, and two random primes $p = 5$ and $q = 13$.

I can now compute $\gcd(3, \phi(5 \cdot 13)) = 3$.

This reveals that $3$ and $\phi(n)$ are not coprime. I assume this could also happen for large values of $p$ and $q$, and likewise for another $e$. I therefore assume that the RSA algorithm must check that $\gcd(e, \phi(pq)) = 1$. But let's assume it doesn't.

How does RSA become vulnerable if $\gcd(e, \phi(pq)) \neq 1$?

• The Rabin cryptosystem is similar to RSA but uses e=2, which trivially divides $\phi(n)$. It needs to do extra work since this makes decryption ambiguous. Dec 11, 2013 at 8:38
• $e=65537$ also requires a good padding scheme. It makes some of the attacks against badly padded RSA harder but not all of them. Dec 11, 2013 at 13:44

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely.

Let us take the example you give: $N=65$ and $e=3$.

Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$.

However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$

Hence, if we get the ciphertext $8$, we have no way of determining whether that corresponds to the plaintext $2$ or $57$ (or $32$, for that matter); all three plaintexts would convert into that one ciphertext value.

Making sure $e$ and $\phi(N)$ are relatively prime ensures this doesn't happen.

BTW: when you generate an RSA key, common practice nowadays is to select $e$ first, and then when you select the primes $p$, $q$, you make sure that $p-1, q-1$ are relatively prime to $e$; this is equivalent to making sure that $e$ and $\phi(N)$ are relatively prime.

• If you choose safe primes $p,q$, s.t. $p=2a+1$, $q=2b+1$, $a,b$ prime, then you can choose any odd $e$ (coprime to $a$ and $b$), since $\phi(pq)=4ab$.
– tylo
Dec 11, 2013 at 13:52
• Can you explain why when e and phi(n) are relatively prime this doesn't happen? How does this happen in the first place? May 6 at 2:15
• @johan: the short answer is "$e$ and $\phi(n)$ are relatively prime" is equivalent to "$e$ is relatively prime to both $p-1$ and $q-1$". If $e$ and $\phi(n)$ aren't rp then $e$ is not rp to (say) $p-1$ - in that case, there will be a $z \ne 1$ s.t. $z^e = 1 \pmod p$ (and that implies that you don't get unique decryption). If $e$ is rp to $p-1$, then $z$ to $z^e \bmod p$ is a bijection; similarly with $q-1$, hence by the Chinese Remainder Theorem, so is $z$ to $z^e \bmod n$ (brief explanation that fits within a comment) May 6 at 2:52

RSA encryption and decryption is built upon Euler's theorem which says that $a^{\phi(n)} \equiv 1 \pmod n$, and since $p$ and $q$ are primes, $\phi(pq) = (p-1)(q-1)$.

If we have message $M$, modulus $n$, private exponent $d$ and public exponent $e$, RSA encryption works like this:

• Encryption: $C = (M^e \bmod n)$
• Decryption: $M' = (C^d \bmod n)$, which must be the same as $M$ for the decryption to be correct.

Now, combining the above, we get $$M' \equiv C^d \equiv (M^e)^d = M^{ed} \pmod n.$$ Since $ed \equiv 1 \mod{\phi(n)}$, we may write $k\cdot\phi(n) = ed - 1$ for some integer $k$ and rearrange this to $ed = k\cdot\phi(n) + 1$.

Therefore $$M' \equiv M^{ed} = M^{k\phi(n) + 1} = M \cdot M^{k\phi(n)} \pmod n,$$ and since $$M^{k\phi(n)} = (M^{\phi(n)})^k \equiv 1^k = 1 \pmod n,$$ the decryption result $M' \equiv M \cdot M^{k\phi(n)} \equiv M \cdot 1 = M \pmod n$ equals the original message.

All this depends crucially on the fact that $ed=1 \mod{\phi(n)}$, so without it, we won't get $M$ back when we decrypt.

• why was this answer downvoted? Jul 9, 2016 at 13:40
• Unless the person that did revisits the page, we don't know. It could well be that "we won't get M back" and "all three plaintexts would convert into that one ciphertext value" as in the answer of poncho was considered too far apart. The answers semantically different, so only one of the two can be right. @poncho could you take a look at this? Dec 24, 2016 at 1:34
• @MaartenBodewes I think this answer is not answering the question while poncho's answer is. The answer to the question is that by choosing $e$ that is not coprime to $\phi(n)$ it becomes impossible to decrypt uniquely. Nevertheless, I think this answer is good anyway as it cleared up for me why you find $ed \equiv 1 \mod \phi(n)$ (the $ed=k\phi(n)+1$ part what I was missing). Sep 25, 2017 at 16:51
• Well, I guess the downvote is now academic after 8 upvotes. And unless the person doing the downvoting explains himself we'll just consider this a nice second answer after the even better voted answer by Poncho. Until anybody proves one of the two wrong of course, let's keep as scientific as possible :) Sep 25, 2017 at 18:42
• To make $(M^{\phi(n)})^k \equiv 1^k \pmod n$ true, it is required that $M$ and $n$ have to be coprime due to Euler's Theorem. I am wondering how do we ensure this given that $M$ is determined by the plaintext of each message. Thanks! Mar 20, 2019 at 15:36