第7章 数字签名与签密课件.ppt

《第7章 数字签名与签密课件.ppt》由会员分享，可在线阅读，更多相关《第7章 数字签名与签密课件.ppt（111页珍藏版）》请在三一办公上搜索。

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

2、的签名和消息进行验证。在发生争执时，可以由一个公正的(可信的)第三方出面，通过双方认可的方式对签名的有效性进行仲裁。通常签名者是一个特定的用户，验证者往往是任意的用户，但在一些特殊签名方案中，验证者也是特定的用户，仲裁者一般是任意的用户。,2 形式化的定义对于数字签名的定义，有各种各样的表达，但其实质是相同的。以下给出几种关于数字签名的定义。定义7-1 签名方案=(Gen，SIG，VER)由三个算法组成：密钥生成算法Gen为用户U产生密钥对，(SDKU，VEKU) Gen(U，T)。其中，T为安全参数；SDK为私钥；VEK为公钥。签名算法SIG为概率算法，对于消息mM，sSIG(m，SDKS)

3、，sS为数字签名。其中，M为消息空间；S为签名空间。,验证算法VER为确定算法，对于数字签名s和消息m，TVER(s，m，VEKS)。 其中，表示验证失败；T表示接受签名。定义7-2 数字签名方案包括三个主要过程：系统的初始化过程、签名产生过程和签名验证过程。,1. 系统的初始化过程此过程产生签名方案的基本参数(M，S，K，SIG，VER)。其中，M是消息集合；S是签名集合；K是密钥(公钥和私钥)集合；SIG是签名算法集合；VER是签名验证算法集合。2. 签名产生过程 对于密钥集合K，相应的签名算法为sigkSIG，sigk：MS，对任意的消息mM，有s=sigk(m)，从而sS为消息m的数字

4、签名。此过程将(s，m)传送给签名验证者。3. 签名验证过程 对于密钥集合K，存在签名验证算法verk:MSTrue，False，verk(x，y)=True当且仅当y=sigk(x)，否则verk(x，y)= False。,7.1.2 对数字签名的攻击要对一种密码体制的安全性进行分析，首先要明确“要保护什么，要防止什么”。对于数字签名来说，消息本身是公开的，机密性对于攻击者来说是没有意义的，攻击者的目标就是要成功伪造(forge)合法的签名。所谓合法的签名，就是能够通过验证，并被签名验证者能够接受的签名。以下给出对数字签名的几种不同程度的攻击：(1) 完全攻击(total break)：攻击

5、者能够通过计算获得签名者的私钥，或者能够得到一个等价于合法签名算法的伪造签名算法。也就是说，攻击者对任意的消息均能伪造出合法签名。,(2) 选择性伪造攻击(selective forgery)：攻击者能够对事先选定的一则消息或一组消息伪造出合法的签名。(3) 存在性伪造攻击(existential forgery)：攻击者能够对至少一则消息伪造出合法签名，而无法对任意选择的消息伪造签名。,从攻击的途径来看，类似于对加密系统的攻击，攻击者可以有两种不同类型的攻击：(1) 唯密钥攻击(key-only attacks)：攻击者在仅知道签名者公钥的情况下，对一个数字签名系统进行攻击。(2) 消息攻击

6、(message attacks)：攻击者在获得并分析与已知或选定消息相关的签名之后，对数字签名系统进行攻击。根据攻击者所获得消息的程度不同，消息攻击可以进一步分为如下三类：(a) 已知消息攻击(known-message attack)：攻击者能够获得对一组已知消息的签名，但消息并不能由攻击者自己选择。,(b) 选择消息攻击(chosen-message attack)：攻击者在伪造签名之前，能够获得对一组给定消息的合法签名。消息是在产生签名之前就已经选定的，因此这种攻击是非适应性的。(c) 适应性选择消息攻击(adaptive chosen-message attack)：签名者为攻击者提

