快速大数模乘算法的研究与分析10.doc

《快速大数模乘算法的研究与分析10.doc》由会员分享，可在线阅读，更多相关《快速大数模乘算法的研究与分析10.doc（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、快速大数模乘算法的研究与分析摘要大数模乘对于RSA公钥密码体系和椭圆曲线公钥密码体系来讲，都是最基本的模乘。首先分析了Blakley大数模乘算法，对算法的复杂度和效率进行了分析，这种算法具有基础性但效率低下；其次，在Blakley大数模乘算法的基础上提出窗口模乘算法，采取简化处理和提高效率的思想，并且对于被乘数和乘数的处理，采取冗余二进制位技术，对乘数进行编码和预先计算，这样处理的结果使得计算复杂程度大大降低；最后，对窗口模乘算法进行实验，实验采取网上典型数据集，测试结果表明窗口模乘算法比Blakley大数模乘算法的效率更高。关键词大数模乘；算法分析；滑动窗口；算法复杂度Research an

2、d Analysis of Fast Large Number Modular Multiplication AlgorithmsAbstractLarge number modular multiplication is the most basic modular multiplication for RSA public key cryptosystem and elliptic curve public key cryptosystem. Firstly, Blakleys modular multiplication algorithm is analyzed, and its co

3、mplexity and efficiency are analyzed. This algorithm is basic but inefficient. Secondly, on the basis of Blakleys modular multiplication algorithm, a window modular multiplication algorithm is proposed. The idea of simplifying and improving efficiency is adopted. For the processing of multiplicands

4、and multipliers, redundant binary bit technology is adopted to process multipliers. The results of encoding and pre-calculation make the computational complexity greatly reduced. Finally, the window modular multiplication algorithm is experimented with typical data sets on the Internet. The test res

5、ults show that the window modular multiplication algorithm is more efficient than Blakleys large modular multiplication algorithm.Key wordslarge modulus multiplication; algorithm analysis; sliding window; algorithm complexity111 绪论1.1 研究背景与意义随着当今社会网络化程度越来越高，人们在工作、生活中对信息的依赖程度越来越高，在网络化时代算法改变人们的工作和生活，对

6、信息进行保护在网络日益渗透到人们生活方方面面的时代越来越重要，应用范围越来越普遍，只要有知识或信息的环境就有可能用到信息保护的算法，目前RSA算法成为应用最为广泛的一种公钥加密算法，当信息的容量和规模呈几何级数增加，人们对加密安全性和加密速度要求的提高，对信息加密问题也是提出了新的严峻的挑战，一般来说软件加密有重大发展的情况下，硬件实现加密算法成了密码学应用的一个趋势。本文所分析研究的快速大数模乘算法1在密码领域具有基础性地位，大数模乘作为公钥密码算法2（如RSA、DSA等）和数字签名算法最基本的运算和最基本的操作，大数模乘的效率特别是大数模乘的运算速度，对密码加密算法的功能和运用范围有重要的

7、制约作用，大数模乘效率高和运算速度快则推动在更广泛的范围内发挥作用，反之运算效率低和运算速度慢则不具有推广价值。通过分析可知，模幂乘一般利用模平方和模乘来实现，其中模平方次数是固定的，而模乘次数是可以优化的，所以可以选出最优运算速度的模乘方法。比如，当前所有的诸如金融、银行、保险、电力等行业的数据多在网络上传输，用户的所有终端都在网络上运行，网络攻击成为了日益增长的威胁，每时每刻都有服务器、网站遭到网络攻击，受训严重。在这种情况下，必须增加公钥体制密钥长度来增加安全性，以应对超大型处理器、网络攻击等诸多挑战，这就意味着增加长度就导致更大的运算量，这样做会运算的效率，所以研究快速大数模乘算法的运

8、算效率、缩短运算时间很重要。大数模乘是RSA、EIGamal、DSA等公钥密码算法和数字签名的基本运算，模乘算法是模幂算法的核心，其运算速度相对这些算法的实现起着重要作用，研究Montgomery等算法3并进行比较选出最优方法对密码加密等技术有着重大的意义。通过分析知道，快速大数模乘是利用模平方和模乘来实现，其中模平方次数是固定的，而模乘次数是可以优化的，这就为研究快速大数模乘提供了研究思想和实践方向，主流的研究焦点集中在减少乘数次数和提高模乘运算速度两个领域。本文重点研究提高模乘运算速度。1.2 研究现状当前国内外对模乘算法的研究是基于历史的，历史上对模乘算法的研究已经比较丰富，有许多成果和

