VC412 RSA公钥密码算法的一种快速实现

公钥加密技术。VISA、〖本文来自：计算机毕业网  〗MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在人们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。
当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法RSA进行蒙哥马利改进。通过对幂模运算的改进，简化，提高RSA加密效率。
幂模运算是RSA的速度瓶颈，在全过程中都有使用。蒙哥马利算法是其中一种。影响模乘运算速度关键在于模运算，模运算其实是除法运算，除运算相对与加减乘运算要费时的多。因此，如果在模乘运算中不用除法或尽量少用除法将大大提高RSA处理的速度。1985年，Peter Montgomery发现了一种只要乘法和数的位移就可以实现模乘运算的灵巧算法，这就是著名的蒙哥马利模乘算法。 think58.com [资料来源：http://www.THINK58.com]

RSA更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台j2ee。事实上，在j2se的标准库中，就为安全和加密服务提供了两组API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是java.security包，此软件包包含的是一组核心的类和接口，Java中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA的基础上作了扩展，JCE也是由几个软件包组成，其中最主要的是javax.crypto包，此软件包提供了JCE加密技术操作API。javax.crypto中的Cipher类用于具体的加密和解密。在上述软件包的实现中，集成了应用RSA算法的各种数据加
〖本文来自：计算机毕业网  〗
1.  利用BORLAND C++BUILDER平台
C++BUILDER界面制作功能强大，操作方便，但由于现在大多数公开C++ RSA算法代码都是用VC++编写，在调用函数上有诸多麻烦，牵涉到很多动态联结，调试比较困难。
2.  利用MICROSOFT VISUAL C++平台
从最初的Visual C++ 1.0到最近的Visual C++.NET , Visual C++经过近十年的发展，现已成为Windows操作系统环境下最主要，最权威的软件开发工具。内部集成众多算法实现函数，可方便的调用，给编程及调试带来极大的方便，最终本工程选定以VC++做为平台，进行本软件的开发工作。

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

2.2 各部分的设计与开发
2.2.1 实现RSA加密算法的C++核心类库
⑴. 大数四则运算与运算符重载:
根据RSA算法的要求，为了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C++类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍四则运算的实现原理。
大数的四则运算由CBIGINT类实现，类中申明了以下若干函数：
基本操作与运算:
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”
Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”
输入输出:
Get，从字符串按10进制或16进制格式输入到大数
Put，将大数按10进制或16进制格式输出到字符串
RSA相关运算: think58
Rab，拉宾米勒算法进行素数测试
Euc，欧几里德算法求解同余方程
RsaTrans，反复平方算法进行幂模运算 think58

将大数看作一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x10000000，假如将一个1024位的大数转化成0x10000000进制，它就变成了32位，而每一位的取值范围就不是0-1或0-9，而是0-0xffffffff。这里正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机来说，实际上是一回事，但是这里完全可以针对unsigned long数组进行“竖式计算”，而循环规模被降低到了32次之内，并且算法很容易理解。
例如大数18446744073709551615，等于“ffffffff ffffffff”，它就相当于10进制的“99”：有两位，每位都是ffffffff。而大数18446744073709551616，等于“00000001 0000000000000000”，它就相当于10进制的“100”：有三位，第一位是1，其它两位是0。如果要计算18446744073709551616-18446744073709551615，就类似于100-99： [资料来源：http://think58.com]

首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到100%准确的大素数，都是通过查已经计算好的素数表的方式。
经过2.2.1.1和2.2.1.2小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类CBigint之中。外部只要调用本类实例的成员函数void GetPrime(int bits);就可以以bits为起点，得到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。
本工程在素数生成时，通过数组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; think58.com [资料来源：http://think58.com]
 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;
 }
}