0
$\begingroup$

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.

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

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$
| improve this answer | |
$\endgroup$
  • $\begingroup$ @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$. $\endgroup$ – Lisbeth Mar 21 '18 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.