21世纪高等学校计算机规划教材
现代密码学
Modern Cryptography
作 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社
彭代渊 信息科学与技术学院 dypeng@ 2009.9-2010.1
1
现代密码学
Modern Cryptography
第6章 数字签名
16
6.1.3 数字签名的安全需求
Hash函数与数字签名的安3 数字签名的安全需求
使用已知消息攻击的存在性伪造
攻击者E从一个有效的签名(x, y)开始,其中y=sigK(h(x)).然后他 计算z=h(x),并企图找到x’x,使得h(x’)=h(x).如果E能做到这一 点,则(x’, y)就是一个有效的签名, 从而y是消息x’的一个伪造 签名.为了阻止这种攻击, 必须要求Hash函数h是弱无碰撞的.
假设签名者A采用先加密后签名的方案把消息x发送给接收 者B ,则他先用B的公开密钥eB对x加密, 然后用自己的私钥 dA签名.设A的模数为nA,B的模数为nB.于是A发送给B的数据 为: ( x eB mod nB ) d A mod nA .
如果B是不诚实的,那么B可能伪造A的签名.例如,假设B想 抵赖收到A发的消息x, 慌称收到的是x1.因为nB是B的模数, 所以B知道nB的分解,于是能够计算模nB的离散对数.即他能 找到k满足: ( x1 ) k x mod nB .
t k r 1 l d r 1 s d c d r 1 r c d c d x mod n.
于是，获得了秘文x。
抵抗措施
用户不要轻易地对其他人提供的随机数据进行签名 对数据的Hash值进行签名
25
6.2.2 RSA数字签名的安全性
4．对先加密后签名方案的攻击 攻击方法
使用唯密钥攻击的存在性伪造
当签名算法遭到唯密钥攻击时, 即攻击者E拥有签名者A的公钥 K.E就可能对一个随机的散列值z伪造签名y=sigK(z). 此时, 如果 Hash函数h不是单向的,则E可能找到一个消息x，使得z=h(x). 所以E能够成功伪造一个签名(x, y).为了阻止这种攻击, 必须要 求Hash函数h是单向的.
d d y y1 y2 =x1 x2 =(x1 x2 )d =xd mod n.
于是攻击者E得到了用户A对消息x的RSA数字签名y 抵抗措施
用户不要轻易地对其他人提供的随机数据进行签名 对数据的Hash值进行签名
24
6.2.2 RSA数字签名的安全性
3．利用签名进行攻击从而获得明文 攻击方法
100111000101 00011000
密钥K
sigK
6
6.1.1 数字签名的基本概念
一个数字签名体制是一个满足以下条件的五元组:
(M ,C , K , S ,V )
（1）消息空间:由所有任意长度消息组成的集合 M =A * （2）签名空间: 由所有签名组成的集合。签名长 度不超过n。 C 1in A i （3）密钥空间: K
任给消息x M , 如果 y sig K ( x) C , 则将数据对（x，y）称为消息x的一个数字签名，或 直接把y称为消息x的数字签名
8
6.1.1 数字签名的基本概念
数字签名基本要求 对每一个密钥K, sigK和verK应该是多项式时间函数 verK是公开的函数, 而sigK是保密的 给定一个消息x, 除了发送者本人以外, 任何其他人找到满 足verK(x,y)为真的数字签名y,应该是计算上不可行的 如果攻击者能够找到满足verK(x,y)的数据对(x,y),而发送者 事先又没有对x签名,则称y是伪造(forgery)的数字签名。 数字签名算法必须满足的条件 签名者事后不能否认自己的签名； 其他人不能伪造签名； 当通信双方为签名真伪发生争执时, 可以由第三方解决 争端
x=ye mod n， 于是可以伪造A的一个RSA数字签名（x，y）。因为 xd =(ye)d =yed =y mod n， 所以用户A对x的RSA数字签名是y。
这种攻击实际上成功的概率是不高的 因为对于选择的数据y，得到的x=ye mod n具有正确语 义的概率是很低的。 抵抗措施
仔细设计数据格式 对数据的Hash值进行签名
然后，B再公布他的新公开密钥为keB。现在B宣布他收到 的消息是x1，而不是x。
由于下式成立，所以A无法争辩。
( x1keB mod nB ) d A mod nA ( xeB mod nB )d A mod nA
4
6.1
数字签名概念
签名是证明当事人的身份和数据真实性的一种信息。 在传统的以书面文件为基础的事物处理中，采用书面 签名的形式，如手签、手印和印章等。书面签名得到 司法部门的支持，具有一定的法律意义
5
6.1
数字签名概念
在以计算机文件为基础的现代事物处理中，应采用电 子形式的签名，即数字签名（digital signature）。 数字签名的目的是提供一种手段，使得一个实体把他 的身份与某个信息捆绑在一起。 一个信息的数字签名实际上是一个数，它仅仅依赖于 签名者的密钥和被签名的消息。
23
6.2.2 RSA数字签名的安全性
2．选择消息攻击 攻击方法: 假设攻击者E想伪造消息x的签名，他容 易找到两个数据x1和x2，使得
x=x1 x2 mod n.
攻击者E设法让用户A分别对x1和x2 进行签名，得到
d y1 x1d mod n, y2 x2 mod n.
然后E可以计算
15
6.1.3 数字签名的安全需求
攻击者对数字签名系统的攻击目的 完全破译（total break） 攻击者E能确定签名者A的私钥K，因而能够计算签名 函数sigK，可以对任何消息产生有效的签名。 选择性伪造（selective forgery） 攻击者E能以某一个不可忽略的概率对另外某个人选 定的消息产生一个有效的签名。也就是说，如果给E 选定一个消息x，那么他能以一个正的概率找到x的签 名y=sigK(x)，并且签名者A以前未对x签名。 存在性伪造（existential forgery） 攻击者E至少能够为一个消息产生一个有效的签名。 也就是说，E可能生成一个数据对（x，y），其中x是 消息，y=sigK(x)。签名者A以前未对x签名。
假设攻击者E已截获了秘文c=xe mod n，他想求出明文x。 于是，他选择一个小的随机数r，并计算 s r e mod n, l s c mod n,
t r 1 mod n. 因为s=re,所以sd=( re)d= mod n，r=sd mod n.然后E 设法让签 名者对l签名. 于是E又获得k=ld mod n. 攻击者E再计算：
verK称为验证算法（verification algorithm） （6）任给密钥K K , 签名算法sig K 与验证算法 verK 满足：
对每一个消息x M 和每一个签名y C , 都有 真, y sig K ( x) verK ( x, y ) 假, y sig K ( x)
9
6.1.1 数字签名的基本概念
手写签名与数字签名的区别 手写签名是所签文件的物理组成部分，数字签名必须 与所签文件捆绑在一起。 手写签名通过与标准签名进行比较或检查笔迹来验证， 数字签名是通过验证算法来验证。手写签名容易伪造， 好的数字签名算法应该使伪造签名十分困难。 手写签名不易复制。数字签名是一个二进制串，容易 复制。所以必须防止数字签名重复使用。
21
6.2.1 RSA算法描述
2．签名算法 设消息为x，则x的RAS签名是
y =x mod n.
3．验证算法 当接收方收到签名（x，y）后，计算
d
x , y e mod n.
如果x= x’，则y是x的RAS签名。
22
6.2.2 RSA数字签名的安全性
1．一般攻击 攻击方法: 设n与e为用户A的公钥，攻击者首先随意 选择一个数据y，并用A的公钥计算
彭代渊 信息科学与技术学院 dypeng@ 2009年12月
2
第6章 数字签名
6.1 6.2 6.3 6.4 6.5 6.6 数字签名概念 RSA数字签名体制 ElGamal数字签名体制 其它数字签名方案 数字签名标准 应用
3
6.1
数字签名概念
在政治、军事、外交、商业和日常生活中，人们经常 需要对纸质材料进行签名。 签名起到确认、核准、生效和负责任等多种作用。 随着计算机网络技术的发展，电子商务、电子政务和 电子金融等系统得到广泛应用，人们需要通过网络信 息传输对电子的文件、契约、合同、信件和张单等进 行数字签名以替代手写签名。
使用选择消息攻击的存在性伪造
攻击者E首先找到x’x, 使得h(x’)=h(x). 然后将消息x发给签名 者A, 并让A对消息的散列值h(x)签名, 从而得到y=sigK(h(x)). 所以E能够成功伪造签名(x’, y). 为了阻止这种攻击,必须要求 Hash函数h是强无碰撞的.
18
6.1.3 数字签名的安全需求
14
6.1.3 数字签名的安全需求
数字签名的攻击模型 唯密钥攻击（keyonly attack） 攻击者E拥有签名者A的公钥K，因而能够计算验证函 数verK。 已知消息攻击（known message attack） 攻击者E拥有一系列以前由签名者A所签名的消息。即 E具有数据对（xi，yi），其中xi是消息，yi=sigK (xi)是 A对xi的签名（i=1, 2, …）。 选择消息攻击（chosen message attack） 攻击者E可以选择一些消息请求签名者A签名。即E选 择消息xi，并将xi发送给签名者A，请求A对xi签名。A 计算yi=sigK(xi)，并将yi发给E。所以，E具有A的有效 数字签名（xi，yi）（i=1, 2, …）。