Sqursa_xx - hspace CTF 2024

Challenge

from Crypto.Util.number import getRandomNBitInteger, isPrime, bytes_to_long

def getprimes(n):
    while True:
        x = getRandomNBitInteger(n)
        p = x**2+(x+1)**2
        q = (x+1)**2+(x+2)**2
        if isPrime(p) and isPrime(q):
            return p,q
        
p1,q1 = getprimes(512)
p2,q2 = getprimes(512)

n = p1*q1*p2*q2
e = 0x10001

flag = b'hspace{????????????????????????????????????????}'
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

n = 6454423213359676492076586433377384180553154620757544375580636919301912582340330508392143924179086305517724790315871965777602816412767932667785917225743888964459281215100787086010016668830402583563646336219115554632701358734847067025341848619400548762530324914694095156014242905576000501466844854717583521018354672616647140198253565997899626127224200790896605164538782905570295472557895383085297115430138928430803582859538825730493758839084879899799398216158836745257075251571822342529507898047855111542881269812151792424474594056262283157679626715246322641756747382495409063744497134544395603436430118568788735344431125836414631479469472536573351325318197962998206654571555804602834262180317579582288243363325765275278501406714064121871120605139007953064543351915737158026571766537213845680330455695151046327322710020889857106661575647667806997201927046708747735408162666543184803577877798956179794067382110706663656064250577566620969777213348041163764963804283776793638453286176479525138548336772489710569607862831782345838643276081662916199285131046163240618362680409014678279053188467230957255603823494564810283216060199029964262559165783399181436805227762425939780483616794679471187311166866683869356743430332429073438672951087468699894418375888511202005954620172123053479891526035918334845089839592625046951303240347170479596290486388946541391657681708774258145488250818980616296606438698573189758486334669746266151703338170791637807913904140049094286627471242723163843772677119277416879085457084156711327209374719292513119440501176236160056813748059146471371197426927193319192745474123565961463549276926043495690034491356870591986879793397130624393098026059675436089288195490184984831291850165393398209624854460653524501554477795329682871804309938638163850247449755102380256926981224647140649202104513541432274321565131311726650582006776075040755746272474402802193430039579128504626312750410911674914552572890403925100237965058643688374031004926300537980709904358727583834331626257249440622820145254962492030976755429680663322388607523989320283713323596171621916183659671847653091458612635961216577708924502057960217009859779593479212143465995773063688273850440921404536332859584172243130294311817961437681396056505644914509453742729337844468273171200489420725692540630039531379777212997173243589542120485295546591535208437258586997077797396729648721741055335239444804115254823625184450177459525222336653887799029614852547890282900545214781195257722608897242501
e = 65537
ct = 3211920181557456447705867851924798752708990421414355820122192360938611781386332224711980759606551668905860913602751130753835381632550746178958999709875074472238988540868916159480210556444799009984038565415219678531891753953698209758295942690479314764749087266173352925418990643351030809640315068589246472379323290881060317893839266713759629608348497036140513230309842885777335648481778907397892486613403445090068019227447190429003767988437837107436934704110794919089616951350644138908722311224307898913062829881877336616731421453165303386295574713758781739641475356815555577271031528300228025567401045796996251216381531736182230114547358080388587403772009142101630896791667763856084653500648453102223780940398136069679822296472658358121454000630565049645807583337949100693218541399710289267321368947402887929256136951633832349956524246062487879577702046434965181196510249638732416989776292712117922766764761444809922375884837539897494074917421244496712432636027299838000548295199098614407392723836050207114589834743972274995877042108801924636062499547256234706607962985651213635338769224151274561799915256490521775106593940999189155770963854132682294549496517585965733737031913715122863432733629136776958194393790585330204929587172773993430490338242569164608633683022217069852503001359245801585281384963967849910159782937245601670477899704207389500906529739620928707777554320012441801905375198367973754268136932521748041342657918224641905006156856537432689958356247162217599986176131463348541726948278870083203185084089293926125131210499708844322015744051683878221611922301938417720853487063136516071385803405332439501164147965782331355581261601966583870792715387889667627566971390390438315796784220832134334237987736620516681694442579402246173258810947876369552120068348639017552352749008541555426870896138846330109143232678674960207763391985026535753210971780209990647800226131183984736101363821935139556258169726475914738900545348023354435052429240114644189976021957056167962380333577479568733062629755826691840996266808872527427964739751459672981148948531368635410602029454238015488851306383227142891858209578031555163706699533481125800349386580314954019948876894653337875187431845261875815202960321624646208303966564183611145918195976036913833321763867524620955804100886688171534648976427010970997046986057897000623131911949182645462816112107326985306930882753682100853764619512859598721493571101073310968859005742037824419284020252637328792886286682854282437966

Solve

Sub in u = (x+1)^2 , v = (y+1)^2

Then you get n = (4*u^2+1) * (4*v^2+1)

