###### tags: `InterKosenCTF2020` `crypto`
# [InterKosenCTF 2020] bitcrypto
## 問題
サーバーで動いてるスクリプトだけもらえる
以下、スクリプトのmain部分

def main():
    pubkey, privkey = key_gen(256)

    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()

    if len(m) > 8:
        print("yoshiking: too long!")
        exit()

    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)

    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()

    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()

    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")

`m`の入力時に弾かれる条件は、
- keywordに含まれている文字を使用している
- `m`が9文字以上だとダメ

これを通ると、`m`を暗号化したもの(`token`)がもらえる．
その後、`token`を入力し、復号したものが`keyword`と同じであれば、flagゲット

入力のバイパスはどうやってもできないので、keygen, enc, decを見てみる．
まず、keygenで気になるのは`pubkey`に`z`が含まれるところ．
この`z`は $(\frac{z}{p})=(\frac{z}{q})=-1$を満たすものである．

encでは、`b`を`m`の1ビット分にして、$z^b \cdot rand(2,n)^2$ を計算していった結果を返す．
decは、与えられた数字`b`が $(\frac{b}{p}) = (\frac{b}{q}) = 1$　だったら`0`を違ったら`1`とし、`m`を復元する．

## 解法
legendre symbolがみそっぽい．
encの式をlegendre symbolのみに注目すると、
$$
z^b =
\begin{cases}
-1 & (b=1)\\
1 & (b=0)
\end{cases}\\
rand(2,n)^2 = 1
$$
となる．
つまり、入力した`m`のビットが`1`のところは`token`のlegendre symbolが`-1`になり．`0`のところはlegendre symbolが`1`となる．decの方法がうまく行くことがわかる．

入力した`m`のビットが`1`となる`token`と`m`のビットが`0`の`token`を使えば任意のビット列が生成できる．
しかし、mainに

if len(c) != len(set(c)):
    print("yoshiking: invalid!")
    exit()

とあるように、同じ値を入れるとexitしてしまう．

これをパスするためには、legendre symbolの性質を使って異なる値となるようにする．legendre symbolは$a^2 \bmod{n}$ の解が存在すれば`1`となるので、適当な値$a$を2乗したものはlegendre symbolが`1`となる．
legendre symbol同士の乗算は普通に成り立つ？（証明はしらん）ので、legendre symbolが`1`となるようなものをかけても全体の値のlegendre symbolは変わらない．

よくわからない文を生成してしまったけど、とりあえず適当な値を2乗したものをかけとけば条件をパスできる．

from ptrlib import *
from Crypto.Util.number import bytes_to_long
from random import randrange, choice

keyword = b"yoshiking, give me ur flag"

sock = Socket("localhost", 13003)

sock.recvuntil("query: ")
sock.sendline(b"@")
sock.recvuntil("yoshiking: ")
token = eval(sock.recvline().decode())

payload = []
for bit in bin(bytes_to_long(keyword))[2:]:
    if bit == '1':
        payload.append(randrange(10000)**2 * token[0])
    else:
        payload.append(randrange(10000)**2 * choice(token[1:]))

print(len(payload))
print(len(set(payload)))
sock.recvuntil("your token: ")
sock.sendline(str(payload))
sock.interactive()

何回か試すと、flagゲット

$ python solver.py 
[+] __init__: Successfully connected to localhost:13003
207
207
[ptrlib]$ yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~
KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}
^C[+] close: Connection to localhost:13003 closed

## 感想
interkosenだとmediumかhardぐらい？
legendre symbolの勉強になった