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.

  • $\begingroup$ 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. $\endgroup$ – Thomas Dec 11 '14 at 6:11
  • $\begingroup$ I think that "operations" should be modular multiplications. $\;$ @Thomas: perhaps the poster realized that asking the (interesting) question was infringing some honor code? $\endgroup$ – fgrieu Dec 11 '14 at 12:42
  • $\begingroup$ @fgrieu "problem solved" doesn't sound like breaking an honor code to me. Anyway, the question has been rolled back (thanks CodesInChaos). $\endgroup$ – Thomas Dec 11 '14 at 12:52
  • $\begingroup$ 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. $\endgroup$ – 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}$.

  • $\begingroup$ 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. $\endgroup$ – fgrieu Dec 12 '14 at 6:27

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.