# yoshiking vs janken - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto`

## 概要
yoshikingとじゃんけんができる夢のサービス。

素数$p$と乱数$g, x \in [2, p-1]$が作られ、$(g, p)$が貰える。
yoshikingは1から3の整数$m$に対して、以下のcommitを計算する。

$$c = (g^r \mod p, mg^{rx} \mod p)$$

この値両方がもらえる。
その後こちらも1から3の整数を出し、じゃんけんをする。このときyoshikingは

\begin{eqnarray}
m &=& \cfrac{c_1}{c_0^x} \mod p \\
&=& \cfrac{mg^{rx}}{(g^r)^x} \mod p
\end{eqnarray}

により$m$を求める。

じゃんけんに100回勝てば良いが、負けると終了する。

## 解法
今$x$が偶数であったとする。（この確率は1/2なので十分。）
このとき、$c_1$の値は以下の3つに限定される。ただし、$rx = 2w$とおく。

$$
c_1 = (g^w)^2 \mod p\\
c_1 = 2(g^w)^2 \mod p\\
c_1 = 3(g^w)^2 \mod p
$$

ここで、$p$を法として1は必ず平方剰余であるが、2と3については4パターンの組み合わせがあり、それぞれについて次のように$m$の情報が得られる。
ただし、$l(x, p)$はルジャンドル記号。

| $l(2, p)$ | $l(3, p)$ | $c_1$と$m$の関係 |
|:-:|:-:|:-:|
| 1 | 1 | $m$に関する情報量は0 |
| 1 | -1 | $l(c_1, p)=1$ならyoshikingはグーかチョキ |
| -1 | 1 | $l(c_1, p)=1$ならyoshikingはグーかパー |
| -1 | -1 | $l(c_1, p)=1$ならyoshikingはグー |

$l(2,p)=l(3,p)=1$のときはつなぎ直せば良いので、3/8のガチャをクリアすればyoshikingに勝ち放題となる。

## コード

from ptrlib import *

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

g, p = map(int, sock.recvregex("g: (\d+), and p: (\d+)"))

x = pow(2, (p-1)//2, p)
y = pow(3, (p-1)//2, p)

strategy_list = {
    (1, p-1): lambda l: 2 if l == p-1 else 1,
    (p-1, 1): lambda l: 1 if l == p-1 else 3,
    (p-1, p-1): lambda l: 3 if l == 1 else 2
}
if (x, y) not in strategy_list:
    logger.warn("Bad luck!")
    exit()

strategy = strategy_list[(x, y)]

win = 0
while win < 100:
    c0, c1 = map(int, sock.recvregex("is=\((\d+), (\d+)\)"))
    hand = strategy(pow(c1, (p-1)//2, p))
    sock.sendlineafter(": ", str(hand))
    sock.recvline()
    sock.recvline()
    sock.recvline()
    if b'win' in sock.recvline():
        print(f"win = {win}")
        win += 1

sock.interactive()

win = 99
[system]: wins: 100
[yoshiking]: Wow! You are the king of roshambo!
[yoshiking]: suge- flag ageru
zer0pts{jank3n-jank3n-0ne-m0r3-batt13}
[ptrlib]$

## 感想・意見
- おもしろかった
- けど個人的にはeasyかな（OT or NOT OTより簡単だと感じたので）
- 所要時間もOT or NOT OTが2日またいで考えたのに、こっちはたぶん1時間以内に解けてる（OT or NOT OTでルジャンドル記号に過敏になっていただけかも）