《毕业设计（论文）ELGamal数字签名技术的研究.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）ELGamal数字签名技术的研究.doc（37页珍藏版）》请在三一办公上搜索。
1、ELGamal数字签名技术的研究 摘 要 计算机网络的产生把我们带进了一个信息化的社会。当前，计算机网络的安全问题日益突出，网络给我们带来便利的同时，网络安全的形式不容乐观，已严重威胁到人们正常的生活，甚至威胁到国家安全。网络安全的实质是信息安全，信息安全技术的核心之一是数字签名技术。如何在信息传输的过程中保证信息的安全性和真实性，这是数字签名技术所要研究的重要问题。数字签名可以解决否认、伪造、篡改、冒充问题。使用数字签名技术使得发送者发送的时候不能否认发送的报文签名，接受者不能伪造发送者的报文签名，即网络中的某一用户不能冒充另一用户。ELGamal数字签名作为一种重要的签名手段与一般公钥密码
2、体制签名方法的不同之处，是具有高安全性和实用性。本文介绍了ELGamal技术的基础知识以及它的推广并与RSA算法做一对比，得出ELGamal有着很大的优越性。最后阐述了基于ELGamal体制盲签名、代理签名以及多重数字签名。关键词 密码学，信息安全，RSA, ELGamalABSTRACTComputer network produces have brought us into a information society. At present, the computer network security problem increasingly, network brings us con
3、venient at the same time, network security is not optimistic, and the form of already a serious threat to peoples normal life and even threaten national security. Network security is the essence of information security, information security technology is one of the core password techniques. How in t
4、he process of information transmission assurance information security and authenticity, this is digital signature technology to research the important problem. Digital signature can be solve deny, forgery, falsify or pretend to be problems. Using digital signature technology makes the sender can den
5、y that send message when recipients cant forged signatures, and the senders message signatures, namely a network of users dont pretend to be another user. ELGamal digital signature method and general public key cryptosystems signature method, is the differences with high safety and practicality. Thi
6、s paper introduces the basic knowledge of ELGamal technology and its promotion and comparison with RSA algorithms, it is concluded that the ELGamal has great advantages. Finally lists the ELGamal signature technique based on other signature scheme.Key Words: Cryptograph, Information Security, RSA, E
7、LGamal目录1. 绪论11.1研究背景及意义11.1.1信息安全的重要地位11.1.2密码理论在信息安全中的重要作用21.2数字签名技术的作用31.3 数字签名原理41.4 数字签名的功能61.5 数字签名技术的应用72.基本概念82.1 数论82.1.1因子82.1.2.素数82.1.3.模运算82.1.4本原元92.2 复杂度理论92.2.1.问题的复杂性92.2.2算法的复杂性103.基于ElGamal 算法的数字签名方案123.1数字签名定义123.1.1 形式化定义123.1.2 数字签名的安全性133.1.3数字签名的攻击143.2 离散对数签名方案143.2.1有限域143.
8、2.2离散对数问题153.3 ELGamal数字签名153.3.1 ELGamal签名方案153.3.2 ELGamal签名方案的变形173.3.3.ELGamal签名体制与其变形的比较193.4 ELGamal算法与RSA算法的性能比较214.基于ELGamal数字签名体制的其它签名方案234.1基于ELGamal体制的盲签名方案234.1.1过程234.1.2.性能分析244.2基于ELGamal体制的代理签名方案254.2.1 签名过程264.3基于ELGamal体制的多重数字签名方案274.3.1基于ELGamal体制的广播多重数字签名274.3.2基于ELGamal体制的有序多重数字
9、签名295.总结32参考文献34答 谢351. 绪论1.1研究背景及意义信息在社会中的地位越来越重要，已成为社会发展的重要战略资源。在当今社会里，大量传输和存储信息的安全保密及防伪问题已成为人们关注的一个重要课题。当前，计算机网络的安全问题日益突出，网络安全的形式不容乐观，已严重威胁到人们正常的生活，甚至威胁到国家安全。网络安全的实质是信息安全，信息安全技术的核心之一是数字签名技术。普遍的观点认为，现代数字签名技术是解决信息安全的最有效的方法。因此，数字签名的研究成为当前国际上的一个研究热点。而怎样利用数字签名来保证信息在传输过程中的安全性和真实性是当前研究的一个重要课题。1.1.1信息安全的
10、重要地位随着计算机网络技术的迅速发展，特别是Internet的广泛普及，如电子商务、电子政务、银行金融网络、网络游戏、聊天室和各类订票系统15等应运而生，Internet在给我们生活带来便利的同时，如何处理它对传统产业和传统观念带来的新的冲击，使传统产业向更好的方向发展?在信息技术的应用过程中，信息是最为宝贵的资源，Internet为信息的传播和获取提供了极大的便利，他使我们不受时间和空间的限制与世界上任何个人或组织进行信息交流，而且各种新闻都能以最快的速度和最短的时间在向世界范围传播。网络在给我们带来巨大的经济利益和便利的同时，黑客，利用网络和系统漏洞，肆意攻击业务应用系统和网站，造成巨大的
11、经济损失。机密信息在网络上被篡改和假冒，不良信息的传播给青少年的成长带来负面影响，计算机犯罪呈上升趋势，这些问题已严重威胁到国家的政治、军事、经济、文化等方面的安全，网络信息安全已成为亟待解决的关键问题。因此，信息安全问题解决不了，信息化将不可能得到持续、健康的发展，与之相关的经济安全、政治安全、国家安全将得不到可靠的保障。从安全需求角度来讲，信息安全应包括五个基本要素1：机密性（confidentiaility）、完整性（integrity）、可用性（availability）、可控性（conttrollability）与不可抵赖性（non-repudiation）等，其特征如下：（1）机密
12、性 机密性是指网络信息只为授权用户使用，不能泄密给非授权用户，不能被非法利用；（2）完整性 完整性就是指网络信息未经授权不进行改变的特性。也就是说，完整性要求在信息传输过程中信息原样保持不变；（3）可用性 可用性就是保证信息及服务可被授权用户使用的特征；（4）可控性 可控性是指网络信息的信息流流向，信息传播和信息内容等具有控制能力的特性；（5）不可抵赖性 不可抵赖性也称作不可否认性，是指网络用户不能否认或抵赖自己的操作和做出承诺。概括来讲，信息安全就是通过计算机技术、网络技术、密码技术和网络安全技术等保护网络信息在传输、交换、和存储过程中的机密性、完整性、可用性、可控性和不可抵赖性等。1.1.
13、2密码理论在信息安全中的重要作用密码学是信息安全的核心和基石。密码学2包括两个分支：密码编码学和密码分析学。密码编码学是对信息进行编码实现隐藏的一门学科，主要研究如何实现信息保密和认证的方法与技术。密码分析学是研究如何破译密码的一门学科，主要目的是研究密文的破译和消息的伪造。为适应计算机通信的迅速发展的需要，密码学的研究领域逐步从消息加密扩展到数字签名、消息认证、身份识别、防否认等。同时密码学的应用不再局限于军事、政治和外交，而扩大到商务、金融和社会各个领域。网络以飞的速度普及的同时，使得一些人就有可能采用各种非法手段窃取、假冒、篡改和破坏传输信息中的重要信息，甚至进行计算机犯罪。也是因为存在
14、的种种信息安全问题，才催生了信息安全技术的发展。信息安全的技术，如数据加密技术、数字签名技术、消息认证与身份识别技术、防火墙技术以及反病毒技术等都是基于密码学来设计的，而数字签名在密码学中的地位不容小视。最近，欧洲委员会的信息社会技术（IST）规划出资33亿欧元支持一项新的欧洲数字签名、信息完整性和加密方案（NESSIE）工程，目标是推出一套密码标准，包括分组密码、流密码、杂凑函数、消息认证码、数字签名和公钥密码等。所有这些密码标准的研究和公布，将为信息安全提供强大的理论基础和技术支持。1.2数字签名技术的作用一个人在文件的最后想证明自己的身份可以用它的印章或手写签名，而一个单位可以用公章，在
15、信息高度化的今天，难道我们可以在一份文件上盖公章吗？回答是肯定的，这就需要使用数字签名。随着计算机网络的应用普及，网络对等实体的识别、通信保密和数据完整性显得越来越重要，而确实解决这一问题则必须使用数字签名技术。数字签名在ISO7498-2标准中定义为：“附加在数据单元上的一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人（例如接收者）进行伪造”。数字签名所要解决的问题2归纳起来大概有下列情况 ：（1）否认 发送方不承认自己发送过某一报文；（2）伪造 接收方自己伪造一份报文，并声称它来自发送方；（3）篡改 接收
16、方对收到的信息进行篡改；（4）冒充 网络上的某个用户冒充另一个用户接受或发送报文。正是由于数字签名具有的独特功能和实际用途，在一些特殊的行业，比如金融、商业、军事等有着广泛的应用，尤其是在数据完整性检验、身份识别、身份证明、防否认等方面，功能独特，满足这些要求的最好办法就是使用数字签名技术。由此可见，数字签名技术在网络通信中的重要作用和特殊位置。1.3 数字签名原理3公钥密码学中，公开密钥和私有密钥组成的密钥对作为一个密钥。数字签名就是用私有密钥进行加密，接收方用公开密钥进行解密，由于公开密钥不能推算出私有密钥，所以公开密钥不会损害私有密钥的安全。公开密钥可以公布于众，而私有密钥必须要保密。当
17、某人用其私有密钥加密消息，用他的公开密钥成功解密时，就可确定该消息是有人签字的，这就是数子签名的基本原理。所有的公钥密码算法都可用于实现数字签名。哈希函数3，把任意长度的消息变换为一个固定长度的散列值。当消息只有一个比特位产生变化时，数据摘要“显著”地发生变化，其目的是把大的消息压缩变短了，因此，称 “数据摘要为数据指纹”。在消息进行篡改、插入和重排之后，数据指纹也会变化，所以，能提供完整性服务。一般来说，数据的完整性检验方法如图1-1所示。从1、2端送入密钥。消息实际收到的附件产生附件消息产生附件所期望的附件附件如果二者一样，则认为消息是完整的消息 附件12图 1-1消息完整性检验 数字签名
18、5就是由信息的发送者通过一个单向函数对要传送的报文进行处理产生别人无法伪造的一段数字串。这个数字串用以认证报文的来源并核实报文是否发生了变化。发送者用自己的私有密钥加密数据传给接受者，接受者用发送者的公钥解开数据后，就可以确定消息来源，同时也是对发送者发送信息的真实性的一个证明，发送者不能抵赖。具有消息摘要的数字签名工作工程如上图1-2所示。原始信息摘要运算签名信息签名方私钥加密文档 有效 数据 信息 附加 验证 信息验证方原始信息签名信息摘要运算结果比较签名方公钥解密签名方图1-2数字签名过程1.4 数字签名的功能 数字签名技术其功能4有以下几个方面：（1）完整性 数字签名与原始的文件或其摘
19、要一起发送给接收方，一旦信息被篡改，接受者可以通过计算机摘要和验证签名来判断该文件无效。（2）机密性 将报文信息用接收方的公钥进行解密，以保证信息的机密性。（3）防伪造 签名密钥即私钥只有签名者自己拥有，别人不能伪造出正确的签名数据。这就是防伪造特性。（4）身份认证 数字签名中，公钥是其身份的标志，使用公钥签名，如果接受方或验证方用其公钥进行验证并获通过，那么可以肯定签名人就是拥有私钥的那个人。（5）防抵赖 数字签名可作为签名者签名操作的依据，防止抵赖。（6）防重放攻击 通常采用对签名报文的加盖时间戳或添加处理流水号等技术，可以防止重放技术。1.5 数字签名技术的应用数字签名技术最早应用于用户
20、登录过程。PKI作为电子商务、电子政务的技术平台，使得技术应用、商业价值、生产力提高成为有机的整体，得到了长足的发展。到目前为止，全国省市几乎都建立了自己的CA认证中心，这些CA中心的数字证书及相关应用方案被广泛应用于网上报关、网上报税、网上报检、网上办公、网上招投标、网上采购、数字工商等大型电子政务和电子商务工程中。数字签名技术还广泛应用于电子邮件、数据交换、电子交易和电子货币等领域。安全电子交易SET是MasterCard两大信用卡公司和多家科技公司于1977年制定的一个在Internet上进行的在线交易的安全标准，SET提供了消费者、商家和银行间的认证，确保了交易数据的安全。完整可靠和交
21、易的不可否认，特别是保证了消费者的隐私。SET已经成为了目前最流行通用的安全电子商务标准，他的核心技术主要有公开密钥加密、数字签名、数字证书、数字信封等。SET协议中的数字签名技术之一是双重签名，双重签名的特性就是把发给两个不同通信实体的两个不同消息联系在一起，两个通信实体都可以验证该双重签名。2.基本概念数论、线性代数、复杂性理论、组合论等，均为数字签名理论不可或缺的工具。本章简单介绍数字签名理论中需要的有关数论和复杂性理论的知识。2.1 数论2.1.1因子3设a,b()是两个整数，如果存在另一整数m，使，则称b整除a，记为,且称b是a的因子。否则称b不整除a。整数具有以下性质：(1)，那么
22、。(2)且，则。2.1.2.素数定义2.1.1：如果整数,且仅能被1和它自身整除，而不能被其他整数整除，则称整数为素数。定义2.1.2：设a，b为整数不全为0，能同时整除a和b的最大正整数称为最大公约数，记为，有时记为,它的等价表示形式为： 2.1.3.模运算 定义2.1.3如果a是一个整数，n是一个正整数，a除以n的余数用表示，n称为模。定理2.1.4对于任何非负整数a和b，有。定义2.1.5令为小于n，且与n互素的所有整数的个数，即为模n既约剩余类中所有元素的个数，称为欧拉函数。定理2.1.6（欧拉定理）若则。2.1.4本原元6首先介绍阶的概念：模19下7的阶为3本原元：模n下a的阶m=p
23、hi(n),m就是n的本原元，如3是19的本原元。本原元并不是唯一的（19的本原元还有2,3,10,14,15）也并不是所有的证书都有本原元。2.2 复杂度理论72.2.1.问题的复杂性复杂度理论分析各种问题求解所需的时间及最小的空间，按照问题的复杂性，将其分成不同类别的类型。根据求解问题所需的时间，对各种问题进行分类。P类代表能在多项式时间内求解的问题，类代表能在多项式时间内，利用“不确定”性图灵机【5】可以求解的问题。不确定性图灵机，能够任意猜测一解，并在多项式时间内判别此解的真伪。显然所有的P类问题可以用不确定性图灵机来求解，因此有。若所有问题可以在多项式时间内利用“确定性”图灵机求解，
24、则。但一般而言，在中的问题都较P问题困难。是否有，这是复杂度理论中受到相当重视的课题，至今未证明。一旦证明，这些系统在确定性多项式时间内也可破解。所有的问题都可以通过多项式问题都可以转换为一类称为的问题，这是类中困难最大的一类问题，对于一个问题，不存在任何已知的确定性算法在多项式时间内求解。但如果知道陷门，则可以求解。因此，问题可以构造密码体制。现有的密码算法的安全性的安全性都是基于问题的。2.2.2算法的复杂性密码系统的安全性，取决于攻击者破解该密码系统的时间和空间开销，即在一个相当长的时间内，在保证密码系统的保密功能有效的前提下，攻击者无法破解，则该密码系统是安全的。复杂度理论是密码分析的
25、基础，而算法的计算复杂性由求解问题所需的运算次数决定，包括时间复杂度和空间复杂度，时间复杂度是指算法实现所需的最大时间，空间复杂度是指算法实现所需的最大空间。一个安全的密码系统不只取决于计算复杂度问题，Shamir8提出的理由如下：（1）复杂度理论，通常只针对某一种问题中的某一特例而进行分析，但密码系统破译者，却拥有许多统计上的数据可供分析。（2）复杂度理论只针对某一问题中最差或平均例子进行分析。但对于一个有用的密码系统，其复杂度的假设，却必须对所有可能的例子都是真值。（3）陷门必须被巧妙的安排入问题中，而只有知道这扇陷门，才能简易地求解。陷门不见得可以轻易地放入任何问题中去。利用复杂度的假设
26、来设计密码系统，是目前密码学的一个研究趋势。如何将陷门藏匿与问题之中，而设计出既安全又实用的密码系统，对密码学研究是一大挑战。3.基于ElGamal算法的数字签名方案1985年，ELGamal基于离散对数难题提出一种数字签名方案，称为ELGamal数字签名方案。1994年，Harn等人对ELGamal及其类似方案进行了总结，得出了18个安全可行的方案，即广义ELGamal签名方案9。同时，Horster 也独立地提出了“Mata-ELGamal签名方案10”，它是Harn的18中方案的进一步推广。因为ELGamal型签名方案是在环或域上进行的二元运算，容易受到同态攻击和代换攻击，因此，在实际应
27、用ELGamal型签名方案时，需要将明文m进行处理，即利用hash(m)来代替m。1994年，Nyberg和Rueppel对ELGamal签名方案进行了攻击，提出具有消息恢复的签名方案，称为N-R数字签名方案12。Hoster, Michels和Petress利用N-S数字签名方案具有较小的签名长度和消息恢复特性设计了一种低通信消耗的签名方案，称为HMP方案13。随后相继提出很多种具有消息恢复特性的签名方案。在签密方案中，信息签发者可以对信息进行加密和签名，信息接收者可以对接收到的信息进行解密和验证。当消息量很大时，还可以采用消息链接的方式进行处理。3.1数字签名定义3.1.1 形式化定义数字
28、签名方案一般包括三个主要过程：系统的初始化过程、签名产生过程和签名验证过程。系统的初始化过程产生数字签名方案用到的一切参数；签名产生过程中，用户利用给定的算法对消息产生签名；签名验证过程中，验证者利用公开的验证方法对给定消息的签名进行验证，得出签名是否有效的结论。定义2.3.17 称由3个集合：消息集合M、密钥集合 、签名集合S和2个算法，即签名算法SIG、验证算法VER、组成的5元组为一个数字签名方案，其中K是包括公钥和私钥在内的所有密钥的集合，并满足下列条件：(1)签名算法 对于密钥集合K，相应的签名算法为，,对任意的消息，有,那么为消息m的签名，将传送到签名验证着。(2)验证算法 对于密
29、钥集合K，有签名验证算法签名接受者或验证者收到后，计算;若签名有效；否则，签名无效。3.1.2 数字签名的安全性14数字签名方案的安全性都是基于某些数学难题的。这些数学难题主要有以下三个：（1）素数域上的离散对数问题，这类应用特别广泛，如现在的大部分签名方案，ELGamal方案，DSA方案和许多协议的设计都是基于此困难问题的。（2）椭圆曲线问题，这是今年来的研究热点，它和离散对数问题是对应的，它与离散对数相比，优点在于速度快得多，更加实用，但缺点在于安全参数的选取比较复杂，而且很多人对它的安全性有一定的怀疑。（3）大合数的因子分解，主要有RSA和Rabin体制等。3.1.3数字签名的攻击对数字
30、签名方案的攻击5，如果攻击者攻破了用户A的签名方案，如果他能够以不可忽略概率完成下面的操作：(1)完全攻破 计算A的秘密陷门信息；(2)一般伪造 找到一个功能等效于A的签名算法的有效签名算法；(3)选择伪造 对敌手优先选择的某个特殊消息伪造一个签名；(4)存在伪造 对至少一个消息伪造一个签名，敌方对他获得的消息及其签名没有任何控制作用。所以他可以是随机的或无意义的。于是，这种伪造对于用户A 仅仅是最小的知识泄露。注意，伪造一个签名也就意味着产生一个新的签名；单从A用户那里获得一个消息及其签名然后说他现在“伪造”了一个签名，但这并不是伪造。3.2 离散对数签名方案3.2.1有限域15有限域，在其
31、上定义模p的代数运算，即加法：如果,则；乘法：如果，则。在中，所有的元素对于加法和乘法满足封闭性，并满足分配律、无零因子条件，构成一个有限域。)有时简记为。令表示中所有非零元素的集合，即中任意元素的集合，即,可以证明在中至少存在一个元素g，使得中任意元素可以表示成g的某次幂的形式，这样的元素成为g的生成元，即3.2.2离散对数问题4设p是一个素数，是其生成元，已知,求称为模p的幂运算。但是反过来，若求成立，已知y求x的问题称为模p的离散对数问题。我们将已知y求x的离散对数定义为寻求符合条件的x。一般，生成元g是模p的本原元，这表明每一个y值都是g的一个幂，如果g不是p的本原元，那么就不会为y值
32、定义离散对数。如果n是满足的最小正整数为模p的关于y的离散对数。3.3 ELGamal数字签名本节给出ELGamal签名方案原形及其它的几种变形方案，并分析了这些方案在计算上的优缺点以及对方案的安全性进行了比较。3.3.1 ELGamal签名方案11方案描述 ELGamal型数字签名方案12包含系统初始过程、签名过程和验证过程：(1)初始过程p 设p是一个大素数；g 整数g是的一个生成元；x 签名人的私钥为；y 相应的公钥为。(2)签名过程对于待签消息m，签名者A执行以下步骤： 计算m的杂凑值H（m）。 任意选取一个随机数，计算。 计算。作为消息m的签名。将m和签名（一起发送给接受者。(3)验
33、证过程 接收方受到m和签名后，验证 是否成立？如果成立，则接受签名，否则，拒绝签名。2.正确性证明由签名方程易得：。3.安全性分析（1）整体性攻击1。如果一个攻击者试图伪造用户A 对消息m的签名，他随机大素数地选取一个整数，攻击成功的概率为,这对于大素数来讲几乎是不可能的。如果要从r中求出消息密钥k，将面临求解离散对数的难题。(2)重复性攻击8。如果对不同的消息使用相同的密钥，则面临消息密钥被暴漏的危险。设,，则。若，则，一旦得到k，就很容易求得x。3.3.2 ELGamal签名方案的变形10在下面的变形体制中，全局参数，私钥参数，公钥参数的选取与原体制保持一致。变形一(1)签名过程生成随机数
34、;计算r：；计算s：；把消息和签名结果（m,r,s）发送给接收者。(2)认证过程计算：；计算：；如果=，表示签名有效；否则签名无效。变形二(1)签名过程生成随机数；计算r：；计算s：；把消息和签名结果（m,r,s）发送给接收者。(2)认证过程计算：；计算：；如果=，表示签名有效；否则，签名无效。变形三(1)签名过程生成随机数；计算r：；计算s：；把消息和签名结果（m,r,s）发送给接收者。(2)认证过程计算：；计算：；如果=，表示签名有效；否则，签名无效。变形四(1)签名过程生成随机数；计算r：；计算s：；把消息和签名结果（m,r,s）发送给接收者。(2)认证过程计算：；计算：；如果=，表示签
35、名有效；否则，签名无效。变形五(1)签名过程生成随机数；计算r：；计算s：；把消息和签名结果（m,r,s）发送给接收者。(2)认证过程计算：；计算：；如果=，表示签名有效；否则，签名无效。ELGamal签名体制及其五种变形，都是基于下面的签名方程： 3.3.3.ELGamal签名体制与其变形的比较1.签名计算由于在不同的签名使用过程中使用的私钥x是固定的，而随机数k是变化的。那么在变形一和变形四中求解出后可以用于不同的消息签名中s的计算。但在原ELGamal体制和变形五中，每次签名都需要求出不同的，变形二或变形三中计算s既不需要计算也不需要计算，签名效率明显由于其他四种签名方案。2.认证计算要
36、认证变形一和变形三中已签名的消息，需计算，可以预先编制的表格，这样在不同签名的消息认证中可通过查表立即得到。从而大大提高了认证速度。这在其他四种体制中是不可行的。例如：当p=476时，的表格所需要的数字个数为475.但在原ELGamal体制中要编制，所需要的数字个数为。随着p的增大，所需个数成二次方级增长。3.安全性4(1)在不知明文密文对下的攻击由于攻击者不知道用户的私钥x，所以要伪造用户的签名，需要先选定一个r(或s)，然后实验找到相应的s(或r)。如果攻击者选定r，实验求解相应的s，在原ELGamal体制中需要计算；在变形一中需要计算离散对数；在变形二中需要计算；变形三中需要计算；在变形
37、四中需要计算；变形五种需要计算；这都是求解离散对数问题。如果攻击者选定s，实验求解相应的r。在原ELGamal体制中他需要求解关于未知数r的方程，在变形一中需要求解；在变形二中需要求解；在变形三中需要求解方程；变形四中需要方程；在变形五中需要求解方程；这都是一个没有可行解法的问题。因此，攻击者在不知明文密文对的情况下这六种签名方案都是正确的。(2)已知明文密文对的攻击如果攻击者知道是合法的签名，实验得到明文m。在ELGamal体制中需要计算；变形一中需要计算；在变形二中需要计算；在变形三中需要计算；在变形四中需要计算；变形五中需要计算；这都是求解离散对数问题。因此，攻击者即使知道明文密文对也不
38、能签名一个随机的消息。如果攻击者知道了两个消息，及其相应的签名 ，；并且这两次签名都使用的是同一个随机数K，那么，在原ELGamal体制中有攻击者可以通过求解方程算出用户的私钥x，则体制被攻破。同样，其它变形方案也可以通过类似上面问题的方程组得到用户的私钥。通过上面的分析可以得到结论：ELGamal体制及其五种变形的安全性是等价的。如果不使用相同的随机数来签名不同的两个消息，都能保证签名消息不被伪造。在签名效率方面，变形二和变形三的签名效率最高。变形一和变形四在签名效率上优于原ELGamal签名方案和变形方案五，在认证效率方面，变形一和变形三的认证效率优于其它四种签名方案。3.4 ELGama
39、l算法与RSA算法的性能比较16RSA被认为是一种理论上最安全的公钥密码体制之一，它的安全性是基于数论中的一个重要论断：求两个素数的积是容易的，而要分解两个素数的积是非常困难的。ELGamal算法其安全性依赖于计算有限域上离散对数这一难题。在此，ELGamal算法与RSA算法4的比较：RSA算法17是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究的最早广泛的公钥算法，从提出到现在经历了各种攻击的考验，逐渐被人们所接受，普遍被认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能的到理论上的证明，也并没有从理论上证明破译RSA的难度与大
40、数分解难度等价。因为没有证明破解RSA就一定需要大数分解。假设存在一种无需分解大数的算法，那它肯定可以修改成为大数分解算法。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且，密码学界得多数人士倾向于因子分解。RSA体制的主要缺陷有17：（1）产生密钥较麻烦，受到素数产生限制的影响，因而难以做到一次一密；（2）分组长度太大，为保证安全性，n的取值很大，使运算代价很高，尤其是速度较慢；（3）RSA在选择密文攻击面前很脆弱。一般攻击者将某一信息做一下伪装，让拥有私钥的实体签署。然后，经过计算就可以得到它所想要的信息。ELGamal算法既能于数据加密也能用于数字签名，其安全性依赖于计算有限域
41、上离散对数这一难题。ELGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。相比较于RSA算法而言，因为ELGamal体制中的随机参数的取值每次均不同，所以，即使使用相同的私钥对相同的明文进行加密，每次加密后得到的签名也各不相同。这样有效的防止了网络中可能出现的重放攻击。这也是与RSA算法的一个最重要区别。ELGamal的一个不足之处是他的计算量大，且密文成倍扩张。4.基于ELGamal数字签名体制的其它签名方案4.1基于ELGamal体制的盲签名方案3盲签名是一种特殊的数字签名，当用户A发送消息m给签名者B时，一方面要求B对消息签名，另一方面又
42、有不想让B知道消息内容，也就是签名者B所签的消息是经过盲化处理的。签名除具有一般数字签名的特征外，还有下面两个特征：（1）签名者无法知道所签消息的具体内容，虽然他为这个消息签了名。（匿名性）(2)即使后来签名者见到这个签名时，也不能将之与盲消息对应起来。（不可跟踪性）其中引入了有向因子2，有向盲签名方案构造为:设，Alice，Bob各自的私钥和公钥，现在。Alice需Bob为消息m进行盲签名。4.1.1过程步骤如下：步骤1 Alice：随机选择盲因子，满足计算,将M送给Bob。步骤2 Bob: (1)接受到M后，随机选择k，,计算,;(2)求出;(3)将作为签名送给Alice。步骤3 Alic
43、e：首先，求出,验证如果不等式成立，则拒绝接受Bob对盲消息的签名。然后由对盲消息M的签名S恢复出对原消息m的签名s验证等式是否成立，决定恢复的s是否正确。方案中各种符号的具体含义分别为：p为一个大素数，可使中求解离散对数为困难问题；m为原消息；M为盲化后的消息；s为原消息的签名；S为盲消息的签名；g,k,r参数的意义和ELGamal签名体制中一致。4.1.2.性能分析1安全性分析18（1）有向因子的引入使得只有验签双方具有签名和验证签名的权利，其他参与者和用户或攻击者将不具备验证消息签名的权利。攻击者欲求出，须知道私钥或，这将面临求解离散对数问题。（2）攻击者如获取盲消息M,欲从M中求得私钥
44、，将面临离散对数问题，而如果想求出原消息m，因为t是一大的随机数，将面对大整整因子分解的困难。（3）攻击者想要从中求得签名者私钥，因为k为签名者随机选取的大素数，所以必然面临大整数因子分解的困难；而欲从中求出k，也会同样面临求解离散对数问题。2方案特点（1）将发送方的私钥引入对消息的盲化，即,相比于原有的盲化方法，提高了盲消息的抗攻击性能。（2）在本方案中，引入有向因子，使得只有特定收发方才具有对消息进行签名的能力，攻击者无法通过对消息进行签名而对签名进行跟踪。在ELGamal签名体制基础上，设计了一种新的盲签名技术。在签名过程中通过有向因子的引入，实现了定向用户验签的功能，并且将私钥引入对消
45、息的盲化过程，提高了算法的安全性能。该方案将加密和盲签名融为一体，具有较高的安全性和实用性就，必将有利于推动电子商务的发展并使盲签名技术在选举投票、数字货币协议、电子支付系统等中得以广泛的应用20。4.2基于ELGamal体制的代理签名方案5在现实生活中有这样的情况，原始签名人因某种原因无法行驶签名权利时，需要将签名权委托给另外一个人代理签名21解决了这一问题。由于的代理签名的广泛用途，它引起了人们的极大兴趣22。虽然这些方案都满足代理签名的基本要求5，但仍存在一些问题5。文献4提出的方案解决了部分问题，但由于代理权没有时间限制，使得代理签名者能够在任何时间代替原始签名者签名。目前的代理签名方
46、案中代理权限的约定大多采用代理授权书的形式但都没有给出防止伪造代理授权书的方案。文献6中在ELGamal知识证明的基础上提出的代理签名方案，代理权虽然有时间限制，但由于代理权授权过程中，原始签名者直接向代理签名者传输了自己的私钥，因此是不安全的。基于此，本文提出了一种代理权有时间限制的基于ELGamal体制的代理签名方案，并在代理授权过程中，原始签名者没有直接将自己的私钥交给代理签名者，因而具有更好的安全性。代理签名是指原始签名者把他的签名权授给代理者，代理者代表原始签名者行使他的签名权。当验证着验证代理签名时，验证者即能验证这个消息的有效性，也能确定这个消息是原始签名者认可的签名。基于ELGamal体制，本节提出了代理权有时间限制的代理签名方案，约束了代理签名者得权利。是代理签名者不能随意使用代理权19，其一般过程如图4-1所示：原始签名者代理签名者验证着图4-1代理签名过程4.2.1 签名过程（1）系统初始化设p是一个使得在上的离散对数问题的大素数13，是一个本原元。原始签名者Alice的公钥为，代理签名者Bob的公钥为,其中，分别是Alice,Bob的私钥，公钥由公钥认证机构颁发证书。（2）授权协议Alice授权Bob在某时间t为代理签名人，具体协
