# padrsa [InterKosenCTF2020]
###### tags: `InterKosenCTF2020` `crypto`

## 概要
フラグまたは任意のメッセージが任意の$e (3 \leq e \leq 65537)$でRSAで暗号化できる。
$N$は接続ごとにランダムに生成され、512-bitである。一方、接続は最大30秒しか持たない。
その間何回でも暗号化できるが、過去と同じ$e$は使えない。
また、$m$は次のようなパディングが付加される。

$m' \leftarrow (r_0|n) || m || r$

$n$はnonceで、暗号化ごとに1足される。$r$は64-bitの乱数で、次のように暗号化ごとに変化する。

$r' \leftarrow (r \ll 1) \oplus (n + 1)$

つまり、平文がよく分からん何かで挟まれる形になる。

## 解法
まず考えるのはe=3にする方法だが、Nが512ビットな以上mが170-8\*9=98ビット=12バイトの必要があり、非現実的なので却下。

ここで$m$が自由に設定できることを考える。$m$を空にすると、$(r_0|n)||r$が暗号化される。これは9バイトなので、e=3などとすれば簡単に復号できることが分かる。したがって、以降付加されるパディングがすべて予測できる。

これにより、Franklin Reiter's Attackが適用できる。
今回、
$$
M_1 = (r_2[0] | n) || flag || r_2 = flag \times 2^{64} + h_1\\
M_2 = (r_3[0] | (n+1)) || flag || r_3 = flag \times 2^{64} + h_2
$$
より、
$$
M_1 = flag \times 2^{64} + h_2 + (h_1 - h_2) = M_2 + (h_1 - h_2)
$$
となり、Franklin Reiter's Attackのパラメータは、
$a = 1, b = h_1 - h_2$
となる。

from sage.all import *
from ptrlib import *

def enc_flag(e):
    sock.sendlineafter('> ', '1')
    sock.sendlineafter('e: ', str(e))
    sock.recvuntil(': ')
    return int(sock.recvline(), 16)

def enc(e, m):
    sock.sendlineafter('> ', '2')
    sock.sendlineafter('e: ', str(e))
    sock.sendlineafter('m: ', m.hex())
    sock.recvuntil(': ')
    return int(sock.recvline(), 16)

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

def franklinreiter(C1, C2, e1, e2, N, a, b):
    P, X = PolynomialRing(Zmod(N), name='X').objgen()
    g1 = (a*X + b)**e1 - C1
    g2 = X**e2 - C2
    result = -gcd(g1, g2).coefficients()[0]
    return int(result)

sock = Socket("localhost", 13001)
#sock = Socket("0.0.0.0", 9999)
sock.recvuntil(': ')
N = int(sock.recvline())

n1 = 1
c1 = enc(5, b'')
r1 = Integer(c1).nth_root(5) & ((1 << 64) - 1)

C1 = enc_flag(3) # M1 = (r2[0]|nonce)||flag||r2
C2 = enc_flag(7) # M2 = (r3[0]|nonce')||flag||r3
r2 = ((r1 << 1) ^ 2) & ((1 << 64) - 1)
r3 = ((r2 << 1) ^ 3) & ((1 << 64) - 1)

for l in range(40, 50):
    h2 = (((r2>>56)|2) << (l*8+64)) + r2
    h3 = (((r3>>56)|3) << (l*8+64)) + r3
    m = franklinreiter(C1, C2, 3, 7, N, 1, h2 - h3)
    print(int.to_bytes(m, byteorder='big', length=64))

## 意見・感想
- 良問
- hardで良さそう。
- 512-bitのNは解かれる可能性がなきにしもあらず...?