Altair626's Blog

SECCON 2020 OnlineCTF Writeup

Altair626 -

2020/10/11(土)15:00~10/12(日)15:00 JSTに開催されたSECCON 2020 OnlineCTFに参加しました。

traP内でメンバーを公募したチームChitandaEruで参加し、501点で正の点数を取った579チーム中58位でした。
私はCryptoのkoharuおよびuraraを解きました。

例年難問ぞろいのSECCONでwarmupでない問題を解くことができたことはかなり励みになりました。これからも精進していこうと思います。
運営および作問者の皆様、お疲れさまでした。また、素晴らしい大会を開催していただき、ありがとうございました。

koharu [crypto,warmup] (144pts, 44solves)

while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")


PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break

while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break

NP = p**P.degree()
NQ = p**Q.degree()

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1

print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)

$\text{GF}(p)[x]/PQ$($PQ$は64次の多項式$P,Q$の積)上で、リスト$c$内の多項式が$S2$か$S2R$かを当てる問題です。

ここで、$R$に関する条件power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1($\text{NP}=\text{NQ}=p^{64}$)が気になります。
与えられた多項式を$\frac{p{64}-1}{2}$乗してみることを考えると、$S2$の$\frac{p{64}-1}{2}$乗は$S{p^{64}-1}\equiv 1$より1に、$S2R$の$S2$の$\frac{p{64}-1}{2}$乗は$R\frac{p^{64}-1}{2}$が残って1でない謎の数になるんだろうなあという気がします。試してみると実際そうなったので勝ちです。

書いたプログラム(sage)は以下の通りです。(プログラム中のc=[..., ...]は文字数の都合で多項式を省略しています)

from Crypto.Util.number import long_to_bytes, inverse, bytes_to_long

p = 4832823609987476353
PR.<x> = PolynomialRing(GF(p))

PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + 1165294508775017303*x^123 + 54498477947855453*x^122 + 564670281176250610*x^121 + 4686383084102262935*x^120 + 4798143559496813901*x^119 + 2373759188753852032*x^118 + 3458843219210551923*x^117 + 3389173528515223367*x^116 + 3175114023644661971*x^115 + 2668820643276713526*x^114 + 1644657084961816584*x^113 + 1949973045428555331*x^112 + 2314884799372359978*x^111 + 1614909032209480656*x^110 + 3706101120120959039*x^109 + 1443476119293487220*x^108 + 507539962924420368*x^107 + 2851578707595377440*x^106 + 2660707099322090529*x^105 + 2275120831055073492*x^104 + 4642644673121099806*x^103 + 780741129747777966*x^102 + 3824963851609159359*x^101 + 1445016816241934269*x^100 + 4706494165496469049*x^99 + 91460120231848540*x^98 + 2033361932245472629*x^97 + 4657205830657809352*x^96 + 627579987075662316*x^95 + 2638155163726745709*x^94 + 773248040814209977*x^93 + 4426134463977473378*x^92 + 1748835523159978170*x^91 + 2545886874835388035*x^90 + 4318027045196127783*x^89 + 529092995613843935*x^88 + 37621695756851259*x^87 + 724317479549357114*x^86 + 235872728824864204*x^85 + 1409136599403563059*x^84 + 984842291673572708*x^83 + 1000642979551429427*x^82 + 2599952022893048437*x^81 + 33489199855748196*x^80 + 2138571356326295553*x^79 + 357904099457660261*x^78 + 1388605866466399741*x^77 + 2123614714168365349*x^76 + 1296407111118101425*x^75 + 3175149128196009486*x^74 + 4407671566428651830*x^73 + 3653949472018283742*x^72 + 2150666969917189331*x^71 + 2425834809198809729*x^70 + 202017664024051124*x^69 + 4656859267960293209*x^68 + 95544718007904685*x^67 + 551963924883187932*x^66 + 1220133766833256737*x^65 + 418789913385574936*x^64 + 3140425594489130574*x^63 + 653426727346469624*x^62 + 2168508737790275670*x^61 + 1350675684196344669*x^60 + 86970043713584944*x^59 + 3125122442296761190*x^58 + 1691082709013935740*x^57 + 14954357710735056*x^56 + 1951640599446313225*x^55 + 3057759244385615044*x^54 + 2842299299534580663*x^53 + 60118912044101305*x^52 + 3791459205438092561*x^51 + 3961025931327708139*x^50 + 3352223936735193809*x^49 + 458087980170556413*x^48 + 303065746752057039*x^47 + 270269323703788403*x^46 + 3435561048914221019*x^45 + 244980776425782882*x^44 + 1756735569264346021*x^43 + 1049402079460555244*x^42 + 1181023304135761892*x^41 + 2480814159047994100*x^40 + 3359295278584507081*x^39 + 1031815312165038169*x^38 + 2284789340145013050*x^37 + 2507227047920435897*x^36 + 4212274843760760739*x^35 + 1874163516348469998*x^34 + 4184876619139253979*x^33 + 2454055493008310058*x^32 + 4810631595605704078*x^31 + 2705618732956794205*x^30 + 4588422028499215564*x^29 + 1362947071518584749*x^28 + 200625668549982104*x^27 + 4162225127389871946*x^26 + 3671964574429446847*x^25 + 497776717675475749*x^24 + 3171362364421276926*x^23 + 4040585504650270495*x^22 + 55143980688943936*x^21 + 1680279432641096886*x^20 + 1141249890787830167*x^19 + 1632171956841566025*x^18 + 4489792289887403690*x^17 + 72863318133800422*x^16 + 3512973315964270180*x^15 + 1880837549990432714*x^14 + 629108155937185931*x^13 + 605563550674482475*x^12 + 3125052390516629852*x^11 + 3434353753938817079*x^10 + 2199180089161294937*x^9 + 4128993677150612079*x^8 + 875038461592559534*x^7 + 1344699457303227348*x^6 + 3605318452000064928*x^5 + 1825112182884559504*x^4 + 4214849563830404245*x^3 + 3018789469914511583*x^2 + 4256870332540451928*x + 3478109193918270445
R = 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + 77535778799313918*x^61 + 3909004297055292936*x^60 + 1574062357470841720*x^59 + 2255026177942473610*x^58 + 2913895405335010190*x^57 + 910153010204378491*x^56 + 4823161627331431259*x^55 + 4314926186108070132*x^54 + 3776194104903441585*x^53 + 4218241384907734159*x^52 + 2928099962473177675*x^51 + 3620663369166129209*x^50 + 4671199329340054093*x^49 + 2953252709684913819*x^48 + 1470028746745533363*x^47 + 393509208258687360*x^46 + 2631641671658679748*x^45 + 4823463900549231672*x^44 + 22025139085889956*x^43 + 3905072220448754367*x^42 + 3525611426409694274*x^41 + 1087703571442464513*x^40 + 983613039355879671*x^39 + 2292836760450398296*x^38 + 2429042383184252432*x^37 + 4241866215562144008*x^36 + 3567456235250802214*x^35 + 289826756486726727*x^34 + 3070079221437908111*x^33 + 3164478508626375897*x^32 + 4028195041942471423*x^31 + 1611744044712776226*x^30 + 682031605725048858*x^29 + 2334009162012075842*x^28 + 1056698946696323305*x^27 + 1193918408929283326*x^26 + 1546583097398597126*x^25 + 632624061599387394*x^24 + 3924194912006864689*x^23 + 836241738980292724*x^22 + 2019639656826418643*x^21 + 646182266409329495*x^20 + 3568811299250961381*x^19 + 4024124722170180214*x^18 + 2765626713849083593*x^17 + 830125243533734584*x^16 + 3773807917205041413*x^15 + 4579071273569219071*x^14 + 4169012455774239610*x^13 + 2779202281389813792*x^12 + 1668767138196611027*x^11 + 3668902156196312613*x^10 + 2118966174503976203*x^9 + 2876683474352545557*x^8 + 4749450906737437136*x^7 + 2048549559963146669*x^6 + 2337906091414592304*x^5 + 3234395871197583532*x^4 + 624006023034932764*x^3 + 1020142386943254010*x^2 + 4346889740151908150*x + 2337193413394346074
c = [..., ...]

NP = p**64
jl = []
for cc in c:
    ro = power_mod(cc, (NP-1)//2, PQ)
    #print(ro)
    jl.append(ro)

#print(jl)
flag_bin = ["1" if i==1 else "0" for i in jl[::-1]]
flag = int("".join(flag_bin), 2)

print(long_to_bytes(flag))

SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}です。

urara [crypto] (240pts, 14solves)

from flag import flag

p = random_prime(1 << 1024)
q = random_prime(1 << 1024)
n = p * q

print("n =", n)

# ---

x = int.from_bytes(flag, "big")
y = randint(0, n-1)

a = randint(0, n-1)
b = (y^2 - (x^3 + a*x)) % n

EC = EllipticCurve(Zmod(n), [a, b])

P = EC((x, y))
Q = 2 * P

print("a, b =", [a, b])
print("Q =", Q.xy())

# ---

m = int.from_bytes(flag, "big")
t = randint(0, n-1)

c = power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)

flagに対して、$\text{GF}(n)$上の楕円曲線を用いた計算と65537乗$(\mod n)$の計算をしています。それぞれの計算と出力されている情報から、flagに関する方程式を得ることを考えます。(方程式中ではflagを$x$と表すことにします)

まず楕円曲線を用いた計算を見ます。output.txtから$a,b$および点$Q$のx座標,y座標($Q_x, Q_y$とします)の値が判明しています。また、点$P$のx座標の値がflagです。
ここで、Q = 2 * Pのx座標に関する計算をうまいこと変形してやると、$$x^4 - 4Q_xx^3 -2ax^2 - (4aQ_x+8b)x + a^2-4bQ_x \equiv 0 (\mod n)$$となります。この方程式の左辺の係数はすべて計算することができます。

