0
$\begingroup$

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!

$\endgroup$

marked as duplicate by otus, DrLecter, rath, D.W., e-sushi Jul 23 '14 at 23:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$

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