# [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を使う。

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しておくこと。