1. 项目概述:为什么要在C++里手搓RSA?

如果你正在用C++处理一些敏感数据,比如用户密码、配置文件或者网络通信中的关键信息,那么“加密”这个词对你来说一定不陌生。对称加密(比如AES)很快,但有个老生常谈的问题:密钥怎么安全地交给对方?非对称加密,尤其是RSA,就是为了解决这个“信任传递”问题而生的。它用一对密钥(公钥和私钥),公钥可以大大方方地发给任何人用来加密,但只有持有私钥的你才能解开。这个特性让它在数字签名、密钥交换、HTTPS握手等场景里无处不在。

网上关于RSA原理的文章很多,但很多要么是纯数学推导,看得人头大;要么是直接调用 openssl 库,一行代码搞定,但内部发生了什么你一无所知。这次,我们不依赖任何第三方加密库,就只用C++标准库,从零开始实现一个完整的RSA加密解密流程。这不仅仅是“造轮子”,而是一次深入理解非对称加密核心机制的绝佳机会。你会亲手处理大素数生成、模幂运算、扩展欧几里得算法这些底层细节。对于C++开发者,尤其是对密码学、网络安全或系统底层感兴趣的朋友来说,这个过程能极大地加深你对算法、数论以及C++处理大整数运算的理解。

2. 核心原理与数学基础拆解

在动手写代码之前,我们必须把RSA背后的数学原理吃透。别怕,我们不用深究所有数论证明,但必须理解几个关键概念和它们是如何串联起来的。

2.1 RSA算法的三大数学支柱

RSA的安全性建立在“大数分解难题”上。简单说,给你一个很大的数(比如几百位),它是两个大素数的乘积,让你找出这两个素数来,以目前计算机的计算能力,在有限时间内几乎不可能完成。基于这个难题,RSA设计了三个核心步骤:

  1. 密钥生成 :核心是找到三个特殊的数字 (n, e, d)
  2. 加密过程 :对于明文 m (需要是小于 n 的整数),计算密文 c = m^e mod n
  3. 解密过程 :对于密文 c ,计算明文 m = c^d mod n

这里 (n, e) 就是公钥,可以公开; (n, d) 就是私钥,必须严格保密。 mod n 表示模 n 运算,即求余数。

2.2 密钥生成:一步步推导

这是最核心也最需要理解的一步。我们假设要生成一个1024位的RSA密钥对。

第一步:选择两个大素数 p q 这是安全性的基石。 p q 必须足够大(比如各512位)、随机且独立。在实际中,我们通过“素性检测”算法(如Miller-Rabin概率检测法)来寻找它们。 p q 的乘积 n = p * q 就是模数,它的长度(比如1024位)通常被称为RSA的密钥长度。

第二步:计算欧拉函数 φ(n) 对于两个素数 p q ,它们的欧拉函数值有一个非常简单的计算公式: φ(n) = (p-1) * (q-1) 。这个 φ(n) 表示了在 1 n-1 之间,与 n 互质的整数个数。它是一个关键的中间量,必须保密,因为知道它就能轻松破解私钥。

第三步:选择公钥指数 e e 是一个整数,需要满足两个条件: 1 < e < φ(n) ,且 e φ(n) 互质(即最大公约数 gcd(e, φ(n)) = 1 )。通常,为了计算效率,我们会选择一个固定的小素数,最常用的是 65537 (0x10001)。选择它有几个好处:它在二进制表示中只有两个1,这使得模幂运算可以非常高效;同时它足够大,能避免一些潜在的攻击。

第四步:计算私钥指数 d d e 关于 φ(n) 的“模逆元”。也就是说, d 需要满足: (e * d) mod φ(n) = 1 。寻找 d 需要用到“扩展欧几里得算法”。这个算法不仅能求出 e φ(n) 的最大公约数(我们已知是1),还能同时求出满足 e*d + φ(n)*k = 1 的系数 d k 。此时, d 就是我们需要的私钥指数。由于是模 φ(n) 运算, d 通常也是一个和 n 长度相当的大数。

