31
$\begingroup$

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

$\endgroup$
2
  • $\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, 2013 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, 2013 at 13:44

2 Answers 2

35
$\begingroup$

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.

$\endgroup$
3
  • 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, 2013 at 13:52
  • $\begingroup$ Can you explain why when e and phi(n) are relatively prime this doesn't happen? How does this happen in the first place? $\endgroup$
    – johan
    May 6 at 2:15
  • $\begingroup$ @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) $\endgroup$
    – poncho
    May 6 at 2:52
15
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ why was this answer downvoted? $\endgroup$
    – toogley
    Jul 9, 2016 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, 2016 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, 2017 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, 2017 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, 2019 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.