今週土日に開催されていたBSides Ahmedabad CTF 2021に出たので自分が解いた問題のWriteupを書きます。

なんと優勝しました、チームとしては初の快挙です。特にPwn担当とRev+Misc担当(ネコチャン)が各分野の数Solves問題を埋めていたのが凄かった、毎度ありがとうございます。

ちなみにAhmedabadの読み方がよくわからなくて「アババババード」とか呼んでたり、"zer0pts CTF 2 2021"と勝手に呼んでたり(実際この記事のリンクは25_zer0pts_2_2021である)しました。ごめんなさい。

(実は"zer0pts CTF 3 2021"があったりしませんか...?)

Table of Contents §

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 $$

ということでで法をとってあげることで、の関係があるので右辺をで割るとフラグが出てくる。

解答スクリプトは以下

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が係数の5次方程式でこれは線形合同法で作られている。ここで次のようにを表現する。

$$ f(x) = g_0 + g_1 x + g_2x^2 + g_3x^3 + g_4x^4 + g_5x^5 \mod p $$

この時各に対して次の関係がある(の時は普通にとする)。

$$ g_i = a^i g_0 + \left(\sum_{j=0}^{i-1} a^j\right) b $$

これでに1から4までを代入するとを変数とする式が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の公開鍵を楕円曲線の法でも用いており、その適当な点に対して次のような暗号化をフラグの各文字に対して行っている。ここでは点のx座標を意味する。

$$ c_i \equiv (m_i \cdot (2^iT)_x)^e \mod N $$

フラグフォーマットがNeko{c00l_l33t_t3xt_by_zer0pts}であることから先頭2文字はNeで確定する。よってこの2文字を既知としてとおくと、次のような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乗はであることからx座標と楕円曲線のパラメータを知っていれば既知になることから元のx座標だけの式になる。

これを下の式に入れてあげるとを変数とした係数多項式が2つ得られる。というわけでFranklin-Reiter Related Message Attackと同じ要領で多項式でGCDを取ってあげれば一次式が現れる事が期待出来る。

無事にを求める事が出来れば、暗号化を再現する事が出来るので、フラグを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...}

感想 §

(前回の記事でこのコーナー廃止するって言ったけどzer0ptsファンボなので書きます)

同じ運営だったzer0pts CTF 2021のCryptoは半分も解けなかったんですが、今回は3/5解く事が出来てよかったです(floorsaは適当に投げたらチームメイトのArkが解いてくれたのでチームとしては4/5解いている)。

...とは言いましたが本音を言うとどうせならThey Were Elevenも解いてCrypto全部解きたかったです。やっぱり格子使うみたいなので格子問題1000本ノックとかで錬成力を鍛えたいところです。

毎週のようにCTFで良い成績を収めているだけでなく、ptr-yudaiさんをはじめとして1年の内に幾つも良質な問題を提供もしているzer0ptsとかいう異常集団の皆さんに敬意を表すると同時に私も彼等を見習いたいです。

定型文になりますが、このような楽しいCTFを開催してくれたzer0ptsの皆様、並びに作問とCTF運営を依頼したBSides Ahmedabadの皆様、本当にありがとうございました。zer0pts CTF 2022を首を長くして待っています。