# Attack on CRT-RSA

The survey paper of Prof. Dan Boneh entitled "Twenty years of attacks on the RSA cryptosystem" mentioned that (Page 5) one can attack CRT-RSA in square root of decryption exponent. However no argument is given. I know this comes from man-in-the-middle attack. However I cannot understand the idea clearly. Is there any lecture notes/paper where this attack is clearly explained?

-
You might have better luck at crypto.stackexchange.com –  Stopple Jan 29 '13 at 0:05

It's a good question, since it looks like Boneh's paper doesn't give a reference. It's not actually a man-in-the-middle attack, at least not the attack I've seen. Instead, it's reminiscent of baby-step giant-step 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{p-1}$ 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 $q-1$ 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}^{D-1} (x^{ei}x^{ebD} - x)$ and $N$ will also be $p$ with good probability. (Note that if the inverse of $e$ modulo $q-1$ 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}^{D-1} (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 linear-time in $D$, and one of the gcds will give us the factor $p$.

-
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. –  Henry Cohn Jan 29 '13 at 2:17
Thank you very much for such detailed explanation. Thank you again. –  user29295 Jan 29 '13 at 2:51