学习目标与要求
1.掌握数字签名方案设计的密码学基础。
2.掌握基本的密码学签名方案和设计思想。
3.掌握数字签名的安全要求和基本原理。
5.1引言
签名（手写签名或签章）是一种古老的安全技术，它通过在文件中附加特殊风格印
记的方式，实现识别签名人身份并表明签名人对文件内容认可度的功能。签名通常被用
于验证签名者与文件之间的“所属”关系，作为一种书写体验证方法，带有署名的签名
应该是能让人读出签名者真名的，如果它不能让人读出其名，则必须能通过某种比对手
段或鉴别机制使人认可其有效性。
如同手写签名一样，数字签名（电子签名或电子签章）就是一种采用密码学技术的
签名方法，它能够实现更加安全的“所有权”关系验证以及所捆绑内容的完整性验证，
故在电子商务和网络环境中具有重要的地位和大量的应用。我国
2005年
4月
1日起实
施的《中华人民共和国电子签名法》确立了电子签名的法律效力，并对电子签名行为和
有关各方的合法权益进行了规范。
本章将对数字签名的基本概念和基本安全性要求，以及几种常见数字签名的构造予
以介绍，使读者熟悉数字签名的构造特点；此外，本章也将介绍一些目前依然广泛使用
的数字签名所存在的缺陷。当然，安全是一种综合性的选择，这些缺陷并不一定影响签
名方案的实际使用，因此需要读者对这些签名予以客观评价。
5.2数字签名的概念
数字签名是一种以电子形式存储消息签名的方法，其功能是实现消息认证，即对信
息系统中的数据或通信中的消息来源进行认证，也就是认证消息是否来源于某个实体
（发送者），保障消息来源的正确性。
5858
与传统手写签名或签章相比较，数字签名在传输、媒介、验证方法等方面都有显著
的不同，这些不同表现在以下几方面：
1
.传统手写签名或签章能成为所签署文件中物理的一部分；而数字签名没有在物
理上依附于文件中，因此使用数字签名必须以某种形式将签名捆绑在所签文件上。
2
.传统手写签名或签章在被验证时需要与其他签名比较来判断真伪；而数字签名
通过一个公开验证算法就能够让所有人来验证签名真伪。
3
.传统手写签名或签章存在验证概率的问题，安全性并不高；而数字签名使用数
学方法来防伪，并使得伪造变得困难，安全性较高。
此外，随着复制手段的提高，签名，无论手写签名还是数字签名，都应该包含日期、
使用说明等附加信息，以防该签名被非法地重复使用。在本文后续内容中，除特殊说明
外均将数字签名简称为签名。
在密码构造方面，数字签名方案为用户提供了一种给消息签名的方法，并且这个签
名可以在之后被其他所有人验证。这种公开可验证性决定了签名方案需要被构造在公钥
密码体制之上。更具体地讲，每个用户都可以生成一个相互匹配的公钥
-私钥对，且只
有用户本人使用自己的私钥才能生成针对该消息的签名，但是任何人使用签名者的公钥
都可以验证该消息的签名。此外，验证者可以确信在消息进行签名之后消息的内容不会
被改变，并且签名者不能否认自己曾经对某个消息进行过签名，因为只有签名者拥有自
己的私钥，任何其他人伪造签名在数学上都是困难的。
具体而言，数字签名应满足的要求包括：
1
.收方能确认或证实发方的签字，像验证手写签名一样；
2
.签名密钥被签名者所控制，发方发出签名后的消息理论上不能否认之前所签
消息；
3
.任何人不能伪造发送方的签名；
4
.签署后，被签名消息及签名的任何变更都能够被发现。
总的来说，数字签名的功能在于以下两方面。
1
.所有权验证：能够指明消息与宣称者之间的所属关系，有时对于版权管理也可
被理解为对拷贝权的验证。
2
.完整性验证：能够验证消息是否与签名时是一致的，用以保证双方之间交换的
数据不被修改，并可检查出对消息的任何变更。
5.3数字签名定义
本节将给出数字签名的形式化定义，其包括两部分：“功能性定义”和“安全性定
义”。其中，功能性定义将给出协议所需要完成的功能，安全性定义则会给出签名所需
59
要的安全性要求。
设
M是所有可能的消息组成的一个有限集，其可被称为消息空间。消息空间通常
可被表示为无限长度的随机串，即
M.{0,1}.。以类似的方式，定义
A是所有可能
的签名组成的一个有限集，
K
= SK
×
PK是所有可能的公
/私密钥对所组成的一个有
限集。
根据以上符号定义，数字签名被定义如下：
定义
5.1（数字签名）令给定的
M,A和
K分别为消息空间、签名空间和密钥
空间，则一个数字签名方案是满足以下条件的一个三元组
(G,S,V)（首字母缩写）。
1
.密钥生成：
GenKey
:1κ →
SK×PK是一个随机密钥生成算法，它以安全参数
κ为输入，输出为用户公钥
pk ∈
PK和对应私钥
sk ∈
SK，即
GenKey(1κ)=(pk,sk) (5.1)
2
.签名过程：
Sign
: SK×M
→
A是一个签名算法，给定输入私钥
sk ∈
SK和
任意大小的消息
m，输出一个签名
σ，也就是
σ = Sig(sk,m)，或者简写为
Signsk(m)= σ (5.2)
3
.验证过程：
Verify
: PK×M×A
→
{true,false}是一个验证算法，给定签名者
公钥
pk ∈
PK，使得对每一个消息
m ∈M和每一签名
σ ∈A，输出签名真实性判定
——真或者假，即，
Verify(pk,m,σ)= true/false，或者
Verifypk(m,σ)= true/false
(5.3)
对于每一个公
/私密钥对
(pk,sk)，签名过程是秘密的，只有签名人知道；而验证
算法是公开的，任何接收方都可进行验证。此外，签名算法和验证算法都是多项式
时间可计算函数。与之前介绍的消息完整性验证方法相比较，由于公钥密码体制的
使用，签名私钥只为签名者所有或被其控制，因此要求签名是不可由其他人伪造的，
并且签名者不能否认自己签过的消息，综上所述签名和完整性验证方法具有较大的
区别。
为了保证签名方案的安全，首先必须保证交互证明系统中的两个基本安全性质：完
整性和完备性。完整性是指对于一个有效的签名，验证算法必须能够确认该签名的有效
性；完备性则相反：对于无效的签名，它通过验证算法验证的成功概率将是可忽略的。
签名者对签名的不可否认性是通过不可伪造性实现的。
定义
5.2（数字签名安全性）数字签名方案应具有以下两种性质：
1=(m)，验证算法都将以
.完整性：对于任意有效的消息签名对
(m,σ)，σ Signsk
概率
1通过验证并输出
true，即
6060
Pr[Verifypk(m, Signsk(m))= true
:(pk,sk)←6GenKey(1κ)]=1 (5.4)
2
.完备性：对于任意无效的消息签名对
(m .,σ.)，即
σ.=6Signk(m .)，验证算法
都将以可忽略的概率
ε通过验证且输出
true，即
Pr[Verifypk(m . ,σ . )= true
:(pk,sk)←6GenKey(1κ),σ .6Signsk(m . )]<ε (5.5)
=
上述定义中，完备性等价于验证算法对无效签名输出否定判决
false的概率是压
倒性的，也就是对于
σ.6Signsk.)，则
Pr[Verifypk.,σ.) false] > 1 .6ε。签
=(m (m =
.
名完备性暗含着不可伪造性（
unforgeability），也就是说对于任意
m ，发现有效签名
σ. = Signsk(m .)的概率也是可以被忽略的。具体而言，完备性可以分为下面两种情况。
定义
5.3数字签名的完备性定义通常分为以下两种情况：
1
.抗选择性伪造：攻击者
A以可忽略的概率
ε对挑战者选择的消息产生一个有
效的签名。换句话说，如果给攻击者
A一个消息
m，那么，
A伪造签名
σ.，使得
Verifyk(m, σ.)= true，上述过程的概率满足
. . (pk,sk)←6GenKey(1κ)
Pr
. . .
Verifypk(m, σ . )= true
: σ. ←6ASignsk
(·)(pk,m) . . .
< ε (5.6)
m6∈6Query(A)
其中，
A表示攻击者，
ASignsk
(·)(pk,m)表示攻击者可以通过签名预言机
Signsk(·)要
求签名者对他提出的消息进行签名，并在查询之后输出一个消息
m的伪造签名
σ.，
Query(A)表示被攻击者
A查询
Signsk(·)的消息集合，但
m不是
A曾经查询过的
消息。
2
.抗存在性伪造：攻击者
A能以可忽略的概率至少为一个消息产生有效的签名。
换句话说，攻击者能产生一个新的消息签名对
(m .,σ.)，使得
Verifypk(m .,σ.)= true，
上述过程的概率满足
2.
(pk,sk)
←
GenKey(1)
6.
.
.. Signsk
(·)
(pk,1)
7
Pr
Verifypk(m ,σ . )=
true
:(m ,σ .)
←
A<ε (5.7)
4.
.
(m ,σ .)
.∈
Query(A)
其中，ASignsk
(·)(pk,1κ)表示攻击者可以要求签名者对他提出的任何消息进行签名并在查
询之后输出一个伪造的消息签名对
(m .,σ.)，Query(A)表示被攻击者
A查询
Signsk(·)
的消息签名对集合，但
m .不是
A曾经查询过的消息。
一个签名方案不可能是无条件安全的，因为对于一个给定的消息
m而言，敌手
使用公开算法
Verify可以测试所有可能的签名
σ ∈A，直到他发现一个有效的签
名。因此，给定足够的时间，敌手总能伪造任何消息
m的签名。因此，如同公钥加
61
密体制一样，设计数字签名的目标是找到在计算上不可行或可在数学上证明安全的签名
方案。
5.4数字签名的一般构造
在介绍
Hash函数和
MAC构造的前文中，已指出它们构造的前提条件是单向函数
的存在。由于签名方案引入了公钥密码体制，故其构造的条件也随之增强，根据已有的
研究表明，它的前提是单向陷门函数（One-way
Trapdoor
Function，OTF)。
数字签名构造的密码学基础是单向陷门函数
OTF存在。
这里，所谓单向陷门函数是指该函数具有如下性质：
.1计算
f(x)= y是容易的；
2
.计算
f.1(y)在数学上是困难的；
3k (y)可以为有效计算。
.给定陷门
k，则
f.1
下面给出一个可证明安全的一般数字签名构造，它由一个单向函数（或
Hash函数）
h和一个单向陷门函数
f构成。该方案的构造如下：
1
.密钥生成：由一个可信第三方选择一个单向函数
h和一个单向陷门函数
f，陷
门为
k。公布两个函数
h和
f，即
pk =(f,h)，并将陷门
sk =(k)发送给签名者。
2
.签名过程：签名者首先利用单向函数
h计算待签名消息
m的摘要
h(m)，然后
计算摘要的签名为
f.1
σ = Signsk(m)= k (h(m))
最后将消息签名对
(m,σ)发送给验证者。
3后通过计算
h(m)是否相
.验证过程：验证者接收到消息签名对
(m,σ)和
f(σ)
等来验证签名的有效性，即
. .
true
h(m)= f(σ)
Verifypk(m,σ)= (5.8)
.
false
h(m)6= f(σ)
上述一般签名构造中使用的函数
h通常是公开的密码
Hash函数，如
SHA3。同
样地，常见的签名方案也几乎总是和一种非常快的
Hash函数结合使用。
Hash函数
h : {0,1}. →{0,1}k以任意长度的消息作为输入，返回一条特定长度的消息摘要，这
就要求
Hash函数输出被转为函数
f的定义域，并在此基础上实现消息的签名。也就是
说，消息先经过
Hash函数获取摘要，然后摘要被用于生成签名。
定理
5.1上述一般数字签名构造可满足数字签名安全性中的完整性要求。
f.1
证明对于有效的消息签名对
(m,σ)，其中
σ = sk (h(m))总能通过验证者的验
证，因为总有
h(m)= f(σ)成立。
■
6262
定理
5.2如果
f是一个具有抗二次原像攻击的单向陷门函数，
h是一个碰撞稳
固的单向函数，则上述一般数字签名构造满足完备性要求。
证明对于无效的消息签名对
(m,σ)，其若要通过验证者的验证，则可分为存在性
伪造和选择性伪造两种情况：
1不可行：若可对上述方案进行选择性伪造，那么任意给定一
.“选择性伪造
”
个消息
m，敌手可伪造出一个签名
σ.，使得
h(m)= f(σ.)成立。这意味着敌手能
够有效地计算出
σ. = f.1(h(m))。由于在没有密钥
k的情况下，单向陷门函数
f
是求逆困难的，
σ.不可在任何多项式时间内获得，所以敌手的能力与
f的求逆困
难假设矛盾。因此，在单向陷门函数
f求逆困难的假设下，上述方案可抵抗选择性
伪造。
2
.“存在性伪造”不可行：这种情况可分为下面三种情况：
m6m .但
σ = σ.：敌手首先找到两条消息
m .6m使得
h(m =
== .)h(m)，然后他
将消息
m发送给签名者，并让签名者对消息摘要
h(m)签名获得
σ。那么
(m .,σ)是有
效的签名消息，而
σ是消息
m .的伪造签名。这是一种利用选择消息来实现攻击的存
在性伪造；如果
h是抗碰撞的，这种攻击就能避免。
m = m .但
σ6= σ.：敌手给定消息签名对
(m,σ)，他将消息
m发送给签名者，并
让签名者对消息摘要
h(m)签名获得
σ.，如果
σ6= σ.，那么
(m .,σ.)是有效伪造，且
f(σ.)= f(σ)。这是典型的二次原像攻击，因此，如果
f可抗二次原像攻击，这种攻击
就能避免。
m6m .且
σ6σ.：如果存在
h(m .)= f(σ.)成立，意味着该消息签名对与之前
==
观察到的消息签名对都没有紧密的关系，因此，考虑两种可能性，即
m . = h.1(f(σ.))
和
σ. = f.1(h(m .))。前者存在与
h的不可逆矛盾，后者存在与
f的不可逆矛盾。因
此，如果
f和
h都是不可逆的（反向计算困难），这种攻击就能避免。
由此可知，保证签名方案的前提是
f是一个具有抗二次原像攻击的单向陷门函数，
而
h是一个碰撞稳固的单向函数。问题得证。
■
数字签名的一般构造并不是唯一的，可根据不同的需要选择不同的设计。例如，下
面是一个更严格的备选方案。
1= sk (h(m))；
.签名函数：σh(m)⊕6f.1
.2验证函数：f(h(m)⊕6σ)= h(m)。
感兴趣的读者可验证此方案的正确性和安全性。需要说明的是，在具体数字签名方
案设计中，由于密码学陷门构造不同和应用需求不同，签名方案的实际构造将与上面一
般性构造差异很大，这也使得数字签名的研究丰富多彩。
63
5.5
RSA数字签名
5.5.1
RSA数字签名方案
RSA是目前使用最广的公钥密码系统，其特点是简单、易于非密码专业人员理解和
实现，故在互联网和商业密码领域一直处于统治地位。从当前密码理论研究看，
RSA密
码本身有很多问题，如无法实现选择明文攻击下的语义安全（
Semantic
Security
under
Chosen
Plaintext
Attack）等，但是这并没有影响它的实际应用。本节将具体介绍
RSA
签名方案。
RSA签名方案建立在
RSA密码系统上，可以简单将其理解为
RSA加密过程的逆过程：
用私钥解密作为签名，用公钥加密作为验证过程，具体的方案构造如下（见表
5.1）所示。
表
5.1
RSA数字签名方案
步骤签名者认证者
选择大素数
p和
q，计算
N =
pq。选择验
证指数
e，使得
gcd[e,.(N)]
=
1。计算签名
密钥生成
指数
d，使
d满足
ed ≡
1[mod
.(N)]。公钥
为
(N,e)
计算消息
m的签名
σ ≡
m e(mod
N)。发送
签名过程
消息和签名对
(m,σ)给验证者
根据消息签名对
(m,σ)和签名者的公钥
′
验证过程(N,e)，计算
m ≡
σe(mod
N)。如果
m ′ =
m，则签名有效；否则，签名无效
1
.密钥生成：秘密选择大素数
p和
q，计算
N = pq。选择验证指数
e，使得
gcd(v,φ(N))=
1，其中，
φ(N) =(p .61)(q .61)为欧拉函数，签名者计算签名指数
d，使其满足
ed ≡6
1[mod
φ(N)]，即
sk =(d)。最后，公开大整数和验证指数为公钥
pk =(N,e)。
2d
.签名过程：用签名指数
d对消息
m进行签名得到
σ ≡6mmod
N，将消息签
名对
(m,σ)发送给验证者。
3
.验证算法：验证者收到消息签名对
(m,σ)之后，首先利用发送方的公开参数
′′
(N,e)验证签名得
m ≡6σe mod
N。如果
m = m，表示签名有效；否则，签名无效。
也就是
. Verifypk(m, σ)= .
.
true
false
m ≡6σe(mod
N)
m6= σe(mod
N)
(5.9)
6464
RSA签名方案的有效性可以直接通过欧拉定理得到，任何人都可以获取签名者的
公钥来对签名进行有效性验证。但这并不意味着
RSA签名是安全的，下面将证明
RSA
数字签名方案存在选择性伪造和存在性伪造的风险。
定理
5.3（选择性伪造）
RSA签名方案在任意消息攻击下可能被选择性伪造。
Nmodd()≡
()σσσN==mmmm1212·12
证明为了产生消息
m的签名，先选择一个随机数
r ∈
Z. 。定义
m1和
m2分别
dd
d
证明如果能够分别产生两个消息的签名，那么两个消息乘积的签名就是两个消息
为
m1
≡
mr(mod
N)，m2
≡
r.1(mod
N)。遵循选择性伪造攻击中的规则，可请求签名
者生成两个消息的签名分别为
σ1
≡
m1
(mod
N)和
σ2
≡
m2
(mod
N)。进而生成这两个
消息乘积的签名，即
d
.1)d .1)d ≡
m
σ = σ1σ2
= m1
·
m2
=(mr)d
·
(r =(mr ·
r d(mod
N)
dd
σ也就是消息
m的签名，即
m1m2
=(mr)r.1
≡
m(mod
N)，伪造成功，定理得证。
■
定理
5.4（存在性伪造）
RSA签名方案在已知消息攻击下可进行存在性伪造。
签名的乘积。设定
m1和
m2是两个消息，遵循选择性伪造攻击中的规则，可请求签名
d
者生成两个消息的签名分别为
σ1
≡
m1
(mod
N)和
σ2
≡
m2
(mod
N)。现在产生两个消
息乘积的签名：
显然，σ也就是消息
m1m2的签名，因此伪造成功，定理得证。
■
5.5.2RSA数字签名方案的安全性
d
尽管从可证明安全的角度而言
RSA签名并不优秀，但是上述两种攻击的实施都需
要敌手欺骗签名者进行某些看似无害的签名，只是这些签名的明文一般是没有实际意义
的，因此当
RSA签名者是人类时敌手很难实施欺骗，这也是
RSA签名被广泛使用的
原因；此外，实际应用中通常还会采用消息的
Hash值进行签名，使上述攻击均可被避
免。但是，随着大量网络签名者由人类变为程序，这种情况下
RSA签名攻击变得更容
易被实施，因此，在未来应用中应尽量采用更加安全的签名方案。
5.5.3
RSA数字签名实例
例
5.1假定选择两个素数，p = 1223，q = 1987。计算
N = p.
q = 1223 ×
1987 =
2 430 101。进而可计算
φ(N)=(p.
1)(q.
1) = 1222 ×
1986 =2 426 892。选择
e使其
与
φ(N)互素且小于
φ(N)，这里选择
e =1 051 235。公开参数是
(e =1 051 235,N =
2 430 101)。
签名者计算
d并使得
ed ≡
1[mod
φ(N)]，计算可得
d = 948 047。对于输入消息
m =1 070 777，签名者计算签名如下：
σ = m s(mod
N)=1 070 777948
047(mod
2 430 101) ≡
1 473 513
65
并将消息签名对
(m,σ)=(1 070 777,1 473 513)发送给验证者。
任何人可用公钥对该签名进行验证如下：
′
m = σd(mod
N)=1 473 5131
051
235(mod
2 430 101) =1 070 777
可得
m ′ = m，则签名有效。
5.6
ElGamal数字签名
5.6.1
ElGamal数字签名方案
本节将介绍另一类重要的签名方案，它是由
ElGamal在
1985年提出的，并被命名
为
ElGamal数字签名。该方案的变形已被美国国家标准技术研究所（
NIST）采纳为签
名标准。此签名建立在
ElGamal加密系统之上，以离散对数问题为基础，但是其签名
本身与加密方案并没有直接的关系，它是为数字签名而专门设计的，这与
RSA方案有
显著的不同。
ElGamal签名的另一个特点是签名不唯一，这意味着对任何给定的消息能够产生
许多有效的签名，并且验证算法能够将它们中的任何一个作为有效签名而接受。
ElGamal签名方案是基于有限域内求解离散对数问题困难的假设下的，明文空间
为
M
= Zp.
，签名空间为
A
= Zp . ×
Zp.1，其中
p为一个安全素数。方案包括三个过程：
密钥生成、签名算法和认证算法。具体方案构造（见表
5.2）如下。
表
5.2
ElGamal数字签名方案
步骤签名者认证者
密钥生成
(1)选择大素数
p和阶
p.
1随机元
g。
(2)选择秘密的签名指数
s，然后计算
v ≡
g s(mod
p)。
公开验证参数
(v, p, g)
签名过程
选择一个随机数
e，计算
m的签名为：
S1
≡
g e (mod
p)，
S2
≡
(m .
sS1
)e .1
(mod
p.
1)。
输出消息签名对
(m,(S1
,S2
))
认证过程
计算
v1
≡
v S1
SS2
1
(mod
p)和
v2
≡
g m
(mod
p)。如果
v1
=
v2，表示签名有效；
否则，签名无效
.密钥生成：签名者选择一个大素数
p和在
Z. p下阶为
p.
1的一个随机元素
g。
6666
选择一个秘密的签名指数
s并计算
v ≡6gs (mod
p)。公开验证参数
pk =(p,g,v)，签名
私钥为
sk =(s)。
.2签名算法：签名者对消息
m进行签名（
m ∈6Z. p），首先选择一个随机数
e（一
个临时密钥且
1 <e<p）计算签名为
.
.
e
S1
≡6g(mod
p)
. .1
S2
≡6(m .6sS1)e(mod
p.61)
然后将消息和签名
(m,σ)发送给验证者，其中
σ =(S1,S2)。
.3验证算法：验证者收到消息签名信息
(m,σ)之后，计算
vS1
S1
S2
(mod
p)，然后
m
将其与
g(mod
p)进行比较，即
. .
S1
SS2
true
gm ≡6v(mod
p)
Verifypk(m,σ)= 1
(5.10)
.
mS1
SS2
false
g=6v1
(mod
p)
如果相等，表示签名有效；否则，签名无效。
5.6.2
ElGamal数字签名方案的安全性
首先，假设如果签名被有效构造出来，那么验证一定会成功。分析从等式
S2
≡6
.1
(m .6sS1)e(mod
p.61)开始，可知
m ≡6eS2
+ sS1
(mod
p.61) (5.11)
上式被载入到
g的指数上，可得到
g m = g eS2
+sS1
≡6(g e)S2
·
(g s)S1
(mod
p) (5.12)
se
将两个等式
v ≡6g(mod
p)和
S1
≡6g(mod
p)代入上式可得
S1
SS2
g m ≡6v ·
1
(mod
p) (5.13)
可见最终的验证等式成立。
其次，分析一下
ElGamal数字签名方案的安全性。从协议构造上看，假定敌手在
不知道加密指数
s的情况下想对给定的消息
m伪造签名。如果敌手选择一个值
S1，然
x
后试图找出相应的
S2，那么他必须计算离散对数
S2
= logS1
gv.S1，根据离散对数问
题的求解困难程度可知，这是不可行的。另一方面，如果首先选择
S2，然后试图找到
S1，那么必须“求解”等式
vS1
S1
S2
≡6gm(mod
p)，以便获得这个未知的
S1，这是一个
还没有已知可行方法来求解的问题。
另一方面，如果敌手先选择
S1和
S2，然后去解
m，那么他又一次面临着求解离散
对数问题的一个实例，也就是计算
m = logg vS1
S1S2
，因此，敌手也不能使用这种方法
对给定的消息
m伪造签名。总之，上述这些都不是可行的方式。