5.4 数字签名

消息鉴别能保护通信双方免受任何第三方的攻击。然而，它无法防止通信双方的互相攻击。如本章开头讨论到的，A与B关于股市投资失败的争执，还有一种可能就是A伪造不同的消息，声称它来自于B，他只需要简单地生成一个报文，并附上由A和B共享的密钥生成的鉴别码就可以了。在这种情况下，发送方与接收方之间存在欺骗或抵赖，因此除了消息鉴别之外还需要别的东西，最常见的解决方案就是采用数字签名。

5.4.1 数字签名的功能与特性

5.4.1.1 手写签名和数字签名

政治、军事、外交等活动中签署文件，商业活动中签订契约或合同，以及日常生活中人们对书信或刷卡购物的凭单签字，传统上都是采用手写签名或印鉴。签名起到认证、核准和生效的作用。手写签名具有如下特性：签名是可信的，接收者相信签名者慎重签署了该文件，确保文件内容的真实可信；签名是不能伪造的，每个人的书写习惯有不同的特征，通过笔迹可以判断是否是其本人的签名；签名是不可重用的，签名只对所签署的文件有效；签名后的文件是不能更改的，为了保证修改是有效的，财务上规定对凭单任何地方的修改都必须签名，考卷批阅规定对考卷任何批阅的修改处也必须签名；签名是不可否认的，签名者无法否认自己的签名，因为他人模仿签名者的笔迹伪造的签名与原签名还是有差别的，可以被识别。

通信和网络技术的产生和发展，为人们提供了通过互联网进行通信、购物、汇款、办公的方便，随之而来的是电子信息世界的行为确认问题，与手写签名对应，数字签名应运而生。作为与手写签名有着同样目的的数字签名（Digital signatures）提供了如下功能：

● 签名者事后不能否认自己的签名。

● 接收者能验证签名，而任何其他人都不能伪造签名。

● 在有争议时，可由第三方进行验证。

● 对签名的作者、日期和时间、签名时刻消息的内容提供了验证。

从上面的解释和说明中，我们看出数字签名也能对消息的完整性提供保证和证明，此外它还提供了消息鉴别之外的附加功能——不可否认性。

手写签名和数字签名的主要差别有：

（1）签署文件方面：手写签名与被签的文件在物理上不可分割，数字签名与所签文件的“绑定”是通过数学变换来实现的。

（2）验证方面：手写签名通过与一个真实的手写签名相比较来验证，相对而言，这种方法不是绝对准确的。数字签名通过公开的验证算法来验证，任何人都可以验证签名的正确性，通过安全的算法和协议保证签名是不可伪造的。

（3）“复制”方面：手写签名不易复制，任何复制品都与原件有差别，而在电子信息世界里，得到数字签名的复制是非常容易的。

5.4.1.2 数字签名的定义

与加密和消息鉴别类似，可以给出数字签名的一个正式定义：一个签名方案是一个满足下列条件的五元组（P，A，K，S，V）：

（1）P是所有可能消息组成的一个有限集合。

（2）A是由所有可能的签名组成的一个有限集合。

（3）K为密钥空间，它是由所有可能密钥组成的一个有限集合。

（4）对每一个k∈K，有一个签名算法Sigk ∈ S和一个相应的验证算法Verk ∈ V。对每一个消息x∈P和每一个签名y∈A，每一个Sigk：P→A和Verk：P×A→{true，false}都是满足下列条件的函数：

由x ∈ P和y ∈ A组成的数据对（x，y）称为签名消息。

5.4.1.3 数字签名的设计要求

为了设计一个安全的签名，需要考虑对签名方案的可能攻击。把可能的攻击分为下面几种：

● 唯密钥攻击（Key-only attack）：攻击者Oscar拥有Alice的公钥，即验证函数Verk。

● 已知消息攻击（know message attack）：Oscar拥有一系列以前由Alice签名的消息（x1，y1），（x2，y2），其中xi是消息，yi是Alice对消息的签名。

● 选择消息攻击（Choose message attack）：Oscar请求Alice对一个消息列表签名。

攻击者对签名方案可能有如下的攻击目的：

