2012-3-19 1
第六章 数字签名
一、数字签名的概念
二,RSA数字签名体制
三,ELGAMAL数字签名体制
四、其他数字签名
五、数字签名标准
2012-3-19 2
一,数字签名 基本概念
2012-3-19 3
数字签名就是两个数学变换, 首先发
送方对信息施以数学变换, 接受方进行逆
变换, 得到原始信息 。 发送方的变换就是
签名, 通常是一种加密, 对应的逆变换就
是对签名的认证, 通常是一种解密措施 。
数字签名体制一般包括两个部分：一是签
名部分, 对消息 M签名, 可以记为 S=SIG（ K
,M）, K是签名者的私钥, 是秘密的 。 二
是接收方的认证部分, 可以记成 VER（ M,S
,K） =（ 真, 假 ） 。
2012-3-19 4
? 数字签名示意图
公钥
算法
加
密
公钥
算法
解
密
数字
签 名
消 息
原 文
消 息
原 文
消 息
原 文
比
较
2012-3-19 5
数字签名的特点
（ 1） 签名是可信的,任何人都可以方便的验证签名的
有效性,
（ 2） 签名是不可伪造的,除了合法的签名者外,任何
其它人伪造签名是困难的, 这种困难性指计算上是不
可行的 。
（ 3） 签名是不可复制的：如果签名是从别的地方复
制的, 任何人都可发现消息与签名的不一致, 从而拒
绝签名 。
2012-3-19 6
数字签名的特点
（ 4） 签名的消息是不可改变的：经过的签名不
能被篡改。
（ 5） 签名是不可抵赖的：签名者不能否认自己
的签名 。
2012-3-19 7
数字签名与加密的区别
(1)在加密中：公钥加密，私钥解密。
(2)数字签名中：签名者用私钥签名，接收者用
签名者的公钥验证。
2012-3-19 8
数字签名的应用
在网络应用中，凡是要解决伪造、抵赖、冒
充、篡改与身份鉴别的问题，都可以运用数
字签名来处理,
1.网上银行通过因特网向客户提供信息查询、
网上支付、信贷等，都需要数字签名。
2.在电子商务中，企业与企业之间，企业与消
费者之间，在网上进行的商业交换活动，也
需要数字签名。
3.在电子政务中,必须提供身份认证服务、权限
控制服务、信息保密服务等，而这些都离不
开数字签名。
2012-3-19 9
二,RSA数字签名体制
2012-3-19 10
? RSA是以它的三个发明者 Ron Rivest，
Adi Shamir和 Leoard Adleman的名字
命名。该算法既可以用于加密，也可以
用于数字签名。 RSA的安全性基于大数
分解的困难性，该算法已经经受住了多
年深入的密码分析，密码分析者既不能
证明也不能否认 RSA的安全性，这恰恰
说明该算法有一定的可信度。
2012-3-19 11
算法描述
? 参数选择
(1)令 是两个素数,
(2)随机选择 e,满足, 那么私钥就
是 （ e,n)
(3)计算,私钥就是 （ d,n),
pqn ?qp,
)(1 ne ???
)(m o d1,nedd ?=
2012-3-19 12
签名过程
（ １ ） 计算消息的散列值Ｈ （ Ｍ ）,
（ ２ ） 加密散列值,
（ ３ ） 签名为
nMHs d m o d))((?
),( sM??
2012-3-19 13
签名验证
(1)解密签名,
(2)比较 h=H(M),如果等号相等, 签名有效；
否则签名无效 。
nsh e m o d?
2012-3-19 14
RSA签名过程图
M || M h
比较
h E D
upk
图中 h,表示 Hah运算； M,消息； E,加密； D解
密 ;Kus, 用户秘密钥 ; Kup, 用户公开密钥。
usk
))(( MhE kus
2012-3-19 15
举例
(1)选择素数 p=5,q=11； n=pq=55,
(2)选择私钥 e=3,由 计算私钥 d=27
假设消息 M=19
(3)签名生成,
(4)签名验证,
40)1-)(1-()( == qpn?
)(m o d1 ned ??
2455m o d19m o d 27 === nmc d
1955m o d24m o d 3 === ncm e
2012-3-19 16
安全性 分析
RSA算法的安全性就是基于大整数的因子
分解困难之上的，到目前为止其还是安全的
。要分析 RSA算法的安全性，我们从攻击 RSA
的角度来审视。总的来分,RSA算法攻击可以
区分为三类,
(1)蛮力攻击：它通过实验所有的可能私钥，
来达到目的。
(2)数字攻击：使用数学技巧，类似于分解 n来
达到攻击目的。
2012-3-19 17
(3)时间攻击：通过观察解密算法运行的时间
来达到目的。
其中抵抗蛮力攻击的方法，与其他加密系统
是一致的 —— 使用大的密钥空间，使穷举法
无能为力。因此 e和 d位数的长度应该与实际
应用系统有综合的权衡 。
2012-3-19 18
因子分解问题
从因子分解问题着手的使用数学手段攻击 RSA的方
法可以区分为如下三类,
（ 1）将 n分解为两个素因子。这就是要计算
,然后可以确定 d。
（ 2） 在不确定 p和 q的情况下，而直接确定 。当
然同样可以计算 。
（ 3）在不确定 的情况下，直接确定 d。
)1)(1()( ??? ppn?
)(n?
)(m o d1 ned ?=
)(n?
2012-3-19 19
目前大部分 RSA密码分析的讨论都集中于
对 n进行素因子分解。给定 n去确定,就
等价于对 n进行因子分解。给定 e和 n,使用目
前已知的攻击算法求出 d的时间开销至少和因
子分解问题的时间开销一样大。所以我们通
常把因子分解的性能作为评价 RSA安全性基准
。
)(n?
2012-3-19 20
定时攻击
定时攻击被安全专家称为, 有创意的攻击,
。因为该攻击与常规攻击方式完全不同，同
时其仅仅使用密文进行攻击。其提出者是密
码分析家 P.C.Kocher,于 1996年提出。 Kocher
曾发明了一种办法，通过监视耗电量的微小
波动，可以推导出一张加密的智能卡中内嵌
的密钥。之后，他又因设计了一种能够攻破
RSA算法实现的技术而轰动一时，该方法其不
是通过正面攻击算法，而是通过观察系统处
理特定函数所花费的时间来寻找破解的蛛丝
马迹。
2012-3-19 21
其他攻击
攻击 RSA还有其他方法，如：迭代攻击、
选择明文攻击、公共模数攻击、低加密指
数攻击等。
2012-3-19 22
使用 RSA的建议
（ 1）不可使用公共模数。
（ 2）明文的熵要尽可能的大。
（ 3）尽量使用散列函数。
2012-3-19 23
三、Ｅ LＧ AMAL数字签名体制
2012-3-19 24
Ｅ LＧ AMAL数字签名体制
ElＧ amal算法既可用于数字签名，也可用于
加密，其安全性依赖于计算有限域上离散对
数的困难性上,ElＧ amal数字签名体制是由
Ｔ．ＥＬＧ amal于１９８５年提出的，其变
体已经使用于ＤＳＳ中,ElＧ amal数字签名体
制是Ｒ abin签名体制的变形，也是使用了随
机数，称为随机化的数签名．ＡＮＳＬＸ９
３０－１９９Ｘ已经将 ElＧ amal数字签名体
制采纳为签名的标准算法,
2012-3-19 25
构造参数
１．全局参数
P：是一个大的素数，确保在 中求
解离散对数在计算上的困难；
g:是 Zp中的乘法群 的一个生成元，
或称为本原元素,
２．私钥参数
x：用户的私钥,
*
pz
*
pz
*
pzx ?
2012-3-19 26
３．公钥参数
y:用户的公钥,
算法中常还使用一个随机数 k．另外，在
本签名体制中，要签字的消息空间为
，签名结果的值空间为 。
pgy x m o d?
pz*
1?
? ?
pp zz
2012-3-19 27
签名 生成
给定要签名的消息为Ｍ，签名过程如下所述,
(1)生成一个随机数
(2)计算
(3)计算
到此，签名结果为（ r,s）
(4)把消息和签名结果（Ｍ,r,s)发送给接收者
pzkk *,?
.m o d,pgrr x?
)1m o d ())((,1 ??? ? pkxrMHss
2012-3-19 28
签名验证
接收方收到消息和签名结果（ M,r,s)后，可以按下面
的步骤验证签名的有效性。
(1)如果１ ≤r≤p -1，那么继续后续步骤；否则，签名
是不合法。
(2)计算
(3)计算
(4)比较 和 如果,表示签名有效；否则，
签名无效,
pryv sr m o d1 ?
pgv MH m o d)(2 ?
1v 2v 12 vv ?
2012-3-19 29
签名验证证明
我们先对签名过程中等式
进行处理有
)1m o d ())((,1 ??? ? pkxrMHss
)1m o d ()(
)1m o d ())((
)1m o d ())((
1
+=?
=?
=
pksrxMH
pxrMHks
pkkxrMHsk
2012-3-19 30
下面考察认证过程中的等式,
因为
所以可以说明该算法是成立的,
12
2
)1-m o d (
2
m o d?
m o d)()(?
m o d
vpryv
pggv
pgv
sr
skrx
pksxr
??
?
?
?
2012-3-19 31
举例
1.参数生成
取 p=2357,g=2;2是 的一个生成元．选择一个
数 x=1751作为私钥．再计算公钥 y,
现在假定消息为 M,H（ M） =1463
pZ*
11852357m o d2m o d 1 7 5 1 === pgy x
2012-3-19 32
签名生成
2.签名过程,
选随机数 k=1529;计算,
签名结果为（ r,s） =(1490,1777)
17772356m o d245)149017511463(
)1m o d ())((
2452356m o d1529)1m o d (
14902357m o d2m o d
1-
1-1
1 5 2 9
????
????
???
???
?
pkxrMHs
pk
pgr
k
2012-3-19 33
签名验证
3.签名验证
接收方在受到消息和签名结果之后，计算,
（ 1）
（ 2）
因为,所以签名有效,
10722357m o d14901185m o d 1 7 7 71 4 9 01 =×== pryv sr
10722357m o d2m o d 1 4 6 3)(2 === pgv MH
21 vv =
2012-3-19 34
ElＧ amal签名体制的变型
? ElＧ amal数字签名体制有很多变形，我们把签名过程中
的等式
修改为,（称为签名方程）
其中，如果,那么签名方程就是
ElＧ amal签名过程中使用的等式。
如果我们把 u,v,w分别对应不同次序的 H（ M）,r,s
就可以得到其他的 ElＧ amal数字签名变体体制,
)1m o d ( ????? pwkvxu
swrvMHu ???,),(
)1m o d ())(( 1 ??? ? pkxrMHs
2012-3-19 35
ElＧ amal签名体制的 6种变形
序号 签名方程 认证等式
１ H(M) r S
２ H(M) s r
３ S r H(M)
４ S H(M) r
５ r s H(M)
６ r H(M) s
v
)1m o d ()( ??? pksxrmh
)1m o d ()( ??? pkrxsmh
)1m o d ()( ??? pMkHxrs
)1m o d ()( ??? pkrMxHs
)1m o d ()( ??? pMkHxsr
)1m o d ()( ??? pksMxHr
prgg srxMH m o d)()( ?
prgg rsxMH m o d)()( ?
prgg MHrxs m o d)( )(?
prgg rMHxs m o d)( )(?
prgg MHsxr m o d)( )(?
prgg sMHxr m o d)( )(?
wu
2012-3-19 36
安全性
? 下面讨论一下 ElＧ amal数字签名体制的安全
１．不知道明文密文对的攻击,
由于攻击者不知道用户私钥Ｘ，所以要伪造
用户签名，需要先选取定一个 r(或 s)，然后实
验求取另外一个值 s(或 r)．都属于求解离散对
数问题,
２．已经知道明文密文对的攻击
攻击者知道（ r,s)是消息Ｍ的合法签字．那么
攻击者可以先择整数 h,i,j,计算,
pyrr ih m o d/ ?
)1m o d ()( 1/ ??? ? pjshrss ?
2012-3-19 37
那么,的合法签字就是,
如果攻击者要预先确定消息,并得到该消
息的合法签名，他还是面临解决离散对数问
题。所以攻击者还是不能得逞。
)1m o d ())(( 1/ ???? ? pjshrishMM ?
/M ),( // sr
/M
2012-3-19 38
（ 3）如果攻击者知道了两个消息,
及其相应的签字, 并且这两
次签名都是使用的同一个随机数Ｋ，那么有
,
那么攻击者可以求解出用户的私钥 x。
所以在签名过程中，要求使用随机数，同时
使用的随机数 Ｋ 不能泄露。
),( 21 MM
),( 11 sr ),( 22 sr
)1m o d (111 ??? pxrksM
)1m o d (222 ??? pxrksM
2012-3-19 39
四、其他数字签名体制
2012-3-19 40
Fiat-Shamir 签名方案
? Fiat-shamir签名方案是由 Fei-Fiat-Shamir
身份鉴别方案变来的，较之 RSA主要好处在于
速度,Fiat-shamir签名方案只需要 RSA的
1/100-4/100的模乘法。
2012-3-19 41
选择 n为两个大素数之积。产生公开密钥 …,,
和私人密钥 …,,满足
（ 1） Alice取 t个 1到 n之间的随机整数,…,,并
计算 …,,满足
（ 2） Alice对消息和这些 x串的连接做散列运算，得到一
个位序列,…,她将串开始的 位
作为 之值，其中 1<I<t,1<j<k。
,,21 vv
kv
,,21 ss
ks
.m o d)( 1 nvs p r ts ii ??
,,21 rr tr
tx,,21 xx,m o d2 nrx ii ?
,,,( 21 xxmH )tx tk?
ijb
2012-3-19 42
（ 3） Alice计算 …,
…
（对于每一个 i,她对基于随机 值的 值做乘法运算。
如果 等于 1，则乘 如果 等于 0，则不乘
（ 4） Alice将, 和 发送给 Bob,他已经获取了
Alice的公开密钥,…,
（ 5） Bob计算 …,
…
,,21 yy,ty
???? bbii ii ssry 21 21( ns bk ik m o d)
ijb
js
1,ib ;1s 1,ib,1s
jib,
m iy
,,21 vv,kv
,,21 zz,tz
???? bbii ii vvyz 21 212 ( nv bk ik m o d)?
2012-3-19 43
（ 6） Bob验证 …, 开始的 个位是
Alice发送给他的 值。
正如身份鉴别方案一样，这种签名方案的安全性正
比于 1/ 。它也依赖于分解 n的难度。 Fiat和 Shamir
指出当分解 n的复杂性低于 时,伪造一个签名很容
易。并且，由于生日类型的攻击，他们推荐 应
从 20至少增至 72，他们建议取 k=9,t=8
,,,( 21 zzmH )tz tk?
jib,
kt2
kt2
tk?
2012-3-19 44
Schnorr数字签名体制
? Schnorr数字签名体制是一个比较著名的
EIGamal签名体制的变种形式。由 C,Schnorr
于 1989年提出的，其密钥的产生与 DSA算法的
密钥产生是一样的，但是对 p,q没有大小的
约束。
? 下面是算法描述
2012-3-19 45
构造参数
1.全局参数
p,q是大的素数。其中 p|(q-1);q是位数大于等于
160bit的整数； p是位数大于等于 152bit的整数，以
确保在 中求解离散对数的困难性。
且 。
以上全局参数，作为所有用户共同使用的参数。
2.私钥参 x, 用户的私钥,1<x<q。
3.公钥参数 y:用户的公钥,
pz
,,* pzgg ? pg q m o d1?
.m o d pgy x?
2012-3-19 46
签名生成
需要签名的消息为 M,那么签名的过程如下,
1.生成一个随机数 k,；
2.计算
3.计算
4.计算
签名结果就是（ s,e)。
*
pzk ?;m o d,pgrr k?
);||(,MrHee ?
.m o d,pxekss ??
2012-3-19 47
认证过程
接收方收到（ M,s,e)后，通过如下步骤进行
认证,
（ 1）取得发送方的公钥 y；
（ 2） 计算
（ 3）计算
（ 4）如果 则表示签名有效；否则签名
无效。;m o d,pygrr es ????
);||(,MrHee ????
ee ??
2012-3-19 48
签名认证证明
如果收到（ M,s,e)中，（ s,e） 是合法的签名
，则有,
r
pg
pg
pgg
pyg
k
xes
exs
es
?
?
?
?
?
?
?
?
m o d
m o d
m o d)(
m o d
r?
2012-3-19 49
Schnorr与 ELGamal比较
（ 1）在 ELGamal签名中,g是 的本原原素；
Schnorr中,g是 的子集 的本原原素。所
ELGamal签名体制安全性高于 Schnorr。
（ 2） Schnorr的签名结果较短，其长度由 和 确定
（ 3）在 Schnorr签名体制中，可以预先计算，因为随机
数与要签名的消息 M无关。
pz
pz q
z
q M
2012-3-19 50
举例
(1) 取 p=129841,q=541,其中（ p-1） /q=240.可以计算
找出一个 g=26,有 。
(2)随机选择 x=423<q,把 x作为用户私钥。计算用户公钥
y,
(3)选择随机数 k=327,计算 r,
然后计算 e:e=H(r||M)=155,
1129841m o d26m o d 5 4 1 ??pg q
115917129841m o d26m o d 4 2 3 ??? pgy x
4 9 3 7 51 2 9 8 4 1m o d26m o d 327 ??? pgr k
2012-3-19 51
举例
（ 4）计算 s,s
签名结果为（ s,e） =（ 431,155）。
（ 5）如果（ m,s,e） 是合法签名则有,
从而验证了签名是有效的。
431
541m o d155423327
m o d
?
???
?? qxek
r?
4 9 3 7 5
1 2 9 8 4 1m o d1 1 5 9 1 726
m o d
1 5 54 3 1
?
??
?
?
? pyg es
:e? 155)||( ???? MrHe
2012-3-19 52
不可否认数字签名
? 一般的数字签名能够被准确复制，其他人都可以用
复制品来验证签名的有效性；这个性质有时是有用
的，如公开宣传品的发布等。但是，有时也带来一
些问题，如签名的私人信件、商业函件等，是不希
望其他人验证的。由此 1989年,Chaum和 Antwerpen
等引入了不可否认数字签名的概念。
? 不可否认数字签名，最本质的是在无签字者的配合
下，不可能验证签字的有效性。利用这个特殊的性
质，可以在一定程度上防止复制或散布他所签字的
文件的可能性，从而使产权所有者可以控制产品的
散发。这在电子出版领域的知识保护中有用途。
2012-3-19 53
? 如果签字者拒绝合作就无法验证签名的有效
性 。但确实是签字者的数字签名，其又拒绝
合作时，又如何处理？那么可以在法庭等第
三方的监督下，启用否认协议（ Disavowal
Protocol）,以证明签名的真假。如果对方
拒绝参与否认协议，那么，就是他签名的；
如果不是他签名的，否认协议可以确认他没
有签名。
? 下面是算法描述,
2012-3-19 54
构造参数
(1)全局参数 p,g
P,q为素数，且 p=2q+1。 那么在 可以构造一个 q
阶乘法子群 G。 g是 本原元素
（ 2） 用户私钥 x
X:满足
（ 3）用户公钥 y
y,
pZ*
)*(11 pzxqx ????
pgy x m o d?
pZ
2012-3-19 55
签名生成
对消息 M的签名如下,
S就是签名结果。在没有签名者的配合下，签
名 S不能被证实。
pms x m o d?
2012-3-19 56
验证过程
在签名者的配合之下，验证如下,
（ 1）验收者收到消息和签名（ m,s）。
（ 2） 接收者选择两个随机数 a,b
(3)接收者然后计算,
将 C发给签名者。
pbpa ???? 0,0
pgsc bxa m o d)(?
2012-3-19 57
签名验证
（ 4）签名者计算,
将 d发送给接收签名的用户。
（ 5）接收者验证下面等式,
如果等式成立，那么，签名成立，否则是签名无效。
pgmd ba m o d?
pcd qx m o dm o d1??
2012-3-19 58
否认协议
上面的验证过程必须要得到签名者的配合才能完成 。
如果签名者拒绝配合过程, 那么就需要启动否认协议
来确定签名的有效性 。
（ 1） 接收者选择随机数 a,b,
（ 2） 接收者计算,
将 c发给签名 者 。
pbpa ???? 0,0
pysc ba m o d?
2012-3-19 59
否认协议
（ 3）签名者计算：,
将 d发给接收者；
（ 4）接收者验证,
如果等式成立，说明签名有效，终止协议。
（ 5）接收者再选择随机数 i,j,;
(6)接收者计算：,将 C发送给签名
者；
pcd qx m o dm o d1-=
pgmd ba m o d=
pjpi ≤≤≤≤ 0,0
pysC ji m o d=
2012-3-19 60
否认协议
（ 7）签名者计算：,
将 D发送给接收者；
（ 8）接收者验证,
如果等式成立，说明签名有效，终止协议。
pcD
qx
m o d
m o d1-
?
pgmD ji m o d=
2012-3-19 61
（ 9）接收者判定，如果下列等式,
成立，那么接收者可以判定签名 s是假的；否
则签名有效。
上面的协议经过了两个回合，（ 1） -（ 4）和（ 5） -
（ 8）都是认证过程的重复；最后通过（ 9）的一致
性检验可以使接受方能够确定出签名者是否如实的
执行了上述规定的协议。
pdgdg ajib m o d)()( -- =
2012-3-19 62
可变换的不可否认签名
1990年,Boyar提出了一种可变换的不可否
认数字签名（ convertible undeniable
signature)算法,该不可否认数字签名能够转
换为常规的数字签名，也就是此时允许所有
人验证签名的有效性。该算法是基于 ELGamal
签名算法的。
2012-3-19 63
算法描述
１．构造参数 与 ELGamal签名算法非常相似。
首先是全局参数,
p,q,都是素数，并且
g,
h:是一个随机数,并且,
*,
qZgqg ∈<
ph <<1
1/ ?pq
phg qp m o d/)1(=
2012-3-19 64
私钥参数,x,
z,
公钥参数,y,
u,
2.签名过程 对消息Ｍ签名过程如下,
（１）选择随机数 t,,
（２） 计算,
qx <
qz <
pgy x m o d=
pgu z m o d=
*∈
qZt
pgT t m o d=
pT tz MM m o d' =
2012-3-19 65
（３）选择随机数Ｒ，,且
（４）计算
（５） 利用欧几里德除法求 s,满足
消息Ｍ的签名结果为（ r,s,T)。
*qZR ∈
1)1,g cd ( ??pR
pgr r m o d=
pRsrxM m o d' +=
2012-3-19 66
3.签名验证过程
（１）接收者产生两个随机数, 并计算
,将 c送给签名者。
（２）签名者产生随机数 k,并计算
将, 发送给接收者。
（３）接收者将 发送给签字者。
1e 2e
pcgh k m o d1 =
phh z m o d12 =
1h 2
h
21、ee
pgTc eT M e m o d21=
签名验证过程
2012-3-19 67
（４）签字者验证如下等式,
成立之后，将随机数 k发送给接收者。
（５）接收者验证,
如果验证成立，表示签名有效。
上述的数字签名算法，当签名者把参数 z公开，该
签名方案就化为普通的数字签名方案。
pgTc eT M e m o d21=
pgTh eT M e m o d211 =
puryh kesere m o d2112 +=
2012-3-19 68
盲签名体制
2012-3-19 69
盲签名
前面介绍的数字签名，签名者可以查看所签
息的内容，这和日常生活的情形相符合：我
们通常需要在知道文件内容之后才会签署。
而在有些时候，要求签名者对所签署消息是
不可见的，就需要盲签名。
盲签名（ blind signature)是由 David Chanm
于 1983年提出的。盲签名在数字现金，电子
投票等领域都有较大的应用价值，特别是目
前的数字现金，大部分都是采用盲签名的原
理实现。
2012-3-19 70
? 盲签名的基本思想是：签名者把明文消息 M通
过盲变换为, 隐藏了明文 M的内容；然后
把 给签字者（仲裁者）进行签名，得到签
名结果 ；最后，签名者取回,采
用解盲变处理得到 S（ M）,就是 M的签名,
M? M?
M?
)(MS ?)(MS ?
盲签名的基本思想
2012-3-19 71
盲签名简图
明文 M S（ M）
)(MS ?M?求签名者 进行盲变换 仲裁者进行签名 求签名者
进行解盲变换
得到签名
S（ M）
2012-3-19 72
完全盲签名协议
假定请求签名者为 A,签字者（仲裁者）
为 B。 盲签名就是要求 A让 B签署一个文件，
而不让 B知悉文件的内容，仅仅要求以后在
需要时 B可以对他所签署的文件进行仲裁。
那么可以通过下面称为完全盲签名的协议
来完成；
（ 1） A把文件用一个随机数乘之，该随机
数常称为盲因子（ Blinding Factor）。
（ 2） A将上面处理后的文件 —— 盲文件传送
给 B。
2012-3-19 73
（ 3） B对盲文件签名。
（ 4） A取回 B的签名结果，并用盲因子除之，
得到 B对原文件的签名。
显然，在上面的协议中，如果签名函数与乘
法可交换，那么上述协议成立。否则盲变换
不能用乘法，而采用其他变换方法。
2012-3-19 74
那么上面协议中,B可以获得文件内容吗？
如果盲因子是完全随机数，显然 B不能获得所
签署文件内容，即使他签署了 A的上万份文件
。但是这些文件确实是他签署的，并且可以
在以后得到证实。
上面的协议使签名者一无所知，虽然具有盲
签名的特点，但是与实际应用还是有差距。
有时签名者希望知道他正在签署的文件是哪
方面的内容，而请求签名者又要求签名者不
能知道所签文件的确切内容。满足该要求就
使用下面协议。
2012-3-19 75
盲签名协议
使用分割 -选择（ Cut-and-Choose） 技术，可
以使签名者 B知道他所签署的是哪方面的信息
，但是还保留盲签名的特征 —— 他不知道所
签署文件的具体内容。下面也使用讲述盲签
名通常使用的例子来加以解说，这些例子在
王育民和 B.Schneier等人的著作中都可以见
到。
2012-3-19 76
【 例 】海关的抽检
【 例 】 海关的抽检。
在繁忙的海关，需要检查进出的人员中有没
有贩毒者。显然检查进出的每一个人是不可能的，
他们采用概率的方法来进行抽查。例如,
对其中 1/10的人进行检查，那么贩毒者有 1/10的
机会被抓获。
当然为了提高对贩毒者的抓获率，就得提高抽检
比例。合理的调整抽检的比例，再辅以其他手段如
高额罚款、科以重刑等，就能够有效的遏制通过海
关的贩毒行为。
2012-3-19 77
RSA模式的盲签名算法
第一个盲签名算法的实现是 D.Chaum于 1985
年提出的，该算法使用了 RSA算法。下面设定
签名者 B的公钥参数为 e,私钥参数为 d,而模
为 n。
下面 A让 B进行盲签名，签署消息 M,
（ 1） A盲变换：选用盲因子 k,1<k<M,计算,
将 t传送给 B
nMkt e m o d?
2012-3-19 78
（ 2） B签名,B对 t进行签名，计算
将签名 S(t)传送给 A
（ 3） A取得签名,A计算取得签名
该签名算法显然成立,S其实就是 B对消息 M进行的
RSA签名
nMkttS ded m o d)()( ??
nMnktS dd m o dm o d/ ??
2012-3-19 79
五、数字签名标准
2012-3-19 80
美国数字签名标准 DSS
数字签名标准 DSS（ Digital Signature
Standard） 是美国国家标准与技术研究所（
NIST） 在 1991年 8月公布的,1994年 5月 19正
式公布的,1994年 12月 1日正式作为美国联邦
信息处理标准 FIPS186颁布（该标准经过一定
的修改，现在叫 FIPS186-2）。 DSS中所用的
算法为 DSA (Digital Signature Algorithm)
注意,DSA是算法,DSS是标准。标准采用算法
，算法是标准的一部分。
2012-3-19 81
DSA的争议
（ 1） DSA不能用于加密或密钥分配。
（ 2） DSA是由 NSA研制的，可能存在馅门。
（ 3） DSA比 RSA慢，二者产生签名的速度相同，
但签名验证 DSA比 RSA慢 40倍。
（ 4） RSA是一个事实上的标准。
2012-3-19 82
DSA的争议
（ 5） DSA的选择过程不公开，并且提供的分析
时间不充分。
（ 6） DSA可能侵犯了其他专利。
（ 7）密钥长度太短。
2012-3-19 83
DSA签名与认证简图
我们先用图来表示 DSA算法的签名过程认
证过程。然后再具体的加以介绍。
M || M h
h 签字 证实
k 比较
s
r
UGK USK UPKUGK
2012-3-19 84
DSA算法作为 EIGamal和 Schnorr签名算法的变
形，显然其安全性也是基于求解离散对数的
困难性上。其算法由参数构造，签名生成，
签名验证构成。
DSA算法描述
2012-3-19 85
构造参数
参数可以分为全局参数、用户私钥和用户公钥三类。
1、全局参数
p,是一个大的素数,；
其中，,并且按 64bit的幅度递增。
q:是（ p-1） 的素因子，并且其字长为 160bit,
即
g:, 其中 h是一个整数,1<h<(p-1),
且要求 。
以上三个参数 p,q,g,是所有用户公用的参数，所
以称之为全局参数，有的也称之为共享的化共模。
1 6 01 5 9 22 ?? q
LL p 22 1 ???
1 0 2 45 1 2 ?? L
phg qp m o d/)1( ??
1m o d/)1( ?? ph qp
2012-3-19 86
2.用户私钥
x:选取一个随机数,要求 0<x<q。
3.用户公钥
y:可以通过计算求得 。
签名的消息空间可以表示为,而签字结果
的值空间可以表示为 。因为签名时需
要一个随机数 k,所以 DSA算法需要一个随机
数生成器。
pgyy x m o d,?
ZP*
pp ZZ ?
2012-3-19 87
签名过程
对消息 M的签名过程可以用如下步骤表示,
（ 1）生成随机数 K,0<k<q;
（ 2） 计算 ;
（ 3）计算,消息 M的签
字结果就是（ r,s）
（ 4） 发送消息和签名结果（ M,r,s）
其中散列函数 H,DSS标准规定使用 SHA,SHA算
法由 SHS标准阐述。
qpgrr k m o d)m o d(,?
qxrMHkSS m o d)))(((,1 ?? ?
2012-3-19 88
认证过程
（ 1）验证者取得发送者的公钥 y；
（ 2） 计算
（ 3）计算
（ 4）计算
（ 5）计算
比较 r,v,如果 r=v,表示签名有效；否则，签名非
法。;m o d))((,11 qwMHuu ?;m o d)(,22 qrwuu ?
qpygvv uu m o d)m o d)((,21?;m o d,1- qsww ?
2012-3-19 89
其它标准
GOST数字签名算法是俄罗斯的数字签名标准
，官方称为 GOST R34.10-94。 该算法与 DSA非
常相似。
2012-3-19 90
算法描述
? p=一个长度在 509到 512位之间的素数。
? q=一个长度在 254到 256位之间，并与 p-1互素的因
子。
? a=任何一个小于 p-1并且满足 的数。
? 私钥,x=一个小于 q的数。
? 公钥,y= modp。
? 算法同样使用一个单向散列函数 H（ x）。 标准指定
了 COSTR34.11-94,一个基于 COST对称算法的函数。
1m o d =pa q
xa
2012-3-19 91
签名生成算法
对消息 m签名时,
（ 1） Alice产生一个小于 q的随机数 k。
（ 2） Alice产生,
如果 那么设它等于 1。如果 r=0,那么另选
一个 k重新开始。签名是两个数,和
,它将这些数发给 Bob,
qpar k m o d)m o d(=
qmHkxrs m o d))((( +=
0m o d)( =qmH
2 5 62m o dr
2 5 62m o ds
2012-3-19 92
签名验证算法
（ 3） Bob通过计算验证签名,
如果 u=r,那么签名是合法的。
qmHv q m o d)( 2??
qsvz m o d)(1 =
qvrqz m o d))((2 ???
qpyau zz m o d)m o d)(( 21 ×=
2012-3-19 93
与 DSA的区别
（ 1）在 DSA中，由于 modq，
导致不同的验证等式。
（ 2） q是 256位，决大多数西方密码学家认为 q
位 160为就满足了，这也许反映俄罗斯倾向于
使它更安全。
? 习题
) ) )((( 1 mHkxrs ???
2012-3-19 94
参考文献
? [1] 杨波编著,现代密码学,北京：清华大学
出版社,2003
? [2]张先红编著,数字签名原理及技术，北京
：机械工业出版社,2004
? [3] 章照止主编，现代密码学基础,北京：
北京邮电大学出版社,2003
? [4] 张焕国，刘玉珍，密码学引论，武汉：
武汉大学出版社,2004
2012-3-19 95
参考文献
? [5] Bruce Schneier著，吴世忠等译，应用密码学（
Applied Cryptography,Protocols,Algorithms,and
Source Code）,北京：机械工业出版社,2000
? [6] William Stallings,Cryprtography and Network
Security,Principles and Practice (2nd version),
北京：清华大学出版社,2000
? [7]冯登国等著，密码学导引，北京：科学出版社，
1999
? [8]王育民、何大可著，保密学 -基础与应用，北京：科
学出版社,1987
第六章 数字签名
一、数字签名的概念
二,RSA数字签名体制
三,ELGAMAL数字签名体制
四、其他数字签名
五、数字签名标准
2012-3-19 2
一,数字签名 基本概念
2012-3-19 3
数字签名就是两个数学变换, 首先发
送方对信息施以数学变换, 接受方进行逆
变换, 得到原始信息 。 发送方的变换就是
签名, 通常是一种加密, 对应的逆变换就
是对签名的认证, 通常是一种解密措施 。
数字签名体制一般包括两个部分：一是签
名部分, 对消息 M签名, 可以记为 S=SIG（ K
,M）, K是签名者的私钥, 是秘密的 。 二
是接收方的认证部分, 可以记成 VER（ M,S
,K） =（ 真, 假 ） 。
2012-3-19 4
? 数字签名示意图
公钥
算法
加
密
公钥
算法
解
密
数字
签 名
消 息
原 文
消 息
原 文
消 息
原 文
比
较
2012-3-19 5
数字签名的特点
（ 1） 签名是可信的,任何人都可以方便的验证签名的
有效性,
（ 2） 签名是不可伪造的,除了合法的签名者外,任何
其它人伪造签名是困难的, 这种困难性指计算上是不
可行的 。
（ 3） 签名是不可复制的：如果签名是从别的地方复
制的, 任何人都可发现消息与签名的不一致, 从而拒
绝签名 。
2012-3-19 6
数字签名的特点
（ 4） 签名的消息是不可改变的：经过的签名不
能被篡改。
（ 5） 签名是不可抵赖的：签名者不能否认自己
的签名 。
2012-3-19 7
数字签名与加密的区别
(1)在加密中：公钥加密，私钥解密。
(2)数字签名中：签名者用私钥签名，接收者用
签名者的公钥验证。
2012-3-19 8
数字签名的应用
在网络应用中，凡是要解决伪造、抵赖、冒
充、篡改与身份鉴别的问题，都可以运用数
字签名来处理,
1.网上银行通过因特网向客户提供信息查询、
网上支付、信贷等，都需要数字签名。
2.在电子商务中，企业与企业之间，企业与消
费者之间，在网上进行的商业交换活动，也
需要数字签名。
3.在电子政务中,必须提供身份认证服务、权限
控制服务、信息保密服务等，而这些都离不
开数字签名。
2012-3-19 9
二,RSA数字签名体制
2012-3-19 10
? RSA是以它的三个发明者 Ron Rivest，
Adi Shamir和 Leoard Adleman的名字
命名。该算法既可以用于加密，也可以
用于数字签名。 RSA的安全性基于大数
分解的困难性，该算法已经经受住了多
年深入的密码分析，密码分析者既不能
证明也不能否认 RSA的安全性，这恰恰
说明该算法有一定的可信度。
2012-3-19 11
算法描述
? 参数选择
(1)令 是两个素数,
(2)随机选择 e,满足, 那么私钥就
是 （ e,n)
(3)计算,私钥就是 （ d,n),
pqn ?qp,
)(1 ne ???
)(m o d1,nedd ?=
2012-3-19 12
签名过程
（ １ ） 计算消息的散列值Ｈ （ Ｍ ）,
（ ２ ） 加密散列值,
（ ３ ） 签名为
nMHs d m o d))((?
),( sM??
2012-3-19 13
签名验证
(1)解密签名,
(2)比较 h=H(M),如果等号相等, 签名有效；
否则签名无效 。
nsh e m o d?
2012-3-19 14
RSA签名过程图
M || M h
比较
h E D
upk
图中 h,表示 Hah运算； M,消息； E,加密； D解
密 ;Kus, 用户秘密钥 ; Kup, 用户公开密钥。
usk
))(( MhE kus
2012-3-19 15
举例
(1)选择素数 p=5,q=11； n=pq=55,
(2)选择私钥 e=3,由 计算私钥 d=27
假设消息 M=19
(3)签名生成,
(4)签名验证,
40)1-)(1-()( == qpn?
)(m o d1 ned ??
2455m o d19m o d 27 === nmc d
1955m o d24m o d 3 === ncm e
2012-3-19 16
安全性 分析
RSA算法的安全性就是基于大整数的因子
分解困难之上的，到目前为止其还是安全的
。要分析 RSA算法的安全性，我们从攻击 RSA
的角度来审视。总的来分,RSA算法攻击可以
区分为三类,
(1)蛮力攻击：它通过实验所有的可能私钥，
来达到目的。
(2)数字攻击：使用数学技巧，类似于分解 n来
达到攻击目的。
2012-3-19 17
(3)时间攻击：通过观察解密算法运行的时间
来达到目的。
其中抵抗蛮力攻击的方法，与其他加密系统
是一致的 —— 使用大的密钥空间，使穷举法
无能为力。因此 e和 d位数的长度应该与实际
应用系统有综合的权衡 。
2012-3-19 18
因子分解问题
从因子分解问题着手的使用数学手段攻击 RSA的方
法可以区分为如下三类,
（ 1）将 n分解为两个素因子。这就是要计算
,然后可以确定 d。
（ 2） 在不确定 p和 q的情况下，而直接确定 。当
然同样可以计算 。
（ 3）在不确定 的情况下，直接确定 d。
)1)(1()( ??? ppn?
)(n?
)(m o d1 ned ?=
)(n?
2012-3-19 19
目前大部分 RSA密码分析的讨论都集中于
对 n进行素因子分解。给定 n去确定,就
等价于对 n进行因子分解。给定 e和 n,使用目
前已知的攻击算法求出 d的时间开销至少和因
子分解问题的时间开销一样大。所以我们通
常把因子分解的性能作为评价 RSA安全性基准
。
)(n?
2012-3-19 20
定时攻击
定时攻击被安全专家称为, 有创意的攻击,
。因为该攻击与常规攻击方式完全不同，同
时其仅仅使用密文进行攻击。其提出者是密
码分析家 P.C.Kocher,于 1996年提出。 Kocher
曾发明了一种办法，通过监视耗电量的微小
波动，可以推导出一张加密的智能卡中内嵌
的密钥。之后，他又因设计了一种能够攻破
RSA算法实现的技术而轰动一时，该方法其不
是通过正面攻击算法，而是通过观察系统处
理特定函数所花费的时间来寻找破解的蛛丝
马迹。
2012-3-19 21
其他攻击
攻击 RSA还有其他方法，如：迭代攻击、
选择明文攻击、公共模数攻击、低加密指
数攻击等。
2012-3-19 22
使用 RSA的建议
（ 1）不可使用公共模数。
（ 2）明文的熵要尽可能的大。
（ 3）尽量使用散列函数。
2012-3-19 23
三、Ｅ LＧ AMAL数字签名体制
2012-3-19 24
Ｅ LＧ AMAL数字签名体制
ElＧ amal算法既可用于数字签名，也可用于
加密，其安全性依赖于计算有限域上离散对
数的困难性上,ElＧ amal数字签名体制是由
Ｔ．ＥＬＧ amal于１９８５年提出的，其变
体已经使用于ＤＳＳ中,ElＧ amal数字签名体
制是Ｒ abin签名体制的变形，也是使用了随
机数，称为随机化的数签名．ＡＮＳＬＸ９
３０－１９９Ｘ已经将 ElＧ amal数字签名体
制采纳为签名的标准算法,
2012-3-19 25
构造参数
１．全局参数
P：是一个大的素数，确保在 中求
解离散对数在计算上的困难；
g:是 Zp中的乘法群 的一个生成元，
或称为本原元素,
２．私钥参数
x：用户的私钥,
*
pz
*
pz
*
pzx ?
2012-3-19 26
３．公钥参数
y:用户的公钥,
算法中常还使用一个随机数 k．另外，在
本签名体制中，要签字的消息空间为
，签名结果的值空间为 。
pgy x m o d?
pz*
1?
? ?
pp zz
2012-3-19 27
签名 生成
给定要签名的消息为Ｍ，签名过程如下所述,
(1)生成一个随机数
(2)计算
(3)计算
到此，签名结果为（ r,s）
(4)把消息和签名结果（Ｍ,r,s)发送给接收者
pzkk *,?
.m o d,pgrr x?
)1m o d ())((,1 ??? ? pkxrMHss
2012-3-19 28
签名验证
接收方收到消息和签名结果（ M,r,s)后，可以按下面
的步骤验证签名的有效性。
(1)如果１ ≤r≤p -1，那么继续后续步骤；否则，签名
是不合法。
(2)计算
(3)计算
(4)比较 和 如果,表示签名有效；否则，
签名无效,
pryv sr m o d1 ?
pgv MH m o d)(2 ?
1v 2v 12 vv ?
2012-3-19 29
签名验证证明
我们先对签名过程中等式
进行处理有
)1m o d ())((,1 ??? ? pkxrMHss
)1m o d ()(
)1m o d ())((
)1m o d ())((
1
+=?
=?
=
pksrxMH
pxrMHks
pkkxrMHsk
2012-3-19 30
下面考察认证过程中的等式,
因为
所以可以说明该算法是成立的,
12
2
)1-m o d (
2
m o d?
m o d)()(?
m o d
vpryv
pggv
pgv
sr
skrx
pksxr
??
?
?
?
2012-3-19 31
举例
1.参数生成
取 p=2357,g=2;2是 的一个生成元．选择一个
数 x=1751作为私钥．再计算公钥 y,
现在假定消息为 M,H（ M） =1463
pZ*
11852357m o d2m o d 1 7 5 1 === pgy x
2012-3-19 32
签名生成
2.签名过程,
选随机数 k=1529;计算,
签名结果为（ r,s） =(1490,1777)
17772356m o d245)149017511463(
)1m o d ())((
2452356m o d1529)1m o d (
14902357m o d2m o d
1-
1-1
1 5 2 9
????
????
???
???
?
pkxrMHs
pk
pgr
k
2012-3-19 33
签名验证
3.签名验证
接收方在受到消息和签名结果之后，计算,
（ 1）
（ 2）
因为,所以签名有效,
10722357m o d14901185m o d 1 7 7 71 4 9 01 =×== pryv sr
10722357m o d2m o d 1 4 6 3)(2 === pgv MH
21 vv =
2012-3-19 34
ElＧ amal签名体制的变型
? ElＧ amal数字签名体制有很多变形，我们把签名过程中
的等式
修改为,（称为签名方程）
其中，如果,那么签名方程就是
ElＧ amal签名过程中使用的等式。
如果我们把 u,v,w分别对应不同次序的 H（ M）,r,s
就可以得到其他的 ElＧ amal数字签名变体体制,
)1m o d ( ????? pwkvxu
swrvMHu ???,),(
)1m o d ())(( 1 ??? ? pkxrMHs
2012-3-19 35
ElＧ amal签名体制的 6种变形
序号 签名方程 认证等式
１ H(M) r S
２ H(M) s r
３ S r H(M)
４ S H(M) r
５ r s H(M)
６ r H(M) s
v
)1m o d ()( ??? pksxrmh
)1m o d ()( ??? pkrxsmh
)1m o d ()( ??? pMkHxrs
)1m o d ()( ??? pkrMxHs
)1m o d ()( ??? pMkHxsr
)1m o d ()( ??? pksMxHr
prgg srxMH m o d)()( ?
prgg rsxMH m o d)()( ?
prgg MHrxs m o d)( )(?
prgg rMHxs m o d)( )(?
prgg MHsxr m o d)( )(?
prgg sMHxr m o d)( )(?
wu
2012-3-19 36
安全性
? 下面讨论一下 ElＧ amal数字签名体制的安全
１．不知道明文密文对的攻击,
由于攻击者不知道用户私钥Ｘ，所以要伪造
用户签名，需要先选取定一个 r(或 s)，然后实
验求取另外一个值 s(或 r)．都属于求解离散对
数问题,
２．已经知道明文密文对的攻击
攻击者知道（ r,s)是消息Ｍ的合法签字．那么
攻击者可以先择整数 h,i,j,计算,
pyrr ih m o d/ ?
)1m o d ()( 1/ ??? ? pjshrss ?
2012-3-19 37
那么,的合法签字就是,
如果攻击者要预先确定消息,并得到该消
息的合法签名，他还是面临解决离散对数问
题。所以攻击者还是不能得逞。
)1m o d ())(( 1/ ???? ? pjshrishMM ?
/M ),( // sr
/M
2012-3-19 38
（ 3）如果攻击者知道了两个消息,
及其相应的签字, 并且这两
次签名都是使用的同一个随机数Ｋ，那么有
,
那么攻击者可以求解出用户的私钥 x。
所以在签名过程中，要求使用随机数，同时
使用的随机数 Ｋ 不能泄露。
),( 21 MM
),( 11 sr ),( 22 sr
)1m o d (111 ??? pxrksM
)1m o d (222 ??? pxrksM
2012-3-19 39
四、其他数字签名体制
2012-3-19 40
Fiat-Shamir 签名方案
? Fiat-shamir签名方案是由 Fei-Fiat-Shamir
身份鉴别方案变来的，较之 RSA主要好处在于
速度,Fiat-shamir签名方案只需要 RSA的
1/100-4/100的模乘法。
2012-3-19 41
选择 n为两个大素数之积。产生公开密钥 …,,
和私人密钥 …,,满足
（ 1） Alice取 t个 1到 n之间的随机整数,…,,并
计算 …,,满足
（ 2） Alice对消息和这些 x串的连接做散列运算，得到一
个位序列,…,她将串开始的 位
作为 之值，其中 1<I<t,1<j<k。
,,21 vv
kv
,,21 ss
ks
.m o d)( 1 nvs p r ts ii ??
,,21 rr tr
tx,,21 xx,m o d2 nrx ii ?
,,,( 21 xxmH )tx tk?
ijb
2012-3-19 42
（ 3） Alice计算 …,
…
（对于每一个 i,她对基于随机 值的 值做乘法运算。
如果 等于 1，则乘 如果 等于 0，则不乘
（ 4） Alice将, 和 发送给 Bob,他已经获取了
Alice的公开密钥,…,
（ 5） Bob计算 …,
…
,,21 yy,ty
???? bbii ii ssry 21 21( ns bk ik m o d)
ijb
js
1,ib ;1s 1,ib,1s
jib,
m iy
,,21 vv,kv
,,21 zz,tz
???? bbii ii vvyz 21 212 ( nv bk ik m o d)?
2012-3-19 43
（ 6） Bob验证 …, 开始的 个位是
Alice发送给他的 值。
正如身份鉴别方案一样，这种签名方案的安全性正
比于 1/ 。它也依赖于分解 n的难度。 Fiat和 Shamir
指出当分解 n的复杂性低于 时,伪造一个签名很容
易。并且，由于生日类型的攻击，他们推荐 应
从 20至少增至 72，他们建议取 k=9,t=8
,,,( 21 zzmH )tz tk?
jib,
kt2
kt2
tk?
2012-3-19 44
Schnorr数字签名体制
? Schnorr数字签名体制是一个比较著名的
EIGamal签名体制的变种形式。由 C,Schnorr
于 1989年提出的，其密钥的产生与 DSA算法的
密钥产生是一样的，但是对 p,q没有大小的
约束。
? 下面是算法描述
2012-3-19 45
构造参数
1.全局参数
p,q是大的素数。其中 p|(q-1);q是位数大于等于
160bit的整数； p是位数大于等于 152bit的整数，以
确保在 中求解离散对数的困难性。
且 。
以上全局参数，作为所有用户共同使用的参数。
2.私钥参 x, 用户的私钥,1<x<q。
3.公钥参数 y:用户的公钥,
pz
,,* pzgg ? pg q m o d1?
.m o d pgy x?
2012-3-19 46
签名生成
需要签名的消息为 M,那么签名的过程如下,
1.生成一个随机数 k,；
2.计算
3.计算
4.计算
签名结果就是（ s,e)。
*
pzk ?;m o d,pgrr k?
);||(,MrHee ?
.m o d,pxekss ??
2012-3-19 47
认证过程
接收方收到（ M,s,e)后，通过如下步骤进行
认证,
（ 1）取得发送方的公钥 y；
（ 2） 计算
（ 3）计算
（ 4）如果 则表示签名有效；否则签名
无效。;m o d,pygrr es ????
);||(,MrHee ????
ee ??
2012-3-19 48
签名认证证明
如果收到（ M,s,e)中，（ s,e） 是合法的签名
，则有,
r
pg
pg
pgg
pyg
k
xes
exs
es
?
?
?
?
?
?
?
?
m o d
m o d
m o d)(
m o d
r?
2012-3-19 49
Schnorr与 ELGamal比较
（ 1）在 ELGamal签名中,g是 的本原原素；
Schnorr中,g是 的子集 的本原原素。所
ELGamal签名体制安全性高于 Schnorr。
（ 2） Schnorr的签名结果较短，其长度由 和 确定
（ 3）在 Schnorr签名体制中，可以预先计算，因为随机
数与要签名的消息 M无关。
pz
pz q
z
q M
2012-3-19 50
举例
(1) 取 p=129841,q=541,其中（ p-1） /q=240.可以计算
找出一个 g=26,有 。
(2)随机选择 x=423<q,把 x作为用户私钥。计算用户公钥
y,
(3)选择随机数 k=327,计算 r,
然后计算 e:e=H(r||M)=155,
1129841m o d26m o d 5 4 1 ??pg q
115917129841m o d26m o d 4 2 3 ??? pgy x
4 9 3 7 51 2 9 8 4 1m o d26m o d 327 ??? pgr k
2012-3-19 51
举例
（ 4）计算 s,s
签名结果为（ s,e） =（ 431,155）。
（ 5）如果（ m,s,e） 是合法签名则有,
从而验证了签名是有效的。
431
541m o d155423327
m o d
?
???
?? qxek
r?
4 9 3 7 5
1 2 9 8 4 1m o d1 1 5 9 1 726
m o d
1 5 54 3 1
?
??
?
?
? pyg es
:e? 155)||( ???? MrHe
2012-3-19 52
不可否认数字签名
? 一般的数字签名能够被准确复制，其他人都可以用
复制品来验证签名的有效性；这个性质有时是有用
的，如公开宣传品的发布等。但是，有时也带来一
些问题，如签名的私人信件、商业函件等，是不希
望其他人验证的。由此 1989年,Chaum和 Antwerpen
等引入了不可否认数字签名的概念。
? 不可否认数字签名，最本质的是在无签字者的配合
下，不可能验证签字的有效性。利用这个特殊的性
质，可以在一定程度上防止复制或散布他所签字的
文件的可能性，从而使产权所有者可以控制产品的
散发。这在电子出版领域的知识保护中有用途。
2012-3-19 53
? 如果签字者拒绝合作就无法验证签名的有效
性 。但确实是签字者的数字签名，其又拒绝
合作时，又如何处理？那么可以在法庭等第
三方的监督下，启用否认协议（ Disavowal
Protocol）,以证明签名的真假。如果对方
拒绝参与否认协议，那么，就是他签名的；
如果不是他签名的，否认协议可以确认他没
有签名。
? 下面是算法描述,
2012-3-19 54
构造参数
(1)全局参数 p,g
P,q为素数，且 p=2q+1。 那么在 可以构造一个 q
阶乘法子群 G。 g是 本原元素
（ 2） 用户私钥 x
X:满足
（ 3）用户公钥 y
y,
pZ*
)*(11 pzxqx ????
pgy x m o d?
pZ
2012-3-19 55
签名生成
对消息 M的签名如下,
S就是签名结果。在没有签名者的配合下，签
名 S不能被证实。
pms x m o d?
2012-3-19 56
验证过程
在签名者的配合之下，验证如下,
（ 1）验收者收到消息和签名（ m,s）。
（ 2） 接收者选择两个随机数 a,b
(3)接收者然后计算,
将 C发给签名者。
pbpa ???? 0,0
pgsc bxa m o d)(?
2012-3-19 57
签名验证
（ 4）签名者计算,
将 d发送给接收签名的用户。
（ 5）接收者验证下面等式,
如果等式成立，那么，签名成立，否则是签名无效。
pgmd ba m o d?
pcd qx m o dm o d1??
2012-3-19 58
否认协议
上面的验证过程必须要得到签名者的配合才能完成 。
如果签名者拒绝配合过程, 那么就需要启动否认协议
来确定签名的有效性 。
（ 1） 接收者选择随机数 a,b,
（ 2） 接收者计算,
将 c发给签名 者 。
pbpa ???? 0,0
pysc ba m o d?
2012-3-19 59
否认协议
（ 3）签名者计算：,
将 d发给接收者；
（ 4）接收者验证,
如果等式成立，说明签名有效，终止协议。
（ 5）接收者再选择随机数 i,j,;
(6)接收者计算：,将 C发送给签名
者；
pcd qx m o dm o d1-=
pgmd ba m o d=
pjpi ≤≤≤≤ 0,0
pysC ji m o d=
2012-3-19 60
否认协议
（ 7）签名者计算：,
将 D发送给接收者；
（ 8）接收者验证,
如果等式成立，说明签名有效，终止协议。
pcD
qx
m o d
m o d1-
?
pgmD ji m o d=
2012-3-19 61
（ 9）接收者判定，如果下列等式,
成立，那么接收者可以判定签名 s是假的；否
则签名有效。
上面的协议经过了两个回合，（ 1） -（ 4）和（ 5） -
（ 8）都是认证过程的重复；最后通过（ 9）的一致
性检验可以使接受方能够确定出签名者是否如实的
执行了上述规定的协议。
pdgdg ajib m o d)()( -- =
2012-3-19 62
可变换的不可否认签名
1990年,Boyar提出了一种可变换的不可否
认数字签名（ convertible undeniable
signature)算法,该不可否认数字签名能够转
换为常规的数字签名，也就是此时允许所有
人验证签名的有效性。该算法是基于 ELGamal
签名算法的。
2012-3-19 63
算法描述
１．构造参数 与 ELGamal签名算法非常相似。
首先是全局参数,
p,q,都是素数，并且
g,
h:是一个随机数,并且,
*,
qZgqg ∈<
ph <<1
1/ ?pq
phg qp m o d/)1(=
2012-3-19 64
私钥参数,x,
z,
公钥参数,y,
u,
2.签名过程 对消息Ｍ签名过程如下,
（１）选择随机数 t,,
（２） 计算,
qx <
qz <
pgy x m o d=
pgu z m o d=
*∈
qZt
pgT t m o d=
pT tz MM m o d' =
2012-3-19 65
（３）选择随机数Ｒ，,且
（４）计算
（５） 利用欧几里德除法求 s,满足
消息Ｍ的签名结果为（ r,s,T)。
*qZR ∈
1)1,g cd ( ??pR
pgr r m o d=
pRsrxM m o d' +=
2012-3-19 66
3.签名验证过程
（１）接收者产生两个随机数, 并计算
,将 c送给签名者。
（２）签名者产生随机数 k,并计算
将, 发送给接收者。
（３）接收者将 发送给签字者。
1e 2e
pcgh k m o d1 =
phh z m o d12 =
1h 2
h
21、ee
pgTc eT M e m o d21=
签名验证过程
2012-3-19 67
（４）签字者验证如下等式,
成立之后，将随机数 k发送给接收者。
（５）接收者验证,
如果验证成立，表示签名有效。
上述的数字签名算法，当签名者把参数 z公开，该
签名方案就化为普通的数字签名方案。
pgTc eT M e m o d21=
pgTh eT M e m o d211 =
puryh kesere m o d2112 +=
2012-3-19 68
盲签名体制
2012-3-19 69
盲签名
前面介绍的数字签名，签名者可以查看所签
息的内容，这和日常生活的情形相符合：我
们通常需要在知道文件内容之后才会签署。
而在有些时候，要求签名者对所签署消息是
不可见的，就需要盲签名。
盲签名（ blind signature)是由 David Chanm
于 1983年提出的。盲签名在数字现金，电子
投票等领域都有较大的应用价值，特别是目
前的数字现金，大部分都是采用盲签名的原
理实现。
2012-3-19 70
? 盲签名的基本思想是：签名者把明文消息 M通
过盲变换为, 隐藏了明文 M的内容；然后
把 给签字者（仲裁者）进行签名，得到签
名结果 ；最后，签名者取回,采
用解盲变处理得到 S（ M）,就是 M的签名,
M? M?
M?
)(MS ?)(MS ?
盲签名的基本思想
2012-3-19 71
盲签名简图
明文 M S（ M）
)(MS ?M?求签名者 进行盲变换 仲裁者进行签名 求签名者
进行解盲变换
得到签名
S（ M）
2012-3-19 72
完全盲签名协议
假定请求签名者为 A,签字者（仲裁者）
为 B。 盲签名就是要求 A让 B签署一个文件，
而不让 B知悉文件的内容，仅仅要求以后在
需要时 B可以对他所签署的文件进行仲裁。
那么可以通过下面称为完全盲签名的协议
来完成；
（ 1） A把文件用一个随机数乘之，该随机
数常称为盲因子（ Blinding Factor）。
（ 2） A将上面处理后的文件 —— 盲文件传送
给 B。
2012-3-19 73
（ 3） B对盲文件签名。
（ 4） A取回 B的签名结果，并用盲因子除之，
得到 B对原文件的签名。
显然，在上面的协议中，如果签名函数与乘
法可交换，那么上述协议成立。否则盲变换
不能用乘法，而采用其他变换方法。
2012-3-19 74
那么上面协议中,B可以获得文件内容吗？
如果盲因子是完全随机数，显然 B不能获得所
签署文件内容，即使他签署了 A的上万份文件
。但是这些文件确实是他签署的，并且可以
在以后得到证实。
上面的协议使签名者一无所知，虽然具有盲
签名的特点，但是与实际应用还是有差距。
有时签名者希望知道他正在签署的文件是哪
方面的内容，而请求签名者又要求签名者不
能知道所签文件的确切内容。满足该要求就
使用下面协议。
2012-3-19 75
盲签名协议
使用分割 -选择（ Cut-and-Choose） 技术，可
以使签名者 B知道他所签署的是哪方面的信息
，但是还保留盲签名的特征 —— 他不知道所
签署文件的具体内容。下面也使用讲述盲签
名通常使用的例子来加以解说，这些例子在
王育民和 B.Schneier等人的著作中都可以见
到。
2012-3-19 76
【 例 】海关的抽检
【 例 】 海关的抽检。
在繁忙的海关，需要检查进出的人员中有没
有贩毒者。显然检查进出的每一个人是不可能的，
他们采用概率的方法来进行抽查。例如,
对其中 1/10的人进行检查，那么贩毒者有 1/10的
机会被抓获。
当然为了提高对贩毒者的抓获率，就得提高抽检
比例。合理的调整抽检的比例，再辅以其他手段如
高额罚款、科以重刑等，就能够有效的遏制通过海
关的贩毒行为。
2012-3-19 77
RSA模式的盲签名算法
第一个盲签名算法的实现是 D.Chaum于 1985
年提出的，该算法使用了 RSA算法。下面设定
签名者 B的公钥参数为 e,私钥参数为 d,而模
为 n。
下面 A让 B进行盲签名，签署消息 M,
（ 1） A盲变换：选用盲因子 k,1<k<M,计算,
将 t传送给 B
nMkt e m o d?
2012-3-19 78
（ 2） B签名,B对 t进行签名，计算
将签名 S(t)传送给 A
（ 3） A取得签名,A计算取得签名
该签名算法显然成立,S其实就是 B对消息 M进行的
RSA签名
nMkttS ded m o d)()( ??
nMnktS dd m o dm o d/ ??
2012-3-19 79
五、数字签名标准
2012-3-19 80
美国数字签名标准 DSS
数字签名标准 DSS（ Digital Signature
Standard） 是美国国家标准与技术研究所（
NIST） 在 1991年 8月公布的,1994年 5月 19正
式公布的,1994年 12月 1日正式作为美国联邦
信息处理标准 FIPS186颁布（该标准经过一定
的修改，现在叫 FIPS186-2）。 DSS中所用的
算法为 DSA (Digital Signature Algorithm)
注意,DSA是算法,DSS是标准。标准采用算法
，算法是标准的一部分。
2012-3-19 81
DSA的争议
（ 1） DSA不能用于加密或密钥分配。
（ 2） DSA是由 NSA研制的，可能存在馅门。
（ 3） DSA比 RSA慢，二者产生签名的速度相同，
但签名验证 DSA比 RSA慢 40倍。
（ 4） RSA是一个事实上的标准。
2012-3-19 82
DSA的争议
（ 5） DSA的选择过程不公开，并且提供的分析
时间不充分。
（ 6） DSA可能侵犯了其他专利。
（ 7）密钥长度太短。
2012-3-19 83
DSA签名与认证简图
我们先用图来表示 DSA算法的签名过程认
证过程。然后再具体的加以介绍。
M || M h
h 签字 证实
k 比较
s
r
UGK USK UPKUGK
2012-3-19 84
DSA算法作为 EIGamal和 Schnorr签名算法的变
形，显然其安全性也是基于求解离散对数的
困难性上。其算法由参数构造，签名生成，
签名验证构成。
DSA算法描述
2012-3-19 85
构造参数
参数可以分为全局参数、用户私钥和用户公钥三类。
1、全局参数
p,是一个大的素数,；
其中，,并且按 64bit的幅度递增。
q:是（ p-1） 的素因子，并且其字长为 160bit,
即
g:, 其中 h是一个整数,1<h<(p-1),
且要求 。
以上三个参数 p,q,g,是所有用户公用的参数，所
以称之为全局参数，有的也称之为共享的化共模。
1 6 01 5 9 22 ?? q
LL p 22 1 ???
1 0 2 45 1 2 ?? L
phg qp m o d/)1( ??
1m o d/)1( ?? ph qp
2012-3-19 86
2.用户私钥
x:选取一个随机数,要求 0<x<q。
3.用户公钥
y:可以通过计算求得 。
签名的消息空间可以表示为,而签字结果
的值空间可以表示为 。因为签名时需
要一个随机数 k,所以 DSA算法需要一个随机
数生成器。
pgyy x m o d,?
ZP*
pp ZZ ?
2012-3-19 87
签名过程
对消息 M的签名过程可以用如下步骤表示,
（ 1）生成随机数 K,0<k<q;
（ 2） 计算 ;
（ 3）计算,消息 M的签
字结果就是（ r,s）
（ 4） 发送消息和签名结果（ M,r,s）
其中散列函数 H,DSS标准规定使用 SHA,SHA算
法由 SHS标准阐述。
qpgrr k m o d)m o d(,?
qxrMHkSS m o d)))(((,1 ?? ?
2012-3-19 88
认证过程
（ 1）验证者取得发送者的公钥 y；
（ 2） 计算
（ 3）计算
（ 4）计算
（ 5）计算
比较 r,v,如果 r=v,表示签名有效；否则，签名非
法。;m o d))((,11 qwMHuu ?;m o d)(,22 qrwuu ?
qpygvv uu m o d)m o d)((,21?;m o d,1- qsww ?
2012-3-19 89
其它标准
GOST数字签名算法是俄罗斯的数字签名标准
，官方称为 GOST R34.10-94。 该算法与 DSA非
常相似。
2012-3-19 90
算法描述
? p=一个长度在 509到 512位之间的素数。
? q=一个长度在 254到 256位之间，并与 p-1互素的因
子。
? a=任何一个小于 p-1并且满足 的数。
? 私钥,x=一个小于 q的数。
? 公钥,y= modp。
? 算法同样使用一个单向散列函数 H（ x）。 标准指定
了 COSTR34.11-94,一个基于 COST对称算法的函数。
1m o d =pa q
xa
2012-3-19 91
签名生成算法
对消息 m签名时,
（ 1） Alice产生一个小于 q的随机数 k。
（ 2） Alice产生,
如果 那么设它等于 1。如果 r=0,那么另选
一个 k重新开始。签名是两个数,和
,它将这些数发给 Bob,
qpar k m o d)m o d(=
qmHkxrs m o d))((( +=
0m o d)( =qmH
2 5 62m o dr
2 5 62m o ds
2012-3-19 92
签名验证算法
（ 3） Bob通过计算验证签名,
如果 u=r,那么签名是合法的。
qmHv q m o d)( 2??
qsvz m o d)(1 =
qvrqz m o d))((2 ???
qpyau zz m o d)m o d)(( 21 ×=
2012-3-19 93
与 DSA的区别
（ 1）在 DSA中，由于 modq，
导致不同的验证等式。
（ 2） q是 256位，决大多数西方密码学家认为 q
位 160为就满足了，这也许反映俄罗斯倾向于
使它更安全。
? 习题
) ) )((( 1 mHkxrs ???
2012-3-19 94
参考文献
? [1] 杨波编著,现代密码学,北京：清华大学
出版社,2003
? [2]张先红编著,数字签名原理及技术，北京
：机械工业出版社,2004
? [3] 章照止主编，现代密码学基础,北京：
北京邮电大学出版社,2003
? [4] 张焕国，刘玉珍，密码学引论，武汉：
武汉大学出版社,2004
2012-3-19 95
参考文献
? [5] Bruce Schneier著，吴世忠等译，应用密码学（
Applied Cryptography,Protocols,Algorithms,and
Source Code）,北京：机械工业出版社,2000
? [6] William Stallings,Cryprtography and Network
Security,Principles and Practice (2nd version),
北京：清华大学出版社,2000
? [7]冯登国等著，密码学导引，北京：科学出版社，
1999
? [8]王育民、何大可著，保密学 -基础与应用，北京：科
学出版社,1987
