ångstromCTF 2024 PHIlosophy

所属しているサークルの CTF 部門で最近始まった試みとして、参加した CTF の中から初心者向け問題を紹介するものがある。

非常にありがたい試みであり、ここでは自分がどの問題を解いたか忘れてしまわないように解説を書こうと思う。

なお、CTF の文化圏では解説（Writeup）はコンテストごとに書くイメージだが、残念なことにそんなにたくさんの問題を解けないので競技プログラミングと同じように 1 問ずつ記事にする。

問題

from Crypto.Util.number import getPrime
from secret import flag

p = getPrime(512)
q = getPrime(512)

m = int.from_bytes(flag.encode(), "big")

n = p * q
e = 65537
c = pow(m, e, n)

phi = (p + 1) * (q + 1)

print(f"n: {n}")
print(f"e: {e}")
print(f"c: {c}")
print(f"\"phi\": {phi}")

"""
n: 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e: 65537
c: 64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
"phi": 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308
"""

解法

$\phi = (p+1)(q+1)$ から $p + q$ の値を求めることで、 $p, q$ を 2 次方程式 $x ^ 2 - (p + q)x + pq = 0$ の解として求めることができる。

あとは RSA 暗号の復号の仕組みと同じように、 $e^{-1} \bmod (p-1)(q-1)$ を求めることで、 $c^{e^{-1}} \bmod n = m$ より Flag が手に入る。

from math import gcd
from Crypto.Util.number import long_to_bytes

n = 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e = 65537
c = 64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
phi = 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308

def sqrt(x: int):
    ok, ng = 0, x
    while ng - ok > 1:
        md = (ok + ng) // 2
        if md * md <= x:
            ok = md
        else:
            ng = md
    return ok

# phi = (p + 1) * (q + 1)
# p + q = phi - n - 1
# p, q は x ^ 2 - a * x + b = 0 の解
a = phi - n - 1
b = n
sq = sqrt(a * a - 4 * b)
p, q = (a + sq) // 2, (a - sq) // 2
# mod (p - 1) * (q - 1) での e の逆元を求めると, c ** einv = m (mod n) となる
assert gcd(e, (p - 1) * (q - 1)) == 1
einv = pow(e, -1, (p - 1) * (q - 1))
assert e * einv % ((p - 1) * (q - 1)) == 1
m = pow(c, einv, n)
print(long_to_bytes(m)) # b'actf{its_okay_i_figured_out_phi_anyway}'

感想

実は $(p-1)(q-1) = 2n- \phi + 2$ でこれがわかれば十分で $p, q$ を陽に求めなくても良かったりする。

RSA 暗号については以下の動画が参考になるらしいので後で視聴しておきたい。