RSA加密算法c++简单实现

RSA是一种非对称加密算法，在公开密钥和电子商业中RSA被广泛使用。它是基于一个很简单的数论事实，两个素数相乘很容易，对两素数乘积因式分解很困难。原理就不再阐述了，我谈谈算法的编程实现过程。

一、RSA加密和解密过程是基于以下形式，其中明文为M，密文为C，公匙PU={e, n}，密匙PR={d, n}。

1、准备工作，选择两个大素数p和q，计算p和q的乘积n，计算p-1和q-1的乘积，选择一个与p-1和q-1乘积互质的数e，计算出d

2、加密过程

3、解密过程

程序没有生成大素数，只是列出1000以内的素数，随机取两个素数p和q，利用欧德里德扩展算法计算出e和d，用反复平方法求数的幂

二、程序流程图

          

三、程序源码

  1 #include <iostream>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <ctime>
  5 #include <cstdlib>
  6 using namespace std;
  7 
  8 
  9 int Plaintext[100];//明文
 10 long long Ciphertext[100];//密文
 11 int n, e = 0, d;
 12 
 13 //二进制转换
 14 int BianaryTransform(int num, int bin_num[])
 15 {
 16 
 17     int i = 0,  mod = 0;
 18 
 19     //转换为二进制，逆向暂存temp[]数组中
 20     while(num != 0)
 21     {
 22         mod = num%2;
 23         bin_num[i] = mod;
 24         num = num/2;
 25         i++;
 26     }
 27 
 28     //返回二进制数的位数
 29     return i;
 30 }
 31 
 32 //反复平方求幂
 33 long long Modular_Exonentiation(long long a, int b, int n)
 34 {
 35     int c = 0, bin_num[1000];
 36     long long d = 1;
 37     int k = BianaryTransform(b, bin_num)-1;
 38 
 39     for(int i = k; i >= 0; i--)
 40     {
 41         c = 2*c;
 42         d = (d*d)%n;
 43         if(bin_num[i] == 1)
 44         {
 45             c = c + 1;
 46             d = (d*a)%n;
 47         }
 48     }
 49     return d;
 50 }
 51 
 52 //生成1000以内素数
 53 int ProducePrimeNumber(int prime[])
 54 {
 55     int c = 0, vis[1001];
 56     memset(vis, 0, sizeof(vis));
 57     for(int i = 2; i <= 1000; i++)if(!vis[i])
 58     {
 59         prime[c++] = i;
 60         for(int j = i*i; j <= 1000; j+=i)
 61             vis[j] = 1;
 62     }
 63 
 64     return c;
 65 }
 66 
 67 
 68 //欧几里得扩展算法
 69 int Exgcd(int m,int n,int &x)
 70 {
 71     int x1,y1,x0,y0, y;
 72     x0=1; y0=0;
 73     x1=0; y1=1;
 74     x=0; y=1;
 75     int r=m%n;
 76     int q=(m-r)/n;
 77     while(r)
 78     {
 79         x=x0-q*x1; y=y0-q*y1;
 80         x0=x1; y0=y1;
 81         x1=x; y1=y;
 82         m=n; n=r; r=m%n;
 83         q=(m-r)/n;
 84     }
 85     return n;
 86 }
 87 
 88 //RSA初始化
 89 void RSA_Initialize()
 90 {
 91     //取出1000内素数保存在prime[]数组中
 92     int prime[5000];
 93     int count_Prime = ProducePrimeNumber(prime);
 94 
 95     //随机取两个素数p,q
 96     srand((unsigned)time(NULL));
 97     int ranNum1 = rand()%count_Prime;
 98     int ranNum2 = rand()%count_Prime;
 99     int p = prime[ranNum1], q = prime[ranNum2];
100 
101     n = p*q;
102 
103     int On = (p-1)*(q-1);
104 
105 
106     //用欧几里德扩展算法求e,d
107     for(int j = 3; j < On; j+=1331)
108     {
109         int gcd = Exgcd(j, On, d);
110         if( gcd == 1 && d > 0)
111         {
112             e = j;
113             break;
114         }
115 
116     }
117 
118 }
119 
120 //RSA加密
121 void RSA_Encrypt()
122 {
123     cout<<"Public Key (e, n) : e = "<<e<<" n = "<<n<<'\n';
124     cout<<"Private Key (d, n) : d = "<<d<<" n = "<<n<<'\n'<<'\n';
125 
126     int i = 0;
127     for(i = 0; i < 100; i++)
128         Ciphertext[i] = Modular_Exonentiation(Plaintext[i], e, n);
129 
130     cout<<"Use the public key (e, n) to encrypt:"<<'\n';
131     for(i = 0; i < 100; i++)
132         cout<<Ciphertext[i]<<" ";
133     cout<<'\n'<<'\n';
134 }
135 
136 //RSA解密
137 void RSA_Decrypt()
138 {
139     int i = 0;
140     for(i = 0; i < 100; i++)
141         Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], d, n);
142 
143     cout<<"Use private key (d, n) to decrypt:"<<'\n';
144     for(i = 0; i < 100; i++)
145         cout<<Ciphertext[i]<<" ";
146     cout<<'\n'<<'\n';
147 }
148 
149 
150 //算法初始化
151 void Initialize()
152 {
153     int i;
154     srand((unsigned)time(NULL));
155     for(i = 0; i < 100; i++)
156         Plaintext[i] = rand()%1000;
157 
158     cout<<"Generate 100 random numbers:"<<'\n';
159     for(i = 0; i < 100; i++)
160         cout<<Plaintext[i]<<" ";
161     cout<<'\n'<<'\n';
162 }
163 
164 int main()
165 {
166     Initialize();
167 
168     while(!e)
169         RSA_Initialize();
170 
171     RSA_Encrypt();
172 
173     RSA_Decrypt();
174 
175     return 0;
176 }

 

 

