This problem looked like an usual RSA problem until i found there was no e on that. What?? As a noob, i got confused at the first time since i couldn’t find the e, there was also two variables named dp and dq which i didn’t know what it means. I did a little google and found that it is just an RSA practical implementation using CRT that you can find here. Ok, we just need to look at those magical formula and do programming.

import gmpy2
c= gmpy2.mpz('95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885')
p = gmpy2.mpz('11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243')
q = gmpy2.mpz('12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629')
dp = gmpy2.mpz('8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961')
dq = gmpy2.mpz('3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659')
qinv = gmpy2.powmod(q,-1,p)
m1 = gmpy2.powmod(c,dp,p)
m2 = gmpy2.powmod(c,dq,q)
h = (qinv*(m1-m2))%p
m = m2+h*q
import binascii
print binascii.unhexlify(gmpy2.digits(m,16))

Run the script and we got the flag.
Flag : Theres_more_than_one_way_to_RSA


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s