注意 :整个密钥生成过程中, p , q , φ(n) d 在计算完成后都必须立即从内存中安全擦除,只保留 (n, e) 作为公钥, (n, d) 作为私钥。任何一环泄露都意味着密钥对彻底失效。

2.3 加解密的正确性证明(简述)

为什么 c^d mod n 能变回 m ?这源于欧拉定理。简单推导如下: 已知 c = m^e mod n , 则 c^d mod n = (m^e)^d mod n = m^(e*d) mod n 。 根据密钥生成过程, e*d ≡ 1 (mod φ(n)) ,即 e*d = 1 + k*φ(n) 。 所以 m^(e*d) = m^(1 + k*φ(n)) = m * (m^φ(n))^k 。 根据欧拉定理,如果 m n 互质,则 m^φ(n) ≡ 1 (mod n) ,因此上式等于 m * 1^k ≡ m (mod n) 。 即使 m n 不互质(概率极低),利用中国剩余定理也能证明解密依然正确。这就保证了加密解密过程的可靠性。

3. C++实现的核心挑战与工具选型

理解了原理,接下来就要用C++来实现。我们立刻会遇到几个现实问题:

  1. 大整数问题 :RSA的 n , p , q , d 等都是上百位的大整数,远超C++原生数据类型(如 long long )的范围。
  2. 大素数生成 :如何快速、可靠地生成上百位的大素数?
  3. 模幂运算 :计算 m^e mod n ,其中指数 e 和底数 m 都可能很大,直接计算再取模会溢出且效率极低。
  4. 扩展欧几里得算法 :如何高效计算模逆元 d

对于这些问题,我们有几种选择:

  • 使用第三方大数库(如GMP, OpenSSL BN) :这是生产环境的标准做法,性能最优,安全性最高。但我们的目标是学习,直接调用库函数就失去了意义。
  • 使用C++自带的大整数类 :C++并没有标准的任意精度整数类。虽然有些编译器提供 __int128 ,但128位对于RSA来说远远不够。
  • 自己实现一个简单的大整数类 :这是本次我们选择的路。它最能锻炼能力,但需要仔细处理。

我们将实现一个基础的 BigInt 类,支持:

  • 构造函数(从字符串、 long long 初始化)
  • 基本的算术运算(加、减、乘、除、取模)
  • 比较运算
  • 快速模幂运算(Montgomery算法或二进制平方乘算法)
  • 扩展欧几里得算法

为了生成大素数,我们将实现一个简单的Miller-Rabin素性检测算法。这是一个概率算法,但通过增加检测轮数,可以将误判概率降到极低(如 2^{-128} ),在实际中完全可接受。

实操心得 :自己实现大数运算时,存储结构是关键。我们可以用 std::vector<uint32_t> 来按位存储大数,从低位到高位排列。这样加减乘除都可以分解为多个32位整数的运算。虽然性能远不如GMP,但对于理解算法和教学演示足够了。在实现乘法时,需要注意处理进位;实现除法(特别是大数除大数)是最复杂的部分,可以借鉴Knuth的算法。

4. 从零构建:BigInt类与核心算法实现

现在,我们开始动手编码。首先搭建我们的大整数运算基石。

4.1 基础BigInt类的设计

我们设计一个相对简单的 BigInt 类,内部用一个 std::vector<uint32_t> 存储数字的各个位(小端序,即 digits[0] 是最低位)。同时维护一个 bool 标志表示正负(RSA中所有数都是正数,但实现完整的类更有通用性)。

// bigint.h
#ifndef BIGINT_H
#define BIGINT_H

#include <vector>
#include <string>
#include <cstdint>

class BigInt {
public:
    // 构造函数
    BigInt();
    BigInt(long long num);
    BigInt(const std::string& numStr); // 从十进制字符串构造
    BigInt(const std::vector<uint32_t>& digits, bool isNegative = false);

