快速大数模乘算法的研究与分析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)算法的易理解性、易实现性和易验证性等等。衡量一个算法的好坏,可以通过前面提出的三个方面进行综合评估。从多个候选
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 农业相关
限制150内