RSA加密算法讲解及C++实现

一.加密原理             

二.C++实现

3.1实现加解密算法

加解密算法示例：

2.2实现pqed的生成

2.2.1找出质数P、Q 

2.2.2计算公共模数N=P*Q

 2.2.3欧拉函数F(N)=(P-1)*(Q-1)

 2.2.4计算公钥E

2.2.5 计算私钥D

完整代码

此步骤讲解建立在了解欧拉函数等数学基础和密码学基础上的。

实现步骤：首先实现加解密算法、接着实现pqed的生成

其中包括：扩展欧几里得算法、加密函数、解密函数、质数的判定函数、互质的判断等独立函数

用最基本思路来做加解密很简单，即为上述6、7步的实现。

void RSAEnc(int& num,int e,int n){
	unsigned long temp = (unsigned long)pow(num,e) % n;
	num = (int)temp;
}

但是很遗憾的是，稍微大一点的数字，都会出现溢出问题。

因此，为防止空间时间复杂性过大，在此我们采用二分快速幂算法，用于加快幂次取模速度。

参考博文：快速幂算法（全网最详细地带你从零开始一步一步优化）_刘扬俊的博客-CSDN博客_快速幂算法

什么？没看懂？什么？太长了看不下去？行吧行吧，我们来总结下：

首先，最重要的是了解取模运算运算法则【原理感兴趣的可以自行百度】：

接着根据这个法则，我们可以根据RSA算法要求推出（E个(M%N)）：

明白这一点我们就可以，使用取模算法优化我们的代码了，如果使用的指数不太大的完全够用。

但是如果幂数很大的情况，还是可能出现溢出问题的。

void RSAEnc(int& num,int e,int n){
//取模运算的运算法则
	int temp = 1;
	for(int i=1;i<=e;i++){
		temp = temp * (num % n);
	}
	num = temp % n;
}

因此我们使用能算出指数非常大的快速幂算法，它通过减小指数的大小，使我们的循环次数大大减小了。

【二次快速幂过程主要看上述博文的动画演示，这个动画比较通俗易懂】

但实际上，最重要思想还的就是咱们上述的取模运算运算法则和指数分半，底数平方。

最终优化后即为：

void RSAEnc(int& num,int e,int n){
//取模运算的运算法则
	int temp = 1;
	while(e > 0){
		if(e & 1){
			temp = temp*num%n;
		}
		e >>= 1;
		num = num*num%n;
	}
	num = temp;
}

对于pqed的生成我的实现思路是根据RSA加密原理的步骤一步步往下撸。

我使用的是p、q由用户输入，因此仅需要判定p、q是否为素数

示例：

bool IsPrime(int n){
	if(n <= 1)
		return false;
	for(int i=2;i

		srand((int)time(0));
		e = rand()%(fn-2)+2;

//互质的判断
bool IsCOPrime(int x,int y){
	int z;
	while(x%y !=0){
		z = x%y;
		x = y;
		y = z;
	}
	if(z == 1)
		return true;
	return false;
}

int e_gcd(int a,int b,int&x,int&y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int  ans = e_gcd(b,a%b,x,y);
	int temp = x;
	x = y;
	y = temp-a/b*y;
	return ans;
}
//生成私钥d=cal(e,fn);
int cal(int a,int m){
	int x,y;
	int gcd = e_gcd(a,m,x,y);
    if(1%gcd !=0) return -1;
	x *= 1/gcd;
	m = abs(m);
	int ans = x%m;
	if(ans <= 0) ans +=m;
	return  ans;
}