2
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2015 at 23:19

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\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, 2014 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.