RSA快速实现算法的研究与改进

《RSA快速实现算法的研究与改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学号：076862姓名：———————一一——●梁小英专业：密码学导师：董丝副塾握学院：垄堂暄2010年01月10日独创性(或创新性)声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。．、』驴本人签名：盔堕二基日期：Z口№．≥。∑关于论文使用授权的说明’学

2、位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在解密后遵守此规定)保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。·本人签名：鎏尘墓同期：羔堡f旦!弓二■’导师签名：日期：如～．弓、I．RSA快速实现算法的研究与改进摘要公钥密码体制使得密码学由传

3、统的政府和军事应用领域走向商用和民用领域，使得现代密码学的商业价值和社会价值得到了广泛的认同。目前，RSA是使用最为广泛的一种公钥密码体制。但由于RSA算法是基于大素数分解难题的，特别是为防止各种攻击，其模长在不断增加，其主要运算是大整数的模幂和模乘，算法的运行速度较慢成为RSA的一个显著缺陷。因此，对大整数模幂和模乘算法以及取模算法的加速实现进行研究具有重要的理论意义和实用价值。本课题重点研究RSA算法的加速实现技术。当前针对RSA的研究主要包括密钥生成的优化、素性检测的优化、大整数模乘和模幂运算的优化等，本文重点研究大数模乘和模幂运算的优化问题。本课题受目前流行的蒙哥马利算

4、法思想的启发，提炼出了模简化定理并予以证明，简化模逆运算，优化了蒙哥马利算法。本课题在研究了基于滑动窗口编码的算法之后，设计出新颖的限长游程编码，并将其应用于设计大整数的模乘和模幂运算实现算法。在完成算法设计之后，本文对算法的时间和空间复杂度进行了详细的分析。对比已有的相关算法效率，在理论上证明了算法的优越性。另外，还编程模拟实现了算法，通过实验证明了算法的效率确实有较大提高。本文还研究了行程编码，并试图将行程编码直接应用于设计大数模乘和模幂算法，经过分析得出行程编码并不适合应用于设计大数模乘和模幂算法的结论，从而进一步证明了本文设计的限长游程编码是应用于设计大整数的模乘和模幂

5、算法的较优编码技术。本课题的完成，为公钥密码体制的进一步推广作出了较大的贡献，使得主要运算为大整数模幂运算的公钥密码算法的运算速度大大提高，具有广阔的商业价值。关键词：公钥密码模乘模幂滑动窗口编码限长游程编码RESEARCH0NFASTIMPLEMENTATl0NOFRSAALGORITHMANDITSIMPROVEMENTABSTRACT■Thepublic—keycryptosystemextendsthecryptologyfromthetraditionalgovernmentandmilitaryapplicationstocommercialandciviliana

6、reas，makingthecommercialandsocialvaluesofmodemcryptographywidelyrecognized．Currently,RSAisthemostwidelyusedpublic—keycryptosystem．However,RSAalgorithmisbasedonlargeprimenumbersdecompositionproblems．Inparticular,topreventtheattacks，themoldlengthisincreasing．Itsmainoperationsarelargeintegermod

7、ularexponentiationandmodularmultiplication，andthealgorithm’SlowspeedbecomesaprominentRSAdefect．Therefore，itisworthwhiletoresearchonacceleratingthelargeintegermodularexponentiationandmodularmultiplicationalgorithm．Thispaperfocusesontheaccelerationof