RSA算法的C++实现

RSA算法的C++实现

[摘要] 公 钥密码体制出现以前，所有的密码算法基本上都是基于代替和置换。而公钥密码体制则是基于新的理论和技术：它突破了传统的代替与置换，是数学函数；它以非对 称的形式提供两个密钥。两个密钥的出现对于保密性、密钥分配、认证等都有划时代的意义。非对称密码体制在加密和解密操作中使用不同的密钥，从而构成不对称 体制。加密密钥可以公开，解密密钥必须保密。其密钥分发简单，可以通过一般的通信渠道分发，需要保密保存的密钥量大大减少，N个人只需N把密钥(线性增 长)，可满足互不相识的人之间的私人谈话的保密要求，可以完成数字签名。

[关键词] RSA 加密 模数 明文 密文

1. 概述
    当 前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名 和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。 它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。
    RSA算法是第 一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密 接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 
    该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性：
    1) 已有确定一个数是不是质数的快速算法；
    2) 尚未找到确定一个合数的质因子的快速算法。
    目 前，日益激增的电子商务和其它因特网应用需求使公钥体系得以普及，这些需求量主要包括对服务器资源的访问控制和对电子商务交易的保护，以及权利保护、个人 隐私、无线交易和内容完整性（如保证新闻报道或股票行情的真实性）等方面。公钥技术发展到今天，在市场上明显的发展趋势就是PKI与操作系统的集 成，PKI是“Public Key Infrastructure”的缩写，意为“公钥基础设施”。公钥体制广泛地用于CA认证、数字签名和密钥交换等领域。
    公钥加密算法中 使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但 很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保 护数据信息的完整性。目前为止，很多种加密技术采用了RSA算法，该算法也已经在互联网的许多方面得以广泛应用，包括在安全接口层（SSL）标准（该标准 是网络浏览器建立安全的互联网连接时必须用到的）方面的应用。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。

2. RSA算法的编程思路
    1) 确定密钥的宽度。
    2) 随机选择两个不同的素数p处q，它们的宽度是密钥宽度的二分之一。
    3) 计算出p和q的乘积n 。
    4) 在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。
    5) 从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。
    6) 得公钥（e ，n ）, 私钥 (d , n) 。
    7) 公开公钥，但不公开私钥。
    8) 将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为：

C = P^e mod n    9) 将密文C解密为明文P，计算方法为：
P = C^d mod n    然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密

3. 程序实现
3.1 密钥产生模块流程图

key_produce.h //==本程序提供密钥产生的一些基本数学实现
#include 
class CKEY_PRODUCE 
{
public:
 CKEY_PRODUCE();
 virtual ~CKEY_PRODUCE();
public:
 int JudgePrime(unsigned int prime);//==========判prime是否为素数
 //============================================算出p*q的欧拉值
 int Count_N_AoLa_Num(unsigned int p, unsigned int q, unsigned int * ao_la);
 //============================================求两个数的最大公因数
 unsigned int CountCommonData(unsigned int a, unsigned int b);
 //=============================================随机选择公钥e
 int RandSelect_e( unsigned int ao_la, unsigned int* e );
 //=============================================求b的e次方除d的余数
 unsigned int GetOutNum(unsigned int b,unsigned int e , unsigned int d);
 //=============================================求任意大于2的整数的欧拉值
 unsigned int CountAnyNumAola(unsigned int number);
 //=============================================产生RSA 公_私 密钥
int Produce_RSA_Key(unsigned int p,unsigned int q, unsigned int* Ke, unsigned int* Kd, unsigned int* model);
 //===========================利用加的模等于模的加求e*d = 1 mod model 中的d
 int OverOneNum(unsigned int e,unsigned int model, unsigned int* d);
};
key_produce.cpp//==本程序提供密钥产生的一些基本数学实现

