Basic Math

Kita diberikan dua file, yakni chall.py dan output.txt.

chall.py

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from flag import FLAG
from math import gcd

key = RSA.generate(2048)
p = key.p
q = key.q
n = key.n
e = key.e
phi = (p - 1) * (q - 1)

_ = q * (n - (p + q) + 1)

pt = bytes_to_long(FLAG)
c = pow(pt, e, n)

with open("output.txt", "w") as f:
    f.write(f"c={c}\n")
    f.write(f"n={n}\n")
    f.write(f"_={_}\n")

output.txt

c=11665601060578904089239843410225375694820409159682646249179665252868538140942592308238001634946015207806182773645946514639330174073596963565398520984052812107864649042722601501632527387908205197544384349913254159008138197292136321258764747423486946823235609128957524452960014865843501039521715215870481409233163822644173905779182369294926574074559860993002680341523344760620344945438597058952297301238786668292187474586927204408094376608063862929071392549106291260554379095737404811174829081624290601025873096893989889282638926503683027576448053817103472391567044397645990604427817477319552748352542310624328971111224
n=20745373907683254825049290479805022577698417756745553065502184542440290698675636611211421768628978558536798632884593780484089228918687940040784362096583885762918444510182091023737128509040813180764229301253403461950991005763724240539347285983746713529429194017968452490924072330045377883194031624546110908624207975197728193864733998735366182116283389761918556904685848874101378924898558207815806672111491676015870193395402827343682606599678263521198825549391621181707164197806471775556954603164376754177030602270124987837166089116699351375651725762442815795419402069377433601213536237573445200548516577224983154385131
_=3008402167498686489658046584687250894054805283581595585910627461718404505357580519988257478154170723732195801598192620002626334174481830535485128278276511858099424631496543061198774072622958637733862789870333290644285980870181665552312286278897680441753106657293626554905420259982375733657176710899917039859895817850089768953028685172911328610240422458044543030626862422759694259734614534705301930280236678366230779802305105972029619231686586980300303046553978920455130556261232110533615116834947668222123916762076470140319035627450247512567064155652636242372945159083886013654433917733912881775893574733186600603947663871285527018487051507837543317898530428326302145470131080870627284805693249892024593858399145837368527441729384247075765654298702328429025268308202019015461840160295361403772376945443406115341340052412259293257561437435810602586966870673570323646951094860378389988561936472503866618300378850460619556867200

Melihat dari source code, diketahui bahwa _ memiliki faktor q, begitu pula dengan n. Maka dari itu, GCD(_,n) = q. Berikut adalah kode solvernya.

solve.py

from Crypto.Util.number import *

c = 11665601060578904089239843410225375694820409159682646249179665252868538140942592308238001634946015207806182773645946514639330174073596963565398520984052812107864649042722601501632527387908205197544384349913254159008138197292136321258764747423486946823235609128957524452960014865843501039521715215870481409233163822644173905779182369294926574074559860993002680341523344760620344945438597058952297301238786668292187474586927204408094376608063862929071392549106291260554379095737404811174829081624290601025873096893989889282638926503683027576448053817103472391567044397645990604427817477319552748352542310624328971111224
n = 20745373907683254825049290479805022577698417756745553065502184542440290698675636611211421768628978558536798632884593780484089228918687940040784362096583885762918444510182091023737128509040813180764229301253403461950991005763724240539347285983746713529429194017968452490924072330045377883194031624546110908624207975197728193864733998735366182116283389761918556904685848874101378924898558207815806672111491676015870193395402827343682606599678263521198825549391621181707164197806471775556954603164376754177030602270124987837166089116699351375651725762442815795419402069377433601213536237573445200548516577224983154385131
_ = 3008402167498686489658046584687250894054805283581595585910627461718404505357580519988257478154170723732195801598192620002626334174481830535485128278276511858099424631496543061198774072622958637733862789870333290644285980870181665552312286278897680441753106657293626554905420259982375733657176710899917039859895817850089768953028685172911328610240422458044543030626862422759694259734614534705301930280236678366230779802305105972029619231686586980300303046553978920455130556261232110533615116834947668222123916762076470140319035627450247512567064155652636242372945159083886013654433917733912881775893574733186600603947663871285527018487051507837543317898530428326302145470131080870627284805693249892024593858399145837368527441729384247075765654298702328429025268308202019015461840160295361403772376945443406115341340052412259293257561437435810602586966870673570323646951094860378389988561936472503866618300378850460619556867200

q = GCD(n, _)
p = n // q
e = 65537

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c,d,n)
print(long_to_bytes(m))

Flag: RECURSION{j4ng4n_k3sering4n_b0l0s_j4m_p3l4j4r4n_MTK}