RSA算法C/C++实现

这里提供一个简单的RSA算法的C/C++实现。

算法流程：

1.选择两个大质数p和q，计算n=p*q。

2.计算欧拉函数φ(n)=(p-1)*(q-1)。

3.选择一个整数e，1< e <φ(n)，且e与φ(n)互质。

4.计算d，使得d*e≡1(mod φ(n))。

5.公钥为(n,e)，私钥为(n,d)。

6.加密：C=M^e(mod n)。

7.解密：M=C^d(mod n)。

代码实现：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

//计算最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

//判断是否为质数
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;
}

//生成大质数
int generatePrime(int min, int max)
{
    int prime;
    do
    {
        prime = rand() % (max - min + 1) + min;
    }while(!isPrime(prime));
    return prime;
}

//计算模幂
int modPower(int a, int b, int m)
{
    int res = 1;
    while(b > 0)
    {
        if(b & 1)
            res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

//生成公私钥对
void generateKey(int &n, int &e, int &d)
{
    int p, q, phi_n;
    do
    {
        p = generatePrime(100, 1000);
        q = generatePrime(100, 1000);
        n = p * q;
        phi_n = (p - 1) * (q - 1);
    }while(gcd(phi_n, 65537) != 1); //65537为常用值
    e = 65537;
    d = 0;
    while((d*e) % phi_n != 1)
        d++;
}

//加密
void encrypt(int n, int e, char *msg, int *cipher)
{
    int len = strlen(msg);
    for(int i=0; i<len; i++)
    {
        cipher[i] = modPower(msg[i], e, n);
    }
}

//解密
void decrypt(int n, int d, int *cipher, char *msg)
{
    int len = strlen(msg);
    for(int i=0; i<len; i++)
    {
        msg[i] = modPower(cipher[i], d, n);
    }
}

int main()
{
    int n, e, d;
    generateKey(n, e, d);
    cout << "公钥：" << "(" << n << "," << e << ")" << endl;
    cout << "私钥：" << "(" << n << "," << d << ")" << endl;

    char msg[100];
    cout << "请输入要加密的明文：";
    cin.getline(msg, 100);
    int cipher[100];
    encrypt(n, e, msg, cipher);
    cout << "密文：";
    for(int i=0; i<strlen(msg); i++)
    {
        cout << cipher[i] << " ";
    }
    cout << endl;

    char dec[100];
    decrypt(n, d, cipher, dec);
    cout << "解密后的明文：" << dec << endl;

    return 0;
}

这个实现中使用了随机生成质数的方法，生成的质数范围在100到1000之间。公钥中的e取65537，私钥中的d通过枚举计算得到。加密和解密过程中使用了模幂运算。整个程序可以编译运行，输入要加密的明文，即可得到加密后的密文和解密后的明文。