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

目录

一.加密原理

此步骤讲解建立在了解欧拉函数等数学基础和密码学基础上的。
步骤 举例1.找出质数 **P、Q *设P=1 Q=112.计算公共模数 N=P*QN=P*Q=311=333.欧拉函数 *F(N)=(P-1)(Q-1)**F(33)=F(3)F(11)=(3-1)(11-1)=204.计算公钥E 1<E<F(N),E与FN互质E可取3.7.9.11.13.17.19 假设E=35.计算私钥D E*D%F(N)=13*D%20=1 故D取76.公钥加密 C=modN假设M=2 C=87.私钥解密 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看这里

不过我相信，聪明的你，看完了一定能自己写出来的对吧？看什么看，还不点赞！