I'm given a public key. Using openssl rsa ..... I got the public key has the exponent as 3. When I calculated the size of the ciphertext, it is 8 bits smaller than the 2048-bit modulus.

How can I decrypt RSA provided I only have public key and ciphertext?

Let me know if you want the files.

  • $\begingroup$ Hint: if $x$ is small enough that $(x^e\bmod N)=x^e$, then you can find $x$ from $x^e\bmod N$ with the sole knowledge of $e$. $\endgroup$ – fgrieu Feb 24 '16 at 9:05
  • 5
    $\begingroup$ The ciphertext being small doesn't mean the plaintext was small... $\endgroup$ – Hilder Vítor Lima Pereira Feb 24 '16 at 9:30
  • 1
    $\begingroup$ @Vitor: absolutely; that's why my hint starts with "if", and for proper use of RSA the odds of the condition that follows are negligible. On the other hand, a noticeable fraction of exercises on RSA with $e=3$ involve exponentiation of something below 16% of the cubic root of the modulus. $\endgroup$ – fgrieu Feb 24 '16 at 10:30
  • $\begingroup$ I understand you. Well, by the way, @Mahesh the ciphertext has 8 bits or 2040 bits (which is what I understand by "8 bits smaller than the 2048-bit modulus") $\endgroup$ – Hilder Vítor Lima Pereira Feb 24 '16 at 12:10
  • $\begingroup$ @Vitor if the ciphertext is only 8 bits then the message is either the number 5 or 6 ... that sounds a bit too simple for a crypto challenge :P $\endgroup$ – Maarten Bodewes Mar 3 '16 at 19:01

"How can I decrypt RSA provided I only have public key and ciphertext?"

You break e=3 RSA. ​ (See pages 393 to 396.)

  • $\begingroup$ I can't find how the linked pages relate to solving the question (I only see how it could help prove that what's asked is infeasible). $\endgroup$ – fgrieu Feb 24 '16 at 9:19
  • $\begingroup$ ... given that the encrypted message was not properly padded ... $\endgroup$ – Maarten Bodewes Mar 3 '16 at 18:57

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.