3.3　数字签名

现实生活中，我们常用签名来验证某个文件或许可的授权者。签名的动作是授权，验证笔迹的过程是确认签名的真实性。在多种信息系统中，我们也会用到相似的数字签名方案。

签名方案一般包括签名和认证两个算法。下面依然以Alice和Bob的交互为例来说明。假设Bob要发给Alice一条信息m，而且两人希望建立一套机制，帮助Alice在收到信息时能验证这条信息是否真的来自于Bob，而不是Carl伪造出来的。算法的基本过程如下。

• Step 1：Bob生成私钥kr和公钥kp等参数，并将公钥kp公开。
• Step 2：Bob利用私钥kr为信息m生成签名s，生成签名后的数据为{m,s}，并将该数据发送给Alice。
• Step 3：Alice利用公钥kp对{m,s}进行验证。如果验证通过，则确认该条信息来自Bob，反之则否认。

可以看到，数字签名方案背后的基本原理和非对称密码算法是相似的，但似乎公钥和私钥的使用过程反过来了。下面简要介绍哈希函数和几种常见的数字签名算法。

3.3.1　哈希函数

实际中，信息m可能很长，直接对m进行签名是低效的。一般的方法是先为信息m生成“摘要”，然后对摘要进行签名，这并不影响签名的安全性。哈希函数就是生成数字摘要的有效手段。

哈希函数的计算过程可用y=h(x)表示。x是原始信息，y是x的短摘要。哈希函数有几个重要特点。第一，它是单向的，即只能由x求解y，而不能轻易用y反推x。第二，它要抗碰撞，即在计算上很难找到两个不同的原始消息x1和x2，使它们的摘要相等，即h(x1)=h(x2)。

最常见的哈希函数有MD5和SHA-1算法。它们的哈希摘要长度不同，SHA-1算法的哈希摘要长度为160，而MD5算法的摘要长度为128。

1979年，Merkle提出了一种统一的哈希函数构造。该构造中，消息m被划分为若干等份，然后迭代式地运用一个压缩函数f对每一块进行处理，最终得出摘要。这个过程如图3-3所示。

MD5函数和SHA-1函数都采用上述通用架构。

MD5将原文消息划分为长度为512比特的等份。由于原文消息的长度是任意的，在MD5算法的开始阶段首先要对消息进行填充，使得它恰好为512的整数倍。对每一个512长度的分块，按照通用架构的过程，利用函数fMD5进行迭代式的处理。fMD5函数的内部结构也是迭代的，它包含64步操作，主要由逻辑与、或、异或和否等运算组成，中间结果保存在4个32位的寄存器中，非常便于计算机实现。上述两个层次的迭代和多种逻辑运算，使得MD5输出的128位摘要值的每一位都和输入消息m的每一位相关，充分地混淆和扩散了数据。由于具有这样的效果，因此人们也将哈希函数称为“散列”函数。

SHA-1算法对原始信息的分块预处理、整体的运算架构和MD5算法并无重大区别。但在每一轮迭代的压缩函数fSHA-1比MD5算法设计更精妙。SHA-1算法中的每个数据块要经过80轮的运算，每一轮计算的中间结果保存在5个32位的寄存器中。进一步来说，在每一轮运算中，fSHA-1引入了可变的运算子函数和加法常量，冗余度和复杂性都比MD5更高。SHA-1的哈希摘要长度比MD5长32位，因此一般认为SHA-1的抗攻击性稍高，但是其计算复杂度也更高一些。

一般认为，摘要长度越长，哈希函数的安全性越高。在SHA-1之后，美国标准局又引入了SHA-256、SHA-384和SHA-512，进一步扩展了摘要长度。

3.3.2　RSA签名

我们已经学习过RSA非对称加密算法。RSA签名方案就是基于该算法构建的，其过程如下。

• Bob计算密钥参数：{p,q,h}为私钥，{n,t}为公钥。将公钥发送给Alice。
• 假设原始信息m的摘要为x，Bob利用签名函数对x进行签名，生成y。计算函数如下：

y=xh mod n

然后，Bob将信息和签名数据发给Alice。

• Alice利用公钥参数对签名进行验证。计算函数如下：

xv=yt mod n

如果xv=x mod n，则验证通过；否则验证失败。

基于RSA算法的数学原理，我们知道只有通过私钥签名的函数才能够被公钥参数验证。在RSA签名方案中，由于只有Bob拥有私钥参数，当Alice验证签名成功后，就可以直接确定该签名来自Bob本人了。另一个附加的功能是，Alice也可以验证原始信息m和x的匹配性，如果m和x匹配，则证明消息传输过程中没有遗漏。RSA签名算法一般选择参数n的长度为1024或2048比特，签名的长度和n相同。

3.3.3　ElGamal签名

ElGamal数字签名方案的过程和RSA签名方案相似，但采用的参数和签名函数不同。回顾ElGamal加密算法，密钥参数中{α,β,p}为公钥，d为私钥。Bob签名的计算过程如下。选择一个临时的随机密钥w，满足w<=p-2，且w和p-1的最大公约数为1。计算：

r=αw mod p

以及

s=(x-dr) w-1 mod p-1。

