3.3 数字签名
前面介绍的报文认证可以保护信息交换双方不受第三方的攻击，但是它不能处理通信双方自己产生的攻击，例如：假定小张使用如图3-4(a)所示的方法给小王发送一条消息，考虑下面的两种情形：
（1）小王可以伪造一条消息并称该消息来自小张。小王只需产生一条消息，用小张和小王共享的密钥对消息的散列码加密并附在消息的后面即可。
（2）小张可以否认曾发送过某条消息。因为小王可以用他们间共享的密钥伪造消息，所以无法证明小张确实发送过该消息。
上面的两种情况都是法律上比较关注的，特别是在涉及金融交易时。在收发双方不能完全相互信任的情况下，就需要除报文认证之外的其他方法来解决这些问题。
在以书面文件为基础的传统事务处理过程中，常常以手写签名的形式验证用户身份，手写签名具有法律意义。以数据文件为基础的现代事务处理过程需要采用电子形式的签名认证用户身份，这种签名方式被称为数字签名（digital signature），也被称为电子签名。我国在2005年4月1日开始施行《电子签名法》，该法律确立了数字签名在我国的法律效力。
3.3.1 数字签名的基本概念
数字签名以密码技术为基础，其安全性取决于签名所使用的密码系统的安全程度。目前，数字签名主要通过公开密钥密码系统实现，此类数字签名可以看作公开密钥密码系统加密过程的颠倒使用。签名者使用自己的私钥处理文件，完成签名，其他用户用签名者的相应公钥验证文件，确定签名的真伪。签名过程利用了公开密钥密码系统的特性，只有签名者本人知道自己的私钥，他人无法通过签名者的公钥破解签名者的私钥，因此可以以私钥标识签名者的身份。信息如果是通过某个用户的私钥处理而得到的，则信息必定是由该用户所处理的，并愿意承担相应的责任。
完善的数字签名体制需要满足以下条件：
（1）签名不能伪造。签名是签名者对文件内容认同的证明，其他人无法对签名进行伪造。
（2）签名不可抵赖。这是对签名者的约束，签名者对文件施行签名以后，不能否认自己的签名行为。
（3）文件在签名后不可改变。在签名者对文件签名以后其他人不能再修改文件内容。
（4）签名不可重复使用。可以采用增加时间标记或者序号标记的方法，防止签名被攻击者重复使用。
（5）签名容易验证。对于签名的文件，一旦发生签名真伪性方面的纠纷，任何第三方都可以准确、有效地进行仲裁。
数字签名体制包括两方面的处理，一方面是签名者施加签名，另一方面是用户验证签名。假设签名者A的私钥为SKA。以SIG表示施加签名的算法，以m表示被签名的数据，以s表示产生的签名信息。A使用自己的私钥SKA对数据签名，签名过程可以描述为SIG(SKA,m)=s。
验证签名的算法以VER表示，用以鉴别特定的签名s是否的确由声称的签名者A产生。验证需要使用A的公钥PKA，验证过程可以描述为VER(PKA,s)。在验证过程中，如果可以通过PKA从签名信息s中恢复被签名的数据m，或者其他能够标识m的信息，则可推断数据m源于用户A。
对传统的书面文件进行手写签名，签名后的文件包括两部分信息，首先是文件的主体内容，其次是签名者的手写签名。由于纸张的特性，一旦出现对纸张上信息内容的涂改、拼凑，其他人很容易发现异常。因此，攻击者难以在他人完成手写签名后，修改文件或者将手写签名与其他文件拼接。数字签名同样需要保证数据文件的完整性，防止攻击者篡改签名数据。
利用公开密钥密码系统进行数字签名，由于私钥为签名者所有，因此其他人难以伪造，签名者也无法否认自己的签名。同时，由于公钥完全公开，任何人都能够验证签名者的签名。为了防止在数字签名后，被签名的数据遭到修改，需要为签名算法增加一项限制条件：如果m1≠ m2，要求SIG(SKA,m1)≠ SIG(SKA,m2)。
该限制条件可以理解为只要数据内容不同，签名信息就应当不同，从而避免攻击者采用张冠李戴的手法，将签名者对某段数据的签名移植到其他数据上。此限制条件的满足要求签名算法产生的签名与被签名的数据长度相同，而在实际应用中为了节省存储开销都会希望签名能够短一些。因此，数字签名通常采用相对而言较为宽松的一个限制条件：即使存在m1≠ m2，SIG(SKA,m1)=SIG(SKA,m2)，但对于给定的数据m1和签名SIG(SKA,m1)，攻击者无法通过计算找到相应的m2。通过这样的限制条件为被签名数据的完整性提供保证。
在介绍公开密钥密码系统时已经提到，以PK表示公钥，SK表示对应的私钥，E表示加密算法，D表示解密算法，m表示任意的明文，如果D(PK，E(SK,m))=m，则该公开密钥密码系统能够用于认证数据发送方的身份，即可以用于数字签名。1994年，美国国家标准与技术学会基于ElGamal公开密钥密码系统制定了数字签名标准DSS（Digital Signature Standard）。2000年，RSA公开密钥密码系统被扩充到DSS中实现数字签名。此外，椭圆曲线密码等很多公开密钥密码系统都可以用于实现数字签名。下面首先介绍基于RSA的数字签名方法。
3.3.2 利用RSA密码系统实现数字签名
首先，验证RSA公开密钥密码系统是否能够应用于数字签名，即条件E(PK,D(SK,m))=m是否满足。RSA公钥系统中用户的公钥PK以{e,n}表示，与之对应的私钥SK以{d}表示，采用m表示明文，c为相应的密文，RSA系统的加密过程可以表示为：
c=E(PK,m)=memod n
相应的解密过程表示为：
m=D(SK,c)=cdmod n
作为一种密码系统，RSA首先必然满足D(SK,E(PK,m))=m，即明文通过公钥加密后，可以由对应的私钥解密。要判断条件E(PK,D(SK,m))=m是否满足，可以逐步分析：
E(PK,D(SK,m))=(md)emod n=(me)dmod n=D(SK,E(PK,m))=m
由上式可知E(PK,D(SK,m))=m，即RSA公开密钥密码系统符合数字签名的条件，能够应用于数字签名。
基于RSA算法进行数字签名时，如果需要签名的消息是m，签名者的私钥SK为{d}，则签名者施加签名的过程可以描述为s=D(SK,m)=mdmod n，其中s为签名者对m的签名。
与签名过程相对应，验证签名需要用到签名者的公钥PK，以{e,n}表示签名者的公钥，在获得签名信息s后，验证签名的过程可以描述为：
m＇=E(PK,s)=semod n
如果m＇=m，则可以判断签名s的签名者身份真实。
举一个简单的实例来看，用户张三的公钥为{79,3337}，对应的私钥为{1019}。张三想把消息72发送给其他用户，在发送前他用自己的私钥对消息进行签名：
。其他用户在接收到消息和签名以后，可以通过张三的公钥对签名进行验证从而确定消息是否的确由张三发出：
，计算所得到的结果与接收到的消息72一致，可以确定消息是由张三发出的，而且消息在传输过程中没有被修改过。
下面对使用RSA进行数字签名与使用RSA进行数据加密进行比较。首先，两者的目的截然不同。加密的目的主要是确保消息的保密性，防范未授权用户获取消息内容。数字签名的目的是对消息发送方的身份进行认证，发送方在对消息进行数字签名后将无法否认发送的消息，此外，数字签名还能为消息的完整性提供有力保证。其次，两者在密钥的使用上存在明显区别。如果需要在网络上传送加密的消息，发送方使用接收方的公钥加密消息，通过网络传送密文，接收方使用自己的私钥进行解密操作，将密文恢复为明文。在数字签名时，发送方使用自己的私钥对消息进行签名，接收方以及所有其他用户可以通过发送方的公钥对签名进行验证，确定发送者的身份。
数字签名无法保证消息的保密性，因为公钥完全公开，所有用户都可以通过签名者的公钥恢复签名的信息。如果不仅要求认证消息的发送方，而且需要确保消息的保密性，可以对数字签名进行加密。发送方首先使用自己的私钥对消息进行签名，再使用接收方的公钥对数字签名进行加密，将加密结果通过网络发送。接收方在接收后，先用自己的私钥进行解密，恢复数字签名，而后利用发送方的公钥验证签名。采用这种发送方先签名后加密、接收方先解密后验证的方法，可以认证发送方的身份并同时确保消息的保密性。
3.3.3 利用ElGamal密码系统实现数字签名
第2章介绍了ElGamal密码系统在加密方面的应用，下面介绍如何用ElGamal实现数字签名。
选择一个素数q，获取素数q的一个原根a，将q和a公开。生成一个随机数x作为其秘密的解密密钥，使得1≤x≤q–1，计算y=axmod q，则公钥为 (y,a,q)，私钥是x。
1.生成签名
设用户A要对明文消息m进行签名，1≤m≤q– 1，签名过程如下：
（1）用户A随机选择一个随机数k，1≤k≤q– 1。
（2）计算r=akmod q。
（3）计算s=(m– x× r)k-1mod (q-1)。
（4）以(r,s)作为m的签名，并将（m,r,s）发给用户B。
2.验证签名
用户B收到（m,r,s）后的验证过程如下：
如果(ammod q)=(yr× rs)mod q成立，则验证通过。
为了安全，随机数x必须是一次性的。由于取(r,s)作为m的签名，所以ElGamal数字签名的数据长度是明文的两倍。另外，ElGamal数字签名需要使用随机数k，这就要求在实际应用中要有高质量的随机数生成器。
3.3.4 利用椭圆曲线密码实现数字签名
利用第2章介绍的椭圆曲线密码可以方便地实现3.3.3节的ElGamal数字签名，下面给出具体的签名过程。
在SEC1椭圆曲线密码标准（草案）中规定，一个椭圆曲线密码由一个六元组来定义：
T=<p,a,b,G,n,h>
其中，p为大于3的素数，它确定了有限域GF (p)；元素a,b∈GF(p)，它确定了椭圆曲线；G为循环子群E1的生成元，n为素数且为生成元G的阶，G和n确定了循环子群E1，h表示椭圆曲线群的阶与n的商。
1.生成签名
（1）选择一个随机数k，k∈{1,2,…,n -1}。
（2）计算点R(xR,yR)=kG，记r=xR。
（3）利用私钥d计算s=(m– d× r)k-1mod n。
（4）以(r,s)作为m的签名，并将（m,r,s）发给用户B。
2.验证签名
用户B收到（m,r,s）后的验证过程如下：
（1）计算s-1mod n。
（2）利用公开的加密密钥Q计算U(xU,yU)=s-1(mG– rQ)。
（3）如果xU=r,则<r,s>是用户A对m的签名。
3.3.5 散列函数在数字签名中的作用
前面介绍的数字签名方案针对完整的消息实施签名，这种方案存在两方面的缺陷。首先，如果消息内容长，则相应的数字签名也将很长。而实际应用中除了需要保留原始的消息内容，还要保存消息的数字签名以备随时验证，这将导致高昂的存储开销。其次，公开密钥密码系统存在处理速度慢、计算开销高昂的缺点，对长消息进行数字签名以及进行签名验证都需要付出高昂的计算代价，同时耗时冗长，实际应用难以接受。
考虑到以上因素，数字签名通常不是针对完整的消息进行的，而是针对能够标识消息的特征信息施行的。被签名的特征信息需要满足一些条件。首先，特征信息不能太长，否则签名的计算开销仍然较高。其次，当信息内容发生改变时，特征信息必须同时改变，为签名数据的完整性验证提供依据。
在实际的数字签名方案中，数字签名往往针对消息的散列值进行。发送方在发送消息前，首先计算消息的散列值。而后，发送方使用自己的私钥对消息的散列值进行数字签名。消息和数字签名一起被发送到接收方。在接收到消息以后，接收方一方面计算接收到的消息的散列值。另一方面，利用发送方的公钥对发送来的数字签名进行验证。如果计算得到的散列值与从数字签名中提取的散列值相同，那么可以判断消息由所声称的发送者发出，同时消息在传输的过程中没有被篡改。采用这种数字签名方案，数字签名和签名验证都是针对消息的散列值进行，这样计算开销和存储开销都降低了。
例如，Internet保密电子邮件系统PGP（参见第10章）首先利用MD5散列函数对邮件正文进行散列处理，然后使用RSA对邮件正文的散列值进行数字签名，以确保真实性。