7、供预言机服务，攻击者可以询问与签名者公钥和事先已获得的签名或消息相关的签名。,7.1.3 数字签名的安全性1 基本的安全属性对于数字签名来说，最重要的安全性为不可伪造性。通常从数字签名的应用场合出发来考虑，如果数字签名能够实现身份认证和完整性验证的功能，那么应该具备以下两个安全属性：(1) 不可伪造性(Unforgeability)：适应性攻击者(adaptive attacker)想要冒充签名者生成一组合法签名在计算上是不可行的。,(2) 不可否认性(Non-repudiation)：一个签名者想要否认他所产生的签名是不可行的，可以由一个可信的第三方来进行仲裁。这两个安全属性往往是相关的。可

8、以这样认为，如果一个数字签名体制是不可伪造的，那么合法的签名只能由合法的签名者产生，因而签名者无法否认这则签名。因此，在很多情况下，讨论数字签名方案的安全性时只关注不可伪造性。常常认为，如果一个数字签名是不可伪造的，那么这个签名方案就是安全的。但并不是不可否认性都可以由不可伪造性推出，例如一个签名算法可以同时产生两则可能的签名，即存在副本签名(duplicate signature)，那么仅凭借一则合法的签名就无法阻止签名者的抵赖。因此，直接从不可伪造性推出不可否认性是不充分的，不可否认性必须要通过另外的证明或分析过程来说明。,2. 安全性证明相关问题在明确了一个数字签名体制至少要满足不可伪造

9、性和不可否认性的安全属性之后，下一个问题就是如何证明这两个属性了。其实不可伪造性和不可否认性是根据经验得到的非形式化的安全性描述，对于严格的应用场合来说，仅仅通过分析来说明是很不充分的。关于数字签名安全性的证明问题其实并不简单，往往比提出一个算法更加困难。在数字签名体制出现以后的很长时间内，对于如何证明一个算法并没有统一的标准和系统化的理论。,大部分的方案的证明只是根据经验去分析，粗略地认为可以归约为某一个困难问题，但是否精确地可归约，或者在什么复杂度的算法时间内可归约，均没有好的理论结果。因此，这样的证明往往是不充分的。包括提出RSA体制的经典论文中，对其安全性的证明也是如此。因此，Wenb

10、o Mao将这种安全性称为教科书式的安全概念。这样的算法并不能直接投入实际应用。对于数字签名的强安全性概念的开创性工作是由Goldwasser、Micali和Rivest完成的，现在的安全性证明技术基本都是在他们提出的框架之下进行的。 对于数字签名安全性更深入的讨论可参见第九章的相关内容和一些相关文献。,7.2 标准化的数字签名方案数字签名的应用非常广泛，特别是随着通信技术、网络技术和应用的发展，数字签名成为实现安全通信和服务中必不可少的安全组件，因而标准化的数字签名算法也是工业应用中的重要问题。尽管已经提出的数字签名算法非常多，但由于安全性、效率等方面的因素，真正被广泛接受为标准的数字签名算

11、法并不多，目前只有RSA和DSA一直是普遍采用的标准数字签名算法。随着计算技术的发展，效率更高的ECDSA数字签名算法正逐步成为第三个标准数字签名算法。本节将介绍这三个标准的数字签名算法。,7.2.1 RSA签名算法1. 简介RSA是迄今为止最为成功的数字签名算法。作为标准数字签名算法，它是应用时间最长，也是接受范围最广的一个算法。RSA算法是由三位密码学家Revist、 Shmir和Adleman于1978年设计的。该算法设计之精巧，安全性和效率之高，至今无人能够超越。RSA算法的高明之处在于它既是一个加密算法又是一个签名算法，加密(签名)和解密(验证)使用了完全相同的操作。三位密码学家因为

12、这项卓越的工作，在2002年获得了计算机科学界的最高荣誉图灵奖。,2. 算法描述RSA签名算法与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)。,签名算法签名者Alice对消息m签名，完成如下操作：(1) 对原始消息进行适当变换，使得m0，n1。(2) 计算s=md m

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

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

15、为签名的目的而设计的。在NIST的DSS标准中，使用了安全散列函数SHA-1。当任意长度小于264 bit的明文作为输入时，SHA-1都能产生160 bit的输出作为消息摘要，产生的消息摘要就可以作为DSA的输入，用来产生消息的签名或者验证签名。因为消息摘要一般要比原始明文小得多，所以对消息摘要进行签名能够提高效率。当然，在验证签名时必须使用与产生签名时相同的散列函数。,2. 算法描述参数设定及密钥生成p为素数，其中2L1p2L，512L1024，且L为64的倍数，即比特长度在5121024之间，长度增量为64 bit。q|(p1),其中2159q2160，g=h(p1)/q mod p，h是

