RSA算法的分析与实现


[摘要] 随着信息技术的发展，特别是电子商务的发展，网络信息的安全传输逐渐成为人们最为关心和头痛的事情。密码安全研究与设计是当前密码学领域的热点问题。通过对RSA的安全性进行了分析，提出构造安全素数。
    在实际应用中 ，在混合密码体制中占有重要地位RSA算法存在着计算复杂，运行速度慢的问题。这些基本算法包括模加，模乘，模逆和模幂运算。大数运算是很费时间的，尤其是大整数的模逆和模 幂运算。同时我将结合自己在用基本类型进RSA算法中，应注意的一些问题.进行论述。

[关键词] RSA算法 密码 安全
1. 绪论
    RSA密码体制是美国麻省理工学院（MIT）Rivest、Shami和Adleman于1978年提出来的，它是第一个理论上最为成功的公开密钥密码体制，它的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它们的素数因子却是非常困难的，它属于NP—完全类，是一种幂模运算的加密体制。除了用于加密外，它还能用于数字签字和身份认证。下面将从各个方面来详细对RSA公钥体制进行研究。
1.1 RSA的构成
    RSA系统由以下几部分组成：
    (1) 随机选取的在素数P和Q，还有N ，其中N=P*Q ，P和Q保密，N公开。
    (2) 任取 (n)=（P-1）*(Q-1)，其中 (n)表示比n小的素数的个数，任取2<=e<= (n),且(e, (n))=1,e为加密密钥，公开。
    (3) (计算d,使e*d=1(mod (n)),称d为e对模 (n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大小小于n,c为密文，则其加密和解密算法如下：
    加密算法 C=E(m)=me(mod n)
    加密算法 m=D(c)=cd(mod n)
    在RSA系统中(e,n)构成加密秘钥，即公钥，(d,n) 构成解密秘钥，即私钥。
1.2 RSA思想的证明
    RSA是基于数论中的Euler定理和其它同余性质的，在证明RSA系统思想正确性之前，先给出Euler定理和同余式相乘的性质：
    Euler定理：设（a,n）=1,即a 和 n互素，则有 a<sup>Φ(n) = 1 (mod n )    同余式相乘性质:设有
    a=b (mod n),c=d (mod n) 则有
a*c=b*d ( mod n)    证明RSA系统思想正确性主要是看能否从密文c和解密秘钥d恢复明文m,即由c和d,计算出m=D(c)=Cd (mod n)。
    下面就证明是否能从密文c和解密密钥d恢复明文m,
    ∵ 为 e*d=1 (mod (n))
    ∴ e*d=k* (n)+1,其中K为任意整数。
    由解密公式D(c) = Cd(mod n) 有：
    D(c)=Cd(mod n)=Me*d=Mk*Φ(n)+1= Mk*Φ(n)*M
    又由Euler定理有
    Mk*Φ(n) =(MΦ(n))k = 1( mod n)
    同样由同余式相乘性质有      D(c)=Cd(mod n)=Me*d=Mk*Φ(n)+1 = Mk*Φ(n)*M = M (mod n)
    由于明文块数值大小小于n,则有
    D(c)=Cd(mod n)=Me*d=M k*Φ(n)+1 = Mk*Φ(n)*M =M (mod n) = M
    故RSA中，能利用e和c恢复明文m,则RSA的系统思想证明是正确的。但众所周知RSA是基于整数因子分解的密码体制，它利用的是：求两个大素数的乘积是很容易计算的，但分解密两个大素数的乘积，求出它们的素数因子却是非常困难的，这样一个数学难题，它属于NP-完全类。因此RSA的安全性完全信赖于因子分解的困难性，只要N=P*Q被因子分解，则RSA便被击破，这样在RSA系统中怎样选取大的素数P，Q才是关键所在。
1.3 RSA中素数的选取
    在RSA中，因N=P*Q， 若P，Q被知道，即能将N因子分解，则由 Φ(n)=（P-1）*(Q-1)可以算出。由于e是公开密钥，且解密秘钥D关于E满足
    D*E=1 (mod Φ(n))
    则D也不难求得，这样RSA系统便被完全攻破。
    RSA中的素数都是上面位的十进制数，怎样才能选择好的P和Q，怎样才能生成这样的数，并且判断它是否为素数，这是一个RSA系统关键的问题。针对素数P和Q的选择，1978年Rivest等人在正式发表的RSA公开密钥的论文中，就建议对素数P和Q的选择应当满足：
    (1) P、Q要足够在，在长度上应相差几位，且二者之差与P、Q位数相近；
    (2) P-1与Q-1的最大公约数GCD(P-1,Q-1)就尽量小；
    (3) P-1与Q-1均应至少含有一个大的素数因子。
    并把满足这些条件的素数称为安全素数。
1.4 RSA安全性分析
    在公布RSA算法之后，在使用RSA密码体制和分析RSA算法发现了一系列的算法本身脆弱性及其存在的问题。
    （1）RSA公钥密码体制在加密或解密变化中涉及大量的数值计算，其加密和解密的运算时间比较长，这比数据加密标准DES的计算量开销大，在一定程度上限制了它的应用范围，以致于实际使用RSA密码体制无法用软件产品，必须用超大规模集成电路的硬件产品。
    （2）虽然提高N=P*Q的位数会大大提高RSA密码体制的安全性，但其计算量呈指数增长，以致使其实现的难度增大，实用性降低。
    （3）RSA公钥密码体制的算法完整性（指密钥控制加密或解密变换的唯一性）和安全性（指密码算法除密钥本身外，不应该存在其它可破译密码体制的可能性）沿有等进一步完善。
    （4）RSA算法面临着数学方法的进步和计算机技术飞跃发展带来的破译密码能力日趋增强的严重挑战。因子分解问题有了长跑的发展，1995年人类成功地分解了128位十进制数RSA密码算法，破译512位长的RSA指日可待。
    尽管如此，自1978年RSA算法公布以来，公开密钥密码已从理论研究进入实际应用研究阶段。RSA公开密钥密码算法在信息交换过程中使用比较广泛，安全性比较高。以当前的计算机水平，如选择1024位长的密钥（相当于300位十进制数字）就认为是无法攻破的。

2. RSA算法的程序实现
    首先产生密钥，过程如下：
    (1) 随机产生两个长度为K/2位的素数P 和 Q
    (2) 计算公钥 publicKey=P*Q;(publicKey 是k位的长度)
    (3) 随机产生一个加密密钥 keyE, 2<=keyE<=Φ(n)-1其中GCD(keyE, Φ(n))=1;
    注意这是保证解密密钥keyE *keyD mod Φ(n)=1 有解的充要条件， Φ(n)称为n的欧拉函数,值为: Φ(n)=(P-1)*(Q-1)
    (4) 求解解密密钥keyD=keyE-1 mod (n) ,keyE-1为解密密钥keyD的逆元 ，此公式原方程为(keyE*keyD mod (n)=1)
    由此公钥，加密密钥，解密密钥全部产生。
    其次 对明文加密或对密文进行解密,过程如下:
    (1) 加密: C = MkeyE mod publicKey;其中M表示明文,C表示密文
    (2) 解密: M = CkeyD mod publicKey. 其中M表示明文,C表示密文

图1 加密或解密流程图
图2 总的流程图
图3 产生密钥流程图     根据前述过程，下面是RSA加密解密代码实现,以及在实现过程中应注意的细节。

2.1 产生密钥
2.1.1 产生两个素数iPrimeOne,iPrimeTwo,调用的函数为long int ProductPrime();
////////////////////////////////////////////////////////////////////////////////
// 产生第一个大素数
long int iPrimeOne=ProductPrime(); //产生第二个大素数
long int iPrimeTwo=ProductPrime(); //防止产生相同的素数
while(iPrimeTwo==iPrimeOne)
{
   iPrimeTwo=ProductPrime();
}
/////////////////////////////////////////////////////////////////////////////////
/***************************
* 产生素数
****************************/
long int CRSADlg::ProductPrime()
{ long int iBigPrime=0; //用来保存产生的素数
  //产生素数
  while(true)
  { //将素数产生的范围控制在100-----200以内，
    BigPrime=rand()%100+100; //判断是否为素数,是，跳出循环
    if(IsPrime(BigPrime)) break;
  }
  return BigPrime; //返回产生的素数
}
    上面这个函数中我将素数的大小控制100----200以内.即产生的素数是三位的，这个素数值不能太大，因为我用的是基本类型做加密解密,太大的话，两个素数的乘积将会超出long int 所能表示的最大数,太小的话，产生的公钥的值可能会比明文的值小，所以素数值的大小，取决于你的加密解密要求。可以使用下面这个小程序测一下你的long int 所能表示的最大数，来决定产生的素数最大值为多少
#include
#include
using namespace std;
void main()
{
  cout<<"largest long int"<::max()<}
//*************************************************
// 素数判断. 除到它的开方仍不能被整数，它就是素数
//*************************************************
bool CRSADlg::IsPrime(long int iValue)
{
  long int iPrime=iValue;
  //求这个数开方，加1是为了防止强制类型转换时，使这个数被
  //四舍五入后可能少除了最后一个数，故加上1来避免这种误差
  long int iSQRT=(long int) sqrt( iPrime)+1;
  //从2开始到要判断的这个数是否素数的开方+1
  for(int i=2;i  {
  //能够整除，说明不是素数
    if((iPrime % i)==0)
    {
     return false;
    }
  }
  //都不能整除，说明这个数是素数
  return true;
}

2.1.2 求解公钥，以及公钥的欧拉函数
    long int iPublicKey=iPrimeOne*iPrimeTwo;
    long int iOrLa=(iPrimeOne-1)*(iPrimeTwo-1);

2.1.3 求加密密钥iKeyE,调用的函数为ProductKEYE(long int iOrLa)
    long int iKeyE= ProductKEYE(iOrLa);
//*************************************************
// 产生加密密钥KEYE,加密密钥的要求
// 2<=iKeyE<=iOrLa-1
// 且iKeyE与iOrLa互素
//**************************************************
long int CRSADlg::ProductKEYE(long int iOrLa)
{
  long int keyE=0;
  while(true)
  {
    keyE=rand()%iOrLa;
    //如果加密密钥大于2，且与欧拉函数公约数为1，即互素满足
    if( (keyE>=2) && GCD(keyE,iOrLa)==1)
    {
      break;
    }
  }
  return keyE;
}

//**************************
//求两个数的最大公约数
//**************************
long int CRSADlg::GCD(long int keyE,long int iOrLa)
{
  long int iDividend=iOrLa; //被除数
  long int iDivisor=keyE; //除数
  long int iResidual=iDividend%iDivisor; //余数
  //碾转相除法
  while(iResidual!=0)
  {
     //将除数作为被除数
    iDividend=iDivisor;
     //把余数作为除数
    iDivisor=iResidual;
     //求新的余数
    iResidual=iDividend%iDivisor;
  }
  //最大公约数
  return iDivisor;
}

2.1.4 求解密密钥iKeyD
    求解密密钥实际上是如何去解一次同余方程 ax ≡ 1 mod n。根据费马定理与欧拉定理给出了同余方程的解为:
    x=a(Φ(n)-1) mod n
    由此可得出iKeyD*iKeyE≡ 1 mod Φ(n)
    即iKeyD=iKeyE(Φ(Φ(n))-1) mod Φ(n)
    对解密密钥的求解可以分为二步
1) 求欧拉函数的欧拉函数,欧拉函数的定义是: 1,2,3…………n-1中与n互素的个数称为n的欧拉函数
//**************************
//求解欧拉函数的欧拉函数
//**************************

long int CRSADlg::IOrLaOfIOrLa(long int iOrLa)
{
  //1与任意的一个数互素故初始化1
  long int iOrLaOfiOrLa=1;
  for(int i=2;i
  {
    //根据公式，2……n-1中互素（公约数为1）则欧拉值加1
    if(GCD(i,iOrLa)==1)
      iOrLaOfiOrLa++;
    }
  return iOrLaOfiOrLa;
}

2) 做高次模运算
//****************************
// 这个函数用来做高次模
//****************************
long int CRSADlg::HightMod(long int iBottomNumber,long int iExponent,long int iMod)
{
  long int iValueMessageAfterCompute=1;
  long int iValueMessage=iBottomNumber;
  long int iKey=iExponent;
  //把key以2进制的形式进行移位乘用
  while(iKey)
  {
    if(iKey&1) iValueMessageAfterCompute=(iValueMessageAfterCompute*iValueMessage)%iMod;
    //高位右移
    iKey>>=1;
    iValueMessage=(iValueMessage*iValueMessage)%iMod;
  }
  return iValueMessageAfterCompute;
}

    因为在做加密和解密的时候也存在做高次模运算，所以在这暂不赘述，在加密和解密过程里将详细讲解
//***************************
//解密密钥
//**************************
long int CRSADlg::ProductKEYD(long int *iOrLaPtr,long int *iKeyEPtr)
{
  //求欧拉函数的欧拉函数 iOrLaOfiOrLa= Φ(Φ(n))
  long int iOrLaOfiOrLa=IOrLaOfIOrLa(*iOrLaPtr);
  //求高次模iKeyE( iOrLaOfiOrLa-1) mod Φ(n)
  //第一参数为iKeyE,第二个参数为 Φ(Φ(n))-1,第三个参数为 Φ(n)
  long int iKEYD=HightMod(*iKeyEPtr, iOrLaOfiOrLa-1, *iOrLaPtr);
  return iKEYD;
}

所以,可得解密密钥
//产生解密密钥
long int iKeyD=ProductKEYD(&iOrLa,&iKeyE );
这里还一种方法可以解解密密钥
因为iKeyD * iKeyE mod iOrLa =1

long int ProductKEYD(long int ikeyE,lont int iOrLa)
{
  long int iKeyD=iOrLa /iKeyE
  while(true)
  {
    if(((iKeyD* iKeyE)%iOrLa)==1)
      break;
    else
      iKeyD++;
  }
  return iKeyD;
}
    这种方法有个缺陷，当iKeyD与iKeyE较大时，iKeyD* iKeyE就会越界，所以这种方法较适用于自定义的大数据类型，当然，这种函数的执行速度还是比较慢的.

2.2 数据的加密解密
    产生密钥后，下一步所要做的就是进行加密和解密，首先我们看一下加密解密的公式：
    C=MkeyE mod publicKey;
    M=CkeyD mod publicKey;
    其中C表示明文，M表示密文，keyE表示加密密钥,KeyD表示解密密钥,publicKey表示公钥.     由此公式可以看出，难点是如何做高次模，先做指数运算，再求模，显然是行不通的，因为keyE通常比较大,M的指数次方运算后所得的值可能会越界，这样求模后的值肯定不正确，(M=CkeyD mod publicKey同理),而且这样做的效率也十分的低。在说明如何做高次模运算时，我们先看一下这个公式:
    (a*b)mod n = [(a mod n)*(b mod n)](mod n)
    当a=b时,这个公式就是
    a mod n=a mod n
    a2 mod n =(a*a)mod n = [(a mod n)*(a mod n)](mod n)
    a3 mod n =( a2 *a)mod n = [(a2 mod n)*(a mod n)] mod n
    ∶
    ∶
    an mod n =( an-1 *a)mod n = [(an-1 mod n)*(a mod n)] mod n
    an+1 mod n =( an *a)mod n = [(an mod n)*(a mod n)] mod n
    在实际编程时，我们不需要按一个一个底数分解因子，而是以2次方的形式迭代计算高次模。
//***********************
//做高次模运算
//***********************
long int CEncryptAndDecrypt::GetValues(long int iMessage,long int key)
{
  //保存乘积的模
  long int iValueMessageAfterCompute=1;
  //指数
  long int iValueMessage=iMessage;
  //底数
  long int iKey=key;
  //把key以2进制的形式进行移位相乘做迭代
  while(iKey)
  {
    //当前的最低位是否为1，是将计算一次乘积
    if(iKey&1) iValueMessageAfterCompute=(iValueMessageAfterCompute*ValueMessage)%PUBLICKEY;
    //高位右移，即指数除以了2
    iKey>>=1;
    //做一次二次方，一直到指数最高位为0为止 iValueMessage=(iValueMessage*iValueMessage)%PUBLICKEY;
  }
  return iValueMessageAfterCompute;
}
    至此，对RSA算法的分析完毕。我在编写RSA加密解密时是以字符为单位，而在实际应用中可以以行单位进行加密解密，这样可以提高加密解密的速度，但总体来看，RSA加密解密的速度在目前的加密解密算法中是最慢的。

3. 总结
    本论文对当前应用广泛的RSA公钥密码体制进行了分析与研究，了解了怎样的密码体制才能充分发挥RSA的安全作用。分析了RSA加密解密的安全性，以及如何选取RSA密钥长度的问题。同时我们考虑到在实际的应用过程中，在满足安全性前提下应当降低计算的复杂度，提高信息加、解密的速度。便于降低成本，利于推广应用等因素，目前国内外对RSA算法实现的研究大多是在运算速度很高的计算机上，在硬件上也主要采用串行处理，为了提高速度，安全性就必然很差，相反，为提高安全强度，则运算处理速度又会降低。在RSA算法中，最基本的算法主要包括模加、模乘、模逆和模幂运算。大数运算很费时间，尤其是大整数的模逆和模幂运算。为了得到较快的加/解密速度，本程序进行了深层次的优化，主要采用移位的方法，大大提高了RSA算法实际应用的运算速度和执行效率。

    总之，随着密码技术的进一步发展，以及计算机安全研究的技术人员的不断努力，我相信具有更高性能、更高效率的密码加密体制将会诞生。</sup>