武汉纺织大学2012届毕业设计论文
大多数的编译器只能支持到32位（或64位）的整数运算，即我们在运算中所使用的整数必须小于等于32位，即0xFFFFFFFF，这远远达不到RSA的需要，于是需要专门建立大数运算库，来解决这一问题。
最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低。当然其优点是算法符合人们的日常习惯，易于理解。 另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。
这里我们采用了一种介于两者之间的思路：将大数看作一个N进制数组，对于目前的32位系统而言，N可以取2的32次方，即0x100000000，假如将一个1024位的大数转化成0x10000000进制，它就变成了32位，而每一位的取值范围是0－0xFFFFFFFF。我们正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机来说，实际上是一回事，但是我们完全可以针对unsigned long数组进行“竖式计算”，而循环规模被降低到了32次之内，并且算法很容易理解。
但考虑到乘法和除法，都要进行扩展才能进行快速的计算（如果把除法变减法而不扩展，速度将慢的无法忍受）。所以我们将N取2的16次方的，即0xFFFF。每一位用unsigned short来表示，当进行乘除运算时，将short扩展成long，这是编译器所支持的，所以运算起来，比较快。
2 大数的各种运算
这些运算都是常见的，同时也是常用的。要实现RSA算法，就必须先实现大数的这些运算。
1) 大数的比较。两个无符号或有符号的大数进行大小比较。大数和一般整数进行比较。大于，等于，小于，返回值各异，以区别比较结果。
2) 大数的赋值。将一个大数的值，符号等，逐位赋给另一个大数。将一般整数的值，符号等赋给一个大数。
3) 大数的加法。两个大数从低位到高位逐位相加，要考虑到进位的问题。
13
武汉纺织大学2012届毕业设计论文
或大数与一般整数的相加。
4) 大数的减法。两个大数从低位到高位逐位相减，要考虑到借位的问题。或大数与一般整数的相减。
5) 大数的乘法。两个大数的乘法，从一个大数的低位到高位，逐位与另一个大数相乘，然后将结果低位对齐相加，要考虑进位，类似于普通的竖式乘法。或大数与一般整数的乘法。
6) 大数的除法。两个大数的除法，从一个大数的高位到低位，逐步与另一个大数相除，要考虑借位，类似于普通的竖式除法。或大数与一般整数的乘法。 7) 大数的取余。两个大数的取余，类似于大数的除法，只是当除到底时，返回的是余数而已，也存在借位的问题。或大数于一般整数的取余。
8) 大数的欧氏算法。它是已知大数A、B，求满足AX≡1 MOD B的X，是最大公约数算法的扩展，同样用辗转相除法。再递归的过程中，两个参数都要用到，到要变化的。具体算法请参考源代码。
9) 大数的蒙氏算法。它是已知大数A、B和C，求X=A^B MOD C的值。要对指数进行逐渐降阶，直到变成2次方，也就是转换成乘法和取余运算。降阶的方法和算法的具体过程，请参考相关书籍和源代码。
10) 大数的最大公约数。求两个大数的最大公约数，用辗转相除法。 3 RSA算法的实现 A. 生成密钥函数
gChar gGenerateKey(gBigInt *n,gBigInt *e,gBigInt *d);
功能：该函数实现了产生密钥的功能。先产生两个随机的大素数p和q，然后计算n＝p×q，随机产生（或固定）一个大数e，计算d，使得ed≡1 MOD (p-1)(q-1)。 参数：
n：两个大数的乘积，和e或d联合构成加密密钥或解密密钥。 e：一个大数，作为加密密钥。
d：一个和e互异的大数，作为解密密钥。 返回值：1－成功，0－失败。 B. 数据加密函数
14
武汉纺织大学2012届毕业设计论文
char gEncRSA(unsigned char* indata, unsigned long inlen, gBigInt* e, gBigInt* n，unsigned char *outdata, unsigned long* outlen, int flg); 功能：把待加密的明文数据indata，用加密密钥e和n进行分段加密。 加密后的数据放到提前开辟好的内存outdata中，其长度outlen不得小于((inlen+k-12)/(k-11))*k，这里k为n的位数。 参数：
indata：指向明文数据的指针。
Inlen：传入数据的长度，即明文数据的长度。 e和n：两个大数，作为加密密钥。 Outdata：存放加密后密文数据的指针。
Outlen：传入outdata的长度，传出数据的长度，即密文数据的长度。 Flg：公钥加密或私钥加密的标志，g_PUBLIC－公钥，g_PRIVATE－私钥。 返回值：1－成功，0－失败。 C. 数据解密函数
char gDecRSA(unsigned char* indata, unsigned long inlen, gBigInt* d, gBigInt* n,unsigned char *outdata, unsigned long* outlen, int flg); 功能：把待解密的密文数据indata，用解密密钥e和n进行分段解密。 解密后的数据放到提前开辟好的内存outdata中，其长度outlen不得小于(inlen)*k/(k-11)， 这里k为n的位数。 参数：
indata：指向密文数据的指针。
Inlen：传入数据的长度，即密文数据的长度。 d和n：两个大数，作为加密密钥。 Outdata：存放解密后明文数据的指针。
Outlen：传入outdata的长度，传出数据的长度，即明文数据的长度。 Flg：公钥加密或私钥加密的标志，g_PUBLIC－公钥，g_PRIVATE－私钥。 返回值：1－成功，0－失败。 D. 用小素数检测
15
武汉纺织大学2012届毕业设计论文
gChar gIsNotPrime(gBigInt *p); 功能：检测随机大数p能否被小素数整除。 参数：
p：待检测的随机大数。
返回值：0－可能是素数，其它－为能整除p的小素数或1。 E. Rabin-Miller检测
gChar gRabinMillerTest(gBigInt *p,int tNum);
功能：用Rabin-Miller算法，对大数p进行tNum次检测，判断p是否可能为素数。 参数：
p：待检测的随机大数。
tNum：检测的次数，它可以决定该检测的可信度。
返回值：0－失败或通不过，1－成功并通过，说明p可能是素数。 F. 随机产生大素数
gChar gGeneratePrime(gBigInt *p); 功能：随机生成一个大素数。 参数：
p：随机生成的大素数。 返回值：0－失败，1－成功。 G. 顺序搜索大素数
gChar gGeneratePrimeEx(gBigInt *p, int flg); 功能：根据标志flg，递增或递减地搜索p附近的大素数。 参数：
p：搜索到的大素数。
Flg：方向标志，g_INCREASE－递增，g_DECREASE－递减。 返回值：0－失败，1－成功。
4 系统分析
4.1 系统需求分析
16
相关推荐：
loading