092_RSA公钥密码算法的一种快速实现

2.1.2 工程方案选择
1. 利用BORLAND C++BUILDER平台
C++BUILDER界面制作功能强大，操作方便，但由于现在大多数公开C++ RSA算法代码都是用VC++编写，在调用函数上有诸多麻烦，牵涉到很多动态联结，调试比较困难。
2. 利用MICROSOFT VISUAL C++平台
从最初的Visual C++ 1.0到最近的Visual C++.NET , Visual C++经过近十年的发展，现已成为Windows操作系统环境下最主要，最权威的软件开发工具。内部集成众多算法实现函数，可方便的调用，给编程及调试带来极大的方便，最终本工程选定以VC++做为平台，进行本软件的开发工作。
2.2 各部分的设计与开发
2.2.1 实现RSA加密算法的C++核心类库
⑴. 大数四则运算与运算符重载:
根据RSA算法的要求，为了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C++类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍四则运算的实现原理。
大数的四则运算由CBIGINT类实现，类中申明了以下若干函数： 【买计算机毕业论文就到www.think58.com】
基本操作与运算:
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=” [来源：http://www.think58.com]
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”
Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”
输入输出:
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
RSA相关运算:
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
RsaTrans，反复平方算法进行幂模运算
GetPrime，产生指定长度的随机大素数
通过Add，Sub，Mu，Div，实现四则运算函数，并实现强制转换运算符unsigned，以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。 copyright think58 [资料来源：http://THINK58.com]
RSA依赖大数运算，目前主流RSA算法都建立在512位到1024位的大数运算之上，大多数的编译器只能支持到64位的整数运算，即在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff也就是18446744073709551615，这远远达不到RSA的需要，于是需要专门建立大数运算库来解决这一问题。
最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低，因为1024位的大数其10进制数字个数就有数百个，对于任何一种运算，都需要在两个有数百个元素的数组空间上做多重循环，还需要许多额外的空间存放计算的进位退位标志及中间结果。当然其优点是算法符合人们的日常习惯，易于理解。
另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。
本工程使用了一种介于两者之间的方法：
将大数看作一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x10000000，假如将一个1024位的大数转化成0x10000000进制，它就变成了32位，而每一位的取值范围就不是0-1或0-9，而是0-0xffffffff。这里正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机来说，实际上是一回事，但是这里完全可以针对unsigned long数组进行“竖式计算”，而循环规模被降低到了32次之内，并且算法很容易理解。 think58好，好think58

例如大数18446744073709551615，等于“ffffffff ffffffff”，它就相当于10进制的“99”：有两位，每位都是ffffffff。而大数18446744073709551616，等于“00000001 0000000000000000”，它就相当于10进制的“100”：有三位，第一位是1，其它两位是0。如果要计算18446744073709551616-18446744073709551615，就类似于100-99：
00000001 00000000 00000000
- ffffffff ffffffff
-----------------------------
= 0 0 1
⑵. 大数幂模与乘模运算Montgomery幂模算法
在实现了CBigInt类型后，大数的存储和四则运算的功能都完成了。考虑到RSA算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个RsaTrans函数，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质 ，先将幂模运算化简为乘模运算。
蒙哥马利算法用到了因子r。r是一个2的幂。若设R'为r在模m下的逆元，那么运算mm（a,b,m）=a*b*R' mod m。另外，a*a mod n=>(a mod n)*(a mod n)mod n。实际上，连mod n这样的运算最后也被转化到mod r，这样模运算就方便多了。
蒙哥马利算法求乘方的模
调用方式：N.Mon(A,B)
返回值：X=N^A MOD B
（1）X=1;
（2）若A为奇数，则A=A-1,X=(X*N) MOD B;
（3）若A为偶数，则A=A/2,N=(N*N) MOD B;
（4）重复（2）、（3）对A进行降阶，直至A=0;
（5）此时的X即为所求结果;
CBigInt CBigInt::RsaTrans(CBigInt& A, CBigInt& B)
{
CBigInt X,Y,Z;
X.Mov(1);
Y.Mov(*this);
Z.Mov(A);
if(A.Mod(2)==1)
{
Z.Mov(Z.Sub(1)); //A=A-1,X=(X*N) MOD B
X.Mov(X.Mul(Y));
X.Mov(X.Mod(B));
}
else
if(A.Mod(2)==0)
{
Z.Mov(Z.Div(2)); //A=A/2,N=(N*N) MOD B
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
}
return X;
}
⑶. 寻找素数与素数测试
首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到100%准确的大素数，都是通过查已经计算好的素数表的方式。
经过2.2.1.1和2.2.1.2小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类CBigint之中。外部只要调用本类实例的成员函数void GetPrime(int bits);就可以以bits为起点，得到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。

think58好，好think58

[资料来源：http://www.THINK58.com]

本工程在素数生成时，通过数组m_ulValue[i]来存储生成的素数，调用C++已有的函数Rand()产生随即数，再通过素数表排除非素数，最终得到待测试之素数。代码如下：
void CBigInt::GetPrime(int bits)
{
unsigned i;
m_nLength=bits;
begin:
for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
m_ulValue[0]=m_ulValue[0]|1;
for(i=m_nLength-1;i>0;i--)
{
m_ulValue[i]=m_ulValue[i]<<1;
if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
}
m_ulValue[0]=m_ulValue[0]<<1;
m_ulValue[0]++;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
CBigInt S,A,I,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
A.Mov(rand()*rand());
S.Mov(K.Div(2));
I.Mov(A.RsaTrans(S,*this));
if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
}
}
接下来，对可能为素数的数用拉宾米勒算法进行测试，测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。拉宾米勒算法是公开的测试素数算法，直接通过函数的调用实现，这里就不详细介绍。

think58.com

综上所述，总结素数寻找的流程，如图2-1所示：

内容来自think58

think58 [资料来源：http://think58.com]

[资料来源：THINK58.com]

内容来自think58 [来源：http://www.think58.com]

think58 [资料来源：THINK58.com]

think58好，好think58

[版权所有：http://think58.com]

copyright think58

[来源：http://think58.com]

[来源：http://think58.com]

开始

think58.com [来源：http://www.think58.com]

[版权所有：http://think58.com]

[资料来源：www.THINK58.com]

copyright think58 [版权所有：http://think58.com]

think58 [资料来源：http://www.THINK58.com]

think58

think58好，好think58

[来源：http://www.think58.com]

图2-1:寻找素数流程
得到了大素数，即RSA算法中的p、q，就可以计算出密钥，进行加密等操作了。
⑷. 二元一次不定方程
在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即为所求。
程序中，函数Euc(CBigInt& A);用来完成这种算法。对应前面的叙述，参数a对应A，函数返回值即为X的最小值。
⑸.文件操作
本工程的核心是利用蒙哥马利算法快速实现RSA加密，为了便于研究对字符串的加密过程，以及记录字符串的密文样本，程序把字符串写入TXT文档，再进行加密解密操作，这样就需要对文件进行操作，以二进制数据流对文件进行读出写入操作。在这里使用一个CFILE类，使用CFILE类对文件进行简单的读写操作十分方便，本工程以一个char型的指针data来存放获得的字符串，用DWORD型变量flen来存放Cfile类中成员函数GetLength()获得的字符串长度，然后直接使用成员函数read(),write()来进行文件的读写操作。

文件的读写操作代码见附。
⑹. 按常规RSA算法实现加密与解密
最后，类CDemoDlg基于前面的准备工作，实现RSA密钥生成和加解密的界面化功能。（界面代码多由C++编译器自动生成，在此不再赘述）在类CDemoDlg的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行RSA加解密操作，也可以载入用户写入的密钥或再次随机生成密钥。类中各成员频繁的用到字符串和vlong类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将unsigned指针指向的一段空间里保存的一个大数，表示成十六进制形式的字符串文本。编码转换通常是用C风格的指针操作。
由于是对文件进行加密，所以涉及对文件内容进行读写操作，这里使用到了CFile类。需要加密和解密的数据是通过字符串参数置入的。由于字符串的结尾字符“\0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“\0”来决定，程序里引入一个unsigned类型的参数来决定置入的串长度，通过Cfile类中的Getlength()函数获得文件中字符串的长度，这样就解决了加密连\0数据时候被截断的问题。
加密解密流程均为标准RSA算法，具体过程和使用方法参见源程序和接口文档。

本文来自think58 [版权所有：http://think58.com]

⑺. 核心类库综述
综上几小节所述，实现RSA加密算法的C++核心类库由两个类组成，类名和对应的功能描述总结如表2-1和图2-2所示。
表2-1：RSA加密算法的C++类库中的类
CBigInt 主要包含大数四则运算，素数生成，检测，密钥生成，存储，RSA核心算法等。
CDemoDlg 主要包含界面功能的实现，按钮触发时间等。

本文来自think58

[来源：http://www.think58.com]

图2-2：主要函数成员
3.软件整体测试与分析改进
3.1 编写测试各项性能需要的计时程序
由于对几个字符的字符串进行RSA加密，所用时间只需10几毫秒，一般的程序计时函数无法达到要求测试结果很可能是0，于是在这里定义了2个long型变量t1,t2来分别存储加密函数运行前后GetTickCount()函数获得的系统时间,然后将两个值相减获得消耗时间，这样做还会有较大误差，于是再次进行了改进，通过一个简单的for循环让程序运行1000次 ，然后将t2-t1的值除1000，以获得较为精确的时间。
附录中给出了这段操作的源代码。
3.2 测试数据与分析改进
3.2.1 密钥生成测试
生成密钥运算最费时的工作是寻找素数。如2.2.1.3小节所叙述，寻找素数是一项颇为复杂的工作，其速度可能受以下影响：RSA加密需要的n的位数（寻找素数的整数起点大小bits），素数通过小素数表进行检查，通过拉宾米勒算法测试素数。其中最具影响力的因素显然是RSA加密需要的n的位数。以下对N的位数对生成密钥时间影响进行测试，暂且忽略操作系统调度对测试的影响。测试PC配置为CPU 奔腾4 2.4GHZ/外频100MHZ/物理内存1024MDDR/MSI6398主板845 Ultra-AD芯片组，下文测试中，未说明PC配置的也都在同一PC完成，不再重复。 [资料来源：THINK58.com]
密钥生成测试数据见表3-1。
表3-1：RSA加密模数n与密钥生成耗时的关系
加密位数n (bit) 第一次 （毫秒） 第二次（毫秒） 第三次（毫秒） 第四次（毫秒） 第五次（毫秒） 平均值（毫秒）
128 22 20 21 21 21 21
256 126 125 118 131 130 126
512 844 875 812 935 770 847
1024 7030 3205 4785 3926 6399 5069
（红色为行中最大，兰色为行中最小）
观察表上的统计数据，很容易发现随着加密位数的增加，密钥生成需要的时间显著增加。在测试范围内，随着加密位数增大，每一行中的最大最小值差距也呈粗略的增大趋势。也就是说对于长密钥来说，RSA随机生成密钥消耗时间的可能范围较大。这是因为对于大整数来说，可能出现在较长一段区间中没有素数的情况。
此表仅能从实验的角度直观理解，具体到一次密钥生成的运算，所需要的时间是很不确定的，比如，一次512位的密钥生成，需要的时间完全可能比一次256位的密钥生成时间短，由于素数分布规律非常奥妙，加上测试运算需要的时间颇长，这里很难给出对于一个具体位数的密钥生成所需时间的统计模型。
3.2.1 加解密测试
加密解密测试是本工程的核心，重在反映RSA算法对小型文本文件加密的可行性，以及蒙哥马利算法对RSA算法的提速效果。这里给出几组不同角度进行测试的数据。

think58

⑴.用相同的密钥对不同长度的文件公钥加密，私钥解密，各自消耗的时间与待加密字符串大小的关系
随即生成两组密钥，一组n长512bit，一组n长1024bit。密钥具体数据见附录。
分别对一组不同大小的文件进行公钥加密。统计消耗时间情况如表3-2：
表3-2：加密消耗时间测试
n位数 文件大小 20Byte（毫秒） 40Byte 60Byte 80Byte 100Byte
512bit公钥加密 119 123 125 128 138
512bit私钥解密 330 453 473 503 508
1024bit公钥加密 442 464 469 473 479
1024bit私钥解密 681 721 721 741 743
从表3可以看出，使用同一公开密钥加密不同大小的文件，消耗时间随着文件大小的增加线性的增加，和1.2.1小节分析的完全一致。对于较大的文件，加密位数对时间的影响十分明显。对于100字节的文件来说，1024bit的公钥加密比512bit的耗时多2.5倍左右；1024bit的私钥解密比512bit的耗时多1.5倍以上。对于一定的加密位数来说，私钥解密所需要的时间比公钥加密需要的时间长。对于一定大小的文件，使用512bit的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的3倍左右；而如果使用1024bit的密钥，私有密钥解密需要的时间是公开密钥加密需要时间的1.5倍以上。可见，本软件密钥长度越长，私有密钥解密与公开密钥加密的耗时比越大，这和其他软件是一致的。因为根据PCKS #1的RSA的应用建议，e是比较短的，而d和n的长度差不多，这就使得求与d、n有关的幂模运算量比与e、n有关的幂模运算量大很多，而且随着n的增加，两组幂模运算的运算量差距也迅速加大。 think58

[资料来源：www.THINK58.com]

⑵.利用蒙哥马利算法进行幂模运算改进，加密时间与改进前RSA加密时间的对比测试
蒙哥马利幂模运算是对RSA算法优化的最常见手段，是提高加密速度，实现相对快速的RSA加密的关键。现测试蒙哥马利算法改进过的加密算法与普通RSA加密算法，使用相同密钥对，对相同文件加密所用时间。如表3-3： think58 [资料来源：http://THINK58.com]

表3-3：蒙哥马利改进测试
文件大小（B） 20 40 60 80 100
512位密钥 Montgomery所用时间（毫秒） 35 35 34 37 42
普通RSA所用时间（毫秒） 119 123 128 133 133
1024为密钥 Montgomery所用时间（毫秒） 70 73 89 101 105
普通RSA所用时间（毫秒） 442 461 463 469 467
通过上表可以得出，使用蒙哥马利幂模运算确实一定程度上提高了RSA加密速度，使用512位密钥加密文件蒙哥马利算法改进后的加密所需时间为为改进的算法所用时间的三分之一左右，而1024位密钥加密文件时，仅为四分之一左右，蒙哥马利幂模运算大大提高了加密效率，当文件大小更大，密钥长度更长的情况下，蒙哥马利幂模运算的优势将更能体现。
copyright think58