1
$\begingroup$

Can someone explain to me (Or better yet, point me to a tool that does the brute forcing) how to crack a standard, simple RSA cipher (So don't bother with padding) if I know just one public key, the ciphertext, and some text that I know for sure is part of the plaintext?

Please don't point me to the Wikipedia article or something, I'm trying to get a simple explanation that is fully understandable.

$\endgroup$
3
  • 1
    $\begingroup$ Hint: if what you don't know about the plaintext is small enough, you can guess it, and check your guess. Other attacks might apply depending on parameters unstated in the question. $\endgroup$
    – fgrieu
    Nov 17, 2015 at 18:20
  • $\begingroup$ Unpadded RSA is simple, or at least simpler, but it is definitely NOT STANDARD because it is a Very Bad Idea to use it for anything, ever. $\endgroup$ Nov 19, 2015 at 21:01
  • $\begingroup$ Depending on the situation you might also have e=3 and without padding you might then be able to decrypt the ciphertext by simply taking the cube root. $\endgroup$
    – Blub
    Mar 14, 2016 at 8:45

1 Answer 1

1
$\begingroup$

Running RSA backwards would imply cracking the key (determining the private key) and you could brute force that by factoring. You could generate all possible prime's of the requisite size until you could generate the known public key. Or perhaps there are other approaches that are more mathematical, that could factor for the primes, which would also be a form of brute force, as currently factoring is thought to be a NP-hard problem.

$\endgroup$
1
  • $\begingroup$ (The decision version of) integer factorisation is believed to not be NP-hard (which is not the same thing as being in NP). $\endgroup$
    – fkraiem
    Nov 19, 2015 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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