# war(sa)mup - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto`

## 問題概要
PKCS#1 v1.5を利用してRSAが実装されている。気になる点は以下：
- eが1337
- $m^e \mod N$と$\lfloor{\cfrac{m}{2}}\rfloor^e \mod N$が貰える

eがphiを互いに素であることはコードで確認されているので、特に問題なさそう。
パディングの実装も見た感じ怪しいところはない。

## 解法
5分ほど式を眺めると、いつも名前を忘れるFranklin Reiter's Attackであることが分かる。（名前は分からないので調べる。）
今回、$m_1 = 2m_2$あるいは$m_1 = 2m_2 + 1$の2通りが考えられる。
前者の場合、$2^e c_2 \mod N = c_1$となるはずだが、確認するとそうはならないので、$m_1 = 2m_2 + 1$であることが分かる。

with open("output.txt") as f:
    n = int(f.readline().split("=")[1])
    e = int(f.readline().split("=")[1])
    c1 = int(f.readline().split("=")[1])
    c2 = int(f.readline().split("=")[1])

def gcd(a, b): 
    while b:
        a, b = b, a % b
    return a.monic()

def franklinreiter(C1, C2, e, N, a, b):
    P.<X> = PolynomialRing(Zmod(N))
    g1 = (a*X + b)^e - C1
    g2 = X^e - C2
    result = -gcd(g1, g2).coefficients()[0]
    return result

m = franklinreiter(c1, c2, e, n, 2, 1) * 2 + 1
print(int.to_bytes(int(m), 0x80, 'big'))

これを実行するとPKCS#1 v1.5でパディングされたフラグが貰える。
`zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}`

## 感想
- warmupで良いと思う