Cyptohack ZKPs Writeup

什么是零知识证明

A zero-knowledge proof (ZKP) is a technique that enables one party (the prover) to demonstrate to another party (the verifier) the truth of a certain statement without revealing any additional information besides the fact that the statement is true. The core idea behind zero-knowledge proofs is that while it’s straightforward to prove you have certain knowledge by disclosing it, the real challenge lies in proving you have that knowledge without actually revealing the knowledge itself or any details about it.

零知识证明（Zero-Knowledge Proof，简称ZKP）是一种技术，使一方（称为“证明者”）能够向另一方（称为“验证者”）证明某个陈述的真实性，同时不泄露除该陈述为真这一事实以外的任何其他信息。零知识证明的核心理念在于：尽管通过直接披露信息来证明自己拥有某种知识是较为直接的方式，但真正的挑战在于如何在不暴露该知识本身或其任何细节的前提下，仍能证明自己确实掌握了这项知识。

例子：
你需要向你的一位色盲朋友维克多证明，两只形状完全相同的球（一只是红色，另一只是绿色）是不同的，但又不能透露哪只是红的、哪只是绿的。为此，你采用了一种特定的证明系统。

你先向维克多展示这两只球。他由于无法分辨颜色，看不出它们的区别。接着他将球藏起来，随机选出一只给你看，然后可能会将它换成另一只，也可能不换，再次展示给你。你需要判断他是否交换了球。由于你能通过颜色分辨球的不同，你每次都能准确判断他是否更换了球。

这个过程重复足够多的次数（例如50次），而你每次都能正确识别是否换了球，这让维克多确信两只球确实不同，但他依然无法得知哪只是红色，哪只是绿色。这个证明过程没有泄露除“这两只球不同”之外的任何信息，因此，这是一个零知识证明的例子。

Sigma Protocol

ZKP Introduction

题

解

1	crypto{1985}

论文链接：
https://dl.acm.org/doi/10.1145/22145.22178
https://dl.acm.org/doi/pdf/10.1145/22145.22178

Proofs of Knowledge

题

注意到：

$g^z \equiv g^{r+ew} \equiv g^r \cdot (g^w)^e \equiv ay^e \text{ mod } p$

论文链接：https://cs.au.dk/~ivan/Sigma.pdf

附件：

import random
from utils import listener


FLAG = "crypto{????????????????????????}"

# Diffie-Hellman group (512 bits)
# p = 2*q + 1 where p,q are both prime, and 2 modulo p generates a group of order q
p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2


# w,y for the relation `g^w = y mod P` we want to prove knowledge of
# w = random.randint(0,q)
# y = pow(g,w,P)
w = 0x5a0f15a6a725003c3f65238d5f8ae4641f6bf07ebf349705b7f1feda2c2b051475e33f6747f4c8dc13cd63b9dd9f0d0dd87e27307ef262ba68d21a238be00e83
y = 0x514c8f56336411e75d5fa8c5d30efccb825ada9f5bf3f6eb64b5045bacf6b8969690077c84bea95aab74c24131f900f83adf2bfe59b80c5a0d77e8a9601454e5

assert (y%p) >= 1
assert pow(y, q, p) == 1

class Challenge:
    def __init__(self):
        self.before_input = "Prove to me that you know an w such that g^w = y mod p. Send me a = g^r mod p for some random r in range(q)\n"
        self.state = "CHALLENGE"

    def challenge(self, msg):
        if self.state == "CHALLENGE":
            # Prover sends a randomly sampled `A` value from Z_p* to verifier
            self.a = msg["a"]
            if (self.a%p) < 1 or pow(self.a, q, p) != 1:
                self.exit = True
                return {"error": "Invalid value"}

            # Verifier sends a random challenge sampled from range(0, 2^t) where 2^t <= q
            self.e = random.randint(0,2**511)
            self.state = "PROVE"
            return {"e": self.e, "message": "send me z = r + e*w mod q"}
        elif self.state == "PROVE":
            # Prover sends z = r + e*w mod q to the Verifier
            z = msg["z"]

            self.exit = True

            # Verifier checks g^z = A*h^e mod p
            if pow(g,z,p) == (self.a*pow(y,self.e,p)) % p:
                return {"flag": FLAG, "message": "You convinced me you know an `w` such that g^w = y mod p!"}
            else:
                return {"error": "something went wrong :("}


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13425)

解

注意，这里给服务器发送参数必须用JSON格式，它返回的也都是这个格式的。

