|
⑶. 寻找素数与素数测试 首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到100%准确的大素数，都是通过查已经计算好的素数表的方式。 copyright paper51.com 经过2.2.1.1和2.2.1.2小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类CBigint之中。外部只要调用本类实例的成员函数void GetPrime(intbits);就可以以bits为起点，得到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。 copyright paper51.com 本工程在素数生成时，通过数组m_ulValue[i]来存储生成的素数，调用C++已有的函数Rand()产生随即数，再通过素数表排除非素数，最终得到待测试之素数。代码如下： http://www.paper51.com void CBigInt::GetPrime(int bits) paper51.com { copyright paper51.com unsigned i; paper51.com
m_nLength=bits; http://www.paper51.com begin: 内容来自www.paper51.com for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand(); http://www.paper51.com
m_ulValue[0]=m_ulValue[0]|1; copyright paper51.com for(i=m_nLength-1;i>0;i--) copyright paper51.com
{ 内容来自论文无忧网 www.paper51.com
m_ulValue[i]=m_ulValue[i]<<1; 内容来自论文无忧网 www.paper51.com if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++; copyright paper51.com } http://www.paper51.com m_ulValue[0]=m_ulValue[0]<<1; copyright paper51.com m_ulValue[0]++; copyright paper51.com
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;} 内容来自www.paper51.com
CBigInt S,A,I,K; 内容来自论文无忧网 www.paper51.com K.Mov(*this); http://www.paper51.com K.m_ulValue[0]--; copyright paper51.com
for(i=0;i<5;i++) http://www.paper51.com { copyright paper51.com A.Mov(rand()*rand()); paper51.com S.Mov(K.Div(2)); 内容来自www.paper51.com
I.Mov(A.RsaTrans(S,*this)); 内容来自www.paper51.com
if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))gotobegin; http://www.paper51.com } copyright paper51.com } paper51.com 接下来，对可能为素数的数用拉宾米勒算法进行测试，测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。拉宾米勒算法是公开的测试素数算法，直接通过函数的调用实现，这里就不详细介绍。 内容来自论文无忧网 www.paper51.com 综上所述，总结素数寻找的流程，如图2-1所示： http://www.paper51.com 开始 内容来自论文无忧网 www.paper51.com
内容来自论文无忧网 www.paper51.com
图2-1:寻找素数流程 copyright paper51.com 得到了大素数，即RSA算法中的p、q，就可以计算出密钥，进行加密等操作了。 paper51.com ⑷. 二元一次不定方程 内容来自www.paper51.com
在RSA 算法中，往往要在已知A、M的情况下，求B的最小值，使得 (AB) mod M = 1。即相当于求解B、N都是未知数的二元一次不定方程 AB-MN=1的最小整数解。 paper51.com 而针对不定方程ax-by=1 的最小整数解，古今中外都进行过详尽的研究，西方有著名的欧几里德算法，即一种辗转相除法，中国有秦九韶的“大衍求一术”。欧几里德算法是一种递归算法，较容易理解。下面举例说明用欧几里德算法求解二元一次不定方程的最小整数解。 http://www.paper51.com 给定不定方程11x-49y=1，求最小的x 内容来自www.paper51.com （1） 11 x - 49 y = 1 49 mod 11 = 5 paper51.com
（2） 11 x - 5 y = 1 11 mod 5 = 1 内容来自论文无忧网 www.paper51.com （3） x - 5 y = 1 5 mod 1 = 0 paper51.com
逆向代入： copyright paper51.com
令y=0 代入（3）得x=1 内容来自论文无忧网 www.paper51.com 令x=1 代入（2）得y=2 内容来自论文无忧网 www.paper51.com 令y=2 代入（1）得x=9 http://www.paper51.com x=9;y=2即为所求。 paper51.com 程序中，函数Euc(CBigInt&A);用来完成这种算法。对应前面的叙述，参数a对应A，函数返回值即为X的最小值。 内容来自www.paper51.com ⑸.文件操作 内容来自www.paper51.com 本工程的核心是利用蒙哥马利算法快速实现RSA加密，为了便于研究对字符串的加密过程，以及记录字符串的密文样本，程序把字符串写入TXT文档，再进行加密解密操作，这样就需要对文件进行操作，以二进制数据流对文件进行读出写入操作。在这里使用一个CFILE类，使用CFILE类对文件进行简单的读写操作十分方便，本工程以一个char型的指针data来存放获得的字符串，用DWORD型变量flen来存放Cfile类中成员函数GetLength()获得的字符串长度，然后直接使用成员函数read(),write()来进行文件的读写操作。 http://www.paper51.com 文件的读写操作代码见附。 内容来自论文无忧网 www.paper51.com ⑹. 按常规RSA算法实现加密与解密 copyright paper51.com 最后，类CDemoDlg基于前面的准备工作，实现RSA密钥生成和加解密的界面化功能。（界面代码多由C++编译器自动生成，在此不再赘述）在类CDemoDlg的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行RSA加解密操作，也可以载入用户写入的密钥或再次随机生成密钥。类中各成员频繁的用到字符串和vlong类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将unsigned指针指向的一段空间里保存的一个大数，表示成十六进制形式的字符串文本。编码转换通常是用C风格的指针操作。 paper51.com 由于是对文件进行加密，所以涉及对文件内容进行读写操作，这里使用到了CFile类。需要加密和解密的数据是通过字符串参数置入的。由于字符串的结尾字符“\0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“\0”来决定，程序里引入一个unsigned类型的参数来决定置入的串长度，通过Cfile类中的Getlength()函数获得文件中字符串的长度，这样就解决了加密连\0数据时候被截断的问题。 paper51.com 加密解密流程均为标准RSA算法，具体过程和使用方法参见源程序和接口文档。 http://www.paper51.com ⑺. 核心类库综述 内容来自www.paper51.com 综上几小节所述，实现RSA加密算法的C++核心类库由两个类组成，类名和对应的功能描述总结如表2-1和图2-2所示。 paper51.com 表2-1：RSA加密算法的C++类库中的类 copyright paper51.com CBigInt 内容来自论文无忧网 www.paper51.com
主要包含大数四则运算，素数生成，检测，密钥生成，存储，RSA核心算法等。 copyright paper51.com CDemoDlg 内容来自论文无忧网 www.paper51.com
主要包含界面功能的实现，按钮触发时间等。 paper51.com
copyright paper51.com
图2-2：主要函数成员 内容来自www.paper51.com 3.软件整体测试与分析改进 paper51.com 3.1 编写测试各项性能需要的计时程序 paper51.com 由于对几个字符的字符串进行RSA加密，所用时间只需10几毫秒，一般的程序计时函数无法达到要求测试结果很可能是0，于是在这里定义了2个long型变量t1,t2来分别存储加密函数运行前后GetTickCount()函数获得的系统时间,然后将两个值相减获得消耗时间，这样做还会有较大误差，于是再次进行了改进，通过一个简单的for循环让程序运行1000次 ，然后将t2-t1的值除1000，以获得较为精确的时间。 paper51.com
附录中给出了这段操作的源代码。 http://www.paper51.com |