9、应用。当前对大数模乘研究的重点转向了对海量数据的处理，对效率的要求，对计算时间的要求方面，要求大数模乘既要快速，也要准确，还要处理量达到海量级别。大数模乘对于RSA公钥密码体系和椭圆曲线公钥密码体系来讲4，都是最基本的模乘，最底层的运算都是大数模乘，正是由于大数模乘有这样一个基础性的地位，不可回避的运算，当前世界上研究密钥的科研人员主要关注着RSA公钥密码体系和椭圆曲线公钥密码体系这两个大方向进行研究5。一个方向，是RSA公钥密码体系，重点是研究模幂运算，即连续的模乘运算模式；另外一个方向，是椭圆曲线公钥密码体系，重点研究大数模乘优化6，解决椭圆曲线公钥密码体系最底层模乘运算单元的有关问题，更

10、多的运用Montgomery模乘方法。在国内研究方面，各个领域的科研人员和理论研究人员把研究是视野停留在比较宽泛的领域7，第一类是将具体的幂运算算法作为了处理对象，对于幂运算算法的私钥进行改进计算，来提高计算效率和计算速度。第二类是对比分析其他一些先进的模幂运算，从理论视角和操作层面二个角度进行了研究，来提高计算效率和计算速度。在国外研究方面，研究的历史比国内更长，研究的点多线长，综合应用的程度也必将高，比如有利用数字剩余系统叠加的方式8，也有研究单词模乘运算的方法9。最后要特别强调一点，大数模乘当前的研究重点有转向硬件设计和实现大数模乘的趋势，国内外都有相当成热的研究方法和实现手段。比如利用

11、VLSI上，通过FIPS方式实现大数模乘控制模块及其数据通路10。1.3 论文结构本文研究主要内容的重点放在对快速大数模乘算法设计上，来提高计算效率和计算速度。改进的算法将具有一定的实用价值。围绕这样的重点研究内容，本文主要研究提纲包括五个方面：一是快速大数模乘算法概述，二是快速大数模乘算法原理，三是快速大数模乘算法设计，四是快速大数模乘算法实验，五是全文总结。本论文将按照这样一个论文结构和上述研究重点展开研究。2 快速大数模乘算法设计原理2.1 模乘算法分析快速大数模乘算法的模乘运算通常包括移位、加法和减法操作而实现的11，通常包括典型的两个步骤：第一步先通过移位、加法求出两数的积；第二步再

12、用减法实现模运算。当前运用至今的典型计算方法主要是Blakley算法12、Montgomery乘法算法13等。Blakley于1983年首先提出了加法型模乘算法，Blakley在设计这个算法的思路是：运用了转化思路，就是将乘法转换为加法实现。通过将模乘限制在一定的域范围内，转换为许多加法运算，这个限制就是要求最终结果。这样对操作过程提出了限定，每次计算都需要对中间结果C进行模化简。根据文献1，可以得到Blakley算法如下：对于上面的这个Blakley算法进行分析，Blakley算法最基本的运算是加法运算，没有涉及到乘除法运算，在整个运算过程中按照位来处理，虽然Blakley算法使用加法替代了

13、乘法而降低了复杂性，但效率仍然不高，共进行k次的k位移位、次k位的移位，2k次k位的比较和平均k次k位的减法。2.2 基于窗口技术模乘新算法本文在这些快速模乘乘法的基础上，考虑设计基于滑动窗口的快速模乘算法，并实验算法的运算效率。由于Blakley算法最基本的运算是加法运算，Blakley算法的计算复杂性高，这样的结果导致在整个运算过程中按照位来处理，效率比较低下。为了解决快速模乘Blakley算法效率低的问题，根本上是减少运算周期，可以利用窗口技术，滑动窗口模乘算法14，借鉴了通信算法的问题处理方法。窗口技术在大数模乘领域应用十分广泛。新的基于窗口技术的模乘算法可以称为窗口模乘算法15，采取

14、这样的简化处理和提高效率的思想，把被乘数和乘数都进行进制转化，也就是计算机能够识别的二进制，若从低位到高位把指数分解成0窗和非0窗，设d为最大窗口的长度，则供需1次平方和次乘法，这样处理的结果使得计算复杂程度大大降低16。2.3 本章小结本章从大数模乘算法分析入手，首先分析了大数模乘算法的设计和实现，而后计算了大数模乘算法的复杂程度，由于大数模乘算法没有设计乘除法，从而导致算法的复杂程度高，为了解决这一个问题提出了运用窗口技术，实现了窗口模乘算法17，其复杂程度大大降低，效率大大提高。3 快速大数模乘算法设计3.1 基于MATLAB实现快速模乘算法在Blakley加法型模乘算法的基础上，实现了