Now an approximation trick, we know that u*v = sqrt(n)//4

Now it’s just 2 equations and 2 unknowns:

from Crypto.Util.number import *

n = 6454423213359676492076586433377384180553154620757544375580636919301912582340330508392143924179086305517724790315871965777602816412767932667785917225743888964459281215100787086010016668830402583563646336219115554632701358734847067025341848619400548762530324914694095156014242905576000501466844854717583521018354672616647140198253565997899626127224200790896605164538782905570295472557895383085297115430138928430803582859538825730493758839084879899799398216158836745257075251571822342529507898047855111542881269812151792424474594056262283157679626715246322641756747382495409063744497134544395603436430118568788735344431125836414631479469472536573351325318197962998206654571555804602834262180317579582288243363325765275278501406714064121871120605139007953064543351915737158026571766537213845680330455695151046327322710020889857106661575647667806997201927046708747735408162666543184803577877798956179794067382110706663656064250577566620969777213348041163764963804283776793638453286176479525138548336772489710569607862831782345838643276081662916199285131046163240618362680409014678279053188467230957255603823494564810283216060199029964262559165783399181436805227762425939780483616794679471187311166866683869356743430332429073438672951087468699894418375888511202005954620172123053479891526035918334845089839592625046951303240347170479596290486388946541391657681708774258145488250818980616296606438698573189758486334669746266151703338170791637807913904140049094286627471242723163843772677119277416879085457084156711327209374719292513119440501176236160056813748059146471371197426927193319192745474123565961463549276926043495690034491356870591986879793397130624393098026059675436089288195490184984831291850165393398209624854460653524501554477795329682871804309938638163850247449755102380256926981224647140649202104513541432274321565131311726650582006776075040755746272474402802193430039579128504626312750410911674914552572890403925100237965058643688374031004926300537980709904358727583834331626257249440622820145254962492030976755429680663322388607523989320283713323596171621916183659671847653091458612635961216577708924502057960217009859779593479212143465995773063688273850440921404536332859584172243130294311817961437681396056505644914509453742729337844468273171200489420725692540630039531379777212997173243589542120485295546591535208437258586997077797396729648721741055335239444804115254823625184450177459525222336653887799029614852547890282900545214781195257722608897242501
e = 65537
ct = 3211920181557456447705867851924798752708990421414355820122192360938611781386332224711980759606551668905860913602751130753835381632550746178958999709875074472238988540868916159480210556444799009984038565415219678531891753953698209758295942690479314764749087266173352925418990643351030809640315068589246472379323290881060317893839266713759629608348497036140513230309842885777335648481778907397892486613403445090068019227447190429003767988437837107436934704110794919089616951350644138908722311224307898913062829881877336616731421453165303386295574713758781739641475356815555577271031528300228025567401045796996251216381531736182230114547358080388587403772009142101630896791667763856084653500648453102223780940398136069679822296472658358121454000630565049645807583337949100693218541399710289267321368947402887929256136951633832349956524246062487879577702046434965181196510249638732416989776292712117922766764761444809922375884837539897494074917421244496712432636027299838000548295199098614407392723836050207114589834743972274995877042108801924636062499547256234706607962985651213635338769224151274561799915256490521775106593940999189155770963854132682294549496517585965733737031913715122863432733629136776958194393790585330204929587172773993430490338242569164608633683022217069852503001359245801585281384963967849910159782937245601670477899704207389500906529739620928707777554320012441801905375198367973754268136932521748041342657918224641905006156856537432689958356247162217599986176131463348541726948278870083203185084089293926125131210499708844322015744051683878221611922301938417720853487063136516071385803405332439501164147965782331355581261601966583870792715387889667627566971390390438315796784220832134334237987736620516681694442579402246173258810947876369552120068348639017552352749008541555426870896138846330109143232678674960207763391985026535753210971780209990647800226131183984736101363821935139556258169726475914738900545348023354435052429240114644189976021957056167962380333577479568733062629755826691840996266808872527427964739751459672981148948531368635410602029454238015488851306383227142891858209578031555163706699533481125800349386580314954019948876894653337875187431845261875815202960321624646208303966564183611145918195976036913833321763867524620955804100886688171534648976427010970997046986057897000623131911949182645462816112107326985306930882753682100853764619512859598721493571101073310968859005742037824419284020252637328792886286682854282437966

var('u v')
f1 = (4*u^2+1) * (4*v^2+1) - n
f2 = u*v - isqrt(n)//4
u = solve([f1, f2], u, v, solution_dict=True)[0][u]

x = isqrt(u) - 1
p = x**2+(x+1)**2
flag = GF(p)(ct).nth_root(e)
print(long_to_bytes(int(flag)))

# hspace{oRderEd_PrimE_eQu4res_Rs4_arE_y0u_A_m4ste1_Of_e9uAti0n_Man1pu1at1oN?}