    // 算术运算
    BigInt operator+(const BigInt& other) const;
    BigInt operator-(const BigInt& other) const;
    BigInt operator*(const BigInt& other) const;
    BigInt operator/(const BigInt& other) const;
    BigInt operator%(const BigInt& other) const;

    // 比较运算
    bool operator==(const BigInt& other) const;
    bool operator!=(const BigInt& other) const;
    bool operator<(const BigInt& other) const;
    bool operator>(const BigInt& other) const;

    // 工具函数
    bool isZero() const;
    BigInt abs() const;
    std::string toDecString() const; // 转换为十进制字符串
    static BigInt fromHexString(const std::string& hexStr); // 从十六进制字符串构造(方便测试)

    // 核心算法(声明为友元或静态成员)
    friend BigInt modularExponentiation(const BigInt& base, const BigInt& exponent, const BigInt& modulus);
    friend BigInt gcdExtended(const BigInt& a, const BigInt& b, BigInt& x, BigInt& y); // 扩展欧几里得

private:
    std::vector<uint32_t> digits; // 低位在前
    bool negative;

    // 内部辅助函数
    void trimZeros();
    int compareMagnitude(const BigInt& other) const; // 比较绝对值大小
    static std::pair<BigInt, BigInt> divide(const BigInt& dividend, const BigInt& divisor); // 除法返回商和余数
};

#endif // BIGINT_H

这个类的实现细节(如加减乘除的逐位运算)代码量较大,核心是模拟手算过程。这里我们更关注在RSA中用到的两个关键算法函数的实现。

4.2 快速模幂运算的实现

计算 base^exponent mod modulus 是RSA中最频繁的操作。直接计算 base^exponent 再取模是不可能的(数字太大)。我们必须使用“平方-乘”算法(也称为二进制指数法)。

其原理基于:将指数 exponent 用二进制表示,例如 e = 13 (二进制 1101 )。那么 base^13 = base^(8+4+1) = base^8 * base^4 * base^1 。我们可以通过反复平方来计算出这些分量,并在每一步都进行取模运算,防止数值爆炸。

// bigint.cpp 中的关键函数
BigInt modularExponentiation(const BigInt& base, const BigInt& exponent, const BigInt& modulus) {
    if (modulus == BigInt(1)) return BigInt(0); // 任何数模1都为0

    BigInt result(1);
    BigInt b = base % modulus;
    BigInt e = exponent;

    while (e > BigInt(0)) {
        // 如果当前二进制位为1
        if (e.digits[0] & 1) { // 检查最低位,这是简化的做法,完整实现需处理多位数
            result = (result * b) % modulus;
        }
        // 右移指数(相当于除以2)
        // 注意:这里需要实现 BigInt 的右移或除以2的操作,我们用一个简化版本
        e = e / BigInt(2); // 实际实现中应有更高效的位操作
        b = (b * b) % modulus; // 平方
    }
    return result;
}

注意事项 :上面的 e / BigInt(2) 和检查最低位是概念性代码。在实际的 BigInt 实现中,我们需要实现高效的位操作(如 isOdd() , rightShift() )来提升性能。模乘运算 (a * b) % modulus 是性能瓶颈,在生产级库中会使用Montgomery模乘来优化,我们自己实现时先用简单方法。

4.3 扩展欧几里得算法求模逆元

我们需要解方程 e*d ≡ 1 (mod φ(n)) ,也就是求 d 使得 e*d + φ(n)*k = 1 。扩展欧几里得算法可以同时求出最大公约数 gcd(e, φ(n)) 和系数 d , k

