# 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に勝ち放題となる。 ## コード ```python= 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でルジャンドル記号に過敏になっていただけかも)