El Reset de 1745
16 minutes to read
We are provided with a Python script that creates a private RSA key and gives us some additional information:
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime,inverse
from sage.all import cos,floor,sqrt
def main():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
print(N,q >> 450)
print(cos(q >> 450).n(4096))
# -0.83677025469083783941541701752761854754793836436580928644247008941810266469532458996045447348443859400152817824525738732652478723578550322419681449352934903962868272432839950443728133311767399079690030001079242722034971856216464693298008475334803612328029119715730610948114017183466860376219520135065944451843458471230390067711216822465611823803314088335568327990572989813880317949003496128817743756941657517592732976171161188449564836856703887590653409218974871687234942350215936871374265782174012360582549759635891009261305443677350659234691411334888094583016691447506478413851786692210332884103069291530840376504431016357464401672842279159473862600445695092589720790836314505433051945268839223026728538635526261735680020640125514694922387865117641745486767737807560114356069413145843513030254057578430063498955558945235100024577603060294061771113596755818633721728098654211982059793050427304804021628754473574523763161349682175284850419236582818156064980865716476145483816198034274679778084438576624517718459301374217997767985615596748052223448537502912453071556058736828589970943263917953424626006378389407199956646994682638376389500968564930356704561568053846692273026900362154710217069324829901876963571359354949212621973636284
e = 0x10001
priv = RSA.construct((p*q, e, inverse(e, (p - 1) * (q - 1))))
with open("priv.pem",'wb') as f:
f.write(priv.exportKey('PEM'))
if __name__ == '__main__':
main()
In addition, we have a PCAP file with encrypted TLS 1.2 data:
Although in the script we have a instruction print(N, q >> 450), we do not have this information. The decimal number that appears commented seems to be the result of cos(q >> 450).n(4096).
RSA
The public RSA key $(N, e)$ can be extracted from the PCAP during the TLS 1.2 negotiation:
Now, we need to obtain the private key (prime numbers $p$ and $q$ such that $N = p \cdot q$) to decrypt communication. To do this, we could use the value of q >> 450, since with this we could apply the Coppersmith method to find $q$. But for this, we need to obtain q >> 450 from cos(q >> 450).n(4096).
Integer linear relations
This part is very similar to the challenge Tan from ImaginaryCTF 2023. The only thing that changes is that the cosine is used instead of the tangent. The way to solve it is using a lattice and LLL to get a short vector.
We know that $c = \cos{(q_H)}$, and we want to find $q_H$. On the one hand, we have many decimals of $c$, and on the other, we know that $q_H$ is an integer. Cosine is a function $\cos: \mathbb{R} \to [-1, 1]$, but inverse cosine is normally defined as $\arccos: [-1, 1] \to [-\pi, \pi]$. This is because the cosine function is periodic and only a period is taken as an image, by agreement:
$$ \cos{(\alpha)} = \cos{(\alpha + k \cdot 2\pi)} \;, \quad k \in \mathbb{Z} $$
Knowing this, we have the following:
$$ \arccos{(c)} + k \cdot 2\pi = q_H \in \mathbb{Z} $$
This is an integer linear relation, which can be resolved by LLL. We can adapt the lattice proposed by the creator of the challenge Tan to our situation, where $B = 4096$:
$$ L = \begin{pmatrix} 2^B & 2^B \arccos{(c)} & 2^B \cdot 2\pi \\ 0 & 1 & 0 \\ 0 & \arccos{(c)} & 2\pi \end{pmatrix} $$
This way, we will be looking for the next short vector of the lattice:
$$ \begin{pmatrix} 2^B & 2^B \cdot \arccos{(c)} & 2^B \cdot 2\pi \\ 0 & 1 & 0 \\ 0 & \arccos{(c)} & 2\pi \end{pmatrix} \cdot \begin{pmatrix} z \\ 1 \\ k \end{pmatrix} = \begin{pmatrix} 2^B (z + q_H) \\ 1 \\ q_H \end{pmatrix} $$
In SageMath, this can be implemented as follows:
N = 0x0084023c955d782cf873302c7199cee0caf8f039ffb6534ee688c884e12b0bcc3ef734128a1a0253f0a878dc7abf060550cb695066686bcd52abba1227bd6f29e0422076ea9aadb4093346c321b16f082a579f467098fa6cf4f199abaa9c434cfd9bae44e08a689665ae223f9d9d12241637a083cdba46033a43674bb3704ab33cb930404171416a84a1fb2a55dfa12ed1ad939c4c37906affd81ee06c5602f8338a1dc958ea4d707f82c81132d4bd4c954f612ecad6633bc3b0d93905eacca5f6feacae5bb4210eb8ff74473253220d6e97d4e2ae9711c4b2ca3d2b1bd3b2071d5066f897ef909faab1a0f94f88be2f76d8bff6fbb1344c39257dfeea663ac09f
print(f'{hex(N) = }')
print(f'{int(N).bit_length() = }')
B = 4096
c = -0.83677025469083783941541701752761854754793836436580928644247008941810266469532458996045447348443859400152817824525738732652478723578550322419681449352934903962868272432839950443728133311767399079690030001079242722034971856216464693298008475334803612328029119715730610948114017183466860376219520135065944451843458471230390067711216822465611823803314088335568327990572989813880317949003496128817743756941657517592732976171161188449564836856703887590653409218974871687234942350215936871374265782174012360582549759635891009261305443677350659234691411334888094583016691447506478413851786692210332884103069291530840376504431016357464401672842279159473862600445695092589720790836314505433051945268839223026728538635526261735680020640125514694922387865117641745486767737807560114356069413145843513030254057578430063498955558945235100024577603060294061771113596755818633721728098654211982059793050427304804021628754473574523763161349682175284850419236582818156064980865716476145483816198034274679778084438576624517718459301374217997767985615596748052223448537502912453071556058736828589970943263917953424626006378389407199956646994682638376389500968564930356704561568053846692273026900362154710217069324829901876963571359354949212621973636284
ac = arccos(c)
pi_n = (2 * pi).n(B)
L = matrix(QQ, [[1, 0, 0], [ac, 1, ac], [pi_n, 0, pi_n]])
L[:, 0] *= 2 ** B
L = L.LLL()
L[:, 0] /= 2 ** B
qH = abs(round(L[0][-1])) << 450
assert c == cos(qH >> 450).n(B)
print(f'{hex(qH) = }')
print(f'{int(qH).bit_length() = }')
And with this we get the value of $q_H$ (q >> 450):
$ sage solve.sage
hex(N) = '0x84023c955d782cf873302c7199cee0caf8f039ffb6534ee688c884e12b0bcc3ef734128a1a0253f0a878dc7abf060550cb695066686bcd52abba1227bd6f29e0422076ea9aadb4093346c321b16f082a579f467098fa6cf4f199abaa9c434cfd9bae44e08a689665ae223f9d9d12241637a083cdba46033a43674bb3704ab33cb930404171416a84a1fb2a55dfa12ed1ad939c4c37906affd81ee06c5602f8338a1dc958ea4d707f82c81132d4bd4c954f612ecad6633bc3b0d93905eacca5f6feacae5bb4210eb8ff74473253220d6e97d4e2ae9711c4b2ca3d2b1bd3b2071d5066f897ef909faab1a0f94f88be2f76d8bff6fbb1344c39257dfeea663ac09f'
int(N).bit_length() = 2048
hex(qH) = '0xb1eb9278a603d830a202f0c2a46b9c97e0563d8e710948527e185e2f2b4fbba2564309f004bb2ca615b378f494c769890afc6c1f4e7c17c9aa88a8fe99214e3bc88b8d47d335d2700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
int(qH).bit_length() = 1024
Coppersmith method
Now we can use the Coppersmith method to find the full value of $q$, since we know some of its most significant bits. A similar challenge is Bank-er-smith.
Even so, it is not so easy to implement since we need to find 450 bits of a 1024-bit number. It is a rather small proportion to make Coppersmith method work well. For this reason, we can help the algorithm with a small brute force (up to 16 bits is affordable) and knowing that the least significant bit will always be $1$ (since the number $q$ is prime, and therefore, odd). We can also use different parameters $\beta$ (normally, around $0.5$ because $q \approx N^{0.5}$). Thus, the SageMath code remains as follows:
import itertools
P.<x> = PolynomialRing(Zmod(N))
for qq, beta in itertools.product(range(2 ** 11), [0.49, 0.499, 0.5, 0.501, 0.51]):
qqH = qH + (qq << (450 - 11))
roots = (1 + 2 * x + qqH).monic().small_roots(X=2 ** (450 - 11 - 1), beta=beta)
if roots:
q = int(1 + 2 * roots[0] + qqH)
if N % q == 0 and 1 < q < N:
print(f'{beta = }')
print(f'{hex(q) = }')
break
And when executing it, we get the value of $q$:
$ sage solve.sage
hex(N) = '0x84023c955d782cf873302c7199cee0caf8f039ffb6534ee688c884e12b0bcc3ef734128a1a0253f0a878dc7abf060550cb695066686bcd52abba1227bd6f29e0422076ea9aadb4093346c321b16f082a579f467098fa6cf4f199abaa9c434cfd9bae44e08a689665ae223f9d9d12241637a083cdba46033a43674bb3704ab33cb930404171416a84a1fb2a55dfa12ed1ad939c4c37906affd81ee06c5602f8338a1dc958ea4d707f82c81132d4bd4c954f612ecad6633bc3b0d93905eacca5f6feacae5bb4210eb8ff74473253220d6e97d4e2ae9711c4b2ca3d2b1bd3b2071d5066f897ef909faab1a0f94f88be2f76d8bff6fbb1344c39257dfeea663ac09f'
int(N).bit_length() = 2048
hex(qH) = '0xb1eb9278a603d830a202f0c2a46b9c97e0563d8e710948527e185e2f2b4fbba2564309f004bb2ca615b378f494c769890afc6c1f4e7c17c9aa88a8fe99214e3bc88b8d47d335d2700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
int(qH).bit_length() = 1024
beta = 0.490000000000000
hex(q) = '0xb1eb9278a603d830a202f0c2a46b9c97e0563d8e710948527e185e2f2b4fbba2564309f004bb2ca615b378f494c769890afc6c1f4e7c17c9aa88a8fe99214e3bc88b8d47d335d273853ffec0cf7b36bc4d3095ccec142bd53ef2e79ecb1ac926646beede6b327383ccd62af2908299c4ab193808281b330249f0fd4e7d92f4ff'
Great, now with this value of $q$ we can find the private RSA key and decrypt all the traffic of the Wireshark PCAP:
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, isPrime
n = 0x84023c955d782cf873302c7199cee0caf8f039ffb6534ee688c884e12b0bcc3ef734128a1a0253f0a878dc7abf060550cb695066686bcd52abba1227bd6f29e0422076ea9aadb4093346c321b16f082a579f467098fa6cf4f199abaa9c434cfd9bae44e08a689665ae223f9d9d12241637a083cdba46033a43674bb3704ab33cb930404171416a84a1fb2a55dfa12ed1ad939c4c37906affd81ee06c5602f8338a1dc958ea4d707f82c81132d4bd4c954f612ecad6633bc3b0d93905eacca5f6feacae5bb4210eb8ff74473253220d6e97d4e2ae9711c4b2ca3d2b1bd3b2071d5066f897ef909faab1a0f94f88be2f76d8bff6fbb1344c39257dfeea663ac09f
q = 0xb1eb9278a603d830a202f0c2a46b9c97e0563d8e710948527e185e2f2b4fbba2564309f004bb2ca615b378f494c769890afc6c1f4e7c17c9aa88a8fe99214e3bc88b8d47d335d273853ffec0cf7b36bc4d3095ccec142bd53ef2e79ecb1ac926646beede6b327383ccd62af2908299c4ab193808281b330249f0fd4e7d92f4ff
assert n % q == 0 and isPrime(q)
p = n // q
e = 0x10001
priv = RSA.construct((p * q, e, inverse(e, (p - 1) * (q - 1))))
with open('priv.pem','wb') as f:
f.write(priv.exportKey('PEM'))
And with this file priv.pem We can see the PCAP traffic when importing the key in Wireshark: (Preferences… -> RSA keys). What we see is an HTTP request to /secrets.zip and its response:
ECC
By extracting the ZIP file and decompressing it, we discover two files:
chad_encryption.sage
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256
def hide_flag_between_reptilians(key,plaintext):
iv = b"iseeyou!"*2
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(plaintext, 32))
return ciphertext.hex()
def get_master_parameters():
p = getPrime(431)
q = getPrime(431)
Gx, Gy = randrange(2**256,2**257), randrange(2**256,2**257)
a = randint(2, (p*q)**2)
b = (Gy**2 - Gx**3 - a*Gx) % (p*q)**2
return (a,b,p,q,(Gx,Gy))
def third_dimension_ecc(G,N):
garbage = [randint(1,N) for _ in range(32)]
secret_array = [garbage[i] * G for i in range(32)]
print(f"In your dimension you are able to see this: {[x.xy() for x in secret_array]}")
return sha256(str(sum(garbage)).encode()).digest()
def main():
a,b,p,q, G = get_master_parameters()
N = p*q
E = EllipticCurve(Zmod(N) , [a,b])
B = E(G)
master_eye = int(E.change_ring(GF(q)).order()*E.change_ring(GF(p)).order())
point2inf = E(0,1,0)
assert master_eye*B == point2inf
print(f"The Master Eye is granted to you: {master_eye}")
EM = EllipticCurve(Zmod(N**2) , [a,b])
with open("flag.txt","rb") as f:
FLAG = f.read()
KEY = third_dimension_ecc(EM(G),N)
print("enc_flag = ",hide_flag_between_reptilians(KEY, FLAG))
if __name__ == "__main__":
main()
output.txt:
The Master Eye is granted to you: 16265471931640785828934127858946752538285468297743536678369884769655894080669562147795213991083005768993394358509783223221158858616114956533429224780974963093860223870869151381622793452378040102391285088110131930993214655276327069828109098832154854719776594644
In your dimension your are able to see this: [(79364468785236952279306319947486981248865881109689880151701940694064893979908366213038221679380344986127502056375006658490264731158574287241753313341555481402017633356285197771242603178001464846171145411665369899716221278004315749554836475575261046450436145959429152755593843874272934087644242937261243790850746058845526628319552492967085187705098606977143896792510184949161152227872504750529657542182084860998608178545130782929487362604009699589317802551001766633251821245604199207911871496973183520003360060704663214, 16687868136816790667937853246796901063040944936759940662722448380093920072006750947759005398743346758508016260528885932320663505212977936388527162162700995881129762284545953159504084714702981447856577155545734415853887630161403524590482445165827667785041932424914364528689537173920286382744504598070079197190571583803626137199250536574114579102857674775519365478519464262272039879237629974345129100337321029345797122618346654708409642719988452075056672175360303595214679844777756177806896404220841682828148652726672638), (18899724296709356965234494619104772779470606388931481117456688008818773207217366971633275128353972861633690819420635187472982517415400458909499316310931735946901572543121761179549512998697352800479852589929855627415400504246815106263800422957389670026191418168234235240406098997159721205877122915135525815565333680276051547563185321448352067894786538244048272702500927838999047658003300634824432270546232541050231457086443144424139179909585041352826454599094625605744436472796192783054911539407677446501812033471321524, 181969980377542764707955040897437722784709145520407120692028567222043813796008600849964806554297247610034947681294613264869782056823632123233711963621923181395296514822877676280308872426739819929410735010216364608798913264921312771916561066019134544296445889808932682039938044349353633612260789631107610936747968998606077205378127104320871869801486116872451256587440551053631039031230396157049192240149053601614033999746393390194723403360681914729802280523975083933174774134319246514382925460749896675407154805485284511), (68471692495575172133443182331265395323780023618521247524518268730711946951940988673749804251758452778660185511305483225416051708878357189530595965992350055334820378387109046064384283138464825854455750319884417034907809207922174034293151428401066968153603720309881678240489554389902246968911783683529409598893006732050710469464502354213081471824890463157409366264164051370265213326073053285020204917375631748764264712643374983681057721917952358757015432749432908948261428353275093151790075022197714189206163134215315103, 21086153520048598786169857750936805604277664567817774664460508684003670502302309090451996890460669084397056007859256108355293069289180286744069869788034455379356774892426063355812211938369687363613649187261276214647682224924760631173273646480179734923052819579729206566136998202738004693357079772445998313417118811575716713719713425456903643208635220241330814329516583323942979855886550421694669869092246154864251064889038193612822797937736925854371199646805580554872113726878535438082715356751200540213482107525098188), (116969053282694964799384771184091326303783633954428385196195106448482795095537983186445774516345149664381173834220871423555644858263622043970631708050194494865598220654365692163194726440427226462426292354441330021886333830775935143649055408074223466986424355324037704727682925776252702628182654864848940761049870226530117740598115594078111417658004448199672691637414626676511064717083418122102790469776547004932065495742273400807655050349768888802235266816179305399411904017010194674411837318963119660814179508659522079, 50084014889793959696599960870266488490551570031242416218275044365044406279560773812159187876069277424936558566002408934269450009685126762919422186537900216338665358746852202216630815904714706257229182538937888481607640416939802948615453184222442533517179199989078012953988190237579277262608278898391324918782630916840313135675473154777780855027523835253960743640206425166079504138147039127770593334045531030931479175201464964155413852798543401227075673058536367848947304461742267492110565792799164008125042863814750484), (75495634491380681480755034982641869190790206884849110723256175106318578661884367627647143036688535570791725909016139335131090112769001955747766299722705758599159778181042043453667346349033547319312262250475534057045860453347457133690528259902127083849168115417362595686165076571790325723969187880950829034560735006803713082244776521462470725461944018138446316622326672180314948459934243221388622927753353641287295474464745004329035876313365899195265984567422425276920658644349603345662940685219340306202950650607462424, 36253213840544424135747639984625468377126489352389007053380932532914480713717870396970116475077843047531097911732210943486983201258877192757861153015876591828621816348899115209925885000722027312971132000986223661591438360763777219039380763132328418089417368883034318747845529041436281909436209997433288486880452129344883136566180200589020934893263313246425182857484118510922258585583154053518563004163870433471783169696048347094801055344875002707558347225173012259302506287684325108055470698444963530011674895234940861), (192481455040907281329193584721852105461149835280168733847414582510382943795683937046047272270386155455427903029708072280124641608091666028101203441908633497627017890386867343567857125870268607159026410298301416630232047646360786504167687619545786494459446199856135388394976238012143847784593439590750118221999002429721920816932370398509030842536157171976181011006850034186822030054621552078384154095398615589672184024311433279726791936051360592141198012580769956217276136748224000824970866935881059774801322488495734737, 263750748030593406555372960075339347959501012664293859999528761406646617202885255209546013672103696519460696026989591318113562143370752757504971207850886357088200588529406714681418094672394611241767914354242709867737587173914012871284335033363056451884058022592279355794323391316627257591556094592398182461024352393825325635906355111844626491458756610991526543618068466546705753811183653095707925663763039824680079042497299645105323384745735490293862452599416389420082263130648481405274914126094178915535243279138216891), (255417412247910237204056992220045681879601415453288901101493272549214517912477637905405057604185717193019107588463580766046854561097661737623152334645649813648085887341524457445897093708191115078479102309838323390531754049310253939778322042103086681614882877414565503266734052030713798844268300288931266616639070681932489338231071158921404363210396384266907626544529764539182475404302001747080341642167481344327297753736338699702763493207235894318368979448459989566928583831763472499113910984819179772191593553652132474, 216838227007896475467505545385808596622593627839947735482086337073695133835970632571085739743178459369081219447146261545489025016023191480118835913846110397255114648919854819641700710717424878468620182038420695530305995881014362474635138548754798584240818513132332952780471786911557099270185846735324286244202698215309265097328428369735979500503151382847521451988517209863599729938833413473246217315543633075429285724935075345739203874313074322507039546739903067587047347937253792823522407423759267865629674811587336735), (124096126188514803544503955059315279141132559829237017973895020854171803237264834921222239856902238141179876125883968947274872965203378100360103207367714763024384163506879494701103972703086350129968586526203471429720871699511033522121952069111450022016969221035561423806264769591980121521115751553028030488337106779564554084983419507958422995036643408111208147569385927747112032878129152578402922719412406569384357851502035073976747328543651617464058989532223729123880689755690748865232003435467745311460600569632062195, 79795929489497405541344074279045484311257046279349845074266797064963552718105676350112801481079796697379543842277745402508713939382393071567528053085584437224203083580852710549037874369323959513137365714211165782436080036247333330794646390255560519641038629449067754438673314304868898813042624277285756041579001910407073190691633730020025977695329396764438605452385145610146775049817517456197497958984225616236669698260373850993781035376644766912592244717606326819474841714478055835222357317541164073792768197449976805), (190703286030345244045469778665561974216325069308265949202325894850227791765904139485525133899256922401602997366124011248349376295580261874319338852553684877393759367840644756984940510336404382711261363588684354508782828978401315935725937405785634244395621036683704621600788947421051146412108450650360926888325295167558040472336174751620673578392573280408257149796768348815768625550159870118878124609165630736159309639790673200547390682579251405402083531773765502679177847618650304506944498168089416322240738303940653213, 24736645903036881803140323581228716611113404998832076832196705758532168994501238783666375149022287321792427144500995307601858381136965807435697339506741211246927952932690067441621139167964194664193434621736623395830739730041951079386866340029257422408469503684333096054282304496745395068380277705022308880154716936569675145590997527120346373478094696152761116815474531993309298675688562696276172987521492269383043279810681588686656859154216730700730536263035848904078841458919347823245082214554180323650026964599193449), (258703341869999263552696566941924062917262532623427112981841289107534325684990395930426708646820618617158698098807584327410715882613007054798579382797202218924771823397597250874444158233109489433439437861168171982652882535734326225316450293623741694672869263741406310745286481287471748736505002599328297372513945104194558584930703398823479254727890496522036645921691948539312161687230707649623943993196786543478056821803577376429265789558098025007309268634834269286613805213473295723199595802084698720821452641690348762, 157597653185058333749305618814281541720926026316916248894515953007654834382945318302782897071081232168734135231503541126542944853455636669320882162239580132818141369909385380309951303769335111171767021649073648211864119796372073673232431330520655857858471659683744957380388861533423069333178715676730080139275594800569694523547635241524786097810950368839577943317787129038527925602633331544524871784599829599691035333266868107278941473293754170485781398238637499037126629714954539370303741202156428560403509971269120259), (144029484484143740842105007898750587818400259866067203106619661765763196612852225351180802281798132738759712673153837981988639932431947090809824592374750203985082077932231250238993558934126045641958929154545019638665302385408753639772238214965583998593458523982768916457289049350438036003586345084629417537221581589792274874386127526724174033010886505160380617273573415323932040916826340570542462697219927548091751481509377962625757071590735901774613456978510749747386546939521455040718702532592290387855298509964335504, 81136403803938509674953360140216723808828994157366853530661289992039975024693660530412770844694016294799917019166287093752795881772713038987632126846487124365054635128318325215698759027661009762825117366778570281270937841455064304807681267714958371425526732088357275832549199054044120705515004113312778633030563138690914909627177849996617456660673293755637236050697184282677574577668950305536160357560245868725179346462569085515282246946818804551864995963132631326540113293786152201453968620257820912842230789280672879), (167933423643310489968736909399339291074532111423728809018251315108934196550988975700904712999504968918797886060359964419385418362138089494181042173732835977776288115501526781854180140081384888294467362388183968192889440693933788263691009913440459578937986555297497010971816134549682779591167883513859028748417671900766328167176421597712058150529821656694452760283330487597721120507927015978002030880379686393503772683299429146980224934216236258524809257894318690697716404775604790364766740110823609354214543678454335207, 249060203030314638656800525340380123405021821952904721849953191711065909060250501335838898260047436743185888780451959829884660980671620355155805987888739105567254190879933334691411436378354628161756038668310804522041631705561214001778546633300265947270561795770260431256098931841216149131420253712922540548278872260455771972510899952597837538488876155123609496441312030794339392252544212884101476954780198469300130297678877552887865118112329028954549930740352455919380615142366214732987382847820614960930054016512403685), (81531132387261687911917499446685797723971871365375671509000262296850261719634523323876587160746818150479196876938791972820817931157649714415936984850766979784687364441837634119019081500667512591299111427780436432976950026422776044193795432616317613520986261395626116948865296824517463828639995464038528157308915881004595745408077589331144910923977821241124679034305505478460626044978730506369719002450030831539905895506531403799691784318024460051225878101146939170314725597099259252484920566074712476020128146708728763, 2937120054477468141509617584718072841466725665936920849977929083765990055665939440305887249811696047078394520908428092839293350858414170848178164083344045344698200810920746906003705786425990783693973403162815180341354385994880845699003303202234732248708097094724976024552659615350213712717065586514234121293071473763401980455740807740160917980173788010327993607060642470248510559196661609000914685808353954049312164318177565333183579224288193591968204930301057232213051631057654211493148123839424779942852687340685859), (103644260861603589957248808023254195447470005051473901151854421472615182158114771695576397034699248112789770191530282302797868406969984836822917079823398511974177377027477715431406825405053605595879747122357745078872754130028142971701445852516659874028185272404314555307882576155287855648800598012051775334174420913382203557539801927105317596120387809472648928484865311968302940472396169283793012693982543833931245644607885977240792560196956780193270009230312161519165925549238619384488289402663988278459288965755045202, 13386131823381627746769871412188175354099500837026101545007050182395652213622116827516458708885503040423176624137354534217799527216400345533053176835186505390864762712683850484524757574534628840609687178597044082451530395700669918033403997664280245962765624164711393899615828305969266729155003151307376498365166318455594869316786666702572444740194586528840860391405316667797716685898051306351300068423693781875048265594832229743511143553177543907602987672492835074752327279125873635511855999185175110114329459883377537), (49806447733446335028783340650616199033338438619086297731292629401023714767537877728133378993911023452403002227083159364255769432882774341778909294590221930944811276789872595855728949386605648638168750044129790208111103100331015942951240705120476205432357062176913813923085615505235799335479085172612638542586397849084541871749283790134400068035128471694535143019228346147248907280201471476695674163387417128954358898944253662151554055947196719426143186764729676220385474455614516558327773933799259609604596713816808540, 67153879925391225704783520063321728291841246303771866370802949117008384122412140630611604172020608684305418836497124227910945398307322662493354546743254952303151830473091638175848920166466803499511290396766988373587222642302671831397081157040791215851705427492378162911106643097070740607333182057088894418177665114567377267999038233912213229123903048082371574624240893841173078444693780515417133220692841998171028137554861232812549476624566311728736485760045414080572245456064999665273894920043788708634808692721225111), (121259199659160450418948388268391671626763025328320946113219792501668203928186402325839464256295141580273373580230405155605770463172239061805223622554363862547879300443826551552724595822125684018396490933825583005990724827277076614006784797779689099622702460506413009438350060304272340392268432807413132707604981714652259643802514139444520463112200299452118287602493071775805573055176357194744688372487796393645874066138755543916937978565303290845579555253269930091309454226581952736942651259771285494328313841696719176, 54423785383353167245475846055742639414462824811528992154255919783122213594530026632096607760980193960486608312853375968958284421107224238091920595029896291015596986820214401232689927476113723708035744569656886855911932772506245596347237606736702765609624147987779604630980992572618251242821548630723856294062865887942586987410202233110518443350460787360988488460220225272399530872204640419820350367837356650390876309151879191299124610782813723570535829463907264642390350356162471637889917462673983296700274587307954465), (92977303619726373774401333534444147442488907995426361498879182990025454415553018333510508171552601209120558825262326946206424684031961499092804928326240295304486879568678879403499951176191105736205078630584013388298255658637491139786884227468870908840259825869871138175305278010052511608139487753205231824362171703992332827590103700189042458984190221436070514094303300081382771155591123233515363366709552805738441658312586231620217316133963684195358526529253054377690560419819547756625965095265987708024421058924420032, 17534083239981379559980686853294607180922082121446077383464277173041051133747075976359326283052436801964963297772275562097872932301281868876431190065920949359745987270625836847527970947817991199732508451593735881928613879776080915431405451290973033569319514193671669728141214871416017947828875927229222881168169257475334995978506638522562727082841621103377534674314230094515648566698775749021699250522226914566251601033319352322004841943102716282077117990514212749731767331369952932713217468397590156019717599467826551), (151714288904469334580506311699687786932470047567590570627562909313285345196856604545832204480874695065076751985948503804773320989285516729101449384425625868713665574733542588482486855117947345613674296154473648201573294656067965326647224949611860214628357359309132040214209027790777151678914123082601456378886356732067541268132080748126762522835420758316631537412494961049197204205425016010352396151454741704273031546867105807470915616417638914866181520925045778461950631479727411682307627799765986827626393424093734894, 113195138575713276051356285353595608257964537355789624720904791904726154999652921625323202826448756838634725794845270773644628040704179463307506514170317679747518970223913451987204840944885539492431928207306649322098820553336366010453320453438302826748962194453073126072743462627626115533593121954332373216153303456196916042716877032156444624816270538578390571230115119658190341882710839242167009432905590403357945527537819618201757354986156989592243059863622832218854572529390202728216950457641950272095047333787845133), (143273408433100301029438629162157732007505901763968878422325872934638796541841921963880559171658699771599739944152860051396803691318827873678982069208535949317553094600976400547016789455183839578913564138947854902083200750061811236297222300037227275227735722169533644406492707041807445447669789156423983937337719273019297023253445936781670574157403858317609232724531493177053685096399564928522819896437359216101466084634086335795457115176098126076627222756666882660350843183492723945161110628940344165059531642659523383, 146674949633658124025273827347861739617972591213255422589451591241575751755759465692501605421798064451279436966144748850444994638018170033409916882690257065465451494369820928610739864416954101393861243749516295000434508472045269683452155382300622934680549683807475343006424675084022636524729510032850421728560842788745437895154746501644714259838329525121421521371090662294754870193345645037618193357860641995113251403596073075572702204621066922420230140482691977493775315013737307525071003333168203735454796604053833545), (249403491506281311380969267380571404400571727185603034767598580858666786446738167171913111309031464069379363518911333160553855193326393702713315185030611815951152637452746142527720323983558876002146517342279115230804997355865418057903304497673749142638365374144470739441077179470538767458050046177835858994825609702629664894934918018990719979984975720592480571603874761730644357479552994821055677150758155915862526298576933222903943787581240032930566464815465204077024966262935795336546362399011433775662246247111398239, 220026583481159087233455062019670620573362768860109890275771463721572578698600501321802550891913369288645565111669790293890107298985819301987334470845204887838326523986148919044265423495050278621214141338819744106934635120845496939830822733488219002062348108603935860045393020164701405072467539274006065291082813376084700667518290775010951235883727637485506655896607963039368820379051422268084714127890377382608847667294781936288634493994597515091795456078934847649806729629586190284753683050015906539243957697001022023), (215079273711572876410986208369683751294908183118379806386470679715006826521170132721726567905439942811382303605708056664603360017394551900388730088190217419850878783175574888901650563370610979038087942241376746471780988908912202971215079064900140401113825730922891606699754858802818433393292483508699051884185015859425552120339604916848864621271989828730706632512180758062407093767038158443746033606152375556179657992769575646334869657982412168590556206097067487695947784501185834313278349861463587166621658897486961285, 165567166071807415210098884820764709496153202096646908950619075676969166055854408565385662974546628510018441833788996418834797201726509458995351065808801225062402256327061845600825747669765288510624735507443675920510399006294180586052938942717561974376882538088092265694134635957495100715662266267357612266079433484517807375368429704206604635121324513004453596132019914682211594230617872219093487683074011218155282605906006194375075803005611967842695926548707579195433499994415413239784543530160970447676692869869775676), (228640244303908717297167044778358038077902415175263705677701277564554270721639076536848778203545648125859327404830206543807475124805809333701155019527553638924049712539331364884394462007690016542789938920025584886621196279327226524440087499458342989252357755491410890483133060523953494059732343775334979996866384865935940617099927020557347955903470709779090391882774438879675954149657556507819136838955515558446346085651316020265457443778053298058612260871138738040683307567599833900424381965386410969307647307369384337, 50165978141277819866049506699428057948802298519848104269621195645506935211584635274953826734316042747547515285609143893926944616496665386006349117172998096582280910144517457297702276740861716885437586834114054074206762165813673080314532603338459131607867567911958178781739505569816626312228165860061197202805933649452157563939564094961259760708185312146707171518968545037144370645198264879962319609864920134620742014988290980148541839415818403783076111150948944201550612135282717822173823751686257249500946118268104684), (260772944033526649752040603039686583353866815340829345188533891968004157467437167053710372219786485894088629376882326037936018907830890211870975702462740982328255444349717705245571849629146899762401559087996404759952457290427825581600106649293512652464779359266335650503918992764721684994867827583945612335934204038413816090349940775896656941750661067477541878792538967929065878101983413114812547001636708105307101185316535811926701056506444389655899925460725232919103379480543873872663434597493298813809089638160216500, 178822297670557205167893884671789644494733002710980842013844409963257117977727466427973839291798664502187859871290871392663447194614632215617775851356048586688401675157884835686198745209102861687009247775089840237122905831291304107610469327023876013149997285955560827672550035934501475882105008318345702835710511139568555607450691543879827538078967647488713788236537917448993732693958930584796688889209027167790147994500386404418863068804471331354407391195350272032834736051454815212017456171393538604058440084178785138), (153951520673385600585961203675637598772601638997436454635342055186847630642649668335965719208548586394720698759337915374432017680802144574982195131450687416186157048436598230083986127273557613203138054681250267787104668155803300164220352768363677389975389879906251331431662461990044058915429571767891876553813802059111070091377174616114219840922496478719633748862558761260936593076772050749815146554186743403077990697502097617642694431073886078861243520255713835477305063044518118066338897871379418786916048308001969642, 156677641648933384765684691841278862645672754960550364491841534426373366855026169555313043450342179770319758154010346709165462884527668929783331518815234286818109634304084831326103818198387741069702702752332554903172870825713486344211463198732464292089738363752466400950781915098607771340376959222392923586445885108829631888240542595711945606244159113099631894036295416012830825883435869636226984125330515770450372976608451137637329197460905623926500239295398492662897852793832046161329679123965719170637821852017541626), (182121275786448274703764860722207288688504251090526347386757201912164299971660589134892392593241000207363015377123532378065868724162125833912530972394915958665480631907067587572014039907112757035041814867937944633329495525743116952775108181544154895419181248880103117645953572669852637658173135330666489107513016628573955811775466684165143992392582744844394450653190459150090420140982302633882320923586679381748714431459394022990660732442705410510333910511438790458145935472292717646314404943912425265028499888510174598, 203440028868962984833821327933789556292629799184980205949050297313869882325162938301832971394230086020203937893809586214315999984427107160219912194805861777145741298008459998847103235243151628211509976280466653813611751247864428514134005135222162797493409369979305348203986570673847042670733283319660635425580706085693423174093318482780132615052711623695122664139057281605247745929023719568948004049990752313628422178360038895083650988297135247676372740583180753811984847210662578351383128821641159416840888477928682078), (218823575478368993955048790301926838437881143334348547262286809656812028268317304117409196876147138768171269470142474896692100140880755219823221990741488174315700621873115881799875553774369475082536987154562339321080637214185501516400621440388225723796980982899499623333730581949456459563202708568004908699142703905181478123703124547955265445070084332319889770567425486299504192535917180867591651719599910708571157067795615339103935726452179859088482325394789423729638822803813023195364259090039516707595275620606223098, 238360831921645517033282852001853402704192593646552818549162257086131847495832206207536403824297663424275603654870000653597808272307859106152007825595353459253005711098749795572570443393454435526757269349583998699531628152424144085951574812986232887851420719883402359586733609130991895552759814577684367961852962954957142339493218345367856462618197020620224169353973697144908034084747802499066704624535556265014878529090655506836355781206186508004035222663675445692924362410085183466479682020421951634577195038189582468), (7605308948924713893554832066864121414252483808305011091620612954856641658669367332357087398584404497275705301412227300132578417133173046053080772734818034453592192660914525809258158102936364260896213514380057335541283089086072298851758871406982865424218623716834685065557610594958011992745774101791101476219252968301741083316175066203079039213553580734030289747773949653701560564634653634860835561109658488968900667869196390219359276163732091789449610499277368225539853863255513232114666428859799256253673733736659934, 84338265593158215073600285774268951532171030715482815121324903198740799001477695481022777242719096465783467452535757377773297443527190828821051666329343779990168147101359925275718790254346877292701611345915823716088047741419538003476861653674067582773629818569266305858464954225803492630796727802186048224313050739888896540519497030255394106498300870595202213057412239405023629489623432730026664229571431460166590904128615265134596663917268529201962732873572258496676098364394367451264108741454944171782819942195095341), (260574236488407935488628660869550896326797079442686943514628661629687399953873851351524123117678854245330138146883940465164632401241414354283763993006051409910547635993821167683763784377300171479035704071118316710560399835534541136502396716751872135374863702011670440373059039486855344367530019761146394096881285791796980662052288525887698305777038723190087660859458441551938560031917347933816170298126009833562473518886720754679296740435464958844554206717306339055626973734868160598112213246395854439553619910006602141, 215031607965289395841597958782668037673484825089737077680116503967686961841667136969161392233440749102334833530419916926904430230760368898665628347399517114710948182534421920881834061302840221573802306449366480749919988514946580495147534756949978412713550979077019198599738941387116501782579306035864628214179812916834096486956736908275485194857938819787685023366084861770486853029181761022412161076373564613780204140998658159981842030287716923797731294561007312770312377377200056945449000311171752181205441965528935874), (198650576114165882449288026892214156276310958538011770523786728908105721360166101586279901877256531212257550264666494397314854415530372455940040150000010464517188336179827548221813135688964063397759290819652552869032850475218576198380858804434982221752101529325232884185525464193387767853411736259300751746214902051788858890055001236520152969180010172699764643110516920458462497046758742780733065725918173268086172671600452269919046762751217264939972190320714063861500100730343214043940778545664923273954431822712458287, 98575677753024287556019342929363679053982268955883779060795868148514132469159057938577626286714738458880375542997435176228749972239849021765147899018326553134629305587630983987645333121909724303395753140044547644366980019247720029923521164816180269979075442608444144431202613744990379185147853120702658487250116464883053687214761782785364318531008585387852132690487409708623886477690527271931747982661236178782523900957816260304362680211164984895592121752024391716149630257731393458732924761811426589241282290399095942), (133239237361361811696048540847458002212650695618301830827793891053639158166896674746134234523487135397403954524183567898886271486999571641531735158385404357658102658615539986689461289623145800299293935203492505727751870154133777899999222627625429326191129944696381042246624406490311860471634501715534659706946193422960549385790867868364451316422996956308516881589568763130787648575177095185336254852857468636860618577916534359157560688439784211466848879111128248465929528606516810076772919357973993801977193176114082633, 91993476954022760012798281670772708974247590300533609094245183822546756179517685689556735104286180548746323121584555720933324078992320978166897622353779701361126291322413292697697396543199293764590408581810818990685090527780478292097542106699940483205806149443174482967568300230425843760446653203856070462189339134604330157898491668720364014222964691584546427448260833308773860654718614894674905336051468516174232055942686622203957221449760803027397791234923638079424420066167267329350115771383830077528497272156638506), (95582621179135234162644663973759115030280708105173042864643748820898368161340863849390296104736276377098268450466214656481306123639700508027953901051290602167543644403815267941649482259183013123386204623097548703992945451692699742180719629475227930324881627331813906906508914901060228391057700936398107111821208803611542219630887301456153687209236199542403045434348094180112509184244726118896660624616403473132543257734828812611125323216911743462747983375152094663325459065388691057143880240380997574071376853464247035, 232352441732141135103454694828789409695750521085516707673246640367598676004047358260302254213092756665608390600758286850148614086134444187559526307489875627257575726111105762131815461870322981755137649000376767125396510619885683103239625485770683659802497093679638121418808084113118832714735551581184248380109440381623813485630097624684044974323307573190413869646763288463464923237420994040221148913548050627902538591565441845343995830686332202964403908307760184053940232271993381347882801989168889743238527356213855452), (258077403654756237716504509389411450264086564167441197441992247041683977605292742137327564976821856572413513401676985367106470072675968010369293214122880029016779939107521858890678568060848094862941480840987133595171797018800289787199783252896262873627767237196210053178254269524723135216496799679281365275621756340432147482265982099094739471498473746177912190376569719635941552555622213874734197454882799555744886325184069583870028520520148657134565959771591400315189969688904284018357614841113544340835425223265680147, 132619711305230755023718414178727374860129372168380541236154544169652117680402142337603417839580343610412910242758120828063112527040245594832613214330126362748191108746206127128051213878124100598393743003465997856657505974679274302377336989381816351610608074708062960998916948448170373532794915312522943031887089971768553107015227988908849150040972068906638987306481505099609598863656873588776064450399947837586887592565715213866014274642313127496432902232963787467375168488326815943797992382485889955510144119668259991)]
enc_flag = 5d130cc326373ca55bc593d06dfe84e33f52b5ef0d1eab5154d47c77c502663bd0a05196f5ad666c69d70ac94dcbb58ada1da640c8df212fd85968ace999e7c70ab1cb8a2050bbe4f82a570936e8b2fd5bf25d376d9cdfeaae1f94b842918ea1
This is the second part of the challenge, which uses ECC to encrypt the flag.
First, we see that it generates two prime numbers $p$ and $q$, then random coordinates for a generator point $G$ of a curve on $N^2 = (p \cdot q)^2$. The $a$ parameter of the curve is generated randomly, but the $b$ parameter is determined by $G$, $a$ and $N^2$ (this is usually done to start with a point that belongs to the curve).
Then, they show us a value master_eye ($m$) which corresponds to the result of multiplying the order of the curve under $\mathbb{F}_p$ and under $\mathbb{F}_q$. And also, they show us that $m \cdot G = O$, The point at infinity (in the curve under $\mathbb{Z}_N$). In some way, this value is like the order of $G$, since by multiplying it times $G$ we obtain the identity element of the group.
Then, the server takes $G$ in the curve under $\mathbb{Z}_{N^2}$ and multiplies this point by 32 random values. Subsequently, it takes the sum of these random values to derive an AES key to encrypt the flag. They give us the result of multiplying all random values times $G$, but not the random values and not even $G$.
Curve parameters
We are in a fairly limited situation, since we have almost no information about the curve. However, we have 32 points (coordinates $\mathrm{x}$ and $\mathrm{y}$) and we know they belong to the curve.
Therefore, we know this:
$$ y_i^2 \equiv x_i^3 + a x_i + b \pmod{N^2} $$
If we use two of the points we have, we can get rid of the parameter $b$:
$$ \begin{cases} y_1^2 \equiv x_1^3 + a x_1 + b \pmod{N^2} \\ \\ y_2^2 \equiv x_2^3 + a x_2 + b \pmod{N^2} \end{cases} \Longrightarrow $$
$$ \Longrightarrow y_1^2 - y_2^2 \equiv x_1^3 - x_2^3 + a (x_1 - x_2) \pmod{N^2} $$
If we do this with two other points, we have a similar equation:
$$ y_3^2 - y_4^2 \equiv x_3^3 - x_4^3 + a (x_3 - x_4) \pmod{N^2} $$
And now we can multiply the first times $(x_3 - x_4)$ and the second times $(x_1 - x_2)$ to be able to eliminate $a$:
$$ \begin{cases} (y_1^2 - y_2^2) (x_3 - x_4) \equiv \left(x_1^3 - x_2^3 + a (x_1 - x_2)\right) (x_3 - x_4) \pmod{N^2} \\ \\ (y_3^2 - y_4^2) (x_1 - x_2) \equiv \left(x_3^3 - x_4^3 + a (x_3 - x_4)\right) (x_1 - x_2) \pmod{N^2} \end{cases} \Longrightarrow $$
$$ \begin{split} \Longrightarrow (y_1^2 - y_2^2) (x_3 - x_4) - (y_3^2 - y_4^2) (x_1 - x_2) \equiv \qquad \qquad \qquad \\ \qquad \equiv (x_1^3 - x_2^3) (x_3 - x_4) - (x_3^3 - x_4^3) (x_1 - x_2) \pmod{N^2} \end{split} $$
Perfect, now we have an equation that is fulfilled and that only depends on the coordinates of 4 points and $N^2$. We can use another 4 points to have similar equations:
$$ \begin{split} \Longrightarrow (y_5^2 - y_6^2) (x_7 - x_8) - (y_7^2 - y_8^2) (x_5 - x_6) \equiv \qquad \qquad \qquad \\ \qquad \equiv (x_5^3 - x_6^3) (x_7 - x_8) - (x_7^3 - x_8^3) (x_5 - x_6) \pmod{N^2} \end{split} $$
If we pass all the terms aside, we have two values that are divisible by $N^2$:
$$ \begin{cases} (y_1^2 - y_2^2) (x_3 - x_4) - (y_3^2 - y_4^2) (x_1 - x_2) - (x_1^3 - x_2^3) (x_3 - x_4) + \qquad \qquad \qquad \\ \qquad + (x_3^3 - x_4^3) (x_1 - x_2) \equiv 0 \pmod{N^2} \\ \\ (y_5^2 - y_6^2) (x_7 - x_8) - (y_7^2 - y_8^2) (x_5 - x_6) - (x_5^3 - x_6^3) (x_7 - x_8) + \qquad \qquad \qquad \\ \qquad + (x_7^3 - x_8^3) (x_5 - x_6) \equiv 0 \pmod{N^2} \end{cases} $$
So, we can use the greatest common divisor (GCD) to recover $N^2$ (well, aactually a multiple of $N^2$, but we can take away the small factors that we have).
Once we have the modulo on which it operates in the curve, it is already easier to find parameters $a$ and $b$ from any two points of the curve. We start from a previous expression:
$$ y_1^2 - y_2^2 \equiv x_1^3 - x_2^3 + a (x_1 - x_2) \pmod{N^2} $$
Since we already know $N^2$, we can calculate multiplicative inverses, and therefore, isolate $a$:
$$ a = (y_1^2 - y_2^2 - x_1^3 + x_2^3) (x_1 - x_2)^{-1} \mod{N^2} $$
And after finding $a$, we can calculate $b$ as follows:
$$ b = y_1^2 - x_1^3 - a x_1 \mod{N^2} $$
All this can be implemented with the following SageMath code:
x, y = [], []
for xx, yy in outputs[:8]:
x.append(xx)
y.append(yy)
kN2 = gcd((x[0] - x[1]) * (x[2] ** 3 - x[3] ** 3 - y[2] ** 2 + y[3] ** 2) - (x[2] - x[3]) * (x[0] ** 3 - x[1] ** 3 - y[0] ** 2 + y[1] ** 2), (x[4] - x[5]) * (x[6] ** 3 - x[7] ** 3 - y[6] ** 2 + y[7] ** 2) - (x[6] - x[7]) * (x[4] ** 3 - x[5] ** 3 - y[4] ** 2 + y[5] ** 2))
N2 = kN2
for pp in primes(1000):
if N2 % pp == 0:
N2 //= pp
N = isqrt(N2)
print(f'N^2 =', N2)
print(f'N =', N)
a = (y[0] ** 2 - y[1] ** 2 - x[0] ** 3 + x[1] ** 3) * pow(x[0] - x[1], -1, N2) % N2
b = (y[0] ** 2 - x[0] ** 3 - a * x[0]) % N2
print(f'{a = }')
print(f'{b = }')
And with this, we get the curve parameters:
$ sage solve_ecc.sage
N^2 = 264565577158994236590031855153889858642149293847448847970649031816068290144718943726237580763969647903770543375415221480423145106277967483944055518720771189157189592025839010707415649298934802554818600881343671391830933519779439364174223387859553464007199819265502917701981157545728448143450273367259289276152361264709006325795000613690279714089006075705019812688622337567736625576157696248463678172321658741121121141186095188499520441835623507334604791145463181077781478470093570533678182144421450743423516076239451209
N = 16265471931640785828934127858946752538285468297743536678369884769134613070708011877740082736319382017849667570641090507172991939418666182470818730451631260930161158328837538561881241462033418605418414010577396121712695567318179840613434951995896817726886735203
a = 255016168931197818685062305277467475939147310316032851940562629263766273806848827361574161304193387338790695002038199730358872156231618756413472252089556793554595535751713490844781606041715667333542594625070573351900213140641050218811210932150487739254199296509019565794946174873502371514562154033669982225110484375322837401197720028302647760803541964996213018205876600519059980832702437327295820859281072782162433368802258604600450884470883303464689592355860840174477238043947992440101763465668785090298241602420559775
b = 50127732115018484203170702229784545965146420529082726037385256846562169633784145549965749115939355046938153878636690046505434313448672070728706649287121339198111456597206969317341833429883720351526802757158855937829665701077162207162706822082172196818620358232889005030349353850169533514493407744045253838278286262204977117355796158321792643972401350420922296278450361220874255243965850220373605475047095584092551599895968561340721051061489824446629675800132597230488528303354169479640856219344579732617565600333600980
Generator point
From the generator point $G$ we know that its coordinates $\mathrm{x}$ and $\mathrm{y}$ are 257-bit integers, And we know that it satisfies the curve equation. In addition, as the curve modulo is $N^2$, which has $2 (2 \cdot 431) = 1724$ bits, we can define the following polynomial:
$$ P(x, y) = x^3 + a x + b - y^2 \mod{N^2} $$
We get a root at $P(G_\mathrm{x}, G_\mathrm{y})$, which is also small compared to the bits that $N^2$ has. Therefore, we can use the Coppersmith method on a bivariate polynomial to find this small root. To do this, we can use defund’s implementation, which admits multivariate polynomials:
load('coppersmith.sage')
P.<Gx, Gy> = PolynomialRing(Zmod(N2))
f = Gx ** 3 + a * Gx + b - Gy ** 2
roots = small_roots(f, (2 ** 257, 2 ** 257))
Gx, Gy = roots[0]
print(f'{Gx = }')
print(f'{Gy = }')
And here we have $G$:
$ sage solve_ecc.sage
N^2 = 264565577158994236590031855153889858642149293847448847970649031816068290144718943726237580763969647903770543375415221480423145106277967483944055518720771189157189592025839010707415649298934802554818600881343671391830933519779439364174223387859553464007199819265502917701981157545728448143450273367259289276152361264709006325795000613690279714089006075705019812688622337567736625576157696248463678172321658741121121141186095188499520441835623507334604791145463181077781478470093570533678182144421450743423516076239451209
N = 16265471931640785828934127858946752538285468297743536678369884769134613070708011877740082736319382017849667570641090507172991939418666182470818730451631260930161158328837538561881241462033418605418414010577396121712695567318179840613434951995896817726886735203
a = 255016168931197818685062305277467475939147310316032851940562629263766273806848827361574161304193387338790695002038199730358872156231618756413472252089556793554595535751713490844781606041715667333542594625070573351900213140641050218811210932150487739254199296509019565794946174873502371514562154033669982225110484375322837401197720028302647760803541964996213018205876600519059980832702437327295820859281072782162433368802258604600450884470883303464689592355860840174477238043947992440101763465668785090298241602420559775
b = 50127732115018484203170702229784545965146420529082726037385256846562169633784145549965749115939355046938153878636690046505434313448672070728706649287121339198111456597206969317341833429883720351526802757158855937829665701077162207162706822082172196818620358232889005030349353850169533514493407744045253838278286262204977117355796158321792643972401350420922296278450361220874255243965850220373605475047095584092551599895968561340721051061489824446629675800132597230488528303354169479640856219344579732617565600333600980
Gx = 187542020032288314214490630204741820227829303492195652833504798640124300158900
Gy = 168843703689929435984972726423710110843417547332425176249556408870268071035700
Elliptic curve factorization method
Before being able to solve the discrete logarithm that will give us the key to decrypt the flag, we need to factor $N$, because to solve the discrete logarithm in the curve under $\mathbb{Z}_{N^2}$ we need to solve it before in the curve under $\mathbb{Z}_{p^2}$ and under $\mathbb{Z}_{q^2}$, and then use the Chinese Remainder Theorem (CRT) to bring together both results.
The factorization of $N$ is something peculiar, since it is necessary to understand how the Lenstra elliptic-curve factorization works:
- If we want to factor a number $n$, we define an elliptic curve under $\mathbb{Z}_n$ and a point $P$ on this curve (we can generate random coordinates $\mathrm{x}$ and $\mathrm{y}$, a random $a$ parameter and then find a $b$ parameter to force the point to be in the curve)
- The goal is to find a couple of points in which the sum of both is not well defined
- To add two points, it is necessary to calculate the slope of the line that joins these points. If this line is vertical, the result is the point at infinity. If it turns out that the GCD of this slope value with $n$ is greater than $1$, the point is not defined. But the important thing is that we will have a factor of $n$
To apply this knowledge to the challenge, we have to remember the value of $m$ (master_eye) which holds that $m \cdot G = O$ in the curve under $\mathbb{Z}_N$:
sage: E = EllipticCurve(Zmod(N), [a, b])
sage: EM = EllipticCurve(Zmod(N2), [a, b])
sage:
sage: G = E((Gx, Gy))
sage: m = 1626547193164078582893412785894675253828546829774353667836988476965589408066956214779521399108300576899339435850978322322115885861611495653342922478
....: 0974963093860223870869151381622793452378040102391285088110131930993214655276327069828109098832154854719776594644
sage: m * G
(0 : 1 : 0)
sage:
sage: P = EM(outputs[0])
sage: m * P
...
ZeroDivisionError: Inverse of 16265471931640785828934127858946752538285468297743536678369884769134613070708011877740082736319382017849667570641090507172991939418666182470818730451631260930161158328837538561881241462033418605418414010577396121712695567318179840613434951995896817726886735203 does not exist (characteristic = 264565577158994236590031855153889858642149293847448847970649031816068290144718943726237580763969647903770543375415221480423145106277967483944055518720771189157189592025839010707415649298934802554818600881343671391830933519779439364174223387859553464007199819265502917701981157545728448143450273367259289276152361264709006325795000613690279714089006075705019812688622337567736625576157696248463678172321658741121121141186095188499520441835623507334604791145463181077781478470093570533678182144421450743423516076239451209 = 16265471931640785828934127858946752538285468297743536678369884769134613070708011877740082736319382017849667570641090507172991939418666182470818730451631260930161158328837538561881241462033418605418414010577396121712695567318179840613434951995896817726886735203*16265471931640785828934127858946752538285468297743536678369884769134613070708011877740082736319382017849667570641090507172991939418666182470818730451631260930161158328837538561881241462033418605418414010577396121712695567318179840613434951995896817726886735203)
We see that errors appear that the point $m \cdot P$ is not defined. We still do not find a factor of $N$, because the error says that there is no inverse of $N$ modulo $N^2$.
What we can do is find some factors of $m$ using factordb.com:
And now, instead of multiplying for $m$, we remove some factor. And after trying a bit, we see a somewhat different mistake:
sage: (m // (2 ** 2 * 3)) * P
...
ZeroDivisionError: Inverse of 3306666750998407949290614826810384435005357289027507523518097170844397310630405493724231782674473208511099023446178055658897571567 does not exist (characteristic = 264565577158994236590031855153889858642149293847448847970649031816068290144718943726237580763969647903770543375415221480423145106277967483944055518720771189157189592025839010707415649298934802554818600881343671391830933519779439364174223387859553464007199819265502917701981157545728448143450273367259289276152361264709006325795000613690279714089006075705019812688622337567736625576157696248463678172321658741121121141186095188499520441835623507334604791145463181077781478470093570533678182144421450743423516076239451209 = 3306666750998407949290614826810384435005357289027507523518097170844397310630405493724231782674473208511099023446178055658897571567*80009749116421201819460392082932543369781073296146200526104333277735370142669725871106604546514530470592721417838917956283421712140325370081541030574865070485541235289513992448161233817820635108170971961669125453845627344044069052189301381281546319302677223308512323449970971168044792073413850208786719548578234348518037138428508360825551264023856385886924097308601393744682119824794566727)
Here we have a factor of $N$:
sage: p = 3306666750998407949290614826810384435005357289027507523518097170844397310630405493724231782674473208511099023446178055658897571567
sage: N % p
0
sage: q = N // p
Discrete logarithm
The last step that remains is to solve a discrete logarithm. The server calculates 32 random values and multiplies them times $G$ in the curve under $\mathbb{Z}_{N^2}$:
$$ \begin{cases} P_1 & = r_1 \cdot G \\ P_2 & = r_2 \cdot G \\ \dots \\ P_{32} & = r_{32} \cdot G \\ \end{cases} $$
Then it uses the sum $r_1 + \dots + r_{32}$ to derive the AES key that encrypts the flag.
An option is to solve 32 discrete logarithms and then add all the results. However, it seems more efficient to add all points $P_1 + \dots + P_{32}$ and solve a single discrete logarithm, resulting in $r_1 + \dots + r_{32}$, because:
$$ P_1 + \dots + P_{32} = (r_1 + \dots + r_{32}) \cdot G $$
Even so, it is not trivial to solve this discrete logarithm because we are in a curve under $\mathbb{Z}_{N^2}$. A curve defined under a composite modulus can be broken down into the “product” of several curves defined under prime modules (more information in crypto.stackexchange.com). A challenge that can serve as an example is Ecchimera from CryptoCTF 2021.
And on the other hand, after investigating how to solve this discrete logarithm, we find a challenge called “pure division” from the zer0pts CTF 2021, and two write-ups that show how to solve it:
In this challenge, a curve defined modulo $p^3$. To solve it, it is necessary to redefine the curve under $\mathbb{Q}_p$ /$p$-adic numbers) with $3$ digits of precision. In this field, discrete logarithm is easy to solve because there is an isomorphism between the points of the curve and $\mathbb{F}_p^+$.
Although the background of the attack is highly complex, the implementation in SageMath is quite simple. For our case, we have to put the points of the curve in $\mathbb{Q}_p$ and $\mathbb{Q}_q$, solve the discrete logarithms and then use the CRT to obtain the result in the curve defined under $\mathbb{Z}_{N^2}$:
sage: EM = EllipticCurve(Zmod(N2), [a, b])
sage: G = EM((Gx, Gy))
sage: P = sum(map(EM, outputs))
sage:
sage: Ep_order = EllipticCurve(GF(p), [a, b]).order()
sage:
sage: EQp = EllipticCurve(Qp(p, 2), [a, b])
sage: pG = EQp(G[0] % (p ** 2), G[1] % (p ** 2)) * Ep_order
sage: pP = EQp(P[0] % (p ** 2), P[1] % (p ** 2)) * Ep_order
sage:
sage: sol_p = ZZ((pP[0] / pP[1]) / (pG[0] / pG[1]))
sage: sol_p * pG == pP
True
sage:
sage: Eq_order = EllipticCurve(GF(q), [a, b]).order()
sage:
sage: EQq = EllipticCurve(Qp(q, 2), [a, b])
sage: qG = EQq(G[0] % (q ** 2), G[1] % (q ** 2)) * Eq_order
sage: qP = EQq(P[0] % (q ** 2), P[1] % (q ** 2)) * Eq_order
sage:
sage: sol_q = ZZ((qP[0] / qP[1]) / (qG[0] / qG[1]))
sage: sol_q * qG == qP
True
sage:
sage: sol = crt([sol_p, sol_q], [p, q])
sage: sol * G == P
False
However, this solution is not correct since the last condition is not met. But the previous conditions are fulfilled.
What is happening here is that this solution is in modulo $N$, and is the result of adding 32 numbers lower than $N$. Therefore, it is expected that the sum is somewhat greater than $N$, and the result we have is smaller:
sage: sol < N
True
So, we can add $N$ to the result until the condition is satisfied (less than 32 iterations):
sage: while sol * G != P:
....: sol += N
....:
sage: sol // N
14
sage: sol
228783371310953134200979693682284782082294455467926861967477800951173709471659482447103308284512776967919781995204775749869580375084462240509528430246695076210060525582252947319050463647309271053406795093984733161889288695889919185344579992689803192397436707284
And that’s it. With this number we can derive the AES key.
Flag
Finally, we can decrypt the flag with AES:
$ python3 -q
>>> from hashlib import sha256
>>> from Crypto.Cipher import AES
>>> from Crypto.Util.Padding import unpad
>>>
>>> key = sha256(b'228783371310953134200979693682284782082294455467926861967477800951173709471659482447103308284512776967919781995204775749869580375084462240509528430246695076210060525582252947319050463647309271053406795093984733161889288695889919185344579992689803192397436707284').digest()
>>>
>>> unpad(AES.new(key, AES.MODE_CBC, b'iseeyou!' * 2).decrypt(ct), 32)
b'HackOn{3r3s_un4_l3y3nd4_d3_l4_cr1pt0_y_s1nc3r4m3nt3_b4st4nt3_r3pt1li4n0}'