上述计算中的{r,s}即为签名的结果。

Alice利用公钥参数对签名进行验证，其过程如下。计算：

t = βr×rs mod p

如果t=αx mod p则验证通过；否则验证失败。

ElGamal签名方案的证明过程不像RSA方案那么直接，需要利用数论中的费马小定理，在这里不做叙述。一般情况下，选择ElGamal数字签名算法参数p的长度为1024或更大。由于输出为{r,s}，因此该算法的签名长度是原文摘要长度的三倍。

3.3.4　DSA

DSA的中文全称是“数字签名算法”，是美国政府1994年颁布的签名标准，它的应用范围远比RSA和ElGamal签名方案广泛。和其他签名算法一样，它包括密钥参数生成、签名和验证等几部分。下面对该算法进行简述。

DSA的密钥参数生成分为以下几个步骤：

• Step 1：找到一个长度为1024比特的素数p。
• Step 2：找到长度位160比特的q，使得q为素数且被p-1整除。
• Step 3：找到集合的本原元α。
• Step 4：随机选择整数d，使得0<d<q。计算β=αd mod p。

上述过程中，{p,q,α,β}为公钥，d为私钥。

Bob签名的计算过程如下：

• Step 1：随机选择整数0<t<q。
• Step 2：计算：r=(αt mod p) mod q以及s=[SHA(x)+dr]×t-1) mod q。

这里SHA(x)表示进行SHA-1计算，输出的是160比特的摘要信息；上述过程中，{r,s}即为签名信息。

Alice验证的计算过程如下：

• Step 1：计算w = s-1 mod q。
• Step 2：计算u1=w×SHA(x) mod q，以及u2=w×r mod q。
• Step 3：计算v=(αu1 ×βu2 mod p) mod q。
• Step 4：进行验证，如果v=r mod q，则通过，否则不通过。

上述计算过程看似复杂，实际上和ElGamal加密算法的数学过程相似，其核心是Bob所选择的随机整数t，以及Alice所计算的辅助变量u1和u2满足如下关系：

t = u1 + du2 mod q。

所以验证函数就是验证v和r是否模相等。当ElGamal签名方案选取参数p的长度为1024时，其签名长度也为1024。通过一些对算法的改变，DSA算法的签名长度减少为320比特。出于算法安全性的考虑，除p为1024比特长度外，还可以选择p长度为2048或3072，分别给出长度为448或512比特的签名。

3.3.5　椭圆曲线DSA

由于椭圆曲线在密钥长度和安全性方面具有优势，美国政府在1998年将椭圆曲线DSA写入标准。椭圆曲线DSA算法的过程和前述DSA算法基本相同，其签名也由一对整数(r,s)构成，其差别在于计算过程是基于椭圆曲线进行的。为方便起见，下面仅对差别部分进行描述。

在算法中，B和A都是椭圆曲线上的点，且B=mA。我们已经知道，椭圆曲线上的数学难题是已知B和A，很难找到m。因此，m是私钥，椭圆曲线采用的其他参数都是公钥。

在签名的过程中，Bob选择一个随机数k，使得1≤k≤q-1，然后找到曲线上点kA的坐标(u,v)。Bob很容易通过坐标(u,v)确定签名{r,s}，即：

r=u mod q

以及

s=k-1 [SHA(x)+mr] mod q

验证的过程中，Alice计算：

w= s-1 mod q

i=w×SHA(x) mod q

j=w×r mod q

如果Alice计算点F=iA+jB的横坐标u满足u mod q = r，则通过验证；否则不通过。

3.3.6　数字签名方案的安全性分析

在本章各方案中，RSA目前运用最为广泛。ElGamal方案是DSA的基础。椭圆曲线和DSA的区别是把运算转移到椭圆曲线上。

如果Carl能够破解RSA、ElGamal等非对称加密的密钥，当然也可以破解相应的数字签名方案。我们知道，为了保障RSA算法的安全，也就是确保大整数分解是计算困难的，至少要保证密钥长度为1024比特或更大。ElGamal的离散对数难题也要求p的长度至少为1024比特。根据理论分析，当p为1024比特时，Carl至少要执行280次运算才可能破解离散对数难题。我们将这称为“80位”的安全性。椭圆曲线的安全性明显更优。密钥长度为192或256比特的椭圆曲线加密方案，就可以获得等同于1024或3072比特的DSA算法安全性能。

数字签名虽然可以验证信息是否来自Bob，但是无法保护明文消息。Carl知道公钥参数，也可以验证签名并获得全部明文消息。因此在实际中，Bob在对消息的摘要进行签名后，需要再用Alice的公钥对消息进行加密得到密文；Alice接收信息后先用自己的私钥解密得到原文，然后利用Bob的公钥进行签名认证。整个流程如图3-4所示。

数字签名还面临一个挑战。如果Carl冒充Bob的身份，用自己的公钥顶替Bob的公钥，那么Alice依然可以收到Carl的签名信息，并通过验证，因为Carl采用的也将会是合法的数字签名算法。为了规避这种情况，在实际应用中又有了“证书”的概念，它引入可信的第三方，对Bob的公钥正确性提供流程和算法上的保障。