はじめに
2024/12/28 23:00(JST)～2024/12/29 23:00(JST) に開催された「ASIS CTF Finals 2024」に参加しました。
ASIS CTFは毎年「Quals」と「Finals」が開催されますが、Qualsの成績（参加したかどうか）にかかわらず、誰でも「Finals」に参加できる点が特徴です*1。
また、毎年夏ごろに開催される「Crypto CTF」も ASIS が主催しているので、スコアサーバーの仕様や Crypto 問の "雰囲気" は「Crypto CTF」とあまり変わりません。
今年は Welcome 以外に 1 問だけ解いたので、その Writeup を記します。
Writeup（Crypto: Prequel）
設問
問題文
The Prequel challenge is an RSA-like cryptosystem that employs primes to encrypt messages; your task is to determine if you can crack it.
さらに、以下の 2 つのファイルが与えられます。
「prequel.py」
#!/usr/bin/env python3 import sys from Crypto.Util.number import * from gmpy2 import * from flag import flag sys.set_int_max_str_digits(31337) def keygen(nbit): p, q = [getPrime(nbit) for _ in '01'] r = getRandomRange(int(sqrt(nbit)) - 6, int(sqrt(nbit)) - 2) el, eu = gmpy2.mpfr(0.313370), gmpy2.mpfr(0.313371) n = p ** r * q LB, UB = gmpy2.mpfr(n ** el), gmpy2.mpfr(n ** eu) while True: d = getRandomRange(int(LB), int(UB)) if gcd(d, (p - 1) * (q - 1)) == 1: e = inverse(d, (p - 1) * p ** (r - 1) * (q - 1)) pkey = (e, n) return pkey, p def encrypt(pkey, m): e, n = pkey return pow(m, e, n) nbit = 313 pkey, p = keygen(nbit) leak = p >> (nbit - 110) m = bytes_to_long(flag) c = encrypt(pkey, m) print(f'{pkey = }') print(f'{leak = }') print(f'{c = }')
「output.txt」
pkey = (944984216927923510201632892590973850396661004462637332470998692449473596147493056311556894274204384772245077199058201622663388870165853321514938390441922867744498045849562497498717541042273278722002724114323618415091788186436761530554704088831215674666508754493615190498409786246565421296815821144500053753541478115299818356208214842787878705507370000629490294894557563667238897580058365172647256838412804911793977543619952840345076821273688643340277663983978371517448815463676125262666981270106439865969562915113205738001725642662329402186543918540592857393236245561690138398624201831557408611329098686349160818187747866456142256107766608245109705394760161152149884966951412665124929307008884695153382823979103652331606374772643625454383796914104674926070440737555826764320704518088196526949189103136022725502727356347447898565076722293345812309904036148668484228145114845351597999627809134413162233694983260023335297935279362831629133363771856519138323406358741822257599256158338525479586263478550717041462562899067010275174754407304718504645899837079557969502458086794913151167168163806285282506054300509388486093311006086376253301164343501616847937093772055957157712109369148744534731794371877307459946892056516053189982899621716318353614392781697596182727270501967480050137271802789989335424116814956605897659695039346323148687277751797419022692731447626006685767185840351540024069735331584364371296637613, 1452555162484423094204272395668825864425858167951825248522254177355034320176317627983704814521987979462679209217224587843692961038072625276289088263063916312454063508971916392662126004169054114695929017189872344842892286936562800914894059094440706797590766534678617438546477291372961430694316631786751565980790336823391361448938562707595799561199804974728837382446309392345427392542054776375430173541164190267637089826224768787716175908383185937154106806666015608403587363740954913044238268027159138149560830255978411373953231081028917316810626513701549109082809033588325835995430775638183746573860855462601730060058435120347307880501033629111555041368645212535321038333226713439706850084390944584620390198451729423255029670597830696884057707298103661063645422201650193037579513548455396626285411554616298390654808282591666199594231724518220087029144900495621196610981488923195891882255051846054094193874725925891053828767058887465063408516838857255119107357554078884804766097567862856413776107172468608979963097253583645713425121828451445286685286957216700892272273593552825477661634343198333035487251526061944732509355481657352585099800059225933115925254158102061140222371901021148054134169351467725305515042483726174527900632582656051498291251313807505045410710795838591329757837318548396644822622741706027733589221502317111724928858949861047058614733251866097738666866237225371884800573975895583145334862421) leak = 796956384442719989903800382564170 c = 38398501009318127402251454303185975044505725081432350072003179352912844506182592025548382411693404106121650125175767577630724584066093007682602717574297661159152529877504145970929948707672120710795817463378725702604444195035278070611986583089799626615006836373315737045972847903057330030714586759298718441702548958143092870823872602673742151510958310995416858464859985704940541327985501673157460094765400202880602253036196854992870865603595310724904723727741990509603676046235020285031674682809676916037159019396902506966869530813777561280788374053428609565028663190600600535950026961420175130542385344783206955617983310086360350162520714760190173399389436035543115475004638417438717844186849132794755110633153868496290621115586696624573124643680384266290308848912781595288421278677349450179551070029795438557683318778608173202855450178371350722473362466795524615544800311313780571398816927500141728472343934416335116140693015632760715583394126989965973932978513042231875305448899469799582957407701353226639056497214505485283678525029670740954711966488522384712245051906041944357637627673748756561944440203114633578364268572508791426432809743171091893729296358440839133044203227653938038939077922999044579549773015685362963501036164991181347497597220000860418745044206521748941309042190678006569494374554817208628917020688605352826432899301626704307738692382180316582310579631651507508469713046192636747409508
問題の分析
問題文にも書かれていた通り、RSA の亜種を扱った問題です。この手の問題は「本来のRSAとの違い」の部分に脆弱性があることが多いので、そこを中心に分析します。
まず、modulus の作り方が特徴的で、p**r*q の形をしています。さらにexponent についても一般的な 0x10001（65537）ではなく、d を先に決めてその値に依存して e が定められています。
提示されたスクリプトに出てくる値の中で、r は明記されていませんが、out.txt に記載された値から計算可能です。具体的には、p, q の bit 数と n の bit 数から、 r=14 であることが判ります。
さらに、LB と UB の値は n から計算できるので、d の値の範囲も計算可能で、1468bit の値になることが確定しています。
また、p の上位 110bit がリークされています。
ここまで分析した結果を踏まえ、雰囲気としては、CopperSmith 法を p もしくは d に適用して、といった感じがします。
検討
d は n に比べそこそこ小さいですが、それでも d のサイズがやや大きいことと、そもそも n の作り方が特殊なため「普通の」Boneh-Durfee 法は適用外となります。
しかし、同じ着想が使えそうなので、もう一度 e, d, p, q の関係を見直すことにします。
n = p**r*q なので、totient（φ(n)）は (p - 1)*p**(r - 1)*(q - 1) です*2。そのため、ある整数 k に対して、e*d - 1 = k*p**13*(p-1)*(q-1)が成り立ちます。左右の bit 数を比較すると、k の bit 数は 概ね d と同じくらいであることが判ります。
Boneh-Durfee 法では、k と s:=(p+q) // 2 を未知数と考え、eを法として CopperSmith 法を適用しますが、右辺の形を見ると s に相当する部分が大きすぎてしまいどうも良くなさそうです*3。
しかし、CopperSmith 法では n の約数を法とした解が算出できることを思い出し、 d を未知数とし pr-1 を法とすれば良さそうだと思って試みることにしました。*4
ソルバ
「solve.py」
from Crypto.Util.number import * pkey = (944984216927923510201632892590973850396661004462637332470998692449473596147493056311556894274204384772245077199058201622663388870165853321514938390441922867744498045849562497498717541042273278722002724114323618415091788186436761530554704088831215674666508754493615190498409786246565421296815821144500053753541478115299818356208214842787878705507370000629490294894557563667238897580058365172647256838412804911793977543619952840345076821273688643340277663983978371517448815463676125262666981270106439865969562915113205738001725642662329402186543918540592857393236245561690138398624201831557408611329098686349160818187747866456142256107766608245109705394760161152149884966951412665124929307008884695153382823979103652331606374772643625454383796914104674926070440737555826764320704518088196526949189103136022725502727356347447898565076722293345812309904036148668484228145114845351597999627809134413162233694983260023335297935279362831629133363771856519138323406358741822257599256158338525479586263478550717041462562899067010275174754407304718504645899837079557969502458086794913151167168163806285282506054300509388486093311006086376253301164343501616847937093772055957157712109369148744534731794371877307459946892056516053189982899621716318353614392781697596182727270501967480050137271802789989335424116814956605897659695039346323148687277751797419022692731447626006685767185840351540024069735331584364371296637613, 1452555162484423094204272395668825864425858167951825248522254177355034320176317627983704814521987979462679209217224587843692961038072625276289088263063916312454063508971916392662126004169054114695929017189872344842892286936562800914894059094440706797590766534678617438546477291372961430694316631786751565980790336823391361448938562707595799561199804974728837382446309392345427392542054776375430173541164190267637089826224768787716175908383185937154106806666015608403587363740954913044238268027159138149560830255978411373953231081028917316810626513701549109082809033588325835995430775638183746573860855462601730060058435120347307880501033629111555041368645212535321038333226713439706850084390944584620390198451729423255029670597830696884057707298103661063645422201650193037579513548455396626285411554616298390654808282591666199594231724518220087029144900495621196610981488923195891882255051846054094193874725925891053828767058887465063408516838857255119107357554078884804766097567862856413776107172468608979963097253583645713425121828451445286685286957216700892272273593552825477661634343198333035487251526061944732509355481657352585099800059225933115925254158102061140222371901021148054134169351467725305515042483726174527900632582656051498291251313807505045410710795838591329757837318548396644822622741706027733589221502317111724928858949861047058614733251866097738666866237225371884800573975895583145334862421) leak = 796956384442719989903800382564170 c = 38398501009318127402251454303185975044505725081432350072003179352912844506182592025548382411693404106121650125175767577630724584066093007682602717574297661159152529877504145970929948707672120710795817463378725702604444195035278070611986583089799626615006836373315737045972847903057330030714586759298718441702548958143092870823872602673742151510958310995416858464859985704940541327985501673157460094765400202880602253036196854992870865603595310724904723727741990509603676046235020285031674682809676916037159019396902506966869530813777561280788374053428609565028663190600600535950026961420175130542385344783206955617983310086360350162520714760190173399389436035543115475004638417438717844186849132794755110633153868496290621115586696624573124643680384266290308848912781595288421278677349450179551070029795438557683318778608173202855450178371350722473362466795524615544800311313780571398816927500141728472343934416335116140693015632760715583394126989965973932978513042231875305448899469799582957407701353226639056497214505485283678525029670740954711966488522384712245051906041944357637627673748756561944440203114633578364268572508791426432809743171091893729296358440839133044203227653938038939077922999044579549773015685362963501036164991181347497597220000860418745044206521748941309042190678006569494374554817208628917020688605352826432899301626704307738692382180316582310579631651507508469713046192636747409508 e = pkey[0] n = pkey[1] #e*d -1 = k * (p-1)*p^13*(q-1) #d: about 1468 bit PR.<x> = PolynomialRing(Zmod(n)) f = e*x-1 #mod n => mod p^13 の解を狙う f = f.monic() d = int(f.small_roots(X=2^1468, beta=0.5)[0]) #betaはテキトーにセットした print(long_to_bytes(pow(c,d,n)))
フラグ
ASIS{F4ct0r!n9_N=p**r*q_F0r_L4rG3_r_BDH_m3Th0d!!!}
おわりに（＋今年の総括）
感想として、本問は「過去の遺産」のおかげで辛うじて解けたような感じでした。しかし裏を返せば、「過去の遺産」を増やせば解ける問題も増えるということになります。
今年は色々と低調で、CTFも「だいぶ伸びしろがある」にもかかわらず、伸びるどころか低迷していた感じがしています。・・・とそう考えるとネガティブな感じになるのですが、視点を変えると「やり方や着眼点を見直す好機」とみることもできます。実は「チャンス到来」だったのかも！
ということで、来年は「読み書き・算盤」（Writeupの読み書きやUpsolve）を中心に、活発な活動を推進したいと思っています。
