Writeup: BSides Ahmedabad CTF 2021
今週土日に開催されていたBSides Ahmedabad CTF 2021に出たので自分が解いた問題のWriteupを書きます。
なんと優勝しました、チームとしては初の快挙です。特にPwn担当とRev+Misc担当(ﾈｺﾁｬﾝ)が各分野の数Solves問題を埋めていたのが凄かった、毎度ありがとうございます。
BSides Ahmedabad 2021 is over!
— zer0pts (@zer0pts) November 7, 2021
🥇./Vespiary
🥈Black Bauhinia
🥉Thehackerscew
Thank you for playing it! We're looking forward to reading your write-ups👀 pic.twitter.com/zvhtwo1esY
ちなみにAhmedabadの読み方がよくわからなくて「ｱﾊﾞﾊﾞﾊﾞﾊﾞｰﾄﾞ」とか呼んでたり、"zer0pts CTF 2 2021"と勝手に呼んでたり(実際この記事のリンクは25_zer0pts_2_2021である)しました。ごめんなさい。
(実は"zer0pts CTF 3 2021"があったりしませんか...?)
dlppp §
次のようなスクリプトとその実行結果が配られる
import os
from Crypto.Util.number import getPrime, getRandomNBitInteger
flag = os.getenv("FLAG", "XXXX{sample_flag}").encode()
m = int.from_bytes(flag, 'big')
p = getPrime(512)
y = pow(1 + p, m, p**3)
assert m < p
print(f"p = {hex(p)}")
print(f"y = {hex(y)}")
二項定理を使うと次のような関係がある事がわかる。
$$ y \equiv 1 + mp + O(m^2)p^2 \mod p^3 $$
ということで$p^2$で法をとってあげることで、$y-1 \equiv mp \mod p^2$の関係があるので右辺を$p$で割るとフラグが出てくる。
解答スクリプトは以下
from Crypto.Util.number import long_to_bytes
from xcrypto.mod import legendre_symbol, mod_sqrt
def get_params():
p = 0xa1c8e1e9b2301cb1f5d424ec6d959d7f275e11507b2177d55f3dc1268c9a3164b72832f362975023f09623814f80fe0ffad179d0e51c40b8a1f882d1f5f28e71
y = 0x6fa0fcc8c9c5f695a5709243698d7640c27c45352375919d538137333ab3a2c748cae5e7c1294d6ffc4007476f6fec6421c992f9fe1919b381306300caa2260953e48f2ec0de7b8c6417faa42001a748b1b367f5211095ddd6bf4e681f7e7ad787e0a7f562f6f0307d6a8d7e8d18cd59bd7572f0c4f430f0fd4fc61503b203f3bcd6dd0b0f84bbdbd42126d95b525fe77e4be62c6dbd083dbcaa284b20a9ea6faf9cbaf20dd88b0180417c9021fa1dcb52b2348c4376bd6b9b38a6c860086af
return p,y
def exploit():
p,y = get_params()
m = (y-1) % p**2
print(m % p)
print(long_to_bytes(m // p))
if __name__ == "__main__":
exploit()
Flag: Neko{b1n0m1al_th3or3m0o00oo000ooo00000ooooo00000000n}
(フラグ見てtheoremoonさんの中に"theorem"が含まれている事に初めて気が付いた)
SSSS.RNG §
次のようなSageスクリプトとその実行結果が与えられる。
p = random_prime(1<<512)
a = randint(2, p-1)
b = randint(2, p-1)
x = randint(2, p-1)
def g():
global a, b, x
x = (a*x + b) % p
return x
with open("flag.txt", "rb") as f:
flag = int.from_bytes(f.read().strip(), "big")
assert flag < p
PR.<X> = PolynomialRing(GF(p))
f = g() + g()*X + g()*X**2 + g()*X**3 + g()*X**4 + g()*X**5
vs = [(i, f(i)) for i in range(1, 5)]
print(p)
print(vs)
print(f(flag))
乱数を生成する用のfは$\mathbb Z/p\mathbb Z$が係数の5次方程式でこれは線形合同法で作られている。ここで次のように$f$を表現する。
$$ f(x) = g_0 + g_1 x + g_2x^2 + g_3x^3 + g_4x^4 + g_5x^5 \mod p $$
この時各$g_i$に対して次の関係がある($i=0$の時は普通に$g_0$とする)。
$$ g_i = a^i g_0 + \left(\sum_{j=0}^{i-1} a^j\right) b $$
これで$f$の$x$に1から4までを代入すると$a,b,g_0$を変数とする式が4つも得られるので上手く変形すれば解けそうである。
ただ、これを手計算でやるのは骨が折れるのでグレブナー基底の力を借りる。厳密な定義はよく知らないが、多項式を投げるとそれらが共通解を持つ際に満たす、より簡単な多項式に変形してくれるようなものだと勝手に思っている。Sageには普通に実装があるのでこれを用いると、無事に3つとも求める事が出来るのであとはfを再現してからf(x) = f(flag)となるようなxをSageのrootsメソッドで殴って解く。
a,b,最初のg()の導出Sageスクリプトは以下
def get_params():
p = 2908561168050746475465170048583677924550221390147321314856251074876765877416890922338619139786060615096740196376171212325702080653039392939240436429222829
ct = 708078355843841364722603057137729966137248436075776171805731561888875332687774464375592593202164126123800524500062359645261336234459019198930345744751457
vs = [(1, 1651293975450381579706844999808202297670211173037061827272908790114230592434748044848097133563469251678879059156225205298834971071359017469397331605782920), (2, 49656064002974834481096383104316375265711545391722811288216446968986145936494966876404160910407919885451814058823146922107458035910700220495010462147112), (3, 1481214561214496310917942246038921499126047497749957535731608952096552856013930232284898279007009260107597472601959627310496773682697020898442717240484400), (4, 1950790377868548708758723604473108315857898618124646291056275632619091046294238343215502355242288776617394025418770078552886012721353626716473759644786481)]
return p, ct, vs
def exploit():
p, ct, vs = get_params()
F = GF(p)
PR.<a,b,g0> = PolynomialRing(F)
gs = []
for i in range(6):
b_coef = F(0)
for j in range(i):
b_coef += a^j
gs.append(a^i * g0 + b_coef * b)
fs = []
for i in range(1, 5):
f = PR(0)
for j in range(6):
g = gs[j]
f += g * i**j
v = vs[i-1][1]
f -= F(v)
fs.append(f)
f1, f2, f3, f4 = fs
univar_polys = []
I = ideal([f1, f2, f3, f4])
B = I.groebner_basis()
for b in B:
if b.is_univariate():
univar_polys.append(b.univariate_polynomial())
print(b)
for poly in univar_polys:
print(poly.roots())
if __name__ == "__main__":
exploit()
この結果からフラグを求めるスクリプトは以下
from Crypto.Util.number import long_to_bytes
a_root = [(641724214461003218113945539310238194860679864469327481854320154403983134678980320062912271013383855149918292306265352356945483382063241416831109904295229, 1)]
b_root = [(119820467757789307416070877524965821549643260879972335640852324784389647266877418806534915035503473182406584797844188705350729761732516989804790924202820, 1)]
g0_root = [(511828835501690573161337510945463047263862092635429467649522898889363852744642142921133057604428541928487386432324014697181273298030598539462420470277785, 1)]
p = 2908561168050746475465170048583677924550221390147321314856251074876765877416890922338619139786060615096740196376171212325702080653039392939240436429222829
ct = 708078355843841364722603057137729966137248436075776171805731561888875332687774464375592593202164126123800524500062359645261336234459019198930345744751457
F = GF(p)
a = F(a_root[0][0])
b = F(b_root[0][0])
g0 = F(g0_root[0][0])
gs = [a^i*g0 + b * (a^i - 1) * (a-1)^(-1) for i in range(6)]
PR.<X> = PolynomialRing(GF(p))
f = gs[0] + gs[1]*X + gs[2]*X**2 + gs[3]*X**3 + gs[4]*X**4 + gs[5]*X**5
vs = [(i, f(i)) for i in range(1, 5)]
print(vs)
roots = (f - F(ct)).roots()
for r, e in roots:
print(long_to_bytes(r))
Flag: Neko{7h3_SSSS_way_wa5_imp3rf3c7}
ECC-RSA 2 §
次のようなSageスクリプトが与えられる。
from Crypto.Util.number import getPrime
from hashlib import sha256
import random
def gen_parameters():
p = getPrime(512)
q = getPrime(512)
N = p * q
a = -3
while True:
b = random.randint(0, N)
if (4*a**3 + 27*b**2) % N != 0:
break
x = random.randint(0, N)
while True:
y2 = (x**3 + a*x + b) % N
if Zmod(p)(y2).is_square() and Zmod(q)(y2).is_square():
break
x = random.randint(0, N)
y = CRT([int(Zmod(p)(y2).sqrt()), int(Zmod(q)(y2).sqrt())], [p, q])
return (N, a, b, (x, y))
with open("flag.txt", "rb") as f:
FLAG = f.read().strip()
N, a, b, (x, y) = gen_parameters()
EC = EllipticCurve(Zmod(N), (a, b))
P = EC(x, y)
T = P
ct = []
for byte in FLAG:
r = int(T.xy()[0])
ct.append(pow(byte*r, 65537, N))
T += T
with open("backdoor.txt", "w") as f:
f.write(str(P.xy()))
print(N)
print(a)
print(b)
print(ct)
RSAの公開鍵$N$を楕円曲線の法でも用いており、その適当な点$T$に対して次のような暗号化をフラグの各文字$m_i$に対して行っている。ここで$P_x$は点$P$のx座標を意味する。
$$ c_i \equiv (m_i \cdot (2^iT)_x)^e \mod N $$
フラグフォーマットがNeko{c00l_l33t_t3xt_by_zer0pts}であることから先頭2文字はNeで確定する。よってこの2文字を既知として$m_0, m_1$とおくと、次のような2つの式が立つ。
$$ \begin{aligned} c_0 &\equiv (m_0 \cdot T_x)^e \mod N \cr c_1 &\equiv (m_1 \cdot (2T)_x)^e \mod N \end{aligned} $$
ここでは式の正しい表現は詳しく書かないが、楕円曲線の2倍算のx座標は、元の点における傾きとx座標に依存し、更に傾きは元の点におけるx座標とy座標の2乗に依存する。特にy座標の2乗は$y^2 \equiv x^3 + ax + b \mod p$であることからx座標と楕円曲線のパラメータを知っていれば既知になることから元のx座標だけの式になる。
これを下の式に入れてあげると$T_x$を変数とした$\mathbb Z/N\mathbb Z$係数多項式が2つ得られる。というわけでFranklin-Reiter Related Message Attackと同じ要領で多項式でGCDを取ってあげれば一次式$x - T_x$が現れる事が期待出来る。
無事に$T_x$を求める事が出来れば、暗号化を再現する事が出来るので、フラグを1文字ずつ暗号化しているという特徴から総当りしながら暗号化を行い、暗号文と一致したものがフラグの対応するインデックスの文字になる。
(蛇足) なお、暗号化スクリプトではTの倍算を行っているが、x座標しか使わないので↑で書いたのと同様の理由でTを求めなくともそのx座標だけで良い。そもそもNの素因数分解に成功しないとTを求める事は出来ない(し、「素因数分解が出来るならRSAが復号出来る」は真だが、「RSAが復号出来るなら素因数分解が出来る」は真ではないので素因数分解も難しい)。
Tのx座標の導出を行ったSageスクリプトは以下
def get_params():
N = 77442460850212773085794635801375958845804707324993357281208194551623657239187349312436696241935186166257591258504749545772004295327768144396282976900520432732812806363533815251339418767473076011913487178468095959185644823866637334571397649439304806976102102648089122600431404774320176332888332026871462714241
a = -3
b = 43578632266128244820417508517042181755548611175192225705779617200211657490732773312201748031199866345732692087242358575000478046482017387745781434943027615258011975018844134398549042530691348612104431176684289790039020991799641531076390867070455143909432946642413870202048257142913333962443315780842386642355
ct = [21697086857122395176967434654620494627649522148784334045225979449081521488425867082556155818341337071695052689435277079021315588247445055792538963495385773534313807325428840566239154599652446828845504373246944071942414868125146072186227947915771087841250919586422115933424816104302793374958996770253881538673, 49266477054257074473484818561542862745662164231714071140708510651506917381315846662378148841703551424449488467221139483391935479888005959017268552566263422337725411476118524905454705883034549736801225658230078676793857361511433206436194566028594273717701913976245784854561523123789898473908838946902331239866, 7028603282358377495992448362382680390936488310246693315946536533009869131409339287743826905497617870069227204058010261234048284371746377537207831676416633787839846455957555930933160453028689071471311111465411188786513962789048766343384192674592887535558074190054508704985519643182566020856627025680632717108, 9050513336296157318966296526057766469795700863500311709011501078551269762419051027920152087634110021002155294396880732088737967114468704530149483319349124108635470983622198438374066941409351854232260998138763975368301797611951517123629772690822424527049219295311881636461980964393606244977156016351237130197, 23722314062555797757055550662032306586520729360778729513752662310125207625493153569344377395808876436885009166977305311030548086876148175329723072006713368012957948111405386576111829480888205290121863395502615092335120796113485396854148984265743154783580839343811115943714225834266064887917047352644157273663, 48520278189315027327894817534851811386313455146699473585424759278836581631834438215028127659907900773403588324713292043072158488639065137602589232334973598468868368868136595807057994768429695117828412579079416200994227636569324964253500177172162270428920418426521656920672461006572251311690498664259670047980, 70423420620276667958899540113166650749957929584320150452943858737019383323207499966037876331842403163896499411502109376042824370402486300015740045806940140883733761725512912671748019148243843240244347716263816398921415127590424564797474114183353623066292171563478747321244668431370593105073524158099680056094, 57677175743132749817331439822970399665404659767046232400429832271041195310159089504574259505839084395228911752958507363083336972538201432695022461280332212130366416141270136752966718318403591384030664906091824255129612295114139331552088520212323865083621659804807770884683449176042760776091854350083404924526, 48354495178825278561692284169233799680622346657017913645204626826186497975565663619029875724669403687881970079897883293075146579126533817892089793279733363828408186593189195318954989827811320586492365150403733361547513650329301069490776474167215307681091587669251138748148858280899282502778544617558206176985, 1336327070743151440916617006304633049523288270254562619190505707777800363977169223021523664064422394562408942874379817062606914194110006907256790564444251004706650094461726630985127782720094405534102852096565040244032680101823175338348529940773275112987271095199550382938852717124375367419138758827097381326, 22760224598067669674305741702965291613331728388294897519447863109696221098333759497452621578774373773250101299991412772367782521770750361046473223867254433118765828070168648680678074827678440816751913544852035837349689096839207930817492399262281578274080957167437289055817376627972980114169584412913968596087, 20595419914155552122877178467755568327152986831708305559340422283926560694627270816462357267364236257470552002381229962748461690478009845199170539143639091918892701434609808867056555409830377497559339044914484597058922482082417592744879083865810837754882387331203935527031110633228009257751264110797024578546, 25341140433014189989539932622500525293113873724972520359086922367924765292994134658438594704158349050190077806366632880963354528018912600358363187448424946962830493706447927874182406022016651649937946717954501209628113046418365164418483361453447889945650700721266118320463924797134271804385670622074565525299, 71177191510640698209863633991256798030200830943142635980027827377414887327579322925925041100506625306452720432569227645732694589215198378402426340400034611720273771011214479201021796422897920411600541006640452747214631793185643377098295849946535998565149249087257863500584983482668519466975765027864589716603, 28599620011804748257313773437078902860397585079299694804300901895147953889926640911593765330517566142707703195092261714644430345907857500070711907828586251177700802862846698634554873409516111081020436277706557672977471490398114685796200916967614622480361351924590483220123264063528533265260362384684263800167, 12253071305410566000639366028350424805155969567562548980487831660524498693689110406039973400134500275712162879393203338094990190978153116504275873511361544692198275051840929761621481573906987661703495903975204878839448224500251350920297587092074190965754981083015315405441492078177074234542052215647621496585, 69112545215140921979983409479033847146003961977233512471297180413815073274242067103795128200730774476345874423963236188960204157437697130322001813035817863785743899181146621118703838005673921929913090825444416288486362059100550311210988610439523180250495676126782785496304292282611950253143881533809309928052, 69966966847614763608073934644371139411463966772615917698612160736399260611565727828099311133390625931472347586254004631142595139970212250775393559262362108676974112023605859835683673130044617900653097579450403529328466613272159668601435242212668737398593910016275915935825126445999512561319770695779206294321, 73299451247510112208904286839181644749199582703719760611429444984804522606405642806033385280377834864514177346267610600726260362817691148922074682132502741862762463570547976082090825815142699899229153329925218724349240307305526021081315530509258175808474910828607629182191198897682198942350885864182628414007, 15616895810808341127764523917074295722136514038191384427000989308264246551792287242058240838534867994602032950960162168844427847817650720837354115976748805960373558190795740222223462376337253107739393485599799897893081874041348077165849860285675462769699066262256208579934583462636625005079624819560028588822, 1438419812071321050059639600278300222339302430716296518316583813588978289559379648962959942934778655009356910585074502145450955001392172672968677179576642798657895449546375502184957867174869040473533810227435579344138056983619652266840621426289618728238980715075056867694562686439781059289518624264781471122, 67996372510707957033060006799149976198282432792896793893101172214439399239528737106624385787438209697098271510620852570441849049544757836991721488854258930308064842963680483282975368155496540614262813644105532116947927151417398714970926667876453972699142502693269556975398296783029326970981791048240201224668, 43883291787408400200588525004386324919448363888776368356357239426167080976315192631213850232267311093476357006059205124005139395089873825866916668841660221456615724745312049204469066643807628702196055081686171468924594661526166240384811598448997207523186388904847912135907422789333573322493636857490033986154, 67760404563554578712047321493191166528018027359412851873668792914055026026286133561688226044425157590397255163185385368549813609161563689118682309664175098646271267445318421021048868742191079429919059652408943738239946909506045163027883015223495051587552609473275289004769239176900778500331417787966243057752, 33583107239590636118967771943982087324812780763028518394246376247731875865144427658491118537828931357539913376664949677961860227170046038707611331705642763909436254147657442466665049334653504004141339308372954659079831857713886693721013067331470196418010765868420007458522210229965617355629675477446001844210, 71862354059694341271875565922320556520854884699515866328747873150089326649147156830602967576658160700322807580886662752329966703026537836315877831776160002191233653472779456318405902629658827055463682614213384824542999366558332546878741780653013041663166059700695124133828487163337219758698715945177800260643, 4389650202426709688781610829889924871717394700561976928740907540453643682729275832551097553798461339373259098778642849458063901076441364987954274664893481147223793554328969936134568234935313468309239201579124009602857926470890061028501014400155764364369701734260211119747381524254600318062049201492458928576]
return N, a, b, ct
def poly_gcd(a, b):
cnt = 0
while b:
if cnt % 100 == 0:
print(cnt)
a, b = b, a % b
cnt += 1
return a.monic()
def exploit():
N, a, b, ct = get_params()
known = b"Neko{"
R = Zmod(N)
curve = EllipticCurve(R, (a,b))
e = 65537
PR.<x> = PolynomialRing(R)
x_e = ct[0] * (R(known[0]))^(-e)
f0 = x^e - x_e
f1_lhs = ((x^2 - a)^2 - 8*x*b)^e * (R(known[1]))^e
print("[+] f1_lhs is prepared")
f1_rhs = ct[1] * 4^e * (x^3 + a*x + b)^e
print("[+] f1_rhs is prepared")
f1 = f1_lhs - f1_rhs
print("[+] f1 is prepared")
r = poly_gcd(f0, f1)
print(r)
if __name__ == "__main__":
exploit()
フラグの復号を行ったスクリプトは以下
def get_params():
N = 77442460850212773085794635801375958845804707324993357281208194551623657239187349312436696241935186166257591258504749545772004295327768144396282976900520432732812806363533815251339418767473076011913487178468095959185644823866637334571397649439304806976102102648089122600431404774320176332888332026871462714241
a = -3
b = 43578632266128244820417508517042181755548611175192225705779617200211657490732773312201748031199866345732692087242358575000478046482017387745781434943027615258011975018844134398549042530691348612104431176684289790039020991799641531076390867070455143909432946642413870202048257142913333962443315780842386642355
ct = [21697086857122395176967434654620494627649522148784334045225979449081521488425867082556155818341337071695052689435277079021315588247445055792538963495385773534313807325428840566239154599652446828845504373246944071942414868125146072186227947915771087841250919586422115933424816104302793374958996770253881538673, 49266477054257074473484818561542862745662164231714071140708510651506917381315846662378148841703551424449488467221139483391935479888005959017268552566263422337725411476118524905454705883034549736801225658230078676793857361511433206436194566028594273717701913976245784854561523123789898473908838946902331239866, 7028603282358377495992448362382680390936488310246693315946536533009869131409339287743826905497617870069227204058010261234048284371746377537207831676416633787839846455957555930933160453028689071471311111465411188786513962789048766343384192674592887535558074190054508704985519643182566020856627025680632717108, 9050513336296157318966296526057766469795700863500311709011501078551269762419051027920152087634110021002155294396880732088737967114468704530149483319349124108635470983622198438374066941409351854232260998138763975368301797611951517123629772690822424527049219295311881636461980964393606244977156016351237130197, 23722314062555797757055550662032306586520729360778729513752662310125207625493153569344377395808876436885009166977305311030548086876148175329723072006713368012957948111405386576111829480888205290121863395502615092335120796113485396854148984265743154783580839343811115943714225834266064887917047352644157273663, 48520278189315027327894817534851811386313455146699473585424759278836581631834438215028127659907900773403588324713292043072158488639065137602589232334973598468868368868136595807057994768429695117828412579079416200994227636569324964253500177172162270428920418426521656920672461006572251311690498664259670047980, 70423420620276667958899540113166650749957929584320150452943858737019383323207499966037876331842403163896499411502109376042824370402486300015740045806940140883733761725512912671748019148243843240244347716263816398921415127590424564797474114183353623066292171563478747321244668431370593105073524158099680056094, 57677175743132749817331439822970399665404659767046232400429832271041195310159089504574259505839084395228911752958507363083336972538201432695022461280332212130366416141270136752966718318403591384030664906091824255129612295114139331552088520212323865083621659804807770884683449176042760776091854350083404924526, 48354495178825278561692284169233799680622346657017913645204626826186497975565663619029875724669403687881970079897883293075146579126533817892089793279733363828408186593189195318954989827811320586492365150403733361547513650329301069490776474167215307681091587669251138748148858280899282502778544617558206176985, 1336327070743151440916617006304633049523288270254562619190505707777800363977169223021523664064422394562408942874379817062606914194110006907256790564444251004706650094461726630985127782720094405534102852096565040244032680101823175338348529940773275112987271095199550382938852717124375367419138758827097381326, 22760224598067669674305741702965291613331728388294897519447863109696221098333759497452621578774373773250101299991412772367782521770750361046473223867254433118765828070168648680678074827678440816751913544852035837349689096839207930817492399262281578274080957167437289055817376627972980114169584412913968596087, 20595419914155552122877178467755568327152986831708305559340422283926560694627270816462357267364236257470552002381229962748461690478009845199170539143639091918892701434609808867056555409830377497559339044914484597058922482082417592744879083865810837754882387331203935527031110633228009257751264110797024578546, 25341140433014189989539932622500525293113873724972520359086922367924765292994134658438594704158349050190077806366632880963354528018912600358363187448424946962830493706447927874182406022016651649937946717954501209628113046418365164418483361453447889945650700721266118320463924797134271804385670622074565525299, 71177191510640698209863633991256798030200830943142635980027827377414887327579322925925041100506625306452720432569227645732694589215198378402426340400034611720273771011214479201021796422897920411600541006640452747214631793185643377098295849946535998565149249087257863500584983482668519466975765027864589716603, 28599620011804748257313773437078902860397585079299694804300901895147953889926640911593765330517566142707703195092261714644430345907857500070711907828586251177700802862846698634554873409516111081020436277706557672977471490398114685796200916967614622480361351924590483220123264063528533265260362384684263800167, 12253071305410566000639366028350424805155969567562548980487831660524498693689110406039973400134500275712162879393203338094990190978153116504275873511361544692198275051840929761621481573906987661703495903975204878839448224500251350920297587092074190965754981083015315405441492078177074234542052215647621496585, 69112545215140921979983409479033847146003961977233512471297180413815073274242067103795128200730774476345874423963236188960204157437697130322001813035817863785743899181146621118703838005673921929913090825444416288486362059100550311210988610439523180250495676126782785496304292282611950253143881533809309928052, 69966966847614763608073934644371139411463966772615917698612160736399260611565727828099311133390625931472347586254004631142595139970212250775393559262362108676974112023605859835683673130044617900653097579450403529328466613272159668601435242212668737398593910016275915935825126445999512561319770695779206294321, 73299451247510112208904286839181644749199582703719760611429444984804522606405642806033385280377834864514177346267610600726260362817691148922074682132502741862762463570547976082090825815142699899229153329925218724349240307305526021081315530509258175808474910828607629182191198897682198942350885864182628414007, 15616895810808341127764523917074295722136514038191384427000989308264246551792287242058240838534867994602032950960162168844427847817650720837354115976748805960373558190795740222223462376337253107739393485599799897893081874041348077165849860285675462769699066262256208579934583462636625005079624819560028588822, 1438419812071321050059639600278300222339302430716296518316583813588978289559379648962959942934778655009356910585074502145450955001392172672968677179576642798657895449546375502184957867174869040473533810227435579344138056983619652266840621426289618728238980715075056867694562686439781059289518624264781471122, 67996372510707957033060006799149976198282432792896793893101172214439399239528737106624385787438209697098271510620852570441849049544757836991721488854258930308064842963680483282975368155496540614262813644105532116947927151417398714970926667876453972699142502693269556975398296783029326970981791048240201224668, 43883291787408400200588525004386324919448363888776368356357239426167080976315192631213850232267311093476357006059205124005139395089873825866916668841660221456615724745312049204469066643807628702196055081686171468924594661526166240384811598448997207523186388904847912135907422789333573322493636857490033986154, 67760404563554578712047321493191166528018027359412851873668792914055026026286133561688226044425157590397255163185385368549813609161563689118682309664175098646271267445318421021048868742191079429919059652408943738239946909506045163027883015223495051587552609473275289004769239176900778500331417787966243057752, 33583107239590636118967771943982087324812780763028518394246376247731875865144427658491118537828931357539913376664949677961860227170046038707611331705642763909436254147657442466665049334653504004141339308372954659079831857713886693721013067331470196418010765868420007458522210229965617355629675477446001844210, 71862354059694341271875565922320556520854884699515866328747873150089326649147156830602967576658160700322807580886662752329966703026537836315877831776160002191233653472779456318405902629658827055463682614213384824542999366558332546878741780653013041663166059700695124133828487163337219758698715945177800260643, 4389650202426709688781610829889924871717394700561976928740907540453643682729275832551097553798461339373259098778642849458063901076441364987954274664893481147223793554328969936134568234935313468309239201579124009602857926470890061028501014400155764364369701734260211119747381524254600318062049201492458928576]
x = -15422689843057186526125928976412696423719449572871212994524208651089235235524114374841595164195609855981759086265794722937874432427319968926596091659119739005498089352389836593636671446811728461522564569376251264182548473226361310129103073632388260872721658116094274497662379838358295811723735790269793030043
return N, a, b, ct, x
def exploit():
N, a, b, ct, x = get_params()
known = b"Neko{"
R = Zmod(N)
curve = EllipticCurve(R, (a,b))
e = 65537
x = R(x)
a = R(a)
b = R(b)
next_x = lambda _x: ((_x^2 - a)^2 - 8 * _x * b) * (4 * (x^3 + a*x + b))^(-1)
flag = ""
for i in range(len(ct)):
r = int(x)
for byte in range(0x20, 0x7f):
c = pow(byte*r, e, N)
if ct[i] == c:
flag += chr(byte)
print(flag)
break
x = next_x(x)
if __name__ == "__main__":
exploit()
Flag: Neko{h4lf_gcd_g0es_brrr...}
Thanks for reading! Read other posts?