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$
  • 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 '15 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$ – dave_thompson_085 Nov 19 '15 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 '16 at 8:45
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.

| improve this answer | |
$\endgroup$
  • $\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 '15 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.