### 使用 Python 实现零知识证明协议以测试两个随机数相等情况 为了实现零知识证明 (Zero-Knowledge Proof, ZKP)，可以采用一种简单的离散对数问题作为基础。以下是具体实现方式： #### 协议描述 1. **设定参数**: 假设有一个素数 $ p $ 和一个生成元 $ g $，其中 $ g $ 是模 $ p $ 的乘法群的一个生成元。 2. **私钥与公钥**: - 设定私钥为 $ x $ （即用户的秘密值）。 - 计算公钥为 $ h = g^x \mod p $。 3. **挑战阶段**: - 用户选择一个随机数 $ r $ 并计算承诺值 $ t = g^r \mod p $。 - 将 $ t $ 发送给验证者。 4. **响应阶段**: - 验证者发送一个随机挑战 $ c $ 给用户。 - 用户根据挑战计算响应 $ s = r + cx \mod (p-1) $。 5. **验证阶段**: - 验证者接收响应 $ s $ 并验证等式 $ g^s \stackrel{?}{=} th^c \mod p $ 是否成立。 #### 代码实现 ```python import random def generate_prime_and_generator(): """Generate a prime number and its generator.""" from sympy import nextprime p = nextprime(random.randint(1000, 2000)) # Generate a small prime for simplicity. g = find_primitive_root(p) return p, g def find_primitive_root(p): """Find a primitive root modulo p.""" phi_p = p - 1 factors = set() temp = phi_p i = 2 while i * i <= temp: if temp % i == 0: factors.add(i) while temp % i == 0: temp //= i i += 1 if temp > 1: factors.add(temp) for g in range(2, p): flag = True for factor in factors: if pow(g, phi_p // factor, p) == 1: flag = False break if flag: return g return None def zero_knowledge_proof(a, b, p, g): """ Perform the Zero Knowledge Proof protocol to test whether two numbers are equal or not. Parameters: a -- Private key of user A b -- Private key of user B p -- Prime modulus g -- Generator of multiplicative group mod p """ # Compute public keys ha = pow(g, a, p) hb = pow(g, b, p) # Prover's side: User A proves knowledge of 'a' r = random.randint(1, p - 2) # Random nonce t = pow(g, r, p) # Commitment value # Verifier sends challenge c = random.randint(1, p - 2) # Prover computes response sa = (r + c * a) % (p - 1) # Verify proof lhs_a = pow(g, sa, p) rhs_a = (t * pow(ha, c, p)) % p sb = (random.randint(1, p - 2) + c * b) % (p - 1) # Simulate incorrect private key lhs_b = pow(g, sb, p) rhs_b = (pow(g, random.randint(1, p - 2), p) * pow(hb, c, p)) % p result_a = (lhs_a == rhs_a) result_b = (lhs_b == rhs_b) return {"proof_for_a": result_a, "proof_for_b": result_b} # Example usage if __name__ == "__main__": p, g = generate_prime_and_generator() # Case where a equals b a = random.randint(1, p - 2) b = a results_eq = zero_knowledge_proof(a, b, p, g) print(f"When a == b ({a} == {b}): {results_eq}") # Case where a does not equal b b = random.randint(1, p - 2) while b == a: b = random.randint(1, p - 2) results_neq = zero_knowledge_proof(a, b, p, g) print(f"When a != b ({a} != {b}): {results_neq}") ``` --- ### 结果解释 1. 当 `a` 等于 `b` 时，验证方应该能够成功确认证明方的知识，因此输出结果应显示为 `True`。 2. 当 `a` 不等于 `b` 时，由于证明方使用的私钥不匹配，验证方将拒绝接受该证明，从而返回 `False`。 ---