Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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[3]{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!
What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt[3]{c}$?
Yes, if the plaintext message is smaller than $\sqrt[3]{N}$, then yes, a simple computation of $\sqrt[3]{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.