16、一整数，1h(p1)。用户私钥x为随机或伪随机整数，其中0 xq，公钥为y=gx mod p。签名算法(1) 选取一个随机整数k(1kp2)，k与p1互素。(2) 计算r=(gk mod p) mod q，s=k1(H(m)+xr) mod q，其中kk1 mod q1。(r，s)为对消息m的数字签名。,验证算法(1) 计算w=s1 mod q。(2) 计算u1=H(m)w mod q，u2=rw mod q，。检验v=r是否成立。,3.相关问题DSA是ElGamal数字签名的变形，也是离散对数型数字签名方案中最为著名的一个。在DSA作为美国国家标准之后，仍有许多批评，其中包括DSA的签名速度

17、要比验证速度快得多，也即DSA算法不是很实用。具体的原因是：消息往往只被签名一次，但要在相当长的时间内多次验证，而且签名往往是在计算能力比较强的环境中完成的，而验证却往往是在计算能力相当弱的终端上进行的，如Smart卡、PDA等。针对这一问题，出现了很多对DSA算法的改进，其中有不少就是将大规模的计算部件从验证算法移到签名算法中，将验证算法变成了一个轻量级的计算，从而使验证签名的算法更快。,DSA算法在发布之初将模数的规模固定为512位，这同样受到很多人的批评。原因是512位在当时是安全的，但以后并不见得安全。后来NIST对其进行了修订，使模数的大小可以调整，但应该是64位的整数倍。,7.2.

18、3 ECDSA签名算法1. 简介ECDSA(Elliptic Curve Digital Signature Algorithm)是于1992年由Scott Vanstone提交给NIST的数字签名标准候选算法。该算法借鉴了DSA的设计思想，但由于ECDLP(Elliptic Curve Discrete Logarithm Problem，椭圆曲线离散对数问题)本身的优势，因此ECDSA与DSA相比较具有更高的安全性。ECDSA是唯一被广泛接受的椭圆曲线数字签名算法，已被众多的标准化组织采纳：1998年被ISO (International Standards Organization)作为

19、ISO 14888-3；1999年被ANSI (American National Standards Institute)作为ANSI X9.62; 2000年被IEEE (Institute of Electrical and Electronics Engineers)作为IEEE 1363-2000 和FIPS标准(FIPS 186-2)。ECDSA是最有可能替代RSA和DSA成为下一代PKI(Public Key Infrastructure，公钥密码基础设施)签名标准的算法。本书按照SEC1标准对ECDSA算法进行描述。,2. 算法描述椭圆曲线相关参数说明有限域Fp上椭圆曲线E(F

20、p)的域参数为T=(p，a，b，G，n，h)其中，a，bFp满足方程y2x3+ax+b (mod p)；G=(xG，yG)为曲线上的基点，基点G的阶n为素数；h=#E(Fp)/n。O为无穷远点(有理点Abel群的0元)，nG=O，#E(Fp)为曲线的阶(曲线上有理点的个数)。,系统初始化U为签名方，V为验证方。(1) U建立椭圆曲线域参数T=(p，a，b，G，n，h)，选择适当的安全强度。(2) U建立自己的密钥对(dU，QU)，QU=dUG。(3) U选择一个哈希函数hash。(4) U通过可靠的方式将所选择的哈希函数和椭圆曲线域参数T传递给V。,签名算法(1) 选择临时密钥对 (k，R)。

21、其中，R=kG=(xR，yR)，与域参数T相关。(2) 令r=xR mod n，如果r=0，则返回1。(3) 计算待签消息的散列值h=hash(M)，将h转换成整数e。(4) 计算s=k1(e+rdU) mod n，如果s=0，则返回1。(5) 输出S=(r，s) 为数字签名。,验证算法验证方V验证从签名方U发来的数字签名是否正确，从而判断接收到的消息是否真实，或者对方是否为真实的实体。(1) 如果 r，s1，n1，则验证失败。(2) 计算待签名消息的散列值h=hash(M) ，将h转换成整数e。(3) 计算u1=es1 mod n，u2=rs1 mod n。(4) 计算R=(xR，yR)=u

