How can we say there is absolute collision in Baby-Step Giant-Step attack for RSA?

Question

According to this paper, there is a Baby-Step Giant-Step attack for RSA encryption.

Consider the following Baby Step, Giant Step attack on RSA, with public modulus $n$. Eve knows a plaintext $m$ and $a$ ciphertext $c$. She chooses $N^2 ≥ n$ and makes two lists:

The first list is $c^j$ (mod n) for 0 ≤ j < N.

The second list is $m.c^{−Nk}$ (mod n) for $ 0 ≤ k < N $.

The mentioned paper solves this problem by the collision of these two lists.

But how can we say there's a absolute collision in these two lists?

Answer 1

But how can we say there's a absolute collision in these two lists?

Well, we know that $c^d \equiv m$ for some value $d < n$, because of this, we have $d = Nk + j$ for some pair of integers $0 \le j < N$ and $0 \le k < N$. We see that $c^j$ will appear somewhere in the first list, and $m \cdot c^{-Nk}$ will appear somewhere in the second list.

Since $c^{Nk + j} = m$, rearranging terms, we have $c^j = m \cdot c^{-Nk}$, and so those two terms will be the same.

That said, this is not a practical attack against RSA (and Coron et al never claimed it was). The attack takes $O(\sqrt n)$ time, making it no more efficient than brute force factoring (and there are plenty of more efficient ways to break RSA than that).