I have a RSA-4096 public key, a ciphertext, and almost the whole plaintext : there are only a couple dozens bytes missing near the end, or in other terms, I know the range 0-80% + 90-100% of the plaintext. Is there any way to recover those missing bytes ?

  • $\begingroup$ Is this textbook RSA, or did the encryptor use real (randomized) RSA encryption padding? If the latter, well, you're a bit out of luck... $\endgroup$
    – poncho
    Oct 6 at 19:03
  • $\begingroup$ Sorry, I forgot to clarify about padding. There is none actually, the plaintext is only ~320 bytes long out of 512. $\endgroup$
    – Katoptriss
    Oct 6 at 19:08

If the encryption exponent is less than one over the proportion of missing plaintext, then you can use Coppersmith's method.

For example, if you are missing bits 3300-3699 of the plaintext, let $t$ be the known plaintext with zeros in places 3300-3699 of the unknown. Then the plaintext is $t+2^{3300}x$ for some unknown number less than $2^{400}$ and the ciphertext is $c(x)=(t+2^{3300}x)^e\pmod N$ where $e$ is the encryption exponent. This can be solved if $x<N^{1/e}$.

  • $\begingroup$ The encryption exponent indeed meets your criteria. I'll go check this method, then. Thank you ! $\endgroup$
    – Katoptriss
    Oct 6 at 19:11
  • $\begingroup$ I think this is a CTF/HW. Anyway, It should be rather $(t+2^{300}x) < N^{1/e}$ $\endgroup$
    – kelalaka
    Oct 6 at 20:10
  • 1
    $\begingroup$ It is soluble if $|x|<N^{1/e}$, but if this is a CTF it’s probably best to leave that as one of many details to be worked out. $\endgroup$
    – Daniel S
    Oct 6 at 20:42

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.