10
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

13
$\begingroup$

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

$\endgroup$
2
  • 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$
    – Henry Cohn
    Jan 29, 2013 at 2:17
  • $\begingroup$ Thank you very much for such detailed explanation. Thank you again. $\endgroup$
    – user29295
    Jan 29, 2013 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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