Schnorr机制是一种基于离散对数难题的知识证明机制，由德国数学家和密码学家Claus-Peter Schnorr在1990年提出。这种知识证明机制具有实现简单，验证速度较快等优点。最开始是为Smart Card这样的资源受限设备而设计。
经过这些年的发展，在原始的Schnorr机制上实现了多种多样的改进与功能，实现了高性能的数字签名，以及包括环签名，门限签名等复杂签名机制。
在这里参考Schnorr的论文与其他的参考资料，分析Schnorr机制的原始机制与实现。并分析现在主流的EdDSA的实现ED25519，以及如何在Schnorr机制上建立的复杂签名机制。
本文中所有出现的变量，小写字母表示标量，即一个数字，在这里指整数；大写字母表示离散对数问题中的参数，例如：椭圆曲线中的点。
Original Schnorr Scheme
原始的Schnorr机制是一个交互式的机制。允许在任何拥有相同生成元（指在离散对数问题中）的协议参与者双方，证明某一方拥有私钥 而不需要直接交换它。其中双方都拥有的生成元设为
，证明者拥有私钥
。验证者从证明者处取得
，其中
，
即公钥。
Original Schnorr Signature的协议流程如下：
- 证明者随机选择一个标量
，然后计算出
。并将
发送至验证者。
- 验证者回应一个随机的标量
。
- 证明者回应一个标量
，通过公式
计算。
因为离散对数问题是困难的，因此验证者不会知道 的值，验证者仅知道由
计算得到的
。但是验证者可以通过以下计算来验证
是正确的：
- 由于
。
- 由于
，可以化简得到
。
其中 是生成元，双方都可知，
验证者都知道，所以验证者可以轻松验证化简过的公式。
这个过程是零知识的，因为验证者并不能得到私钥 的值，却可以通过计算与通讯的方式验证证明者确实拥有私钥
。
Problem of Original Schnorr Scheme
然而这样交互式的过程，会导致验证者通过"fork"的方式获得私钥 。验证者只需要简单的提供两个不同的随机值
，并要求证明者计算
，即可计算出
。这样一来，这个过程便无法公开的验证，因为一旦两个验证者相互串通，交换自己得到的值，便可以推出私钥
。
为了解决这个问题，后续将会通过对现有的协议进行Fiat–Shamir变换，使用Random oracles改造这个算法来使Schnorr原始的Schnorr Scheme变成可公开验证的非交互式算法。
Fiat–Shamir and Random oracles
上述原始Schnorr Scheme中存在的私钥泄露问题使得算法无法在公开的环境下使用。通过将原始的交互式协议转变为非交互式协议可以解决这个问题。
Fiat–Shamir变换是一种利用交互式零知识证明方案创建数字签名的方式。根据Fiat–Shamir变换，我们可以将原始方案中的证明者采用随机数预言机（Random oracle）来代替，利用这样的方式构造数字签名。
随机数预言机，即随机数函数，是一种针对任意输入得到的输出之间是项目独立切均匀分布的函数。理想的随机数预言机并不存在，在实现中，经常采用密码学哈希函数作为随机数预言机。
原本的设计中，Schnorr签名是一种交互式协议，需要一个实际存在的验证者与参与者，而根据Fiat-Shamir转换，可以将具体的验证者采用随机数预言机来代替。将验证者替换为随机数预言机后，外部的验证者便无法通过交换 来推出私钥
，原本的
采用随机数预言机产生的随机数来表示。
网友评论