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

Katoptriss

2/6/23, 6:45 PM

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 ?

0 + 0

rsa

poncho

2/6/23, 7:03 PM

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...

Katoptriss

2/6/23, 7:08 PM

Sorry, I forgot to clarify about padding. There is none actually, the plaintext is only ~320 bytes long out of 512.

Score:3

Crypto

Daniel S

2/6/23, 6:57 PM

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}$.

0 + 0

Katoptriss

2/6/23, 7:11 PM

The encryption exponent indeed meets your criteria. I'll go check this method, then. Thank you !

kelalaka

2/6/23, 8:10 PM

I think this is a CTF/HW. Anyway, It should be rather $(t+2^{300}x) < N^{1/e}$

Daniel S

2/6/23, 8:42 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: RSA : กู้คืนไบต์ที่ขาดหายไปบางส่วนในข้อความธรรมดาที่เกือบสมบูรณ์

RO: RSA: recuperarea câțiva octeți lipsă într-un text simplu aproape complet

RU: RSA: восстановление нескольких недостающих байтов в почти полном открытом тексте

VI: RSA: khôi phục một vài byte bị thiếu trong một bản rõ gần như hoàn chỉnh

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.