# Textbook RSA with exponent e=3 [duplicate]

I remember $e=3$ is a bad choice for textbook RSA. But I can't really recall why. What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt{c}$? Why can't I do that with bigger $e$s? Is it possible to retrieve $d$, $p$ or $q$?

I remember that we had something with the Chinese Remainder Theorem (CRT), but when I look at it now, I does not seem to make any sense.

I'm thankful for fast responses!

• Did you try the search here on crypto SE, e.g. for "RSA small exponent", before asking? – DrLecter Jul 23 '14 at 20:04

What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt{c}$?
Yes, if the plaintext message is smaller than $\sqrt{N}$, then yes, a simple computation of $\sqrt{C}$ will recover the original message.
Why can't I do that with bigger $e$'s?
Actually, you could... as long as the plaintext message is smaller than $\sqrt[e]{N}$. However, if you actually consider that for, say, $e=65537$, well, that value turns out (for any sane value of $N$) to be less than 2; hence that could be used only if the plaintext message was either 0 or 1 (and if that's the case, well, the problem would be pretty easy anyways).
Is it possible to retrieve $d$, $p$ or $q$?
No, it's not. If it were, well, that'd give an easy way to factor the modulus (!), even if we were using RSA properly. All the attacker would need to do is take the modulus, and pretend that he was using textbook RSA and $e=3$; he would generate messages his own of his own choosing, encrypt those messages (using plaintext RSA and an $e=3$), and use the technique to recover $d$, $p$ or $q$. Any of the three is enough to factor the modulus.