密码学 | Schnorr 协议：零知识身份证明和数字签名
🥕原文： Schnorr 协议：零知识身份证明和数字签名
🥕写在前面： 本文属搬运博客，自己留存学习。文中的小写字母表示标量，大写字母表示椭圆曲线中的点。
1 Schnorr 简介
Schnorr 由德国数学家和密码学家 Claus-Peter Schnorr 在 1990 年提出，是一种基于离散对数难题的知识证明机制。
Schnorr 本质上是一个零知识证明协议，即证明者声称自己知道密钥 x x x 的值。通过使用 Schnorr 协议，证明者可以在不揭示 x x x 的值情况下，向验证者证明自己确实知道 x x x 的值。因此，你可以用 Schnorr 协议来证明自己确实拥有某个私钥。
Schnorr 中涉及到的技术有：哈希函数的性质、椭圆曲线的离线对数难题。其中，椭圆曲线的离线对数难题是指，已知椭圆曲线 E E E 和点 G G G，随机选择一个整数 d d d，容易计算 Q = d ∗ G Q=d*G Q=d∗G，但根据给定的 Q Q Q 和 G G G 来计算 d d d 就非常困难。
预备知识：椭圆曲线密码学😇
2 技术价值
Schnorr 的技术价值有二：
- 身份识别：证明你知道某个私钥
- 数字签名
3 交互式 Schnorr
原始的 Schnorr 机制是一个交互式的机制。在讲述其机制时，不得不请出密码学中的两个虚拟大人物 Alice 和 Bob 。注意，这两位可不是省油的灯，都存在作弊的可能性！
3.1 场景描述
允许任何拥有相同生成元 G G G 的协议参与者双方，能够证明其中一方拥有私钥 s k = a sk=a sk=a，而不需要直接交换私钥的值。假设协议参与者双方分别是 Alice 和 Bob 。目前证明者 Alice 拥有私钥 s k sk sk，并且验证者 Bob 已经从 Alice 处取得了她的公钥 P K PK PK，Bob 要在不知道 a a a 的情况下验证 Alice 知道它。
说明：私钥 s k sk sk 的值就是 a a a，Bob 要能验证 Alice 确实知道 a a a，但 Bob 不能知道 a a a 是多少。
3.2 协议流程
- Alice：随机选择一个标量 r r r，计算出 R = r ∗ G R=r*G R=r∗G，然后将 R R R 发送给 Bob；
- Bob：回应一个随机标量 c c c；
- Alice：通过计算 s = r + c ∗ s k s=r+c*sk s=r+c∗sk，将标量 s s s 回应给 Bob；
- Bob：将 s s s 转换为椭圆曲线上的点，即 s ∗ G s*G s∗G，然后验证 s ∗ G = ? R + c ∗ P K s*G \overset{?}{=} R+c*PK s∗G=?R+c∗PK。
个人感觉：Alice 的随机数 r r r 是为了隐藏 s k sk sk 的值，Bob 的随机数 c c c 是为了防止 Alice 撒谎。因为如果没有 c c c 的限制，Alice 可以随意地构造 s s s 以使验证通过，后文会进行说明。
上图是交互式 Schnorr 协议的协议流程。
3.3 零知识解释
由于 s = r + c ∗ s k s=r+c*sk s=r+c∗sk，因此等式两边同时乘以生成元 G G G 即可得到： s ∗ G = R + c ∗ P K s*G=R+c*PK s∗G=R+c∗PK，从而可以验证 Alice 确实拥有私钥 s k sk sk。与此同时，验证者 Bob 并不能得到私钥 s k sk sk 的值，因此这个过程是零知识的，且是交互式的。
碎碎念： R + c ∗ P K R+c*PK R+c∗PK 的本质就是 ( r + c ∗ s k ) ∗ G (r+c*sk)*G (r+c∗sk)∗G，只要能猜到一个等于 ( r + c ∗ s k ) (r+c*sk) (r+c∗sk) 的 s s s 值就能使等式成立，其中 r r r 和 c c c 又是已知的。在这种前提下 Schnorr 的安全性还是很好，说明攻击者很难试到正确的 s s s 值？
3.4 安全性分析
随机数 r r r
由于是椭圆曲线上的离散对数问题，因此在知道 R R R 和 G G G 的情况下，通过 R = r ∗ G R=r*G R=r∗G 解出 r r r 是不可能的，从而保证了 r r r 的私密性。但是，该协议也只能在证明者和验证者的一对一安全通道中进行。
这是由于该协议存在交互过程。在公开验证的场景中，一旦两个验证者相互串通，交换自己得到的值，便可以推出私钥。因此，交互式 Schnorr 协议不支持公开验证。
不妨来个数学理论推导：在公开验证的条件下，两个验证者分别提供两个不同的随机值 c 1 c_1 c1 和 c 2 c_2 c2，并要求证明者计算 s 1 = r + c 1 ∗ s k , s 2 = r + c 2 ∗ s k s_1 = r + c_1*sk,\ s_2 = r + c_2*sk s1=r+c1∗sk, s2=r+c2∗sk，验证者即可推出：
s k = s 1 − s 2 c 1 − c 2 sk=\frac{s_1-s_2}{c_1-c_2} sk=c1−c2s1−s2
因此，这个过程便无法公开验证。
话说证明者两次为什么要选择同样的 r r r 呢？难道这是公开验证的要求？
随机数 c c c
进一步分析，为什么需要验证者回复一个随机标量 c c c 呢？答：防止 Alice 造假！
如果 Bob 不回复一个 c c c，就变成了如下的一次性交互：
如上图所示，一次性交互去掉了第二步 Bob 回复 c c c，并将之前的第一步和第三步合并成了一步。同样地，Alice 的随机数 r r r 是为了隐藏 s k sk sk，Bob 能够通过 R R R 来完成验证，但不能通过 R R R 来倒推 r r r。
由于是椭圆曲线上的离散对数问题，因此在知道 P K PK PK 和 G G G 的情况下，通过 P K = a ∗ G PK = a * G PK=a∗G 倒推 a a a 是不可能的，从而保证了 a a a 的私密性。但是该方案存在重大问题。
因为 r r r 和 s s s 都是 Alice 自己生成的，同时她又知道 Bob 的验证方式是拿 R + P K R+PK R+PK 和 s ∗ G s * G s∗G 进行比较，所以她完全可以在不知道 a a a 的情况下构造： R = r ∗ G − P K R = r * G - PK R=r∗G−PK 和 s = r s = r s=r。
这样 Bob 的验证过程就变成了：
s ∗ G = ? R + P K ⇒ r ∗ G = ? r ∗ G − P K + P K s * G \overset{?}{=} R + PK \Rightarrow r * G \overset{?}{=} r * G - PK + PK s∗G=?R+PK⇒r∗G=?r∗G−PK+PK
上述等式是永远成立的，因此这种方案并不正确。
4 非交互式 Schnorr
通过 3.4 节的讨论可知，交互式 Schnorr 协议存在私钥泄露的问题，因此该协议无法在公开验证的场景中使用。通过将原始的交互式协议转变为非交互式协议可以解决这个问题。
这是因为没有交互过程了，所以两个验证者之间没有机会进行串通。
4.1 协议流程
- Alice：随机选择一个 r r r，并依次计算 R = r ∗ G , c = H a s h ( R , P K ) , s = r + c ∗ s k R=r*G,\ c=Hash(R,PK),\ s=r+c*sk R=r∗G, c=Hash(R,PK), s=r+c∗sk；
- Alice：生成证明 ( R , s ) (R,s) (R,s)；
- Bob (或者任意一个验证者)：计算 c = H a s h ( R , P K ) c=Hash(R,PK) c=Hash(R,PK)；
- Bob (或者任意一个验证者)：验证
s
∗
G
=
?
R
+
c
∗
P
K
s*G \overset{?}{=} R+c*PK
s∗G=?R+c∗PK。
下图是非交互式 Schnorr 协议的协议流程：
Alice 一个人把该算的都算完了，然后再全部发送给 Bob😇
4.2 安全性分析
在交互式 Schnorr 协议中，为了不让 Alice 造假，需要 Bob 发送一个 c c c 值，并要求 Alice 将 c c c 值构造进公式中。由此可见，只要 Alice 自己选择一个无法造假的且大家公认的 c c c 值，并将其构造进公式中，这个问题就解决了。如下图所示：
使用 Hash 函数计算 c c c 值，达到了两个目的：
- 一是，Alice 在产生 R R R 之前，没有办法预测 c c c，即使 c c c 是 Alice 自己计算的；
- 二是，
c
c
c 是通过 Hash 函数计算的，会均匀分布在一个整数域内，因此可以视为一个随机数。
请注意：Alice 绝不能在产生 R R R 之前预测到 c c c，不然，Alice 就等于变相具有了「时间倒流」的超能力，从而能任意愚弄 Bob 。
由于一个密码学安全的 Hash 函数是「单向」的，比如 SHA256 等。
单向性是指，通过一个 Hash 值输出很难或者不可能推导出原始输入数据。即在已知 c c c 值的情况下，无法反推 ( R , P K ) (R,PK) (R,PK) 的值。换句话说，即使 Alice 找到某 c c c 值很适合作弊，她也无法找到对应的 ( R , P K ) (R,PK) (R,PK) 值。
即使 c c c 是 Alice 计算的，Alice 也没有能力通过挑选 c c c 来进行作弊。因为只要 Alice 一产生 R R R， c c c 就相当于固定下来了。此外，Alice 可直接发送 ( R , s ) (R,s) (R,s) 给 Bob，由于 Bob 拥有 Alice 的公钥 P K PK PK，因此 Bob 可自行计算出 c c c 值。然后验证：
s ∗ G = ? R + c ∗ P K s*G \overset{?}{=} R + c*PK s∗G=?R+c∗PK
为了使验证等式恒成立，Alice 可以随意地构造毫无关系的 R R R 值和 c c c 值吗？答：当然不行。到时候 c c c 值是由 Bob 亲自算的，算出来的 c c c 值一定与 R R R 值配套，Alice 的构造都是白干。
4.3 零知识解释
整个过程中 Alice 并未暴露自己的私钥，且 Bob 无法通过正常手段或作弊手段获取 Alice 的私钥，因此也是零知识的。
5 Schnorr 用于数字签名
提出数字签名的出发点有二：
- 一是，当消息基于网络传输时，接收方希望证实消息 m m m 在传递过程中没有被篡改；
- 二是，希望确认发送者的身份，即发送者有一个私钥，且私钥和消息
m
m
m 进行关联计算。
针对发送者证明自己的身份。这个很简单，正是 Schnorr 协议的功能。即能够向对方证明「我拥有私钥」这个陈述。并且这个证明过程是零知识的，不会泄露关于「私钥」的任何知识。
5.1 流程
那么私钥是如何和消息 m m m 关联的呢？我们修改 c c c 的计算过程：
m = "白日依山尽，黄河入海流" c = Hash(R, m)
为了保证攻击者不能随意伪造签名，这里利用了离散对数难题和 Hash 函数满足抗第二原象这个假设。
下图就是基于非交互式 Schnorr 协议的数字签名方案：
与原始协议的主要区别在于：
- H a s h ( R , P K ) ⇒ H a s h ( R , m ) Hash(R,PK) \Rightarrow Hash(R,m) Hash(R,PK)⇒Hash(R,m) 将公钥替换为了待签名的消息
-
(
R
,
s
)
⇒
(
c
,
s
)
(R,s) \Rightarrow (c,s)
(R,s)⇒(c,s) 将
R
R
R 替换为了
c
c
c，后文会进行说明
5.2 优化
优化：Alice 发给 Bob 的内容不是 ( R , s ) (R,s) (R,s) 而是 ( c , s ) (c,s) (c,s)，这是因为 R R R 可以通过 c , s c,s c,s 计算出来。
注：为什么说这是一个「优化」呢？
假设我们采用了非常接近 2 256 2^{256} 2256 的有限域，也就是说 s s s 是 256 比特，那么椭圆曲线群的大小也差不多要接近 256 比特，这样一来，把 2 256 2^{256} 2256 开平方根后就是 2 128 2^{128} 2128，所以说 256 比特椭圆曲线群的安全性只有 128 比特。那么，挑战数 c c c 也只需要 128 比特就足够了。
这样 Alice 发送 c c c 要比发送 R R R 要更节省空间，而后者至少需要 256 比特。 c c c 和 s s s 两个数值加起来总共 384 比特。相比现在流行的 ECDSA 签名方案来说，可以节省 1/4 的宝贵空间。现在比特币开发团队已经准备将 ECDSA 签名方案改为一种类 Schnorr 协议的签名方案 —— MuSig，可以实现更灵活地支持多签和聚合。
6 Fiat-Shamir 变换
上述通过 Hash 函数来把一个交互式证明系统，转换为非交互式证明系统的方法称为 Fiat-Shamir 变换，该变换通过减少通信的步骤提高了通信的效率。
Fiat-Shamir 变换，又叫 Fiat-Shamir Heurisitc 启发式，或者 Fiat-Shamir Paradigm 范式。
Fiat-Shamir 变换允许将交互步骤替换为非交互随机数预言机。
随机数预言机，即随机数函数，是一种针对任意输入得到的输出之间是相互独立且均匀分布的函数。理想的随机数预言机并不存在，在实现中，经常采用密码学哈希函数作为随机数预言机。
下面是一个示例图，大家可以迅速理解 Fiat-Shamir 变换的做法：
