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

Improve this question
$\endgroup$
3
  • 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$
    – CodesInChaos
    Commented 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$
    – Gilles 'SO- stop being evil'
    Commented Dec 11, 2013 at 13:44
  • $\begingroup$ ϕ(5⋅13) = 48, it share with e = 3 with 2 factors 1 and 3, so they are not co-primes I think. $\endgroup$
    – Eric
    Commented Jan 4, 2023 at 8:47

2 Answers 2

Reset to default
37
$\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.

Improve this answer
$\endgroup$
5
  • 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
    Commented 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$
    – thyu
    Commented May 6, 2022 at 2:15
  • 1
    $\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
    Commented May 6, 2022 at 2:52
  • $\begingroup$ How to choose e first, just a random prime number ? $\endgroup$
    – Eric
    Commented Jan 4, 2023 at 8:53
  • 1
    $\begingroup$ @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... $\endgroup$
    – poncho
    Commented Jan 4, 2023 at 14:17
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ why was this answer downvoted? $\endgroup$
    – uuu
    Commented 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 ♦
    Commented 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
    Commented 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 ♦
    Commented 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
    Commented Mar 20, 2019 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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