数字签名-认定消息的来源

在一定程度上，笔迹可以被模仿，甚至有一些人专门从事伪造签名和手写文件的职业。但要完美地模仿笔迹几乎是不可能的，总有一些细微差别可以区分真迹和伪造品。一个人的笔迹可以说是独一无二的，天然具有签名的性质。

假设你在设计一个电子投票系统，选民通过互联网远程投票，为了验证选票内容完整未被篡改，而且是通过选民真实产生的。如果我们用 MAC 实现会是什么样的？MAC 是对消息和密钥组合计算得到哈希值，在电子投票系统中，选票需要被多方验证，也就是密钥需要被多方共享，因此，用 MAC 实现是不合适的。

这种场景需要使用数字签名（Digital Signature），不仅具备 MAC 防伪造的特点，同时还具备公钥密码的特点，签名只能由私钥持有者产生，而所有公钥持有者都可以验证签名。

公钥密码的加密是通过公钥进行的，然后使用配对的私钥解密。而数字签名是反过来使用，使用私钥签名，而配对的公钥用来验证签名。就像签署文件签署一样，私钥的私有属性让数字签名具有防止抵赖的特点。

RSA 公钥密码可以用来生成签名和验证签名，它和加密解密过程并没有本质不同。

如果把 RSA 加密解密过程的密文当成消息，使用私钥计算后生成的内容就是签名，由于 RSA 密钥数学上的关联性，只需要用配对的公钥执行加密过程，计算出来的结果就是消息。再和原消息一比对是否一致就知道是否真实未被篡改了。

现在用 RSA 公钥密码实现电子投票系统，每位选民都持有私钥，在投票前，选民用私钥对选票进行了签名。系统收到选票后用手上的公钥验证选票是否真实且未被篡改，由于公钥的公开属性，任何持有对应公钥的人都可以查验选票。

一般不会直接对消息应用签名算法，而是先用单向哈希函数得出消息的哈希值，然后再对哈希值签名。因为签名算法的性能通常比单向哈希算法差得多，一般情况下，哈希值比消息本身短得多，与直接对消息签名相比，这两种做法是等效的，但是性能会好很多。

除了 RSA 之外，还存在其它多种数字签名算法，下面我们简单介绍一下 Rabin、EIGamal、 ECDSA、Schnorr 和 DSA。

Rabin：

Rabin 是一种签名算法，由以色列数学家 Michael O. Rabin 在1978提出，也是最早提出的数字签名方案之一。 Rabin 类似于 RSA，不同的是 Rabin 签名算法直接使用了 RSA 算法的平方取模运算，不需要进行额外的模幂运算，因此，Rabin 的签名和验证过程比 RSA 更加高效。

但是 Rabin 存在一个多解的固有缺陷。在 Rabin 签名算法中，签名 Y 是消息哈希值 X 的2次方模 N：$Y = X^2 \pmod N$ ，由于平方运算存在多解性，同一个签名，存在四个可能的不同消息。Rabin 签名算法通常会采用一些措施来缓解这个问题，比如对消息加入一定的填充位和对消息进行哈希后再签名。除此之外，Rabin 其安全性也是基于大整数的因子难分解问题，目前还没有有效的攻击手段能够在合理的时间内解决这问题。除非未来出现有效的大整数分解算法或是量子计算机的突破进展。

EIGamal

EIGamal 签名算法是一种基于离散对数问题的公钥签名算法，由 Taher ElGamal 在1985年提出。EIGamal 基于离散对数问题，算法相对简单。GnuPG 中也曾使用过 EIGamal 进行数字签名，但是1.0.2版本中数字签名的实现存在漏洞，现在的 GnuPG 中的 EIGamal 仅用于公钥加密。

EIGamal的 安全性基于离散对数问题的难度，具有很高的安全性。但是它涉及模幂运算和模逆运算，计算效率较低，特别是在处理大数据的时候。

ECDSA

ECDSA（Elliptic Curve Digital Signature Algorithm，椭圆曲线数字签名算法）是一种用于数字签名的密码算法，它基于椭圆曲线密码学（ECC）。相对于其他基于离散对数问题或大数分解问题的算法（如 DSA 和 RSA），ECC 的数学原理相对复杂，但是，对于相同的安全级别，ECC 的密钥长度要比 RSA 小得多，例如，256 位 ECC 密钥与 3072 位 RSA 密钥的安全性相当。ECDSA 的性能较高，在处理能力和存储空间有限的环境（如嵌入式系统）中特别有优势。

Schnorr 和 EdDSA

Schnorr 是一种数字签名算法。由德国数学家和密码学家 Claus Schnorr 于1989年提出。Schnorr 最初基于离散对数问题设计的，它也可以应用于椭圆曲线，使用椭圆曲线上的点来代替传统离散对数群中的元素，椭圆曲线版本的 Schnorr 签名称为 EdDSA （Edwards-curve Digital Signature Algorithm）。椭圆曲线版本的比最初基于离散对数版本的有更好的性能和更高的安全性。Schnorr 生成的签名较短，在存储空间或者带宽受限的环境中具有优势。Schnorr 还可以批量验证签名，也就是将多个签名组合成一个，单次验证多个签名，在来回传输数据代价较高的场景中特别有优势。

DSA

DSA（Digital Signature Algorithm）是一种数字签名算法，名字也叫数字签名算法。它是美国联邦签名算法标准。最初的版本是1991年 NSA 向 NIST 提交的设计，1993年成为联邦签名算法标准之一，DSA 基于模幂运算和离散对数问题的数学概念，是 Schnorr 和 ElGamal 的变体，不过DSA 的密钥生成速度相对较慢。虽然在早期受到美国政府专利限制，但 DSA 是一种成熟、安全的数字签名算法，有着广泛的使用。

对数字签名的攻击

要安全地使用数字签名，不仅要选择安全的算法，密钥也应当有足够长度，当然私钥是要妥善保密的，在做好这些的前提之下，针对数字签名的威胁主要来自中间人攻击。

这里我们举个例子，小明使用私钥对消息签名后，将消息和签名一同发送给小红。小红使用手上配对的密钥，验证消息与签名是否匹配。其实这里基于一个假设，即小红的公钥和小明的私钥是配对的。

小明给小红发送公钥的过程中，数据历经层层网络设备，如果公钥被中间人小黑截获，然后小黑将公钥换成自己的，小红和小明并不知情，小明以为公钥已经准确送达，小红认为收到的是来自小明的公钥。小明后续正常将消息签名后，通过网络发送，小黑将数据截获，替换成自己的消息和签名。小红收到数据后，用自己手上的公钥验证消息和签名，确认匹配，因为她的公钥、消息和签名都来自中间人。

这里问题在于一开始，接收方并没有验证公钥的真假，而且也无从验证，而是假设来自于真实的发送方，发送方也无法确信可以将公钥安全配送。下一篇我们会看到如何使用 PKI 来解决这个问题。