RSA算法c++代码

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，用于数据加密和数字签名。以下是RSA算法的一个简单C++代码示例，它包含了密钥生成、加密和解密的基本步骤。请注意，这只是一个基础版本，实际应用中需要更完善的错误处理和安全性考虑：

#include <iostream>
#include <string>

// 导入模数和欧拉函数计算
long long modpow(long long base, long long exp, long long modulus) {
    if (exp == 0)
        return 1;
    else if (exp % 2 == 0)
        return modpow(base * base % modulus, exp / 2, modulus);
    else
        return base * modpow(base, exp - 1, modulus) % modulus;
}

// 计算欧拉函数phi(n)
long long phi(long long n) {
    long long result = n;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

// RSA密钥生成
void generateKeys(int p, int q) {
    // p*q是模数n
    long long n = p * q;
    
    // 欧拉函数phi(n)
    long long phi_n = phi(n);
    
    // 选择e，满足gcd(e,phi(n))=1
    int e = 65537;
    long long gcd = __gcd(e, phi_n);
    while (gcd != 1) {
        e++;
        gcd = __gcd(e, phi_n);
    }
    
    // 计算d，d是e关于模phi(n)的逆元
    long long d = modinv(e, phi_n);

    std::cout << "Public Key (e, n): (" << e << ", " << n << ")\n";
    std::cout << "Private Key (d, n): (" << d << ", " << n << ")\n";
}

// 明文加密
std::string encrypt(std::string message, int e, long long n) {
    std::string encrypted = "";
    for (char c : message) {
        encrypted += static_cast<char>((static_cast<int>(c) + e) % n);
    }
    return encrypted;
}

// 明文解密
std::string decrypt(std::string cipher, int d, long long n) {
    std::string decrypted = "";
    for (char c : cipher) {
        decrypted += static_cast<char>((static_cast<int>(c) - d) % n);
    }
    return decrypted;
}

int main() {
    int p = 61, q = 53; // 这里只是示例，实际使用时应从足够大的素数开始
    generateKeys(p, q);
    std::string plaintext = "Hello, RSA!";
    std::string ciphertext = encrypt(plaintext, 5, p * q);
    std::cout << "Ciphertext: " << ciphertext << "\n";
    std::string decryptedtext = decrypt(ciphertext, 13, p * q); // 使用私钥d解密
    std::cout << "Decrypted text: " << decryptedtext << "\n";

    return 0;
}