从原理到实现：C++手写AES与RSA加密算法全解析

1. 项目概述为什么我们需要自己动手实现加密在当今这个数据即资产的时代加密技术早已不是密码学家的专属玩具而是每一位开发者尤其是系统级、后端或安全相关领域开发者必须掌握的核心技能。你可能在项目中调用过 OpenSSL 的接口或者使用过某个语言内置的加密库但有没有那么一刻你心里会犯嘀咕这个黑盒子里到底发生了什么当性能出现瓶颈或者遇到一个诡异的跨平台兼容性问题时那种无从下手的无力感相信不少人都体会过。这正是我动手用 C 从头实现 AES 和 RSA 加密算法的初衷。这绝不是一个“重复造轮子”的学术练习而是一次深入加密算法心脏的“外科手术”。通过亲手实现你才能真正理解 AES 的字节代换、行移位、列混合和轮密钥加这四大步骤是如何环环相扣的你才能看清 RSA 的大数运算、模幂计算背后那些关于质数、欧拉函数和模逆的数学之美。更重要的是当你掌握了这些底层原理性能优化就不再是盲人摸象。你知道在哪里可以并行计算在哪里可以预计算在哪里可以牺牲一点灵活性换取数十倍的性能提升。这份指南就是我这次“手术”的完整记录包含了从原理到实现从基础代码到极致优化的全路径。无论你是想夯实基础、应对面试还是真正要解决生产环境中的加密性能瓶颈这里都有你想要的答案。2. 核心密码学原理快速解析在动手写代码之前我们必须先打好地基。AES 和 RSA 设计哲学迥异理解其核心原理是后续一切优化工作的前提。2.1 AES对称加密的“标准答案”AESAdvanced Encryption Standard是一种分组对称加密算法。所谓“对称”就是加密和解密使用同一把密钥。“分组”意味着它每次处理固定长度的一块数据AES 是 128 位即 16 字节。它的核心在于“置换”和“混淆”通过多轮重复的、可逆的变换将明文彻底打乱。AES 主要有三种密钥长度AES-128, AES-192, AES-256分别对应 10、12、14 轮加密。每一轮操作都包含四个步骤字节代换SubBytes通过一个称为 S-Box 的非线性替换表将状态矩阵中的每一个字节替换成另一个字节。这是 AES 非线性的主要来源能有效抵抗线性密码分析。行移位ShiftRows将状态矩阵的每一行进行循环左移第 0 行不移第 1 行移 1 位第 2 行移 2 位第 3 行移 3 位。这一步提供了扩散性。列混合MixColumns将状态矩阵的每一列视为一个系数在有限域 GF(2^8) 上的多项式与一个固定的多项式进行模乘运算。这一步极大地增强了扩散效果。轮密钥加AddRoundKey将当前的状态矩阵与当前轮的轮密钥进行简单的按位异或XOR操作。密钥由此被引入加密过程。最后一轮略有不同它省略了列混合步骤这是为了确保加密和解密过程的结构对称便于实现。注意AES 的加解密算法并不完全对称。解密并非简单地将加密步骤逆序执行而是每个步骤都有其对应的逆操作InvSubBytes, InvShiftRows, InvMixColumns。但在一种称为“等价解密电路”的实现方式中可以通过调整轮密钥的顺序和内容使得解密过程与加密过程使用相同的结构这在硬件实现中很有优势。我们软件实现通常采用直接的逆操作。2.2 RSA非对称加密的基石RSA 的安全性建立在“大数质因数分解”这一数学难题之上。它的过程比 AES 更“数学化”密钥生成选择两个大质数 p 和 q。计算 n p * q。n 的长度就是 RSA 密钥的长度如 2048 位。计算欧拉函数 φ(n) (p-1)*(q-1)。选择一个整数 e满足 1 e φ(n)且 e 与 φ(n) 互质。e 通常取 655370x10001因为它二进制表示中 1 很少计算效率高且安全。计算 d使得 (d * e) mod φ(n) 1。d 就是 e 关于 φ(n) 的模逆元是私钥的核心部分。公钥为 (n, e)私钥为 (n, d)。p, q, φ(n) 必须严格保密。加密与解密加密用公钥对于明文消息 m (需要转换为小于 n 的整数)计算密文 c m^e mod n。解密用私钥对于密文 c计算明文 m c^d mod n。这里的核心运算是“模幂运算”即计算a^b mod n。当指数 be 或 d非常大时比如一个 2048 位的数直接计算是不可行的必须使用快速模幂算法如平方-乘算法。实操心得RSA 的直接运算对象是“大整数”远超标准 C 数据类型如long long的范围。因此实现 RSA 的第一步是实现一个支持加、减、乘、除、模运算的大整数类Big Integer。这是整个 RSA 实现中最具挑战性的部分也是性能优化的关键战场。市面上有 GMPGNU Multiple Precision Arithmetic Library这样的专业库但为了学习和深度控制我们选择自己实现一个基础版本。3. 核心模块设计与实现有了理论武装我们开始搭建代码框架。一个清晰的模块划分能让后续的编码和调试事半功倍。3.1 AES 模块设计我们的 AES 模块将围绕一个核心的AES类来构建。这个类需要封装密钥、状态并提供加解密接口。// aes.h #ifndef AES_H #define AES_H #include vector #include cstdint class AES { public: enum KeySize { AES_128 16, AES_192 24, AES_256 32 }; // 构造函数传入密钥和密钥长度 AES(const uint8_t* key, KeySize key_size AES_128); // 加密一个 128 位的数据块 void encryptBlock(uint8_t* block); // 解密一个 128 位的数据块 void decryptBlock(uint8_t* block); // 针对任意长度数据的 CBC 模式加密/解密 std::vectoruint8_t encryptCBC(const std::vectoruint8_t plaintext, const std::vectoruint8_t iv); std::vectoruint8_t decryptCBC(const std::vectoruint8_t ciphertext, const std::vectoruint8_t iv); private: KeySize m_keySize; int m_rounds; // 加密轮数 uint8_t m_roundKey[240]; // 扩展后的轮密钥最多 (141)*16240 字节 uint8_t m_state[4][4]; // 当前处理的状态矩阵 // 内部核心函数 void keyExpansion(const uint8_t* key); void subBytes(); void shiftRows(); void mixColumns(); void addRoundKey(int round); // 解密逆操作 void invSubBytes(); void invShiftRows(); void invMixColumns(); }; #endif // AES_H关键点解析状态矩阵m_stateAES 所有操作都是在一个 4x4 的字节矩阵上进行的。在实现时我们既可以用二维数组也可以用一个一维的 16 字节数组通过索引映射来模拟行列。二维数组在理解行移位和列混合时更直观。轮密钥扩展keyExpansion这是 AES 的第一个关键步骤。它通过 Rijndael 的密钥调度算法将初始的 128/192/256 位密钥扩展成用于每一轮加密的轮密钥。这个算法本身也使用了 S-Box 和轮常量。务必确保此函数正确无误否则后续所有加解密都是错的。工作模式我们提供了基础的块加密/解密并实现了 CBC密码分组链接模式作为示例。CBC 模式需要一个初始化向量IV来增加随机性且能有效避免相同的明文块加密成相同的密文块。在实际应用中你还需要考虑 PKCS#7 填充等细节。3.2 大整数与 RSA 模块设计RSA 的实现始于一个大整数类BigInt。我们不会实现一个全功能的 GMP而是聚焦于 RSA 所需的操作构造、比较、加减乘除、取模、模幂、模逆。// bigint.h #ifndef BIGINT_H #define BIGINT_H #include vector #include cstdint #include string class BigInt { public: BigInt(); BigInt(uint64_t value); BigInt(const std::string hexStr); // 从16进制字符串构造 BigInt(const std::vectoruint8_t bytes, bool isBigEndian true); // 算术运算 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; // ... 其他比较操作符 // 核心算法快速模幂运算 (a^b mod n) static BigInt modPow(const BigInt base, const BigInt exponent, const BigInt modulus); // 辅助函数 bool isZero() const; size_t bitLength() const; std::string toHexString() const; std::vectoruint8_t toBytes(bool isBigEndian true) const; private: std::vectoruint32_t m_digits; // 使用 uint32_t 作为基础存储单元便于实现进位处理 bool m_isNegative; // 内部辅助函数如学校乘法、Karatsuba乘法、除法算法等 void normalize(); };有了BigIntRSA 的实现就相对直接了// rsa.h #ifndef RSA_H #define RSA_H #include bigint.h #include utility class RSA { public: struct PublicKey { BigInt n; // 模数 BigInt e; // 公钥指数 }; struct PrivateKey { BigInt n; // 模数 BigInt d; // 私钥指数 }; // 生成一对 RSA 密钥密钥长度指 n 的比特数如 1024, 2048 static std::pairPublicKey, PrivateKey generateKeyPair(int keyBits 2048); // 使用公钥加密 static BigInt encrypt(const PublicKey pubKey, const BigInt message); // 使用私钥解密 static BigInt decrypt(const PrivateKey privKey, const BigInt ciphertext); // 使用私钥签名本质是解密操作 static BigInt sign(const PrivateKey privKey, const BigInt hash); // 使用公钥验签本质是加密操作 static bool verify(const PublicKey pubKey, const BigInt hash, const BigInt signature); private: // 辅助函数生成大素数、计算模逆等 static BigInt findPrime(int bits); static BigInt modInverse(const BigInt a, const BigInt m); };关键点解析大数存储我们使用std::vectoruint32_t来存储大数的每一位以 2^32 为基。选择 32 位是因为它在 64 位和 32 位系统上都能高效地进行进位和乘法计算。质数生成findPrime是 RSA 密钥生成中最耗时的部分。通常采用随机生成大奇数然后用米勒-拉宾素性测试进行快速判定。需要多次测试以确保足够高的概率是素数。模幂运算BigInt::modPow是 RSA 加解密和签名的核心必须使用平方-乘算法来实现。其基本思想是将指数二进制化根据每一位是 0 还是 1 决定是平方还是平方后乘底数。数据转换RSA 操作的对象是BigInt但实际应用中我们需要加密字节流或字符串。这涉及到填充方案如 PKCS#1 v1.5 或 OAEP和将字节流转换为BigInt。这是一个容易出错的地方需要严格按照标准实现。4. 性能优化深度剖析实现功能只是第一步让代码飞起来才是工程化的追求。以下是针对 AES 和 RSA 的深度优化技巧。4.1 AES 性能优化实战AES 的优化主要围绕查表和并行化展开。1. 使用预计算查表T-table这是软件实现 AES 最经典的优化手段。将一轮中的SubBytes、ShiftRows、MixColumns三个步骤合并通过预先计算好的表T-table来一次性完成变换。通常需要 4 张 256 项每项 32 位的查找表。// 预计算 T-table static const uint32_t Te0[256], Te1[256], Te2[256], Te3[256]; // 用于加密 static const uint32_t Td0[256], Td1[256], Td2[256], Td3[256]; // 用于解密 // 优化后的加密轮函数以一轮为例 void AES::encryptRoundOptimized(int round) { // 将状态矩阵的每一列通过查表快速计算 uint32_t s0, s1, s2, s3; // ... 从 m_state 加载数据到 s0-s3 ... s0 Te0[(s0 24) ] ^ Te1[(s1 16) 0xff] ^ Te2[(s2 8) 0xff] ^ Te3[(s3 ) 0xff] ^ m_roundKey[round*4]; // ... 类似计算 s1, s2, s3 ... // ... 将 s0-s3 存回 m_state ... }通过这种方式原本需要数十次运算的一轮操作被缩减为几次内存查表和几次异或操作性能提升可达一个数量级。2. 利用现代 CPU 指令集AES-NI如果你的目标平台是较新的 x86/x86-64 CPUIntel Westmere 架构以后或 AMD Bulldozer 以后那么 AES-NIAES New Instructions指令集是终极武器。它通过硬件指令直接完成 AES 的核心步骤速度极快且能有效抵御旁路攻击。// 使用编译器 intrinsics (需要包含 wmmintrin.h, 编译时启用 -maes) #include wmmintrin.h __m128i aes_encrypt_block(__m128i block, const __m128i* round_keys) { block _mm_xor_si128(block, round_keys[0]); for (int i 1; i 10; i) { // AES-128 为例 block _mm_aesenc_si128(block, round_keys[i]); } block _mm_aesenclast_si128(block, round_keys[10]); return block; }实操心得在实现中最好能提供多套后端一个纯软件的查表优化版本兼容性好一个 AES-NI 版本性能极致。在运行时通过 CPU 特性检测如cpuid指令动态选择使用哪个后端。这是工业级库如 OpenSSL的常见做法。3. 模式并行化对于 CBC 模式由于后一个块的加密依赖于前一个块的密文天然是串行的。但像 CTR计数器模式或 ECB 模式不推荐用于一般加密各个数据块的加密是独立的可以轻松利用多线程并行处理充分利用多核 CPU。4.2 RSA 性能优化实战RSA 的瓶颈几乎全在大数运算上尤其是模幂运算。1. 大数乘法的算法优化基础的“学校乘法”复杂度是 O(n^2)。对于大数我们必须使用更高级的算法Karatsuba 算法将复杂度降至约 O(n^1.585)。当数字大到一定程度例如超过几百个机器字时这是一个很好的选择。Toom-Cook 算法更通用的分治算法对于更大的数比 Karatsuba 更快。FFT快速傅里叶变换乘法对于非常大的数数千位以上这是最快的算法但实现极其复杂。通常像 GMP 这样的库才会使用。在我们的实现中可以先实现学校乘法作为基准然后为BigInt实现一个 Karatsuba 乘法并在内部根据操作数大小自动切换算法。2. 模运算优化蒙哥马利约减RSA 的核心运算是a^b mod n。其中的模运算mod n如果使用普通的除法取余代价非常高。蒙哥马利约减是一种巧妙的方法它将模运算转化为在另一种“蒙哥马利域”下的乘法运算避免了昂贵的除法。它特别适合用于连续进行模乘的场景比如平方-乘算法。实现蒙哥马利约减是提升 RSA 性能的关键一步。3. 选择公钥指数 e65537如前所述e65537 (0x10001) 只有两个二进制位是 1这使得在快速模幂运算中需要进行的“乘”操作非常少极大地加快了公钥加密和验签的速度。这是行业标准做法。4. 使用中国剩余定理CRT加速解密这是对私钥操作解密和签名的“杀手级”优化。回忆一下私钥包含 (n, d)而 n p * q。CRT 允许我们利用 p 和 q在密钥生成时知道且必须保存来加速计算。 原理是分别计算m_p c^(d mod (p-1)) mod pm_q c^(d mod (q-1)) mod q 然后再组合得到最终的 m mod n。 由于 p 和 q 的大小只有 n 的一半所以模幂运算的速度会快大约 4 倍。这是生产环境 RSA 实现的标配。BigInt RSA::decryptCRT(const PrivateKey privKey, const BigInt c) { // 假设 privKey 中还保存了 p, q, dP d mod (p-1), dQ d mod (q-1), qInv q^(-1) mod p BigInt m_p BigInt::modPow(c % privKey.p, privKey.dP, privKey.p); BigInt m_q BigInt::modPow(c % privKey.q, privKey.dQ, privKey.q); BigInt h (privKey.qInv * (m_p - m_q)) % privKey.p; if (h.isNegative()) h h privKey.p; BigInt m m_q privKey.q * h; return m % privKey.n; }5. 完整源码关键环节与集成测试限于篇幅无法贴出全部上万行代码但我会勾勒出最关键、最容易出错的环节并提供完整的测试思路。5.1 AES 核心S-Box 与轮密钥扩展S-Box 是一个 256 字节的常量数组其生成基于有限域 GF(2^8) 上的乘法逆元和仿射变换。你必须确保使用的 S-Box 是完全正确的。// aes.cpp 中的一部分 const uint8_t AES::sbox[256] { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, // ... 剩余 240 个值必须精确无误 };轮密钥扩展函数keyExpansion需要正确处理不同密钥长度并正确使用轮常量Rcon。一个细微的错误会导致所有加解密失败。5.2 RSA 核心大数除法与模逆实现大数除法BigInt::operator/和%是算法中最繁琐的部分。可以借鉴 Knuth 的“算法 D”。而模逆运算用于计算私钥指数 d通常使用扩展欧几里得算法。BigInt BigInt::modInverse(const BigInt a, const BigInt m) { // 扩展欧几里得算法实现 BigInt t 0, newt 1; BigInt r m, newr a; while (!newr.isZero()) { BigInt quotient r / newr; // 更新 (t, newt) BigInt tmpT newt; newt t - quotient * newt; t tmpT; // 更新 (r, newr) BigInt tmpR newr; newr r - quotient * newr; r tmpR; } if (r 1) return BigInt(0); // 不可逆 if (t 0) t t m; return t; }5.3 集成测试如何验证你的实现是对的自己实现的加密库最怕的就是“闭门造车”加解密自己跑得通但和标准不兼容。必须进行严格的向量测试。使用官方测试向量NIST美国国家标准与技术研究院发布了 AES 和 RSA 的完整测试向量Test Vectors。这些是黄金标准。你需要编写测试代码用你的库去加密官方给出的明文和密钥看输出的密文是否一个字节都不差。对于 RSA也有标准的测试密钥和加解密数据对。与成熟库交叉验证用 OpenSSL 或 Crypto 库生成随机密钥和数据分别用你的库和成熟库进行加解密比较结果是否一致。可以从简单的短数据开始逐步增加到长数据、各种边缘情况。性能基准测试编写基准测试对比优化前后的性能对比你的实现与 OpenSSL 在相同任务下的性能差异。这能直观地反映优化效果。内存与线程安全测试检查是否有内存泄漏使用 Valgrind 等工具在多线程环境下调用加解密函数是否安全。6. 常见陷阱、安全考量与进阶方向即使算法实现正确在实际应用中仍有许多坑等着你。6.1 典型陷阱排查清单问题现象可能原因排查方法AES 加解密结果不对但有时又对工作模式如 CBC的初始化向量IV未正确处理或重用。确保每次加密使用随机且唯一的 IV并将 IV 与密文一起存储/传输。解密时使用相同的 IV。AES 解密最后出现乱码没有正确实现 PKCS#7 填充或解密后没有正确去除填充。仔细检查填充逻辑。加密时明文长度必须是块大小的整数倍不足则填充解密后根据最后一个字节的值移除填充。RSA 加密小数据正常大数据失败明文整数 m 未满足0 m n。或者填充后数据超限。RSA 加密前必须进行填充如 OAEP填充后的消息长度必须小于密钥长度单位字节。检查填充方案。RSA 解密速度极慢未使用中国剩余定理CRT优化。在密钥生成时保存 p, q, dp, dq, qinv并在解密时使用 CRT 加速函数。大数运算结果偶尔出错大整数类的进位或借位处理有边界错误。编写针对大数加减乘除的单元测试覆盖边界情况如全 0、全 F、进位溢出等。使用 Valgrind 检查内存访问。跨平台结果不一致字节序大端/小端问题。在将数据转换为整数或字节数组时未统一约定。在BigInt::toBytes和构造函数中明确指定并使用同一种字节序通常网络字节序即大端。6.2 安全考量比性能更重要密钥管理实现加密算法只是安全链条的一环。密钥如何生成、存储、分发、轮换是更关键的问题。绝对不要硬编码密钥在代码中。侧信道攻击你的实现是否在时间或功耗上泄露了信息例如RSA 的平方-乘算法如果根据密钥位的分支判断不同就可能被计时攻击破解。需要使用常数时间的实现。随机数质量AES 的 IV、RSA 的质数 p 和 q都需要密码学安全的随机数。不要用rand()要用/dev/urandomLinux或BCryptGenRandomWindows等。填充预言攻击旧的 RSA PKCS#1 v1.5 填充方案存在漏洞。在可能的情况下优先使用 OAEP最优非对称加密填充用于加密使用 PSS 用于签名。6.3 进阶方向当你掌握了基础实现和优化后可以探索以下方向支持更多模式实现 GCM伽罗瓦/计数器模式以同时提供加密和认证。椭圆曲线加密ECC用比 RSA 短得多的密钥实现相同或更高的安全性性能也更好。尝试实现 ECDSA 签名或 ECIES 加密。硬件加速除了 AES-NI探索利用 Intel SHA Extensions 或者 GPU 进行并行哈希/加密计算。形式化验证对于核心算法使用形式化验证工具来证明其正确性这是最高级别的质量保证。从头实现 AES 和 RSA 是一次对计算机科学和数学的深度巡礼。它强迫你理解从布尔代数、有限域到数论的每一个细节。这个过程带来的不仅仅是两个可用的加密函数而是一种对复杂系统进行分解、实现和优化的底层能力。当你再次使用 OpenSSL 时你看到的将不再是一个神秘的魔法盒而是一系列精妙绝伦的、你可以理解甚至改进的齿轮的咬合。这份指南的源码和思路希望能成为你打开这扇大门的钥匙。记住在加密的世界里理解永远比调用更重要。