论文部分内容阅读
公钥密码体制使得密码学由传统的政府和军事应用领域走向商用和民用领域,使得现代密码学的商业价值和社会价值得到了广泛的认同。目前,RSA是使用最为广泛的一种公钥密码体制。但由于RSA算法是基于大素数分解难题的,特别是为防止各种攻击,其模长在不断增加,其主要运算是大整数的模幂和模乘,算法的运行速度较慢成为RSA的一个显著缺陷。因此,对大整数模幂和模乘算法以及取模算法的加速实现进行研究具有重要的理论意义和实用价值。本课题重点研究RSA算法的加速实现技术。当前针对RSA的研究主要包括密钥生成的优化、素性检测的优化、大整数模乘和模幂运算的优化等,本文重点研究大数模乘和模幂运算的优化问题。本课题受目前流行的蒙哥马利算法思想的启发,提炼出了模简化定理并予以证明,简化模逆运算,优化了蒙哥马利算法。本课题在研究了基于滑动窗口编码的算法之后,设计出新颖的限长游程编码,并将其应用于设计大整数的模乘和模幂运算实现算法。在完成算法设计之后,本文对算法的时间和空间复杂度进行了详细的分析。对比已有的相关算法效率,在理论上证明了算法的优越性。另外,还编程模拟实现了算法,通过实验证明了算法的效率确实有较大提高。本文还研究了行程编码,并试图将行程编码直接应用于设计大数模乘和模幂算法,经过分析得出行程编码并不适合应用于设计大数模乘和模幂算法的结论,从而进一步证明了本文设计的限长游程编码是应用于设计大整数的模乘和模幂算法的较优编码技术。本课题的完成,为公钥密码体制的进一步推广作出了较大的贡献,使得主要运算为大整数模幂运算的公钥密码算法的运算速度大大提高,具有广阔的商业价值。