CKEY_PRODUCE::CKEY_PRODUCE()
{}
CKEY_PRODUCE::~CKEY_PRODUCE()
{}
int CKEY_PRODUCE::Produce_RSA_Key(unsigned int p,unsigned int q, unsigned int* Ke, unsigned int* Kd, unsigned int* model)
{
 unsigned int ao_la;
 if( Count_N_AoLa_Num(p, q, &ao_la) )
 {
  if( RandSelect_e(ao_la, Ke) )
  {
//*Kd= GetOutNum (*Ke, CountAnyNumAola(ao_la)-1 ,ao_la) ;
//注：求Kd还是不用 x= a^(n'的欧拉数 - 1) mod n' (其中n'= (p-1)*(q-1) ),因n'的//欧拉数也不好求
   if( OverOneNum(*Ke, ao_la, Kd) )
   {
    *model= p*q;
    return 1;
   }
  }
 }
 return 0;
}
int CKEY_PRODUCE::JudgePrime(unsigned int prime)
{
 unsigned int i;
 unsigned int limit= (unsigned int)sqrt( (double)prime );
 for(i=2; i <= limit; i++)
 {
  if(prime%i==0)
  {
   return 0;
  }
 }
 return 1;
}
int CKEY_PRODUCE::Count_N_AoLa_Num(unsigned int p, unsigned int q, unsigned int * ao_la)
{
 if( !JudgePrime(p) )
  return 0;
 if( !JudgePrime(q) )
  return 0;
 *ao_la = (p-1)*(q-1);
 return 1;
}
unsigned int CKEY_PRODUCE::CountCommonData(unsigned int a, unsigned int b)
{
 unsigned int c ;
 if( c= a%b )
  return CountCommonData(b,c);
 else
  return b;
}
int CKEY_PRODUCE::RandSelect_e( unsigned int ao_la, unsigned int* e )
{
 unsigned int tmp;
 unsigned int div;
 if( ao_la <= 2 )
 {
  return 0;
 }
 srand( time(0) );
 div= ao_la - 2;
 do
 {
  tmp = ( (unsigned int)rand()+90 ) % div + 2;
 }while( CountCommonData(tmp, ao_la)!=1 );
 *e = tmp;
 return 1;
}
//==================================求b的e次方除d的余数
unsigned int CKEY_PRODUCE::GetOutNum(unsigned int b,unsigned int e , unsigned int d)
{
 unsigned int i;
 unsigned int outNum= 1;
 for( i=0; i//=========用了乘的模 等于 模的乘
 {
  outNum *= b;//==============b d如果长过16位，很有可能溢出
  if( outNum >= d )
   outNum %= d;
  if(!outNum)
   return outNum;
 }
 return outNum%d;
}
//==============================利用加的模等于模的加求e*d = 1 mod model 中的d
int CKEY_PRODUCE::OverOneNum(unsigned int e,unsigned int model, unsigned int* d)
{
 unsigned int i;
 unsigned int over= e;
 for(i=1; i {
  over= over % model;
  if( over==1 )
  {
   *d = i;
   return 1;
  }
  else
  {
   if(over+e<= model)
   {
    do
    {
     i++;
     over += e;
    }
    while( over+e <= model );
   }
   else

   {
    i++;
    over +=e;
   }
  }
 }
 return 0;
}
//==================================求任意大于1的整数的欧拉值
unsigned int CKEY_PRODUCE::CountAnyNumAola(unsigned int number)
{
 unsigned int ao_la= 1;
 unsigned int i;  if( number<=1 )
  printf("本函数不处理2以下的范围!\n");
 for(i=2; i {
  if( CountCommonData(number, i)==1 )
   ao_la ++;
 }
 return ao_la;
}

3.2 加密模块流程图

encryption.h//==本程序提供对文件进行加密解密的操作
class CENCRYPTION
{
public:
 CENCRYPTION();
 virtual ~CENCRYPTION();
void Encrypt(UINT PublicKey, UINT mod, FILE* fipRe, FILE* fipWr,char* extrName );
 void Explain(UINT PrivateKey, UINT mod, FILE* fipRe, FILE* fipWr );
 void TxtEncrypt(unsigned* cipSourceTxt, int buffSize, unsigned int Ke, unsigned int model);
private:
//==================================求b的e次方除d的余数
unsigned int GetOutNum(unsigned int b,unsigned int e , unsigned int d);
//==================================对原文进行加密并覆盖原缓冲区
};
encryption.cpp//==本程序提供对文件进行加密解密的操作

CENCRYPTION::CENCRYPTION()
{ }
CENCRYPTION::~CENCRYPTION()
{ }
//==================================对原文进行加密并覆盖原缓冲区
void CENCRYPTION::TxtEncrypt(unsigned* cipSourceTxt, int buffSize, unsigned int Ke, unsigned int model)
{
 int i;
 for( i=0; i < buffSize; i++ )
 {
  cipSourceTxt[i] = GetOutNum( cipSourceTxt[i], Ke, model );
 }
}
//==================================求b的e次方除d的余数
unsigned int CENCRYPTION::GetOutNum(unsigned int b,unsigned int e , unsigned int d)
{
 unsigned int i;
 unsigned int outNum= 1;
 for( i=0; i < e; i++)//=========用了乘的模 等于 模的乘
 {
  outNum *= b;
  if( outNum >= d )
  {
   outNum %= d;
  }
  if(!outNum)
   return outNum;
 }
 return outNum%d;
}
void CENCRYPTION::Encrypt(UINT PublicKey, UINT mod, FILE* fipRe, FILE* fipWr ,char* extrName)
{
 unsigned int ReSize;
 unsigned int uBuf[BUFFER_SIZE]= {0,};
 char cBuf[BUFFER_SIZE];
 unsigned int i;
 for(i=0; i<3; i++)//=====我认为扩展名是3个字符
 {
  if(extrName)//=========如果有扩展名, 将扩展名放入uBuf 和数据一样加密
  {
   uBuf[i]= 0;
   *((char*)(&uBuf[i])) = extrName[i];
  }
  else
   uBuf[i]= 0;
 }
 if(extrName)//===============如果有扩展名, 将扩展名加密
  TxtEncrypt(uBuf, 3,PublicKey,mod);
fwrite( (char*)uBuf,1, 3*sizeof(unsigned int), fipWr);//密文前12个,字节中是源文件的 扩展名信息
 do
 {
  ReSize= fread(cBuf, 1, BUFFER_SIZE,fipRe);
  if(ReSize)
  {
   unsigned int record=1;
   unsigned int WrNum;
   for(i=0; i < ReSize; i++)
   {
    uBuf[i]= 0;
    *((char*)(&uBuf[i])) = (cBuf[i]) ;
   }    TxtEncrypt(uBuf, ReSize,PublicKey,mod);    WrNum= fwrite( (char*)uBuf,1, ReSize*sizeof(unsigned int), fipWr);
   printf("第%d次写入%d字节!\n",record++, WrNum);
  }
 }while(ReSize == BUFFER_SIZE);
}
void CENCRYPTION::Explain(UINT PrivateKey, UINT mod, FILE* fipRe, FILE* fipWr )
{
 unsigned int ReSize;
 unsigned int uBuf[BUFFER_SIZE]= {0,};
 char cBuf[BUFFER_SIZE];
 do
 {
  ReSize= fread(uBuf, sizeof(unsigned int), BUFFER_SIZE,fipRe);
  if(ReSize)
  {
   unsigned int i;
   unsigned int record=1;
   unsigned int WrNum;
   TxtEncrypt(uBuf, ReSize,PrivateKey,mod);
   for(i=0; i    cBuf[i]= (char)(uBuf[i]);
   WrNum= fwrite( cBuf,1, ReSize, fipWr);   
   printf("第%d次写入%d字节!\n",record++, WrNum);
  }

 }while(ReSize == BUFFER_SIZE);
}

3.3 解加密模块流程图

4. RSA程序的运行

4.1 密钥产生
    点击‘密钥产生’按钮，在 公钥、私钥、模数所示的编辑框内将出现随机产生的密钥。
    也可以点击‘导入密钥’按钮来使用以前产生的密钥，用‘导出密钥’按钮保存本次产生的密钥（下图是导入密钥的截图）

4.2 明文加密
    点击‘加密’铵钮，在弹出的‘加密’对话框中选择 待加密的明文，存加密结果的密文 ，点击‘OK’即可生成密文（其程序截图如下）

4.3 密文解密
    确定私钥、模数 和 加密时的公钥、模数相对应， 点击‘解密’按钮，在弹出的‘解密’对话框中选择 待解密的密文，存解密结果的明文， 点击‘OK’即可生成明文 （其程序截图如下）

5. 算法总结
    我写该程序的目的是为了掌握RSA算法的基本原理、体验应用效果，所以算法中还有些地方需要改进，才能使其更具有实用性，例如，由于没有用到“大数运算子模块”，所以随机所选的素数必须归定在一定的范围里，这在实际运用中就会有安全隐患。
    在编定程序过程中，经老师指点，我实现了对任意类型文件的加密，且解密过程能够自动恢复原明文的扩展名，使用户不要为事先约定文件类型而烦恼。
    以上是本人的一些真实感受，如有不是之处，请指正。


6. 软件下载演示


7. 参考文献
[1] Douglas R.Stinson.《密码学原理与实践》.北京:电子工业出版社,2003,2:131-132
[2] 西蒙.辛格.《密码故事》.海口:海南出版社,2001,1:271-272
[3] 嬴政天下.加密算法之RSA算法,，2003
[4] 加密与数字签名.