# OT or NOT OT - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto`

## 概要
サーバーに繋ぐ式の問題。

512ビットの素数$p$と、乱数$r, s \in [2, p-1]$が生成される。
ここで$r$は$p$を法とした平方剰余にならないよう、$s$はなるように作られる。

まずランダムな鍵とIVでAESを初期化し、フラグを暗号化する。
最初にこのIVと暗号化されたフラグ、素数$p$、そして鍵のビット長が貰える。

その後、鍵$k$を$k_0$として、以下の処理を$k_i > 0$の間実行する

1. 過去に入力されていない$g > 1$をユーザー入力として受け取る
2. さらに、$g_a, g_b, g_{c_0}, g_{c_1}$を受け取る（いずれも1より大きく、$g_{c_0} \neq g_{c_1}$である）
3. $a, b$をそれぞれ$k_i$の下位1ビット、2ビット目とする
4. $k_{i+1} = k_i >> 2$
5. $m_0 = r^{a + 1}s \mod p$
6. $m_1 = r^{b + 1}s \mod p$
7. $w = \left(g_a^r \mod p \right) \left(g^s \mod p \right) \mod p$
8. $z_0 = \left((g_{c_0}^r \mod p)(g_b^s \mod p)\mod p \right) \oplus {m_0}$
9. $z_1 = \left((g_{c_1}^r \mod p)(g_b^s \mod p)\mod p \right) \oplus {m_1}$

各イテレーションにおける$w, z_0, z_1$の値が貰える。

## 解法
XORしてるところとか意味不明感がある。

今$r$は平方剰余でないので、求めるビットが0ならば$m$は平方剰余にならず、1ならば平方剰余になる。これを使えば、とりあえず$m_0, m_1$が分かったときに$a, b$の値を知ることができる。

$m_0, m_1$を知るためには$z_0, z_1$を上手く操作する必要がある。理想的には$z_0 = w \oplus m_0, z_1 = w \oplus m_1$とかになったら嬉しい。

$w, z_0 \oplus m_0, z_1 \oplus m_1$は似た形をしているので、これは実現可能なのだが、$g_{c_0} \neq g_{c_1}$という条件が厳しい。これでは1回にどちらか一方のビットしか復元できないように思える。

しかし、$r$が偶数のとき(?)に$g_a = g_{c_0} = g_{c_1} - p$と定めると、$g_a^r\mod p = g_{c_0}^r\mod p = g_{c_1}^r\mod p$となる。暗号担当じゃないので数学的な理由は知らないが、sageで適当に試してたらそうなった。（Legendre symbolが-1なのが関係してそう？）

これにより、両方のビットが復元できるので、あとはAESでフラグを復号してやれば良い。

## コード

from ptrlib import *
from Crypto.Cipher import AES
import base64

def legendre(x, p):
    a = pow(x, (p-1)//2, p)
    if a == 1:
        return 1
    elif a == 0:
        return 0
    else:
        return -1

sock = Socket("localhost", 10130)
#sock = Process(["python", "./server.py"])

b = base64.b64decode(sock.recvlineafter("flag: "))
iv, cipher = b[:AES.block_size], b[AES.block_size:]

p = int(sock.recvlineafter("p = "))
keylen = int(sock.recvlineafter("() = "))

k = ''
g = 2
for i in range((keylen + 1) // 2):
    print(f"{i} / {(keylen + 1) // 2}")
    sock.sendlineafter("g = ", str(g))
    sock.sendlineafter("ga = ", str(g))
    sock.sendlineafter("gb = ", str(g))
    sock.sendlineafter("gc0 = ", str(g))
    sock.sendlineafter("gc1 = ", str(p - g))
    z0 = int(sock.recvlineafter("z0 = "))
    z1 = int(sock.recvlineafter("z1 = "))
    w = int(sock.recvlineafter("w = "))
    m0 = z0 ^ w
    m1 = z1 ^ w
    k = ('0' if legendre(m0, p) == -1 else '1') + k
    k = ('0' if legendre(m1, p) == -1 else '1') + k
    g += 1

key = int.to_bytes(int(k, 2), 32, 'big')
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = aes.decrypt(cipher)
print(flag)

sock.close()

## 感想・意見
- 難易度感わからんけど結構考えた（mediumくらい？）
- これ以上簡単な解法は見つからなかった