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
n = 0x90def3c2c91ae9bf6089ec8857960d567fdbcd7c2c3ea713046977231e65f44e1b91550971d4e5d43b51675fae4ba640add3af02dad4bf68c3ddef3a98907e1e01156de7a4474d9fce2ba8c055f44673c703a72a111a06f8a7b2fe582463938d802e91630e1e1b5483b1774e608eb4368c6bbf4da375319d9a2799bf8a5ae453

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
y = 0x17d7f90a4597fb2bbbb41d1a70f505f0d8c5cb53faaafea259150eb6910fb08fbf1ba40e42de70c596fb0032d132c9c6ce46c650999ad5f14a990d205984260146e2949b819dc8732beceed452701d88b2c8723b410fce739009df89930424c566af5102403981c26c3e75d9c62065a347e815b26984dcd3b5f02fc8a8092051

Solution