1
$\begingroup$

Can Coppersmith's method be used to break RSA when we only have access to public key and one ciphertext? For e.g. suppose we have N and ciphertext c both are 1024-bit numbers and the public exponent e = 5. Armed with only this information can we use Coppersmith's method to decrypt c? In all the literature that I have come across regarding this topic, either some part of plaintext is known or some bits of private key are known. But if none of this is available, is it possible to decrypt c using Coppersmith's method? If not, is there any other way to solve such a problem? References that I went through: https://www.cis.upenn.edu/~cis556/lattices.pdf https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf

$\endgroup$
1
$\begingroup$

If you only know the ciphertext and the public key, you should not be able to do anything, since RSA is intended to be used that way.

However, here are some leads which may help you to recover your message (since $e$ is low):

  • If the same message (with the same padding!) have been sent to $e$ different people (hence encrypted with $e$ different public key), you can recover the message using the Chinese Remainder Theroem. This is known as Hastad's broadcast attack.
  • If the message is short and not padded, you may be able to recover the message simply by taking the $e^{th}$ root of the ciphertext. Note that it can only work if $m^e < n$.

In a more general way, I invite you to take a look at Dan Boneh's "Twenty Years of Attacks on the RSA Cryptosystem" namely the section about low public exponent.

$\endgroup$

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.