Zenn
📌

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

2022/04/25に公開
Python
CTF
crypto
tech

前書き

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は20bitの素数）

 
また、e_{1}は128bitの素数なので、\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)

20bitの乱数をランダムに発生させ、それで割り切れるかどうかを確認していってます。
数分時間はかかりますが、\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}といったべき乗を扱う計算にて、オイラーの定理をどのように適用できるのか学ぶことができてよかったです。とても面白い問題でした。

Discussion