Cake CTF 2022 frozen cake Writeup
この記事は Cake CTF 2022 - frozen cake の初心者向け解説Writeupです。競技プログラミングなどには慣れているがCryptoの問題をほとんど解いたことのない、といった方を主に対象としています。
まずは問題スクリプトを読んでみましょう。
code:chall.py
from Crypto.Util.number import getPrime
import os
flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)
p = getPrime(512)
q = getPrime(512)
n = p*q
print("n =", n)
print("a =", pow(m, p, n))
print("b =", pow(m, q, n))
print("c =", pow(m, n, n))
code:output.txt
n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549
Cryptoの問題はPythonで実装されていることが多いです。ライブラリが充実している、多倍長整数型が扱いやすい、問題コードをコピペで動かせるなどの理由から、問題を解くソルバもPythonで実装することをお勧めします。
Crypto.Util.numberはCryptoで良く使われるライブラリで、ここでは512ビットの素数p,qを生成するのに使っているようです。pip install pycryptodomeなどでインストールすることができます。
code:py
flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)
この部分を見ると、フラグ文字列を環境変数から読み込んでint型に変換し、m に代入しています。この m を求めることがこの問題のゴールです。
さらに、$ a = m^p \bmod n, b = m^q \bmod n, c = m^n \bmod n が output.txt で与えられています。
RSA暗号をベースにした問題のようです。
この問題を解くために、オイラーの定理を利用します。次のような定理です。
$ a と $ n を互いに素な整数とすると、 $ a^{\varphi(n)} \equiv 1 \pmod n が成り立つ。
この問題のように $ n が$ 2つの素数の積で表せる場合は、$ \varphi(n) = (p-1)(q-1) となります。（これらはRSAをベースにした問題の多くで用いる重要な事実です）。
さらに、この定理から次のことも言えます。（これも多くの問題で用います）。
$ x \equiv y \pmod {\varphi(n)}ならば $ a^x \equiv a^y \pmod n
問題に戻りましょう。$ m^{\varphi(n)} \equiv m^{n-p-q+1} \equiv m^n \cdot m^{-p} \cdot m^{-q} \cdot m \pmod n
であることから、$ c \cdot a^{-1} \cdot b^{-1} \cdot m \equiv 1 \pmod n が成り立ちます。$ m 以外の値はすべて既知なので、この式から $ m = a \cdot b \cdot c^{-1} \pmod nとして $ m を求めることができます！
実際にソルバを書いてみましょう：
code:python
from Crypto.Util.number import long_to_bytes
m = pow(c, -1, n) * a * b % n
print(long_to_bytes(m))
Pythonでは pow(x, -1, n) として $ x の $ \bmod n での逆元を求めることができます。
long_to_bytes は、整数から文字列（バイト列）に変換するための関数です。Pythonの標準ライブラリにあるint.to_bytesといった関数を使ってもよいですが、lengthやbyteorderを指定しないでよいのでこちらのほうが便利で、多くの問題では整数から文字列への変換にはこの関数が用いられています。逆に、bytes_to_long という関数を使うと文字列（バイト列）から整数に変換することができます。（問題文にあるint(flag.encode().hex(), 16)もbytes_to_longと同じ処理をしています。）
実行してみると、無事フラグを得ることができました！