# Textbook RSA Attacks

Given textbook RSA encryption, if an attacker obtains the ciphertext and has the public key that was used, can he or she decrypt said ciphertext without calculating the private key?

• Depends on the ciphertext (and to some degree on the public exponent). – CodesInChaos Nov 14 '16 at 18:34
• ... And on the methods in use to post-process message data. – SEJPM Nov 14 '16 at 20:20
• Hint: assume the plaintext is known to be a name on the class's call roll. – fgrieu Nov 15 '16 at 7:51

No, in general. But since in textbook RSA you do not use pad, you can have an attack better than brute force (under some plausible conditions). Say $c=RSA_{e}(m)=m^{e}\pmod n$ and $N$ is the number of bits of the message $m$ (i.e. $m\approx 2^N$). With some ("large?") probability $m=m_1m_2$ and $m_1,m_2<2^{N/2}.$ So $c/m_1^{e}=m_2^{e}\pmod{n}.$ The idea is to construct two lists (in ${\bf Z}_n$) $$L_1 =\{c/1^{e},c/2^{e},c/3^{e},\dots,c/2^{eN/2}\}$$ $$L_2 = \{1^{e},2^{e},3^{e},\dots,2^{eN/2}\}$$ An element of the intersection, $c/a^{ei}=b^{je}$ provides $m_1=a^{i},m_2=b^{j},$ thus $m=a^{i}b^{j}.$ Since construction,sorting and finding the intersection takes $\tilde{O}(2^{N/2})$ time, you get a better time than brute force.

Now, if $m$ has 64-bit, you can experimentally see that with probability $\approx 1/4$ you get that $m=m_1m_2$ with $m_1,m_2<2^{32}.$ For larger messages this probability is smaller.

So, the answer to your question is that you can decrypt without knowing the private key, with some large probability if the message is small enough.

• So basically the only way in this situation is a brute force attack, or a chosen plaintext attack. Let's say the message can only use capital letters, broken up into 3 letter base 26 numbers, which seems like a common scheme for textbook RSA. That's only $26^3 = 17576$ possibilities. – Hydracronis Nov 15 '16 at 14:53