网络与信息安全数字签名精品文稿.ppt

网络与信息安全数字签名网络与信息安全数字签名1第1页，本讲稿共79页第第5 5章章 Hash函数与数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用2第2页，本讲稿共79页5.6 5.6 数字签名概念数字签名概念l在政治、军事、外交、商业和日常生活中，人们经常在政治、军事、外交、商业和日常生活中，人们经常需要对纸质材料进行签名。需要对纸质材料进行签名。l签名起到确认、核准、生效和负责任等多种作用。签名起到确认、核准、生效和负责任等多种作用。l随着计算机网络技术的发展，电子商务、电子政务和随着计算机网络技术的发展，电子商务、电子政务和电子金融等系统得到广泛应用，人们需要通过网络信电子金融等系统得到广泛应用，人们需要通过网络信息传输对电子的文件、契约、合同、信件和张单等进息传输对电子的文件、契约、合同、信件和张单等进行数字签名以替代手写签名。行数字签名以替代手写签名。3第3页，本讲稿共79页5.6 5.6 数字签名概念数字签名概念l签名是证明当事人的身份和数据真实性的一种信息。签名是证明当事人的身份和数据真实性的一种信息。l在传统的以书面文件为基础的事物处理中，采用书面在传统的以书面文件为基础的事物处理中，采用书面签名的形式，如手签、手印和印章等。书面签名得到签名的形式，如手签、手印和印章等。书面签名得到司法部门的支持，具有一定的法律意义司法部门的支持，具有一定的法律意义4第4页，本讲稿共79页5.6 5.6 数字签名概念数字签名概念l在以计算机文件为基础的现代事物处理中，应采用电在以计算机文件为基础的现代事物处理中，应采用电子形式的签名，即数字签名（子形式的签名，即数字签名（digital signature）。）。l数字签名的目的是提供一种手段，使得一个实体把他数字签名的目的是提供一种手段，使得一个实体把他的身份与某个信息捆绑在一起。的身份与某个信息捆绑在一起。l一个信息的数字签名实际上是一个数，它仅仅依赖于一个信息的数字签名实际上是一个数，它仅仅依赖于签名者的密钥和被签名的消息。签名者的密钥和被签名的消息。10011100010100011000sigK密钥K5第5页，本讲稿共79页5.6.1 数字签名的基本概念数字签名的基本概念u（1）消息空间:由所有任意长度消息组成的集合 u（2）签名空间:由所有签名组成的集合。签名长度不超过n。u（3）密钥空间:u（4）sigK称为签名算法（signing algorithm）l一个数字签名体制是一个满足以下条件的五元组:6第6页，本讲稿共79页5.6.1 数字签名的基本概念数字签名的基本概念u（5）verK称为验证算法（verification algorithm）u（6）u 则将数据对（x，y）称为消息x的一个数字签名，或直接把y称为消息x的数字签名7第7页，本讲稿共79页5.6.1 数字签名的基本概念数字签名的基本概念l数字签名基本要求u对每一个密钥K,sigK和verK应该是多项式时间函数uverK是公开的函数,而sigK是保密的 u给定一个消息x,除了发送者本人以外,任何其他人找到满足verK(x,y)为真的数字签名y,应该是计算上不可行的u如果攻击者能够找到满足verK(x,y)的数据对(x,y),而发送者事先又没有对x签名,则称y是伪造(forgery)的数字签名。l数字签名算法必须满足的条件u签名者事后不能否认自己的签名；u其他人不能伪造签名；u当通信双方为签名真伪发生争执时,可以由第三方解决争端8第8页，本讲稿共79页5.6.1 数字签名的基本概念数字签名的基本概念l手写签名与数字签名的区别u手写签名是所签文件的物理组成部分，数字签名必须与所签文件捆绑在一起。u手写签名通过与标准签名进行比较或检查笔迹来验证，数字签名是通过验证算法来验证。手写签名容易伪造，好的数字签名算法应该使伪造签名十分困难。u手写签名不易复制。数字签名是一个二进制串，容易复制。所以必须防止数字签名重复使用。9第9页，本讲稿共79页5.6.1 数字签名的基本概念数字签名的基本概念l签名算法进行分类u按应用目的p普通数字签名p特殊目的数字签名:不可否认数字签名、盲签名、群签名等u按验证方法p在验证时需要输入被签名信息p在验证时自动恢复被签名信息u按签名时是否使用随机数p分成确定性数字签名p随机数字签名10第10页，本讲稿共79页5.6.2 数字签名的基本构造方法数字签名的基本构造方法l利用Hash函数和加密算法可以构造有效的数字签名方案。l基于Hash函数和单钥密码算法构造数字签名 11第11页，本讲稿共79页5.6.2 数字签名的基本构造方法数字签名的基本构造方法l基于Hash函数和双钥密码算法构造数字签名12第12页，本讲稿共79页5.6.2 数字签名的基本构造方法数字签名的基本构造方法l具有保密作用的数字签名u双钥密码体制：SK是发送方的私钥，PK是发送方的公钥，E1和D1分别是加密算法与解密算法。u单钥密码体制密钥：K是双方公用密钥，E2和D2分别是对应的加密算法和解密算法。13第13页，本讲稿共79页 5.6.3 数字签名的安全需求数字签名的安全需求l数字签名的攻击模型数字签名的攻击模型u唯密钥攻击（唯密钥攻击（key only attack）攻击者攻击者E拥有签名者拥有签名者A的公钥的公钥K，因而能够计算验证函，因而能够计算验证函数数verK。u已知消息攻击（已知消息攻击（known message attack）攻击者攻击者E拥有一系列以前由签名者拥有一系列以前由签名者A所签名的消息。即所签名的消息。即E具有数据对（具有数据对（xi，yi），其中），其中xi是消息，是消息，yi=sigK(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页 5.6.3 数字签名的安全需求数字签名的安全需求l攻击者对数字签名系统的攻击目的u完全破译（total break）攻击者E能确定签名者A的私钥K，因而能够计算签名函数sigK，可以对任何消息产生有效的签名。u选择性伪造（selective forgery）攻击者E能以某一个不可忽略的概率对另外某个人选定的消息产生一个有效的签名。也就是说，如果给E选定一个消息x，那么他能以一个正的概率找到x的签名y=sigK(x)，并且签名者A以前未对x签名。u存在性伪造（existential forgery）攻击者E至少能够为一个消息产生一个有效的签名。也就是说，E可能生成一个数据对（x，y），其中x是消息，y=sigK(x)。签名者A以前未对x签名。15第15页，本讲稿共79页 5.6.3 数字签名的安全需求数字签名的安全需求lHash函数与数字签名的安全性u对消息的散列值签名16第16页，本讲稿共79页 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使用选择消息攻击的存在性伪造使用选择消息攻击的存在性伪造 攻击者攻击者E首先找到首先找到x x,使得使得h(x)=h(x).然后将消息然后将消息x发给签名发给签名者者A,并让并让A对消息的散列值对消息的散列值h(x)签名签名,从而得到从而得到y=sigK(h(x).所以所以E能够成功伪造签名能够成功伪造签名(x,y).为了阻止这种攻击为了阻止这种攻击,必须要求必须要求Hash函函数数h是强无碰撞的是强无碰撞的.17第17页，本讲稿共79页 5.6.3 数字签名的安全需求数字签名的安全需求u使用唯密钥攻击的存在性伪造 当签名算法遭到唯密钥攻击时,即攻击者E拥有签名者A的公钥K.E就可能对一个随机的散列值z伪造签名y=sigK(z).此时,如果Hash函数h不是单向的,则E可能找到一个消息x，使得z=h(x).所以E能够成功伪造一个签名(x,y).为了阻止这种攻击,必须要求Hash函数h是单向的.18第18页，本讲稿共79页第第5 5章章 HashHash函数与数字签名函数与数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用19第19页，本讲稿共79页 5.7 RSA数字签名体制数字签名体制l利用RSA加密算法构造的数字签名称为RAS数字签名体制。l5.7.1 RSA算法描述l1密钥生成算法u选取两个大素数p，q，计算 n=pq，(n)=(p 1)(q 1)。u任选整数e，满足：0 e(n)，且gcd(e,(n)=1。u用扩展Euclidean算法求e模(n)的逆d，即 ed=1 mod(n)。u签名者的公钥:n，e，私钥:p，q，d。20第20页，本讲稿共79页 5.7.1 RSA算法描述算法描述l2签名算法 设消息为x，则x的RAS签名是l3验证算法 当接收方收到签名（x，y）后，计算如果如果x=x，则，则y是是x的的RAS签名。签名。21第21页，本讲稿共79页5.7.2 RSA数字签名的安全性数字签名的安全性l1一般攻击u攻击方法:设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仔细设计数据格式p对数据的Hash值进行签名22第22页，本讲稿共79页5.7.2 RSA数字签名的安全性数字签名的安全性l2选择消息攻击u攻击方法:假设攻击者E想伪造消息x的签名，他容易找到两个数据x1和x2，使得 攻击者E设法让用户A分别对x1和x2 进行签名，得到 然后E可以计算 于是攻击者E得到了用户A对消息x的RSA数字签名yu抵抗措施p用户不要轻易地对其他人提供的随机数据进行签名p对数据的Hash值进行签名 23第23页，本讲稿共79页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 mod n.攻击者E再计算：于是，获得了秘文x。u抵抗措施p用户不要轻易地对其他人提供的随机数据进行签名p对数据的Hash值进行签名 24第24页，本讲稿共79页5.7.2 RSA数字签名的安全性数字签名的安全性l4对先加密后签名方案的攻击u攻击方法 假设签名者A采用先加密后签名的方案把消息x发送给接收者B,则他先用B的公开密钥eB对x加密,然后用自己的私钥dA签名.设A的模数为nA,B的模数为nB.于是A发送给B的数据为:如果B是不诚实的,那么B可能伪造A的签名.例如,假设B想抵赖收到A发的消息x,慌称收到的是x1.因为nB是B的模数,所以B知道nB的分解,于是能够计算模nB的离散对数.即他能找到k满足:然后，B再公布他的新公开密钥为keB。现在B宣布他收到的消息是x1，而不是x。由于下式成立，所以A无法争辩。25第25页，本讲稿共79页5.7.2 RSA数字签名的安全性数字签名的安全性l4对先加密后签名方案的攻击u抵抗措施p签名者A应当在发送的数据中加入时间戳，从而可证明是用公开密钥eB对x加密，而不是用新公开密钥keB对x1加密。p对数据的Hash值进行签名。l综上所述，对于RSA数字签名系统，必须采取如下安全措施：u不直接对消息进行签名，而应该对消息的Hash值进行签名。u要采用先签名后加密的方式，而不要采用先加密后签名的方式。26第26页，本讲稿共79页第第5 5章章 HashHash函数与数字签名函数与数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用27第27页，本讲稿共79页5.8 ElGamal5.8 ElGamal数字签名体制数字签名体制u在1985年，ElGamal T.提出了一个基于离散对数问题的数字签名体制，通常称为ElGamal数字签名体制。uElGamal签名体制的安全性主要是基于有限域上离散对数问题的难解性。28第28页，本讲稿共79页5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述l1参数生成算法参数生成算法u选取一个大素数选取一个大素数p，g Zp*是一个本原元，是一个本原元，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页5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述l3验证算法 接收方收到签名(M,(r,s)后，验证 是否成立，如果等号成立，则确认(r,s)是M的有效签名。l有效性证明 因此，如果（r，s）是M的正确签名，则一定有30第30页，本讲稿共79页5.8.1 ElGamal5.8.1 ElGamal签名算法描述签名算法描述lElGamal数字签名是一个随机的数字签名体制 l例5.6 设p=11，g=2是Z11*的本原元。选取私钥为x=8，u计算公钥 设签名者A要对消息M=5进行签名。签名者A首先秘密选取一个整数k=9，计算u签名者A对M=5的ElGamal签名为（6,3）。u接收者B可以对消息M=5的签名（6,3）进行验证。因为31第31页，本讲稿共79页5.8.25.8.2 ElGamal数字签名的安全性数字签名的安全性 lElGamal数字签名算法的实现u需要作一次模指数运算u一次扩展Euclidean算法运算（求随机数k的逆元）u二次模乘运算u前两个运算可以离线进行u是一个随机的数字签名体制 lElGamal数字签名体制的参数pup的选择与在Zp*中计算离散对数的算法有直接关系。从目前的计算水平来看，p至少应该是二进制512位的素数，从长期安全性考虑，应使用1024位或更长的素数。up1最好有大的素因子u私钥x最好是Zp*的素数阶子群的生成元。32第32页，本讲稿共79页5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击 假设攻击者E不知道私钥x，要想伪造消息M的签名(r,s),则E可能使用的攻击方式有：u(1)攻击者已知消息M,选择一个值r,再求另一个值s.此时,因为有 所以攻击者E必须计算离散对数。u(2)攻击者已知消息M,选择一个值s,再求另一个值r.此时,他必须从同余方程 中求出r。这是一个到目前为止还没有可行方法求解的方程，甚至也看不出它与离散对数问题有没有关系。33第33页，本讲稿共79页5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击 u(3)攻击者已知消息M，同时求(r,s).即他必须从同余方程 中同时求出(r,s)。现在人们对这个方程的认识几乎是一无所有，既没有人发现解这个问题的方法，也没有人能够证明不能解这个问题。u(4)攻击者选择数据对(r,s)，求消息M。此时必须计算离散对数34第34页，本讲稿共79页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，计算，计算 成立，所以(r,s)是消息M的有效签名 p该攻击方法属于存在性伪造。因此，在使用ElGamal数字签名方案时，不要直接对消息进行签名，而应该对消息的Hash值进行签名。35第35页，本讲稿共79页5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l1不知道私钥的攻击 u例5.7 设p=467，g=2是Z467*的本原元，签名者公钥y=132。攻击者选择整数i=99，j=179，计算所以（117，41）是消息M=331的有效签名。36第36页，本讲稿共79页5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l2已知消息攻击 u假设攻击者E知道(r,s)是消息M的签名,则E可利用它来伪造其它消息的签名.选择整数l,i,j,0l,i,j p2，gcd(lrjs,p1)=1,计算 可见(u,v)是消息W的有效签名。u该攻击方法属于存在性伪造u使用对消息的Hash值进行签名的方式,可以抵抗这类攻击.37第37页，本讲稿共79页5.8.35.8.3 ElGamal数字签名的安全性数字签名的安全性 l使用ElGamal数字签名方案的安全措施 u(1)不要泄露随机数ku(2)不要使用同一个随机数k给两个不同的消息签名 设（r，s）是消息M的签名，（u，v）是消息W的签名，使用的是同一个随机数k，则可求出私钥。38第38页，本讲稿共79页5.8.4 ElGamal签名体制的变形签名体制的变形lElGamal数字签名算法有多种变形u设大素数p是模数，g是一个模p的本原元，x为签名者的私钥，k为随机数，m为待签名的消息，（r，s）是对M的签名。签名值的分量r=gk mod p,分量s由签名算法确定。ElGamal数字签名各种变形的签名算法和验证算法见下表。39第39页，本讲稿共79页5.8.4 ElGamal签名体制签名体制的变形的变形40第40页，本讲稿共79页第第5 5章章 数字签名数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用41第41页，本讲稿共79页5.9.1 FiatShamir数字签名lFiat Shamir数字签名由数字签名由A.Fiat和和 A.Shamir提出，有时简提出，有时简记为记为FS数字签名。与数字签名。与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页5.9.1 FiatShamir数字签名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页5.9.1 FiatShamir数字签名l3验证算法:接收方B收到签名数据（m,bij,sj）后,按以下步骤进行验证：u（1）利用A的公钥计算u（2）计算Hash函数值依次取出其前kt个比特值，记为u（3）比较等式 是否成立。如果kt个等式全部成立，则数字签名有效。否则，数字签名无效。44第44页，本讲稿共79页5.9.1 FiatShamir数字签名l该验证算法的正确性 当数据传输正确时，有45第45页，本讲稿共79页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=1011。即有 数字签名为（1,0,1,1,26）.46第46页，本讲稿共79页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页5.9.2 一次性数字签名l一次性签名方案是指一对公、私钥只能用于对一个消息进行签名的方案，它通常被用于芯片卡（chipcards)。l1978年，M.O.Rabin首次提出一次性签名方案。在Rabin一次性签名方案中，签名算法使用了对称加密算法，验证过程需要验证者与签名者共同参与。l1979年，L.Lamport提出一个类似的方案，不同之处在于验证时不需要验证者与签名者交互。该方案由于受到著名密码学家Diffie和Hellman的重视而有名。l1992年，Bos与Chaum对Lamport的另一个更有效的一次性签名方案做了本质的改进，并证明了改进的签名方案在选择消息攻击下是不可伪造的。48第48页，本讲稿共79页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页5.9.2 Lamport一次性数字签名 l(2)签名算法签名算法 设消息x=(xk xk-1x2 x1)是二进制串，则对消息x的签名为：ui=yi,j|1ik,xi=j。l(3)验证算法 若 f(ui)|1ik包含在公钥中，则签名是合法的。50第50页，本讲稿共79页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)=35831=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页5.9.2 Lamport一次性数字签名 l例5.11 取素数p=7879，已知3是Z7879的本原元。u接收方验证时计算：3735 mod 7879=3810,32464 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页5.9.3 Bos-Chaum 一次性数字签名 lBos-Chaum一次性签名方案的签名比一次性签名方案的签名比Lamport方案的签名短。设方案的签名短。设A=1，2，2n是是2n元集合，元集合，B是是A的所有的所有n元子集构成的集合，则有元子集构成的集合，则有|B|=C2nn。定。定义义Bos-Chaum签名方案使用的单射函数为：签名方案使用的单射函数为：0,1kB，它把长为它把长为k的字符串映射到的字符串映射到A的的n元子集，这里元子集，这里2k C2nn53第53页，本讲稿共79页5.9.3 Bos-Chaum 一次性数字签名 l(1)密钥生成密钥生成 设 f：YZ是单向函数，取y1，y2，y2nY作为私钥，z1，z2，z2nZ作为公钥，其中f(yi)=zi(1i2n)。l(2)签名算法签名算法 设消息x=(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页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，y4，y6，y8，对010011的Bos-Chaum签名为y2，y3，y4，y7，容易得到对111100的Bos-Chaum签名为y2，y4，y7，y8。所以该签名方案是一次性签名方案。55第55页，本讲稿共79页56第56页，本讲稿共79页5.9.4 不可否认数字签名l(3)验证协议l 假设签名者假设签名者A想否认一个想否认一个“由签名生成算法构造出来的由签名生成算法构造出来的”合法签名，其方式有：合法签名，其方式有：拒绝参与验证协议；拒绝参与验证协议；错误错误地执行验证协议；地执行验证协议；即使验证协议成功，也断言签名是即使验证协议成功，也断言签名是伪造的。对于前者很明显，而后两种情况难以防范。使伪造的。对于前者很明显，而后两种情况难以防范。使用用“否认协议否认协议”（disavowal protocol）能够确定是签名者）能够确定是签名者A试图否认一个由签名算法得出的签名，还是签名本身是试图否认一个由签名算法得出的签名，还是签名本身是伪造的。否认协议由两遍验证协议组成。伪造的。否认协议由两遍验证协议组成。57第57页，本讲稿共79页5.9.4 不可否认数字签名l(4)否认协议 进行一致性检验，若C=C，则s是对m的伪造签名；若CC，则s是对m的合法签名，签名者试图否认.58第58页，本讲稿共79页5.9.4 不可否认数字签名l 否认协议的性质 u性质1 如果验证者和签名者都正确执行协议，则必有C=C，说明s是对m的伪造签名，即 u 性质2u 性质359第59页，本讲稿共79页5.9.5 盲签名 l 对于前面介绍的数字签名，签名者知道所签名的消息。但在数字现金、电子投票等应用领域，要求签名者不能知道所签名的消息。l签名者对所签署消息和对消息的签名都不可见的数字签名称为盲签名（blind signature）l盲签名由D.Chaum在1982年首次提出 60第60页，本讲稿共79页5.9.5 盲签名 l 盲签名过程 uA是消息m的拥有者,称为求签名者uB称为签名者 u盲签名需要两个基本构件：p1)求签名者A知道的盲化函数f 及脱盲函数g。f与g必须满足：g(SB(f(m)=SB(m)。p2)签名者B的数字签名方案SB。61第61页，本讲稿共79页5.9.5 盲签名 l 考虑盲签名在电子货币中的应用，例如顾客A得到银行B对钱款m的盲签名后，自己算出银行的真正签名SB(m)。在支付时提交出m和SB(m)，银行能验证SB(m)是否为m的合法签名，但不知道这是谁的一笔消费。从而使A保持匿名状态，即消费行为不受到监控。62第62页，本讲稿共79页5.9.5基于RSA公钥密码系统的Chaum盲签名lChaum提出的盲签名方案是基于提出的盲签名方案是基于RSA公钥密码系统的公钥密码系统的 l(1)密钥生成密钥生成:选取素数p、q，令nB=pq，1bB(nB)且gcd(bB,nB)=1，随机选取1aB(nB)使得aBbB1 mod (nB)。签名者B的公钥是（nB，bB），私钥是aB。63第63页，本讲稿共79页5.9.5基于RSA公钥密码系统的Chaum盲签名l(2)盲签名协议：设需签名的消息为m l(3)盲签名验证算法 64第64页，本讲稿共79页5.9.5基于离散对数问题的盲签名 l瑞士学者J.Lcamenisch,J.M.Pivetean提出了基于离散对数问题的盲签名 l(1)密钥生成:签名者选择两个大素数p，q，q|(p1)，在Zp*上离散对数问题是难解问题。a是Zp*的q阶元。选取私钥x，令y=ax mod p，（p，q，a，y）为公钥。65第65页，本讲稿共79页5.9.5基于离散对数问题的盲签名 l(2)盲签名协议：设A需签名的消息为m，盲签名由签名者B开始 l(3)盲签名验证算法 66第66页，本讲稿共79页第第5 5章章 数字签名数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用67第67页，本讲稿共79页5.10.1 美国数字签名标准l数字签名标准（DSS:Digital Signature Standard）由美国国家标准技术研究所（NIST）于1991年提出，并于1994年正式成为美国联邦信息处理标准（FIPS PUB186），这标志着数字签名已得到政府的支持。DSS使用的签名算法称为数字签名算法（DSA:Digital Signature Algorithm）。2000年1月美国政府将RSA和椭圆曲线密码引入数字签名标准DSS，进一步丰富了DSS的算法。目前，DSS的应用已十分广泛，并被多个国际标准化组织采纳作为标准。美国的一些州已经通过相关法律，正式承认数字签名的法律意义。这是数字签名得到法律支持的重要标志。68第68页，本讲稿共79页5.10.1 美国数字签名标准l(1)算法参数:DSA使用的参数如下 up，q，g是公开参数，可为一组用户公用ux和y分别为一个签名者的私钥和公钥，私钥x用于产生签名，必须保密 u所有这些参数可在一定时间内固定69第69页，本讲稿共79页5.10.1 美国数字签名标准l(2)签名算法：设SHA是一个安全hash函数 70第70页，本讲稿共79页5.10.1 美国数字签名标准l(3)验证算法71第71页，本讲稿共79页5.10.2 俄罗斯数字签名标准 l1994年俄罗斯颁布了自己的数字签名标准（GOST），1995年启用，官方称为GOST R34.1094。GOST算法使用的单向Hash函数H(x)是在分组密码算法GOSY 78147.89基础上建立的 l(1)算法参数:DSA使用的参数如下 72第72页，本讲稿共79页5.10.2 俄罗斯数字签名标准 l(2)签名算法：设要签名的消息为M，签名过程如下 73第73页，本讲稿共79页5.10.2 俄罗斯数字签名标准 l(3)验证算法：接收者收到（M，r，s）后，按以下步骤验证签名的有效性 74第74页，本讲稿共79页第第5 5章章 数字签名数字签名l5.6 数字签名概念l5.7 RSA数字签名体制 l5.8 ElGamal数字签名体制 l5.9 其它数字签名方案l5.10 数字签名标准l5.11 应用75第75页，本讲稿共79页5.11 应用l对于电子邮件的安全性，主要有两个要求：其一是确保只有收信人才能阅读信件内容；其二收信人能够判断信件确由发信人发送，而未被别人伪造、或篡改。l目前应用最多的安全电子邮件系统是PGP（pretty good privacy）。PGP是一种基于Internet的保密电子邮件软件系统，能提供邮件加密、数字签名、认证、数据压缩和密钥管理功能，它是由美国Phi Zimmermann开发的。由于PGP系统功能强大，使用方便，所以在Windows、Unix和Mashintosh平台上得到广泛应用。lPGP采用ZIP压缩算法对邮件数据进行压缩，采用IDEA对压缩后的数据进行加密，采用MD5对邮件数据进行散列处理，采用RSA对邮件数据的散列值进行数字签名，采用支持公钥证书的密钥管理，采用先签名后加密的数字签名方案 76第76页，本讲稿共79页5.11 应用lPGP发送数据的过程 uKd发送者的RSA私钥uK IDEA密钥uKe接收者的RSA公钥uBASE 64码制转换将8bit字节流变为ASCII码77第77页，本讲稿共79页5.11 应用lPGP发送数据的过程 u（1）对邮件数据M使用MD5进行散列处理，形成数据的摘要；u（2）用发送者的RSA私钥Kd对数据摘要进行数字签名，以确保真实性；u（3）将邮件数据与数字签名值链接，规定邮件数据在前，签名值在后；u（4）用ZIP对链接后的数据进行压缩，以便于存储与传输；u（5）用IDEA对压缩后的数据进行加密，以确保秘密性，密钥为K；u（6）用接收者的RSA公钥Ke加密IDEA的密钥K；u（7）将经IDEA加密的数据与经RSA加密的IDEA密钥链接，规定数据在前，密钥在后；u（8）将加密数据进行BASE 64码制转换，将8bit字节流变为ASCII码。因为许多EMail系统只支持ASCII码。78第78页，本讲稿共79页5.11 应用lPGP巧妙地将公钥密码RSA和单钥密码IDEA结合在一起，兼顾了安全性和效率。支持公钥证书的密钥管理使PGP系统更安全方便。PGP具有很好的灵活性，可支持IDEA、3DES等单钥密码体制，MD5、SHA等Hash函数，DiffeHellman等密钥协议。这些显著的技术特色使得PGP成为Internet环境最著名的保密电子邮件软件系统。lPGP采用1024位的RSA、128位的IDEA密钥、128位的MD5、DiffeHellman密钥协议、公钥证书，因此PGP是安全的。如果采用160位的SHA，将进一步提高PGP的安全性。79第79页，本讲稿共79页