# In RSA, why is it important choosing 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*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 lets 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. –  CodesInChaos Dec 11 '13 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. –  Gilles Dec 11 '13 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.

-
Your last paragraph only works for prime $e$. –  CodesInChaos Dec 11 '13 at 8:40
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 '13 at 13:52
@CodesInChaos: doh! I knew that; however since I personally use prime $e$, it slipped my mind... –  poncho Dec 11 '13 at 14:12

RSA encryption and decryption is built upon Fermat's theorem which says: $a^{\phi(n)} = 1 \mod(n)$, and since $p$ and $q$ are primes: $\phi(p*q) = (p-1)*(q-1)$.

If we have message $M$ and private key $d$ and public pair $e$…

Encryption: $C = M^e (\mod n)$
Decryption: $C^d \mod(n)$ which most be the same as $M$

Now, $C^d = (M^e)^d = M^{(ed)} \mod(n)$. Since $ed = 1 \mod \phi(n)$, we may write $K*\phi(n) = ed - 1$ for some integer $k$ which renders it to $ed = k*\phi(n) + 1$.

Now $M^{(ed)} = M^{(\phi(n) + 1 )} = M*M^{(phi(n))} \mod(n)$, and since $M^{(\phi(n))} = 1 \mod(n)$ the result becomes $M$ the message again.

So, without the fact that $ed=1 \mod(\phi(n))$ we wont get $M$ back.

-