《现代密码学》课件第7章.ppt

1、第7章 数字签名与签密 7.1 数字签名的基本概念 7.2 标准化的数字签名方案 7.3 代理签名 7.4 群签名 7.5 签密 7.6 广义签密 第第7章章 数字签名与签密数字签名与签密 第7章 数字签名与签密 7.1.1 数字签名的定义数字签名的定义1 基本描述基本描述数字签名也叫签名、数字签字、签字、数位签字。在密码学的不同场合中它有不同含义，可表示一种密码体制(Digital Signature)，也可表示一种密码操作(Sign)，还可表示签名操作所生成的数据(Signature)。标准的数字签名是一个两方协议，由签名者(发送者)和验证者(接收者)两方参与。签名者用自己的私钥对一则给定

2、消息签名，然后将签名连同消息发送给验证者，验证者通过公开的方式获得签名者的公钥，对所收到的签名和消息进行验证。在发生争执时，可以由一个公正的(可信的)第三方出面，通过双方认可的方式对签名的有效性进行仲裁。通常签名者是一个特定的用户，验证者往往是任意的用户，但在一些特殊签名方案中，验证者也是特定的用户，仲裁者一般是任意的用户。第7章 数字签名与签密 2 形式化的定义形式化的定义对于数字签名的定义，有各种各样的表达，但其实质是相同的。以下给出几种关于数字签名的定义。定义定义7-1 签名方案=(Gen，SIG，VER)由三个算法组成：密钥生成算法Gen为用户U产生密钥对，(SDKU，VEKU)Gen

3、(U，T)。其中，T为安全参数；SDK为私钥；VEK为公钥。签名算法SIG为概率算法，对于消息mM，sSIG(m，SDKS)，sS为数字签名。其中，M为消息空间；S为签名空间。第7章 数字签名与签密 验证算法VER为确定算法，对于数字签名s和消息m，TVER(s，m，VEKS)。其中，表示验证失败；T表示接受签名。定义定义7-2 数字签名方案包括三个主要过程：系统的初始化过程、签名产生过程和签名验证过程。第7章 数字签名与签密 1.系统的初始化过程系统的初始化过程此过程产生签名方案的基本参数(M，S，K，SIG，VER)。其中，M是消息集合；S是签名集合；K是密钥(公钥和私钥)集合；SIG是签

4、名算法集合；VER是签名验证算法集合。2.签名产生过程签名产生过程 对于密钥集合K，相应的签名算法为sigkSIG，sigk：MS，对任意的消息mM，有s=sigk(m)，从而sS为消息m的数字签名。此过程将(s，m)传送给签名验证者。3.签名验证过程签名验证过程 对于密钥集合K，存在签名验证算法verk:MSTrue，False，verk(x，y)=True当且仅当y=sigk(x)，否则verk(x，y)=False。第7章 数字签名与签密 7.1.2 对数字签名的攻击对数字签名的攻击要对一种密码体制的安全性进行分析，首先要明确“要保护什么，要防止什么”。对于数字签名来说，消息本身是公开的

5、，机密性对于攻击者来说是没有意义的，攻击者的目标就是要成功伪造(forge)合法的签名。所谓合法的签名，就是能够通过验证，并被签名验证者能够接受的签名。以下给出对数字签名的几种不同程度的攻击：(1)完全攻击(total break)：攻击者能够通过计算获得签名者的私钥，或者能够得到一个等价于合法签名算法的伪造签名算法。也就是说，攻击者对任意的消息均能伪造出合法签名。第7章 数字签名与签密(2)选择性伪造攻击(selective forgery)：攻击者能够对事先选定的一则消息或一组消息伪造出合法的签名。(3)存在性伪造攻击(existential forgery)：攻击者能够对至少一则消息伪造