● 完全破译（Total break）：攻击者Oscar可以确定Alice的私钥，即签名函数sigk，因此能对任何消息产生有效签名。

● 选择性伪造（Selective forgery）：攻击者能以某一不可忽略的概率对另外某个人选择的消息产生一个有效的签名，该消息不是以前Alice曾经签名的消息。

● 存在性伪造（Existential forgery）：攻击者至少能够为一则消息产生一个有效的签名，该消息不应该是以前Alice曾经签名的消息。

我们以RSA签名方案为例说明可能的攻击类型。

Oscar能通过对某一 y 计算 x = EKUa（y）伪造一个Alice对随机消息 x 的签名，因为 y =SigKRa（x）。这是一种唯密钥攻击的存在性伪造。

如果Osacr拥有Alice对消息x1，x2的签名分别是y1和y2，则Oscar可伪造Alice关于消息x1x2 mod n的签名y1y2mod n，因为SigKRa（x1x2）= SigKRa（x1）SigKRa（x2）mod n。这是一种已知消息攻击的存在性伪造。

假定Oscar要伪造消息x的签名，Oscar找到x1，x2∈Zn，使x ≡ x1x2 mod n。他请求A对x1，x2签名，签名结果分别是y1和y2。y1 y2 mod n是消息x1 x2 mod n的签名。这是一种选择消息攻击的选择性伪造。

考虑到以上的攻击，我们给出对数字签名的设计要求：

● 签名必须是依赖于被签名信息的一个位串模式，类似于笔迹签名与被签文件的不可分离性。

● 签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认，类似于笔迹签名的独特性。

● 必须相对容易生成该数字签名。

● 必须相对容易识别和验证该数字签名。

● 伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名，类似笔迹签名不可模仿性。

● 在存储器中保存一个数字签名副本是现实可行的，显然签名不能太长。

5.4.2 数字签名方案

根据接收者验证签名的方式可以将数字签名分为直接数字签名（Direct digital signature）和仲裁数字签名（Arbitrated digital signature）。从计算能力上，可将数字签名分为无条件安全的数字签名和计算上安全的数字签名。现有的数字签名大部分是计算上安全的，所谓计算上安全是指任何伪造者伪造签名是计算上不可行的。Chaum和Roijakkers提出了第一个无条件安全的数字签名，理论上它能代替计算上安全的数字签名，但在实际应用中不太有效，因为这种签名需要一个复杂的交互密钥生成协议，而且签名很长。根据签名者在一个签名方案中能签的消息的数量，可将数字签名分为一次性的数字签名和多次性的数字签名。一次性数字签名方案只能签一个消息，如果签两个或以上的不同消息，伪造者就能伪造签名，类似于一次一密的方案。此外，还有一些具有特殊性质的数字签名。本节介绍一些有代表性的数字签名方案。

5.4.2.1 RSA数字签名方案

RSA算法中，公开密钥为{e，n}，其中n是两素数p和q的乘积，私有密钥为{d，p，q}，一种直接的数字签名方案为：

对消息M签名，计算y = Sig（M）= M d（mod n）

验证签名，计算M′= y e（mod n），判断其是否与原来的M相同。

这种签名方案有如下缺点：速度慢；信息量大，签名和明文一样长；第三方仲裁时必须暴露明文信息；且存在以下漏洞：EKRa（x×y）≡ EKRa（x）× EKRa（y）mod n。这一漏洞可以通过对原始消息的消息摘要的签名替换直接对消息的签名来避免，先做摘要hm=H（M），再对hm签名SA=EKRa（hm），散列函数的无碰撞性保证了签名的有效性，如图5.6所示。

本质上签名提供真实性（Authentication），加密提供机密性（Confidentiality）。如果想要同时提供机密性和真实性，就需要同时实现签名和加密。当用户A向用户B发送消息时，有两种实现的方式：一种是先签名，后加密，EKUb{M || SigKRa（M）}；另一种是先加密，后签名，{EKUb（M）||SigKRa（EKUb（M））}。后一种方法存在如下争议：

● 发生争议时，B需要向仲裁者提供自己的私钥。

● 安全漏洞：攻击者E截获消息，把SigKRa（EKUb（M））换成SigKRe（EKUb（M）），让B以为该消息来自E。