22、1G+u2QU，如果R=O，则验证失败。(5) 令v=xR mod n，如果v=r，则验证成功，否则验证失败。,3. ECDSA的安全性如前所述，ECDSA是DSA算法在椭圆曲线上的模拟，那么是否意味着ECDSA和DSA的安全性就相同呢？长期以来，研究者只是粗略地认为ECDSA和DSA和安全性基本相同，但并没有给出精确的数学证明。如何精确刻画ECDSA的安全性是一个公开问题。近几年的一些研究发现，ECDSA和DSA的安全性并不相同。关于ECDSA安全性分析的大量工作是由D.Brown完成的7。,1) 不可伪造性(Unforgeability)ECDSA的最重要的安全性是不可伪造性。伪造者可以是

23、除签名者本人以外的任何人。攻击者要伪造签名，必须确定一对(r，s)，使得验证方程R=(xR，yR)=u1G+u2QU=es1G+rs1QU成立。 如果攻击者先确定一个r，则R相应地也被确定，验证方程可变形为sR=eG+rQU，要求解s属于典型的ECDLP。ECDSA的强可证明安全性主要是指抵抗选择消息攻击下的存在性伪造(existentially unforgeable against a chosen message attack)，这也是目前对数字签名的最强的安全性定义。其含义为：攻击者可以要求签名者为其所选择的任何消息(除要伪造签名的消息)提供签名服务，在此情况下仍不能伪造出针对任何消息

24、(除已经询问过的消息)的合法签名。Brown证明了ECDSA在以上意义下的安全性。,2) 不可否认性(Non-repudiation)不可否认性是指一个签名者不能否认自己的签名。不可否认性的对象是签名者本人。一般认为，不可伪造性蕴含不可否认性。如果其他人有可能伪造或者延展一则签名，则签名者完全可以否认，因为接收者没有足够的证据证明签名是来自签名者的。如果签名不可伪造，当接收者出示一则合法签名时，该签名只可能是签名者本人签发的，因此签名者无法否认。,2002年, J.Stern、D.Pointcheval、J.Malone-Lee等发现ECDSA签名能产生副本签名(duplicate signa

25、ture)，因此仅依靠不可伪造性来说明不可否认性是不充分的。由于椭圆曲线两个对称点的x坐标相同: R=(xR，yR)，R=(xR，yR)，因此，ECDSA中映射f：Rr不是一一映射，对三元组(m1，R，s)和(m2，R，s)能够得到相同的签名文本(r，s)。由于(m1，r，s)和(m2，r，s)都能通过验证，因此签名者可以用(m2，r，s)否认(m1，r，s)。,令m1，m2是两则不同的消息，有e1=hash(m1)，e2=hash(m2)。(r1，s1)为对m1的签名，有s1=k1(e1+r1dU) mod n。(r2，s2)为对m2的签名，有s2=k1(e2+r2dU) mod n。令r1

26、=r2=r，e2=e12rdU，就有s2=s1。对消息m2产生的签名称为副本签名。,e2=hash(m2)是个单向函数，签名者无法对消息m1计算出合适的m2，但如果签名者能够控制密钥生成过程，则他可以通过生成密钥来产生副本签名：当签名者对给定消息m1签名时，他可以随机选择一个副本消息m2，计算签名私钥dU=(e2+e1)/2r mod n，相应的公钥为QU=dUG。关于ECDSA的安全性的严格证明其实是很困难的，目前已经取得的结果也不是最后的结论，预期在将来会有进展。,7.3 代理签名在现实世界中，权力往往可以传递，某人可以全权或部分委托他人来代表自己行使权力，如委托他人代理自己签署文件，或将

