# 2048-bit RSA Decryption

If a message is encoded with 2048 bit RSA. The ciphertext is $M^e mod N$. In some cases, the message is short, $M \approx 10^{20}$. With a high probability, $M$ can be written as $M = ab$ with $a, b \leq 4\sqrt{M}$.

Can you explain to me how I can find the initial message $M$ given $N, e,$ and the ciphertext using a computation with no more than $\approx$ $4*10^{20}$ total operations?

I heard that there was some relation between small a's and b's and being able to do a trick.

• What is the point of deleting questions? If you do that, nobody else can benefit from it later on. Please consider posting your solution as an answer for future visitors. – Thomas Dec 11 '14 at 6:11
• I think that "operations" should be modular multiplications. $\;$ @Thomas: perhaps the poster realized that asking the (interesting) question was infringing some honor code? – fgrieu Dec 11 '14 at 12:42
• @fgrieu "problem solved" doesn't sound like breaking an honor code to me. Anyway, the question has been rolled back (thanks CodesInChaos). – Thomas Dec 11 '14 at 12:52
• Is there any particular problem with keeping the question, ABC? Maybe you could flag a mod instead. Note that any trusted user can roll back at any time. – Maarten Bodewes Jan 28 '15 at 23:19

So if $M \approx 10^{20}$, and you have $4 * 10^{20}$ operations, why not just bruteforce it?
For more efficient solution, consider meet-in-the-middle technique. For all $1 \le a \le 4\sqrt{M} \approx 10^{20}$, make a hash table with values $a^e \mod{N}$. Then for all $1 \le b \le 4\sqrt{M} \approx 10^{20}$ check if $M^e/b^e \mod{N}$ is in the table.
Indeed, $M^e / b^e \equiv (ab)^e / b^e \equiv a^e \pmod{N}$ so it should be in the table (of course b must be invertible, otherwise it contains a factor of N and you can simply factorize N).
So total number of operations is $\approx 8\sqrt{M}$.
• Right. Notice that if $e=2^{16}+1$, the cost of brute force is $\approx 17\cdot M$ modular multiplications; when the answer's algorithm uses about $17\cdot4\sqrt M$ in the first phase, and $k\cdot4\sqrt M$ in the second phase, for some $k$ depending on the modular inverse algorithm, certainly $k<2\log_2(N)=4096$, which is a huge improvement, trouncing the $4\cdot10^{20}$ asked in the question. $\;$ As an aside, we can simplify things slightly by merging the two phases: we can search for $(M^e)\cdot((a^e)^{-1})\bmod N$ in the table right after entering $a^e\bmod N$ in the table. – fgrieu Dec 12 '14 at 6:27