目录
一.加密原理
二.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
完整代码
一.加密原理
此步骤讲解建立在了解欧拉函数等数学基础和密码学基础上的。
| 步骤 | 举例 |
| 1.找出质数 P、Q | 设P=1 Q=11 |
| 2.计算公共模数 N=P*Q | N=P*Q=3*11=33 |
| 3.欧拉函数 F(N)=(P-1)*(Q-1) | F(33)=F(3)*F(11)=(3-1)*(11-1)=20 |
| 4.计算公钥E 1<E<F(N),E与FN互质 | E可取3.7.9.11.13.17.19 假设E=3 |
| 5.计算私钥D E*D%F(N)=1 | 3*D%20=1 故D取7 |
| 6.公钥加密 C=modN | 假设M=2 C=8 |
| 7.私钥解密 M=modN | 故解得M=2 |
二.C++实现
实现步骤：首先实现加解密算法、接着实现pqed的生成
其中包括：扩展欧几里得算法、加密函数、解密函数、质数的判定函数、互质的判断等独立函数
3.1实现加解密算法
用最基本思路来做加解密很简单，即为上述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;
}
2.2实现pqed的生成
对于pqed的生成我的实现思路是根据RSA加密原理的步骤一步步往下撸。
2.2.1找出质数P、Q
我使用的是p、q由用户输入，因此仅需要判定p、q是否为素数
示例：
bool IsPrime(int n){
if(n <= 1)
return false;
for(int i=2;i<sqrt(n);i++){
if((n%i) == 0)
return false;
}
return true;
}
2.2.2计算公共模数N=P*Q
这不用说了吧
2.2.3欧拉函数F(N)=(P-1)*(Q-1)
这也不用说了吧
2.2.4计算公钥E
分为随机数的生成与互质的判定。
随机数生成：rand随机生成的数的取值范围为[0,x)，故x取fn-2，最终结果再加2，e的取值范围为[2,fn)中的整数。
srand((int)time(0));
e = rand()%(fn-2)+2;
互质的判定：辗转相除法求解最大公约数，当余数为0，除数为1时，两数互质。通俗点就是，这俩数的最大公约数为1，那可不就是互质嘛。
//互质的判断
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;
}
2.2.5 计算私钥D
在敲代码的时候，看了很多的讲关于扩展欧几里得算法的文章，通俗易懂的很少，推荐这一篇：扩展欧几里德算法详解_zhj5chengfeng的博客-CSDN博客_扩展欧几里得算法
我们用的是对乘法逆元的计算：
可以表示为：
再对比上述文章中的：
很熟悉了是不是，我们直接套用就ok了。
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;
}完整代码
完整cpp看这里文章来源：https://www.toymoban.com/news/detail-415448.html
不过我相信，聪明的你，看完了一定能自己写出来的对吧？看什么看，还不点赞！文章来源地址https://www.toymoban.com/news/detail-415448.html
到了这里，关于RSA加密算法讲解及C++实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