● 保存信息多：除了M， SigKRa（EKUb（M）），还要保存EKUb（M），因为KUb可能过期。

5.4.2.2 数字签名标准DSS/DSA

ElGamal于1985年提出了一个基于离散对数问题的数字签名体制，通常称为ElGamal数字签名体制，它很大程度上为Diffie-Hellman密钥交换算法的推广和变形。该方案是特别为签名的目的而设计的。DSS（Digital Signature Standard）是由NIST于1991年提出的，1994年12月1日被美国NIST采纳作为数字签名标准（FIPS 186）。DSS使用SHA作为散列函数，并提出了一种新的数字签名技术，即数字签名算法DSA（Digital Signature Algorithm）。

在数字签名算法DSA中，发送方先利用安全散列算法产生报文的消息摘要，然后将消息摘要和一个专用于该签名的随机数k作为签名函数的输入，该签名函数还依赖于发送方的私有密钥（KRa）和一个全局公开密钥（KUG），事实上是一组相关联的参数。生成的签名由两个分量组成，记为s和r。接收方将计算所收到报文的散列码，该散列码和签名作为验证函数的输入。验证函数同时还依赖于全局公开密钥以及与发送方私钥配对的发送方公钥。如果签名是有效的，验证函数的输出等于签名分量r。如图5.7所示。

DSA算法的计算步骤如下：

（1）全局公开密钥的选择：首先选择一个160 bit的素数q，接着，选择一个素数p，要求p的长度L在512到1024 bit之间，且L为64的倍数，（p -1）能被q整除。最后，选择g等于modp，其中h是大于1小于（p -1）的整数，要求g大于1。

（2）选择用户私钥公钥对：有了上面的全局公开密钥，用户就能选择一个私有密钥并产生一个公开密钥。私有密钥x必须是1到（q -1）之间的随机数或者伪随机数，公开密钥。给定x计算y是简单的，然而给定公开密钥y，要确定x需要计算以g为底的模p的离散对数，这在计算上是不可行的。y g x mod p=

（3）生成签名：用户为每个报文M选择随机数k，其中0 < k < q，计算两个分量r与s，r =（gk mod p）mod q，s = [k-1（H（M）+ xr）] mod q，签名为（r，s），发送签名（r，s）和消息M。

（4）验证签名：接收方先根据收到的s′计算w，w =(s′)-1 mod q，然后根据w和收到的r′，报文的散列值，y，q，g等值计算验证签名值v

u1 = [H(M′)w] mod q，u2 =(r′)w mod q

v = [（gu1 yu2）mod p] mod q

将v与接收到的r比较，若相等则接受签名。

DSS具有如下特点：DSS的签名比验证快得多，NIST认为这对安全没有影响；DSS不能用于加密或者密钥分配，只能用于数字签名；若p为512位，q为160位，而DSS只需要两个160位，即320位。

DSS使用中要注意避免以下问题：

（1）当用户产生的签名s = 0，会泄露私钥

