C语言实现零知识证明（小白也能看懂的零知识证明算法入门教程）

什么是零知识证明？

想象这样一个场景：Alice 想向 Bob 证明她知道一个洞穴中魔法门的密码，但又不想告诉 Bob 密码本身。洞穴呈环形，有两个入口 A 和 B，中间由一扇需要密码才能打开的门连接。

Bob 站在洞口外，让 Alice 进入。然后 Bob 随机喊出“A”或“B”，要求 Alice 从指定出口出来。如果 Alice 知道密码，她总能从任意出口出来；如果不知道，她只有 50% 的概率猜对。重复多次后，Bob 就可以高度确信 Alice 确实知道密码——而整个过程 Alice 没有透露任何密码信息！

这就是零知识证明的核心思想：**完整性**（知道秘密就能通过验证）、**可靠性**（不知道秘密几乎无法通过）、**零知识性**（验证者得不到任何额外信息）。

用 C 语言模拟零知识证明

下面我们用 C 语言编写一个简化版的交互式零知识证明程序。我们将模拟“离散对数问题”中的零知识证明，这是许多真实 ZKP 系统的基础。

假设存在一个公开的大素数 p 和一个生成元 g。Alice 知道一个秘密 x，并公开 y = g^x mod p。她想向 Bob 证明她知道 x，而不泄露 x。

协议步骤：

1. Alice 选择随机数 r，计算 t = g^r mod p，发送 t 给 Bob。
2. Bob 随机发送一个挑战位 c ∈ {0, 1}。
3. 若 c = 0，Alice 返回 r；若 c = 1，Alice 返回 s = (r + c * x) mod (p-1)。
4. Bob 验证：若 c = 0，检查 g^r ≡ t mod p；若 c = 1，检查 g^s ≡ t * y^c mod p。

C 语言代码实现：

#include <stdio.h>#include <stdlib.h>#include <time.h>// 快速幂取模: (base^exp) % modlong long mod_exp(long long base, long long exp, long long mod) {    long long result = 1;    base = base % mod;    while (exp > 0) {        if (exp % 2 == 1)            result = (result * base) % mod;        exp = exp >> 1;        base = (base * base) % mod;    }    return result;}int main() {    // 公共参数（实际应用中应使用大素数）    long long p = 23;   // 小素数便于演示    long long g = 5;    // 生成元    // Alice 的秘密    long long x = 6;    // 秘密指数    long long y = mod_exp(g, x, p); // 公钥 y = g^x mod p    printf("公共参数: p = %lld, g = %lld\n", p, g);    printf("Alice 的公钥 y = %lld\n\n", y);    srand(time(NULL));    // 模拟多次交互以提高可信度    int rounds = 3;    for (int i = 1; i <= rounds; i++) {        printf("--- 第 %d 轮验证 ---\n", i);        // Step 1: Alice 选择随机 r，发送 t = g^r mod p        long long r = rand() % (p - 1) + 1;        long long t = mod_exp(g, r, p);        printf("Alice 发送 t = %lld\n", t);        // Step 2: Bob 随机选择挑战 c ∈ {0, 1}        int c = rand() % 2;        printf("Bob 发送挑战 c = %d\n", c);        // Step 3: Alice 计算响应        long long response;        if (c == 0) {            response = r;        } else {            response = (r + x) % (p - 1);        }        printf("Alice 发送响应 s = %lld\n", response);        // Step 4: Bob 验证        long long left, right;        if (c == 0) {            left = mod_exp(g, response, p);            right = t;        } else {            left = mod_exp(g, response, p);            right = (t * y) % p;        }        if (left == right) {            printf("✅ 验证通过！\n\n");        } else {            printf("❌ 验证失败！\n\n");            return 1;        }    }    printf("🎉 所有轮次验证成功！Bob 相信 Alice 知道秘密 x。\n");    return 0;}

为什么这叫“零知识”？

注意，在整个过程中，Bob 只看到了 t、c 和 s，但他无法从中推导出 x。因为每次的 r 是随机的，响应 s 也包含随机性，Bob 得到的信息等价于他自己可以模拟出来的（例如，先选 c，再选 s，反推 t）。因此，他没有获得任何关于 x 的新知识——这就是“零知识”的含义。

总结

通过这个简单的 C 语言程序，我们演示了C语言零知识证明的基本原理。虽然实际应用中的零知识证明（如 zk-SNARKs）要复杂得多，但核心思想是一致的：在不泄露秘密的前提下证明你知道它。

掌握 零知识证明算法 对理解区块链、隐私计算等前沿技术至关重要。希望这篇 零知识证明教程 能为你打开密码学的大门！如果你对 C语言密码学 感兴趣，不妨尝试扩展这个程序，比如使用更大的素数，或实现非交互式版本（Fiat-Shamir 变换）。

注：本示例仅用于教学目的，不可用于生产环境。真实系统需使用加密安全的随机数和大整数库。