1
$\begingroup$

Are there attacks which will return the RSA private key when the attacker knows the public key, plain text, and cipher text when no padding is used in the RSA algorithm? If yes, what are the known attacks, under what conditions have they been successfully implemented, and what other cryptographically-secure asymmetrical encryption algorithms will produce identical cipher texts from the same plain text without the attacker being able to determine the private key through knowledge of the public key, the plain text, and the cipher text?

It is not important that the attacker knows the plain text or the cipher text because they will have access to that information along with the public key. What is important is that the private key can not be obtained and that the public-key encryption results of identical plain texts are the same.

For reference, the asymmetrical encryption usage is a subset of an algorithm which requires the characteristics specified above.

While there is a related question, there was no accepted answer and other responses to that question and similar questions caveat their answers with "when properly used", i.e., when RSA is implemented with padding: Finding Private key in RSA with public key, cipher text and plain text

$\endgroup$
1
$\begingroup$

No there is not.

First of all the key size needs to be bigger then the message otherwise RSA will not work

Remember one thing, if you have a public key you can have as many clear texts and cipher texts as you want. This is because everyone can use your public key to cipher a message. So if there was a method were by knowing the public key, clear text and cipher text you could discover the private key RSA would not be used. The question of whether the Padding is used or not is irrelevant. Knowing the public key you can cipher the messages using padding or no padding it is your choice. I am sure that in java you will have providers that implement RSA with no padding so you right now can get millions of clear texts and cipher texts from any public key.

Now why this can't happen:

$C^b = M\ mod\ N$

Being C the ciphertext, b the private key and M the clear text. Then you get

$b = \log_c M\ mod\ N$

And this is the problem. This is discrete log which is in NP. So you can't solve this in polynomial time even if you have infinite number of ciphertexts and clear texts

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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