// 扩展欧几里得算法
// 返回 gcd(a, b),并计算出 x, y 使得 a*x + b*y = gcd(a, b)
BigInt gcdExtended(const BigInt& a, const BigInt& b, BigInt& x, BigInt& y) {
    if (b.isZero()) {
        x = BigInt(1);
        y = BigInt(0);
        return a;
    }

    BigInt x1, y1;
    BigInt gcd = gcdExtended(b, a % b, x1, y1);

    // 更新 x 和 y
    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

// 使用上述函数求模逆元
BigInt modInverse(const BigInt& a, const BigInt& m) {
    BigInt x, y;
    BigInt g = gcdExtended(a, m, x, y);
    if (g != BigInt(1)) {
        // a 和 m 不互质,逆元不存在(对于RSA密钥生成,这不应该发生)
        throw std::runtime_error("Modular inverse does not exist");
    }
    // 确保结果是正数
    BigInt result = (x % m + m) % m;
    return result;
}

在RSA密钥生成中,我们调用 d = modInverse(e, phi_n) 即可得到私钥指数 d

4.4 Miller-Rabin素性检测

生成大素数是关键且耗时的步骤。Miller-Rabin是一个概率性测试,但非常高效可靠。

算法思路 :对于一个待测奇数 n ,我们将其写成 n-1 = 2^s * d 的形式,其中 d 是奇数。然后随机选择一个底数 a ( 1 < a < n-1 ),计算 x = a^d mod n

  • 如果 x == 1 x == n-1 ,则 n 可能为素数,进入下一轮测试。
  • 否则,将 x 连续平方 s-1 次,每次平方后模 n 。如果某次得到 n-1 ,则 n 可能为素数,进入下一轮。
  • 如果以上都不满足,则 n 一定是合数。 重复这个过程 k 轮( k 越大,准确率越高)。如果所有轮次都通过,则我们可以说 n 是素数的概率极高。
bool isProbablePrime(const BigInt& n, int iterations = 20) {
    if (n < BigInt(2)) return false;
    if (n == BigInt(2) || n == BigInt(3)) return true;
    if (n % BigInt(2) == 0) return false; // 偶数

    // 将 n-1 写成 2^s * d 的形式
    BigInt d = n - BigInt(1);
    int s = 0;
    while (d % BigInt(2) == 0) {
        d = d / BigInt(2);
        s++;
    }

    // 进行 iterations 轮测试
    for (int i = 0; i < iterations; ++i) {
        // 随机生成一个 [2, n-2] 之间的底数 a
        // 这里需要一个安全的随机大数生成器,我们简化处理
        BigInt a = generateRandomBigInt(BigInt(2), n - BigInt(2));

        BigInt x = modularExponentiation(a, d, n);
        if (x == BigInt(1) || x == n - BigInt(1)) {
            continue; // 可能为素数,继续下一轮
        }

        bool continueTest = false;
        for (int j = 0; j < s - 1; ++j) {
            x = (x * x) % n;
            if (x == n - BigInt(1)) {
                continueTest = true;
                break;
            }
        }
        if (continueTest) {
            continue;
        }
        return false; // 一定是合数
    }
    return true; // 很可能为素数
}

有了这个函数,我们就可以通过循环随机生成大奇数,并用 isProbablePrime 测试它,直到找到一个素数为止。

5. 整合与测试:完整的RSA密钥生成与加解密

现在,我们将所有模块组合起来,实现完整的RSA流程。

5.1 RSA密钥对结构体

首先,定义密钥对的结构。

struct RSAPublicKey {
    BigInt n; // 模数
    BigInt e; // 公钥指数
};

struct RSAPrivateKey {
    BigInt n; // 模数
    BigInt d; // 私钥指数
};

5.2 密钥生成函数

#include <random>
#include <ctime>

std::pair<RSAPublicKey, RSAPrivateKey> generateRSAKeys(int bitLength) {
    // 1. 生成两个大素数 p, q (各约 bitLength/2 位)
    BigInt p = generateLargePrime(bitLength / 2);
    BigInt q = generateLargePrime(bitLength / 2);
    // 确保 p 和 q 不相等(极小概率事件,但需检查)
    while (p == q) {
        q = generateLargePrime(bitLength / 2);
    }

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

    // 3. 选择公钥指数 e,常用 65537
    BigInt e(65537);
    // 确保 e 与 φ(n) 互质,虽然 65537 是素数,但理论上仍需检查
    if (gcd(e, phi_n) != BigInt(1)) {
        // 极罕见情况,需重新选择 e,这里简单处理为抛异常
        throw std::runtime_error("e and phi(n) are not coprime");
    }

    // 4. 计算私钥指数 d
    BigInt d = modInverse(e, phi_n);

    // 5. 构造密钥对
    RSAPublicKey pubKey{n, e};
    RSAPrivateKey privKey{n, d};

    // !!! 安全擦除中间变量 p, q, phi_n !!!
    // 在实际应用中,需要使用安全的内存擦除函数
    // 例如,将存储这些值的 vector 用随机数据覆盖。

    return {pubKey, privKey};
}

其中 generateLargePrime 函数内部会调用我们之前实现的随机数生成和 isProbablePrime 检测。

5.3 加密与解密函数

加密和解密本质上都是模幂运算。

// 加密:明文 m 必须满足 0 <= m < n
BigInt rsaEncrypt(const BigInt& m, const RSAPublicKey& pubKey) {
    if (m >= pubKey.n) {
        throw std::runtime_error("Message too large for modulus");
    }
    return modularExponentiation(m, pubKey.e, pubKey.n);
}

// 解密
BigInt rsaDecrypt(const BigInt& c, const RSAPrivateKey& privKey) {
    return modularExponentiation(c, privKey.d, privKey.n);
}

5.4 简单测试与演示

为了测试,我们需要将字符串(或数据)转换为 BigInt 。一个简单的方法是将其视为一个大端序的字节数组,然后转换成一个大整数。但为了演示,我们先用小数字测试数学正确性。

int main() {
    // 使用小素数便于验证
    BigInt p(61);
    BigInt q(53);
    BigInt n = p * q; // 3233
    BigInt phi_n = (p-1)*(q-1); // 3120
    BigInt e(17); // 选择与3120互质的公钥指数
    BigInt d = modInverse(e, phi_n); // 应得到2753

    RSAPublicKey pubKey{n, e};
    RSAPrivateKey privKey{n, d};

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

    // 测试加密解密
    BigInt plaintext(123); // 明文
    std::cout << "Plaintext: " << plaintext.toDecString() << std::endl;

    BigInt ciphertext = rsaEncrypt(plaintext, pubKey);
    std::cout << "Ciphertext: " << ciphertext.toDecString() << std::endl;

    BigInt decrypted = rsaDecrypt(ciphertext, privKey);
    std::cout << "Decrypted: " << decrypted.toDecString() << std::endl;

    if (plaintext == decrypted) {
        std::cout << "RSA test PASSED!" << std::endl;
    } else {
        std::cout << "RSA test FAILED!" << std::endl;
    }

    return 0;
}

运行这个程序,你应该能看到加密解密成功的输出。这验证了我们核心算法的正确性。

6. 进阶话题:填充、性能与安全考量

一个能跑通的Demo距离“可用”还有很长的路。以下是几个必须考虑的进阶问题。

6.1 为什么需要填充?—— 对抗攻击

我们上面的实现是“教科书式RSA”或“裸RSA”。它在实际中使用是 极其危险 的,因为它存在多种攻击方式:

  • 确定性 :同样的明文永远加密成同样的密文,攻击者可以通过构建字典来破解。
  • 可延展性 :攻击者可以在不知道明文的情况下,修改密文使其解密出有特定关系的明文。
  • 小明文攻击 :如果明文 m 很小,使得 m^e < n ,那么加密就变成了 c = m^e (没有取模),攻击者直接对 c e 次方就能得到 m

解决方案是使用 填充方案 。最常用的是OAEP(Optimal Asymmetric Encryption Padding)。它的核心思想是在加密前,先将明文用随机数“填充”到与模数 n 长度相近,并且结构复杂化,破坏明文的原有结构。解密后,再去掉填充得到真实明文。 在任何实际应用中,都必须使用标准化的填充方案(如RSAES-OAEP或RSAES-PKCS1-v1_5)。

6.2 性能优化方向

我们自实现的 BigInt 性能很低。生产环境优化方向包括:

  1. 使用专业库 :直接集成GMP或使用OpenSSL的BIGNUM是正道。
  2. 算法优化
    • 乘法 :实现Karatsuba或FFT(快速傅里叶变换)算法来加速大数乘法。
    • 模幂 :使用滑动窗口法等优化指数扫描过程。
    • 模运算 :实现Barrett约减或Montgomery乘法,这是提升模幂运算速度的关键。
  3. 中国剩余定理(CRT)解密 :这是RSA解密的核心加速技术。私钥持有者知道 p q ,可以预先计算一些值,将解密运算 c^d mod n 分解为在模 p 和模 q 下的两个更小的运算,最后合成结果。速度可以提升4倍左右。

6.3 常见问题与调试技巧

在实现和调试过程中,你可能会遇到以下问题:

  1. 解密结果不正确

    • 检查密钥生成 :确保 e φ(n) 互质。确保 d e φ(n) 的逆元,验证 (e*d) % φ(n) == 1
    • 检查数据范围 :确保加密的明文整数 m 严格小于模数 n
    • 检查大数运算 :逐步调试 modularExponentiation 函数,用小的测试用例验证每一步的模乘和模平方结果是否正确。特别注意你实现的 BigInt::operator% 在除数为0或结果为负时的行为。
  2. 素数生成太慢

    • 优化随机数生成 :使用硬件随机数生成器(如 /dev/urandom std::random_device )。
    • 预筛选 :在调用耗时的Miller-Rabin测试前,先用小素数(比如前1000个素数)试除,快速排除明显的合数。
    • 调整Miller-Rabin迭代次数 :对于非密码学用途的演示,可以将迭代次数 k 降低到10-15次,以平衡速度和误判概率。
  3. 内存与性能瓶颈

    • 避免不必要的拷贝 :在 BigInt 运算中大量使用值传递会导致深拷贝,性能堪忧。合理使用移动语义、引用和返回值优化(RVO)。
    • 使用 reserve :在 std::vector<uint32_t> 操作前预估大小并使用 reserve ,减少动态扩容开销。

踩坑实录 :我在第一次实现大数除法时,因为一个边界条件没处理好(当被除数小于除数时,商应为0,余数为被除数),导致后续的模逆元计算总是出错,花了很长时间才定位。调试密码学代码,一定要从最小的、可验证的单元测试开始,比如先确保 BigInt(10) / BigInt(3) 得到商3余1,再测试模幂,最后测试整个RSA流程。

7. 项目总结与扩展思考

通过这个项目,我们不仅仅是实现了一个RSA算法,更是一次对C++能力、算法思想和安全意识的综合锻炼。从大整数的存储与运算,到数论算法的实现,再到对密码学核心概念的实践,每一步都充满了挑战。

这个自实现的RSA库 绝对不应用于任何真实的生产环境或安全敏感场景 。它的意义在于教育和理解。在真正的项目中,你应该使用久经考验的库,如 OpenSSL (C语言)、 Crypto++ Botan (C++)。这些库经过了无数安全专家的审查和优化,提供了完整的、抗侧信道攻击的、支持各种填充方案和标准的RSA实现。

如果你想在此基础上继续深入,可以考虑以下几个方向:

  1. 实现OAEP填充 :这是将“玩具”升级为“工具”的关键一步,研究PKCS#1 v2.2标准,实现编码和解码。
  2. 集成中国剩余定理 :修改私钥结构,存储 p , q , dP , dQ , qInv 等值,并实现CRT解密算法,对比性能提升。
  3. 支持文件加密 :将文件分块,每块转换为大整数,加密后再写回。注意分块大小要小于密钥长度(字节数)。
  4. 尝试其他公钥算法 :理解了RSA,可以再去看看基于椭圆曲线的ECC(椭圆曲线密码学),它的密钥更短、速度更快,是现代TLS的主流选择。

最后,密码学是一个深水区,自己动手实现是学习的最佳途径,但务必牢记“不要自己发明密码学”。理解原理,然后信任并使用那些由社区共同维护、经过严格审计的标准库。

更多推荐