from pwn import *
import json
import random

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2

w = 0x5a0f15a6a725003c3f65238d5f8ae4641f6bf07ebf349705b7f1feda2c2b051475e33f6747f4c8dc13cd63b9dd9f0d0dd87e27307ef262ba68d21a238be00e83


r = remote("socket.cryptohack.org", 13425)

random_r = random.randint(0, q)
a = pow(g, random_r, p)

# 发送 a，注意是 JSON 格式
r.sendafter(b"for some random r in range(q)\n",json.dumps({"a": a}).encode())

line = r.recvline()
response = json.loads(line.decode())
e = response["e"]

z = (random_r + e * w) % q

r.sendline(json.dumps({"z": z}).encode())

print(r.recvline().decode())
# {"flag": "crypto{sigma_protocol_complete!}", "message": "You convinced me you know an `w` such that g^w = y mod p!"}

Special Soundness

简单来讲就是如果2次证明使用的是一个a，那么就可以通过这些传递的参数计算出w来。

题

解

这道题依旧用的上面提到的Protocol。

由于可以任意挑选$e$的值，所以最简单的办法就是第一轮选择$e_1=1$，第二轮选择$e_2=2$，那么（由于$a_1=a_2$）就有：

$z_2-z_1 \equiv (r_1+e_1w) - (r_2+e_2w) \equiv w \text{ mod } q$

from pwn import *
import json
import random
from Crypto.Util.number import long_to_bytes

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2


r = remote("socket.cryptohack.org", 13426)
# 第一轮
r.recvuntil(b"such that y = g^w mod p.\n")
line = r.recvline()
response1 = json.loads(line.decode())
a1 = response1["a"]
print(response1["message"])
# send random e in range 0 <= e < 2^511

e = 1
r.sendline(json.dumps({"e": e}).encode())

line = r.recvline()
response1 = json.loads(line.decode())
z1 = response1["z"]
print(response1["message"])
# not convinced? I'll happily do it again!

# --------------------------------------------------------------------
# 第二轮
line = r.recvline()
response2 = json.loads(line.decode())
a2 = response2["a2"]
print(response2["message"])
# send random e in range 0 <= e < 2^511

e = 2
r.sendline(json.dumps({"e": e}).encode())

line = r.recvline()
response2 = json.loads(line.decode())
z2 = response2["z2"]
print(response1["message"])
# not convinced? I'll happily do it again!


# --------------------------------------------------------------------
w = long_to_bytes((z2-z1)%q)
print(w)
# b'crypto{specially_sound_sigmas}\xf7c\xb0H\xa1j\t\x9f\x9ab`%\xf7\xe3\x1552\x15\xda%\xf7\xf5yk\xd2\xa7\x1f\xbb3\x8f\xfd&'

当然其实选择随机的$e$也可以计算出$w$：

$w \equiv (z_2-z_1) \cdot (e_2-e_1)^{-1} \text{ mod } q$

from pwn import *
import json
import random
from Crypto.Util.number import long_to_bytes

p = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef
q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7
g = 2


r = remote("socket.cryptohack.org", 13426)
# 第一轮
r.recvuntil(b"such that y = g^w mod p.\n")
line = r.recvline()
response1 = json.loads(line.decode())
a1 = response1["a"]
print(response1["message"])
# send random e in range 0 <= e < 2^511

e1 = randint(0,2**511)
r.sendline(json.dumps({"e": e1}).encode())

line = r.recvline()
response1 = json.loads(line.decode())
z1 = response1["z"]
print(response1["message"])
# not convinced? I'll happily do it again!

# --------------------------------------------------------------------
# 第二轮
line = r.recvline()
response2 = json.loads(line.decode())
a2 = response2["a2"]
print(response2["message"])
# send random e in range 0 <= e < 2^511

e2 = randint(0,2**511)
r.sendline(json.dumps({"e": e2}).encode())

line = r.recvline()
response2 = json.loads(line.decode())
z2 = response2["z2"]
print(response1["message"])
# not convinced? I'll happily do it again!


# --------------------------------------------------------------------
w = long_to_bytes((z2-z1) * pow(e2-e1,-1,q)%q)
print(w)
# b'crypto{specially_sound_sigmas}\xf7c\xb0H\xa1j\t\x9f\x9ab`%\xf7\xe3\x1552\x15\xda%\xf7\xf5yk\xd2\xa7\x1f\xbb3\x8f\xfd&'