《网络与信息安全数字签名幻灯片.ppt》由会员分享，可在线阅读，更多相关《网络与信息安全数字签名幻灯片.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、网络与信息安全数字签名网络与信息安全数字签名1第1页，共79页，编辑于2022年，星期二第第5 5章章 Hash函数与数字签名l5.6 5.6 数字签名概念数字签名概念l5.7 RSA5.7 RSA数字签名体制数字签名体制 l5.8 ElGamal5.8 ElGamal数字签名体制数字签名体制 l5.9 5.9 其它数字签名方案其它数字签名方案l5.10 5.10 数字签名标准数字签名标准l5.11 5.11 应用应用2第2页，共79页，编辑于2022年，星期二5.6 5.6 数字签名概念数字签名概念l在政治、军事、外交、商业和日常生活中，人们经常在政治、军事、外交、商业和日常生活中，人们经常
2、需要对纸质材料进行签名。需要对纸质材料进行签名。l签名起到确认、核准、生效和负责任等多种作用。签名起到确认、核准、生效和负责任等多种作用。l随着计算机网络技术的发展，电子商务、电子政务和随着计算机网络技术的发展，电子商务、电子政务和电子金融等系统得到广泛应用，人们需要通过网络信电子金融等系统得到广泛应用，人们需要通过网络信息传输对电子的文件、契约、合同、信件和张单等进息传输对电子的文件、契约、合同、信件和张单等进行数字签名以替代手写签名。行数字签名以替代手写签名。3第3页，共79页，编辑于2022年，星期二5.6 5.6 数字签名概念数字签名概念l签名是证明当事人的身份和数据真实性的一种信息。
3、签名是证明当事人的身份和数据真实性的一种信息。l在传统的以书面文件为基础的事物处理中，采用书面在传统的以书面文件为基础的事物处理中，采用书面签名的形式，如手签、手印和印章等。书面签名得到签名的形式，如手签、手印和印章等。书面签名得到司法部门的支持，具有一定的法律意义司法部门的支持，具有一定的法律意义4第4页，共79页，编辑于2022年，星期二5.6 5.6 数字签名概念数字签名概念l在以计算机文件为基础的现代事物处理中，应采用电在以计算机文件为基础的现代事物处理中，应采用电子形式的签名，即数字签名（子形式的签名，即数字签名（digital signature）。）。l数字签名的目的是提供一种手
4、段，使得一个实体把他数字签名的目的是提供一种手段，使得一个实体把他的身份与某个信息捆绑在一起。的身份与某个信息捆绑在一起。l一个信息的数字签名实际上是一个数，它仅仅依赖于一个信息的数字签名实际上是一个数，它仅仅依赖于签名者的密钥和被签名的消息。签名者的密钥和被签名的消息。10011100010100011000sigK密钥K5第5页，共79页，编辑于2022年，星期二5.6.1 数字签名的基本概念数字签名的基本概念u（1）消息空间）消息空间:由所有任意长度消息组成的集合由所有任意长度消息组成的集合 u（2）签名空间）签名空间:由所有签名组成的集合。签名长由所有签名组成的集合。签名长度不超过度不
5、超过n。u（3）密钥空间）密钥空间:u（4）sigK称为签名算法（称为签名算法（signing algorithm）l一个数字签名体制是一个满足以下条件的五元组一个数字签名体制是一个满足以下条件的五元组:6第6页，共79页，编辑于2022年，星期二5.6.1 数字签名的基本概念数字签名的基本概念u（5）verK称为验证算法（称为验证算法（verification algorithm）u（6）u 则将数据对（则将数据对（x，y）称为消息）称为消息x的一个数字签名，或的一个数字签名，或直接把直接把y称为消息称为消息x的数字签名的数字签名7第7页，共79页，编辑于2022年，星期二5.6.1 数字签
6、名的基本概念数字签名的基本概念l数字签名基本要求数字签名基本要求u对每一个密钥对每一个密钥K,sigK和和verK应该是多项式时间函数应该是多项式时间函数uverK是公开的函数是公开的函数,而而sigK是保密的是保密的 u给定一个消息给定一个消息x,除了发送者本人以外除了发送者本人以外,任何其他人找到满足任何其他人找到满足verK(x,y)为真的数字签名为真的数字签名y,应该是计算上不可行的应该是计算上不可行的u如果攻击者能够找到满足如果攻击者能够找到满足verK(x,y)的数据对的数据对(x,y),而发送者事而发送者事先又没有对先又没有对x签名签名,则称则称y是伪造是伪造(forgery)的
7、数字签名。的数字签名。l数字签名算法必须满足的条件数字签名算法必须满足的条件u签名者事后不能否认自己的签名；签名者事后不能否认自己的签名；u其他人不能伪造签名；其他人不能伪造签名；u当通信双方为签名真伪发生争执时当通信双方为签名真伪发生争执时,可以由第三方解决争可以由第三方解决争端端8第8页，共79页，编辑于2022年，星期二5.6.1 数字签名的基本概念数字签名的基本概念l手写签名与数字签名的区别手写签名与数字签名的区别u手写签名是所签文件的物理组成部分，数字签名必须与所手写签名是所签文件的物理组成部分，数字签名必须与所签文件捆绑在一起。签文件捆绑在一起。u手写签名通过与标准签名进行比较或检
8、查笔迹来验证，数字手写签名通过与标准签名进行比较或检查笔迹来验证，数字签名是通过验证算法来验证。手写签名容易伪造，好的数字签名是通过验证算法来验证。手写签名容易伪造，好的数字签名算法应该使伪造签名十分困难。签名算法应该使伪造签名十分困难。u手写签名不易复制。数字签名是一个二进制串，容易复制。手写签名不易复制。数字签名是一个二进制串，容易复制。所以必须防止数字签名重复使用。所以必须防止数字签名重复使用。9第9页，共79页，编辑于2022年，星期二5.6.1 数字签名的基本概念数字签名的基本概念l签名算法进行分类签名算法进行分类u按应用目的按应用目的p普通数字签名普通数字签名p特殊目的数字签名特殊
9、目的数字签名:不可否认数字签名、盲签名、群不可否认数字签名、盲签名、群签名等签名等u按验证方法按验证方法p在验证时需要输入被签名信息在验证时需要输入被签名信息p在验证时自动恢复被签名信息在验证时自动恢复被签名信息u按签名时是否使用随机数按签名时是否使用随机数p分成确定性数字签名分成确定性数字签名p随机数字签名随机数字签名10第10页，共79页，编辑于2022年，星期二5.6.2 数字签名的基本构造方法数字签名的基本构造方法l利用利用Hash函数和加密算法可以构造有效的数字签名方案。函数和加密算法可以构造有效的数字签名方案。l基于基于Hash函数和单钥密码算法构造数字签名函数和单钥密码算法构造数
10、字签名 11第11页，共79页，编辑于2022年，星期二5.6.2 数字签名的基本构造方法数字签名的基本构造方法l基于基于Hash函数和双钥密码算法构造数字签名函数和双钥密码算法构造数字签名12第12页，共79页，编辑于2022年，星期二5.6.2 数字签名的基本构造方法数字签名的基本构造方法l具有保密作用的数字签名具有保密作用的数字签名u双钥密码体制：双钥密码体制：SK是发送方的私钥，是发送方的私钥，PK是发送方的公钥，是发送方的公钥，E1和和D1分别是加密算法与解密算法。分别是加密算法与解密算法。u单钥密码体制密钥：单钥密码体制密钥：K是双方公用密钥，是双方公用密钥，E2和和D2分别是对应
11、的分别是对应的加密算法和解密算法。加密算法和解密算法。13第13页，共79页，编辑于2022年，星期二 5.6.3 数字签名的安全需求数字签名的安全需求l数字签名的攻击模型数字签名的攻击模型u唯密钥攻击（唯密钥攻击（key only attack）攻击者攻击者E拥有签名者拥有签名者A的公钥的公钥K，因而能够计算验证函数，因而能够计算验证函数verK。u已知消息攻击（已知消息攻击（known message attack）攻击者攻击者E拥有一系列以前由签名者拥有一系列以前由签名者A所签名的消息。即所签名的消息。即E具有数据具有数据对（对（xi，yi），其中），其中xi是消息，是消息，yi=sig
12、K(xi)是是A对对xi的签名（的签名（i=1,2,）。）。u选择消息攻击（选择消息攻击（chosen message attack）攻击者攻击者E可以选择一些消息请求签名者可以选择一些消息请求签名者A签名。即签名。即E选择消息选择消息xi，并将并将xi发送给签名者发送给签名者A，请求，请求A对对xi签名。签名。A计算计算yi=sigK(xi)，并，并将将yi发给发给E。所以，。所以，E具有具有A的有效数字签名（的有效数字签名（xi，yi）（）（i=1,2,）。）。14第14页，共79页，编辑于2022年，星期二 5.6.3 数字签名的安全需求数字签名的安全需求l攻击者对数字签名系统的攻击目的
13、攻击者对数字签名系统的攻击目的u完全破译（完全破译（total break）攻击者攻击者E能确定签名者能确定签名者A的私钥的私钥K，因而能够计算签名函数，因而能够计算签名函数sigK，可以对任何消息产生有效的签名。，可以对任何消息产生有效的签名。u选择性伪造（选择性伪造（selective forgery）攻击者攻击者E能以某一个不可忽略的概率对另外某个人选定的能以某一个不可忽略的概率对另外某个人选定的消息产生一个有效的签名。也就是说，如果给消息产生一个有效的签名。也就是说，如果给E选定一个选定一个消息消息x，那么他能以一个正的概率找到，那么他能以一个正的概率找到x的签名的签名y=sigK(x
14、)，并且签名者并且签名者A以前未对以前未对x签名。签名。u存在性伪造（存在性伪造（existential forgery）攻击者攻击者E至少能够为一个消息产生一个有效的签名。也就是说，至少能够为一个消息产生一个有效的签名。也就是说，E可能生成一个数据对（可能生成一个数据对（x，y），其中），其中x是消息，是消息，y=sigK(x)。签名者签名者A以前未对以前未对x签名。签名。15第15页，共79页，编辑于2022年，星期二 5.6.3 数字签名的安全需求数字签名的安全需求lHash函数与数字签名的安全性函数与数字签名的安全性u对消息的散列值签名对消息的散列值签名16第16页，共79页，编辑于2
15、022年，星期二 5.6.3 数字签名的安全需求数字签名的安全需求u使用已知消息攻击的存在性伪造使用已知消息攻击的存在性伪造 攻击者攻击者E从一个有效的签名从一个有效的签名(x,y)开始开始,其中其中y=sigK(h(x).然后他计然后他计算算z=h(x),并企图找到并企图找到x x,使得使得h(x)=h(x).如果如果E能做到这一点能做到这一点,则则(x,y)就是一个有效的签名就是一个有效的签名,从而从而y是消息是消息x的一个伪造签名的一个伪造签名.为为了阻止这种攻击了阻止这种攻击,必须要求必须要求Hash函数函数h是弱无碰撞的是弱无碰撞的.u使用选择消息攻击的存在性伪造使用选择消息攻击的存
16、在性伪造 攻击者攻击者E首先找到首先找到x x,使得使得h(x)=h(x).然后将消息然后将消息x发给签名者发给签名者A,并让并让A对消息的散列值对消息的散列值h(x)签名签名,从而得到从而得到y=sigK(h(x).所以所以E能够成功能够成功伪造签名伪造签名(x,y).为了阻止这种攻击为了阻止这种攻击,必须要求必须要求Hash函数函数h是强无碰撞是强无碰撞的的.17第17页，共79页，编辑于2022年，星期二 5.6.3 数字签名的安全需求数字签名的安全需求u使用唯密钥攻击的存在性伪造使用唯密钥攻击的存在性伪造 当签名算法遭到唯密钥攻击时当签名算法遭到唯密钥攻击时,即攻击者即攻击者E拥有签名
17、者拥有签名者A的公钥的公钥K.E就可就可能对一个随机的散列值能对一个随机的散列值z伪造签名伪造签名y=sigK(z).此时此时,如果如果Hash函数函数h不是不是单向的单向的,则则E可能找到一个消息可能找到一个消息x，使得，使得z=h(x).所以所以E能够成功伪造一能够成功伪造一个签名个签名(x,y).为了阻止这种攻击为了阻止这种攻击,必须要求必须要求Hash函数函数h是单向的是单向的.18第18页，共79页，编辑于2022年，星期二第第5 5章章 HashHash函数与数字签名函数与数字签名l5.6 5.6 数字签名概念数字签名概念l5.7 RSA5.7 RSA数字签名体制数字签名体制 l5
18、.8 ElGamal5.8 ElGamal数字签名体制数字签名体制 l5.9 5.9 其它数字签名方案其它数字签名方案l5.10 5.10 数字签名标准数字签名标准l5.11 5.11 应用应用19第19页，共79页，编辑于2022年，星期二 5.7 RSA数字签名体制数字签名体制l利用利用RSA加密算法构造的数字签名称为加密算法构造的数字签名称为RAS数字签名体制。数字签名体制。l5.7.1 RSA算法描述算法描述l1密钥生成算法密钥生成算法u选取两个大素数选取两个大素数p，q，计算，计算 n=p q，(n)=(p 1)(q 1)。u任选整数任选整数e，满足：，满足：0 e (n)，且，且g
19、cd(e,(n)=1。u用扩展用扩展Euclidean算法求算法求e模模(n)的逆的逆d，即，即 e d=1 mod (n)。u签名者的公钥签名者的公钥:n，e，私钥，私钥:p，q，d。20第20页，共79页，编辑于2022年，星期二 5.7.1 RSA算法描述算法描述l2签名算法签名算法 设消息为设消息为x，则，则x的的RAS签名是签名是l3验证算法验证算法 当接收方收到签名（当接收方收到签名（x，y）后，计算）后，计算如果如果x=x，则，则y是是x的的RAS签名。签名。21第21页，共79页，编辑于2022年，星期二5.7.2 RSA数字签名的安全性数字签名的安全性l1一般攻击一般攻击u攻
20、击方法攻击方法:设设n与与e为用户为用户A的公钥，攻击者首先随意选择一个的公钥，攻击者首先随意选择一个数据数据y，并用，并用A的公钥计算的公钥计算 x=ye mod n，于是可以伪造于是可以伪造A的一个的一个RSA数字签名（数字签名（x，y）。因为）。因为 xd=(ye)d=yed=y mod n，所以用户所以用户A对对x的的RSA数字签名是数字签名是y。u这种攻击实际上成功的概率是不高的这种攻击实际上成功的概率是不高的 因为对于选择的数据因为对于选择的数据y，得到的，得到的x=ye mod n具有正确语义的概具有正确语义的概率是很低的。率是很低的。u抵抗措施抵抗措施p仔细设计数据格式仔细设计
21、数据格式p对数据的对数据的Hash值进行签名值进行签名22第22页，共79页，编辑于2022年，星期二5.7.2 RSA数字签名的安全性数字签名的安全性l2选择消息攻击选择消息攻击u攻击方法攻击方法:假设攻击者假设攻击者E想伪造消息想伪造消息x的签名，他容易找到两的签名，他容易找到两个数据个数据x1和和x2，使得，使得 攻击者攻击者E设法让用户设法让用户A分别对分别对x1和和x2 进行签名，得到进行签名，得到 然后然后E可以计算可以计算 于是攻击者于是攻击者E得到了用户得到了用户A对消息对消息x的的RSA数字签名数字签名yu抵抗措施抵抗措施p用户不要轻易地对其他人提供的随机数据进行签名用户不要
22、轻易地对其他人提供的随机数据进行签名p对数据的对数据的Hash值进行签名值进行签名 23第23页，共79页，编辑于2022年，星期二5.7.2 RSA数字签名的安全性数字签名的安全性l3利用签名进行攻击从而获得明文利用签名进行攻击从而获得明文u攻击方法攻击方法 假设攻击者假设攻击者E已截获了秘文已截获了秘文c=xe mod n，他想求出明文，他想求出明文x。于是，他选。于是，他选择一个小的随机数择一个小的随机数r，并计算，并计算 因为因为s=re,所以所以sd=(re)d=mod n，r=sd mod n.然后然后E 设法让签名者对设法让签名者对l签名签名.于是于是E又获得又获得k=ld mo
23、d n.攻击者攻击者E再计算：再计算：于是，获得了秘文于是，获得了秘文x。u抵抗措施抵抗措施p用户不要轻易地对其他人提供的随机数据进行签名用户不要轻易地对其他人提供的随机数据进行签名p对数据的对数据的Hash值进行签名值进行签名 24第24页，共79页，编辑于2022年，星期二5.7.2 RSA数字签名的安全性数字签名的安全性l4对先加密后签名方案的攻击对先加密后签名方案的攻击u攻击方法攻击方法 假设签名者假设签名者A采用先加密后签名的方案把消息采用先加密后签名的方案把消息x发送给接收者发送给接收者B,则他先用则他先用B的公开密钥的公开密钥eB对对x加密加密,然后用自己的私钥然后用自己的私钥d
24、A签名签名.设设A的的模数为模数为nA,B的模数为的模数为nB.于是于是A发送给发送给B的数据为的数据为:如果如果B是不诚实的是不诚实的,那么那么B可能伪造可能伪造A的签名的签名.例如例如,假设假设B想抵赖想抵赖收到收到A发的消息发的消息x,慌称收到的是慌称收到的是x1.因为因为nB是是B的模数的模数,所以所以B知道知道nB的分解的分解,于是能够计算模于是能够计算模nB的离散对数的离散对数.即他能找到即他能找到k满足满足:然后，然后，B再公布他的新公开密钥为再公布他的新公开密钥为keB。现在。现在B宣布他收到的消息宣布他收到的消息是是x1，而不是，而不是x。由于下式由于下式成立，所以成立，所以
25、A无法争辩。无法争辩。25第25页，共79页，编辑于2022年，星期二5.7.2 RSA数字签名的安全性数字签名的安全性l4对先加密后签名方案的攻击对先加密后签名方案的攻击u抵抗措施抵抗措施p签名者签名者A应当在发送的数据中加入时间戳，从而可证明应当在发送的数据中加入时间戳，从而可证明是用公开密钥是用公开密钥eB对对x加密，而不是用新公开密钥加密，而不是用新公开密钥keB对对x1加密。加密。p对数据的对数据的Hash值进行签名。值进行签名。l综上所述，对于综上所述，对于RSA数字签名系统，必须采取如下安全措施：数字签名系统，必须采取如下安全措施：u不直接对消息进行签名，而应该对消息的不直接对消
26、息进行签名，而应该对消息的Hash值进行签名。值进行签名。u要采用先签名后加密的方式，而不要采用先加密后签要采用先签名后加密的方式，而不要采用先加密后签名的方式。名的方式。26第26页，共79页，编辑于2022年，星期二第第5 5章章 HashHash函数与数字签名函数与数字签名l5.6 5.6 数字签名概念数字签名概念l5.7 RSA5.7 RSA数字签名体制数字签名体制 l5.8 ElGamal5.8 ElGamal数字签名体制数字签名体制 l5.9 5.9 其它数字签名方案其它数字签名方案l5.10 5.10 数字签名标准数字签名标准l5.11 5.11 应用应用27第27页，共79页，
27、编辑于2022年，星期二5.8 ElGamal5.8 ElGamal数字签名体制数字签名体制u在在1985年，年，ElGamal T.提出了一个基于离散对数问提出了一个基于离散对数问题的数字签名体制，通常称为题的数字签名体制，通常称为ElGamal数字签名体制。数字签名体制。uElGamal签名体制的安全性主要是基于有限域上离散对签名体制的安全性主要是基于有限域上离散对数问题的难解性。数问题的难解性。28第28页，共79页，编辑于2022年，星期二5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述l1参数生成算法参数生成算法u选取一个大素数选取一个大素数p，g Zp*
28、是一个本原元，是一个本原元，p和和g是系统是系统公开参数。公开参数。u任选整数任选整数x，满足：，满足：1xp 2。计算。计算 y=gx mod p.签名者的公钥为签名者的公钥为y，私钥为，私钥为x。l2签名算法签名算法 设设M Zp*为待签名的消息。签名者随机选择一个秘为待签名的消息。签名者随机选择一个秘密整数密整数k，1kp 2，计算，计算 签名者对签名者对M的的ElGamal签名为签名为:签名者将数据签名者将数据(M,(r,s)发送给接收者。发送给接收者。29第29页，共79页，编辑于2022年，星期二5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述l3验证算
29、法验证算法 接收方收到签名接收方收到签名(M,(r,s)后，验证后，验证 是否成立，如果等号成立，则确认是否成立，如果等号成立，则确认(r,s)是是M的有效签名。的有效签名。l有效性有效性证明证明 因此，如果（因此，如果（r，s）是）是M的正确签名，则一定有的正确签名，则一定有30第30页，共79页，编辑于2022年，星期二5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述lElGamal数字签名是一个随机的数字签名体制数字签名是一个随机的数字签名体制 l例例5.6 设设p=11，g=2是是Z11*的本原元。选取私钥为的本原元。选取私钥为x=8，u计算公钥计算公钥 设
30、签名者设签名者A要对消息要对消息M=5进行签名。签名者进行签名。签名者A首先秘密首先秘密选取一个整数选取一个整数k=9，计算，计算u签名者签名者A对对M=5的的ElGamal签名为（签名为（6,3）。）。u接收者接收者B可以对消息可以对消息M=5的签名（的签名（6,3）进行验证。）进行验证。因为因为31第31页，共79页，编辑于2022年，星期二5.8.25.8.2 ElGamal数字签名的安全性数字签名的安全性 lElGamal数字签名算法的实现数字签名算法的实现u需要作一次模指数运算需要作一次模指数运算u一次扩展一次扩展Euclidean算法运算（求随机数算法运算（求随机数k的逆元）的逆元
31、）u二次模乘运算二次模乘运算u前两个运算可以离线进行前两个运算可以离线进行u是一个随机的数字签名体制是一个随机的数字签名体制 lElGamal数字签名体制的参数数字签名体制的参数pup的选择与在的选择与在Zp*中计算离散对数的算法有直接关系。从目前中计算离散对数的算法有直接关系。从目前的计算水平来看，的计算水平来看，p至少应该是二进制至少应该是二进制512位的素数，从长期安位的素数，从长期安全性考虑，应使用全性考虑，应使用1024位或更长的素数。位或更长的素数。up 1最好有大的素因子最好有大的素因子u私钥私钥x最好是最好是Zp*的素数阶子群的生成元。的素数阶子群的生成元。32第32页，共79
32、页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击不知道私钥的攻击 假设攻击者假设攻击者E不知道私钥不知道私钥x，要想伪造消息，要想伪造消息M的签名的签名(r,s),则则E可能使用的攻击方式有：可能使用的攻击方式有：u(1)攻击者已知消息攻击者已知消息M,选择一个值选择一个值r,再求另一个值再求另一个值s.此时此时,因为有因为有 所以攻击者所以攻击者E必须计算离散对数。必须计算离散对数。u(2)攻击者已知消息攻击者已知消息M,选择一个值选择一个值s,再求另一个值再求另一个值r.此此时时,他必须从同余方程他必须从同余方程 中求出
33、中求出r。这是一个到目前为止还没有可行方法求解的。这是一个到目前为止还没有可行方法求解的方程，甚至也看不出它与离散对数问题有没有关系。方程，甚至也看不出它与离散对数问题有没有关系。33第33页，共79页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击不知道私钥的攻击 u(3)攻击者已知消息攻击者已知消息M，同时求，同时求(r,s).即他必须从同即他必须从同余方程余方程 中同时求出中同时求出(r,s)。现在人们对这个方程的认识几乎。现在人们对这个方程的认识几乎是一无所有，既没有人发现解这个问题的方法，也没是一无所有，既没有人发现
34、解这个问题的方法，也没有人能够证明不能解这个问题。有人能够证明不能解这个问题。u(4)攻击者选择数据对攻击者选择数据对(r,s)，求消息，求消息M。此时必须计。此时必须计算离散对数算离散对数34第34页，共79页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击不知道私钥的攻击 u(5)攻击者同时选择数据攻击者同时选择数据M，r和和s，使得，使得(r,s)是是M的签名。的签名。这种攻击方法可能获得成功。攻击者首先选择整数这种攻击方法可能获得成功。攻击者首先选择整数i和和j，0i,jp 2，gcd(j,p 1)=1，计算，计算 成
35、立，所以成立，所以(r,s)是消息是消息M的有效签名的有效签名 p该攻击方法属于存在性伪造。因此，在使用该攻击方法属于存在性伪造。因此，在使用ElGamal数字签名方案数字签名方案时，不要直接对消息进行签名，而应该对消息的时，不要直接对消息进行签名，而应该对消息的Hash值进行签名。值进行签名。35第35页，共79页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击不知道私钥的攻击 u例例5.7 设设p=467，g=2是是Z467*的本原元，签名者公钥的本原元，签名者公钥y=132。攻击者选择整数。攻击者选择整数i=99，j=1
36、79，计算，计算所以（所以（117，41）是消息）是消息M=331的有效签名。的有效签名。36第36页，共79页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l2已知消息攻击已知消息攻击 u假设攻击者假设攻击者E知道知道(r,s)是消息是消息M的签名的签名,则则E可利用它来伪造其它消息可利用它来伪造其它消息的签名的签名.选择整数选择整数l,i,j,0 l,i,j p 2，gcd(lr js,p 1)=1,计算计算 可见可见(u,v)是消息是消息W的有效签名。的有效签名。u该攻击方法属于存在性伪造该攻击方法属于存在性伪造u使用对消息的使用对消息的
37、Hash值进行签名的方式值进行签名的方式,可以抵抗这类攻击可以抵抗这类攻击.37第37页，共79页，编辑于2022年，星期二5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l使用使用ElGamal数字签名方案的安全措施数字签名方案的安全措施 u(1)不要泄露随机数不要泄露随机数ku(2)不要使用同一个随机数不要使用同一个随机数k给两个不同的消息签名给两个不同的消息签名 设（设（r，s）是消息）是消息M的签名，（的签名，（u，v）是消息）是消息W的签名，的签名，使用的是同一个随机数使用的是同一个随机数k，则，则可求出私钥可求出私钥。38第38页，共79页，编辑于2022年，
38、星期二5.8.4 ElGamal签名体制的变形签名体制的变形lElGamal数字签名算法有多种变形数字签名算法有多种变形u设大素数设大素数p是模数，是模数，g是一个模是一个模p的本原元，的本原元，x为签名者的为签名者的私钥，私钥，k为随机数，为随机数，m为待签名的消息，（为待签名的消息，（r，s）是对）是对M的的签名。签名值的分量签名。签名值的分量r=gk mod p,分量分量s由签名算法确由签名算法确定。定。ElGamal数字签名各种变形的签名算法和验证算数字签名各种变形的签名算法和验证算法见下表。法见下表。39第39页，共79页，编辑于2022年，星期二5.8.4 ElGamal签名体制签
39、名体制的变形的变形40第40页，共79页，编辑于2022年，星期二第第5 5章章 数字签名数字签名l5.6 5.6 数字签名概念数字签名概念l5.7 RSA5.7 RSA数字签名体制数字签名体制 l5.8 ElGamal5.8 ElGamal数字签名体制数字签名体制 l5.9 5.9 其它数字签名方案其它数字签名方案l5.10 5.10 数字签名标准数字签名标准l5.11 5.11 应用应用41第41页，共79页，编辑于2022年，星期二5.9.1 FiatShamir数字签名lFiat Shamir数字签名由数字签名由A.Fiat和和 A.Shamir提出，有时简记为提出，有时简记为FS数数
40、字签名。与字签名。与RSA数字签名相比较，数字签名相比较，FS数字签名的主要优势是速度快，数字签名的主要优势是速度快，它仅需要它仅需要RSA的的1%4%的模乘法。的模乘法。FS数字签名的理论基础是大整数数字签名的理论基础是大整数素因子分解的困难性。素因子分解的困难性。l1参数生成参数生成:选取两个大素数p、q，令n=pq。n是公开参数，p和q是管理中心CA掌握的密钥。设h是一个公开的Hash函数，k是一个固定的正整数。u管理中心CA为用户A产生k个公开密钥：yi(i=1,2,k)是模n的平方剩余u再为用户A产生k个私钥（保密）42第42页，共79页，编辑于2022年，星期二5.9.1 Fiat
41、Shamir数字签名l2.签名算法签名算法:为了对消息为了对消息m进行签名进行签名,用户用户A执行以下步骤执行以下步骤u（1）随机选取一个正整数t。u（2）在1和n之间随机选取t个正整数rj(j=1,2,t)，并计算u（3）计算Hash函数值h(m|R1|R2|Rt)，依次取出其前kt个比特值，记为 u（4）计算u用户A对消息m的数字签名为 签名者将数据（m，bij，sj）发送给接收者B 43第43页，共79页，编辑于2022年，星期二5.9.1 FiatShamir数字签名l3验证算法验证算法:接收方接收方B收到签名数据（收到签名数据（m,bij,sj）后）后,按以按以下步骤进行验证：下步骤
42、进行验证：u（1）利用A的公钥计算u（2）计算Hash函数值依次取出其前kt个比特值，记为u（3）比较等式 是否成立。如果kt个等式全部成立，则数字签名有效。否则，数字签名无效。44第44页，共79页，编辑于2022年，星期二5.9.1 FiatShamir数字签名l该验证算法的正确性该验证算法的正确性 当数据传输正确时，有45第45页，共79页，编辑于2022年，星期二5.9.1 FiatShamir数字签名l例例5.8 设n=35，k=4，用户A的4个公钥为：y1=4，y2=11，y3=16，y4=29。则A的4个私钥为：取t=1，r1=16，计算为了简化，设h(m|R1)=R1=11=1
43、011。即有 数字签名为（1,0,1,1,26）.46第46页，共79页，编辑于2022年，星期二5.9.1 FiatShamir数字签名l例例5.9 设n=35，k=4，用户A的4个公钥为：y1=4，y2=11，y3=16，y4=29。数字签名为（1,0,1,1,26）.所以数字签名有效。接收方验证方法如下。由于47第47页，共79页，编辑于2022年，星期二5.9.2 一次性数字签名l一次性签名方案是指一对公、私钥只能用于对一个消息进行签名一次性签名方案是指一对公、私钥只能用于对一个消息进行签名的方案，它通常被用于芯片卡（的方案，它通常被用于芯片卡（chipcards)。l1978年，年，
44、M.O.Rabin首次提出一次性签名方案。在首次提出一次性签名方案。在Rabin一一次性签名方案中，签名算法使用了对称加密算法，验证过次性签名方案中，签名算法使用了对称加密算法，验证过程需要验证者与签名者共同参与。程需要验证者与签名者共同参与。l1979年，年，L.Lamport提出一个类似的方案，不同之处在于验证时不提出一个类似的方案，不同之处在于验证时不需要验证者与签名者交互。该方案由于受到著名密码学家需要验证者与签名者交互。该方案由于受到著名密码学家Diffie和和Hellman的重视而有名。的重视而有名。l1992年，年，Bos与与Chaum对对Lamport的另一个更有效的一次性签的
45、另一个更有效的一次性签名方案做了本质的改进，并证明了改进的签名方案在选择消名方案做了本质的改进，并证明了改进的签名方案在选择消息攻击下是不可伪造的。息攻击下是不可伪造的。48第48页，共79页，编辑于2022年，星期二5.9.2 Lamport一次性数字签名 l(1)密钥生成：密钥生成：已知单向函数f：YZ。u在Y中随机选取 y1,0，y1,1，y2,0，y2,1，yk,0，yk,1 为私钥。u计算 zi,j=f(yi,j)（1ik，j=0,1），单向函数f及z1,0，z1,1，z2,0，z2,1，zk,0，zk,1为公钥。49第49页，共79页，编辑于2022年，星期二5.9.2 Lampo
46、rt一次性数字签名 l(2)签名算法签名算法 设消息x=(xk xk-1x2 x1)是二进制串，则对消息x的签名为：ui=yi,j|1ik,xi=j。l(3)验证算法验证算法 若 f(ui)|1ik包含在公钥中，则签名是合法的。50第50页，共79页，编辑于2022年，星期二5.9.2 Lamport一次性数字签名 l例例5.10 取素数p=7879，已知3是Z7879的本原元。定义f(x)=3x mod 7879，令k=3。取私钥：y1,0=5831,y1,1=735,y2,0=803,y2,1=2467,y3,0=4285,y3,1=6449.计算公钥为：z1,0=f(y1,0)=3583
47、1=2009 mod 7879,z1,1=3810,z2,0=4672,z2,1=4721,z3,0=268,z3,1=5731.u求消息x=011的签名。对于x3=0，由i=3，j=0，相应的签名为u3=y3,0=4285。同理，x2=1相应的签名为u2=y2,1=2467，x1=1相应的签名为u1=y1,1=735。所以，对消息x=011的签名为（4285，2467，735)。51第51页，共79页，编辑于2022年，星期二5.9.2 Lamport一次性数字签名 l例例5.11 取素数p=7879，已知3是Z7879的本原元。u接收方验证时计算：3735 mod 7879=3810,32
48、464 mod 7879=4721,34285 mod 7879=268.l对手虽然不能从zi,j求出yi,j，但是用这个签名方案对两个不同的消息签名时，对手就能伪造出另一些消息的签名。例如，在例6.5中，对手知道011和101的签名分别是（y3,0，y2,1，y1,1)和（y3,1，y2,0，y1,1)，显然（y3,1，y2,1，y1,1)和（y3,0，y2,0，y1,1)分别是111和001的签名。52第52页，共79页，编辑于2022年，星期二5.9.3 Bos-Chaum 一次性数字签名 lBos-Chaum一次性签名方案的签名比一次性签名方案的签名比Lamport方案的签名短。设方案
49、的签名短。设A=1，2，2n是是2n元集合，元集合，B是是A的所有的所有n元子集构成的集合，则有元子集构成的集合，则有|B|=C2nn。定义。定义Bos-Chaum签名方案使用的单射函数为：签名方案使用的单射函数为：0,1kB，它把长为它把长为k的字符串映射到的字符串映射到A的的n元子集，这里元子集，这里2k C2nn53第53页，共79页，编辑于2022年，星期二5.9.3 Bos-Chaum 一次性数字签名 l(1)密钥生成密钥生成 设 f：YZ是单向函数，取y1，y2，y2nY作为私钥，z1，z2，z2nZ作为公钥，其中f(yi)=zi(1i2n)。l(2)签名算法签名算法 设消息x=(
50、xkxk-1x2x1)2是二进制串，则对消息x的签名为：a1，a2，an=yj|j(x)。l(3)验证算法验证算法 计算集合C=f(ai),1in和(x)。如果C=zj|j(x)，则a1，a2，an是对x的合法签名。54第54页，共79页，编辑于2022年，星期二5.9.3 Bos-Chaum 一次性数字签名 l由于f是单向函数，对手不可能伪造消息的Bos-Chaum签名。如果使用Bos-Chaum方案签了两个消息，则对手容易伪造Bos-Chaum签名。例如，令n=4，容易计算出(110010)=2，4，6，8，(010011)=2，3，4，7。已知对110010的Bos-Chaum签名为y2