6、出合法签名，而无法对任意选择的消息伪造签名。第7章 数字签名与签密 从攻击的途径来看，类似于对加密系统的攻击，攻击者可以有两种不同类型的攻击：(1)唯密钥攻击(key-only attacks)：攻击者在仅知道签名者公钥的情况下，对一个数字签名系统进行攻击。(2)消息攻击(message attacks)：攻击者在获得并分析与已知或选定消息相关的签名之后，对数字签名系统进行攻击。根据攻击者所获得消息的程度不同，消息攻击可以进一步分为如下三类：(a)已知消息攻击(known-message attack)：攻击者能够获得对一组已知消息的签名，但消息并不能由攻击者自己选择。第7章 数字签名与签密(

7、b)选择消息攻击(chosen-message attack)：攻击者在伪造签名之前，能够获得对一组给定消息的合法签名。消息是在产生签名之前就已经选定的，因此这种攻击是非适应性的。(c)适应性选择消息攻击(adaptive chosen-message attack)：签名者为攻击者提供预言机服务，攻击者可以询问与签名者公钥和事先已获得的签名或消息相关的签名。第7章 数字签名与签密 7.1.3 数字签名的安全性数字签名的安全性1 基本的安全属性基本的安全属性对于数字签名来说，最重要的安全性为不可伪造性。通常从数字签名的应用场合出发来考虑，如果数字签名能够实现身份认证和完整性验证的功能，那么应该

8、具备以下两个安全属性：(1)不可伪造性(Unforgeability)：适应性攻击者(adaptive attacker)想要冒充签名者生成一组合法签名在计算上是不可行的。第7章 数字签名与签密(2)不可否认性(Non-repudiation)：一个签名者想要否认他所产生的签名是不可行的，可以由一个可信的第三方来进行仲裁。这两个安全属性往往是相关的。可以这样认为，如果一个数字签名体制是不可伪造的，那么合法的签名只能由合法的签名者产生，因而签名者无法否认这则签名。因此，在很多情况下，讨论数字签名方案的安全性时只关注不可伪造性。常常认为，如果一个数字签名是不可伪造的，那么这个签名方案就是安全的。但

9、并不是不可否认性都可以由不可伪造性推出，例如一个签名算法可以同时产生两则可能的签名，即存在副本签名(duplicate signature)，那么仅凭借一则合法的签名就无法阻止签名者的抵赖。因此，直接从不可伪造性推出不可否认性是不充分的，不可否认性必须要通过另外的证明或分析过程来说明。第7章 数字签名与签密 2.安全性证明相关问题安全性证明相关问题在明确了一个数字签名体制至少要满足不可伪造性和不可否认性的安全属性之后，下一个问题就是如何证明这两个属性了。其实不可伪造性和不可否认性是根据经验得到的非形式化的安全性描述，对于严格的应用场合来说，仅仅通过分析来说明是很不充分的。关于数字签名安全性的证

10、明问题其实并不简单，往往比提出一个算法更加困难。在数字签名体制出现以后的很长时间内，对于如何证明一个算法并没有统一的标准和系统化的理论。第7章 数字签名与签密 大部分的方案的证明只是根据经验去分析，粗略地认为可以归约为某一个困难问题，但是否精确地可归约，或者在什么复杂度的算法时间内可归约，均没有好的理论结果。因此，这样的证明往往是不充分的。包括提出RSA体制的经典论文中，对其安全性的证明也是如此。因此，Wenbo Mao将这种安全性称为教科书式的安全概念。这样的算法并不能直接投入实际应用。对于数字签名的强安全性概念的开创性工作是由Goldwasser、Micali和Rivest完成的，现在的安

11、全性证明技术基本都是在他们提出的框架之下进行的。对于数字签名安全性更深入的讨论可参见第九章的相关内容和一些相关文献。第7章 数字签名与签密 7.2 标准化的数字签名方案标准化的数字签名方案数字签名的应用非常广泛，特别是随着通信技术、网络技术和应用的发展，数字签名成为实现安全通信和服务中必不可少的安全组件，因而标准化的数字签名算法也是工业应用中的重要问题。尽管已经提出的数字签名算法非常多，但由于安全性、效率等方面的因素，真正被广泛接受为标准的数字签名算法并不多，目前只有RSA和DSA一直是普遍采用的标准数字签名算法。随着计算技术的发展，效率更高的ECDSA数字签名算法正逐步成为第三个标准数字签名

