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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Looks like RSA CRT; you have everything for last line of step 1 then step 2 here. $\endgroup$– fgrieu ♦Mar 11, 2018 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$– DesertSandsMar 11, 2018 at 15:28
-
$\begingroup$ Look at Sage <sagemath.org> $\endgroup$– user94293Mar 11, 2018 at 15:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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, dqandc.
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.
- Compute $q_{\mathit{inv}}=(1/q)=q^{-1}\bmod p$, e.g. using
inverse_mod - Compute $m_1=c^{d_p}\bmod p$, e.g. using
pow(c,dp,p) - Compute $m_2=c^{d_q}\bmod q$
- Compute $h=q_{\mathit{inv}}\cdot (m_1-m_2)\bmod p$
- Recover $m=m_2+h\cdot q$
-
$\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$– LisbethMar 21, 2018 at 9:58