# 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.

Without any additional knowledge? No.

The problem here is, that this understanding of security is wrong / too weak. Ciphertext-only attacks is the weakest kind of attack model, which is only relevant for classical ciphers any more.

To consider a cryptosystem secure today, it has to resist the much stronger attacks, most commonly the chosen-plaintext attacks and (in the case of public key crypto) chosen ciphertext attack. And on the other hand, we also don't require the attacker to decrypt the actual message. We consider the system broken if the attacker can distinguish messages already, for instance ciphertext indistinguishability.

... without calculating the private key?

If the attack goal would be decryption, the only known way is to break the private key. It is unknown, if the RSA problem and the factorization problem are equivalent or not. And if we had an algorithm which could decrypt but not calculate the private key, this question would be solved.

• 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
• I don't know where that example is from but any small number of possibilities is bad - and with a deterministic encryption scheme the attacker can just try them all. Textbook RSA is not IND-CPA, and it should never be used on its own. Usually the padding scheme OAEP is used with RSA encryption. And it's also quite common not to encrypt data with RSA directly - but to use hybrid encryption, where a random symmetric key is encrypted with RSA. – tylo Nov 15 '16 at 16:11