MapleCTF 2022の振り返り - アロワナ飼いたい

■ 概要

先日行われたMapleCTF 2022のメモ。解けた問題に対するアプローチや感想などをまとめる。　なお、sanity checkを除いてたった1問しか解けなかったため、非常に内容の少ない記事となった。最終順位は234位（チーム：4r0wana）。

■ brsaby（Crypto）

以下のようなスクリプトファイル（script.py）が与えられる。

from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

msg = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
N = p*q
e = 0x10001
enc = pow(msg, e, N)
hint = p**4 - q**3

print(f"{N = }")
print(f"{e = }")
print(f"{enc = }")
print(f"{hint = }")

'''
N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282
'''

通常のRSA暗号の問題と同様で、 $N$ を素因数分解できればフラグを求められる。
$p$ と $q$ を求めるヒントとして、 $h = p^{4} - q^{3}$ の値が与えられている点がポイントである。

まず、 $N= pq$ 、 $h = p^{4} - q^{3}$ という関係式から、変数が $p$ だけの式を作ることを目指してみる。 $p^{3} q^{3}=N^{3}$ であり、 $q^{3}=p^{4}-h$ であるから、以下が成り立つ。

$\displaystyle p^{3}(p^{4}-h) = N^{3}$

上記を変形すると、 $p$ に関する7次方程式となる（ $h$ と $N$ は既知の定数）。

$\displaystyle p^{7}-hp^{3} - N^{3} = 0$

この方程式の解の一つが $N$ の素因数 $p$ であるから、あとはSageMathなどを用いて解けばよい。
以下は、SageMathで $p$ を求めた様子である。

7個の解のうち、最初に表示されたものが求める $p$ である。これを用いて $q$ を計算する。

これで $q$ も求められた。あとは復号するだけである。

from Crypto.Util.number import long_to_bytes

N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
c = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
p = 11917573148183173444338385104784582231114229409447057112131253050235068806316496452352116287542988361044359262597423159386263430710183647113674868056755407
q = 11248052945492193606877386307812298309646455365482356576580845624056836046347518805927852646289457003475918197991787867864250859819603651806169306473552239
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
msg = pow(c, d, N)
FLAG = long_to_bytes(msg)

print(f"{FLAG = }")