# RSA private key?

I recently solved a stage in a challenge where I received 5 very large integers with character labels. I think they are components of an RSA key but I am a nooby to crypto and not sure.

I have p, q, dp, dq and c. Any help would be appreciated.

• Looks like RSA CRT; you have everything for last line of step 1 then step 2 here. – fgrieu Mar 11 '18 at 14:57
• @fgrieu Any tools to perform those calculations? I can't get my computer to accurately compute qinv, it keeps rounding 1/q to 0 – DesertSands Mar 11 '18 at 15:28
• Look at Sage <sagemath.org> – user94293 Mar 11 '18 at 15:48

I can't get my computer to accurately compute qinv, it keeps rounding $1/q$ to 0

This is because you are using real-valued division. You want $q_{\mathit{inv}}=q^{-1}\bmod p$, i.e. the integer $q_{\mathit{inv}}$ such that $q\cdot q_{\mathit{inv}}\bmod p=1$. If you are using sagemath, then you can use the built-in inverse_mod(q,p) function to make the above computation.

I think they are components of an RSA key but I am a nooby to crypto and not sure. I have p, q, dp, dq and c.

As pointed out by fgrieu in the comments, this resource details how to decrypt, given these values, as you are in the last line of the first step. I shall reproduce the (computationally relevant) contents for your convenience.

1. Compute $q_{\mathit{inv}}=(1/q)=q^{-1}\bmod p$, e.g. using inverse_mod
2. Compute $m_1=c^{d_p}\bmod p$, e.g. using pow(c,dp,p)
3. Compute $m_2=c^{d_q}\bmod q$
4. Compute $h=q_{\mathit{inv}}\cdot (m_1-m_2)\bmod p$
5. Recover $m=m_2+h\cdot q$
• @DesertSands Note the $dp$ and $dq$ are redundant, you can get message $m$ just with knowing $p$, $q$, public exponent $e$ and cipher $c$. For this first compute $\phi = (p-1)(q-1)$, and then compute $d$ by $d = e^{-1} \pmod \phi$ and then $m = c ^{d} \pmod n$, whete $n = pq$. – Lisbeth Mar 21 '18 at 9:58