# 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
• ϕ(5⋅13) = 48, it share with e = 3 with 2 factors 1 and 3, so they are not co-primes I think.
– Eric
Jan 4 at 8:47

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?
– thyu
May 6, 2022 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, 2022 at 2:52
• How to choose e first, just a random prime number ?
– Eric
Jan 4 at 8:53
• @Eric: actually, any arbitrary odd number $e > 1$ will work; you just need to make sure that, when you pick $p, q$, that $p-1, q-1$ is relatively prime to $e$. Now, a prime $e$ makes that test a bit easier (you just need to make sure that $p-1, q-1 \bmod e \ne 0$ ), but the corresponding test for composite $e$ wouldn't be that much work. In practice, we use a fixed $e$, often 65537, sometimes 3... Jan 4 at 14:17

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.

• @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
• 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