RSA非对称加密算法原理（详解和C++代码实现）

RSA非对称加密

选择两个素数p和q ,计算n=p*q和欧拉函数φ(n)=(p-1)(q-1)，选择整数e，使gcd(φ(n), e)=1（即φ(n)和e是互素），1<e<φ(n)
计算e的逆元d=e-1mod φ(n)（即ed = 1 mod φ(n)）
得到公钥Kpub＝{e, n}，私钥Kpri＝{d, n}（公开公钥Kpub ，保密私钥Kpri ）
加密(使用公钥Kpub)：对于明文m<n，密文c=me mod n ;
解密(使用私钥Kpri)：对于密文c，明文m=cd mod n

RSA加解密示例

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0Q9Us3Q7-1652526233397)(C:\Users\admin\AppData\Roaming\Typora\typora-user-images\1652314089801.png)]$

代码实现（c++）

#include <iostream>
using namespace std;

// 最大公因数
int maxCommonDivisor(int a, int b)
{
    int temp = a;
    if (a < b)
    {
        a = b;
        b = temp;
    }

    while(a % b)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return b;
}

// 最小公倍数
int leastCommonMultiple(int a, int b)
{
    int macDivisor = maxCommonDivisor(a, b);
    return a / macDivisor  *  b;
}

// 计算 input ^ rate mod y
int multiMod(int input, int rate, int y)
{
    int start = 1;
    int arr[100];
    arr[0] = 1;
    arr[1] = input;
    int step = 1;
    int result = 1;

    while(rate)
    {
        if (step == 1)
        {
            arr[step] = input;
        }
        else
        {
            arr[step] = arr[step - 1] * arr[step - 1];
            arr[step] %= y;
        }
        if(rate&1)
        {
            result *= arr[step];
            result %= y;
        }
        step ++;
        rate = rate >> 1;
    }

    return result;
}

int main()
{
    int input;
    int p, q;
    int N, L, E, D;

    while(cin >> p >> q >> input >> E)
    {
        N = p * q;
        //最小公倍数
        L = leastCommonMultiple(p - 1, q - 1);
        //E * D mod L = 1
        int X = 1;
        while((X * L + 1) % E)
        {
            X ++;
        }

        D = (X * L + 1) / E;
        cout<<"N = " << N << "  L = " << L << " E = " << E << "  D = " << D << "  X = " << X <<endl;
        // 加密过程
        int code = multiMod(input, E, N);
        // 解密过程
        int deCode = multiMod(code, D, N);
        cout<< "code = " << code << "  deCode = " << deCode << endl;
    }
}