次に、65537乗$(\mod n)$の計算を見ます。こちらは与えられたプログラムから明らかに、
$$(x+t)^{65537} - c \equiv 0 (\mod n)$$
です。

あとは、上で求めた2つの方程式を用いてflagを求めます。2つの方程式について、互除法みたいな感じで次数の大きい方を小さい方で割って余りに置き換えることを繰り返して次数を減らしていったところ、$rx+s\equiv 0(\mod n)$の形にできたので、$x\equiv -sr^{-1} (\mod n)$を計算してflagを求められました。

書いたプログラム(sage)は以下の通りです。

from Crypto.Util.number import long_to_bytes, inverse, bytes_to_long

n = 2495486283720196414658156567206136253284019243567958059321851922493511599099119079680539265897209530360296446936208426800428584598438104476991265428916133300767614183255586657557318228860960807727808759584720952822528262134841932977582943502095440882371004412919346559104839698667880585368725210776035801955698546309524104974030342228550787050046049567579065187788994920743809520302849445149655730482323230359606160072691147584028808470430189686361894038637340270209743137983546710783035439259335812370392005195583920997311705713592323771863115626855381027900474814101769171537793566286513448923754562724664313084249
a, b = [972698759004177594974248512452291945375078088533797369007356091167161417126661888563796734970930291849416186353401136601333663184182496443559710260512865444011720544123349975347739686656458945047235004231083887412945922041617098821848109846466185381123572906286526866381831235952511603159063112700803240801865531290422765608302160438343367509056504904308915457764244188011067916227743467457188390983251694692503189881215955070503001896424929414573915023552143884558308649592326241873353092050570518609492131325132956538067260949200100411641491893433056989039052880009034587425997261355587991692486739450094236514758, 1008573312161911000752400660247274100068850370101842340234132233694416751783423219213618251410638912974573281248522724039762013929414424219508458136249643022502332214316678524707691239057071086157162469422064755831275222236081328847657177640054036054045406160824940362440246044883298682522453311877923136432805003451856768017606479097933453907524689590456734108278484158414310289226885363416716427913861763258366781222560451163637643863000635404382308239958732271399310367790172837289160588101927655476531792837448724884102324974548266581640538857040307464673210901987003942198966596512095342443290488073222934653919]
Q = (867873247748174812072354447691943457644353996950272562674084117171032057450250434260859133245258701778341990173401264117064176603158749478700828272476995001485212129112894717807517326303812223951203313709014636942885555951223369106229497656316475383382128690099423171335569734684044941751080119216645566879454705354381241993772833561805053182217457917853140417414526348110486320351897963479122149636934280817200288672007854340543650563779551397976130991102876798375410531876063549460135790157054904126255613039452837589835705186004228042174285947129036321556613553671390037190356528190615214682864974887455909937619, 92156177218703573237225387608427402840283864799028130419669842561042657427033824263488342006248150114770090783060742870361337890590575949279141298574463897596258155388694505972290467228718686940706114514588166273676766526477678084721956511277781446249434968683955693367295727100489236602819441636378541120672736441095144636166942675405988795394557885388103901609694713050343823947711145939998064604641585844723037739727543720657955244689568060357318664843191704220939056774964806734882132924887657592200535178476768157269833478823542760608627255145238265363439669379993951234531206810550094244882515659269421133342)
t = 1777168232191821289919361506719035105250381465284676268198289506955330183480124536544599410896048478441274216496360402574201869585399683211082212730215235958242478585658417025279266624856606193964114464891213954565004165135702759126347979656143036294768812017453240638705726695168190715353794422332588623776474921669253740204759173522894816230138329334719993075279033623376817492761735171138485911978022373863743336360226609344072307935615642938848948516305275434543979476810981458780983782786892497139062392102615609343631554433368313342218231607432462736876822618694937755989879907893923918048177205572935961542238
c = 2495229390232434790849433815327288468942817979063945643796061305651846860246802186265725586015982098870449933396313764591953669092562225099204762704457578001689923221436404745009925073617272135602713059363827274464818599027905362654459980006227162213728037809437236173304627762460414746305401818555455721634808613093466198536909678291636025089911028651869899954385806560064211623734732747231127694454204886697599833768585606205744494003870149200884542308351359803929906608329439509726117597736110772616668829705345022404944932702135376373114568136049373919012494457087384217492589157659130773882703580148119446812556

Q = Q[0]
PR.<x> = PolynomialRing(Zmod(n))

pol1 = x^4 - 4*Q*x^3 -2*a*x^2 - (4*Q*a+8*b)*x + a*a-4*b*Q
print(pol1)

pol2 = (x+t)**65537 % pol1 - c
print(pol2)

pol3 = pol1 % pol2
#print(pol3)

pol4 = pol2 % pol3
#print(pol4)

r = int(pol4 // x)
s = int(pol4 % x)
#print(r, s)
num = (n-s)*inverse(r, n) % n

#print(num)
print(long_to_bytes(num))

SECCON{0n3_tw0_thr33_f0ur_fiv3_six_chachan}です。