RSA Implementation using Chinese Reminder Theorem(CRT) [PICO CTF Level2 Crypto]

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


Håstad’s Broadcast Attack [PICO CTF Level 3 Crypto]

The problem was called “Broadcast” and we got some big integer variables named e,c1,n1,c2,n2,c3,n3. However, I know that it is an RSA stuff but I didn’t understand how we could decrypt the message. At the first time, I tried to factorize the number using but I got nothing, the number is too big. When I went back to the problems page,  there was a hint said that this problem is about RSA attack on the small public exponent. I did my best on google and I found that this problem is about Håstad’s Broadcast Attack.

Read more