从零实现C++大整数类与RSA加密算法：深入理解非对称加密原理-拓冰建站

1. 项目概述：从大整数到RSA加密

最近在整理一些旧项目，翻到了一个当年让我印象深刻的“轮子”——一个纯手工打造的C++大整数类，并用它完整实现了RSA加密算法。现在回想起来，这个项目虽然“造轮子”的意味很浓，但它对理解计算机底层数据表示、密码学原理以及C++面向对象设计，有着教科书无法替代的价值。你可能会问，现在有Boost.Multiprecision、GMP这样的成熟库，为什么还要自己写？我的回答是，这就像学车用手动挡一样，理解了离合、油门和换挡的配合，你才能真正驾驭车辆。自己实现一遍大整数运算和RSA，你会对“为什么RSA是安全的”、“一次加密解密背后到底发生了多少计算”有刻骨铭心的认识。

这个项目主要解决两个核心问题：第一，C++内置的整数类型（如long long）范围有限，无法处理RSA所需的数百甚至数千位的大整数，因此我们需要一个能够进行任意精度算术运算的BigInteger类。第二，基于这个大整数类，实现RSA算法的关键步骤：密钥生成、加密和解密。这个过程会涉及到数论中的模幂运算、扩展欧几里得算法等核心概念。无论你是想深入理解非对称加密的底层原理，还是准备应对那些喜欢问底层实现的技术面试，亦或是为特定的嵌入式或安全敏感场景定制加密组件，这个“从零开始”的旅程都会让你受益匪浅。

2. 核心需求与设计思路拆解

在动手写代码之前，我们必须把需求理清楚。一个完整的“大整数类+RSA实现”项目，远不止是让两个大数相乘那么简单。

2.1 大整数类的核心需求

首先，我们的BigInteger类需要模拟我们手算整数的过程。计算机内存是有限的，我们无法用一个int变量存下1024位的数字。通用的方法是采用“多精度算术”，即用一个数组（或向量）来存储数字，数组的每个元素代表数字的一位。通常，我们选择以一个大进制（如2^32或10^9）为基，这样每个数组元素就能存储很大一部分数字，提高运算效率。

核心功能需求如下：

表示与存储：能够表示任意大小的正整数（我们先从正整数开始，再考虑符号）。内部使用std::vector<uint32_t>这样的容器来存储“数字位”。
基本算术运算：实现加、减、乘、除（带余数）。这是最核心也是最复杂的部分。例如，乘法不能简单地用*运算符，需要实现像小学竖式一样的算法（如Karatsuba算法可以优化大数乘法）。
比较运算：判断两个大整数的大小、是否相等。
位运算与移位：虽然不直接用于RSA，但实现左移、右移（相当于乘以或除以2的幂）对内部优化和某些算法有帮助。
输入/输出：能够从字符串（如“12345678901234567890”）构造大整数，也能将大整数转换为字符串输出。这涉及到进制转换。
辅助函数：求绝对值、判断奇偶性等。

设计考量：我们选择uint32_t作为每个“位”的类型。为什么不是uint64_t？因为在进行乘法运算时，两个uint32_t相乘的结果最大为2^64 - 2^33 + 1，这可以安全地存储在一个uint64_t的中间变量中，而不会溢出。这为我们实现进位处理提供了便利。如果直接用uint64_t，乘法则需要处理128位的中间结果，在标准C++中会更麻烦。

2.2 RSA算法的核心需求与流程

有了大整数这个“超级算盘”，我们才能玩转RSA。RSA的安全性基于“大数分解难题”，即给定一个大整数N（它是两个大质数p和q的乘积），在可接受的时间内分解出p和q是极其困难的。

RSA密钥生成流程：

选择两个大质数p和q：这是关键。我们需要一个生成大质数的算法，通常使用Miller-Rabin素性测试。
计算模数n：n = p * q。n的长度（比特数）就是RSA密钥的长度（如1024位、2048位）。
计算欧拉函数φ(n)：φ(n) = (p-1) * (q-1)。
选择公钥指数e：选择一个整数e，满足1 < e < φ(n)，且e与φ(n)互质（最大公约数为1）。通常选择65537（0x10001），因为它二进制表示中1很少，能加速加密运算，且是质数，与大多数φ(n)互质。
计算私钥指数d：计算e关于模φ(n)的模逆元d。即满足(d * e) % φ(n) = 1。这需要用到扩展欧几里得算法。

