How weak rsa key is decrypted?

Question

I want to know how weak rsa that have e=3 can be decrypted easily.How can it be possible? I also want a python or ruby script that decrypt such encryption.Thanks a lot.

Answer 1

The RSA key needn't be weak for this attack. What you need is a message m whose value m^3 is smaller than the public modulus (N) for the key. When the m^3 value is smaller than N, taking (m^3) % N gives you (m^3), at which point an attacker can take the cube root of the "encrypted" message to recover the plaintext.

This is usually the result of using "textbook RSA" rather than a modern implementation. (Modern implementations pad the message to ensure this never happens.)

There's a detailed description of the math over on crypto.se.