# RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$

Suppose for a RSA system I have the following variables given:
modulus $$n$$, expononent $$e$$, $$d_p$$ and $$d_q$$

Where, $$d_p = d\bmod(p-1)$$ and $$d_q = d\bmod(q-1)$$,

Is it possible to find the private exponent $$d$$ ?

Note: $$p$$, $$q$$, $$p-1$$ and $$q-1$$ are not known

• Hint: it holds that $e\,d_p\equiv1\bmod(p-1)$. – fgrieu Apr 14 at 7:07
• I understand that, but I can't figure out where to use it – TheBlueFlame121 Apr 14 at 7:17
• Thank you, I finally got the solution. I iterated k over the range or e and the checking condition was as follows : math.gcd(65537, p1) == 1 and isprime(p1+1) == True and n % (p1+1) == 0 – TheBlueFlame121 Apr 14 at 9:36
• That method works fine in the small $e$ case, For large $e$, you could compute $\gcd( r^{e \cdot d_p} - r, n)$ for random $r$, this is (with good probability) $p$. – poncho Apr 14 at 12:51
• @poncho: you should make an answer with that one, it is much cleaner, and I had missed it. – fgrieu Apr 14 at 13:27