The survey paper of Prof. Dan Boneh entitled "Twenty years of attacks on the RSA cryptosystem" mentioned that (Page 5) one can attack CRTRSA in square root of decryption exponent. However no argument is given. I know this comes from maninthemiddle attack. However I cannot understand the idea clearly. Is there any lecture notes/paper where this attack is clearly explained?
1 Answer
It's a good question, since it looks like Boneh's paper doesn't give a reference. It's not actually a maninthemiddle attack, at least not the attack I've seen. Instead, it's reminiscent of babystep giantstep but with an extra twist. Here's how it works.
Suppose we are given $N$ and $e$, where $N=pq$ with $p$ and $q$ distinct primes and $ed \equiv 1 \pmod{p1}$ with $0 < d < D^2$. We are not given $p$, $q$, or $d$, but we know the bound $D$. We want to factor $N$ in roughly $D$ steps (up to log factors). For what I'm about to do, we'll have to assume that the inverse of $e$ modulo $q1$ isn't $d$, and in fact isn't anything like $d$, but this assumption holds for CRT RSA.
For a random value of $x$, $\gcd(x^{ed}x,N)$ will be $p$ with good probability (this is where we need the assumption). If we write $d = a + bD$ with $0 \le a,b < D$, then $\gcd(x^{ea}x^{ebD}x,N)$ will be $p$, and in fact the gcd of $\prod_{i=0}^{D1} (x^{ei}x^{ebD}  x)$ and $N$ will also be $p$ with good probability. (Note that if the inverse of $e$ modulo $q1$ were of the form $i+bD$ with $0 \le i < D$, then this would fail since we would pick up a factor of $q$ in the product. This is what I meant by "anything like $d$" above.)
Now consider the polynomial $\prod_{i=0}^{D1} (x^{ei}y  x)$ in the variable $y$. In a number of steps nearly linear in $D$, we can compute this polynomial modulo $N$ and then we can evaluate it at any $D$ given points. (This requires special algorithms, since for example multiplying the factors one by one would require about $D^2$ operations. See Chapter 10 of von zur Gathen and Gerhard's book Modern Computer Algebra for background on fast evaluation and interpolation algorithms.)
Given these fast algorithms, the final steps are easy: we compute the polynomial, compute the $D$ evaluation points $y = x^{ebD}$ with $0 \le b < D$, compute the evaluations of the polynomial at these points, and take their gcds with $N$. All of this is nearly lineartime in $D$, and one of the gcds will give us the factor $p$.

1$\begingroup$ P.S. I did some looking around and was surprised at how hard it is to find a good reference. It's described on page 506 of Galbraith's book Mathematics of Public Key Cryptography, where it is attributed to Pinch. He gives a reference to a 2000 paper by Qiao and Lam, who cite a 1997 private communication from Pinch. I've got no idea whether this is the earliest occurrence in the literature. $\endgroup$ Jan 29, 2013 at 2:17

$\begingroup$ Thank you very much for such detailed explanation. Thank you again. $\endgroup$ Jan 29, 2013 at 2:51