..................................................................................................30 5.2 BARRETT 缩减.................................................................................................................31 5.3 MONTGOMERY 缩减 ........................................................................................................336 大整数除法实现 ...................................................................................................................37 6.1 使用减法替换除法运算 ................................................................................................37 6.2 模拟笔算除法 ................................................................................................................387 大整数幂运算实现 ...............................................................................................................43 7.1 单数位幂乘 ....................................................................................................................43 7.2 K—RAY 幂乘...................................................................................................................45 7.3 滑动窗口幂乘 ................................................................................................................45结论 ..........................................................................................................................................47参考文献 ..................................................................................................................................48致谢 ..........................................................................................................错误!未定义书签。
附录 A ......................................................................................................................................49 IV 1 绪论1.1 题目的背景 科学技术和网络的发展使计算机深入到了各行业的方方面面,计算机在带来方便和提高了工作效率的同时却也带来了各种各样的新问题,其中信息安全问题最为突出,随着计算机信息安全要求的不断提高 计算机保密系统已变得越来越重要。
随着香农定理的发表,信息安全技术得到了迅猛的发展。
密码学应用不再是局限于军事、国防等有限领域,而是迅速的走进了千家万户。
RSA、ElGamal、DSA、ECC 等公钥密码算法和数字签名等算法得到了快速发展。
其实现都是建立在大整数运算的基础上,耗时的大整数乘法、除法、模乘、幂运算、模幂乘等运算更是被上述算法大量使用。
而计算机微机的字长限制对信息安全中大整数的操作,带来了巨大的困难。
它们的运算速度对这些算法的高效实现起着重要的作用,如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。
1.2 国内外研究状况 长期以来,各方面的工作者对大数基本运算的快速实现问题进行了大量研究,主要围绕模幂算法设计与优化、模乘算法设计与优化、专用芯片设计等,并且已经取得不少研究成果。
模幂通常都转化为一系列模乘和模平方运算,目前较好的算法已经能够将 1次 n 比特数的模幂运算转化为约 5n/4 次 n 比特的模乘运算,再减少模乘的次数的难度很大,因此,提高模乘的速度是模幂快速实现的关键1。
目前,模乘主要有估商型、加法型和 Montgomery 型 3 类方法。
1960 年,Pope 和 Stein 就提出了采用估商方法将模乘转化为一系列乘法和除法进行计算的思想;1981 年,Knuth 具体给出了一种转换为乘法和除法的估商型模乘算法2;1987 年,Barrett 提出了一种转换为乘法和加法而没有除法的估商型模乘算法3。
1983 年,Blakley 提出了一种加法型模乘算法,其设计思想是将模乘转换为一系列加法。
为减少加法次数,人们提出了窗口模乘算法和滑动窗口模乘算法,并相继提出不少改进方法,获得较理想的结果。
1 1985 年 Montgomery 提出了一种计算模乘的有效算法,其设计思想是将普通模乘转换为易于计算的特殊模乘4。
此后,人们提出了不少基于 Montgomery 思想的改进算法,并得到了广泛的实际应用。
大多数情况下,一种算法的理论描述和实际实现之间有不小的差距,是两个完全的不同的概念,因此,众多学者为这些优秀算法的具体的软、硬件实现、优化付出了辛勤的汗水,在软件实现方面这些算法多数被包含在某些算法库中,其中也有不少是开放源代码的算法函数库,最著名的就是 GNU 的号称地球上最快的多精度大数库 GMP,还有Miracl、openssl、cryptopp、cryptlib、flint 等优秀的算法库,而我国的郭先强先生的HugeCalc.dll 库也同样出名,虽然它不是开放源码的,但它的速度赶得上 GMP 甚至在某些方面超越了 GMP。
然而,正如 Tom St Denis 所说,不存在一个易懂的大数库!从目前收集到的信息看,凡是效率高的算法实现,要么结构复杂、层次庞大,要么编码风格奇特;所有速度快的库都使用了汇编,同时大部分都使用了 MMX、SSE2、SIMD 系列指令作加速,也对多核心 CPU 进行了优化,使用了多线程等,甚至运行时监测 CPU 类型而使用相关的特殊优化,最大限度地榨取 CPU 的性能。
然而,这些很好的优化技术却大大地降低了代码的可读性,极大地提高了理解、学习的门槛。
在学术专著方面,大数算术也备受欢迎,Donald E.Knuth 也用了一整本书—— 《TheArt of Computer Programming Volume 2》来从理论的角度讲述了多精度算术,并讲解了高效的算法背后关键的数学概念;《Handbook of Applied Cryptography》6也讲述了应用 7密码学相关的大数算术算法的有效实现; 《Kryptographie in C und C》 和 而 《BigNumMath: Implementing Cryptographic Multiple Precision Arithmetic》等则从编码学的角度对大数算术进行了多方面的讨论。
1.3 本文研究内容 本文基于 32 位的系统,首先采用模块化的思想建立大整数运算库的基础框架,在实现一些辅助函数后在此运算库框架上讨论并实现多精度大整数的基本加法、减法、乘法、平方算法、缩减算法、模乘、模幂乘等算法。
本文讨论的所用程序均采用 C/C语言编写,所采用的优化也均建立在 C/C语言这一层面上,在保证算法有足够高的效率的同时力求代码清晰易懂,函数接口简单明了,具有可移植性和稳定性。
2 2 大整数的结构 大整数运算是一些相当复杂的运算,本文要实现的是大整数基本运算,采用模块化思想按照层次结构来设计及实现一些其它的辅助函数,而不是把它们内嵌在算法函数内,这样既能够避免算法函数的程序代码的过分冗长,使代码清晰易懂、突出算法过程又能够使程序易于测试、排错、更新和复用。
由于本文是介绍大整数的基本算法,在本文开始之前只介绍一些关键的辅助函数,其它辅助函数是在相关算法实现的时候再简略介绍它的功能。
2.1 大整数的存取结构2.1.1 大整数结构分析 大数的存储方式主要是有两种——链式存储方式和顺序存储方式。
一是采用链表作为存储结构,这种方式可以适应不定长度的大数,这种方式的存储空间包括整数表示部分和链表指针部分,其空间利用率不高,而且其
上一篇:
企业日常工作排班系统【毕业论文,绝对精品】
下一篇:
2012邮政局信息公开总结