A pointer in the terms of programming is a variable contains an address that points to another address in the memory. When I was in my first semester, a pointer is a thing that takes time for me to understand. However, once I got the point I also found that pointer is so powerful. Pointer itself is literally a variable, it contains an address to another location in the memory where we stored other variables, pointers are so powerful because it points directly to the address so we can access the address and manipulate its value in the memory. Since we manipulate value directly in the memory it will reduce the length of our code and the program execution time.
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
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 factordb.com 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.