0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Dec 30 '20 at 14:05
3
$\begingroup$

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

$\endgroup$

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.