27、自己的印章交给其他人。代理签名技术是一类能够实现权力传递的数字签名。代理签名是指签名者可以授权他人代理自己，由被指定的代理签名者代表原始签名者生成有效的签名。代理签名的概念在1996年由Mambo、Usuda 和Okamoto首先提出。由于代理签名技术有着重要的用途，因此引起了广大学者的关注，许多学者已在其概念的界定和实现理论与技术方面取得了许多重要成果。,7.3.1 代理签名的定义一个代理签名系统至少有几个参与者: 对他人进行授权的原始签名者、获得授权执行签名的一个或多个代理签名者、对签名进行验证的一个或多个验证者。代理签名有很多定义，以下是由伊丽江给出的一个定义。,定义7-4(代理签名)

28、一个数字签名体制(R，SK，PK，M，S，KeyGen，Sign，VER)，A、B为两个用户，他们的私钥、公钥分别是(xA ，yA )和(xB，yB)。如果有以下条件成立： (1) A利用他的私钥xA计算出一个数，并将秘密地交给B。 (2) 任何人(包括B)在试图求出xA时，不会对他有任何帮助。 (3) B可以用和xB生成一个新的签名密钥AB。 (4) 存在一个公开的验证算法VERABTrue, False，使得对任何sS和mM，都有VERAB(yA, s, m)=Trues=Sign(AB, m)。,(5) 任何人在试图求出xA、xB、和AB时，任何数字签名Sign(AB, m)都不会对他产

29、生帮助。那么我们就称用户A将他的(部分)数字签名权力委托给了用户B，并且称A为B的原始签名者 (Original Signer)，称B为A的代理签名者(Proxy Signer)，称为委托密钥(Delegating Key)，称AB为代理签名密钥(Proxy-signing Key)，称以AB作为签名密钥对消息mM生成的数字签名Sign(AB, m)为A的代理签名(Proxy Signature)。,以上定义中，R为随机参数空间，SK为私钥空间，PK为公开密钥空间，M为消息空间，S为签名空间，KeyGen：RSKPK为密钥生成算法，Sign：SKMS为签名生成算法，Ver：PKSMTrue，F

30、alse为签名验证算法。,7.3.2 代理签名的安全性质Mambo、Usuda 和Okamoto提出一个代理签名方案应满足如下六条性质：(1) 不可伪造性(unforgeability)，指除原始签名者外，只有获得授权代理签名者能够代表原始签名者进行签名。(2) 可验证性(verifiability)，指通过代理签名，验证者能够确定被签名的文件已经得到原始签名者的认可。(3) 不可否认性(undeniability)，指当代理签名者完成了一个有效的代替签名后，就不能向原始签名者否认他的有效签名。,(4) 可区分性(distinguishability)，指能够正确地区分代理签名和原始签名者的签

31、名。(5) 代理签名者的不符合性(proxy signers deviation)，指代理签名者必须创建一个能检测到是代理签名的有效代理签名。(6) 可识别性(identifiability)，指原始签名者能够通过代理签名确定代理签名者的身份。,一般认为代理签名应满足以下三个最基本的条件：(1) 验证者能够像验证原始签名者的签名那样来验证代理签名。(2) 能够容易地区分代理签名和原始签名。(3) 原始签名者对代理签名者所作的代理签名不可否认。,7.3.3 代理签名的分类代理签名目前还没有严格的分类。Mambo、Usuda 和Okamoto把代理签名分为三类：完全代理型签名、部分代理型签名和具有

32、证书的代理签名(或称授权型代理签名)。完全代理型签名(full delegation)，指原始签名者通过可靠途径直接把自己的签名密钥分发给代理签名者，代理签名者产生的签名与原始签名者所产生的签名完全相同。由于这种签名不具有可区分性，相应地也不具有可识别性和不可否认性，与代理签名基本要求不符，因此不能适用于许多应用场合。,部分代理型签名(partial delegation)，指原始签名者用自己的签名密钥生成代理签名密钥s，然后将代理签名密钥通过可靠途径分发给代理签名者，要求代理签名者不能由自己所获得的代理签名密钥推算出原始签名者的签名密钥。部分代理签名又可分为两种：代理非保护代理签名和代理保护

