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,用反复平方法求数的幂
二、程序流程图
三、程序源码
#include <iostream>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std; int Plaintext[];//明文
long long Ciphertext[];//密文
int n, e = , d; //二进制转换
int BianaryTransform(int num, int bin_num[])
{ int i = , mod = ; //转换为二进制,逆向暂存temp[]数组中
while(num != )
{
mod = num%;
bin_num[i] = mod;
num = num/;
i++;
} //返回二进制数的位数
return i;
} //反复平方求幂
long long Modular_Exonentiation(long long a, int b, int n)
{
int c = , bin_num[];
long long d = ;
int k = BianaryTransform(b, bin_num)-; for(int i = k; i >= ; i--)
{
c = *c;
d = (d*d)%n;
if(bin_num[i] == )
{
c = c + ;
d = (d*a)%n;
}
}
return d;
} //生成1000以内素数
int ProducePrimeNumber(int prime[])
{
int c = , vis[];
memset(vis, , sizeof(vis));
for(int i = ; i <= ; i++)if(!vis[i])
{
prime[c++] = i;
for(int j = i*i; j <= ; j+=i)
vis[j] = ;
} return c;
} //欧几里得扩展算法
int Exgcd(int m,int n,int &x)
{
int x1,y1,x0,y0, y;
x0=; y0=;
x1=; y1=;
x=; y=;
int r=m%n;
int q=(m-r)/n;
while(r)
{
x=x0-q*x1; y=y0-q*y1;
x0=x1; y0=y1;
x1=x; y1=y;
m=n; n=r; r=m%n;
q=(m-r)/n;
}
return n;
} //RSA初始化
void RSA_Initialize()
{
//取出1000内素数保存在prime[]数组中
int prime[];
int count_Prime = ProducePrimeNumber(prime); //随机取两个素数p,q
srand((unsigned)time(NULL));
int ranNum1 = rand()%count_Prime;
int ranNum2 = rand()%count_Prime;
int p = prime[ranNum1], q = prime[ranNum2]; n = p*q; int On = (p-)*(q-); //用欧几里德扩展算法求e,d
for(int j = ; j < On; j+=)
{
int gcd = Exgcd(j, On, d);
if( gcd == && d > )
{
e = j;
break;
} } } //RSA加密
void RSA_Encrypt()
{
cout<<"Public Key (e, n) : e = "<<e<<" n = "<<n<<'\n';
cout<<"Private Key (d, n) : d = "<<d<<" n = "<<n<<'\n'<<'\n'; int i = ;
for(i = ; i < ; i++)
Ciphertext[i] = Modular_Exonentiation(Plaintext[i], e, n); cout<<"Use the public key (e, n) to encrypt:"<<'\n';
for(i = ; i < ; i++)
cout<<Ciphertext[i]<<" ";
cout<<'\n'<<'\n';
} //RSA解密
void RSA_Decrypt()
{
int i = ;
for(i = ; i < ; i++)
Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], d, n); cout<<"Use private key (d, n) to decrypt:"<<'\n';
for(i = ; i < ; i++)
cout<<Ciphertext[i]<<" ";
cout<<'\n'<<'\n';
} //算法初始化
void Initialize()
{
int i;
srand((unsigned)time(NULL));
for(i = ; i < ; i++)
Plaintext[i] = rand()%; cout<<"Generate 100 random numbers:"<<'\n';
for(i = ; i < ; i++)
cout<<Plaintext[i]<<" ";
cout<<'\n'<<'\n';
} int main()
{
Initialize(); while(!e)
RSA_Initialize(); RSA_Encrypt(); RSA_Decrypt(); return ;
}四、运行结果