1、6.1 数字签名的基本原理 6.2 RSA数字签名*6.3 Rabin数字签名 6.4 ElGamal数字签名 6.5 数字签名标准DSS 6.6 不可否认的签名 习题 6.1 数字签名的基本原理数字签名的基本原理6.1.1 数字签名的基本概念数字签名的基本概念第4章讨论的Hash函数和消息认证码能够帮助合法通信的双方不受来自系统外部的第三方攻击和破坏，但却无法防止系统内通信双方之间的互相抵赖和欺骗。当Alice和Bob进行通信并使用消息认证码提供数据完整性保护，一方面Alice确实向Bob发送消息并附加了用双方共享密钥生成的消息认证码，但随后Alice否认曾经发送了这条消息，因为Bob完全有
2、能力生成同样的消息及消息认证码；另一方面，Bob也有能力伪造一个消息及消息认证码并声称此消息来自Alice。如果通信的过程没有第三方参与的话，这样的局面是难以仲裁的。因此，安全的通信仅有消息完整性认证是不够的，还需要有能够防止通信双方相互作弊的安全机制，数字签名技术正好能够满足这一需求。在人们的日常生活中，为了表达事件的真实性并使文件核准、生效，常常需要当事人在相关的纸质文件上手书签字或盖上表示自己身份的印章。在数字化和网络化的今天，大量的社会活动正在逐步实现电子化和无纸化，活动参与者主要是在计算机及其网络上执行活动过程，因而传统的手书签名和印章已经不能满足新形势下的需求，在这种背景下，以公钥
3、密码理论为支撑的数字签名技术应运而生。数字签名是对以数字形式存储的消息进行某种处理，产生一种类似于传统手书签名功效的信息处理过程。它通常将某个算法作用于需要签名的消息，生成一种带有操作者身份信息的编码。通常将执行数字签名的实体称为签名者，所使用的算法称为签名算法，签名操作生成的编码称为签名者对该消息的数字签名。消息连同其数字签名能够在网络上传输，可以通过一个验证算法来验证签名的真伪以及识别相应的签名者。类似于手书签名，数字签名至少应该满足三个基本要求：(1)签名者任何时候都无法否认自己曾经签发的数字签名；(2)收信者能够验证和确认收到的数字签名，但任何人都无法伪造别人的数字签名；(3)当各方对
4、数字签名的真伪产生争议时，通过仲裁机构(可信的第三方)进行裁决。数字签名与手书签名也存在许多差异，大体上可以概括为：(1)手书签名与被签文件在物理上是一个整体，不可分离；数字签名与被签名的消息是可以互相分离的比特串，因此需要通过某种方法将数字签名与对应的被签消息绑定在一起。(2)在验证签名时，手书签名是通过物理比对，即将需要验证的手书签名与一个已经被证实的手书签名副本进行比较，来判断其真伪。验证手书签名的操作也需要一定的技巧，甚至需要经过专门训练的人员和机构(如公安部门的笔迹鉴定中心)来执行。而数字签名却能够通过一个严密的验证算法准确地被验证，并且任何人都可以借助这个公开的验证算法来验证一个数
5、字签名的真伪。安全的数字签名方案还能够杜绝伪造数字签名的可能性。(3)手书签名是手写的，会因人而异，它的复制品很容易与原件区分开来，从而容易确认复制品是无效的；数字签名的拷贝与其原件是完全相同的二进制比特串，或者说是两个相同的数值，不能区分谁是原件，谁是复制品。因此，必须采取有效的措施来防止一个带有数字签名的消息被重复使用。比如，Alice向Bob签发了一个带有他的数字签名的数字支票，允许Bob从Alice的银行账户上支取一笔现金，那么这个数字支票必须是不能重复使用的，即Bob只能从Alice的账户上支取指定金额的现金一次，否则Alice的账户很快就会一无所有，这个结局是Alice不愿意看到的
6、。从上面的对比可以看出，数字签名必须能够实现与手书签名同等的甚至更强的功能。为了达到这个目的，签名者必须向验证者提供足够多的非保密信息，以便验证者能够确认签名者的数字签名；但签名者又不能泄露任何用于产生数字签名的机密信息，以防止他人伪造他的数字签名。因此，签名算法必须能够提供签名者用于签名的机密信息与验证者用于验证签名的公开信息，但二者的交叉不能太多，联系也不能太直观，从公开的验证信息不能轻易地推测出用于产生数字签名的机密信息。这是对签名算法的基本要求之一。一个数字签名体制一般包含两个组成部分，即签名算法(Signature Algorithm)和验证算法(Verificaton Algori
7、thm)。签名算法用于对消息产生数字签名，它通常受一个签名密钥的控制，签名算法或者签名密钥是保密的，由签名者掌握；验证算法用于对消息的数字签名进行验证，根据签名是否有效验证算法能够给出该签名为“真”或者“假”的结论。验证算法通常也受一个验证密钥的控制，但验证算法和验证密钥应当是公开的，以便需要验证签名的人能够方便地验证。数字签名体制(Signature Algorithm System)是一个满足下列条件的五元组(M，S，K，SIG，VER)，其中：(1)M代表消息空间，它是某个字母表中所有串的集合。(2)S代表签名空间，它是所有可能的数字签名构成的集合。(3)K代表密钥空间，它是所有可能的签
8、名密钥和验证密钥对(sk，vk)构成的集合。(4)SIG是签名算法，VER是验证算法。对于任意的一个密钥对(sk，vk)K，每一个消息mM和签名sS，签名变换SIG：MK|skS 和验证变换VER:MSK|vktrue，false是满足下列条件的函数：)(SIG )(SIG ),(msfalsemstruesmVERskskvk由上面的定义可以看出，数字签名算法与公钥加密算法在某些方面具有类似的性质，甚至在某些具体的签名体制中，二者的联系十分紧密，但是从根本上来讲，它们之间还是有本质的不同。比如对消息的加解密一般是一次性的，只要在消息解密之前是安全的就行了；而被签名的消息可能是一个具体法定效用
9、的文件，如合同等，很可能在消息被签名多年以后才需要验证它的数字签名，而且可能需要多次重复验证此签名。因此，签名的安全性和防伪造的要求应更高一些，而且要求签名验证速度比签名生成速度还要快一些，特别是联机的在线实时验证。6.1.2 数字签名的特性数字签名的特性综合数字签名应当满足的基本要求，数字签名应具备一些基本特性，这些特性可以分为功能特性和安全特性两大方面，分别描述如下。数字签名的功能特性是指为了使数字签名能够实现需要的功能要求而应具备的一些特性，这类特性主要如下：(1)依赖性。数字签名必须依赖于被签名消息的具体比特模式，不同的消息具有不同的比特模式，因而通过签名算法生成的数字签名也应当是互不
10、相同的。也就是说一个数字签名与被签消息是紧密相关、不可分割的，离开被签消息，签名不再具有任何效用。(2)独特性。数字签名必须是根据签名者拥有的独特信息来产生的，包含了能够代表签名者特有身份的关键信息。惟有这样，签名才不可伪造，也不能被签名者否认。(3)可验证性。数字签名必须是可验证的，通过验证算法能够确切地验证一个数字签名的真伪。(4)不可伪造性。伪造一个签名者的数字签名不仅在计算上不可行，而且希望通过重用或者拼接的方法伪造签名也是行不通的。比如希望把一个签名者在过去某个时间对一个消息的签名用来作为该签名者在另一时间对另一消息的签名，或者希望将签名者对多个消息的多个签名组合成对另一消息的签名，
11、都是不可行的。(5)可用性。数字签名的生成、验证和识别的处理过程必须相对简单，能够在普通的设备上快速完成，甚至可以在线处理，签名的结果可以存储和备份。除了上述功能特性之外，数字签名还应当具备一定的安全特性，以确保它提供的功能是安全的，能够满足安全需求，实现预期的安全保障。上面的不可伪造性也可以看做是安全特性的一个方面，除此之外，数字签名至少还应当具备如下安全特性：(1)单向性。类似于公钥加密算法，数字签名算法也应当是一个单向函数，即对于给定的数字签名算法，签名者使用自己的签名密钥sk对消息m进行数字签名是计算上容易的，但给定一个消息m和它的一个数字签名s，希望推导出签名者的签名密钥sk是计算上
12、不可行的。(2)无碰撞性。即对于任意两个不同的消息mm，它们在同一个签名密钥下的数字签名SIGsk(m)=SIGsk(m)相等的概率是可以忽略的。(3)无关性。即对于两个不同的消息mm，无论m与m存在什么样的内在联系，希望从某个签名者对其中一个消息的签名推导出对另一个消息的签名是不可能的。数字签名算法的这些安全特性从根本上消除了成功伪造数字签名的可能性，使一个签名者针对某个消息产生的数字签名与被签消息的搭配是惟一确定的，不可篡改，也不可伪造。生成数字签名的惟一途径是将签名算法和签名密钥作用于被签消息，除此之外别无它法。6.1.3 数字签名的实现方法数字签名的实现方法现在的数字签名方案大多是基于
13、某个公钥密码算法构造出来的。这是因为在公钥密码体制里，每一个合法实体都有一个专用的公私钥对，其中的公开密钥是对外公开的，可以通过一定的途径去查询；而私有密钥是对外保密的，只有拥有者自己知晓，可以通过公开密钥验证其真实性，因此私有密钥与其持有人的身份一一对应，可以看做是其持有人的一种身份标识。恰当地应用发送方私有密钥对消息进行处理，可以使接收方能够确信收到的消息确实来自其声称的发送者，同时发送者也不能对自己发出的消息予以否认，即实现了消息认证和数字签名的功能。图6-1给出公钥算法用于消息认证和数字签名的基本原理。图6-1 基于公钥密码的数字签名体制在图6-1中，发送方Alice用自己的私有密钥s
14、kA加密消息m，任何人都可以轻易获得Alice的公开秘密pkA，然后解开密文c，因此这里的消息加密起不了信息保密的作用。可以从另一个角度来认识这种不保密的私钥加密，由于用私钥产生的密文只能由对应的公钥来解密，根据公私钥一一对应的性质，别人不可能知道Alice的私钥，如果接收方Bob能够用Alice的公钥正确地还原明文，表明这个密文一定是Alice用自己的私钥生成的，因此Bob可以确信收到的消息确实来自Alice，同时Alice也不能否认这个消息是自己发送的；另一方面，在不知道发送者私钥的情况下不可能篡改消息的内容，因此接收者还可以确信收到的消息在传输过程中没有被篡改，是完整的。也就是说，图6-
15、1表示的这种公钥算法使用方式不仅能够证实消息来源和发送者身份的真实性，还能保证消息的完整性，即实现了前面所说的数字签名和消息认证的效果。在上述认证方案中，虽然传送的消息不能被篡改，但却很容易被窃听，因为任何人都可以轻易取得发送者的公钥来解密消息。为了同时实现保密和认证的能力，可以将发送方的私钥加密和接收方的公钥加密结合起来，进行双重加/解密，如图6-2所示。在图6-2中，发送方Alice先用自己的私钥skA加密待发送消息，对消息做签名处理，然后再用对方Bob的公钥pkB对签名后的消息加密，以达到保密的目的；接收方Bob收到消息后先用自己的私钥skB解密消息，再用对方Alice的公钥pkA验证签
16、名，只有签名通过验证的消息，接收者才会接受，其中 。)()(),(mEEzEcmEzABBAskpkpksk图6-2 基于公钥密码的加密和签名体制也许有人会想象改变图6-2中发送方Alice对消息双重加密的顺序,即先使用Bob的公钥pkB加密，再使用Alice的私钥skA签名，然后将收信方Bob解密的顺序也做相应修改。这样做，似乎同样可以实现消息的保密性和认证性，但是如果真的按这样的顺序来处理的话，可能会有很大的安全隐患。这是因为在这种先加密后签名的方案中，发信方产生的密文，也就是在信道上传输的密文是，任何人(不妨说是Oscar)都可以用Alice的公钥pkA来解密c得到，然后再用自己的私钥s
17、kX来加密产生 ，并仍然发送给Bob，那么Bob就会以为他收到的消息来自Oscar(而不是Alice)，接下来Bob就会将原本要发送给Alice的消息转而发送给Oscar。)(mEEcBApksk)(mEBpk)(mEBpk)(mEEBXpksk也就是说，这种先加密后签名的方案允许任何用户Oscar伪装成合法用户Alice，并假冒Alice行事。这是一个很大的安全漏洞，因此不能简单地采用这样的处理顺序。当然，这样的处理顺序也有一个优点，那就是如果接收方发现收到的消息不能通过签名验证，就不用再对其解密了，因而减少了运算量，但这点优势明显抵不上它的安全隐患。在实际应用中，对消息进行数字签名，可以选
18、择对分组后的原始消息直接签名，但考虑到原始消息一般都比较长，可能以千比特为单位，而公钥算法的运行速度却相对较低，因此通常先让原始消息经过Hash函数处理，再签名所得到的Hash码(即消息摘要)。在验证数字签名时，也是针对Hash码来进行的。通常，验证者先对收到的消息重新计算它的Hash码，然后用签名验证密钥解密收到的数字签名，再将解密的结果与重新计算的Hash码比较，以确定签名的真伪。显然，当且仅当签名解密的结果与重新计算的Hash码完全相同时，签名为真。一个消息的Hash码通常只有几十到几百比特，例如SHA-1能对任何长度的消息进行Hash处理，得到160比特的消息摘要。因此，经过Hash处
19、理后再对消息摘要签名能大大地提高签名和验证的效率，而且Hash函数的运行速度一般都很快，两次Hash处理的开销对系统影响不大。数字签名的实现方法如图6-3所示。图6-3 数字签名的实现方法经过学者们长期持续不懈的努力，大量的数字签名方案相继被提出，它们大体上可以分成两大类方案，即直接数字签名体制和需要仲裁的数字签名体制。1.直接数字签名体制直接数字签名体制直接数字签名仅涉及通信双方，它假定接收方Bob知道发送方Alice的公开密钥，在发送消息之前，发送方使用自己的私有密钥作为加密密钥对需要签名的消息进行加密处理，产生的密文就可以当作发送者对所发送消息的数字签名。但是由于要发送的消息一般都比较长
20、，直接对原始消息进行签名的成本以及相应的验证成本都比较高且速度慢，因此发送者常常先对需要签名的消息进行Hash处理，然后再用私有密钥对所得的Hash码进行上述的签名处理，所得结果作为对被发送消息的数字签名。显然这里用私有密钥对被发送消息或者它的Hash码进行加密变换，其结果并没有保密作用，因为相应的公开密钥众所周知，任何人都可以轻而易举地恢复原来的明文消息，这样做的目的只是为了数字签名。虽然上述直接数字签名体制的思想简单可行，且易于实现，但它也存在一个明显的弱点，即直接数字签名方案的有效性严格依赖于签名者私有密钥的安全性。一方面，如果一个用户的私有密钥不慎泄密，那么在该用户发现他的私有密钥已泄
21、密并采取补救措施之前，必然会遭受其数字签名有可能被伪造的威胁。更进一步，即使该用户发现自己的私有密钥已经泄密并采取了适当的补救措施，但仍然可以伪造其更早时间(实施补救措施之前)的数字签名，这可以通过对数字签名附加一个较早的时间戳(实施补救措施之前的任何时刻均可)来实现。另一方面，如果因为某种原因签名者在签名后想否认他曾经对某个消息签过名，他可以故意声称他的私有密钥早已泄密，并被盗用来伪造了该签名。方案本身无力阻止这种情况的发生，因此在直接数字签名方案中，签名者有作弊的机会。2.可仲裁的数字签名体制可仲裁的数字签名体制为了解决直接数字签名体制存在的问题，可以引入一个可信的第三方作为数字签名系统的
22、仲裁者。每次需要对消息进行签名时，发信者先对消息执行数字签名操作，然后将生成的数字签名连同被签消息一起发送给仲裁者；仲裁者对消息及其签名进行验证，通过仲裁者验证的数字签名被签发一个证据来证明它的真实性；最后消息、数字签名以及签名真实性证据一起被发送给接收者。在这样的方案中，发信者无法对自己签名的消息予以否认，而且即使一个用户的签名密钥泄密也不可能伪造该签名密钥泄密之前的数字签名，因为这样的伪造签名不可能通过仲裁者的验证。然而正所谓有得必有失，这种可仲裁的数字签名体制比那种直接的数字签名体制更加复杂，仲裁者有可能成为系统性能的瓶颈，而且仲裁者必须是公正可信的中立者。下面介绍几种数字签名体制。6.
23、2 RSA数字签名数字签名6.2.1 RSA数字签名算法数字签名算法RSA数字签名算法系统参数的选择与RSA公钥密码体制基本一样，首先要选取两个不同的大素数p和q，计算n=pq;再选取一个与(n)互素的正整数e，并计算出d满足ed=1 mod(n)，即d是e模(n)的逆;最后，公开n和e作为签名验证密钥，秘密保存p、q和d作为签名密钥。RSA数字签名体制的消息空间和签名空间都是Zn，分别对应于RSA公钥密码体制的明文空间和密文空间，而密钥空间为K=n，p，q，e，d，与RSA公钥密码体制相同。当需要对一个消息mZn进行签名时，签名者计算s=SIGsk(m)=md mod n得到的结果s就是签名
24、者对消息m的数字签名。验证签名时，验证者通过下式判定签名的真伪：VERvk(m，s)=truemse mod n这是因为，类似于RSA公钥密码体制的解密变换，有se mod n=(md)e mod n=medmod nm 可见，RSA数字签名的处理方法与RSA加解密的处理方法基本一样，不同之处在于，签名时签名者要用自己的私有密钥对消息“加密”，而验证签名时验证者要使用签名者的公钥对签名者的数字签名“解密”。RSA数字签名有效性的验证正好可以通过5.3节中RSA解密算法的正确性得到证实。6.2.2 RSA数字签名算法的安全问题数字签名算法的安全问题RSA数字签名算法是依据数字签名方式运用RSA公
25、钥密码算法产生的，在5.3.2节中已经讨论了RSA算法安全性的一些问题，并在5.3.3节中对如何更安全地选择RSA算法的参数给出了一些建议，这些讨论和建议对于RSA算法用于数字签名同样有效。对RSA数字签名算法进行选择密文攻击可以实现三个目的，即消息破译、骗取仲裁签名和骗取用户签名，简述如下：(1)消息破译。攻击者对通信过程进行监听，并设法成功收集到使用某个合法用户公钥e加密的密文c。攻击者想恢复明文消息m，即找出满足c=me mod n的消息m，可以按如下方法进行处理：第一步，攻击者随机选取rn且gcd(r，n)=1，计算三个值：u=re mod n，y=uc mod n，t=r-1mod
26、n第二步，攻击者请求合法用户用其私钥d对消息y签名，得到s=yd mod n。第三步，由u=re mod n可知r=ud mod n，所以t=r-1 mod n=u-dmod n。因此，攻击者容易计算出ts mod n=u-dyd mod n=u-dudcd mod n=cd mod n=medmod n=m即得到了原始的明文消息。(2)骗取仲裁签名。仲裁签名是仲裁方(即公证人)用自己的私钥对需要仲裁的消息进行签名，起到仲裁的作用。如果攻击者有一个消息需要仲裁签名，但由于公证人怀疑消息中包含不真实的成分而不愿意为其签名，那么攻击者可以按下述方法骗取仲裁签名。假设攻击者希望签名的消息为m，那么他
27、随机选取一个值x，并用仲裁者的公钥e计算y=xe mod n。再令M=my mod n，并将M发送给仲裁者要求仲裁签名。仲裁者回送仲裁签名Md mod n，攻击者即可计算(Md mod n)x-1mod n=mdydx-1mod n=mdxedx-1mod n=md mod n立即得到消息m的仲裁签名。(3)骗取用户签名。这实际上是指攻击者可以伪造合法用户对消息的签名。比如说如果攻击者能够获得某合法用户对两个消息m1和m2的签名和，那么他马上就可以伪造出该用户对新消息m3=m1m2的签名。因此，当攻击者希望某合法用户对一个消息m进行签名但该签名者可能不愿意为其签名时，可以将m分解成两个(或多个
28、)更能迷惑合法用户的消息m1和m2，且满足m=m1m2，然后让合法用户对m1和m2分别签名，攻击者最终获得该合法用户对消息m的签名。nmdmod1nmdmod2nmmnmdddmodmod213容易看出，上述选择密文攻击都是利用了指数运算能够保持输入的乘积结构这一缺陷(称为可乘性)。因此一定要记住，任何时候都不能对陌生人提交的消息直接签名，最好先经过某种处理，比如先用单向Hash函数对消息进行Hash运算，再对运算结果签名。以上这些攻击方法都是利用了模幂运算本身具有的数学特性来实施的。还有一种类似的构成RSA数字签名体制安全威胁的攻击方法，这种方法使任何人都可以伪造某个合法用户的数字签名，方法
29、如下：伪造者Oscar选取一个消息y，并取得某合法用户(被伪造者)的RSA公钥(n，e)，然后计算x=ye mod n，最后伪造者声称y是该合法用户对消息x的RSA签名，达到了假冒该合法用户的目的。这是因为，该合法用户用自己的私钥d对消息x合法签名的结果正好就是y，即SIGsk(x)=xd mod n=(ye)d mod n=yed mod ny因此从算法本身不能识别伪造者的假冒行为。如果伪造者精心挑选y，使x具有明确的意义，那么造成的危害将是巨大的。*6.3 Rabin数字签名数字签名Rabin数字签名体制利用Rabin公钥密码算法构造而成，由于Rabin公钥密码算法与RSA公钥密码算法的相
30、似性，Rabin签名算法与RSA签名算法也具有类似的相似性。6.3.1 Rabin数字签名算法数字签名算法Rabin数字签名算法的系统参数包括两个随机选取的相异大素数p和q，以及它们的乘积n=pq，其中n为公开密钥，p和q则需要保密。消息空间和签名空间都是由同为模p平方剩余和模q平方剩余的正整数构成的集合。使用Rabin签名体制对一个消息mZn签名时，首先要确保消息m既是模p的平方剩余，同时也是模q的平方剩余。如果消息m不能满足这一要求，可以先对m作一个变换，将其映射成满足要求的m。这里假设消息m已满足要求，对m签名就是计算m模n的平方根，即nmmsmod)(SIG由5.4节关于Rabin公钥
31、密码体制的讨论知道，求解合数模的平方根是困难的，除非能够对模数进行素因子分解，即知道模数n的两个素因子p和q，然后将问题转化成一次同余方程组，再利用中国剩余定理求解。因此，伪造Rabin数字签名是困难的。验证Rabin数字签名时，验证者只需计算消息签名的平方，然后通过下式确认数字签名的真伪VER(m，s)=truem=s2 mod nRabin数字签名正确性的验证是显而易见的。6.3.2 Rabin数字签名算法的安全问题数字签名算法的安全问题无论是用于数据加密还是消息签名，Rabin算法都可以看做是RSA算法的一个特例，这使得它在算法安全性问题上与RSA算法具有极大的相似性，前面5.3节和6.
32、2节所讨论的RSA算法的安全问题基本上都适合Rabin算法。另外，我们还知道Rabin算法是一种基于平方剩余的公钥体制，这种体制已经被证明它的安全性正好等价于大整数分解的困难性，但这种体制也容易遭受一种特定的攻击，其方法如下：攻击者选取一个x，计算出x2=M mod n；再将M发送给签名者签名，并等待签名者回送数字签名s。由5.4节的知识知道，签名者对M的签名可能有四个结果，其中包括x mod n，因此攻击者有1/2的概率得到一个非x mod n的签名，进而解出p和q，达到分解n的目的。也就是说，攻击者有1/2的机会攻破此系统。所以，在使用Rabin体制时要非常小心，否则可能不安全；而RSA体
33、制则没有这个缺点。Rabin数字签名算法的另一个缺陷是它要求被签消息必须是模n的平方剩余，否则就需要将被签消息映射到满足要求的另一个消息上，再用后者的Rabin签名作为原消息的签名，这给方案的应用造成很大的不便。后来，Rabin又对他的方案进行了改进，使任何消息都能直接被签名，这里不再进行介绍。6.4 ElGamal数字签名数字签名ElGamal数字签名体制是一种基于离散对数问题的数字签名方案。不同于既能用于加密又能用于数字签名的RSA算法，ElGamal数字签名算法是专门为数字签名设计的，它与用于加密的ElGamal公钥加密算法并不完全一样。现在，这个方案的修正形式已被美国国家标准与技术协会
34、采纳为用于数字签名标准(DSS)的数字签名算法。6.4.1 ElGamal数字签名算法数字签名算法与ElGamal公钥密码体制一样，ElGamal签名体制也是非确定性的，任何一个给定的消息都可以产生多个有效的ElGamal签名，并且验证算法能够将它们中的任何一个当作可信的签名接受。ElGamal数字签名算法的描述如下：ElGamal数字签名算法的系统参数包括：一个大素数p，且p的大小足以使Zp上的离散对数问题难以求解；的生成元g以及一个任取的秘密数a；一个由g和a计算得到的整数y，且满足y=ga mod p这些系统参数构成ElGamal数字签名算法的密钥K=(p，g，a，y)，其中(p，g，y
35、)是公开密钥，a是私有密钥。*pZ在对一个消息mZp签名时，签名者随机选取一个秘密整数k且gcd(k,(p)=1，计算=gk mod p=(m-a)k-1 mod(p)将得到的(，)作为对消息m的数字签名，即签名s=SIGa(m，k)=(，)，ElGamal数字签名体制的签名空间为ZpZ(p)。*pZ验证一个消息m的ElGamal数字签名时，验证者对收到的消息m及其签名s=(，)按下式验证其真伪：VER(m，)=trueygm mod p这是因为，如果签名是正确构造的，那么1()()mod()()mod()mod()modakakak m akpam apmpmygggggggp在上述ElGa
36、mal数字签名算法中，同一个消息m，对不同的随机数k会得到不同的数字签名s=(，)，并且都能通过验证算法的验证，这就是在前面所说的不确定性，这个特点有利于提高安全性。例例6.1 假设选取p=467，Z467的生成元g=2，签名者的私有密钥a=127，那么有y=ga mod p=2127 mod 467=132若要对消息m=100签名，假设取随机数k=213且 k-1 mod(p)=213-1 mod 466=431则有=gk mod p=2213 mod 467=29=(m-a)k-1 mod(p)=(100-12729)431 mod 466=51因此，得到的数字签名是s=(29，51)。假
37、如另取k=117重新计算对消息m=100的数字签名，则有k-1 mod(p)=117-1 mod 466235且=gk mod p=2117 mod 467=126=(m-a)k-1 mod(p)=(100-127126)235 mod 466=350所以，又得到一个新的数字签名是s=(126，350)。下面来验证这两个数字签名。对于第一个数字签名s=(29，51)，有y=132292951189 mod 467而gm mod p=2100 mod 467=189对于第二个数字签名s=(126，350)，仍然有gm mod p=2100mod 467=189而y=132126126350189
38、 mod 467所以，两个数字签名都是有效的。6.4.2 针对针对ElGamal数字签名算法的可能攻击数字签名算法的可能攻击由于验证ElGamal数字签名算法只是核实同余式ygm mod p是否成立，因此攻击者可以考虑通过伪造能够满足该同余式的数偶(，)来攻击此方案。在不知道签名者私有密钥a的情况下，攻击者想伪造这样的数偶(，)，并使之能够成为某个消息m的数字签名，他可以选定一个值作为，然后试图找出合适的，但这必需计算离散对数log(gmy-)。同样，攻击者也可以通过选择来寻找合适的，而这必需求解同余方程ygm mod p来获得，但目前这类方程还没有可行的解法。如果试图通过尝试不同的以得到m，
39、仍然需要计算离散对数logg(y)。最后，如果攻击者通过选择和，然后计算出m，那么他再一次面临求解离散对数logg(y)。因此，ElGamal数字签名算法的安全性依赖于求解离散对数问题的困难性，如果求解离散对数已经不再困难了，那么ElGamal数字签名算法也就没有任何意义了。在假定离散对数问题依然难以求解的情况下，ElGamal数字签名算法仍然存在一些安全威胁，这些安全威胁首先来自于对算法使用不当而造成的可能攻击，它包括如下两个方面：(1)对签名中使用的随机整数k保管不当，发生泄露。如果攻击者知道k的话，那么只要攻击者能够再获得签名者对某一个消息m的合法签名s=(，)，就可以非常容易地计算出签
40、名者的私有密钥a=(m-k)-1 mod(p)。这时整个系统完全被破坏，攻击者可以随意伪造该签名者的数字签名。(2)对ElGamal方案的另一个误用是重复使用签名随机数k。这同样可以使攻击者易于计算出签名者的私有密钥a，具体做法如下：设(，1)和(，2)分别是某个签名者对消息m1和m2的签名，且m1m2 mod(p)，有m1=a+k1 mod(p)m2=a+k2 mod(p)两式相减，得m1-m2k(1-2)mod(p)设d=gcd(1-2，(p)，那么d|(p)且d|(1-2)，所以d|(m1-m2)。记则等式变成1212()mmmddppd modmkp由于gcd(，p)=1，所以可以用扩
41、展的欧几里德算法求出()-1 mod p，然后得到k=m()-1 mod p于是k=m()-1+ip mod(p)，i0，1，d-1对于这d个可能的候选值，只需利用同余式=gk mod p逐一验证，即可检测出惟一正确的那个k。找到了签名随机数k，就可以像上述(1)一样计算出签名者的私有密钥a。除了使用不当造成的安全威胁以外，ElGamal签名方案还面临着伪造签名的攻击。有多种方法可以伪造出ElGamal数字签名，分述如下：(1)第一种伪造方法，仅需知道合法签名者的签名验证密钥(即公开密钥)，即可通过任意选择的，构造出和m，使(，)恰好是该签名者对消息m的签名。由此可见，攻击者可以在惟密钥的情况
42、下进行存在性伪造。设i和j是0，p-2上的整数且可表示为=giyj mod p。那么签名验证条件是gmy(giyj)mod p于是有gm-iy+j mod p若m-i0 mod(p)且+j0 mod(p)则上式成立。因此，在给定i和j，且gcd(j，(p)=1的条件下，很容易利用这两个同余式求出和m，结果如下：=giyj mod p=-j-1mod(p)m=-ij-1mod(p)显然，按照这种方法构造出来的(，)是消息m的有效签名，但它是伪造的。例例6.2 如例6.1，设p=467，g=2，y=132。假如选择i=209和j=147，那么j-1 mod(p)=149。计算(435，425)是对
43、消息m=285的有效签名，这可以从下面的式子得到验证：20914711mod2132mod467435mod()435 149mod466425mod()435209 149mod466285ijg ypjpmijp 43542528513243534 mod467234 mod467myg(2)第二种伪造方法属于已知消息攻击的存在性伪造，伪造签名者需要从合法签名者的某个已签名消息开始，来伪造一个新消息的签名。假定(，)是消息m的有效签名，h、i、j是0，p-2上的三个整数且gcd(h-j，(p)=1。计算那么，签名验证条件显然成立。于是伪造出一个(，)是m的有效签名。11mod()mod()
44、()()mod()hijg yphjpmhmihjp modmygp这两种伪造签名的攻击都是对ElGamal数字签名的存在性伪造，目前似乎还不能将其演化成选择性伪造，对抗这种存在性伪造的简单办法是使消息格式化。最简单的消息格式化机制是在消息中嵌入一个可识别的部分，如签名者的身份数据，使消息成为类似这样的格式m=MID。而最有效的消息格式化机制是对消息进行Hash函数处理，如果签名者在签名之前先对消息进行Hash函数处理，这两种存在性伪造攻击方法就不能对ElGamal签名体制造成实际的威胁。这里再一次发现了安全Hash处理的重要性。(3)第三种伪造方法，如果系统参数p和g满足如下条件：(p)=b
45、qg=t mod p其中，q是一个足够大的素数，b是一个仅具有小的素因子的数，=cq，且cp条件下可行。假设(，)是对消息m的有效签名，可以通过下面的步骤伪造对任意一个消息m的数字签名。先计算然后再计算，使满足umod (p)mod p显然，可以通过中国剩余定理解出。1mod()mod()um mpup 检查验证同余式是否成立：因此，(，)是消息m的有效签名，但它是伪造出来的，因为并没有使用签名的私有密钥。如果在验证签名时检查1，则令gh(p-1)/q mod p，否则重选h。(4)一个用户随机选取的整数a，并计算出y=ga mod p。*pZ*pZ*pZ*pZ(5)一个Hash函数H：0，1
46、*|Zp。这里使用的是安全的Hash算法SHA-1。这些系统参数构成DSA的密钥空间K=p，q，g，a，y，H，其中(p，q，g，y，H)为公开密钥，a是私有密钥。为了生成对一个消息m的数字签名，签名者随机选取一个秘密整数kZq，并计算出s(，)就是消息m的数字签名，即SIGa(m，k)=(，)。由此可见，DSA的签名空间为ZqZq，签名的长度比ElGamal体制短了许多。1(mod)mod()modkgpqkH maq验证DSA数字签名时，验证者知道签名者的公开密钥是(p，q，g，y，H)，对于一个消息签名对(m，(，)，验证者计算下面几个值并判定签名的真实性：12112mod()modmo
47、d(mod)moduuwquH m wquwqvg ypq(,(,)VER mtruev 这是因为，如果(，)是消息m的有效签名，那么图6-4所示为DSA数字签名算法的基本框图。12111()()(mod)mod(mod)mod(mod)mod(mod)moduuH maH makvg ypqggpqgpqgpq 图6-4 DSA数字签名算法基本框图例例6.3 取q=101，p=78q+1=7879。由于3是的一个生成元，因此取g=378mod 7879=170g是上的一个q阶元素。假设签名者的私有密钥为a=87，那么y=ga mod p=17087mod 7879=3226*7879Z*78
48、79Z现在，假如该签名者要对一个消息摘要为SHA-1(m)=132的消息m签名，并且签名者选择的秘密随机数为k=79，则签名者需要计算因此，(99，57)是对消息摘要为132的消息m的签名。11791mod79mod10178(mod)mod(170mod7879)mod101907mod10199()mod78(1328799)mod101682110 mod10157kkqgpqkH maq要验证这个签名，需要进行下面的计算：所以说明以上签名是有效的。1112mod57mod10139()mod13239mod10198mod9939mod10123wquH m wquwq129823(m
49、od)mod(1703226mod7879)mod10199uuvg ypq6.5.2 DSA算法的安全问题算法的安全问题DSS公布以后，引起了学术界和产业界的广泛关注，大家对它的反应更多的是批评和谴责，认为它的政治性强于学术性。NIST随后开展了一次征求意见活动，到1992年2月活动结束时，共收到109篇评论。概括起来，评价的意见主要体现在以下几个方面：(1)DSA算法不能用于数据加密，也不能用于密钥分配。DSS只是一个数字签名标准，但当时美国还没有法定的公钥加密标准，因此引起了人们对DSS的猜疑。(2)DSA算法比RSA慢。DSA与RSA生成数字签名的速度相当，在验证签名时DSA比RSA要
50、慢10到40倍。(3)DSA算法的密钥长度太短。最初的DSA模数为512比特，由于DSA算法的安全性依赖于求解离散对数问题的困难性，这种规模的离散对数已不能保证长期的安全，因此后来NIST将DSA的密钥设置为可变的，变化范围在512比特到1024比特之间。(4)DSA算法由美国国家安全局(NSA)研制，其设计过程不公开，提供的分析时间不充分，怀疑其中可能存在陷门。这主要是担心政府借机干涉公民的隐私。(5)其他意见。比如DSA算法可能侵犯别人的专利；RSA经受了多年的分析已成为一个事实标准，并产业界已投入了大量资金；等等。现在看来，DSA算法的安全问题并不象当初很多人猜测的那样可怕，有些涉及安全