33、代理签名。代理非保护代理签名(proxy-unprotected proxy signature)指除原始签名者外，指定的代理签名者能够代替原始签名者产生有效代理签名。但是，没有指定为代理签名者的第三方不能产生有效代理签名。代理保护代理签名(proxy-protected proxy signature)指只有指定的代理签名者能够代替原始签名者产生有效代理签名。但是，原始签名者和第三方都不能产生有效代理签名。,在部分代理签名中，代理签名者以s为签名密钥，按普通的签名方案产生代理签名，可以使用修改的验证方程来验证代理签名的有效性。因为在验证方程中有原始签名者的公钥，所以验证者能够确信代理签名是经

34、原始签名者授权的。人们根据不同的需要提出了各种各样的部分代理签名。例如，门限代理签名、不可否认代理签名、多重代理签名、具有接收者的代理签名、具有时戳的代理签名和具有证书的部分代理签名，极大地丰富和发展了部分代理签名。,具有证书的代理签名(delegation by warrant)有两种类型：授权代理签名和持票代理签名。授权代理签名(delegate proxy)指原始签名者用他的签名密钥使用普通的签名方案签一个文件 (称某某为代理签名者)，然后，把产生的证书发给代理签名者。持票代理签名(bearer proxy) 指证书是由消息部分和原始签名者对新产生的公钥的签名组成，原始签名者把新产生的公

35、钥所对应的秘密钥以安全的方式发给代理签名者。根据不可否认性，代理签名又可分为强代理签名和弱代理签名。强代理签名是指一个代理签名不仅能够代表原始签名者的签名，也能代表代理签名者的签名；而弱代理签名是指一个代理签名只代表原始签名者的签名。,7.3.4 基于离散对数的代理签名Mambo等提出了一个基于离散对数的代理签名协议，直接使用该协议可以构造代理签名。1. 代理签名协议1委托过程(1) A选取一个随机数kRZq，并计算K=gk mod p；(2) A计算出=s+kK mod q，并将(，K)通过安全信道发送给B；,(3) B验证等式g=yAKK mod p是否成立，如果不成立，则B要求A重新执行

