rsa解密函数c++代码

以下是 RSA 解密函数的 C++ 代码示例：

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

// 求两个数的最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

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

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

// 获取一个指定范围内的随机质数
int get_prime(int min, int max) {
    int n;
    do {
        n = rand() % (max - min + 1) + min;
    } while (!is_prime(n));
    return n;
}

// RSA 解密函数
int rsa_decrypt(int ciphertext, int d, int n) {
    int plaintext = 1;
    while (d) {
        if (d & 1) {
            plaintext = (plaintext * ciphertext) % n;
        }
        ciphertext = (ciphertext * ciphertext) % n;
        d >>= 1;
    }
    return plaintext;
}

int main() {
    // 选择两个不同的质数 p 和 q
    int p = get_prime(100, 200);
    int q = get_prime(200, 300);

    // 计算 n 和 φ(n)
    int n = p * q;
    int phi_n = (p - 1) * (q - 1);

    // 选择公钥 e
    int e = 65537;  // 通常选择 65537

    // 计算私钥 d
    int x, y;
    int d = exgcd(e, phi_n, x, y);
    d = (x + phi_n) % phi_n;

    // 显示密钥对
    cout << "公钥：(" << e << ", " << n << ")" << endl;
    cout << "私钥：(" << d << ", " << n << ")" << endl;

    // 加密
    int plaintext = 12345;
    int ciphertext = rsa_decrypt(plaintext, e, n);
    cout << "明文：" << plaintext << endl;
    cout << "密文：" << ciphertext << endl;

    // 解密
    plaintext = rsa_decrypt(ciphertext, d, n);
    cout << "解密后的明文：" << plaintext << endl;

    return 0;
}

在上面的代码中，首先通过 `get_prime()` 函数获取两个不同的质数 `p` 和 `q`，然后计算出 `n` 和 `φ(n)`，选择公钥 `e`，并计算私钥 `d`。接下来使用 `rsa_decrypt()` 函数对明文进行加密和解密。其中，加密时使用公钥 `e`，解密时使用私钥 `d`。