陕西理工学院毕业论文（设计）
结论
RSA算法的运算量很密集，采用组合算法可以比较好降低这一运算的复杂性，这样就可以通过一系列的简单运算的循环迭代完成整个RSA加解密过程。
论文以对RSA体制所采用的数论基础的研究为前提，结合多种RSA实现算法，对影响RSA效率的关键环节——模幂乘积的运算进行了深入的研究分析，并提出了改进方案。
1. 对密码学，信息安全做了简要的概述，介绍了当今密码学的基本动态，阐述了目前RSA加密体制的现状和不足，详细分析了RSA加密体制的数论基础以及面临的安全问题及对策。通过对数论基础（欧拉定理、乘法逆元等）以及加解密变换的研究，分析了RSA实现加解密的过程。结合当前针对RSA算法的攻击手段及对策，归纳总结了提高其安全性的原则。
2. 为了减少RSA模幂乘运算过程耗时，提高RSA加解密的速度，选择了当前RSA主要算法中的指数2进制化算法、基于乘同余特性的ＳＭＭ算法进行深入研究，分析总结出两种算法的优缺点并据此提出一种组合型的改进算法，在算法的改进一节中提及，我们下一步的研究工作将是以实验为基础比较所提出的改进算法与原有算法得出新算法效率有一定程度提高的结论，达到预先设想的结果。以新算法为核心设计一加密软件，并提出一基于单位局域网的邮件收发系统的RSA应用方案。
RSA虽然具有其它众多加密体制无法比拟的安全性能，但其工作效率一直影响其进一步发展，为进一步提高RSA的效率，增大适用范围，进一步需要开展的工作有：
１. 新的实现算法的研究
在现有的RSA实现算法中不论是以降低指数为手段减少替代次数进而提高运算效率的指数2进制化算法还是目前公认的以将普通的模余转换成模n同余并进行相应操作为手段的具有较高模乘性能的算法，都存在算法改进不足或适用范围受限制的问题。因此通过整合更多实现算法的优点研究新的实现算法是一个具有实际意义的方向。
２. 加密系统的配合应用研究
在当今还没有一个较RSA公钥密码系统更为优秀的密码系统出现之前，能够既利用RSA加密系统的高安全性又利用其他密码系统的高效性，进行加密系统的配合使用可以有效的解决问题。如单密钥加密算法的密钥管理是一个复杂过程，密钥的管理直接决定着它的安全性，因此采用公钥密码系统管理单钥加密系统的密钥，然后用单钥加密算法加密数据，这样就形成了两类密码体制的优点，即实现了加密速度快的优点，又实现了方便管理密钥的优点。
k
k
第27页 共41页
陕西理工学院毕业论文（设计）
致谢
首先感谢我的指导张文丽老师的细心指导和各论坛程序员朋友的支持与建议。
其次感谢陕西理工学院电信工程系的领导和老师，是他们的鼓励和教导使我逐渐成长为一名合格的大学毕业生。在学分攻读期间，王少华，尹继武，陈莉，王战备，龙光利，侯宝生，张文丽，，陈正涛等各位老师无私的将自己所掌握的知识传授于我；在毕设程序调试阶段他们给予许多热情的指导，在这里我对他们深表感谢。
真诚的感谢在毕设过城中给予我帮助的各位老师和同学，谢谢你们！
第28页 共41页
陕西理工学院毕业论文（设计）
参考文献
[1] 冯登国，计算机通信网络安全，[M]北京:清华大学出版社，2001.
[2] 黄元飞，陈麟，唐三平信息安全与加密解密核心技术[M]上海:浦东电子出版 社，2001
[3] 吴世忠，2003国内外网络与信息安全年度报告(上)，信息安全与通信保密，2004.1: P12}14 [4] 吴世忠，2003国内外网络与信息安全年度报告(心，信息安全与通信保密，2004.2: P9} 12 [5] 李煌.一种随机公开密钥加密算法及一种压缩算法 [J]. 科技情报开发与经济： 2006年01期 [6] 兰海兵,程胜利. RSA算法及其实现技术的改进研究 [J]. 交通与计算机： 2006年01期
[7] 程庭,张明慧,石国营. 一种基于DES和RSA算法的数据加密方案及实现 [J].河南教育学院学报(自然科学版)：2003年02期： 74-76
[8] 王国兵,杨建沾,谢贵. 基于RSA算法的网络安全体系构造 [J].武汉大学学报(自然科学版)： 2000年01期： 33-36
[9] 吕皖丽，钟城．数字签名方案分析[J]．广东科学院学报，2002，18(14)：161-165．
[10] 李继红．ElGamal型数字签名方案及其应用的研究[D]．西安：西安电子科技大学，1999． [11] 张先红编著．数字签名原理及技术[M]．北京：机械工业出版社．2004．1．
[12] 郑子伟,李翠华. 用类的RSA体制实现方案 [J].华侨大学学报(自然科学版)： 2003年03期： 102-105
[13] 杨维忠,李彤,郝林.RSA加密体制的安全隐患 [J].云南大学学报(自然科学版)： 2004年03期： 35-38
[14] Rivet R L, Shamir A，Ad leman L. A method for obtaining digital signatures and public key cryptosystems. Comm., ACM. [M] 1977
[15] Peter L Montgomery. Modular Multiplication Without Trial Division. [J] Mathematics of Computation, 1985, 44(170): S 19-521
[16] A.Atkin,F.Morain.Elliptic Curves and Primality Proving[J].Mathematics of Computation，1993,61(2):29-68．
[17] R.Schoof.Ell iptic Curves over Finite Field and the Computation of Square Roots Mod P[J].Mathematics of Computation,1985,53(4):483-494．
第29页 共41页
陕西理工学院毕业论文（设计）
附录A：英文资料及翻译
英文资料：
(It comes from Carlton R.Davis.IPSEC:Securing VPNS.北京：清华大学出版社，2002)
Cryptanalysis and Improvement of Digital Multisignature Scheme Based on RSA
SU Li (粟 栗) CUI Guohua (崔国华) CHEN Jing (陈 晶) YUAN Jun (袁 隽)
School of Computer Science and Technology, Hua zhong University of Science and Technology, Wuhan 430074, China
Abstract
Zhang et a.l proposed a sequential multisignature scheme based on RSA. The scheme has advantages of low computation and communication costs, and so on. However, we find a problem in their scheme that the verifier can not distinguish whether the multi-signature is signed by all the signers of the group or only by the last signer. Thus, any single signature created by the last signer can be used as a multisignature created by the whole group members. This paper proposes an improved scheme that can overcome the defect. In the new scheme, the identity messages of all the signers are added in the multisignature and used in verification phase, so that the verifier can know the signature is generated by which signers. Performance analysis shows that the proposed scheme costs less computation than the original scheme in both signature and verification phases. Furthermore, each partial signature is based on the signer’s identity certificate, which makes the scheme more secure.
Key words: Digital multisignature; Sequential multisignature; RSA cryptosystem; Cryptanalysis
Introduction
Multisignature is a joint signature generated by a group of signers. The group has a security policy that requires a multisignature to be signed by all group members with the knowledge of multiple private keys. Digital multisignatures should have several basic properties [1]: (1)Multisignatures are generated by multiple group members with the knowledge of multiple private keys. (2) Multisignatures can be verified easily by using the group public key without knowing each signer s public key. (3) It is computationally
in feasible to generate the group signature without the cooperation of all group members.
In 2003, Zhang et a.l[2]proposed a sequential multisignature scheme based on RSA, in which all the signers use a common modulus. The scheme has the advantages of low computation and communication costs, and can resist forgery and coalition attacks. The difficulty of
breaking the system is equivalent to that of factoring a large integer into its two large prime factors.
However, our cryptanalysis of Zhang et a.l’s scheme finds a serious problem; that is a ultisignature is verified by using the last signer’s public key instead of the group
第30页 共41页
陕西理工学院毕业论文（设计）
public key. As a result the verifier can not distinguish whether a signature is signed by a group of signers or only by the last signer, which violates the basic properties of sequential multisignature[1, 3, 4]. Therefore, we propose an improvement scheme to overcome this defect in this paper, so that the verifier knows who have created the multisignature. Performance and security analyses show that the new scheme not only keeps the advantages of original cheme, but also satisfies the definition of mltisignature and is more secure. 1 Review of Zhang et a.l s Sequential Multisignature Scheme 1. 1 System initialization
First the Trust Center (TC) selects two large prim p and q ,and computes the RSA modulus n=pq. Then, TC selects a random number as the public key which makes gcd (e,?(n))=1, where
gcd(·) is the greatest common divisor function, ?(n) =(p-1)(q-1),and 1 TC computes the private key d which makes ed≡1mod(?(n)). In the mean while, TC Upublishes the public key (n, e) and keeps (d, p, q) secretly. Define i(i=1,2,?,k)to be CCthe signer who has a exclusive certificate i(i=1,2,?,k),where i is public, and M the message to be signed. ?dh?H(C)s?h(modn)for every signerUi, and sends the iiiiTC computes and (C,s)certificate ii to each signer through a safe channel where H(·) is secure hash hCfunction, which generates a fixed length identity information i from the certificate i, sand i is the private key of the signer. Then, the corresponding signer verifies the ?eh?s(modn), and keeps si as a secret iivalidity of the certificate through the formula key if the formula holds. 1. 2 Generating partial signature of sequential multisignature As a preparation for generation of partial signatures, TC publishes the order of signers through their identity (C1,C2,...,Ck) . eStep 1 The signerU1selects a random number rcomputes T1?r1(1?r1?n) and 1(modn), m1?H(M,T1), D1?r1s1m1(modn), f1?1, Where T1 is the commitmentofU1;m1binds the commitment and plaintext by hash function;(D1, f1)is the signature of m1. Then the signerU1sends the partial signature (T1,m1,D1,f1) to the signer U2. Step 2 By analogy, if the (i-1)th partial signature is right, tUi (2?i mimie Ti?Ti?1ri(modn),mi?H(M,Ti),Di?Di?1rsii(modn),fi?fi?1hi(modn). Then Ui sends the partial signature (Ti,mi,Di,fi) to the signer Ui?1 . Ui?1 computes **i,hi=H (Ci), Ti*?Diefihim(modn)m?H(M,T?1ii). Ui?1 verifies the validity of the ith partial signature by comparing the value of mi* with mi. The partial signature is right if mi* equals mi; otherwise it is wrong. Step 3 Ui?1 creates the next partial signature. The above process is repeated untill the signer Uk creates the signature (Tk,mk,Dk,fk) and sends it to multisignature 第31页 共41页