15、基于窗口技术的模乘算法，这个算法的思路是：在Blakley加法型模乘算法的框架下，把被乘数和乘数都进行进制转化，也就是计算机能够识别的二进制，这样操作的复杂程度大大降低18。基于窗口技术的模乘算法如下：为方便叙述描述基于滑动窗口的快速模乘算法，本文将模N设置成1024，窗口宽度设置为4，那么具体的算法如下所示：3.2 测试算法时间与效率具体算法的时间与效率的体现主要在以下三个方面：（1）算法在执行过程中所消耗的时间；（2）算法在执行过程中所占资源的大小，例如，占用内存空间的大小；（3）算法的易理解性、易实现性和易验证性等等。衡量一个算法的好坏，可以通过前面提出的三个方面进行综合评估。从多个候选

16、算法中找出运行时间短、资源占用少、易理解、易实现的算法。然而，现实情况却不尽人意。往往是，一个看起来很简便的算法，其运行时间要比一个形式上复杂的算法慢的多；而一个运行时间较短的算法往往占用较多的资源。本节在上述内容研究和分析的基础上，对算法进行了测试，具体测试主要代码如附录所示。3.3 本章小结本章在上述第三章研究的基础上实验了基于窗口技术的模乘算法，算法实验的平台采取了MATLAB实验环境，从网上下载了计算的数据集合，两种算法的测试结果正确，但基于窗口技术的模乘算法对同样数据集合的运算时间短，计算效率高。4 快速大数模乘算法实验4.1 实验过程在完成具体算法的设计和实现后，并单独对算法进行了

17、时间测试和效率测试，为了进一步考察算法的实用性，这里对本文研究的算法进行了全面的实验。本文选取了四组数据进行大数乘法实验，具体的实验结果如图4.1简单计算的大数乘法与图4.2幂次方大数乘法所示。如图4.1所示，本文对于简单计算的大数乘法计算了19*22*650*950*4560*7680 =9.51515151E12与65*78*490*6870*9900*12340*53640=1.118407E23两个等式。其中E12表示10的12次方；这一结果本文使用计算器进行了验证，表征了幂次方大数模乘算法的正确性。图4.1简单计算的大数乘法图4.2幂次方大数乘法表4.1 算法效率对比算例算式Blak

18、ley算法(单位：s)基于窗口技术模乘新算法(单位：s)效率提升/%case 119*22*650*950*4560*7680=9.51515151E126.435.3217.26case 265*78*490*6870*9900*12340*53640=1.118407E239.687.8916.43case 3265=3.6893488147419E197.236.5612.08case 4280=1.20892581961463E2415.6413.759.26图4.3 算法效率对比柱形图如上图4.2所示，本文对于幂次方大数乘法计算了265=3.6893488147419E19与280=

19、1.20892581961463E24二个幂次方大数乘法大数乘法，并且对于简单计算的大数乘法与幂次方大数乘法本文对于四个计算的效率进行了统计，具体的二种算法的效率对比如表4.1所示。对于四个算式的时间来说，基于窗口技术模乘新算法效率都有所提升，并且本文将四个式子的平均运算时间绘制成了柱形图，具体算法效率对比柱形图图形如图4.3所示。如表4.1以及图4.3所示，式子19*22*650*950*4560*7680=9.51515151E12效率提升17.26%，式子65*78*490*6870*9900*12340*53640=1.118407E23效率提升16.43%，式子265=3.68934

20、88147419E19效率提升12.08%，式子280=1.20892581961463E24效率提升9.26%，四个式子的平均效率得到了13.75%，可以看出来，得到了较好的提升。4.2 实验结论通过本章第一节实验过程，本文第三章所设计的算法和对应的算法代码在计算矩阵数据上，结果是正确的；同时，本文选取了四组数据进行大数乘法实验，证明了基于窗口技术模乘新算法大数算法的准确性，同时对于二种算法的效率也进行了统计，得到了基于窗口技术模乘新算法效率获得了较好提升的结论。4.3 本章小结本章主要是在第三章选择实验数据集合的基础上，提供实验用文本文件，使用MATLAB导入数据，利用MATLAB计算平台

21、完成程序设计和实现，实验结论表明新的算法效率提高的程度比较大，特别是遇到较大规模数据集合时效率提高的更加明显。5 结束语本文首先阐释了快速大数模乘算法研究的背景、意义和现状，大数模乘对于RSA公钥密码体系和椭圆曲线公钥密码体系来讲，都是最基本的模乘，最底层的运算都是大数模乘，具有最基础的作用，另外大数模乘是公钥密码算法和数字签名最基本的算法，其运算速度相对这些算法的实现起着重要作用，通常利用模平方和模乘来实现，其中模平方次数是固定的，而模乘次数是可以优化的。其次，快速大数模乘算法典型的计算方法包括Blakley算法、Montgomery乘法算法等，采用移位、加法和减法来实现，但这些算法的复杂程

