Writeup from noxCTF’18

noxCTF 2018: Chop-Suey

Category: Crypto
Challenge Points: 118
Solves: 235
Description:

Today I ate in a Chinese restaurant and got myself a fortune cookie. These things usually contain a note with a nice sentence or phrase, but mine had numbers in it instead! Can you help me find the meaning of the numbers?

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

So if you have learned Chinese Remainder Theorem, you would definitely have known this optimisation technique for RSA.
It states:
dp = d (mod p-1)
dq = d (mod q-1)
This technique is more faster than the Textbook RSA and with out p and q, you’d be having a really tough time. Just take a glimpse into what Wiki#Using_the_Chinese_remainder_algorithm) has to say.
But for the funny part, they have already provided us with p and q values! We can easily recompute qinv, to get the flag.

To construct qinv,

qinv = modinv(q, p)
m2 = pow(c, dq, q)
m1 = pow(c, dp, p)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q

The complete script:

from gmpy2 import *

p=8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229

q=12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469

dp=6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929

dq=783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041

c=24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

qinv = modinv(q, p)
m2 = pow(c, dq, q)
m1 = pow(c, dp, p)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q
print(m)

txt = hex(m)[2:]
print ''.join([chr(int(''.join(c), 16)) for c in zip(txt[0::2],txt[1::2])])

Flag

noxCTF{W31c0m3_70_Ch1n470wn}