为了保证生成素数的成功率，A至少要有4个。如果少于4个，则素数测试失败的可能性比较大，经过测试发现不可以忽略。2.2.1.3小节曾经提到，如果素数测试通过了合数，就可能产生错误的密钥，使加密解密操作失败。所以测试A的时候，最少有让其取4个值。而取6个值以上，测试算法失败的概率已经非常小，没有什么实用意义，所以这里测试A从4个到6个的情况。固定其他变量：n取512位和1024位（即素数搜索起点位数设置为32和64），NP取200，SS取1000。从理论上说，对于同样的起点，素数测试次数越多，需要的时间就越长。实际测试结果如表3-2所示（其中A取4个的情况直接从表3-1复制数据，不再另做测试），表中各项对应的全部测试数据见http://3mn.net/www/download/RSAkeygen_A-Ttest.txt ，包括两个作为素数搜索起点的随机数和生成的素数p、q以及e、d、n。
表3-2 素数测试底数A对密钥生成时间的影响
A的设置 测试5次 n为512bit时密钥生成需要的时间(秒) 平均耗间(秒)
2,3,5,7 2.5346 2.4067 2.6756 4.5683 1.9542 2.8279
2,3,5,7,11 3.3030 2.5838 3.7744 2.4474 2.3716 2.8960
2,3,5,7,11,13 2.3906 3.8213 2.2279 1.9119 2.4995 2.5702
A的设置 测试5次 n为1024bit时密钥生成需要的时间(秒) 平均耗间(秒)
2,3,5,7 6.2941 17.1003 12.3989 11.5311 11.0922 11.6833
2,3,5,7,11 24.0268 27.0971 10.0254 20.1331 7.8633 17.8291
2,3,5,7,11,13 7.1299 17.7117 28.4306 27.8631 8.7279 17.9726
由表3-2可以看出，对于512bit密钥，A取从4个到6个，对随机密钥的产生时间影响不大。但是对于较长的1024bit密钥，A取4个和A取6个值，密钥生成时间产生明显差距，A取6个值时生成随机密钥需要的平均时间比A取4个值时长数秒之多。为了同时保证密钥生成速度和素数的准确程度，我们在实际使用时取A为5个值，即2、3、5、7、11。
3. 测试小素数因子个数NP对耗时的影响
固定其他变量：A取5个分别为2、3、5、7、11，n取512位和1024位（即素数搜索起点位数设置为32和64），SS取1000。测试结果如表3-3所示。表中各项对应的全部测试数据见http://3mn.net/www/download/RSAkeygen_P-Ttest.txt ，包括两个作为素数搜索起点的随机数和生成的素数p、q以及e、d、n。
表3-3 小素数因子个数NP对密钥生成时间的影响
NP 测试5次 n为512bit时密钥生成需要的时间(秒) 平均耗间(秒)
100 2.7550 1.7077 3.1189 3.0514 2.7971 2.6860
200 3.3030 2.8311 4.2693 2.8760 2.8581 3.2275
300 3.0029 2.1159 3.4268 2.2918 2.7531 2.7181
400 2.6944 5.6355 4.1228 3.6816 2.5232 3.7315
500 3.3725 4.3178 4.3426 3.7141 2.9172 2.8643
测试5次 n为1024bit时密钥生成需要的时间(秒) 平均耗间(秒)
100 5.7052 13.5294 9.9006 20.3994 23.3666 14.4542
200 13.7745 9.3998 11.3043 24.1689 7.7326 13.2760
300 7.4426 8.2489 29.1550 15.2442 27.4376 17.5056
400 17.8602 23.3219 17.7196 18.8298 11.5861 17.8635
500 13.9936 22.6667 14.7468 14.2334 12.5631 15.6407
不同颜色的单元格表示每行中的最大值和最小值 这种颜色代表行中最大值 这种颜色代表行中最小值
由于测试时间漫长，测试的数据量比较有限。这里并没有看出什么明显的规律。
而且通过本次测试还可以发现，表3-3中NP为200，n为1024bit测试的一行，变量设置和表3-2中A设置为2、3、5、7、11，n为1024bit的一行完全一致（对应还有一行n为512bit的数据变量设置一致），但是耗时平均差距相差4秒之多（512bit的一行差距不到1秒）。可见对于长密钥，同一种情况测试5个数据取均值并不能精确的说明问题，除非测试得到的数据有很明显的大幅差距，例如前面两段测试n的位数和A的个数的耗时影响情况。这里也正是因为前面提到的，对于大整数来说，可能出现在较长一段区间中没有素数的情况，使得同样设置的各次密钥生成耗时的可能范围很大，再加上大素数分布规律奥妙，观察5次测试结果的均值对于不很明显的规律显得意义不大。
实际使用中，设置NP值为200。
4. 测试SS对耗时的影响
同样未发现明显规律，在使用中设置SS为1000。
3.2.2 数据输入输出测试
主要测试文件的输入输出性能。实际上就是测试.Net基础类库中实现文件操作的System.IO中的StreamReader、StreamWriter等类的读写性能。直接在Visual Studio调试一个简单的C#文件读写程序，得到本软件中使用的文件操作方法的执行性能。在配置为CPU CR1.7GHZ/外频100MHZ/物理内存512M DDR/MSI6398主板845 Ultra-AD芯片组/UTA133 2M缓存硬盘的PC上，读入一个100KB的文件仅需要35毫秒，写出一个100KB的文件需要29毫秒。这样的时间消耗，相对于繁复的RSA计算所消耗的时间来说，是完全可以忽略不计的。
3.2.3 加密解密测试
进行对任意文件加密与解密的测试，这里给出几组从不同角度进行测试的数据。下面除了第3组测试，其他都是把文件逐字节进行RSA运算，逐字节加密是本软件的默认设置。加密时使用的测试文件、各密钥文件以及加解密后生成的文件可以从以下地址下载：http://3mn.net/www/download/RSAtestfiles.rar 内附说明。
1. 用同样的密钥对不同大小的文件公钥加密、私钥解密，各自消耗的时间与待加密文件大小的关系
随机生成两组密钥，一组n长512bit，一组n长1024bit。密钥具体数据见附录（n的实际位数有微小差距）。
分别对一组不同大小的文件进行公钥加密。统计消耗时间情况如表3-4所示，统计数据以曲线表示如图3-1。
表3-4 待加密文件大小与加密时间的关系(时间单位：秒)
n位数 文件大小 50Byte 100Byte 150Byte 200Byte 250Byte
512bit公钥加密 4.8537 9.7636 14.3205 18.9084 23.5322
512bit私钥解密 9.5452 18.9207 28.1287 37.9556 46.5794
1024bit公钥加密 12.6111 24.5664 36.5895 48.6288 60.6503
1024bit私钥解密 40.0084 79.2507 120.4443 158.0028 198.365
图3-1 文件大小--加密时间曲线(逐字节)
从表3-4以及图3-1可以看出，使用同一公开密钥加密不同大小的文件，消耗时间随着文件大小的增加线性的增加，和1.2.1小节分析的完全一致。对于较大的文件，加密位数对时间的影响十分明显。对于250字节的文件来说，1024bit的公钥加密比512bit的耗时多1.5倍左右；1024bit的私钥解密比512bit的耗时多3倍以上。对于一定的加密位数来说，私钥解密所需要的时间比公钥加密需要的时间长。对于一定大小的文件，使用512bit的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的2倍左右；而如果使用1024bit的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的3倍以上。再测试几个1280bit的密钥加解密，发现私有密钥解密所需要的时间相对于公钥加密时间更长。可见，本软件密钥长度越长，私有密钥解密与公开密钥加密的耗时比越大，这和其他软件是一致的。因为根据PCKS #1的RSA的应用建议，e是比较短的，而d和n的长度差不多，这就使得求与d、n有关的幂模运算量比与e、n有关的幂模运算量大很多，而且随着n的增加，两组幂模运算的运算量差距也迅速加大。为了减少d、n幂模运算的时间消耗，考虑到使用中国余数定理分解简化运算，具体做法见3.3节。
2. 用同样的密钥对不同大小的文件公钥加密，加密后生成的文件大小与待加密文件大小的关系
在上一组测试进行完之后，我们得到了一些加密文件，下面详细分析这些加密后生成的文本文件大小。表3-5给出了加密后的各文件大小。
表3-5 本软件生成的加密文件大小测试(文件大小单位：Byte)
n位数 文件大小 50Byte 100Byte 150Byte 200Byte 250Byte
512bit公钥加密 6,557 12,977 19,397 25,817 32,237
1024bit公钥加密 12,986 25,835 38,684 51,533 64,382
从表3-5的数据可以发现，对于同样的文件进行加密，使用1024bit密钥加密所得到的文件大小是使用512bit加密的2倍左右。而且不论用哪组密钥进行加密，加密所生成的文件大小都比原来未加密的文件大。可以从两个角度来理解文件在加密后增大：（1） 因为模数n通常较大，所以加密幂模运算的结果通常很大，这使得逐字节加密时，密文比明文长很多。（2） 因为加密完以后保存成十六进制文本，对于十六进制文本来说，每字节可能出现的字符只有16个，所以字节熵是4bit；而对于任意数据来说，每字节的熵是8bit。所以同样的信息量，采用十六进制文本要比原始数据大一倍。从更简单的角度理解，每字节表示为两位十六进制，每位十六进制在文本中是一个符号，占用1字节，所以长度大了一倍。
从表3-5的数据还可以看出，对于同样的密钥，随着原始文件大小的线性增长，加密后的文件大小也基本呈线性增长。在使用512bit加密时，加密后的文件大小是加密前数据大小的130倍左右；在使用1024bit加密时，加密后文件大小是加密前数据大小的260倍左右。根据这些数据，可以总结出本软件使用的加密方式，加密前后文件大小的近似换算公式如下：
，
其中A是待加密文件数据长度，B是加密后文件长度，N是RSA加密位数，N>8。
以上公式其实也可以从理论上得到，因为模数n取8位时，幂模运算的结果仍然近似为8位，这时一个字节的数据经过加密，得到的数据大小近似不变，转换成十六进制文本，大小就增加了1倍。按此原理，幂模运算结果长度近似为加密模数n的长度，加密后数据长度是加密前的N/8倍（N是加密位数），而转换为十六进制文本后长度又增大1倍，加密后得到的文本长度就是加密前原始数据大小的N/4倍，所以B=A×N/4，这与前面从实验结果总结得到的公式基本一致，可以把公式中的260修正为更精确一些的256。
3. 以多字节为步长，对文件进行加密
默认的设置是加密时逐个字节进行RSA运算，可以通过设置窗体把分块的大小更改为其他长度，比如2字节一组、4字节一组，进行RSA运算。下面测试多字节为步长的加密执行效率。取一个480字节长的文件作为加密对象，对其进行512bit RSA公钥加密、私钥解密还原，记录所消耗的时间。统计数据如表3-6所示。
表3-6 加密分段大小改变对效率的影响测试(消耗时间单位：秒)
加密方式 步长 2字节 4字节 6字节 8字节 10字节
512bit公钥加密 23.5551 12.8205 7.8117 5.9185 5.1848
512bit私钥解密 46.3083 23.6089 16.1083 11.4820 9.2541
可见，增大加密步长使加密解密速度大幅增加，而且大步长的加密生成的文本文件体积也比小步长的小。这都是因为增大了步长后，文件被分成的块数少了，幂模运算次数下降。所以在使用RSA加密时，设置使用合适的数据分块也是提高加密速度的关键。
4. 在更快的PC，对进行文件加密测试
在一些性能更好的PC上，本软件可以获得更好的性能，测试数据同样可以分析得到以上段落叙述的结论。下面对照表3-4，给出一组其他PC上同样的测试得到的数据，测试PC配置为CPU AMD Athron2800+，外频333MHZ，物理内存512MB。数据见表3-7。
表3-7 待加密文件大小与加密时间的关系再次测试(时间单位：秒)
n位数 文件大小 50Byte 100Byte 150Byte 200Byte 250Byte
512bit公钥加密 2.4347 4.8975 7.1728 9.4508 11.9837
512bit私钥解密 4.7725 9.4427 14.002 19.0125 23.6544
1024bit公钥加密 6.3501 12.2364 18.2459 24.3001 30.1284
1024bit私钥解密 20.0101 39.8754 60.2126 79.3351 99.5482
对于这组数据，表3-4后的推理分析仍都成立。在此PC测试填写表3-6，同样得到了类似规律的数据，在此不再罗列。经过一系列各种机型、各种Windows操作系统（包括Windows XP/2000SP4/ME/98，均需.Net框架）上的测试，本软件均能正常运行。在2006年初主流配置的PC上运行此软件，逐字节加密1KB大小的文件，消耗时间均在1分钟以内。
3.2.4 性能分析与改进优化
经过一系列的RSA密钥生成、文件输入输出和加密解密测试，做简要的性能分析如下。
① 软件消耗时间的运算，大部分集中在C++核心类库，即RSA相关的各种运算。其中，幂模运算和寻找素数对时间的消耗最大，在核心优化时应优先考虑。
② 文件输入输出消耗时间其次，因为磁盘读写速度要远远低于内存读写速度。所以，应该将频繁的读写操作尽量集中到内存，然后一次性写入磁盘。
针对以上两点，软件应进行一系列改进和优化。主要有以下几方面。
① 在要对文件进行加密解密的时候，先将文件按一定的数据结构读入内存，然后进行加密或解密操作。运算数据都读取自内存。
② 在对加密或解密完成的数据进行写出的时候，都是将其直接写到指定好的文件，即直接写入磁盘。这是因为，考虑到中途可能因为意外断电等原因引起操作中断，为了保护已经花费时间运算完成的数据，将其直接写入磁盘。
③ 在关键算法上做进一步优化，例如在寻找素数时，素数测试使用更快速的算法；还有3.3节提到的，在用私有密钥进行幂模运算时使用中国余数定理等。
④ 对C++核心类库进行重点优化，使其运算效率尽可能提高。其中包括对各类之间的组织细节、各程序模块的具体编写等，进行全面细致的检查和修改，例如将大数据类型以对象指针传递而不拷贝，将简单的for循环展开等。
由于开发时间仓促等因素，在书写本文时，软件并未完成全面细致的优化。
3.3 使用中国余数定理
对于用RSA加密解密的一方，是计算。这里n＝p×q，p和q是两个二进制长度接近的大素数。由于用私密密钥加密或解密的一方实际知道n的分解，即p和q，所以这一计算可以分解为以下两部分分别进行 (附录中有中国余数定理的简单介绍) 。
其中的C1、C2、d1、d2如下：
根据RSA算法的要求，私密密钥d的二进制长度接近n的长度，因此，d1和d2的二进制长度仅有n的一半左右，这样就节省了大量的计算工作。最后，应用中国余数定理就能计算出的值m。，其中.
如果应用中国余数定理计算幂模，主要工作花在计算上，计算C1、C2、d1、d2和m的运算与幂摸运算相比，计算时间较短可以不计。而位数对幂摸运算速度影响很大，因此分开计算比计算要快很多。经过测试，使用中国余数定理来简化一些幂模运算，速度比不使用中国余数定理时有很大的提高。
在书写本文时软件中尚未使用中国余数定理。
第4章 可移植模块的简要说明与开发前景
如2.1.2节所叙述，分层设计给移植带来方便，下面简要叙述各层可能的移植方式。
①实现RSA加密算法的C++核心类库，是基于C和C++的标准库创建的，没有用到C++泛型计算、STL相关内容，代码中没有任何与操作系统相关的内容。这是一种移植特性最好的程序模块，因为现今多数非PC设备支持C++编译。一般可以直接将本模块交叉编译给嵌入式设备，或在其他操作系统编译使用。在编译前，将rsa_san.cpp和vlong.cpp文件中的#include "stdafx.h"一行去掉，然后连同各自的头文件拷贝出来，仅这四个文件即为实现RSA加密算法的C++类库代码。例如，可以将它们在linux操作系统用gcc编译成程序模块，把RSA加密功能提供给系统上的其他程序使用。
②封装C++核心类库的DLL组件可以被Windows上的很多开发环境引用。例如在VB6，要使用这个组件，只需在程序最开始以引用win32api的方式引用即可，即public declare function XXX的形式。
③作为.Net类库，此模块可以被几十种支持.Net的语言引用。但是由于底层DLL组件的存在，使应用局限于PC上的Windows系统。在此层的使用不仅限于窗体应用程序，.Net类库可以由服务器程序（诸如aspx）方便的引用，以BS（浏览器服务器）的模式提供给网络上的用户使用，所以此应用程序可以通过简单的修改用于数字证书和数字签名等身份验证系统。
如1.2.2节最后所分析的，将任意文件加密成文本有其重要的意义。
因为此应用程序是可以将任意文件加密成文本的，所以加密成的数据可以方便的在Internet上传送。由此想到xml在Internet上携带数据的应用模式。实际上，此软件可以通过简单的修改实现将任意文件加密为一定格式的xml文件。通过这种加密方式，可以满足重要的小应用程序等小型二进制数据在网络上安全顺利传输的要求。而且，通过加密的数据以xml方式传送，使web应用的灵活性更好，此方式甚至可以看作一种通用的小型二进制数据安全交换协议来开发。
结束语
RSA应用于文件加密适合交流管理小型文件，将任意文件以非对称密钥加密成文本可以对其更方便的交流和管理，有广阔的开发前景。本项目应用的设计模式兼顾执行效率和可复用性。整个项目开放源代码和各种开发资料，便于引用和继续开发。应用本程序可以方便的在公众论坛等环境交流要求高度安全的各种数据，包括任意二进制和文本文件。
谢 辞
感谢蒋萍花老师的细心指导和各论坛程序员朋友的支持与建议。
参考文献
1．华罗庚，数论导引，科学出版社， 1979．
2．Montgomery PL， Modular multiplication without trialdivision［J］， Mathematics of Computation， 1985， 44(170)：519--521．
3．Oh JH，Moon S J， Modular multiplication method［J］， IEE Proceedings：Computers and Digital Tech－niques， 1998， 145(4)：317--318．
