RSA算法的C++实现
· 概述
RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在(美国麻省理工学院)开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
。 它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法,因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册,人们用公钥加密文件发送给个人,个人就可以用私钥解密接受。为提高保密强度,RSA密钥至少为500位长,一般推荐使用1024位。
RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。
RSA的算法涉及三个参数,n、e1、e2。
其中,n是两个大质数p、q的积,n的二进制
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示时所占用的位数,就是所谓的密钥长度。
e1和e2是一对相关的值,e1可以任意取,但要求e1与(p-1)*(q-1)互质;再选择e2,要求(e2*e1)mod((p-1)*(q-1))=1。
(n及e1),(n及e2)就是密钥对。
RSA加解密的算法完全相同,设A为明文,B为密文,则:A=B^e1 mod n;B=A^e2 mod n;
e1和e2可以互换使用,即:
A=B^e2 mod n;B=A^e1 mod n;
· RSA算法的编程思路
1) 确定密钥的宽度。
2) 随机选择两个不同的素数p处q,它们的宽度是密钥宽度的二分之一。
3) 计算出p和q的乘积n 。
4) 在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素,整数e用做加密密钥(其中Φ(n)=(p-1)*(q-1))。
5) 从
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
ed ≡ 1 mod Φ(n)中求出解密密钥d 。
6) 得公钥(e ,n ), 私钥 (d , n) 。
7) 公开公钥,但不公开私钥。
8) 将明文P (假设P是一个小于n的整数)加密为密文C,计算方法为:
C = Pe mod n
9) 将密文C解密为明文P,计算方法为:
P = Cd mod n
然而只根据n和e(不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密
· C++程序实现
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<e; 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<model; )
{
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<number ; i++)
{
if( CountCommonData(number, i)==1 )
ao_la ++;
}
return ao_la;
}
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<ReSize; i++)
cBuf[i]= (char)(uBuf[i]);
WrNum= fwrite( cBuf,1, ReSize, fipWr);
printf("第%d次写入%d字节!\n",record++, WrNum);
}
}while(ReSize == BUFFER_SIZE);
}