ZKP Introduction

just google it

Proof of Knowledge

#!/usr/bin/env python3
import socket
import json
import random

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2
w = 0x5a0f15a6a725003c3f65238d5f8ae4641f6bf07ebf349705b7f1feda2c2b051475e33f6747f4c8dc13cd63b9dd9f0d0dd87e27307ef262ba68d21a238be00e83
y = 0x514c8f56336411e75d5fa8c5d30efccb825ada9f5bf3f6eb64b5045bacf6b8969690077c84bea95aab74c24131f900f83adf2bfe59b80c5a0d77e8a9601454e5

def main():
    HOST = 'socket.cryptohack.org'
    PORT = 13425

    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))

        data = s.recv(4096).decode()
        print("[Server]", data.strip())

        r = random.randint(0, q - 1)
        a = pow(g, r, p)
        msg = {"a": a}
        s.sendall((json.dumps(msg) + "\\n").encode())
        print("[Prover] Send a =", a)

        data = s.recv(4096).decode()
        print("[Server]", data.strip())
        challenge_resp = json.loads(data)
        e = challenge_resp["e"]
        print("[Prover] Received e =", e)

        z = (r + e * w) % q
        msg = {"z": z}
        s.sendall((json.dumps(msg) + "\\n").encode())
        print("[Prover] Send z =", z)

        data = s.recv(4096).decode()
        print("[Server]", data.strip())

if __name__ == "__main__":
    main()

Special Soundness

同じ a に対して，複数回チャレンジを成功させると w が計算できてしまうことがある

#!/usr/bin/env python3
import socket
import json
import random
from Crypto.Util.number import inverse, long_to_bytes

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7

HOST = "socket.cryptohack.org"
PORT = 13426

def readline_json(sockfile):
    line = sockfile.readline()
    if not line:
        return None
    line = line.strip()
    if not line:
        return None
    try:
        return json.loads(line)
    except json.JSONDecodeError:
        return None

def main():
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))
        sockfile = s.makefile("r")

        while True:
            data = readline_json(sockfile)
            if data is not None:
                break
        a = data["a"]
        y = data["y"]
        print("[Server] a =", a, "y =", y)

        e = random.getrandbits(511)
        print("[Client] Send e =", e)
        s.sendall((json.dumps({"e": e}) + "\\n").encode())

        while True:
            data = readline_json(sockfile)
            if data is not None and "z" in data:
                break
        z = data["z"]
        print("[Server] z =", z)

        while True:
            data = readline_json(sockfile)
            if data is not None and "a2" in data:
                break
        a2 = data["a2"]
        print("[Server] a2 =", a2)

        e2 = random.getrandbits(511)
        print("[Client] Send e2 =", e2)
        s.sendall((json.dumps({"e": e2}) + "\\n").encode())

        while True:
            data = readline_json(sockfile)
            if data is not None and "z2" in data:
                break
        z2 = data["z2"]
        print("[Server] z2 =", z2)

        diff_z = (z - z2) % q
        diff_e = (e - e2) % q

        inv_diff_e = inverse(diff_e, q)
        w_val = (diff_z * inv_diff_e) % q

        print("[+] Extracted w as integer:", w_val)

        w_bytes = long_to_bytes(w_val)
        start_idx = w_bytes.find(b"crypto{")
        if start_idx >= 0:
            end_idx = w_bytes.find(b"}", start_idx)
            if end_idx >= 0:
                flag = w_bytes[start_idx:end_idx+1]
                print("[+ FLAG:", flag.decode())
                return
        print(w_bytes)

if __name__ == "__main__":
    main()

Honest Verifier Zero Knowledge

シミュレータに対して応答を行う

シミュレータは通常と逆の手順で検証を行うため，検証者はトランスクリプトから情報を得ることができな

#!/usr/bin/env python3
import socket
import json
import random
from Crypto.Util.number import inverse, long_to_bytes

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2

HOST = "socket.cryptohack.org"
PORT = 13427

def readline_json(sockfile):
    while True:
        line = sockfile.readline()
        if not line:
            return None 
        line = line.strip()
        if not line:
            continue
        try:
            return json.loads(line)
        except json.JSONDecodeError:
            continue

def main():
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))
        sockfile = s.makefile("r") 
        while True:
            data = readline_json(sockfile)
            if data is not None and "e" in data and "y" in data:
                break
        e = data["e"]
        y = data["y"]
        print("[Server] e =", e)
        print("[Server] y =", y)

        z = random.randrange(q)

        t = pow(y, e, p)

        inv_t = inverse(t, p)
        gz = pow(g, z, p)
        a = (gz * inv_t) % p

        send_data = {"a": a, "z": z}
        s.sendall((json.dumps(send_data) + "\\n").encode())
        print("[Client] Send transcript:", send_data)

        data = readline_json(sockfile)

        print("[Server] response =", data)
        if "flag" in data:
            print("[+] Got Flag:", data["flag"])

if __name__ == "__main__":
    main()

Non-Interactive

NIZK に関する問題．Prover は w を知っているので，適当な乱数 a と e を作り，そこから z を求めて送り付ければいい．同じ方法でハッシュを取る必要があることに注意

#!/usr/bin/env python3
import socket
import json
import random
from hashlib import sha512
from Crypto.Util.number import bytes_to_long, long_to_bytes

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2

w = 0xdb968f9220c879b58b71c0b70d54ef73d31b1627868921dfc25f68b0b9495628b5a0ea35a80d6fd4f2f0e452116e125dc5e44508b1aaec89891dddf9a677ddc0
y = 0x1a1b551084ac43cc3ae2de2f89c6598a081f220010180e07eb62d0dee9c7502c1401d903018d9d7b06bff2d395c46795aa7cd8765df5ebe7414b072c8289170f0

HOST = "socket.cryptohack.org"
PORT = 13428

def sha512_int(a):
    h = sha512(str(a).encode()).digest()
    return bytes_to_long(h) % (2**511)

def main():
    s = socket.socket()
    s.connect((HOST, PORT))

    data = s.recv(4096).decode()
    print("[Server]", data.strip())

    data = s.recv(4096).decode()
    print("[Server]", data.strip())
    info = json.loads(data)

    r = random.randint(0, q-1)
    a = pow(g, r, p)
    e = sha512_int(a)
    z = (r + e*w) % q

    if pow(a, q, p) != 1:
        print("[!] something unexpected with a^q != 1, please re-try")
        return

    proof = {"a": a, "z": z}
    s.sendall((json.dumps(proof) + "\\n").encode())
    print("[Prover] Sent (a,z).")
    data = s.recv(4096).decode()
    print("[Server]", data.strip())

if __name__ == "__main__":
    main()