深入浅出零知识证明（三）：零知识证明的过程和基于RSA的零知识证明

让我们从快速回顾RSA是如何工作的开始，请记住，我们通常使用模某个数，而不是直接在整数上进行计算，这里的符号是"a + b ≡ c (mod n)"，意思是"(a + b) % n = c % n"。注意，"(mod n)"部分不适用于右边的"c"，而实际上适用于"≡"和同一方程中的所有其他"≡"。

现在我们来回顾一下RSA，证明者提出以下数字：

p，q：两个随机的秘密质数

n := p q

d：一个随机数，使得1 < d < n - 1

e：一个数字，使得d e ≡ 1 (mod (p-1)(q-1))。

公钥是(e, n)，私钥是d。质数p和q可以丢弃，且不能被泄漏给其他参与方。

通过以下方式对消息m进行加密：

E(m) := m^e % n

并通过以下方式解密c = E(m)：

D(c) := c^d % n。

由于c^d ≡ (m^e % n)^d ≡ m^{ed} (mod n)，并且指数m的乘法在模(p-1)(q-1)的乘法群中的计算类似于乘法，我们得到m^{ed} ≡ m (mod n)。此外，RSA的安全性依赖于n不能被有效地分解，因此无法从e计算出d（如果我们知道p和q，这将很容易）。

RSA的一个显著特点是它具有乘法同态性。通常情况下，这允许任意参与方，交换两个计算的顺序而不影响最终结果，则这两个计算被称为是同态的。

在同态加密的情况下，您可以对加密数据进行任何属性的计算（加法和乘法）。完全同态加密是存在的，但目前还不实用，它允许在加密数据上计算任意函数。在这里，对于RSA，我们只谈论乘法，进一步来说地说：E(x) E(y) ≡ xe ye ≡ (xy)e ≡ E(xy) (mod n)，即两个消息的加密的乘积等于消息的乘积的加密。

这种同态性已经允许某种形式的乘法零知识证明：证明者知道一些秘密数字x和y，并计算它们的乘积，但只发送加密版本a = E(x)，b = E(y)和c = E(xy)给验证者。验证者现在检查(ab) % n ≡ c % n，验证者只知道是乘积的密文以及乘积被正确计算了，但验证方既不知道n的两个因子，也不知道最后实际的乘积。

如果你将乘积替换为加法，这已经朝着区块链的方向发展，许多zkSNARK方案都是依赖于加法同态来构造的。

目前基于电路的zkSNARK，都是先将相应的证明（计算）任务规约为一个电路，并利用该电路来证明计算的正确性。同时，从RSA的例子也可以看出，我们可以使用特定算法的同态性来构造zkSNARK。

下一章，我们将给大家带来交互式零知识证明，及更详细的复杂度理论介绍。

分享仅供学习参考，若有不当，请联系我们处理。