# RSA : recovering a few missing bytes in an almost complete plaintext

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 ?

• 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... Oct 6 at 19:03
• Sorry, I forgot to clarify about padding. There is none actually, the plaintext is only ~320 bytes long out of 512. Oct 6 at 19:08

## 1 Answer

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.

• The encryption exponent indeed meets your criteria. I'll go check this method, then. Thank you ! Oct 6 at 19:11
• I think this is a CTF/HW. Anyway, It should be rather $(t+2^{300}x) < N^{1/e}$ Oct 6 at 20:10
• 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. Oct 6 at 20:42