公钥为(n, e)，私钥为(n, d)。p, q, φ(n)必须严格保密。

加密与解密：

加密：对于明文消息M（需要先转换为一个小于n的整数），计算密文C = M^e mod n。
解密：用私钥计算明文M = C^d mod n。

可以看到，RSA的核心运算就是模幂运算（Modular Exponentiation）：计算base^exponent mod modulus。直接先计算幂再取模是不可行的，因为中间结果会巨大无比。必须使用快速模幂算法（如平方-乘算法）。

设计思路总结：我们的项目将分为两大模块。第一个模块是BigInteger类，它提供所有底层的大整数运算能力。第二个模块是RSA类，它依赖BigInteger，实现密钥生成、加密和解密。我们将采用自底向上的构建方式，先确保大整数运算正确可靠，再在其上构建RSA这座大厦。

3. 大整数类（BigInteger）的实现细节

这是整个项目最基础，也最考验耐心和细致程度的部分。一个微小bug可能导致后续所有RSA计算错误。

3.1 内部表示与构造函数

我们选择用std::vector<uint32_t>来存储数字，采用小端序（Least Significant Digit First），即向量的第0个元素存储数字的最低位。这样在做加法、乘法时，从低位向高位处理会更自然。

class BigInteger { private: std::vector<uint32_t> digits; // 存储数字，digits[0]是最低位 bool isNegative; // 符号位，true表示负数 public: // 默认构造为0 BigInteger() : digits({0}), isNegative(false) {} // 从uint64_t构造 BigInteger(uint64_t value) : isNegative(false) { if (value == 0) { digits.push_back(0); } else { while (value > 0) { digits.push_back(value & 0xFFFFFFFF); // 取低32位 value >>= 32; // 右移32位 } } } // 从十进制字符串构造，如“123456789” BigInteger(const std::string& decimalStr); };

从字符串构造是一个难点。我们需要模拟“读入字符串，不断乘以10并加下一位”的过程。一个高效的方法是先按9位十进制数为一组进行分组（因为10^9 < 2^32，一组数可以安全存入一个uint32_t），然后再进行进制转换。

3.2 核心算术运算的实现

加法：从最低位开始，对应位相加，并处理进位。进位最多为1（因为两个32位数相加，最大为2^33 - 2，除以2^32的商最大为1）。

BigInteger operator+(const BigInteger& rhs) const { if (this->isNegative == rhs.isNegative) { // 同号相加 BigInteger result; result.digits.clear(); result.isNegative = this->isNegative; size_t maxLen = std::max(this->digits.size(), rhs.digits.size()); uint64_t carry = 0; // 使用64位存储中间和与进位 for (size_t i = 0; i < maxLen || carry; ++i) { uint64_t sum = carry; if (i < this->digits.size()) sum += this->digits[i]; if (i < rhs.digits.size()) sum += rhs.digits[i]; result.digits.push_back(sum & 0xFFFFFFFF); // 存储低32位 carry = sum >> 32; // 进位是高32位 } // 移除前导零（最高位为0的情况） result.removeLeadingZeros(); return result; } else { // 异号相加转化为减法 // ... 减法实现 } }

减法：比加法复杂，因为需要处理借位和结果符号。核心是确保我们总是用大数减小数。可以先实现一个“绝对值减法”的辅助函数，然后根据符号规则组合结果。

乘法：最直接的算法是模拟竖式乘法，时间复杂度为O(n²)。对于我们的教学项目，实现这个即可。但如果你追求效率，可以实现更快的Karatsuba算法（时间复杂度约为O(n^1.585)）。其思想是将两个大数X和Y分别拆分为高位和低位：X = A * B^m + B,Y = C * B^m + D。那么X*Y = AC * B^(2m) + ((A+B)(C+D) - AC - BD) * B^m + BD。这样将一次大规模乘法转化为三次较小规模的乘法（递归进行）。

除法：这是最复杂的运算。常用的算法是“试除法”或更高效的“Knuth除法”（D算法）。对于入门，实现一个简单的“移位相减”法：将被除数和除数对齐，然后不断将除数左移（相当于乘以2），直到接近被除数，然后相减，并记录商位。这是一个需要仔细处理边界条件和性能的环节。

实操心得：在实现除法时，一个常见的坑是前导零的处理。在运算过程中可能会产生无效的高位零，必须在返回结果前调用一个removeLeadingZeros()函数来清理，否则会影响后续比较和运算的正确性。我曾在调试一个模逆元运算时，花了半天时间才发现是因为一个中间结果的digits向量末尾多了一个0，导致比较大小出错。

3.3 辅助函数与运算符重载

除了四则运算，我们还需要：

比较运算符(<,<=,>,>=,==,!=)：从最高位开始逐位比较。
模运算(%)：在实现除法时，余数自然就得到了。

快速幂与模幂：这是RSA的基石。实现一个函数BigInteger modPow(const BigInteger& exponent, const BigInteger& modulus)。使用平方-乘算法：

BigInteger result = 1; BigInteger base = *this % modulus; BigInteger exp = exponent; while (exp > 0) { if (exp.isOdd()) { // 判断指数当前最低位是否为1 result = (result * base) % modulus; } base = (base * base) % modulus; // 平方 exp = exp >> 1; // 指数右移一位 } return result;

这个算法将计算复杂度从O(exponent)降到了O(log exponent)。

最大公约数(GCD)与扩展欧几里得算法：用于计算模逆元。扩展欧几里得算法不仅能求出gcd(a,b)，还能找到整数x和y，使得ax + by = gcd(a,b)。当a与b互质时，x就是a模b的逆元。

4. RSA加密系统的具体实现

有了强大的BigInteger，实现RSA就相对清晰了。我们将构建一个RSAKeyPair结构来保存公私钥，并创建一个RSA类来封装所有操作。

4.1 密钥生成：寻找大质数

这是RSA安全性的根本。我们不可能遍历所有数来找质数，而是采用概率性测试。最常用的是Miller-Rabin素性测试。

Miller-Rabin测试原理：对于一个待测奇数n，我们可以写成n-1 = 2^s * d，其中d是奇数。如果n是质数，那么对于任意整数a (1 < a < n-1)，以下两个条件至少有一个成立：

a^d ≡ 1 (mod n)
存在某个r (0 <= r < s)，使得a^(2^r * d) ≡ -1 (mod n)

如果对于某个a，以上都不成立，那么n一定是合数。如果成立，n可能是质数。通过多次随机选择不同的a进行测试，可以将误判（合数被判定为质数）的概率降到极低（如测试k次后，错误概率小于4^{-k}）。

bool isProbablePrime(const BigInteger& n, int iterations = 20) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n.isEven()) return false; // 偶数不是质数 // 将n-1写成 2^s * d 的形式 BigInteger d = n - 1; int s = 0; while (d.isEven()) { d = d >> 1; s++; } // 进行iterations次测试 for (int i = 0; i < iterations; ++i) { BigInteger a = getRandomBigInt(2, n - 2); // 获取随机底数a BigInteger x = modPow(a, d, n); // 计算 a^d mod n if (x == 1 || x == n - 1) { continue; // 可能为质数，继续测试下一个a } bool continueTest = false; for (int r = 1; r < s; ++r) { x = (x * x) % n; // 平方 if (x == n - 1) { continueTest = true; break; } } if (continueTest) continue; return false; // 一定是合数 } return true; // 通过所有测试，很可能是质数 }

生成质数时，我们先随机生成一个大奇数，然后用Miller-Rabin测试它，如果不是质数，就不断加2再测试，直到找到质数为止。

4.2 计算模逆元：扩展欧几里得算法

生成公钥指数e（如65537）后，我们需要计算私钥指数d，满足e*d ≡ 1 (mod φ(n))。这需要用到扩展欧几里得算法。

// 扩展欧几里得算法，返回 gcd(a,b)，并设置 x, y 使得 ax + by = gcd(a,b) BigInteger extendedGcd(const BigInteger& a, const BigInteger& b, BigInteger& x, BigInteger& y) { if (b == 0) { x = 1; y = 0; return a; } BigInteger x1, y1; BigInteger gcd = extendedGcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return gcd; } // 计算 a 在模 m 下的逆元，如果逆元不存在则抛出异常 BigInteger modInverse(const BigInteger& a, const BigInteger& m) { BigInteger x, y; BigInteger g = extendedGcd(a, m, x, y); if (g != 1) { throw std::runtime_error("模逆元不存在"); } // 确保结果为正数 return (x % m + m) % m; }

计算出的x可能为负数，我们需要将其调整到[0, m)范围内。

4.3 加密与解密的实现

至此，所有准备工作已完成。加密和解密就是直接的模幂运算。

class RSA { private: BigInteger n_; // 模数 BigInteger e_; // 公钥指数 BigInteger d_; // 私钥指数 // p, q, phi(n) 在生成后应被安全清除 public: struct PublicKey { BigInteger n; BigInteger e; }; struct PrivateKey { BigInteger n; BigInteger d; }; // 密钥生成 void generateKeys(int bitLength) { // 1. 生成两个大质数p, q，长度约为bitLength/2 BigInteger p = generateLargePrime(bitLength / 2); BigInteger q = generateLargePrime(bitLength / 2); // 确保p != q while (p == q) { q = generateLargePrime(bitLength / 2); } // 2. 计算 n = p * q n_ = p * q; // 3. 计算 φ(n) = (p-1)*(q-1) BigInteger phi_n = (p - 1) * (q - 1); // 4. 选择公钥指数 e，通常为65537 e_ = 65537; // 确保 e 与 φ(n) 互质 while (gcd(e_, phi_n) != 1) { // 极少发生，如果发生则稍微改变e或重新生成质数 e_ = e_ + 2; } // 5. 计算私钥指数 d = e^(-1) mod φ(n) d_ = modInverse(e_, phi_n); // 安全清除 p, q, phi_n (可选，实际中很重要) // p.clear(); q.clear(); phi_n.clear(); } // 使用公钥加密 BigInteger encrypt(const BigInteger& message, const PublicKey& pubKey) { // 明文 m 必须满足 0 <= m < n if (message >= pubKey.n) { throw std::runtime_error("消息过长，无法加密"); } return modPow(message, pubKey.e, pubKey.n); } // 使用私钥解密 BigInteger decrypt(const BigInteger& ciphertext, const PrivateKey& privKey) { // 密文 c 必须满足 0 <= c < n return modPow(ciphertext, privKey.d, privKey.n); } // 获取密钥对 PublicKey getPublicKey() const { return {n_, e_}; } PrivateKey getPrivateKey() const { return {n_, d_}; } };

4.4 数据的分块与填充

上面的代码直接对一个大整数进行加密。但实际应用中，我们需要加密的是字节流（如文件、网络消息）。这就涉及到两个问题：

分块：RSA一次能加密的数据长度受限于模数n。对于1024位的n，其值小于2^1024，因此能加密的明文整数必须小于2^1024，这大约相当于128字节。对于更长的数据，需要分成块进行加密（但RSA很慢，通常只用它加密一个对称密钥）。
填充：直接加密（称为“教科书RSA”）是不安全的，容易受到多种攻击。必须使用填充方案，如PKCS#1 v1.5填充或OAEP（最优非对称加密填充）。填充会在明文前加入随机数据，确保每次加密相同明文得到的密文都不同，并增加结构以抵抗攻击。

在我们的教学实现中，为了聚焦核心，可以暂时省略填充，但必须明确这仅用于学习，绝不能用于实际系统的安全通信。

5. 性能优化与常见问题排查

自己实现的大整数库和RSA，性能肯定无法与GMP、Crypto++等高度优化的工业级库相比。但我们可以通过一些优化来提升体验，并了解可能遇到的问题。

5.1 大整数运算的优化点

乘法算法升级：将基础的竖式乘法替换为Karatsuba算法。当数字位数超过一定阈值（如40个uint32_t）时，切换到Karatsuba，可以显著提升大数乘法的速度。
内存预分配：在已知结果大致位数时，为digits向量预分配（reserve）空间，避免多次动态扩容。
移除前导零：在每次运算后，特别是除法、乘法后，要记得调用removeLeadingZeros()，避免无效计算和内存浪费。
使用移动语义：在C++11及以上，为BigInteger实现移动构造函数和移动赋值运算符，避免在返回对象时不必要的深拷贝。

5.2 RSA实现中的典型问题与调试

加密解密结果不正确：
- 首先检查大整数基础运算：编写单元测试，测试BigInteger的加、减、乘、除、模运算是否正确。特别是除法和模运算，最容易出错。
- 检查模幂运算：单独测试modPow函数。用小的数字验证，比如计算2^10 mod 11，看结果是否为(1024%11)=1。
- 验证密钥关系：生成密钥后，随机取一个小整数m，计算c = m^e mod n，再计算m2 = c^d mod n，验证m是否等于m2。这是验证整个RSA流程是否正确的金标准。
- 检查数据范围：确保加密的明文整数严格小于模数n。
性能极慢：
- 算法复杂度：确认使用的是快速模幂算法（平方-乘），而不是先求幂再取模。
- 大整数乘法：如果乘法是O(n²)的朴素算法，对于1024位密钥（约32个uint32_t）尚可，对于2048位就会很慢。考虑实现Karatsuba。
- 质数生成：Miller-Rabin测试的次数iterations设置为15-20次即可在安全性和速度间取得很好平衡。过多无益。
内存消耗过大：
- 检查拷贝：避免在函数参数传递和返回时不必要的BigInteger拷贝，使用常量引用或移动语义。
- 及时清除敏感数据：在密钥生成后，用于计算d的中间变量p,q,phi_n应及时清空（例如，将其赋值为0）。

5.3 一个完整的调试示例

假设我们实现后，加密解密不对。我们可以进行最小化测试：

// 测试1：基础大整数运算 BigInteger a("123456789"); BigInteger b("987654321"); BigInteger sum = a + b; std::cout << "Sum: " << sum.toString() << std::endl; // 应输出 1111111110 // 测试2：模幂运算 BigInteger base(7); BigInteger exp(10); BigInteger mod(11); BigInteger result = modPow(base, exp, mod); std::cout << "7^10 mod 11 = " << result.toString() << std::endl; // 应输出 1 // 测试3：RSA小规模测试（使用小质数，便于人工验证） RSA rsa; // 我们可以手动设置小的p, q, e, d进行测试，而不是调用generateKeys BigInteger p(61); // 质数 BigInteger q(53); // 质数 BigInteger n = p * q; // 3233 BigInteger phi = (p-1)*(q-1); // 3120 BigInteger e(17); // 与3120互质 BigInteger d = modInverse(e, phi); // 计算d，应为2753 rsa.setKeys(n, e, d); // 假设有一个设置密钥的函数 BigInteger message(65); // 明文 BigInteger cipher = rsa.encrypt(message); BigInteger plain = rsa.decrypt(cipher); std::cout << "Message: " << message.toString() << std::endl; std::cout << "Cipher: " << cipher.toString() << std::endl; std::cout << "Decrypted: " << plain.toString() << std::endl; // 应输出65

通过这种从小到大的渐进式测试，可以有效地定位问题所在。

6. 项目总结与扩展思考

手动实现一遍大整数类和RSA算法，是一个极具挑战性但也收获满满的过程。它强迫你去思考整数在计算机中是如何被表示和操作的，去理解模运算、幂运算这些抽象概念的具体计算步骤，去体会一个看似简单的“加密”函数背后庞大的计算量。

几点深刻的体会：

正确性优先于性能：在最初实现时，不要追求极致的优化。先确保算法的每一步逻辑正确，输出结果准确。用一个庞大的、未经优化的BigInteger完成一次2048位RSA加密可能需要几秒甚至更久，但这没关系，只要它是正确的。在此基础之上，再去考虑用Karatsuba优化乘法，用滑动窗口法优化模幂。
测试是生命线：为BigInteger的每一个操作编写详尽的单元测试。包括边界情况（如零、一、大数）、溢出情况。对于RSA，使用已知的测试向量（可以从标准文档或其它密码库中找到）进行验证。
理解“为什么”比“怎么做”更重要：你知道Miller-Rabin测试为什么多次迭代后错误概率极低吗？你知道为什么RSA解密一定能把密文恢复成明文吗（欧拉定理的应用）？在实现过程中，带着这些问题去查阅资料，你的理解会深刻得多。
自己实现的密码不能用于生产环境：这是最重要的安全警示。我们的实现缺乏常数时间执行（防御时序攻击）、缺乏安全的随机数生成、缺乏标准的填充方案，并且可能存在侧信道漏洞。学习的目的在于理解原理，实际应用请务必使用OpenSSL、Crypto++、libsodium等经过严格审计和测试的库。

可能的扩展方向：