【CrewCTF 2022】「The HUGE e」についてのメモ

前書き

CrewCTF 2022にて出題された問題「The HUGE e」に関する解法のメモです。
個人の備忘録としてまとめたものですが、誰かのお役に立てれば幸いです。

問題概要

以下のスクリプトと出力ファイルが与えられます。

chall.py

from Crypto.Util.number import getPrime, bytes_to_long, inverse, isPrime
from secret import flag

m = bytes_to_long(flag)

def getSpecialPrime():
    a = 2
    for i in range(40):
        a*=getPrime(20)
    while True:
        b = getPrime(20)
        if isPrime(a*b+1):
            return a*b+1


p = getSpecialPrime()
e1 = getPrime(128)
e2 = getPrime(128)
e3 = getPrime(128)

e = pow(e1,pow(e2,e3))
c = pow(m,e,p)

assert pow(c,inverse(e,p-1),p) == m

print(f'p = {p}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'e3 = {e3}')
print(f'c = {c}')

out.txt

p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613

次のように暗号化をしていることが分かります。

$$c\equiv m^{e}\pmod p \tag{1}$$

 
ただし、$e = e_{1}^{(e_{2}^{e_3})}$で、$p$は独自に定義されたgetSpecialPrime関数によって生成される素数です。
 
通常のRSA暗号と同様に考えると、$m^{\phi(p)}\equiv 1\pmod p$（オイラーの定理）より、$ed\equiv 1\pmod {\phi(p)}$を満たす$d$で、式$（1）$の両辺を$d$乗すれば以下のように$m$が求まります。

$$c^{d} \equiv m^{ed} \equiv m\pmod p \tag{2}$$

 
$p$が公開されており、$\phi(p) = p - 1$であることから、$e$が分かれば$d$が求められます。
しかし、chall.pyで記載された方法（$e = e_{1}^{(e_{2}^{e_3})}$）では、$e$の計算が終わりません。

ではどのようにして$e$を求めるのか、というのがこの問題です。

解法

オイラーの定理を改めて確認します。

$$m^{\phi(p)}\equiv 1\pmod p \tag{3}$$

 
式$(3)$は、法$p$の世界で$m$のべき乗を求めていくと、$m$の$\phi(p)$乗が$1$となり、周期$\phi(p)$で同じ値が現れることを意味しています。これを式$(1)$と組み合わせると、次のようになります（$k$は整数）。

$$m^{e}\equiv m^{e + k\phi(p)}\equiv m^{e\pmod {\phi(p)}}\pmod p \tag{4}$$

 
さらに、指数部は以下のように表せます（$e = e_{1}^{(e_{2}^{e_3})}$, $\phi(p) = p - 1$）。

$$e_{1}^{(e_{2}^{e_3})}\pmod {p - 1} \tag{5}$$

 
ここで、$p - 1$について考えてみます。
chall.pyのgetSpecialPrime関数を見てみると、$p$は以下の特徴をもつことが分かります。

• $p - 1 = 2 \times a_{1} \times a_{2} \times \cdots \times a_{40} \times b$と素因数分解できる（各$a_{i}$と$b$は$20$bitの素数）

 
また、$e_{1}$は$128$bitの素数なので、$\rm{GCD}(e_{1}, p - 1) = 1$です。
よって、オイラーの定理より、以下が成り立ちます。

$$e_{1}^{\phi(p - 1)}\equiv 1\pmod {p - 1} \tag{6}$$

 

先ほどと同様にして、式$(5)$と式$(6)$を組み合わせます（$k$は整数）。

$$e_{1}^{(e_{2}^{e_3})} \equiv e_{1}^{(e_{2}^{e_3}) + k\phi(p)} \equiv e_{1}^{(e_{2}^{e_3})\pmod {\phi(p - 1)}}\pmod {p - 1} \tag{7}$$

 
式$(7)$より、${e_{2}}^{e_{3}}$乗の代わりに、${e_{2}}^{e_{3}}\pmod {\phi(p - 1)}$乗してもよいことが分かりました。
$e_{1}^{(e_{2}^{e_3})}$の計算はできなかったので、代わりに$e_{1}^{(e_{2}^{e_3})\pmod {\phi(p - 1)}}$による計算を試みます。
 
なお、$\phi(p - 1)$に関しては、$p-1$が簡単に素因数分解できるので、次のとおり求められます。

$$\phi(p - 1) = \phi(2)\phi(a_{1})\phi(a_{2})\cdots \phi(a_{40})\phi(b) = (a_{1} - 1)(a_{2} - 1)\cdots(a_{40} - 1)(b - 1) \tag{8}$$

 

phi.py

from Crypto.Util.number import getPrime, isPrime
p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823

phi = 1
q = (p - 1) // 2

while True:
    if isPrime(q) == 1:
	phi *= q - 1
	break
    a = getPrime(20)
    if q % a == 0:
	phi *= a - 1
	q = q // a
	
print(phi)

$20$bitの乱数をランダムに発生させ、それで割り切れるかどうかを確認していってます。
数分時間はかかりますが、$\phi(p - 1)$の値が求まります。

phi.txt

phi = 63775594668498404422995279661693309334486076035802944116275814269950078792958445557761589097717204934857369990271713664698474867142217580223510594284968730411939236198524531363514002763605853593498040656788050786948899096447734618521600000000

あとは以下のとおりにフラグを求めていきます。

1. ${e_{2}}^{e_{3}}\pmod {\phi(p - 1)}$を計算する
2. $e = {e_{1}}^{(\rm{1.で求めた値})}\pmod{p - 1}$を計算する
3. 法$p - 1$の世界における$e$の逆元$d$を計算する
4. $c^{d}\pmod p$を計算する
5. 4.で得られた数値を変換する

solver.py

from Crypto.Util.number import long_to_bytes
p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
phi = 63775594668498404422995279661693309334486076035802944116275814269950078792958445557761589097717204934857369990271713664698474867142217580223510594284968730411939236198524531363514002763605853593498040656788050786948899096447734618521600000000
    
e2_e3 = pow(e2, e3, phi)
e = pow(e1, e2_e3, p - 1)
d = pow(e, -1, p - 1)
m = pow(c, d, p)
print(long_to_bytes(m))

フラグは次のとおりです。

flag.txt

b'crew{7hi5_1s_4_5ma11er_numb3r_7han_7h3_Gr4ham_numb3r}'

感想

大きな数や$a^{b^c}$といったべき乗を扱う計算にて、オイラーの定理をどのように適用できるのか学ぶことができてよかったです。とても面白い問題でした。