Attack on CRT-RSA - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:54:20Z http://mathoverflow.net/feeds/question/120160 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120160/attack-on-crt-rsa Attack on CRT-RSA unknown (google) 2013-01-28T23:26:39Z 2013-01-29T01:50:35Z <p>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? </p> http://mathoverflow.net/questions/120160/attack-on-crt-rsa/120166#120166 Answer by Henry Cohn for Attack on CRT-RSA Henry Cohn 2013-01-29T01:50:35Z 2013-01-29T01:50:35Z <p>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.</p> <p>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 &lt; d &lt; 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.</p> <p>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 &lt; 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 &lt; 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.)</p> <p>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.)</p> <p>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 &lt; 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>