C++实现RSA加密解密算法详解：代码与原理分析

本教程将带您深入理解RSA加密解密算法的实现原理，并提供C++代码示例。文章分为两部分，第一部分展示RSA加密解密的C++代码，第二部分将逐行解析代码，并结合原理进行详细说明。

一、RSA加密解密的C++代码实现

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

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long fast_pow(long long a, long long b, long long mod) {
    long long ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

long long ext_euclid(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = ext_euclid(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

bool is_prime(long long n) {
    if (n <= 1) {
        return false;
    }
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

long long get_prime(long long x) {
    while (true) {
        if (is_prime(x)) {
            return x;
        }
        ++x;
    }
}

void generate_key(long long &p, long long &q, long long &n, long long &e, long long &d) {
    p = get_prime(1000);
    q = get_prime(10000);
    n = p * q;
    long long phi = (p - 1) * (q - 1);
    e = 65537;
    long long x, y;
    ext_euclid(e, phi, x, y);
    d = (x % phi + phi) % phi;
}

long long encrypt(long long m, long long e, long long n) {
    return fast_pow(m, e, n);
}

long long decrypt(long long c, long long d, long long n) {
    return fast_pow(c, d, n);
}

int main() {
    long long p, q, n, e, d;
    generate_key(p, q, n, e, d);
    cout << "p = " << p << endl;
    cout << "q = " << q << endl;
    cout << "n = " << n << endl;
    cout << "e = " << e << endl;
    cout << "d = " << d << endl;
    cout << "Please input the number you want to encrypt: ";
    long long m;
    cin >> m;
    long long c = encrypt(m, e, n);
    cout << "The encrypted number is: " << c << endl;
    cout << "Do you want to decrypt it? (y/n) ";
    char choice;
    cin >> choice;
    if (choice == 'y' || choice == 'Y') {
        long long decrypted = decrypt(c, d, n);
        cout << "The decrypted number is: " << decrypted << endl;
    }
    return 0;
}

这段代码实现了RSA加密和解密的过程。其中主要包括以下几个函数：

gcd(long long a, long long b)：求两个整数a和b的最大公约数。
fast_pow(long long a, long long b, long long mod)：求a的b次方对mod取模的结果。
ext_euclid(long long a, long long b, long long &x, long long &y)：求ax + by = gcd(a, b)的一组解(x, y)。
is_prime(long long n)：判断一个数是否为素数。
get_prime(long long x)：获取大于等于x的最小素数。
generate_key(long long &p, long long &q, long long &n, long long &e, long long &d)：生成RSA的公钥和私钥。
encrypt(long long m, long long e, long long n)：RSA加密过程。
decrypt(long long c, long long d, long long n)：RSA解密过程。

在主函数中，首先调用generate_key函数生成公钥和私钥，然后让用户输入需要加密的数字m，将其加密为c，并输出加密后的结果。接着询问用户是否需要解密，如果需要解密，则将加密后的结果c解密为decrypted，并输出解密后的结果。

这段代码实现了RSA加密和解密的过程，但其中很多细节需要解释。下一篇文章将对每行代码进行详细解释。