C++手搓RSA加密:从大数运算到密钥生成全流程实现
1. 项目概述:为什么要在C++里手搓RSA?
如果你正在用C++处理一些敏感数据,比如用户密码、配置文件或者网络通信中的关键信息,那么“加密”这个词对你来说一定不陌生。对称加密(比如AES)很快,但有个老生常谈的问题:密钥怎么安全地交给对方?非对称加密,尤其是RSA,就是为了解决这个“信任传递”问题而生的。它用一对密钥(公钥和私钥),公钥可以大大方方地发给任何人用来加密,但只有持有私钥的你才能解开。这个特性让它在数字签名、密钥交换、HTTPS握手等场景里无处不在。
网上关于RSA原理的文章很多,但很多要么是纯数学推导,看得人头大;要么是直接调用 openssl 库,一行代码搞定,但内部发生了什么你一无所知。这次,我们不依赖任何第三方加密库,就只用C++标准库,从零开始实现一个完整的RSA加密解密流程。这不仅仅是“造轮子”,而是一次深入理解非对称加密核心机制的绝佳机会。你会亲手处理大素数生成、模幂运算、扩展欧几里得算法这些底层细节。对于C++开发者,尤其是对密码学、网络安全或系统底层感兴趣的朋友来说,这个过程能极大地加深你对算法、数论以及C++处理大整数运算的理解。
2. 核心原理与数学基础拆解
在动手写代码之前,我们必须把RSA背后的数学原理吃透。别怕,我们不用深究所有数论证明,但必须理解几个关键概念和它们是如何串联起来的。
2.1 RSA算法的三大数学支柱
RSA的安全性建立在“大数分解难题”上。简单说,给你一个很大的数(比如几百位),它是两个大素数的乘积,让你找出这两个素数来,以目前计算机的计算能力,在有限时间内几乎不可能完成。基于这个难题,RSA设计了三个核心步骤:
- 密钥生成 :核心是找到三个特殊的数字
(n, e, d)。 - 加密过程 :对于明文
m(需要是小于n的整数),计算密文c = m^e mod n。 - 解密过程 :对于密文
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++来实现。我们立刻会遇到几个现实问题:
- 大整数问题 :RSA的
n,p,q,d等都是上百位的大整数,远超C++原生数据类型(如long long)的范围。 - 大素数生成 :如何快速、可靠地生成上百位的大素数?
- 模幂运算 :计算
m^e mod n,其中指数e和底数m都可能很大,直接计算再取模会溢出且效率极低。 - 扩展欧几里得算法 :如何高效计算模逆元
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 性能很低。生产环境优化方向包括:
- 使用专业库 :直接集成GMP或使用OpenSSL的BIGNUM是正道。
- 算法优化 :
- 乘法 :实现Karatsuba或FFT(快速傅里叶变换)算法来加速大数乘法。
- 模幂 :使用滑动窗口法等优化指数扫描过程。
- 模运算 :实现Barrett约减或Montgomery乘法,这是提升模幂运算速度的关键。
- 中国剩余定理(CRT)解密 :这是RSA解密的核心加速技术。私钥持有者知道
p和q,可以预先计算一些值,将解密运算c^d mod n分解为在模p和模q下的两个更小的运算,最后合成结果。速度可以提升4倍左右。
6.3 常见问题与调试技巧
在实现和调试过程中,你可能会遇到以下问题:
-
解密结果不正确 :
- 检查密钥生成 :确保
e和φ(n)互质。确保d是e模φ(n)的逆元,验证(e*d) % φ(n) == 1。 - 检查数据范围 :确保加密的明文整数
m严格小于模数n。 - 检查大数运算 :逐步调试
modularExponentiation函数,用小的测试用例验证每一步的模乘和模平方结果是否正确。特别注意你实现的BigInt::operator%在除数为0或结果为负时的行为。
- 检查密钥生成 :确保
-
素数生成太慢 :
- 优化随机数生成 :使用硬件随机数生成器(如
/dev/urandom或std::random_device)。 - 预筛选 :在调用耗时的Miller-Rabin测试前,先用小素数(比如前1000个素数)试除,快速排除明显的合数。
- 调整Miller-Rabin迭代次数 :对于非密码学用途的演示,可以将迭代次数
k降低到10-15次,以平衡速度和误判概率。
- 优化随机数生成 :使用硬件随机数生成器(如
-
内存与性能瓶颈 :
- 避免不必要的拷贝 :在
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实现。
如果你想在此基础上继续深入,可以考虑以下几个方向:
- 实现OAEP填充 :这是将“玩具”升级为“工具”的关键一步,研究PKCS#1 v2.2标准,实现编码和解码。
- 集成中国剩余定理 :修改私钥结构,存储
p,q,dP,dQ,qInv等值,并实现CRT解密算法,对比性能提升。 - 支持文件加密 :将文件分块,每块转换为大整数,加密后再写回。注意分块大小要小于密钥长度(字节数)。
- 尝试其他公钥算法 :理解了RSA,可以再去看看基于椭圆曲线的ECC(椭圆曲线密码学),它的密钥更短、速度更快,是现代TLS的主流选择。
最后,密码学是一个深水区,自己动手实现是学习的最佳途径,但务必牢记“不要自己发明密码学”。理解原理,然后信任并使用那些由社区共同维护、经过严格审计的标准库。
更多推荐
所有评论(0)