【VC++开源代码栏目提醒】:网学会员VC++开源代码为您提供大整数乘法的实现与分析(毕业论文 代码) - 课程设计参考,解决您在大整数乘法的实现与分析(毕业论文 代码) - 课程设计学习中工作中的难题,参考学习。
大整数乘法的实现与分析 摘 要 随着计算机信息安全要求的不断提高,密码学被大量应用到生活中。
RSA、ElGamal、DSA、ECC 等公钥密码算法和数字签名算法都建立在大整数运算的基础上,比较耗时的大整数乘法、除法、模乘、幂运算、幂乘等运算却被上述算法大量使用,它们的运算速度对这些算法的高效实现起着重要的作用,如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。
本文基于 32 位的系统,首先采用模块化的思想建立大整数运算库的基础框架,在实现一些辅助函数后在此框架上讨论并实现多精度大整数的基本加法、减法、乘法、除法、平方算法、缩减、模乘、模幂乘等算法。
所用程序均采用 C/C语言编写,所采用的优化也均建立在 C/C语言这一层面上,在保证算法有足够高的效率的同时力求
代码清晰易懂,函数接口简单明了,具有可移植性和稳定性。
关键词:多精度大整数,Comba,Montgomery,二分查找,笔算注:本设计(论文)题目来源于企业项目。
I Abstract Nowadays as computer information security requirements improve continuously thecryptology has been widely applied to life. Public key cryptographic algorithms and digitalsignature algorithms such as RSA ElGamal DSA ECC are all base on multiple precisionarithmetic. Multiple precision multiplication Division modular multiplication exponen-tiation modular exponentiation which need more working time is used by public keycryptographic algorithms widely their speed is very important to the implementations of thosealgorithms. How to fast implement those arithmetic above is the hot topic in the public keycryptographic field. This paper is based on the 32 bit system. First of all we found the modular foundation ofmultiple precision arithmetic library After some auxiliary function is formed we discuss andimplement the multiple precision integer basic addition Subtractionmultiplication kinds of square algorithmsdivisionreduction and some relational function. All thealgorithm discuss in this paper is implement entirely in portable ISO C/Cand theoptimization of those algorithms implementations is built on the C/C language level. thealgorithm has high enough to ensure the efficiency of the code at the same time strive toclearly understand simple interface function with portability and stability. Key
words: Multiple Precision IntegerCombaMontgomeryBinary search Written calculation II 目录1 绪论 ........................................................................................................................................1 1.1 题目的背景 ......................................................................................................................1 1.2 国内外研究状况 ..............................................................................................................1 1.3 本文研究内容 ..................................................................................................................22 大整数的结构 .........................................................................................................................3 2.1 大整数的存取结构 ..........................................................................................................3 2.1.1 大整数结构分析 .......................................................................................................3 2.1.2 大整数结构 ...............................................................................................................4 2.2 预定义的变量 ..................................................................................................................5 2.3 大整数基本函数定义 ......................................................................................................5 2.3.1 大整数初始化操作 ...................................................................................................5 2.3.2 大整数的销毁操作 ...................................................................................................6 2.3.3 大整数的扩展 ...........................................................................................................6 2.3.4 大整数的输入和输出函数 .......................................................................................6 2.4 大整数的移位函数 ..........................................................................................................7 2.4.1 字移位运算 ...............................................................................................................7 2.4.2 比特移位运算 ...........................................................................................................93 大整数加法和减法实现 .......................................................................................................13 3.1 符号相同的加法运算 ....................................................................................................13 3.2 符号不相同的加法运算 ................................................................................................164 大整数乘法实现 ...................................................................................................................19 4.1 笔算乘法........................................................................................................................19 4.2 使用 COMBA 方法的快速乘法 ......................................................................................22 4.3 平方算法 ........................................................................................................................24 4.3.1 笔算平方算法 .........................................................................................................25 4.3.2 Comba 思想的平方算法.........................................................................................27 III5 大整数模缩减实现 ...............................................................................................................30 5.1 模 2 的幂 ........................................................................................................................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 大整数结构分析 大数的存储方式主要是有两种——链式存储方式和顺序存储方式。
一是采用链表作为存储结构,这种方式可以适应不定长度的大数,这种方式的存储空间包括整数表示部分和链表指针部分,其空间利用率不高,而且其存储空间是离散的,所以随机访问效率也不高,而且频繁的堆操作和引用操作势必大量增加开销,不利于编译器优化速度;另外,根据内存管理方式的不同,顺序存储方式可以再分为静态存储方式和动态存储方式。
静态存储方式数组的大小是事先已经知道的,适合知道大小的整数运算。
而因其数组长度是固定不变的,在运算的时候容易造成溢出。
所以其不适合不定长度的整数运算。
而动态方式,其可以动态分配内存空间。
可以根据整数位数的变化调整大小。
其是最
常用的顺序存储方式,而且顺序存储方式是连续分配空间,所以其可以实现随机访问,提高速度,因为存储空间就是整数本身,没有其他额为开销,所以空间利用率也较高。
由于受到计算机字长的限制制约着大整数的运算,所以必须要解决大整数表示问题 , 通 常 是 采 用 B 进 制 表 示 , 如 x x x x ...x , 其 表 示 为 : 0 1 2 n b n 1 n2x x b x b x 2 b ... x n 1 b x n ( x 0 0 ) ( 0 i n )必 n 1 0 1 ,而且系数 x 0须是计算机可以表示的常数。
在基选择上,最容易想到也是最直接易懂的是用整数数组来保存大数,数组的每个元素保存大数的一个十进制数字,这种方式操作比较简单,但这种方式需要较多的额外运算,而且效率明显不高,也需要比较多的存储空间;效率比 3较高的,被采用的比较多的方式是用 B 进制数组存储大数,即把大数转化 B 进制表示,数组的每个元素存储这个 B 进制数的一个 B 进制的数位,这样既方便计算机处理又提高了内存的利用率,同时缩短了大数的实际表示长度,减少了循环的次数,有利于提高效率。
为了更好的适应各种算法的需要及避免过度浪费存储空间,本文采用多精度的方式。
1985 年,西安交通大学的王永祥副教授曾经采用过万进制的方法表示大数,并实现了自己的大数算法11。
根据万进制的原理,本文决定将整数进制 B 取为 2 的某次幂。
本文是基于 32 位系统,
VC有__int64 这样的 64 位整数类型,但 32 位硬件上毕竟不能直接处理 64 位整数,那势必需要附加内部操作来完成。
为了匹配硬件操作,取 B 进制为半个 CPU 字长的 unsigned short int 型,即 216 进制. 由于 m 位的数乘以 n 位的数最多将产生 mn 位的数所以两个 216 进制数位的乘积可以用一个 232 数来保存而不超出 CPU的字长。
2.1.2 大整数结构 为了模块化编程程序结构清晰易懂。
本文在开始之前先对大整数做一个结构封装,使用一个结构体来表示大整数。
标示符 MBigInt 表示一个多精度的大整数结构:typedef struct / 定义大整数的结构 / long int alloclen / 记录数组已经分配总的空间大小 / long int length / 记录大整数的长度,即系数的个数 / int sign / 记录大整数的符号 / un_short pBigInt/ 指向大整数的数据的指针,即指向系数的地址 / MBigInt 上面大整数封装的结构中,分别记录大整数分配到的空间 alloclen 大小和已经在使用到的空间 length 大小。
使用这种结构能够有效地管理内存,减少堆操作的次数,减少相关操作带来的性能损失;通过一个指针来指向保存大整数的数据的数组,这样有利于内存的动态调整,可以不移动数组的任何元素而交换两个大整数,其只需要交换三个内置的整数值和一个指针就可以了。
本文所讨论的大整数的数位是按照低位在前的方式存放,则按从低位到高位的顺序把大整数的数位按下标从小到大顺序存放到数组中去,也 4就是十进制表示方式相反方向,这样既有利于扩展大数的长度也有利于缩减。
2.2 预定义的变量 因为在编程的时候很多的变量字符比较长,很容易略写某个字符,造成编程错误,所以本文首先对一些变量进行预定义。
typedef unsigned short int un_short /16 位数的声明符号/ypedef unsigned long int un_long /32 位数的声明符号/define BIT_PRE_WORD 16UL / 每个单精度数字含有的 bit 数 // 定义信号标识 /RETU.