AngstormCTF_PHIlosophy_Writeup
まずは問題スクリプトを読んでみましょう。
code:python
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
"""
Cryptoの問題はPythonで実装されていることが多いです。ライブラリが充実している、多倍長整数型が扱いやすい、問題コードをコピペで動かせるなどの理由から、問題を解くソルバもPythonで実装することをお勧めします。
code:python
from Crypto.Util.number import getPrime
from secret import flag
p = getPrime(512)
q = getPrime(512)
Crypto.Util.numberはCryptoで良く使われるライブラリで、ここでは512ビットの素数p,qを生成するのに使っているようです。pip install pycryptodomeなどでインストールすることができます。
secretというライブラリをインポートしていますが、これは配布されていないため手元ではエラーが出るはずです。flagという文字列をインポートしていますが、出力されている情報からこれを求めるのがこの問題のゴールです。
手元でこのコードを実行してみたい場合、from secret import flagの部分を消し、その場所にflag = "flag{dummy}"とフラグ変数を自分で用意するとよいでしょう。
code:python
"""
n: 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e: 65537
c: 64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
"phi": 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308
"""
最後についている文字列はsecretモジュールが存在する環境でこのファイルが実行された時の出力です。Cryptoの問題は、このようにコードの出力が付属していてそこからフラグを得る、またはサーバーと通信してフラグを得るという形式が多いです。
code:python
m = int.from_bytes(flag.encode(), "big")
n = p * q
e = 65537
c = pow(m, e, n)
この部分は標準的なRSA暗号の暗号化の実装です。flagを文字列から整数に変換し、公開鍵 n,e から暗号文 c を計算しています。
RSA暗号
この問題で使う範囲でRSA暗号について軽く解説しておきます。詳しくはこの動画 などを見るなりすると良いと思います。 登場する値
$ m: 平文
$ c: 暗号文
$ n: 公開鍵。素数 $ p,q の積として表される
$ e: 公開鍵。多くの場合65537が使われる。
$ d: 秘密鍵。これが漏れると暗号文から平文を計算（復号）できてしまう。
$ \varphi(n): オイラーのφ関数 $ n = pq の場合、$ \varphi(n) = (p-1)(q-1) となる。 これらを用いて、
暗号化: $ c = m^e \bmod n （pythonの場合: c = pow(m, e, n)）
復号: $ m = c^d \bmod n （pythonの場合: m = pow(c, d, n)）
と 暗号化/復号 するのがRSA暗号です。
また、これらの間で成り立つ関係式として、$ ed = 1 \bmod \varphi(n) というものがあります。これを使えば、$ e,d,\varphi(n) のうち二つがわかれば残りの一つが計算できます。
例: $ e,\varphi(n)がわかっているとき、$ d = e^{-1} \bmod \varphi(n)であるため d = pow(e, -1, phi) として $ d が計算できます。
code:python
phi = (p + 1) * (q + 1)
この値が得られる点がこの問題の脆弱なポイントです。$ \varphi(n) = (p-1)(q-1) と似ており、この値を元に $ \varphi(n) を計算することができるとよさそうです。実際、頑張って式変形していくと、(p - 1) * (q - 1) = 2 * n + 2 - phi と $ \varphi(n) が計算できます。（誤解を生みそうなので補足として、一般的にはphi という変数で指すのは$ \varphi(n) そのもので $ (p+1)(q+1) ではありません。）
これでc を復号するための情報が得られました！実際にソルバを書いてみましょう：
code:python
from Crypto.Util.number import long_to_bytes
n = 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e = 65537
c = 64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
phi = 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308
x = 2 * n + 2 - phi
d = pow(e, -1, x)
m = pow(c, d, n)
print(long_to_bytes(m))
long_to_bytes は、整数から文字列（バイト列）に変換するための関数です。ほとんどの問題では整数から文字列への変換にはこの関数が用いられています。逆に、bytes_to_long という関数を使うと文字列（バイト列）から整数に変換することができます。
実行してみると、無事フラグを得ることができました！