0
$\begingroup$

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.

|improve this question
$\endgroup$

closed as off-topic by user61539, e-sushi Nov 26 '18 at 10:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Do you possibly mean $x^e$ instead of $ê$? Hit ^ + space or switch to US keyboard layout to get it. $\endgroup$ – Maarten Bodewes♦ Nov 22 '18 at 4:58
1
$\begingroup$

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.

|improve this answer
$\endgroup$
1
$\begingroup$

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.
|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I've never heard any English speaker use 'imbricated'; the usual word for what I think you mean is 'nested' -- i.e. lower/inner loops each within a higher/outer one. (PS: except in COBOL. In COBOL this is quite ugly. But computer science people mostly ignore the existence of COBOL.) $\endgroup$ – dave_thompson_085 Nov 23 '18 at 6:30
  • 1
    $\begingroup$ @dave_thompson_085: you guessed it, I'm not a native English speaker. Yes, nested loops is the proper term for my "boucles imbriquées". $\endgroup$ – fgrieu Nov 23 '18 at 7:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.