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