0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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 ♦
    Commented Feb 24, 2016 at 9:05
  • 5
    $\begingroup$ The ciphertext being small doesn't mean the plaintext was small... $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Feb 24, 2016 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 ♦
    Commented Feb 24, 2016 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 Vitor Lima Pereira
    Commented Feb 24, 2016 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 ♦
    Commented Mar 3, 2016 at 19:01

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Improve this answer
$\endgroup$
2
  • $\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 ♦
    Commented Feb 24, 2016 at 9:19
  • $\begingroup$ ... given that the encrypted message was not properly padded ... $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 3, 2016 at 18:57

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.