CrewCTF2022 The HUGE e

問題

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

のパラメータが与えられる．$c$は，$m$を次の式によって計算された値である． $$ c \equiv m^{e_1^{e_2^{e_3}}} \pmod p $$ また，$p$はとてもsmoothである．

解法

$e=e_1^{e_2^{e_3}}$として$d=e^1\mod \phi(p)$が求まれば良いわけだが，タイトルの通り$e$がとんでもなく大きな数になってしまうため，何か工夫が必要だ．

オイラーの定理(またはフェルマーの小定理)より，$e\equiv e_1^{e_2^{e^3}} \pmod {\phi(p)}$としてしまって良い．これで，$ e_1^{e_2^{e^3}}\pmod {p-1}$の値を求める問題になった． ここでさらに，$e_1^{e_2^{e^3}}=e_1^{e_4}$とおくと，$e_4 \equiv e_2^{e_3} \pmod {\phi(p-1)}$としてしまって良い．これなら簡単に求められる．$\phi(p-1)$の値だが，$p-1$がsmoothであることを使えば簡単に求められる．

def factor(N):
    f = [] # p-1の素因数分解
    i = 2
    N = p-1
    while i*i<=N:
        if N%i==0:
            f.append(i)
            N = N//i
        else:
            i+=1
    f.append(N)
    return f

p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
e1 = 219560036291700924162367491740680392841
e2 = 325829142086458078752836113369745585569
e3 = 237262361171684477270779152881433264701
c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
phi = p-1
phiphi = 1
fs = factor(phi)
for f in fs:
    phiphi *= f-1
e4 = pow(e2,e3,phiphi)
e = pow(e1,e4,phi)
d = pow(e,-1,phi)
m = pow(c,d,p)
print(long_to_bytes(m))

crew{7hi5_1s_4_5ma11er_numb3r_7han_7h3_Gr4ham_numb3r}

コメント

フェルマーの小定理やオイラー関数を正しく使えるかを問う問題だった．競プロでもABC228-Eみたいなフェルマーの小定理をしっかり使う問題が出ています．