Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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