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.

Improve this question
$\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 ♦
    Commented 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$
    – dave_thompson_085
    Commented 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
    Commented Mar 14, 2016 at 8:45

1 Answer 1

Reset to default
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$
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
    Commented Nov 19, 2015 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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