# [InterKosenCTF 2019] E_S_P ###### tags: `InterKosenCTF 2019` `crypto` ## 概要 `esp.py`と`out.txt`の2つが渡される。 `flag`と`yukko`が別ファイルからインポートされている。`out.txt`から $c =long(yukko | flag)^e \mod n$ と$N$, $e$, yukkoが貰える。 ``` N = 25125134527021311263131201640268273666244557592208296629651759140211810056674965088015474996071758507098811539822754801260772032982941022766820539265157407588709437139245493070450686253906706844855399857592004189185685514855616268579498238198520875125650782202219654519276611448640293834273910395334094545840047592734245001773144424282657884975748195521734768090993962224718901528750534156808339883575005261263527600450052408823594764396415214613676467680972048258991994310937930623461699560724105004882273917981925914977777376778601562332819634997976043403206821247602523606569331062096328435629432248251396836108791 e = 5 c = 1384882833358403107157483455837030126423776016700668066053485773536388137294341568225159281690842109551926339999967266126391991789325831114121174108693051569050725756549736748903818703028171722130614529263461024040623029006901921580342699946922790777643943404689373899738644309548617889405405228819343954990734340839760452212622631171070223285200073012764109859645127047073664810852475508920393361410397538905070637632995165937761377533163250554189274510508924626068398815869851763964298758064076300229914772467980140555957148498015329692800898979490576541587517944657669592051985331161151433440968360042050648071352 yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> " ``` ぱっと見た感じだとeが小さいが、yukkoが結構大きいのでLow Public Exponent Attackは出来なさそう。 しかし、平文の始めの部分が分かっているので、Coopersmith's Attackが可能である。 平文$m$の上位ビットが分かっているとき、その部分を$m_{known}$、残りの部分を$m_{unknown}$とする。($m = m_{known}|m_{unknown}$) このとき、RSAは$c = (m_{known}|m_{unknown})^e \mod n$を計算するので、$(m_{known}|m_{unknown})^e - c = 0 \mod n$なる$m_{unknown}$を求めれば良い。 さて、$e=5$なので平文の始めが$1-e^{-1}=0.8$程度分かっていれば良い。 今回はyukkoが69バイトで、フラグが39バイトであるので、$\cfrac{69}{69 + 39}=0.6388...$しか分かっていない。 0.8を超えるには87バイト平文が必要だが、`KosenCTF{`から始まることを利用しても78バイトである。さらに最後が`}`であることを利用すると79バイト。 残念ながらこれでは求まらなかったので、1バイトずつ総当りしていく。 ここではCoppersmithの定理で方程式の解を効率よく求めてくれるSageを使う。 ```python def solve(f, N): XX = 2^((39 - len(prefix) - 2) * 8) rt = f.small_roots(XX, 1.0) return rt N = 25125134527021311263131201640268273666244557592208296629651759140211810056674965088015474996071758507098811539822754801260772032982941022766820539265157407588709437139245493070450686253906706844855399857592004189185685514855616268579498238198520875125650782202219654519276611448640293834273910395334094545840047592734245001773144424282657884975748195521734768090993962224718901528750534156808339883575005261263527600450052408823594764396415214613676467680972048258991994310937930623461699560724105004882273917981925914977777376778601562332819634997976043403206821247602523606569331062096328435629432248251396836108791 e = 5 c = 1384882833358403107157483455837030126423776016700668066053485773536388137294341568225159281690842109551926339999967266126391991789325831114121174108693051569050725756549736748903818703028171722130614529263461024040623029006901921580342699946922790777643943404689373899738644309548617889405405228819343954990734340839760452212622631171070223285200073012764109859645127047073664810852475508920393361410397538905070637632995165937761377533163250554189274510508924626068398815869851763964298758064076300229914772467980140555957148498015329692800898979490576541587517944657669592051985331161151433440968360042050648071352 prefix = "KosenCTF{" yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> " table = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" for w1 in table: print(yukko + prefix + w1) m_known = int((yukko + prefix + w1).encode('hex'), 16) << ((39 - len(prefix) - 1) * 8) m_known += ord("}") print(hex(m_known)) P.<x> = PolynomialRing(Zmod(N)) f = (m_known + x * 0x100) ^ e - c flag = solve(f.monic(), N) if len(flag) > 0: flag = m_known + flag[0] * 0x100 print(flag) exit() ``` なんか求まった。 ``` Yukko the ESPer: My amazing ESP can help you to get the flag! -----> KosenCTF{H0RI_i5_57r0ng_7han_UriG3113r} ``` # 修正ポイント - これが想定解なら変数`flag`が`KosenCTF{`で始まり`}`で終わることをassertしておくこと。