快速大数模乘算法的研究与分析研究 应用数学专业VIP专享VIP免费

快速大数模乘算法的研究与分析摘要大数模乘对于RSA公钥密码体系和椭圆曲线公钥密码体系来讲，都是最基本的模乘。首先分析了Blakley大数模乘算法，对算法的复杂度和效率进行了分析，这种算法具有基础性但效率低下；其次，在Blakley大数模乘算法的基础上提出窗口模乘算法，采取简化处理和提高效率的思想，并且对于被乘数和乘数的处理，采取冗余二进制位技术，对乘数进行编码和预先计算，这样处理的结果使得计算复杂程度大大降低；最后，对窗口模乘算法进行实验，实验采取网上典型数据集，测试结果表明窗口模乘算法比Blakley大数模乘算法的效率更高。关键词大数模乘；算法分析；滑动窗口；算法复杂度ResearchandAnalysisofFastLargeNumberModularMultiplicationAlgorithmsAbstractLargenumbermodularmultiplicationisthemostbasicmodularmultiplicationforRSApublickeycryptosystemandellipticcurvepublickeycryptosystem.Firstly,Blakley'smodularmultiplicationalgorithmisanalyzed,anditscomplexityandefficiencyareanalyzed.Thisalgorithmisbasicbutinefficient.Secondly,onthebasisofBlakley'smodularmultiplicationalgorithm,awindowmodularmultiplicationalgorithmisproposed.Theideaofsimplifyingandimprovingefficiencyisadopted.Fortheprocessingofmultiplicandsandmultipliers,redundantbinarybittechnologyisadoptedtoprocessmultipliers.Theresultsofencodingandpre-calculationmakethecomputationalcomplexitygreatlyreduced.Finally,thewindowmodularmultiplicationalgorithmisexperimentedwithtypicaldatasetsontheInternet.ThetestresultsshowthatthewindowmodularmultiplicationalgorithmismoreefficientthanBlakley'slargemodularmultiplicationalgorithm.Keywordslargemodulusmultiplication;algorithmanalysis;slidingwindow;algorithmcomplexity1绪论1.1研究背景与意义随着当今社会网络化程度越来越高，人们在工作、生活中对信息的依赖程度越来越高，在网络化时代算法改变人们的工作和生活，对信息进行保护在网络日益渗透到人们生活方方面面的时代越来越重要，应用范围越来越普遍，只要有知识或信息的环境就有可能用到信息保护的算法，目前RSA算法成为应用最为广泛的一种公钥加密算法，当信息的容量和规模呈几何级数增加，人们对加密安全性和加密速度要求的提高，对信息加密问题也是提出了新的严峻的挑战，一般来说软件加密有重大发展的情况下，硬件实现加密算法成了密码学应用的一个趋势。本文所分析研究的快速大数模乘算法[1]在密码领域具有基础性地位，大数模乘作为公钥密码算法[2]（如RSA、DSA等）和数字签名算法最基本的运算和最基本的操作，大数模乘的效率特别是大数模乘的运算速度，对密码加密算法的功能和运用范围有重要的制约作用，大数模乘效率高和运算速度快则推动在更广泛的范围内发挥作用，反之运算效率低和运算速度慢则不具有推广价值。通过分析可知，模幂乘一般利用模平方和模乘来实现，其中模平方次数是固定的，而模乘次数是可以优化的，所以可以选出最优运算速度的模乘方法。比如，当前所有的诸如金融、银行、保险、电力等行业的数据多在网络上传输，用户的所有终端都在网络上运行，网络攻击成为了日益增长的威胁，每时每刻都有服务器、网站遭到网络攻击，受训严重。在这种情况下，必须增加公钥体制密钥长度来增加安全性，以应对超大型处理器、网络攻击等诸多挑战，这就意味着增加长度就导致更大的运算量，这样做会运算的效率，所以研究快速大数模乘算法的运算效率、缩短运算时间很重要。大数模乘是RSA、EIGamal、DSA等公钥密码算法和数字签名的基本运算，模乘算法是模幂算法的核心，其运算速度相对这些算法的实现起着重要作用，研究Montgomery等算法[3]并进行比较选出最优方法对密码加密等技术有着重大的意义。通过分析知道，快速大数模乘是利用模平方和模乘来实现，其中模平方次数是固定的，而模乘次数是可以优化的，这就为研究快速大数模乘提供了研究思想和实践方向，主流的研究焦点集中在减少乘数次数和提高模乘运算速度两个领域。本文...