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

  • $\begingroup$ 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. $\endgroup$ Dec 11 '13 at 8:38
  • 4
    $\begingroup$ $e=65537$ also requires a good padding scheme. It makes some of the attacks against badly padded RSA harder but not all of them. $\endgroup$ 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.

  • 3
    $\begingroup$ 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$. $\endgroup$
    – tylo
    Dec 11 '13 at 13: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.

  • $\begingroup$ why was this answer downvoted? $\endgroup$
    – toogley
    Jul 9 '16 at 13:40
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes
    Dec 24 '16 at 1:34
  • $\begingroup$ @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). $\endgroup$
    – desowin
    Sep 25 '17 at 16:51
  • $\begingroup$ 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 :) $\endgroup$
    – Maarten Bodewes
    Sep 25 '17 at 18:42
  • $\begingroup$ 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! $\endgroup$
    – David Chen
    Mar 20 '19 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.