1. はじめに
2022/11/19(土)15:33 JST ～ 17:13 JSTに開催された「TSG LIVE!9 CTF」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記です*1。
2. 参戦準備について
日ごろから Twitter で「TSG」を叫び続けていたので、参加するか参加するか参加するかの三択でした。ですので、「参加する」を選びました。
しかし、前日の疲労がヤバいレベルで HP も MP もほぼ空だったので*213:30くらいから昼寝をしていたのですが、気が付いたら15:15で起床事故寸前でした。あぶねー。
とりあえず、「途中離脱せず、100分もたせる」ため甘味（アルフォート）を補給しました。なお、恒例である「ゲン担ぎのカツ」は前日・前々日に食したのでカツ愛、もとい割愛です。
そんなこんなで、15:28にはどうにか体制を整えることはできました。間に合ったからヨシ！
3. 15:43 Solved (Crypto: rsa_debug?）
いつものとおり、Crypto 全完を目標として、まずは「rsa_debug?」に着手しました。
ファイル：「problem.py」
def my_pow(a, n, m): result = 1 while n > 0: if n % 2 != 0: result = (result + a) % m # omg! a = (a + a) % m # oops! n = n // 2 return result from Crypto.Util.number import getPrime, bytes_to_long p = getPrime(512) q = getPrime(512) N = p * q phi = (p - 1) * (q - 1) e = 0x101 d = my_pow(e, -1, phi) with open('flag.txt', 'rb') as f: flag = bytes_to_long(f.read()) c = my_pow(flag, e, N) print(f'N = {N}') print(f'e = {e}') print(f'c = {c}') if my_pow(c, d, N) != flag: print('there is a bug i guess lol')
ファイル：「output.txt」
N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591 e = 257 c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363 there is a bug i guess lol N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591 e = 257 c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363 there is a bug i guess lol
「オレオレ pow 関数」が肝ですが、コーディング力ヨワヨワ*3なのでよく読めず、1、2、3、 10 とか テキトーに数字入れてみてどんな関数なのかを探っていました*4。
my_pow(m,e,n) = m*e + 1 であると確信したので、m = (c-1) // e で算出できました。
※終わってから眺めてみると、そういえば楕円曲線のスカラー倍を自力実装するときよく見かけるコードで、確かに乗算を計算するものでした。
思考の経緯を省略してソルバの形にまとめると、以下のようになります。
ソルバ：
from Crypto.Util.number import * N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591 e = 257 c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363 m = (c-1) // e print(long_to_bytes(m).decode())
TSGLIVE{g0od_Mult1plic4t10N-Algor1thm_6y_ru55iAn_Pea5ants}
TSG にしては優しめ*5の問題でした。
ペースはまぁ普段通り「ボチボチ」ですが、今後 RTA を駆けるのなら 3 倍速は欲しいかなと思う次第。
4. 15:55 Solved (Crypto: rsa_debug??）
とりあえず 1 問解けたので、次の「rsa_debug??」に着手しました。前問とよく似ていますが、「オレオレ pow 関数」の中身が異なっています。
ファイル：「problem.py」
def my_pow(a, n, m): result = 1 while n > 0: if n % 2 != 0: result = (result * a) % m a = (a + a) % m # oops! n = n // 2 return result from Crypto.Util.number import getPrime, bytes_to_long p = getPrime(512) q = getPrime(512) N = p * q phi = (p - 1) * (q - 1) e = 0x101 d = my_pow(e, -1, phi) with open('flag.txt', 'rb') as f: flag = bytes_to_long(f.read()) assert flag.bit_length() <= 400 c = my_pow(flag, e, N) print(f'N = {N}') print(f'e = {e}') print(f'c = {c}') if my_pow(c, d, N) != flag: print('there is a bug i guess lol')
ファイル：「output.txt」
N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727 e = 257 c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600 there is a bug i guess lol
前問同様、1、2、3、10 とかテキトーに数字入れてみてどんな関数なのかを探ったところ、前問より少してこずりましたが、（e=257 のときは）my_pow(m,e,n) = (e-1)*m2 のような動きをしていることが分かったので、c // (e-1) の平方根を計算してみたところフラグをゲットできました。
※なお、上の関係式は e = 2k+1 型の時成り立つようです。
ソルバ：
from Crypto.Util.number import * import gmpy2 N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727 e = 257 c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600 m_ = c // (e-1) m = gmpy2.iroot(m_,2)[0] print(long_to_bytes(m).decode())
TSGLIVE{Th1ng5_cOmE_1n_thr33s..._but_H0w?}
当面の目標である「Crypto 全完」が見えてきました。
5. 16:05頃 Solved (Crypto: Ta-Shi-Ma-Ku-Ri SAtursday!）
順当に!?、Crypto 問のラスト「Ta-Shi-Ma-Ku-Ri SAtursday!」を解きました。
ファイル：「problem.py」
from Crypto.Util.number import getPrime, bytes_to_long from random import randint p = getPrime(2048) q = getPrime(2048) N = p * q e = 65537 with open('flag.txt', 'rb') as f: flag = bytes_to_long(f.read()) c = [] for x in range(3): m = 0 for i in range(x // 2): m += flag for i in range(randint(1, 100)): m += p for i in range(randint(1, 100)): m += q c.append(pow(m, e, N)) print(f'N = {N}') print(f'e = {e}') print(f'c = {c}')
ファイル：「output.txt」
N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529 e = 65537 c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033]
c には 3 つの値が入っていますが、最初の 2 つは (a * p + b * q)e の形の数で、最後の 1 つは (F + a * p + b * q)e （F:フラグ）の形をしています（1≦a, b≦100）。
解法はシンプルで、もしc[0]=(a * p + b * q)e、c[1]=(s * p + t * q)e ならば (te * c[0] - be * c[1]) % N は p の倍数となりますので、1 ≦ b, t ≦ 100 で x :=GCD( (te * c[0] - be * c[1])%N, N) を全探索し、1< x < N となる x が見つかればそれが p に該当*6します。
p がわかれば q がわかり、phi = (p-1) * (q-1) が計算できるので RSA 復号処理ができるようになります。
c[2] を RSA 復号処理の後、フラグに足された部分（a * p + b * q）を 1≦a, b≦100 総当たりで減じてみて、「long_to_bytes したとき b"TSGLIVE" を含むもの」を正解と見立てます。なお、long_to_bytes がコケるかもしれないので、try ～ catchで括っています。
ソルバ：
N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529 e = 65537 c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033] from Crypto.Util.number import * for b in range(1,100): for t in range(1,100): x = (c[0] * pow(t,e,N) - c[1] * pow(b,e,N)) % N if GCD(x, N) != 1: p = GCD(x, N) break q = N // p phi = (p-1)*(q-1) d = inverse(e, phi) m_ = pow(c[2], d, N) for a in range(1,100): for b in range(1,100): m = m_ - a*p - b*q try: if b"TSGLIVE" in long_to_bytes(m): print(long_to_bytes(m).decode()) exit() except: pass
TSGLIVE{p_and_Q_Mu5t_6e_1nFiN1Tesim41_nUmb3Rs_Becau53_pq_acts_Lik3_a_zer0}
好物である「RSA 問」の中でも、特に好きなタイプの問題でした。
6. まだだ、まだ終わらんよ！（Rev: angry）
この段階でまだ時間があったので、もう 1 問くらい行きたいと思いました。「angry」に取り組みながら他の問題を見ていましたが、結果的に何もできず、ここで打ち止めとなりました。無念。
ということで、残り時間は「まだだ、まだ終わらんよ！」と（いつも通り）心で叫びながら、ひたすら angr をぶん回していました。競技終了まで、地球温暖化の促進に貢献していました。ネオジオン万歳！
・・・嘘です。他の方の Writeup みながら反省会しますので許してください。
7. 結果
Crypto 全完のみで 700 点、11位でした。
結果はともかく、TSG ファンクラブ会員（自称）としては、TSG のイベントを楽しめたのでヨシ！もうこれに尽きます。
次の TSG CTF が楽しみです。次の TSG CTF が楽しみです。（大事なことなので２回言いました。）