12、算法。本节将介绍这三个标准的数字签名算法。第7章 数字签名与签密 7.2.1 RSA签名算法签名算法1.简介简介RSA是迄今为止最为成功的数字签名算法。作为标准数字签名算法，它是应用时间最长，也是接受范围最广的一个算法。RSA算法是由三位密码学家Revist、Shmir和Adleman于1978年设计的。该算法设计之精巧，安全性和效率之高，至今无人能够超越。RSA算法的高明之处在于它既是一个加密算法又是一个签名算法，加密(签名)和解密(验证)使用了完全相同的操作。三位密码学家因为这项卓越的工作，在2002年获得了计算机科学界的最高荣誉图灵奖。第7章 数字签名与签密 2.算法描述算法描述RSA签

13、名算法与RSA加密算法完全相同，由密钥生成算法、签名算法和验证算法三个部分组成。密钥生成算法假设Alice的公钥为(n;e)，私钥为d。(1)随机生成两个大素数p和q，要求大小大致相当。(2)计算n=pq及其Euler函数(n)=(p1)(q1)。(3)选择一个随机整数e，1e(n)，要求gcd(e;(n)=1。(4)计算整数d，1d(n)，要求ed1(mod(n)。第7章 数字签名与签密 签名算法签名者Alice对消息m签名，完成如下操作：(1)对原始消息进行适当变换，使得m0，n1。(2)计算s=md mod n。(3)输出s，作为Alice对消息m的签名。验证算法为验证Alice的签名，

14、并恢复出消息m，Bob完成如下操作：(1)获得Alice的公钥(n，e)。(2)计算m=se mod n。(3)验证，如果未通过，则认为签名是错误的。?m m第7章 数字签名与签密 3.安全性及相关问题安全性及相关问题众所周知，RSA的安全性基于大数分解问题的困难性。很显然，如果大合数N能够被成功分解，则RSA就被攻破，但攻破RSA的难度是否等价于分解N的难度呢？关于RSA算法的安全性问题，是密码学中一个长期研究的焦点。定义定义7-3 RSA问题(RSAP，RSA Problem)。给定一个由两个奇素数p和q相乘产生的正整数n，一个正整数e，满足gcd(e，(p1)(q1)=1，和一个正整数c

15、，能够计算出一个正整数m，使得mec(mod n)。RSA问题的实质是求解整数模n的e次根。当前，该问题是一个困难问题。关于RSA安全性更多的内容，目前已经发表了大量的研究论文。更深入的内容可参看相关的研究文献。第7章 数字签名与签密 7.2.2 DSA签名算法签名算法1.简介简介1991年，美国国家标准局NIST(National Institute of Standards and Technology)将数字签名算法DSA(Digital Signature Algorithm)作为其数字签名标准DSS(Digital Signature Standard)，该方案是特别为签名的目的而设

16、计的。在NIST的DSS标准中，使用了安全散列函数SHA-1。当任意长度小于264 bit的明文作为输入时，SHA-1都能产生160 bit的输出作为消息摘要，产生的消息摘要就可以作为DSA的输入，用来产生消息的签名或者验证签名。因为消息摘要一般要比原始明文小得多，所以对消息摘要进行签名能够提高效率。当然，在验证签名时必须使用与产生签名时相同的散列函数。第7章 数字签名与签密 2.算法描述算法描述参数设定及密钥生成参数设定及密钥生成p为素数，其中2L1p2L，512L1024，且L为64的倍数，即比特长度在5121024之间，长度增量为64 bit。q|(p1),其中2159q2160，g=h(p1)/q mod p，h是一整数，1h(p1)。用户私钥x为随机或伪随机整数，其中0 x1；群公钥Y=(n，e，G，g，a，)。*nZ第7章 数字签名与签密 2.产生群成员密钥和证书产生群成员密钥和证书当用户A要加入到群中时，他选择一私钥xR0,1,21，计算y=ax mod n和成员私钥z=gy。A传送y和z给群管理员，并证明他知道以a为底y的离散对数，群管理员在确认A知道该离散对数值后，发