rsa-3072 算法C++

以下 C++ 中使用 RSA-3072 算法进行加密和解密的示例代码：

#include <iostream>
#include <string>
#include <random>
#include <ctime>
#include <cmath>
#include <bitset>
#include <sstream>

using namespace std;

const int RSA_KEY_SIZE = 3072; // RSA 密钥位数

class RSA
{
public:
    RSA()
    {
        // 生成 RSA 密钥对
        generateRSAKeys();
    }

    // 加密函数
    string encrypt(string plaintext)
    {
        // 将明文转换为整数
        int m = stringToInteger(plaintext);

        // 计算密文
        int c = powerMod(m, e, n);

        // 将密文转换为字符串
        return integerToString(c);
    }

    // 解密函数
    string decrypt(string ciphertext)
    {
        // 将密文转换为整数
        int c = stringToInteger(ciphertext);

        // 计算明文
        int m = powerMod(c, d, n);

        // 将明文转换为字符串
        return integerToString(m);
    }

private:
    int n; // RSA 模数
    int e; // RSA 公钥指数
    int d; // RSA 私钥指数

    // 生成 RSA 密钥对
    void generateRSAKeys()
    {
        // 生成两个大素数 p 和 q
        int p = generateLargePrime();
        int q = generateLargePrime();

        // 计算 RSA 模数 n = p * q
        n = p * q;

        // 计算欧拉函数 φ(n) = (p-1)*(q-1)
        int phi_n = (p - 1) * (q - 1);

        // 选择 RSA 公钥指数 e，要求 1 < e < φ(n) 且 e 和 φ(n) 互质
        e = generateCoPrime(phi_n);

        // 计算 RSA 私钥指数 d，要求 d * e ≡ 1 (mod φ(n))
        d = findModularInverse(e, phi_n);
    }

    // 生成一个大素数
    int generateLargePrime()
    {
        // 设置随机数生成器的种子为当前时间
        mt19937 rng(time(nullptr));

        // 生成一个大于 2^(RSA_KEY_SIZE-1) 的奇数
        uniform_int_distribution<int> dist(pow(2, RSA_KEY_SIZE - 1) + 1, pow(2, RSA_KEY_SIZE) - 1);
        int n = dist(rng);

        while (!isPrime(n))
        {
            // 如果不是素数，则继续生成下一个奇数
            n += 2;
        }

        return n;
    }

    // 判断一个数是否为素数
    bool isPrime(int n)
    {
        if (n == 2 || n == 3)
        {
            return true;
        }

        if (n == 1 || n % 2 == 0)
        {
            return false;
        }

        int s = 0;
        int d = n - 1;

        while (d % 2 == 0)
        {
            s++;
            d /= 2;
        }

        for (int i = 0; i < 128; i++)
        {
            int a = rand() % (n - 3) + 2;
            int x = powerMod(a, d, n);

            if (x == 1 || x == n - 1)
            {
                continue;
            }

            for (int j = 0; j < s - 1; j++)
            {
                x = (x * x) % n;

                if (x == 1)
                {
                    return false;
                }

                if (x == n - 1)
                {
                    break;
                }
            }

            if (x != n - 1)
            {
                return false;
            }
        }

        return true;
    }

    // 生成一个与 φ(n) 互质的数
    int generateCoPrime(int phi_n)
    {
        // 设置随机数生成器的种子为当前时间
        mt19937 rng(time(nullptr));

        int e;

        do
        {
            // 生成一个范围在 [2, φ(n)-1] 之间的整数
            uniform_int_distribution<int> dist(2, phi_n - 1);
            e = dist(rng);
        } while (gcd(e, phi_n) != 1);

        return e;
    }

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

        return gcd(b, a % b);
    }

    // 计算 a 的 b 次方对 m 取模的结果
    int powerMod(int a, int b, int m)
    {
        int result = 1;

        while (b > 0)
        {
            if (b % 2 == 1)
            {
                result = (result * a) % m;
            }

            a = (a * a) % m;
            b /= 2;
        }

        return result;
    }

    // 计算 a 在模 n 意义下的乘法逆元
    int findModularInverse(int a, int n)
    {
        int t = 0, new_t = 1;
        int r = n, new_r = a;

        while (new_r != 0)
        {
            int quotient = r / new_r;

            int temp_t = t;
            t = new_t;
            new_t = temp_t - quotient * new_t;

            int temp_r = r;
            r = new_r;
            new_r = temp_r - quotient * new_r;
        }

        if (r > 1)
        {
            throw runtime_error("a is not invertible");
        }

        if (t < 0)
        {
            t += n;
        }

        return t;
    }

    // 将字符串转换为整数
    int stringToInteger(const string& s)
    {
        int result = 0;

        for (char c : s)
        {
            result = result * 256 + static_cast<unsigned char>(c);
        }

        return result;
    }

    // 将整数转换为字符串
    string integerToString(int n)
    {
        stringstream ss;

        while (n > 0)
        {
            ss.put(n % 256);
            n /= 256;
        }

        string result = ss.str();
        reverse(result.begin(), result.end());

        return result;
    }
};

int main()
{
    RSA rsa;

    string plaintext = "Hello, RSA!";
    string ciphertext = rsa.encrypt(plaintext);
    string decryptedtext = rsa.decrypt(ciphertext);

    cout << "明文：" << plaintext << endl;
    cout << "密文：" << ciphertext << endl;
    cout << "解密后的明文：" << decryptedtext << endl;

    return 0;
}

注意：RSA-3072 是一个非常大的密钥，运行此代码可能需要较长时间。如果需要更快的运行速度，可以将 RSA_KEY_SIZE 设置为较小的值，例如 1024 或 2048。