# How to decrypt RSA if ciphertext is less than the modulus and e=3?

I'm given a public key. Using openssl rsa ..... I got the public key has the exponent as 3. When I calculated the size of the ciphertext, it is 8 bits smaller than the 2048-bit modulus.

How can I decrypt RSA provided I only have public key and ciphertext?

Let me know if you want the files.

• Hint: if $x$ is small enough that $(x^e\bmod N)=x^e$, then you can find $x$ from $x^e\bmod N$ with the sole knowledge of $e$. – fgrieu Feb 24 '16 at 9:05
• The ciphertext being small doesn't mean the plaintext was small... – Hilder Vitor Lima Pereira Feb 24 '16 at 9:30
• @Vitor: absolutely; that's why my hint starts with "if", and for proper use of RSA the odds of the condition that follows are negligible. On the other hand, a noticeable fraction of exercises on RSA with $e=3$ involve exponentiation of something below 16% of the cubic root of the modulus. – fgrieu Feb 24 '16 at 10:30
• I understand you. Well, by the way, @Mahesh the ciphertext has 8 bits or 2040 bits (which is what I understand by "8 bits smaller than the 2048-bit modulus") – Hilder Vitor Lima Pereira Feb 24 '16 at 12:10
• @Vitor if the ciphertext is only 8 bits then the message is either the number 5 or 6 ... that sounds a bit too simple for a crypto challenge :P – Maarten Bodewes Mar 3 '16 at 19:01

## 1 Answer

"How can I decrypt RSA provided I only have public key and ciphertext?"

You break e=3 RSA. ​ (See pages 393 to 396.)

• I can't find how the linked pages relate to solving the question (I only see how it could help prove that what's asked is infeasible). – fgrieu Feb 24 '16 at 9:19
• ... given that the encrypted message was not properly padded ... – Maarten Bodewes Mar 3 '16 at 18:57