RSA文件加密原理及代码实现(三)
在flex_unit的存储功能基础上，将其派生，得到vlong_value，在vlong_value中实现四则运算函数，并实现强制转换运算符unsigned，以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类vlong，关联(Associate，即使用vlong_value类型的对象或其指针作为成员)vlong_value，在vlong重载运算符。这样，当我们操作vlong大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。之所以将vlong_value的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。
2. 大数幂模与乘模运算•Montgomery幂模算法
在实现了vlong类型后，大数的存储和四则运算的功能都完成了。考虑到RSA算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个vlong的友元，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质，先将幂模运算化简为乘模运算。
通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D=，E=15，可分解为如下6个乘模运算。
归纳分析以上方法，对于任意指数E，可采用如图2-4的算法流程计算 。
图2-4 幂模运算分解为乘模运算的一种流程
按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。
① 求的值
开始 D = 1 P = 2 mod 17 = 2 E = 15
E奇数 D = DP mod n = 2 P = PP mod n = 4 E = (E-1)/2 =7
E奇数 D = DP mod n = 8 P = PP mod n = 16 E = (E-1)/2 =3
E奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =1
E奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =0
最终D = 9 即为所求。
② 求的值
开始 D = 1 P = 2 mod 17 = 2 E = 8
E偶数 D = 1 P = PP mod n = 4 E = E/2 =4
E偶数 D = 1 P = PP mod n = 3 E = E/2 =2
E偶数 D = 1 P = PP mod n = 9 E = E/2 =1
E奇数 D = DP mod n = 9 P = 不需要计算 E = (E-1)/2 =0
最终D = 9 即为所求。
观察上述算法，发现E根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变量D,P,E的二进制各位下标从左到右为u,u-1,u-2,…,0。
Powmod(C,E,n)
{
D=1;
P=C mod n;
for i=0 to u do
{
if(Ei=1)D=D*P(mod n);
P=P*P(mod n);
}
return D;
}
有些文献将上述算法称为平方乘积二进制快速算法，例如参考文献中的《基于RSA算法的一种新的加密核设计》，其实这种算法本质上和图2-4的流程完全一致，只是把根据指数奇偶分开的减一和除以二合并成对指数二进制各位的判断而已。在本软件的代码中采用直接扫描vlong二进制各位的办法。
剩下的问题就是乘模运算了。提高乘模运算的速度是提高模幂运算速度的关键。一般情况下，n是数百位乃至千位以上的二进制整数，用普通的除法求模而进行乘模运算是不能满足速度的要求的。为此，Montgomery在1983年提出了一种模加右移的乘模算法（主要著作发表于1985年），从而避免了通常求模算法中费时的除法步骤。本软件仅仅是应用Montgomery(蒙哥马利)算法，算法的具体推导证明需要颇多数论知识，不在本文的讨论范围内，如需了解可参见蒙哥马利的相关著作。下面简单描述RSA中常用的Montgomery(蒙哥马利)算法供参考理解源程序。
选择与模数n互素的基数R=2k，n满足2k－1≤n<2k， n应为奇数。并且选择R-1及n’，满足0< R-1<n, 0< n’<n,使得 RR-1-nn’＝1。对于0≤m<Rn的任意整数,Montgomery给出求模乘法mR-1 mod n 的快速算法M(m):
M(m)
{
if (t≥n) return (t-n);
else return t;
}
因为，故t为整数；同时，得。由于，M(m) 中t结果范围是0≤t<2n，返回时如果t不小于n，应返回t-n。
本软件程序中，RSA核心运算使用的乘模算法就是 M(A*B)。虽然M(A*B)并不是乘模所需要的真正结果，但只要在幂模算法中进行相应的修改，就可以调用这个乘模算法进行计算了。本软件起初未使用Montgomery 乘模算法时，加密速度比使用Montgomery乘模算法慢，但速度相差不到一个数量级。
将上述乘模算法结合前面叙述的幂模算法，构成标准Montgomery幂模算法，即本软件所使用的流程，叙述如下。
M(m)
{
k = ( m * n’ ) mod R;
x = (m + k*n ) / R;
if (x>=n) x -= n;
return x;
}
exp(C,E,n)
{
D=R-n;
P=C*R mod n;
i=0;
while(true)
{
if(E的当前二进制位Ei==1)D=M(D*P); //从低位到高位检测二进制位
i+=1;
if(i==E的二进制位数)break;
P=M(P*P);
}
return D*R-1 (mod n);
}
在具体的实现中，对应monty类的mul和exp方法。全局函数modexp初始化monty对象并调用其exp方法，使用的时候直接调用modexp即可。
3. 寻找素数•Eratosthenes筛选与Fermat素数测试
首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到100%准确的大素数，都是通过查已经计算好的素数表的方式。但是素数表的方式给RSA的安全性带来隐患，因为攻击者如果得到了密钥生成时所使用的素数表，攻破RSA加密的难度将会大大降低。本程序起初使用素数表的方式，后来考虑到安全性问题，生成密钥的方式改为随机计算生成。这样，短时间内如果要得到一个100%准确的大素数是很困难的，只能以尽可能高的概率得到一个大素数。
RSA文件加密原理及代码实现(三)由毕业论文网（www.huoyuandh.com）会员上传。