s = 0 = k-1[H（M）+ xr）mod q

x = -H（M）r -1mod q

（2）用户产生的s-1 mod q要存在，要求s≠0 mod q，如果得到的s ≡ 0 mod q，接收者可拒绝该签名，要求重新构造该签名。实际上，s ≡ 0 mod q的概率非常小，为2-160。

（3）不能将签名所使用的随机数k泄露出去。如果签名中所使用的随机数k泄露了，那么任何知道的人可由方程s = [k-1（H（M）+ xr）] mod q求出：

x = [sk-H（M）]r-1mod q

一旦x被知道，攻击者就可以任意伪造签名。

（4）不要使用同一个k签两个不同的消息，如果使用同一个k签两个不同的消息，会使攻击者计算私钥变得容易。

5.4.2.3 直接数字签名和仲裁数字签名

直接数字签名是接收者直接验证签名的方式，这种验证模式依赖于发送方私有密钥的保密。当发送方要抵赖发送过某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名。通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在。一种改进的方式是要求被签名的信息包含一个时间戳（日期与时间），并将已暴露的密钥报告给一个授权中心。但是用户U的某些私有密钥确实在时间T被窃取，敌方可以伪造U的签名及早于或等于时间T的时间戳。为了避免以上问题，在数字签名体制中引入仲裁者。通常的做法是所有从发送方U到接收方V的签名消息首先送到仲裁者A，A对消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给V。仲裁者在这一类签名模式中扮演敏感和关键的角色。所有的参与者必须极大地相信这一仲裁机制工作正常。

5.4.2.4 不可否认的数字签名方案

不可否认的数字签名（Undeniable digital signature）方案是由Chaum和van Antwerpen在1989年提出的，其中最主要的特征是没有签名者的合作，签名就不能得到验证。从而防止了由她签署的电子文档资料没有经过她的同意而被复制和分发的可能性。不可否认签名的真伪性是通过接收者和签名者执行一个协议来推断的，这个协议称为否认协议。为了防止用户A否认一个之前的签名，一个不可否认签名与一个否认协议结合。用户U对签名进行验证，通过这种方式用户U能证明一个签名是伪造签名。不可否认的数字签名方案由三部分组成：签名算法、验证协议和否认协议。

5.4.2.5 一次性数字签名方案

如果一个签名方案仅给一则消息签名时是安全的，则签名方案是一次性签名方案，当然可以进行若干次验证。Lamport数字签名方案就是一个一次性数字签名，它可以基于任何单向函数来构造，它的缺点是签名信息比较长。如果单向函数基于离散对数问题来构造，当 p 是1024位，则签名信息扩大1024倍。如果基于对称密码体制来构造，当密钥是128位，则签名信息扩大128倍。由于Lamport方案的签名太长，不太实用，改进方案之一是Bos-Chaum签名方案，使得签名的长度大约降低50%。

5.4.2.6 群签名方案

群签名（Group digital signature）方案允许群中各个成员以群的名义匿名地签发消息，它具备下列三个特性：只有群内成员能代表那个群为消息签名；接收者能验证签名是来自于该群的合法签名；接收者不能确认签名者是群内的哪一个人，需要时，可借助于群成员或者可信机构找到签名者。群数字签名方案由三个算法组成：签名算法、验证算法和识别算法。群签名方案的应用例子有投标、公司打印机管理等。对于公司的打印机管理，群是公司所有员工的集合，通常情况下，每个员工都可以匿名地用群签名使用打印机，当出现打印机被滥用的行为时，无须签名者的合作，可以查出滥用的员工。Chaum和van Heijst在1991年提出了一种群签名方案。

5.4.2.7 盲签名方案

所谓盲签名（Blind digital signature）是指签名人员只是完成对文件的签名，并不了解所签文件的内容。它要求：消息内容对签名者不可见；签名被接收者泄露后，签名者无法追踪签名。它应用在某些需要参加者匿名性的密码协议中，如电子货币、电子选举。如果不考虑顾客的隐私权，银行能追踪顾客的每一笔开支，顾客不能隐瞒把钱交给了谁，购买了什么东西，这种电子货币称为可追踪电子货币，利用现有的密码技术是很容易实现的。我们在实际生活中用现金购物，商家并不知道是谁购买了这个商品。如果电子货币也具有同样的特性，银行不知道顾客把钱付给了谁，购买了什么东西的话，这种电子货币称为不可追踪的电子货币。盲签名过程是先对消息进行盲变换，再对变换后的消息（称为盲消息）签名，接收者收到签名后进行逆盲变换。绝对的盲签名并不实用，加入“切选”（Cut and choose）技术的签名方案，是有实际需求的。一个基于RSA的盲签名方案如下：

B的公钥KUb，私钥是KRb，f是单向函数，如散列函数，A需要B为他盲签消息x。

（1）对消息x进行盲变换：A随机选择k，计算x′= f（x）EKUb（k）mod n，把x′给B。

（2）B对盲消息 ′x 签名：B对x′进行签名得到y′= SigB（x′）= EKRb（x′），把y′给A。

（3）A对签名逆盲变换：A计算y =y′/k mod n = EKRb（f（x）EKUb（k））/k mod n = EKRb（f（x））mod n。上面的方案中，随机数k使得签名者无法知道签名的内容，f的单向性增加了安全性。