zh3r0 CTF-Are you the Master? 2 Official Write-up

Master 2 is more like a Math problem than a RSA problem.

So you are given 3 files. 2 from challenge and 1 from Google Drive.

From python file:

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from key import pt
p=getPrime(1024)
q=getPrime(1024)
x=getPrime(1024)
y=getPrime(1024)
n1=p*q
n2=x*y
e=65537
ct1=pow(pt,e,n1)
ct2=pow(pt,e,n2)
ootp=”N1 : “+str(n1)+”\nN2 : “+str(n2)+”\nE : 65537\nct1 : “+str(ct1)+”\nct2 : “+str(ct2)
aaa=”p+q+r+s: “+str(p+q+r+s)+”\n(p-q)-(x-y): “+str((p-q)-(x-y))
red=open(“RSA.txt”,”w”)
red.write(ootp)
red.close()
red=open(“prxy.txt”,”w”)
red.write(aaa)
red.close()

We got to know that it is made up of 4 primes and n1=p*q|n2=x*y

Now lets get to making script

n1 = 12417127080422815737857829178789430387283644656796286644007190181275233038254982650900520208444570033944895679971951177467573644862800675887334791773359856548963510883567782247183009990733340366515218860231712518296231805253324709898640633155086183815927550133617562353243937514697745005568701059532650134387938324758897250094164121081436717576172349562189353547255742022806306628952658668123205041188480195366849528415075164756192945905158788561605088805110011605401289098591967818721785957410628314905762182529466041792601801094942412062721024595217699250282503561387690942463365022141266614422371304745947051066911
n2 = 13535742671170343194649874173445485003326954678704056429640294829224266409224232171669448606741290104143837444968157218953588036492336055641208728870300040922937631422614960829636268967870984021444065500833099886484031433400395173560484969029637105065058222908335510602204222935794203521997891554881452372380306145071165640328082610889602712719130949436394915102917587068497410741572114811122786488523349899125527219920591403522973523980874897487583741525542325853756358317440225706520923430697121297492167491992231025785528653319733872313411135278109820094900710129215353037113925434816021050732043191473976761644041
e = 65537
ct = 3776478243125222658515594635416338601627622074381925747470047865965623614236065341693278202724655814789048471523954172003395524166507583326259250957544858846929239564248292316635638398557784195461238822667662560834324258193103655795748902328797091392483535364256029591727235692999622720632986889258592903607027869408557025837341680731133831338187240101119708022782009249576510526966551941049438189519877273072953206086848387281968052298929142667413389464722377867077939780430741421774157426130552850296605612726411410208158788106389052244165013174051754347396411043231017624630314985276556512095367376194166983202656
#p+q+x+y
a = 461865358514192960434982980388049288328080532500468524967649213492976854354009981587975391303842169821869139144259614711715053619184463738325803100173566859332560510654710569094589524171402215115591813322237293103273306369558719284046155313287463229499747397470701965008926099021198426250727264745924621147722
#p+y-(q+x)
b = 72904645555375913591333808068681895072188978607726716983118482918641130003107637360771239343328911228636046234796389775690478441161899404683856843572593683704394524558615891086457573500744380638740361933791300531356267210630868457364050727161034745914546893554710104131439008766029508068850386010386259775806
#p+y
c=(a+b)/2
#q+x
d=(a-b)/2
#px+qy
aa=(c*d)-(n1+n2)
"""
Now its time for Math :P
n1*n2=p*q*x*y
so, we can write px as n1*n2
                       -----
                        q*y
so aa becomes:
aa = n1*n2 + q*y
     -----
      q*y
so cross multiplying it we get:
q*y*aa = n1*n2 + (q*y)^2
so
(q*y)^2 - q*y*aa + n1*n2
Now we have to solve quadratic equation
     
q*y = aa + √(aa^2) - 4*(n1*n2)
      ----------------------------
                2
I am taking q*y as qy
"""
qy = aa + (isqrt((aa**2)-(4*n1*n2)))
#q=HCF(n1,qy)
q = GCD(n1,qy)
p = n1//q
phin = (p-1)*(q-1)
d = inverse(e,phin)
print(long_to_bytes(pow(ct,d,n1)))

After running this we get the flag:

zh3r0{Th1s_1s_4_K3y_gfh}