3.4 数字签名
在通信网络安全中的密钥分配、认证以及电子商务系统中，信息除了需要保证机密性以外，还需要满足完整性、可认证性、不可否认性以及匿名性等基本安全要求。数字签名作为这些基本安全要求的实现手段之一，在现代密码学中具有重要的意义。本节将首先阐述数字签名的基本概念，然后介绍ElGamal、RSA和DSS等常用的数字签名算法。
3.4.1 基本概念
数字签名（又称公钥数字签名）类似于写在纸上的普通物理签名，但使用了公钥加密领域的技术进行实现。签名信息是采用一套规则和一系列参数通过某种运算得到的，通过它可以鉴别认证签名者的身份并验证电子文档或数据的完整性。一套数字签名机制通常需要定义两种互补的运算，一种用于签名，另一种用于验证。
随着计算机和通信网络的发展，人们希望通过电子设备实现快速、远距离的交易，由于在传输过程中存在不安全因素，数字签名方法便应运而生，并开始广泛应用于商业通信系统，如电子邮件、电子商务和电子政务等。
数字签名与手写签名有相似之处，它们都需要满足下列条件：接收方能够确认或证实发送方的签名，但不能伪造；发送方发出带有签名的内容给接收方后，就不能再否认它所签发的内容；接收方对已收到的签名内容不能否认，即需要有收报认证；必要时，第三方可以确认收发双方之间的签名内容，但不能伪造这些内容。
同时，数字签名与手写签名也有许多不同之处。首先，在数字签名中，签名同消息是分开的，需要一种方法将签名与消息绑定在一起，而在手写签名中，签名被认为是被签名消息的一部分；其次，在签名验证的方法上，数字签名利用一种公开的方法对签名进行验证，任何人都可以对签名进行验证，而手写签名是由经验丰富的接收者通过与以往的签名进行比对来验证；而且，数字签名和所签名的消息能够在通信网络中传输，而手写签名只能使用传统的安全方式进行传输；最后，对于手写签名的复制比较困难，而对数字签名的复制则非常容易。因此，在数字签名方案的设计中要预防签名的重用。
为了满足在网络环境中身份认证、数据完整性和不可否认性等安全需求，数字签名必须具有以下几个重要特性。
1）可信性。即签名的接收方可以方便并有效地通过一个专门的验证算法来验证真伪。
2）不可伪造性。即除了合法的签名者之外，任何人都无法伪造出这一签名。
3）不可复制性。即对于某一条消息的签名，任何一方都不能将此签名用作对另一条消息的签名。
4）不可抵赖性。即签名一旦生成并被发送出去，签名的生成者不能否认自己的签名，因为接收方可以向别人出示签名来证明消息的来源。
5）不可修改性。即签名一旦完成，则对被签名消息的任何修改都能够被轻易发现。
通常，根据接收方验证签名的方式不同，可以将数字签名分成两大类——真数字签名和仲裁数字签名。真数字签名就是签名的接收方在收到签名之后能够独立地验证签名的真伪而不必借助于其他任何人；仲裁数字签名则是指接收方不能独立完成签名的验证，而是需要与一个可信的第三方（即仲裁者）合作来完成验证。
根据数字签名实现方法的不同，又可以将数字签名分为采用对称加密算法的数字签名和采用公钥加密算法的数字签名。采用对称加密算法的数字签名技术需要签名的生成方和验证方都持有相同的（或者是可以互相推导的）签名密钥来完成签名生成和验证的过程。这种方式容易导致所持有的密钥外泄，并存在伪造的可能，因此其安全性并不高。而采用公钥加密算法的数字签名由于任何人都无法从公钥推导出私钥，因此密钥外泄的可能性要低很多。当然，这类数字签名技术的运行速度要比采用对称加密算法的数字签名慢得多。
图3-8展示了一个采用公钥加密算法的数字签名算法的原理示意图。
图3-8 数字签名原理示意图
由图3-8可知，采用公钥加密算法的数字签名的具体运行过程如下。
1）发送端首先对所要发送的消息数据采用Hash函数进行运算并获得其消息摘要，然后使用私钥对这段摘要进行加密，将加密结果作为数字签名附在所要发送的消息数据之后一同发出。
2）接收端通过一个可信的第三方——证书机构（Certification Authority，CA）获得发送端的公钥，对接收到的数字签名进行解密，得到摘要1。
3）接收端采用相同的Hash函数计算并获得消息数据的摘要2，然后将摘要1与摘要2进行比较，以判断数字签名是否有效。
3.4.2 常用数字签名技术
目前，数字签名主要采用的是公钥密码算法，其中比较典型的有两个：RSA签名算法和ElGamal签名算法。RSA签名算法提出的时间比较早，其建立的基础同RSA加密算法一样，两者都是基于大数分解难题。1985年，ElGamal签名算法方案被提出，该方案的改进版已经被NIST采纳为数字签名算法（Digital Signature Algorithm，DSA），用于数字签名标准（Digital Signature Standard，DSS）中。DSA的安全性建立在离散对数求解困难的基础上，并使用了安全Hash算法SHA，其安全性与RSA算法基本相当。
本节将介绍RSA数字签名方案、ElGamal数字签名方案和DSS数字签名标准。
1. RSA数字签名方案
数字签名方案通常由签名算法和验证算法两部分组成。其中，签名算法可以是保密的，也可以是公开的，而验证算法则必须是公开的，并且验证者可以通过这个公开的验证算法来直接判断出签名的真伪。
RSA数字签名方案在其运行过程中采用了前面介绍过的RSA公钥加密算法，但在签名方案中其使用方式有所不同。在作为加密算法使用时，发送方使用接收方的公钥对信息进行加密，接收方利用自己的私钥来解密信息；而在签名方案中，发送方使用自己的私钥对信息进行加密，接收方使用发送方的公钥来解密信息进行验证。其具体过程如下。
（1）算法描述
1）初始化。任意选取两个大素数p和q，计算乘积n=pq以及欧拉函数值ϕ（n）=（p-1）（q-1）；再随机选取一个整数e，满足1＜e＜ϕ（n），而且e与ϕ（n）互素；然后计算整数d，使得ed≡1modϕ（n）。最后，公开n，e的值作为公钥，而p、q和d保密。
2）签名过程。设需要签名的消息为x（x∈Zn），选择一个安全的Hash函数，发送方的私钥为d，计算
SigK≡h（x）dmodn
则SigK即为对消息x的签名。
3）验证过程。设接收方收到的签名消息为y，利用发送方的公钥e对签名进行验证
VerK（x，y）=TRUE⇔h（x）modn≡yemodn，其中x，y∈Zn
若VerK（x，y）=TRUE，则签名有效；否则签名无效。
（2）正确性证明
由ed≡1modϕ（n）可得
ed=kϕ（n）+1，k∈Zn
于是，根据签名和验证算法可以得到
yemodn=（SigK）emodn=h（x）edmodn=h（x）kφ（n）+1modn=h（x）modn
由此，即可证明签名方案的正确性。
2. ElGamal数字签名方案
ElGamal加密方案能够使用用户的公钥进行加密，并利用用户的私钥进行解密。而El-Gamal数字签名方案，则是使用私钥进行加密，而用公钥进行解密。
先来看一下ElGamal方案中使用的数论原理。对于素数q和
，则有
a，a2，…，aq-1
取模（modq）后各不相同。如果a是q的本原元，则进一步有
1）对于任意整数m，am≡1（modq）当且仅当m≡0（modq-1）。
2）对于任意整数i、j，ai≡aj（modq）当且仅当i≡j（modq-1）。
同ElGamal加密方案一样，ElGamal数字签名方案的基本元素是素数q和a，其中a是q的原元。用户A通过如下步骤产生公钥和私钥。
1）生成随机整数XA，使得1＜XA＜q-1。
2）计算YA=aXAmodq。
3）则A的私钥是XA；A的公钥是{q，a，YA}。
为了对消息M进行签名，用户A首先计算M的Hash值m=H（M），这里m是满足0≤m≤q-1的整数。然后A通过如下步骤产生数字签名。
1）选择随机整数K，满足1≤K≤q-1以及gcd（K，q-1）=1，即K与q-1互素。
2）计算S1=aKmodq。
3）计算K-1 mod（q-1），即计算K模q-1的逆。
4）计算S2=K-1（m-XAS1）mod（q-1）。
5）签名包括（S1 ，S2 ）对。
任意用户B都能通过如下步骤验证签名。
1）计算V1=ammodq。
2）计算V2=（YA）S1（S1）S2 modq。
如果V1=V2 ，则说明签名合法。
3. DSS数字签名标准
DSS是一种数字签名方案，它是在由ElGamal基于离散对数问题提出的一个既可用于加密又可用于数字签名的密码算法的基础上改进而来的，已经被NIST采纳。该方案本身是一个非确定性的算法，这也意味着对于任何给定的消息将有许多合法的签名。DSS数字签名的具体过程如下。
（1）算法描述
1）初始化。选取两个大素数p和q，满足p-1能够被q整除；选取一个整数h，计算g=h（p-1）/q modp，满足h∈Zp∗，且h（p-1）/q modp＞1；再随机选取一个正整数x（0＜x＜q）作为私钥，并计算y=gxmodp，将（p，q，g，y）作为公钥；选择单向Hash函数H（x），DSS标准中规定为SHA-1算法。
2）签名过程。假设待签名的消息为M（M∈Z∗p），签名者选择随机数k（0＜k＜q），计算
r=（gkmodp）modq
s=k-1 [H（M）+xr] modq
则（r，s）即为对消息M的签名。
3）验证过程。接收方收到消息M和签名值（r，s）后，进行以下步骤
w=s-1 modq
u=[H（M）w] modq
t=（rw）modq
v=[（guyt）modp] modq
当v=r时，说明签名有效。
（2）正确性证明
根据签名和验证算法可以得到
v =[（guyt）modp] modq=[（gH（ M） wyrw）modp] modq=[（gH（ M） wgxrw）modp] modq
=[（g[H（M）+xr]w）modp] modq=（gskwmodp）modq=（gkmodp）modq=r
由此，可以证明签名方案的正确性。