四、运行结果

 

 

分类: Cryptology

评论

3 楼 腾讯rep 2015-08-12  

lowser

2 楼 doloveme 2014-04-01  

RSA算法的C++实现
?  概述
RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。 它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。
RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。

　　RSA的算法涉及三个参数，n、e1、e2。

　　其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。

　　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) 从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。
    6) 得公钥（e ，n ）, 私钥 (d , n) 。
    7) 公开公钥，但不公开私钥。
    将明文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&lte; 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&ltmodel; )
 {
  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&ltnumber ; 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&lt3; 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&ltReSize; i++)
    cBuf[i]= (char)(uBuf[i]);
   WrNum= fwrite( cBuf,1, ReSize, fipWr);   
   printf("第%d次写入%d字节!\n",record++, WrNum);
  }

 }while(ReSize == BUFFER_SIZE);
}

1 楼 doloveme 2014-04-01  

//RSA public decrypt
void RSA_PublicDecrypt()
{
    cout<<"Public Key (e, n) : e = "<<e<<" n = "<<n<<'\n';
    cout<<"Private Key (d, n) : d = "<<d<<" n = "<<n<<'\n'<<'\n';

    int i = 0;
    for(i = 0; i < 100; i++)
        Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], e, n);

    cout<<"Use the public key (e, n) to encrypt:"<<'\n';
    for(i = 0; i < 100; i++)
        cout<<Ciphertext[i]<<" ";
    cout<<'\n'<<'\n';
}

//RSA private encrypt
void RSA_PrivateEncrypt()
{
    int i = 0;
    for(i = 0; i < 100; i++)
        Ciphertext[i] = Modular_Exonentiation(Plaintext[i], d, n);

    cout<<"Use private key (d, n) to decrypt:"<<'\n';
    for(i = 0; i < 100; i++)
        cout<<Ciphertext[i]<<" ";
    cout<<'\n'<<'\n';
}