22、度高，计算效率低。第三，在分析了Blakley大数模乘算法的基础上，对算法的复杂度和效率进行了分析，这种算法具有基础性但效率低下，在Blakley大数模乘算法的基础上提出了窗口模乘算法，采取这样的简化处理和提高效率的思想，把被乘数和乘数都进行进制转化，也就是计算机能够识别的二进制，这样处理的结果使得计算复杂程度大大降低。最后，对窗口模乘算法进行实验，实验采取网上典型数据集，测试结果表明窗口模乘算法比Blakley大数模乘算法的效率更高。在本文研究的基础上，下一步，主要着眼无线网络通信技术的发展前沿加密技术，解决人们对无线网络安全的担忧，提高无线网络的安全问题，研究高效的无线网络加密算法，这中间

23、要用到模乘算法这个基础，利用这次的研究知识继续在这个方面有所作为。参考文献1 Blakley G R. A computer algorithm for calculating the product AB module M J. IEEE Transactions on Dependable and Secure Computing, 1983, 32(5), 497500.2 Montgomery PL. Modular multiplication without trial divisionJ. Mathe matics of Computation, 1985, 44(170): 5

24、91521. 3 Koc C K,Acar T,KaliskiB S. Analyzing and comparing montgomery multiplication algorithmsJ. IEEE Micro, 1996, 16(3):2633.4 殷新春,张宝. 公钥密码中大数模幂的并行窗口算法J.计算机工程与应用，2004,02(79):1417.5 赵学秘, 陆洪毅, 戴葵. 一种高性能大数模幂协处理器SEAJ. 计算机研究与发展，2005.37(5):3645.6 陈勤, 周律, 张旻. 一种新的加法型快速大数模乘算法J.计算机工程,2007,12(06):2227.7 芦殿

25、军,张秉儒. 基于RSA体制的大数模幂乘算法J.青海大学学报, 2007, 48 (7):5561.8 芦殿军. 基于离散对数体制的大数模幂乘算法的软件实现方法J.青海师专学报(教育科学), 2007(01): 3646.9 伍红茹，黄欣阳，刘双根.最佳滑动窗口编码法及其在快速模幂乘中的应用J.南昌大学学报(工科版), 2005(2):8487.10 刘松.基于移动终端的RSA快速算法研究与实现J.华中科技大学学报,2008,06(73):1619.11 William Stallings.密码编码学与网络安全原理与实践(第四版)M,北京：电子工业出版社，2012,03(24): 548551

26、.12 Rivest, A. Shamir, L. Adelman. A Method for Obtaining Digital Signature and Public-KeyCryptosystemsJ. Communications ACM, 1978(4):120126.13 ElGama1, T. A public key cryptosystem and a signature scheme based on discrete logarithmsJ. IEEE Trans. Information Theory, 1985, 31(96): 46947214 N. Koblit

27、z. Elliptic curve cryptosystems J. Mathematics of Computation, 1987, 48(16): 203209.15 Mi11er.V. Uses of elliptic curve in cryptography J. In CRYPTO85. Lecture Notes in Computer Science, 1986(75):417426. 16 李德庆.椭圆曲线密码体制的研究与实现D. 陕西：西安电子科技大学, 2008:236.17 丁宏,郭艳华.快速大数模乘算法及其应用J. 小型微型计算机, 2003(68):1367137

28、0.18 郭炜.基于二进制域ECC密码算法的研究与硬件实现D. 上海交通大学, 2007:6063.附录：测试算法效率代码：publicMyBigInteger multiply(MyBigInteger bigtwo) String returnNum=null; booleanpositive =false; if(bigtwo.bignum.charAt(0) =-&this.bignum.charAt(0) =-) | (!(bigtwo.bignum.charAt(0) =-) & !(this.bignum.charAt(0) =-) positive =true; if(bigt

29、wo.bignum.charAt(0) =-) bigtwo.bignum = bigtwo.bignum.substring(1);if(this.bignum.charAt(0) =-) this.bignum =this.bignum.substring(1);inta =this.bignum.length();intb = bigtwo.bignum.length(); String s1 =newStringa; String s2 =newStringb; int mulAll =newinta + b -1; for(inti =0; i a; i+) s1a - i -1 =

30、this.bignum.substring(i, i +1);for(inti =0; i b; i+) s2b - i -1 = bigtwo.bignum.substring(i, i +1);if(a b) inttemp = a; a = b; b = temp; String stemp = s1; s1 = s2; s2 = stemp;for(inti =0; i a; i+) for(intj =0; j b; j+) mulAlli + j +=Integer.parseInt(s1i) * Integer.parseInt(s2j);for(inti =0; i 9) while(mulAlli 9) mulAlli -=10;mulAlli +1 +=1;returnNum =;for(inti = mulAll.length -1; i =0; i-) returnNum = returnNum + mulAlli;if(positive) returnnewMyBigInteger2(returnNum);elsereturnNum =-+ returnNum;returnnewMyBigInteger(returnNum);