easy-rsa - pingCTF 2023

Challenge:

from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long

p = getPrime(2048)
q = getPrime(2048)
n = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))
flag = open("flag.txt","rb").read()

print(f"q & p = {q & p}")
print(f"q & (p << 1) = {q & (p << 1)}")
print(f"n = {n}")
print(f"ct = {pow(bytes_to_long(flag), e, n)}")

Output:

q & p = 19255533152796212242992720925015052977165100229038356072853122758344297941391913731811288637503889893957835822989935905303713710752777324449266828571841201518847196873248114942547801080335290296371569234716421544911658172501145437393374846710803138137307808989325161763203891991730019545282414118666012446323593086041877728885890674444508568272709108666087094340700674807743690571277087703553222951943577713106957357837938244344527749744370370435090293574356857988176670599582946379436655614131476306476922532815575101035473325680474072477054146850541735494484153707953999275852485352550848613495775319945508202644999
q & (p << 1) = 7112801180654287964416909811366845221897670460107053268303965490368202211276157255630735531566632628465152668686888640536853981159344411188296318259605583929497982211483530931191597394343036880068072881710523781673885424996130058924135020477539221992619498201582190182198153594649904776914100045695897933800407597682900652789330655753567616853658441592170031153228700361032402777562805345962689285290223782295723638984115678627453468399955519885678698327942540059520178138360999657256216711952458812051551165176295610310500428357599329357195749872213722317472180820883692423118643045719988782875815244858084697476366
n = 629263048151678305452575447956575574759729289344426844202876190608729386386187311507156472537419877194722565074742404474698366095301561396335500009086708551715132944925359104482586968535982172950848450616991486882164933308508030447653541771655030633998773150256734151751231794877979894290664805083776347342841761965788022840306507239441472691061434470185155032785918312667155385234312006506953766398470559241684348455601303254513011313918610616344912164305133747945264184175075854717949201043915926552112919719551057640336347310797718453167003130736074852312783981575598197332137858417098138416213397261148554654179742495625000360596380874940069029982601426157700748784881191392765089982233146921318026797755334408105373194190261281426387522068561242744164826397282820570568637958792140799126352243030106388095542265469305391551869027843342339154723022877866472822563864376560243639560467511356673304688994611178354402493975884389423599865545923442816759098328052411030900992085384559185402018882151132333482321734163732964488703573324125780883694828630888629776285568460726623516777110511994045844185435441079697963865653276442218986812145494888396848459290412863370866388156404788872458013848321261694230557300704687955285231150137
ct = 35298631628116130359224654110168305695982263906500815601759249283108606781495993601939607677236970629068001134120097872048346298307953019858839919026717964105487869203149070597551936375993296199579660217021336136433998784937743603970683139418478689946222340268013996123454851821390724257210413455383613162701044471319404611416122452452921345595693933169636951035696702392623767085416101066602717724444002299274612686682594037338907063212581482954711824313661812748820691063881955175084607554637569409759030783300364288473371373832534871778535166888722850811961187103969586607877763143837938758790388347366625971683806113122596153715440188499656167803082999535346051898784036138811121907140409949123154237058329266014568111157279036477684552616957311754125182216065734001391180809071098197495830457756618079294014902429236831364119377802719574368458610707827017826257992031935701095686318205715338591241306163306525299337400170716508041836622056171392705019985962093427177719472269053233585174677794853848800112460097556102315773427435151857478042275125516910669415068837225875052551650890943588902290783802793542904493909655842024149436485583744880955905477870547039491983853968026355806167211650396511235141802512018515691794973835

Solve:

from Crypto.Util.number import long_to_bytes

a = 19255533152796212242992720925015052977165100229038356072853122758344297941391913731811288637503889893957835822989935905303713710752777324449266828571841201518847196873248114942547801080335290296371569234716421544911658172501145437393374846710803138137307808989325161763203891991730019545282414118666012446323593086041877728885890674444508568272709108666087094340700674807743690571277087703553222951943577713106957357837938244344527749744370370435090293574356857988176670599582946379436655614131476306476922532815575101035473325680474072477054146850541735494484153707953999275852485352550848613495775319945508202644999
b = 7112801180654287964416909811366845221897670460107053268303965490368202211276157255630735531566632628465152668686888640536853981159344411188296318259605583929497982211483530931191597394343036880068072881710523781673885424996130058924135020477539221992619498201582190182198153594649904776914100045695897933800407597682900652789330655753567616853658441592170031153228700361032402777562805345962689285290223782295723638984115678627453468399955519885678698327942540059520178138360999657256216711952458812051551165176295610310500428357599329357195749872213722317472180820883692423118643045719988782875815244858084697476366
n = 629263048151678305452575447956575574759729289344426844202876190608729386386187311507156472537419877194722565074742404474698366095301561396335500009086708551715132944925359104482586968535982172950848450616991486882164933308508030447653541771655030633998773150256734151751231794877979894290664805083776347342841761965788022840306507239441472691061434470185155032785918312667155385234312006506953766398470559241684348455601303254513011313918610616344912164305133747945264184175075854717949201043915926552112919719551057640336347310797718453167003130736074852312783981575598197332137858417098138416213397261148554654179742495625000360596380874940069029982601426157700748784881191392765089982233146921318026797755334408105373194190261281426387522068561242744164826397282820570568637958792140799126352243030106388095542265469305391551869027843342339154723022877866472822563864376560243639560467511356673304688994611178354402493975884389423599865545923442816759098328052411030900992085384559185402018882151132333482321734163732964488703573324125780883694828630888629776285568460726623516777110511994045844185435441079697963865653276442218986812145494888396848459290412863370866388156404788872458013848321261694230557300704687955285231150137
ct = 35298631628116130359224654110168305695982263906500815601759249283108606781495993601939607677236970629068001134120097872048346298307953019858839919026717964105487869203149070597551936375993296199579660217021336136433998784937743603970683139418478689946222340268013996123454851821390724257210413455383613162701044471319404611416122452452921345595693933169636951035696702392623767085416101066602717724444002299274612686682594037338907063212581482954711824313661812748820691063881955175084607554637569409759030783300364288473371373832534871778535166888722850811961187103969586607877763143837938758790388347366625971683806113122596153715440188499656167803082999535346051898784036138811121907140409949123154237058329266014568111157279036477684552616957311754125182216065734001391180809071098197495830457756618079294014902429236831364119377802719574368458610707827017826257992031935701095686318205715338591241306163306525299337400170716508041836622056171392705019985962093427177719472269053233585174677794853848800112460097556102315773427435151857478042275125516910669415068837225875052551650890943588902290783802793542904493909655842024149436485583744880955905477870547039491983853968026355806167211650396511235141802512018515691794973835

sol = {(0, 0)}
for i in range(2048):
    cur_sol = set()
    for pp, qq in sol:
        for b1 in [0, 1]:
            for b2 in [0, 1]:
                p = b1*2**i + pp
                q = b2*2**i + qq
                
                m = 2**(i+1)
                if q & p != a % m:
                    continue
                if q & (p << 1) != b % m:
                    continue
                if (p*q) % m != n % m:
                    continue
                cur_sol.add((p, q))
    sol = cur_sol

p, q = list(sol)[0]
d = pow(65537, -1, (p-1)*(q-1))
print(long_to_bytes(pow(ct, d, n)))