第7章---数字签名与签密课件

单击此处编辑母版标题样式,第7章 数字签名与签密,7.1 数字签名的基本概念,7.2 标准化的数字签名方案,7.3 代理签名,7.4 群签名,7.5 签密,7.6 广义签密,第7章 数字签名与签密,7.1 数字签名的基本概念 7.2 标准化的数字,7.1.1 数字签名的定义,1 基本描述,数字签名也叫签名、数字签字、签字、数位签字。在密码学的不同场合中它有不同含义，可表示一种密码体制(Digital Signature)，也可表示一种密码操作(Sign)，还可表示签名操作所生成的数据(Signature)。,标准的数字签名是一个两方协议，由签名者(发送者)和验证者(接收者)两方参与。签名者用自己的私钥对一则给定消息签名，然后将签名连同消息发送给验证者，验证者通过公开的方式获得签名者的公钥，对所收到的签名和消息进行验证。在发生争执时，可以由一个公正的(可信的)第三方出面，通过双方认可的方式对签名的有效性进行仲裁。通常签名者是一个特定的用户，验证者往往是任意的用户，但在一些特殊签名方案中，验证者也是特定的用户，仲裁者一般是任意的用户。,7.1.1 数字签名的定义,2 形式化的定义,对于数字签名的定义，有各种各样的表达，但其实质是相同的。以下给出几种关于数字签名的定义。,定义7-1,签名方案=(Gen，SIG，VER)由三个算法组成：密钥生成算法Ge,n,为用户,U,产生密钥对，(,SDK,U,，,VE,K,U,) Gen(,U,，,T,)。其中，,T,为安全参数；,SDK,为私钥；,VE,K为公钥。签名算法SIG为概率算法，对于消息,m,M,，,s,SIG(,m,，,SDK,S,)，,s,S,为数字签名。其中，,M,为消息空间；,S,为签名空间。,2 形式化的定义对于数字签名的定义，有各种各样的,验证算法VER为确定算法，对于数字签名,s,和消息,m,，TVER(,s,，,m,，,VE,K,S,)。 其中，表示验证失败；T表示接受签名。,定义7-2,数字签名方案包括三个主要过程：系统的初始化过程、签名产生过程和签名验证过程。,验证算法VER为确定算法，对于数字签名s和消息m，,1. 系统的初始化过程,此过程产生签名方案的基本参数(,M,，,S,，,K,，SIG，VER)。其中，,M,是消息集合；,S,是签名集合；,K,是密钥(公钥和私钥)集合；SIG是签名算法集合；VER是签名验证算法集合。,2. 签名产生过程,对于密钥集合K，相应的签名算法为sig,k,SIG，sig,k,：,M,S,，对任意的消息,m,M,，有,s,=sig,k,(,m,)，从而,s,S,为消息,m,的数字签名。此过程将(,s,，,m,)传送给签名验证者。,3. 签名验证过程,对于密钥集合,K,，存在签名验证算法ver,k,:,M,S,True，False，ver,k,(,x,，,y,)=True当且仅当,y,=sig,k,(,x,)，否则ver,k,(,x,，,y,)= False。,1. 系统的初始化过程此过程产生签名方案的基本参数,7.1.2 对数字签名的攻击,要对一种密码体制的安全性进行分析，首先要明确“要保护什么，要防止什么”。对于数字签名来说，消息本身是公开的，机密性对于攻击者来说是没有意义的，攻击者的目标就是要成功伪造(,f,o,r,ge)合法的签名。所谓合法的签名，就是能够通过验证，并被签名验证者能够接受的签名。以下给出对数字签名的几种不同程度的攻击：(1) 完全攻击(total break)：攻击者能够通过计算获得签名者的私钥，或者能够得到一个等价于合法签名算法的伪造签名算法。也就是说，攻击者对任意的消息均能伪造出合法签名。,7.1.2 对数字签名的攻击要对一种密码体制的安全性,(2) 选择性伪造攻击(selective forgery)：攻击者能够对事先选定的一则消息或一组消息伪造出合法的签名。(3) 存在性伪造攻击(existential forgery)：攻击者能够对至少一则消息伪造出合法签名，而无法对任意选择的消息伪造签名。,(2) 选择性伪造攻击(selective forger,从攻击的途径来看，类似于对加密系统的攻击，攻击者可以有两种不同类型的攻击：(1) 唯密钥攻击(key-only attacks)：攻击者在仅知道签名者公钥的情况下，对一个数字签名系统进行攻击。(2) 消息攻击(message attacks)：攻击者在获得并分析与已知或选定消息相关的签名之后，对数字签名系统进行攻击。根据攻击者所获得消息的程度不同，消息攻击可以进一步分为如下三类：(a) 已知消息攻击(known-message attack)：攻击者能够获得对一组已知消息的签名，但消息并不能由攻击者自己选择。,从攻击的途径来看，类似于对加密系统的攻击，攻击者可以有两,(b) 选择消息攻击(chosen-message attack)：攻击者在伪造签名之前，能够获得对一组给定消息的合法签名。消息是在产生签名之前就已经选定的，因此这种攻击是非适应性的。(c) 适应性选择消息攻击(adaptive chosen-message attack)：签名者为攻击者提供预言机服务，攻击者可以询问与签名者公钥和事先已获得的签名或消息相关的签名。,(b) 选择消息攻击(chosen-message at,7.1.3 数字签名的安全性1 基本的安全属性,对于数字签名来说，最重要的安全性为不可伪造性。通常从数字签名的应用场合出发来考虑，如果数字签名能够实现身份认证和完整性验证的功能，那么应该具备以下两个安全属性：(1) 不可伪造性(Unforgeability)：适应性攻击者(adaptive attacker)想要冒充签名者生成一组合法签名在计算上是不可行的。,7.1.3 数字签名的安全性1 基本的安全属性,(2) 不可否认性(Non-repudiation)：一个签名者想要否认他所产生的签名是不可行的，可以由一个可信的第三方来进行仲裁。这两个安全属性往往是相关的。可以这样认为，如果一个数字签名体制是不可伪造的，那么合法的签名只能由合法的签名者产生，因而签名者无法否认这则签名。因此，在很多情况下，讨论数字签名方案的安全性时只关注不可伪造性。常常认为，如果一个数字签名是不可伪造的，那么这个签名方案就是安全的。但并不是不可否认性都可以由不可伪造性推出，例如一个签名算法可以同时产生两则可能的签名，即存在副本签名(duplicate signature)，那么仅凭借一则合法的签名就无法阻止签名者的抵赖。因此，直接从不可伪造性推出不可否认性是不充分的，不可否认性必须要通过另外的证明或分析过程来说明。,(2) 不可否认性(Non-repudiation)：一,2. 安全性证明相关问题,在明确了一个数字签名体制至少要满足不可伪造性和不可否认性的安全属性之后，下一个问题就是如何证明这两个属性了。其实不可伪造性和不可否认性是根据经验得到的非形式化的安全性描述，对于严格的应用场合来说，仅仅通过分析来说明是很不充分的。关于数字签名安全性的证明问题其实并不简单，往往比提出一个算法更加困难。在数字签名体制出现以后的很长时间内，对于如何证明一个算法并没有统一的标准和系统化的理论。,2. 安全性证明相关问题在明确了一个数字签名体制至,大部分的方案的证明只是根据经验去分析，粗略地认为可以归约为某一个困难问题，但是否精确地可归约，或者在什么复杂度的算法时间内可归约，均没有好的理论结果。因此，这样的证明往往是不充分的。包括提出RSA体制的经典论文中，对其安全性的证明也是如此。因此，Wenbo Mao将这种安全性称为教科书式的安全概念。这样的算法并不能直接投入实际应用。对于数字签名的强安全性概念的开创性工作是由Goldwasser、Micali和Rivest完成的，现在的安全性证明技术基本都是在他们提出的框架之下进行的。 对于数字签名安全性更深入的讨论可参见第九章的相关内容和一些相关文献。,大部分的方案的证明只是根据经验去分析，粗略地认为可以归约为某,7.2 标准化的数字签名方案,数字签名的应用非常广泛，特别是随着通信技术、网络技术和应用的发展，数字签名成为实现安全通信和服务中必不可少的安全组件，因而标准化的数字签名算法也是工业应用中的重要问题。尽管已经提出的数字签名算法非常多，但由于安全性、效率等方面的因素，真正被广泛接受为标准的数字签名算法并不多，目前只有RSA和DSA一直是普遍采用的标准数字签名算法。随着计算技术的发展，效率更高的ECDSA数字签名算法正逐步成为第三个标准数字签名算法。本节将介绍这三个标准的数字签名算法。,7.2 标准化的数字签名方案,7.2.1 RSA签名算法1. 简介,RSA是迄今为止最为成功的数字签名算法。作为标准数字签名算法，它是应用时间最长，也是接受范围最广的一个算法。RSA算法是由三位密码学家Revist、 Shmir和Adleman于1978年设计的。该算法设计之精巧，安全性和效率之高，至今无人能够超越。RSA算法的高明之处在于它既是一个加密算法又是一个签名算法，加密(签名)和解密(验证)使用了完全相同的操作。三位密码学家因为这项卓越的工作，在2002年获得了计算机科学界的最高荣誉图灵奖。,7.2.1 RSA签名算法1. 简介RSA是迄,2. 算法描述,RSA签名算法与RSA加密算法完全相同，由密钥生成算法、签名算法和验证算法三个部分组成。密钥生成算法假设Alice的公钥为(,n,;,e,)，私钥为,d,。(1) 随机生成两个大素数,p,和,q,，要求大小大致相当。(2) 计算,n,=,pq,及其Euler函数(,n,)=(,p,1)(,q,1)。(3) 选择一个随机整数e，1,e,(,n,)，要求gcd(e; (,n,)=1。(4) 计算整数,d,，1,d,(,n,)，要求,ed,1 (mod (,n,)。,2. 算法描述RSA签名算法与RSA加密算法完全相,签名算法签名者Al,ic,e对消息,m,签名，完成如下操作：(1) 对原始消息进行适当变换，使得,m,0，,n,1。(2) 计算,s,=,m,d,mod,n,。(3) 输出,s,，作为Alice对消息,m,的签名。验证算法为验证Alice的签名，并恢复出消息,m,，Bob完成如下操作：(1) 获得Alice的公钥(,n,，,e,)。(2) 计算,m,=,s,e,mod,n,。(3) 验证,，如果未通过，则认为签名是错误的。,签名算法签名者Alice对消息m签名，完成如下操作,3. 安全性及相关问题,众所周知，RSA的安全性基于大数分解问题的困难性。很显然，如果大合数N能够被成功分解，则RSA就被攻破，但攻破RSA的难度是否等价于分解N的难度呢？关于RSA算法的安全性问题，是密码学中一个长期研究的焦点。,定义7-3,RSA问题(RSAP，RSA Problem)。给定一个由两个奇素数p和q相乘产生的正整数,n,，一个正整数,e,，满足gcd(,e,，(,p,1)(,q,1)=1，和一个正整数,c,，能够计算出一个正整数,m,，使得,m,e,c,(mod,n,),。RSA问题的实质是求解整数模,n,的,e,次根。当前，该问题是一个困难问题。关于RSA安全性更多的内容，目前已经发表了大量的研究论文。更深入的内容可参看相关的研究文献。,3. 安全性及相关问题众所周知，RSA的安全性基于,7.2.2 DSA签名算法1. 简介,1991年，美国国家标准局NIST(National Institute of Standards and Technology)将数字签名算法DSA(Digital Signature Algorithm)作为其数字签名标准DSS(Digital Signature Standard)，该方案是特别为签名的目的而设计的。在NIST的DSS标准中，使用了安全散列函数SHA-1。当任意长度小于2,64,bit的明文作为输入时，SHA-1都能产生160 bit的输出作为消息摘要，产生的消息摘要就可以作为DSA的输入，用来产生消息的签名或者验证签名。因为消息摘要一般要比原始明文小得多，所以对消息摘要进行签名能够提高效率。当然，在验证签名时必须使用与产生签名时相同的散列函数。,7.2.2 DSA签名算法1. 简介1991年,2. 算法描述,参数设定及密钥生成,p,为素数，其中2,L,1,p,2,L,，512,L,1024，且,L,为64的倍数，即比特长度在5121024之间，长度增量为64 bit。,q,|(,p,1),其中2,159,q,2,160,，,g,=,h,(,p,1)/,q,mod,p,，,h,是一整数，1,h,(,p,1)。用户私钥,x,为随机或伪随机整数，其中0,x,1；群公钥,Y,=(,n,，,e,，,G,，,g,，a，,，,)。,7.4.3 Camenisch-Stadler群签名,2. 产生群成员密钥和证书,当用户A要加入到群中时，他选择一私钥,x,R,0, 1, , 2,1，计算,y,=,a,x,mod,n,和成员私钥,z,=,g,y,。A传送y和z给群管理员，并证明他知道以a为底y的离散对数，群管理员在确认A知道该离散对数值后，发放证书,v,=(,y,+1)1/,e,mod,n,给A。,2. 产生群成员密钥和证书当用户A要加入到群中时，,3. 产生群签名,设,m,是待签名的消息，A代表群体执行下列操作产生群签名。选取，计算以及消息,m,的签名是，签名验证可使用对,V,1,和,V,2,的知识签名验证的方法。,4. 打开签名,由于群管理员掌握了每个成员的,y,值，因此可以通过检验下面等式成立与否找出签名者:,3. 产生群签名设m是待签名的消息，A代表群体执行,7.4.4 ACJT群签名,2000年, Ateniese、Camenisch、Joye和Tsudik提出了一个非常高效的群签名方案，它满足群签名的所有安全需求，并且其群公钥的尺寸和群体大小无关，且群公钥在群体生命周期里保持不变。该签名方案得到了密码学界的广泛关注，引发了对其安全性的讨论以及改进方案的研究，而且在此基础上已经构造了许多高效的协议。,7.4.4 ACJT群签名2000年, Atenie,参数描述,GM为群管理员。设,1，,k,和,l,p,为安全参数，定义两个整数区间和。 这里，。,1. 初始化,(1) GM随机选择,l,p,比特的素数,p,和,q,，使得,p,=2,p,+1,q,=2,q,+1为素数, 令,n,=,pq,；(2) GM随机选择,a,a,0,g,h,R,QR,(,n,)；(3) GM随机选择,x,Z,p,q,，令,y,=g,x,mod,n,；(4) 群公钥为,Y,=(,n,a,a,0,y,g,h,)；(5) GM的私钥为,S,=(,p,q,x,)。,参数描述GM为群管理员。设1，k和lp为,2. 成员加入,假定成员与GM间的通信是安全的，那么执行以下协议：(1) 成员,P,i,产生一个秘密值，一个随机整数，计算，把,C,1,发送给GM，并证明,C,1,的正确性。(2) GM检查,C,1,QR,(,n,)是否成立，若成立，则GM随机选择,i,i,0, 2,1,，发送(,i,i,)给,P,i,。,2. 成员加入假定成员与GM间的通信是安全的，那么,(3),P,i,计算，把,发送给GM，,P,i,向GM证明：(,a,),C,2,对,a,的离散对数在内。(,b,) 知道,u,v,w,使得:,u,在内;,u,等于对,a,的离散对数;,。,(3) Pi计算，把,(4) GM检查,C,2,QR,(,n,)是否成立，如果成立且上述证明正确，则GM选择一个素数,e,i,，计算，并给,P,i,发送成员证书,A,i,e,i,。(5),P,i,验证,。,(4) GM检查C2QR(n)是否成立，如果成立且上述,3. 群签名,群成员执行以下操作：(1) 随机产生，计算 (2) 随机选择,计算,3. 群签名群成员执行以下操作：(1) 随机,(3) 计算,(4) 计算 (5) 输出。,(3) 计算 (4) 计算,4. 验证,(1) 计算,4. 验证(1) 计算,(2) 计算,(3) 计算,(4) 当且仅当下列条件同时成立时签名正确。,(2) 计算 (3) 计算,5. 打开,(1) 通过验证算法验证签名的有效性；(2) 通过自己的私钥，管理者可以计算,，恢复,A,i,；(3) 证明。,5. 打开(1) 通过验证算法验证签名的有效性；,7.5 签 密,在许多应用场合中都需要同时满足机密性和完整性。传统的做法是将加密和认证组合起来，但简单地组合不一定能够带来更高的安全性，往往会削弱原有的安全性。加密和认证可以有三种组合方式：认证再加密(AtE)、加密再认证(EtA)和加密且认证(E&A)。安全协议SSL、IPSec和SSH分别使用了这三种方式。在公钥密码领域中实现认证和加密的方法是数字签名和非对称加密。相应地，数字签名和非对称加密的组合也有三种方式，即签名再加密(StE)、加密再签名 (EtS)和签名且加密(S&E)。简单的EtS方式是不安全的，这是因为密文中包括了公钥，使得明文数据易被延展。,7.5 签 密,E&S方式由于签名泄露了明文的部分消息，因而也是不安全的。最常用的方法是StE，即在消息发出之前，发送者首先对消息签名，然后用一个对称加密算法加密消息(包括签名)，最后再用接收者的公钥加密对称算法所使用的加密密钥。PGP加密软件、PEM协议都使用了这种方法。StE方式虽然有可能同时提供机密性和完整性，但在实际应用中仍存在一些问题：由于签密是加密和签名之和，因此会带来较大的计算负担，也会带来较大的数据膨胀，而且应用系统的设计者通常不是专业的密码学家，所设计的组合方式往往不安全。,E&S方式由于签名泄露了明文的部分消息，因而也是不安全的,Y.Zheng在1997年提出了一种新颖的密码体制签密(Signcryption)，其基本思想是在一个操作步骤内同时完成加密和签名双重功能，但计算复杂性和数据量远小于StE方式，同时给应用系统设计者提供一个安全的原子操作。签密在出现后的短短几年中得到了很大的发展，其理论不断丰富和完善。Y.Zheng提出了第一个签密方案，F.Bao和R.H.Deng在1998年对其作了改进；D.H.Yum、P.J.Lee等提出了一个基于韩国数字签名标准KCDSA的签密；J.B.Shin、K.Lee和K.Shim提出了第一个基于数字签名标准DSA的签密算法SC-DSA；,Y.Zheng在1997年提出了一种新颖的密码体制签,Malone-Lee和W.Mao在2003年提出具有IND-CCA2安全性的RSA型签密方案TBOS,15,；Malone-Lee在2002年,16,，Libert和Quisquater、X.Boyen在2003年，Liqun Chen和Malone-Lee在2004年分别提出了基于身份的签密方案。D.J.Kwak和S.J.Moon在2003年提出了群签密，2004年W. Mao提出了可应用于一般加密和签名的可证明强安全的确定性签密方案。近几年，又有大量的新型签密方案被提出，公开发表的关于签密的研究论文超过百篇。,Malone-Lee和W.Mao在2003年提出具有IND-,签密作为一种全新的密码体制，其应用前景十分广阔，标准化是一个急待解决的问题。 Y.Zheng已在2002年8月向IEEE提交报告，建议将签密作为P1363-3标准。目前，只有深入研究签密的概念、设计、安全性证明等一系列问题，才能迅速推动签密的标准化。不久将会有一个标准的签密算法应用在要求同时满足机密性和完整性的场合。,签密作为一种全新的密码体制，其应用前景十分广阔，标准化是,7.5.1 签密的定义,签密是一种特殊的公钥密码方案，其实质是一个两方协议。执行协议的双方是签密方(发送方),S,和解签密方(接收方),R,。,S,对消息空间,M,中的一则消息,m,签密，产生签密文,，,R,解密出原始消息同时验证。类似于签名，发生争议时第三方可以进行仲裁。以下给出签密的有关定义。,7.5.1 签密的定义签密是一种特殊的公钥密码方案，,定义7-5,签密方案=(Gen，SC，DSC)由三个算法组成： 密钥生成算法Gen, 为用户U产生密钥对，(,SDK,U,，,VEK,U,)Gen(U，,T,)，,T,为安全参数，SDK为私钥，,VE,K为公钥。 签密算法SC, 为概率算法，对于消息,m,M,，,SC(,m,，,SDK,S,，,VEK,R,)，,为签密文。 解签密算法DSC, 为确定算法，对于签密文,，mDSC(,，,SDK,R,，,VEK,S,)，表示验证失败。,定义7-5 签密方案=(Gen，SC，DSC)由三个,定义7-6(正确性),签密方案=(Gen，SC，DSC)是正确的：,S,、,R,，,m,M,，DSC(SC(,m,，,SDK,S,，,VEK,R,)，,SDK,R,，,VEK,S,)=,m,。Zheng给出了签密的安全性概念。一个签密方案是安全的，如果满足如下安全属性： 不可伪造性(Unforgeability)，适应性攻击者(包括接收者)冒充发送方伪造一则签密文在计算上是不可行的。 不可否认性(Non-repudiation)，发送方想要否认他曾发出的签密文时，第三方进行仲裁在计算上是可行的。 机密