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

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?

• I don't see that the mentioned paper solves this problem or proposes to build such lists for another purpose. And this algorithm is much more costly that a competent method to factor $n$, since it has cost like $>N$ modular multiplications, thus $\>\sqrt n$ modular multiplications. Also, if the attack is able to explicitly compute the second list, then $m$ is known, hence the goal is not to break RSA per se, it's to factor $n$. So, is the question asking how the Baby-Step Giant-Step attack for RSA works? That usually assuming $m$ is small enough that $\sqrt m$ operations is tractable.
– fgrieu
Dec 30 '20 at 14:05

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