Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
You might have better luck at crypto.stackexchange.com –  Stopple Jan 29 '13 at 0:05
add comment

1 Answer

up vote 10 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.