RSA文件加密原理及代码实现(四)
经过2.2.1.1和2.2.1.2小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类Prime_factory_san之中。外部只要调用本类实例的成员vlong find_prime( vlong & start )就可以以大数start为起点，得到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。
首先在需要寻找素数的整数范围内对整数进行筛选，把所有确知为合数的整数排除出去。程序中构造了一个数组b[]，大小为一轮素数搜索的范围，记搜索范围大小为SS。b[0]到b[SS]分别对应大数start到start+SS。b[]中所有元素先初始化为1，如果对应的大数确定为合数，就将b[]中对应的元素置为0。最后，只需对那些b[]中为1的元素对应的大数进行比较确切的素数测试即可，只要被测试的数是素数概率达到一定门限，就判这个数为素数。这样做既保证了这段程序可以在短时间内执行完，又保证了可以以比较高的准确度得到素数。
函数find_prime先把b[]的所有元素赋值为1，然后按参数start给标记数组b[]的各元素赋0值。下面描述标记数组b[]的赋0值算法。首先，在类Prime_factory_san被构造的时候，构造函数中从2开始搜寻一些小素数，记录在数组pl[]中，共记录NP个。这些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除(即把数组b[]的对应元素标记为0)，剔除的程序代码如下。
for (i=0;i<np;i++)
{
unsigned p = pl[i];
unsigned r = start % vlong(p);
if (r) r = p - r;
while ( r < SS )
{
b[r] = 0;
r += p;
}
}
这里利用start对各小素数因子p求模的办法，得到当前p在素数搜索范围内的最小倍数在b[]中的对应位置，将其剔除后，不断后移p个位置，将这个小素数因子p在搜索范围内的所有倍数全部剔除，如图2-5所示。在完成对所有小素数因子的类似操作后，他们的倍数在搜索范围内的位置标记b[r]被全部标记为0。实际上这就是Eratosthenes筛选法。
图2-5 在素数搜索范围内剔除小素数因子p的倍数
接下来，对可能为素数的数(即标记数组b[]中值为1的元素对应的数)进行素数测试。数论学家利用费马小定理研究出了多种素数测试方法，本程序使用一种最简单的方式，直接应用费马小定理。取一个与p互素的整数A，对于大素数p来说应该满足Ap-1mod p=1，但是我们把p代入一个大整数，满足这个关系的数不一定是素数。这时我们改变A，进行多次测试，如果多次测试都通过，这个数是素数的概率就比较大。按这种原理，我们编写素数测试函数如下。
int is_probable_prime_san( const vlong &p )
{
const rep = 4; //测试次数
const unsigned any[rep] = { 2,3,5,7 }; //测试用的底数
for ( unsigned i=0; i<rep; i+=1 )
if ( modexp( any[i], p-vlong(1), p ) != vlong(1) ) return 0;
//modexp是幂模函数，按上一小节叙述的算法编码。
//这里modexp计算any[i]p-1mod p。
return 1;
}
测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。在这里其实有一个不可忽视的问题，就是得到一个测试通过的合数。对于这种情况，RSA算法加密解密是否还可以实现，是一个需要从数学角度论证的问题。因为得到素数的概率很高，经过一整天的生成密钥和加密操作，没有发现失败的密钥， 所以本文暂没有对这个问题进行讨论。
综上所述，总结素数寻找的流程，如图2-6所示。
图2-6 函数find_prime寻找素数的流程框图
得到了大素数，即RSA算法中的p、q，我们就可以计算出密钥，进行加密等操作了。
4. 二元一次不定方程
在RSA 算法中，往往要在已知A、M的情况下，求B的最小值，使得 (AB) mod M = 1。即相当于求解B、N都是未知数的二元一次不定方程 AB-MN=1的最小整数解。
而针对不定方程ax-by=1 的最小整数解，古今中外都进行过详尽的研究，西方有著名的欧几里德算法，即一种辗转相除法，中国有秦九韶的“大衍求一术”。欧几里德算法是一种递归算法，较容易理解。下面举例说明用欧几里德算法求解二元一次不定方程的最小整数解。
给定不定方程11x-49y=1，求最小的x
（1） 11 x - 49 y = 1 49 mod 11 = 5
（2） 11 x - 5 y = 1 11 mod 5 = 1
（3） x - 5 y = 1 5 mod 1 = 0
逆向代入：
令y=0 代入（3）得x=1
令x=1 代入（2）得y=2
令y=2 代入（1）得x=9
x=9;y=2即为所求。
程序中，全局函数vlong modinv( const vlong &a, const vlong &m )用来完成这种算法。对应前面的叙述，参数a对应A，参数m对应M，函数返回值即为B的最小值。
5. 按常规RSA算法实现加密与解密
最后，类RSA_san基于前面的准备工作，实现RSA密钥生成和加解密的功能(算法在此不再赘述，RSA算法协议见http://www.di-mgt.com.au/rsa_alg.html)。为了方便阅读，整个类的源程序中，所使用的变量字母均和RSA算法协议中一致。在类RSA_san的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行RSA加解密操作，也可以载入以前保存的密钥或再次随机生成密钥。类中各成员频繁的用到字符串和vlong类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将unsigned指针指向的一段空间里保存的一个大数，表示成十六进制形式的字符串文本。编码转换通常是用C风格的指针操作和sprintf函数来完成。
需要加密和解密的数据也是通过字符串参数置入的。由于字符串的结尾字符“\0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“\0”来决定，程序里引入一个unsigned类型的参数来决定置入的串长度，这样就解决了加密连0数据时候被截断的问题。
因为是对文件加密的软件，需要加密的数据通常并不止几字节，这时由上层程序将数据按用户的设置分块，分别加密或解密。本软件默认的分块大小是1字节，即逐个字节作为参数，调用C++核心模块中的方法。
加密解密流程均为标准RSA算法，具体过程和使用方法参见源程序和接口文档。
6. 核心类库综述
综上几小节所述，实现RSA加密算法的C++核心类库由六个类组成，类名和对应的功能描述总结如表2-1所示。各个类之间的关系如图2-7所示。
表2-1 RSA加密算法的C++类库中的类
class flex_unit 大数运算和存储最基本的类，主要实现超大整数的存储和索引管理。
class vlong_value 是flex_unit的派生类，在灵活大数存储的基础上实现四则运算函数。
class vlong 以vlong_value为基础(将一个vlong_value指针作成员)，重载运算符。
class monty 为RSA准备大数求幂模运算的函数，vlong的友元。
class Prime_factory_san 素数工厂，寻找大素数的类。
class RSA_san 在前5个类的基础上，实现RSA核心算法的类。
图2-7 C++核心功能类图
另外需要说明的是，程序中有几个不属于任何类的全局函数，比如应用辗转相除法求最大公约数的函数gcd、解同余方程的函数modinv等。按常规设计模式来说，不应当出现类之外的函数，但是因为这些函数使用频繁，考虑到机器效率，直接置于全局，不再另行包装。
2.2.2 封装C++核心类库的DLL组件
在Visual Studio当前的解决方案中以VC++创建一个win32dll工程，将测试好的实现RSA加密算法的C++核心类库中的所有文件加入到此工程下，新建一对cpp和h文件，把可能用到的功能全部规划为新文件中的全局函数，并以C接口导出，即__declspec(dllexport)。由于核心类库的对外功能都使由RSA_san类提供的，所以在新cpp文件中全局的声明一个RSA_san类的对象指针(RSA_san *WRSA)，全局函数int start_RSA_san()初始化*WRSA对象，在初始化成功后，其他全局函数通过调用*WRSA对象的公开方法实现各种功能，如加密、读取密钥等。在关闭上层引用程序以前，应执行int finish_RSA_san()来释放WRSA，该函数执行delete WRSA的操作。其他接口函数的使用见DLL接口文档。
另外，DLL组件可以自己在全局函数中实现一些其他功能，作为对核心类库功能的补充。C接口的DLL组件可以被诸如VB、Delphi等开发环境方便的引用。
2.2.3 引用DLL的.Net类与实现文件操作功能的窗体应用程序
在C#编写的.Net类里，使用特性[DllImport("sanpack_rsa.dll")]引用C接口的DLL组件。类中接口DLL的函数都以静态成员的方式对外公开，其他.Net程序可以直接使用。在类库中还提供了任意长度随机串的生成函数，此函数用于生成寻找素数的大数起点。
文件操作使用.Net基础类库中的System.IO中的类实现。一般因为文件操作十分简单，用流输入输出的方式包装完成，程序中将文件操作直接放在菜单项关联的事件处理函数中。
窗体等图形操作界面直接由Visual Studio的所见即所得的方式完成，不需要编码实现。
最终实现的应用程序，结构如图2-8所示。
图2-8 本软件的Visual Studio解决方案
第3章 软件整体测试与分析改进
3.1 编写测试各项性能需要的精确计时类
由于.Net基础类库提供的计时功能十分不精确，无法胜任软件性能测试的工作，这里使用Windows API 函数QueryPerformanceCounter和QueryPerformanceFrequency进行精确计时。功能被封装在C#类HighResolutionTimer中，使用时只需构造一个此类的对象，在计时开始的时候调用其Start方法，计时结束时调用其Stop方法，然后访问其ElapsedTime属性，就可以得到一个以秒为单位的float型精确的计时值了。API 函数QueryPerformanceCounter和QueryPerformanceFrequency是靠查询CPU的高精度计时器来计时的，所以可以轻松的精确到毫秒级计时。
附录中给出了这个类的源代码。
3.2 测试数据与分析改进
3.2.1 密钥生成测试
生成密钥运算最费时的工作是寻找素数。如2.2.1.3小节所叙述，寻找素数是一项颇为复杂的工作，其速度可能受以下变量的影响：RSA加密需要的n的位数（寻找素数的整数起点大小start）、大素数测试时底数A的个数（针对一个整数的素数测试次数）、小素数因子p的个数NP、一轮寻找遍历的整数个数SS等。其中最具影响力的因素显然是RSA加密需要的n的位数。以下对各变量分别进行测试，暂且忽略操作系统调度对测试的影响。
1. 测试加密使用的n的位数对耗时的影响
即 在固定A、NP、SS等变量的情况下，改变加密位数n，测试密钥生成的时间消耗情况。测试时，A取4个值，分别为2、3、5、7，NP取200，SS取1000。测试PC配置为CPU CR1.7GHZ/外频100MHZ/物理内存512MDDR/MSI6398主板845 Ultra-AD芯片组，下文测试中，未说明PC配置的也都在同一PC完成，不再重复。统计数据如表3-1所示。表中各项对应的全部测试数据见http://3mn.net/www/download/RSAkeygen_n-Ttest.txt ，包括两个作为素数搜索起点的随机数和生成的素数p、q以及e、d、n。
表3-1 RSA加密模数n与密钥生成耗时的关系
加密位数n (bit) 对应的搜索起点字节数 测试5次获得随机密钥消耗的时间(秒) 平均时间消耗(秒)
第一次 第二次 第三次 第四次 第五次
256 16 0.7968 0.5448 0.6000 0.6024 0.7899 0.6668
384 24 1.3858 1.8130 1.4065 2.2514 1.4137 1.6541
512 32 2.5346 2.4067 2.6756 4.5683 1.9542 2.8279
640 40 4.3264 3.5319 7.3716 5.8340 2.8486 4.7825
768 48 10.1956 6.9521 5.3732 6.6958 4.1091 6.6652
896 56 6.6307 5.1443 14.0495 14.7396 11.3944 10.3863
1024 64 6.2941 17.1003 12.3989 11.5311 11.0922 11.6833
1152 72 20.3097 15.8271 23.7094 16.2601 13.1304 17.8473
1280 80 26.6514 11.5004 54.1937 13.3371 18.3094 24.7973
不同颜色的单元格表示每行中的最大值和最小值 这种颜色代表行中最大值 这种颜色代表行中最小值
观察表3-1上的统计数据，很容易发现随着加密位数的增加，密钥生成需要的时间显著增加。在测试范围内，随着加密位数增大，每一行中的最大最小值差距也呈粗略的增大趋势。也就是说对于长密钥来说，RSA随机生成密钥消耗时间的可能范围较大。这是因为对于大整数来说，可能出现在较长一段区间中没有素数的情况。
在较常用的1024位RSA加密时，用本软件的算法，测试时最长出现了17秒多的计算，虽然这对于用户来说时漫长的等待，但是考虑到安全性，还是舍弃了素数表和密钥库的方案，而使用大素数随机生成，用户可以把生成的私钥单独加密保存在可靠的存储空间内，以获得更高的安全性。
表3-1仅能从实验的角度直观理解，具体到一次密钥生成的运算，所需要的时间是很不确定的，比如，一次1280位的密钥生成，需要的时间完全可能比一次896位的密钥生成时间短，由于素数分布规律非常奥妙，加上测试运算需要的时间颇长，这里很难给出对于一个具体位数的密钥生成所需时间的统计模型。
另外需要说明的是，表3-1的加密位数在实际软件设置时并不严格。这是因为，实际作为参数设置的是两个大素数的搜索起点。如果随机生成的起点整数大小比较接近更长一位的整数的话（例如FFFF很接近10000），向后寻找所得到的素数很可能长出一位。而且，两个k位长的整数相乘的结果也未必是2k位，比如100*100=10000，相乘结果是2k-1位。所以，在表3-1实际测试填写时，加密位数可能会有几位的差距，但是这不碍大局。
2. 测试底数A对耗时的影响
RSA文件加密原理及代码实现(四)由毕业论文网（www.huoyuandh.com）会员上传。