36、步骤(1)，或终止协议。代理签名的生成过程对某个消息m，B生成普通的数字签名s=Sign(，m，然后以(s，K)作为他代表A对消息m生成的数字签名，即代理签名。,代理签名的验证过程如果代理签名的收方收到了消息m和代理签名(s，K)，那么进行以下步骤来验证代理签名的有效性： (1) 计算出v=yAKK mod p； (2) 验证VER(yA, (s, K), m)=TrueVER(v, s, m)=True。,2. 代理签名协议2委托过程(1) A选取一个随机数kRZq，并计算K=gk mod p；(2) A计算杂凑值e=H(K)；(3) A计算=xAe+k mod q，并将(，K)通过安全信道

37、发送给B；(4) B计算杂凑值e=H(K)；(5) B验证等式g=yAKK mod p是否成立，如果不成立，则B要求A重新执行步骤(1)，或终止协议。,代理签名的生成过程对某个消息m，B生成普通的数字签名s=Sign(，m，然后以(s，K)作为他代表A对消息m生成的数字签名，即代理签名。代理签名的验证过程如果代理签名的收方收到了消息m和代理签名(s，K)，那么进行以下步骤来验证代理签名的有效性：(1) 计算e=H(K)；(2) 计算v=yAKK mod p；(3) 验证VER(yA, (s, K), m)=TrueVER(v, s, m)=True。,1991年，Chaum和Van Heyst

38、提出了群签名的概念，它是一种既具有匿名性又具有可跟踪性的数字签名技术。签名者能用自己持有的签名私钥代表群体进行签名，签名验证者可以用公开的群公钥验证签名的有效性，但无法知道真实的签名人。在必要时可由群管理员来揭示签名者的身份。群签名还具有消息无关性，在不揭示群签名的条件下，任何人均不能确定两个群签名是否为同一个群成员所签署。第一个群签名方案是于1991年由Chaum和Van Heyst提出的。1994年Chen和Pedersen又提出动态群签名，开始考虑动态群的问题，即群可以动态变化，新的成员可以加入进来。,7.4 群 签 名,但动态群签名又存在一个问题：群签名的长度和群公钥的长度与群中成员个

39、数有关，以及增加新成员需要重新分发成员私钥和改变群公钥。直到 1997年，Camenisch和Stadler首次提出了群公钥和群签名的长度与群成员个数无关的群签名方案，才使群签名技术走向实用。他们提出的群签名方案克服了之前方案中所存在的一些缺陷，但是该方案还是存在删除群中成员需要重新分发成员私钥和改变群公钥的不足。在后来，群签名的研究论文和新方案不断涌现，但是关于群签名安全性的系统描述工作始终没有完成。直到2003年，由Bellare、Micciancio和Warinschi给出了群签名有关概念的强定义，如匿名性、可追踪性等。在最近几年中，随着形式化安全证明理论和技术的发展，又出现了几个可证明

40、安全的群签名方案。,7.4.1 群签名的定义群签名是一种具有可撤销匿名性的数字签名。对于一个群签名，群体中的任何成员可以代表群体签署一则消息，验证者也可以检验消息是否来自一个群体，但无法确定是由哪个成员签名的。在必要时，可以由群管理员通过所掌握的信息来揭示签名成员的身份，而签名成员本身不能否认自己的签名。一个群签名方案一般包括一个群管理员和若干个群成员。群签名方案一般由如下几个算法构成： Setup(群建立算法)，产生群体公钥，群成员公钥和私钥，以及管理员打开签名的信息。, Sign(签名算法)，由群体中的某一成员完成对消息的签名。 Verify(验证算法)，对群签名进行验证。 Open(打开

41、算法)，输入群签名和打开私钥，可以揭示签名人的身份。在考虑动态群时，在群建立算法中还包括一个成员加入算法Join。 Join(成员加入算法)新成员与群管理员经过交互后，加入签名群。,7.4.2 群签名的安全性质一般来说，一个群签名方案的安全性质如下： 不可伪造性(Unforgeability)，在不知道签名者私钥的情况下，想要伪造一则合法的群签名是不可行的。 匿名性(Anonymity)，除群管理员之外，对于给定的一则合法签名，任何人想要确定签名者的身份是不可行的。 无关联性(Unlinkability)，在不打开签名时，任何人都无法确定两个不同的合法签名是否来自同一个群成员。, 可追踪性(T

42、raceability)，在必要时，群管理员能够打开签名以确定签名者的身份，而签名成员无法阻止。 抗陷害性(Exculpability)，包括群管理员在内的任何成员，都不能以其他成员的名义产生合法的群签名。 抗合谋攻击性(Coalition-Resistance)，即使多个不诚实的成员合谋也不能产生一个合法的群签名。,7.4.3 Camenisch-Stadler群签名Camenisch和Stadler于1997年首次提出了群公钥长度和群签名长度与群成员个数无关的群签名方案。该签名方案还有一个良好的性质，即新成员加入无需更改群公钥和原群成员的密钥。该方案是群签名发展过程中一个非常重要的成果。1

43、. 系统建立由群管理者计算下列值：一个RSA公钥(n，e)；一个阶为n的循环群G=g；选择一个元素aR，密钥长度的上界和一常量1；群公钥Y=(n，e，G，g，a，)。,2. 产生群成员密钥和证书当用户A要加入到群中时，他选择一私钥xR0, 1, , 21，计算y=ax mod n和成员私钥z=gy。A传送y和z给群管理员，并证明他知道以a为底y的离散对数，群管理员在确认A知道该离散对数值后，发放证书v=(y+1)1/emod n给A。,3. 产生群签名设m是待签名的消息，A代表群体执行下列操作产生群签名。选取，计算以及消息m的签名是，签名验证可使用对V1和V2的知识签名验证的方法。4. 打开签

44、名由于群管理员掌握了每个成员的y值，因此可以通过检验下面等式成立与否找出签名者:,7.4.4 ACJT群签名2000年, Ateniese、Camenisch、Joye和Tsudik提出了一个非常高效的群签名方案，它满足群签名的所有安全需求，并且其群公钥的尺寸和群体大小无关，且群公钥在群体生命周期里保持不变。该签名方案得到了密码学界的广泛关注，引发了对其安全性的讨论以及改进方案的研究，而且在此基础上已经构造了许多高效的协议。,参数描述GM为群管理员。设1，k和lp为安全参数，定义两个整数区间和。 这里，。1. 初始化(1) GM随机选择lp比特的素数p和q，使得p=2p+1, q=2q+1为素

45、数, 令n=pq；(2) GM随机选择a, a0, g, hRQR(n)；(3) GM随机选择xZpq，令y=gx mod n；(4) 群公钥为Y=(n, a, a0, y, g, h)；(5) GM的私钥为S=(p, q, x)。,2. 成员加入假定成员与GM间的通信是安全的，那么执行以下协议：(1) 成员Pi产生一个秘密值，一个随机整数，计算，把C1发送给GM，并证明C1的正确性。(2) GM检查C1QR(n)是否成立，若成立，则GM随机选择i, i0, 21，发送(i, i)给Pi。,(3) Pi计算，把发送给GM，Pi向GM证明：(a) C2对a的离散对数在内。(b) 知道u, v,

46、w使得: u在内; u等于对a的离散对数; 。,(4) GM检查C2QR(n)是否成立，如果成立且上述证明正确，则GM选择一个素数ei，计算，并给Pi发送成员证书Ai, ei。(5) Pi验证。,3. 群签名群成员执行以下操作：(1) 随机产生，计算 (2) 随机选择计算,(3) 计算 (4) 计算 (5) 输出。,4. 验证(1) 计算,(2) 计算 (3) 计算 (4) 当且仅当下列条件同时成立时签名正确。,5. 打开(1) 通过验证算法验证签名的有效性；(2) 通过自己的私钥，管理者可以计算，恢复Ai；(3) 证明。,7.5 签 密在许多应用场合中都需要同时满足机密性和完整性。传统的做法

47、是将加密和认证组合起来，但简单地组合不一定能够带来更高的安全性，往往会削弱原有的安全性。加密和认证可以有三种组合方式：认证再加密(AtE)、加密再认证(EtA)和加密且认证(E&A)。安全协议SSL、IPSec和SSH分别使用了这三种方式。在公钥密码领域中实现认证和加密的方法是数字签名和非对称加密。相应地，数字签名和非对称加密的组合也有三种方式，即签名再加密(StE)、加密再签名 (EtS)和签名且加密(S&E)。简单的EtS方式是不安全的，这是因为密文中包括了公钥，使得明文数据易被延展。,E&S方式由于签名泄露了明文的部分消息，因而也是不安全的。最常用的方法是StE，即在消息发出之前，发送者

48、首先对消息签名，然后用一个对称加密算法加密消息(包括签名)，最后再用接收者的公钥加密对称算法所使用的加密密钥。PGP加密软件、PEM协议都使用了这种方法。StE方式虽然有可能同时提供机密性和完整性，但在实际应用中仍存在一些问题：由于签密是加密和签名之和，因此会带来较大的计算负担，也会带来较大的数据膨胀，而且应用系统的设计者通常不是专业的密码学家，所设计的组合方式往往不安全。,Y.Zheng在1997年提出了一种新颖的密码体制签密(Signcryption)，其基本思想是在一个操作步骤内同时完成加密和签名双重功能，但计算复杂性和数据量远小于StE方式，同时给应用系统设计者提供一个安全的原子操作。

49、签密在出现后的短短几年中得到了很大的发展，其理论不断丰富和完善。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；,Malone-Lee和W.Mao在2003年提出具有IND-CCA2安全性的RSA型签密方案TBOS15；Malone-Lee在2002年16，Libert和Quisquater、X.Boyen在2003年，Liqun Chen和Malone-Lee在2004年分

50、别提出了基于身份的签密方案。D.J.Kwak和S.J.Moon在2003年提出了群签密，2004年W. Mao提出了可应用于一般加密和签名的可证明强安全的确定性签密方案。近几年，又有大量的新型签密方案被提出，公开发表的关于签密的研究论文超过百篇。,签密作为一种全新的密码体制，其应用前景十分广阔，标准化是一个急待解决的问题。 Y.Zheng已在2002年8月向IEEE提交报告，建议将签密作为P1363-3标准。目前，只有深入研究签密的概念、设计、安全性证明等一系列问题，才能迅速推动签密的标准化。不久将会有一个标准的签密算法应用在要求同时满足机密性和完整性的场合。,7.5.1 签密的定义签密是一种