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.

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!

share|improve this question

marked as duplicate by otus, DrLecter, rath, D.W., e-sushi Jul 23 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  
Did you try the search here on crypto SE, e.g. for "RSA small exponent", before asking? –  DrLecter Jul 23 at 20:04

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

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