How to determine if padding has been used while encrypting a message with RSA?

Question

I am trying to decrypt a RSA encrypted text file. I have a 2048 bit public key. Analyzing the public key with openssl reveals the exponent used is 3.

openssl rsa -pubin -inform PEM -text -noout < publickey.pub

Public-Key: (2048 bit)

Modulus: [..snipped..]


Exponent: 3 (0x3)

After some googling, I found out that the text can be decrypted using e^th root attack, if message was not padded. Since attempts to decrypt message failed, I'm doubting my assumption that padding had not been used. Is there any way to know it for sure?

Answer 1

Given the public key and a single encrypted file, the only way to check is to take the integer $e$th root of the ciphertext and see if the resulting value "makes sense" (where whether or not it makes sense is very context specific to the application at hand).

If you have access to additional information you can figure it out.

Access to an encryption oracle
For example, if you have access to an encryption oracle, i.e., something that will encrypt whatever you send it. Since you know the exponent is $3$, just send it the plaintext $2$, if it returns $8$, you know it is unpadded.

More generally, you could have it encrypt the same plaintext twice and see if they are equivalent. This would work especially well if the plaintexts must be of a specific, but understood format where something like $2$ would be rejected.

Access to executable code
If you have access to the source code doing the encryption, you can reverse engineer it to figure out what it is doing.

Access to decryption oracle
Ask it to decrypt your ciphertext and see what the answer is. Then encrypt the resulting plaintext yourself with no padding.