cpawCTF level3 Common World ○○○○○○の定理じゃないの？

ちょっと納得いかなかったので共有。

問題文

Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました．しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう.

(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)

暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904

これは…？

フラグは以下のシンタックスです.
cpaw{復号した値}

※復号した値はそのままで良いですが，実は意味があります，余力がある人は考えてみてください.

「これは…？」をクリックするとhint.txtが貰える。

Cpaw君は自力では解けないのでRSA暗号のプロに尋ねるとヒントをくれました.

(e, N) = (13, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)

暗号文: 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664

クレーム

解法はCommon Modulus Attackをやるらしい。

e1=11, e2 = 13とすると、e1×6+e2×(-5)=1となる。問題文にある暗号文をc1, hint.txtにある方をc2とすると、m = c1⁶ × c2^-5 mod n で求まるとのこと。m^{e1×6+e2×(-5)} = m¹ となりますからね。

ただCommon Modulus Attackが成立する条件は、「同じnと異なるeで同じ平文mを暗号化してはいけない」だ。hint.txtには同じ平文をeで暗号化したとは一言も言ってない。これをエスパーしろというのは酷では？

まあ、level2までのCrypto問題もそこまで難しい問題ではなかったから比較的簡単なCMAを扱ったというのは分からんでもないが、ちょっとなぁ。問題名も確かに…。うーん。

別解？

クレームをつけた理由として、Common Modulus Attackを使わずに解いたからがあげられる。

カーマイケルの定理を使った。この記事がわかりやすい。

p - 1 ≡ 0 (mod e) のときの RSA 復号方法 | y011d4.log

そもそもnは素因数分解可能でありそれで簡単に解けるかと思いきや、eとφ(n)が互いに素でない。Seccon Beginnersでも同様の問題があり、それを引っ張り出してきた。どうでもいいけど毎回beginnerのスペルが怪しい。engineerやpioneerにつられてbegineerと書きたくなる。

SECCON Beginners CTF 2021 Crypto writeup - Attack All Around

ここで腹が立ったのが、φ(n)がe2=13の倍数でもあったこと。hint.txtの暗号文を復号すれば何かヒントがもらえると思い込んでいたのでつらかった。

L = 3^φ(n)/e とすれば後は記事通り。2じゃダメだった。

e=11なので11種類の平文が出てくる。かなり短い平文を発見したので提出したらcorrectだった。

from Crypto.Util.number import *
import math

n = (中略)
p = pow(2,607)-1
assert n%p == 0
q = n//p
e = 11
c = (中略)
phi = (((p-1)*(q-1))//(math.gcd(p-1,q-1)))
# カーマイケルの定理
d = inverse(e,phi//e)
m = pow(c,d,n)
L = pow(3,phi//e,n)
for i in range(e):
    mm = (pow(L,i)*m)%n
    print("cpaw{"+str(mm)+"}")
    
# Common Modulus Attack
ee = 13
cc = (中略)

s1 = 6
s2 = -5
cc_inv = inverse(cc,n)
M = (pow(c,s1,n)*pow(cc_inv,-s2,n))%n
print("cpaw{"+str(M)+"}")