07 数字签名

数字签名方案的定义

消息的真实性在公钥加密的环境下是比私钥环境更重要的问题，因为在公钥加密中任何人都可以加密消息并发送给接收方。类比消息认证码MAC，在非对称密码学中我们用数字签名(digital signature)来做消息认证。定义如下：

一个数字签名方案是一个三元组$(\text{Gen},\text{Sign},\text{Vrfy})$：输入$n$，$\text{Gen}(n)$输出公钥$k_p$和私钥$k_s$（并不是用来做加密而是用来做认证的）；签名算法$\text{Sign}$接受消息$m$与私钥$k_s$，生成签名(sign) $\sigma=\text{Sign}_{k_s}(m)$；验证程序$\text{Vrfy}$接受消息$m$，签名$\sigma$以及公钥$k_p$作为输入，如果输出$1$代表认证成功，输出$0$代表认证失败。

从以上定义可以看出，只有私钥持有方才能生成签名，而只要持有公钥就能进行认证。也就是说，一个数字签名方案只能用于生成生成私钥的人的签名，而全世界所有的人都可以认证该签名的合法性。

安全性定义

同样仿照私钥，我们可以给出数字签名方案的安全性定义：

考虑以下实验$SigForge_{\mathcal{A}, \Pi}(n)$：输入$n$，由$\text{Gen}$生成$(k_p,k_s)$；敌手$\mathcal{A}$得到输入$k_p$，询问签名oracle多项式次，得到许多二元组$(m,\sigma)$；敌手最终输出一个不曾询问过oracle的消息$m_0$和对应的签名$\sigma_0$，如果通过认证$\text{Vrfy}_{p_k}(m_0,\sigma_0)=1$，就称敌手成功。如果任何敌手成功的概率都满足$\Pr[SigForge_{\mathcal{A},\Pi}(n)=1]\leq \text{negl}$，就称该方案是安全的。

The Schnorr Signature Scheme

下面我们构造一个基于Diffie-Hellman假设的安全的数字签名方案，称为Schnorr签名方案。

Gen：输入$n$给$\text{Gen}$，$\text{Gen(n)}$输出一个关于Diffie-Hellman假设安全的$G,q,g$；随机选取$x \in \Z_q$，令$h=g^x$，输出公钥$(G,q,g,h)$，设置私钥为$x$；$\text{Gen}$还需要输出一个$\{0,1\}^\ast$到$\Z_q$的哈希函数$H$，我们要求这个哈希函数是collision-resistant的。

Sign：输入私钥$x$和消息$m$，均匀随机选取$y\in\Z_q$，令$r:=H(g^y\|m)$，计算$s=(rx+y)\mod q$，输出签名$\sigma=(r,s)$。

Vrfy：输入消息$m$和签名$(r,s)$，计算$z=g^s\cdot h^{-r}$，判断是否成立$H(z\|m)=r$，如果是输出1，否则输出0。

我们来验证这一方案的正确性。对于由Sign生成的签名，有$z=g^{rx+y}\cdot g^{-xr}=g^y$，因此$H(z\|m)=H(g^y\|m)=r$，成立。

下面我们要验证这一方案的安全性。证明的sketch是：如果有敌手能以大于$\text{negl}$的概率forge一对消息和签名$(m^*,(r^*,s^*))$，那么我们可以认为有$r^*=H(g^y\|m^*)$（因为我们假设了哈希函数是collision-resistant的，所以$r^*\neq H(g^y\|m)$的概率是negligible的）。于是根据$s^*=r^*x+y\mod q$，我们可以得到$x=(s^*-y)(r^*)^{-1}\mod q$，这样我们就得到了$x,y$之间的联系，于是可以攻破Diffie-Hellman假设。一个严谨的证明可以参见Introduction to Modern Cryptography 13.5, “The underlying intuition for the Schnorr signature scheme is best explained by taking a slight detour to discuss (public-key) identification schemes. We then describe the Fiat–Shamir transform that can be used to convert identification schemes to signature schemes in the random-oracle model. Finally,we present the Schnorr identification scheme—and corresponding signature scheme—based on the discrete-logarithm problem”.

总结

我们总结一下到目前为止我们学习的公钥加密的big picture。我们基于离散对数问题构造了Diffie-Hellman假设，利用Diffie-Hellman假设我们可以实现Key Exchange，可以实现一般的Public Key Encryption，可以实现数字签名算法。在公钥加密中，除了基于离散对数的Diffie-Hellman假设，还有基于大整数分解(factoring)的RSA假设，利用RSA假设同样也可以实现一套公钥加密算法和数字签名算法，这里因为课时限制原因就不展开了。

值得指出的是，离散对数假设和大整数分解假设对于量子计算机都是不安全的。换言之，如果量子计算机被最终实现出来，那么基于离散对数假设和大整数分解的方案都会被攻破（因为量子计算机不能再被认为是一个PPT的敌手了）。为此，密码学家也在寻找新的假设（例如LWE等等），构建对于量子计算机安全的密码学方案，这类算法称为后量子算法。