## Factoring RSA With CRT Optimization

Recover a RSA private key when an optimization goes wrong

When using RSA to perform a sign or decrypt operation, a common performance speedup is to use the Chinese Remainder Theorem to operate in the groups $Z/pZ$ and $Z/qZ$, rather than $Z/nZ$ (where $p*q = n$). Rather than computing $x^d \text{ mod } n$ the optimization is outlined below:

$\text{ Compute: } dp = e^{-1} \text{ mod } (p-1), dq = e^{-1} \text{ mod } (q-1), qinv = q^{-1} \text{ mod } p$

The RSA private key is now the tuple $(p, q, dp, dq, qinv)$ rather than the usual value of just $d$. Now, to compute a signature $y$ for message $x$, or perform a decrypt operation on $x$ we do the following:

$y_1 = x^{dp} \text{ mod } p, y_2 = x^{dq} \text{ mod } q, h = qinv * (y_1 - y_2) \text { mod } p$
$y = y_2 + h * q$

As recently highlighted in this paper, if the computation of $y1$ or $y2$ (but not both) fails, it is possible to recover a factor of $n$. Suppose we have the following RSA parameters:
e = 0x10001

We additionally know that a message $x$ was signed with these parameters, but that the failure mentioned above happened when computing the signature $y$. Recover the private exponent $d$, and submit $d \text{ mod } 1000000007$ given:
x = 0xdeadc0de