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

## overview

You should beat yoshiking at the rock-paper-scissors over 100 times without defeat. He decides his hand and give us its commitment before you input your hand. The commitment is encrypted by ElGamal encryption scheme.

import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse

HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}

def commit(m, key):
    (g, p), (x, _) = key
    r = random.randint(2, p-1)
    c1 = pow(g, r, p)
    c2 = m * pow(g, r*x, p) % p
    return (c1, c2)


def decrypt(c, key):
    c1, c2 = c
    _, (x, p)= key

    m = c2 * inverse(pow(c1, x, p), p) % p
    return m


def keygen(size):
    p = getStrongPrime(size)
    g = random.randint(2, p-1)
    x = random.randint(2, p-1)

    return (g, p), (x, p)


signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))

round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))

    yoshiking_hand = random.randint(1, 3)
    c = commit(yoshiking_hand, key)
    print("[yoshiking]: my commitment is={}".format(c))

    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()

    yoshiking_hand = decrypt(c, key)
    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))

        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the private key: {}".format(key[1][0]))
        exit()

print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)

## solution

It has better to focus on that the plaintext-space is quite small: 1 or 2 or 3. If we could see such like that the yoshiking's hand is even or not, or yoshiking's hand is quadratic residue or not.

The commitment is $(C_1, C_2) = (g^x, mg^{xr}) \mod p$. When we assume $g^{xr}$ is quadratic residue, $C_2$ is quadratic residue when $m$ is quadratic residue and $C_2$ is quadratic non-residue when $m$ is quadratic non-residue.

1 is always quadratic residue. Weather 2, 3 are quadratic residue or not is decided by $p$. For example, if we find a good $p$ such that $2, 3$ are quadratic non-residue, we can distinguish yoshiking's hand is 1 or otherwise by his commitment.

Thus, we can choose our hand adaptively in response to yoshiking's hand. Then we don't lose against yoshiking.

## exploit

from ptrlib import Socket
import random
import os

HOST = os.getenv("HOST", "localhost")
PORT = os.getenv("PORT", "9999")

def legendre_symbol(a, p):
    ls = pow(a, (p - 1)//2, p)
    if ls == p - 1:
        return -1
    return ls

while True:
    sock = Socket(HOST, int(PORT))
    g, p = sock.recvregex("g: ([0-9]+), and p: ([0-9]+)")
    g, p = int(g), int(p)


    # check parameter
    try:
        assert legendre_symbol(1, p) == 1
        assert legendre_symbol(2, p) != 1
        assert legendre_symbol(3, p) != 1

        for _ in range(100):
            m = random.randint(1, 3)
            c = m * pow(g, random.randint(2, p-1), p) % p
            assert legendre_symbol(m, p) == legendre_symbol(c, p)
    except AssertionError:
        sock.close()
        continue
    break

while True:
    c1, c2 = eval(sock.recvlineafter("="))

    qr = legendre_symbol(c2, p)
    if qr == 1:
        sock.sendlineafter("(1-3): ", "3")
    else:
        sock.sendlineafter("(1-3): ", "2")

    sock.recvline()
    sock.recvline()
    sock.recvline()
    result = sock.recvline().decode()
    if "draw" in result:
        pass

    elif "ahaha" in result:
        print("[-] something wrong")
        exit()

    elif "win" in result:
        wins = int(sock.recvlineafter("wins: "))
        print("wins: {}".format(wins))
        if wins >= 100:
            break

print(sock.recvuntil("}").decode())