9

Let $$d_p = d~\mathrm{mod}~(p−1)$$ and $$d_q = d~\mathrm{mod}~(q−1).$$

Given $d_p$, $d_q$, $p$ and $q$, how can I reconstruct $d$?

Aleph
  • 1,816
  • 18
  • 23
Bennett Yardley
  • 91
  • 1
  • 3
  • 1
    You can use the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Case_of_two_moduli) (that's why parameters in this form are called CRT parameters) – puzzlepalace Apr 12 '17 at 02:01
  • 2
    And if what you really want is to decrypt, you don't need d at all, just use the CRT-based algorithm given in PKCS1 and Wikipedia, which is much more efficient; that's the _reason_ RSA keys usually _have_ CRT parameters although usually they have q^{-1} mod p also. – dave_thompson_085 Apr 12 '17 at 03:45

2 Answers2

6

If you happen to know also $e$ then you can use the formula

$$d = d_p + d_q - e\cdot d_p\cdot d_q \quad\bmod (p-1)\cdot(q-1).$$

Instead of modulo $\varphi(p\cdot q) = (p-1)\cdot(q-1)$ you can also calculate the result modulo the least common multiple of $p-1$ and $q-1$.

PS: I do not understand the downvote(s) for the question. When generating an RSA key one usually first finds $p, q, d_p, d_q$ (and maybe $p^{-1}\bmod q)$ given $e$. If one uses the private key on an embedded device that is susceptible to fault attacks like the Bellcore attack, one might prefer to refrain from using the CRT despite the performance advantages.

itsme
  • 61
  • 1
  • Just as an aside related to your `I do not understand the downvote(s) for the question.` — Any downvotes the Q initially received most probably originated in the fact that its original form, the Q included ciphertext and practically asked how to crack a potentially ongoing CTF task. Meanwhile, things were edited and some issues resolved. But it might explain why the Q wasn't well-received at first by some of our users. Anyway, it shows a score of $2$ (with $0$ downvotes) right now… so the Q definitely managed to recover. ;) – e-sushi Apr 13 '17 at 17:10
0

Check The Chinese Reminder Theorem.

Is pretty easy.

https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm

they give you all you need, including DP and DQ, the only think you would have to calculate is qinv where you can use python gmpy and the function gmpy.invert(e,phi).

GoyMan
  • 9
  • 1