rsa加密算法代码c++

以下是C++实现的RSA加密算法代码，其中包括了公钥加密和私钥解密的过程：

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <algorithm>

using namespace std;

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

//计算扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

//判断是否为质数
bool isprime(int n)
{
    if(n == 2 || n == 3) return true;
    if(n == 1 || n % 2 == 0) return false;
    for(int i = 3; i <= sqrt(n); i += 2)
        if(n % i == 0)
            return false;
    return true;
}

//产生一个大素数
int generate_prime()
{
    int prime = rand() % 100 + 100;
    while(!isprime(prime))
        prime = rand() % 100 + 100;
    return prime;
}

//产生RSA公钥和私钥
void generate_key(int &e, int &d, int &n)
{
    srand((unsigned)time(NULL)); //设置随机数种子
    int p = generate_prime(); //产生一个大素数p
    int q = generate_prime(); //产生一个大素数q
    n = p * q; //计算n
    int phi = (p - 1) * (q - 1); //计算phi(n)
    e = rand() % (phi - 2) + 2; //随机选择e，1 < e < phi(n)，且e与phi(n)互质
    while(gcd(e, phi) != 1)
        e = rand() % (phi - 2) + 2;
    exgcd(e, phi, d, d); //计算d，使得ed ≡ 1 (mod phi(n))
    d = (d % phi + phi) % phi; //保证d是正整数
}

//将字符串转换为整数
unsigned int str2int(string str)
{
    unsigned int num = 0;
    stringstream stream(str);
    stream >> num;
    return num;
}

//将整数转换为字符串
string int2str(unsigned int num)
{
    stringstream stream;
    stream << num;
    return stream.str();
}

//加密
string encrypt(string plain, int e, int n)
{
    string cipher = "";
    for(int i = 0; i < plain.length(); i++)
    {
        unsigned int m = (unsigned int)plain[i]; //将明文的每个字符转换为整数
        unsigned int c = 1;
        for(int j = 0; j < e; j++) //使用快速幂算法计算c ≡ m^e (mod n)
            c = (c * m) % n;
        cipher += int2str(c) + " "; //将加密后的整数转换为字符串，并用空格隔开
    }
    return cipher;
}

//解密
string decrypt(string cipher, int d, int n)
{
    string plain = "";
    stringstream stream(cipher);
    string str;
    while(stream >> str) //将密文中的每个整数分别解密
    {
        unsigned int c = str2int(str);
        unsigned int m = 1;
        for(int i = 0; i < d; i++) //使用快速幂算法计算m ≡ c^d (mod n)
            m = (m * c) % n;
        plain += (char)m; //将解密后的整数转换为字符
    }
    return plain;
}

int main()
{
    int e, d, n;
    generate_key(e, d, n); //生成RSA公钥和私钥

    string plain = "Hello, RSA!"; //设置明文
    cout << "Plain text: " << plain << endl;

    string cipher = encrypt(plain, e, n); //加密
    cout << "Cipher text: " << cipher << endl;

    string dec_plain = decrypt(cipher, d, n); //解密
    cout << "Decrypted plain text: " << dec_plain << endl;

    return 0;
}

在实现加密和解密的过程中，我们采用了快速幂算法来计算幂取模运算，以提高加密和解密的效率。