数字签名机制 - Schnorr 机制

Schnorr机制是一种基于离散对数难题的知识证明机制，由德国数学家和密码学家Claus-Peter Schnorr在1990年提出。这种知识证明机制具有实现简单，验证速度较快等优点。最开始是为Smart Card这样的资源受限设备而设计。

经过这些年的发展，在原始的Schnorr机制上实现了多种多样的改进与功能，实现了高性能的数字签名，以及包括环签名，门限签名等复杂签名机制。

在这里参考Schnorr的论文与其他的参考资料，分析Schnorr机制的原始机制与实现。并分析现在主流的EdDSA的实现ED25519，以及如何在Schnorr机制上建立的复杂签名机制。

本文中所有出现的变量，小写字母表示标量，即一个数字，在这里指整数；大写字母表示离散对数问题中的参数，例如：椭圆曲线中的点。

Original Schnorr Scheme

原始的Schnorr机制是一个交互式的机制。允许在任何拥有相同生成元（指在离散对数问题中）的协议参与者双方，证明某一方拥有私钥 而不需要直接交换它。其中双方都拥有的生成元设为 ，证明者拥有私钥 。验证者从证明者处取得 ，其中 ， 即公钥。

Original Schnorr Signature的协议流程如下：

1. 证明者随机选择一个标量 ，然后计算出 。并将 发送至验证者。
2. 验证者回应一个随机的标量 。
3. 证明者回应一个标量，通过公式 计算。

因为离散对数问题是困难的，因此验证者不会知道 的值，验证者仅知道由 计算得到的 。但是验证者可以通过以下计算来验证是正确的：

• 由于，等式两边同时添加相同的生成元可得 。
• 由于，，可以化简得到 。

其中 是生成元，双方都可知， 验证者都知道，所以验证者可以轻松验证化简过的公式。

这个过程是零知识的，因为验证者并不能得到私钥 的值，却可以通过计算与通讯的方式验证证明者确实拥有私钥 。

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转换，可以将具体的验证者采用随机数预言机来代替。将验证者替换为随机数预言机后，外部的验证者便无法通过交换 来推出私钥 ，原本的 采用随机数预言机产生的随机数来表示。