brute force RSA [closed]

Question

I have a ciphertext c_t and a RSA public key pair (e, n). I also know that the encrypted message is a three-letter word in the following manner ... (a-z, a-z, a-z). Now I want to decrypt this ciphertext.

My thoughts are the following: I want to use bruteforce for decryption like this ...

if(c_t && c = (aaa)^e mod n)
if(c_t && c = (baa)^e mod n)
if(c_t && c = (caa)^e mod n)
//...
if(c_t && c = (zzz)^e mod n)
{
  //match: decrypted
}

My next idea is, that I use 3 loops (i, j, k) for this iterative process to check all possible combinations.

But I am not sure if there is a better way to decrypt such a tree-letter word.

Answer 1

Your approach will recover the plain text, and I believe it is the best way given the conditions. After all, this approach only requires 26^3 test encryption actions in the worst case. Encryption is the inexpensive operation in RSA -> m^e % n, e very frequently being 65537.

If the implementation was naive, this would be all you needed to recover the plain text. However, RSA typically uses a padding scheme and must do so in order to be secure. If the padding scheme is purely deterministic, you would simply run the same padding scheme on your test encryption each test. But if the padding scheme introduced any pseudo random bytes -- I don't know if such a scheme exists for RSA -- this could easily make recovery of the plain text virtually impossible.

Answer 2

The idea of trying all the plaintexts works when there are few enough and no randomized padding is used. This should never hold in practice (which uses RSAES-OAEP, RSAES-PKCS1-v1_5, or RSA-KEM).

If these conditions are met, trying all the plaintexts has the advantage of working even when $n$ is too large to be factored (for $n$ below perhaps a few dozen decimal digits, factorization of $n$ would probably be the fastest attack).

Some remarks on the code

• In computer science, repetitive tasks (like enumerating all 3-letter words) should not be accomplished by writing explicit code for each value. A simple alternative is 3 nested loops; there are others methods, making the number of letters a parameter.
• in RSA, computing $x^e\bmod n$ should not be performed by computing $x^e$ then reducing modulo $n$; that would be grossly inefficient. There are more efficient modular exponentiation techniques.