# RSA: Find message (m) given that you know p,q, cp and cq where cp=m^dp mod p and cq = m^dq mod q

I have come across an RSA problem that goes like this:

You have $$p,q,cp,$$ and $$cq$$.

You know that

• $$cp = (m^{dp}) \bmod p$$ and
• $$cq = (m^{dq}) \bmod q$$

where

• $$dp = d \bmod(p-1)$$ and
• $$dq = d \bmod(q-1)$$.

With $$p$$ 1023-bit.

p  = 77521726407994312521574336297980709217530535587222058104143959969571660552797969474172937932738698506571416574103619966726945303225764903362666667915390994020563629603293171675938588115667633661770464872616447872544118726459248341421707592374348579901510230543653339835551959943115753367330314736507150772889
q  = 122043042610716803715485743054462817831797141151559626639660496010897753782905342871017865915858397385764743054519977321492994176452745910908749665987785423001182475295840889607694693125144689913443175241343223873981089261312260861004124800781256596427988822384724029792777632967012658639985349009210056116091
cp = 59541694220665015603506075680282236406328112807267216674188239193490851380911340890624190172062558224787860350672780489394061999335612457967049040181819906153599084668914230173111131906093647509390351820805346222543999428186721157360369017623698866284406487457004308459071130900275586148944902383219800200993
cq = 15281742228497214552346817366564582907638255619077531248069440760470985265165749879478383668076090388631632911972324378253632937895945694638171824766288669021780545670263807231637778601559768864667795718038562064859779318600228186879233482290716651865639425284629942145861317464254055008370322465189231689348


Now what I have found extremely hard about this is the lack of $$e$$.

I know I can find $$c$$ with $$c = \text{CRT}(cp,cq) \bmod n$$ so far and working on it, but from there I am stuck. $$\text{CRT}$$ is the Chinese Remainder Theorem.

c = 1234500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000054321


Numbers: https://pastebin.com/rP6ay1hG

Does anyone know how to find $$m$$? It has to be feasible in time (Aka not take months)

• @kelalaka It was posed as a question at a Computer Security course I attended. Never managed to solve it though. Nov 13, 2020 at 16:11
• I have not managed to find this question anywhere to be honest and am pretty stuck. Yes, that is the whole question. (Of course, provided p,q,cp and cq are actual numbers, not just theoretic. (So a small amount of bruteforce would work, but nothing above 2-3hrs) Nov 13, 2020 at 16:17
• pastebin.com/rP6ay1hG Nov 13, 2020 at 16:21
• My hint when reading the question was to try various values of $e$ (not those you listed: $3$ and $5$ are incompatible with your $p$, $q$, and there are other common values including $17=2^{(2^2)}+1$, $257=2^{(2^3)}+1$, $37$), compute $m$, and submit it to some automated referee. But now that I have seen the actual problem statement: "Find the value of the message $m$ given the two CRT decryption shares $cp=m^{dp}\bmod p$ and $cq=m^{dq}\bmod q$", all that remains to do is understand the context and fix the extremely misleading notation used.
– fgrieu
Nov 13, 2020 at 21:11
• Yes that's my best explanation. The statement makes it clear that $cp=m^{dp}\bmod p$ and $cq=m^{dq}\bmod q$ are used for decryption, thus $m$ there is the ciphertext. And it's asked the plaintext, which is the $c$ that you computed, and for some reason is also named $m$ in the statement. Perhaps the person thought $cp=c^{dp}\bmod p$ and $cq=c^{dq}\bmod q$ and mistyped (that just happened to me!), or wanted to make the problem harder, or mimic the tragic reality where errors creep everywhere (including exams and standards), who knows.
– fgrieu
Nov 13, 2020 at 21:46