C++实现DES加密算法：从Feistel结构到分组密码实践

1. 项目概述：从理论到实践的DES加密之旅

最近在整理一些旧项目，翻到了当年在学校信息安全课上做的DES加密算法实现。说实话，现在AES已经是主流，但在理解对称加密的底层逻辑上，DES依然是一个绝佳的“教学标本”。它结构清晰，包含了分组加密几乎所有的核心概念：置换、迭代、S盒、密钥调度。用C++亲手实现一遍，远比只看书或者调用现成的库要来得深刻。这个项目适合所有对密码学感兴趣，或者想深入理解C++在底层数据处理（比如位操作、数组管理）上如何发挥威力的朋友。无论你是正在学习《密码学》课程的学生，还是希望夯实C++基本功、挑战一下复杂逻辑实现的开发者，跟着这个思路走一遍，收获的绝不仅仅是一个能加密解密的程序，更是一套处理复杂问题的思维方法和扎实的编程功底。

2. DES算法核心原理快速解析

在动手写代码之前，我们必须先搞清楚DES到底在干什么。DES是一种分组密码，每次处理64位（8字节）的明文数据块，输出64位的密文，使用的密钥长度是56位（外加8位奇偶校验位，通常我们说64位密钥）。它的核心思想是“混淆”和“扩散”，通过多轮复杂的置换和替代操作，让明文和密钥之间的关系变得极其复杂。

2.1 核心流程：Feistel网络结构

DES采用的是经典的Feistel网络结构。这是它最巧妙的设计之一，也是我们实现时需要牢牢把握的框架。Feistel结构的核心优势在于，加密和解密过程可以使用几乎相同的逻辑，只是子密钥的使用顺序相反，这极大地简化了我们的代码设计。

具体来说，对于每一轮加密：

1. 将64位的输入数据分成左右两半，各32位，记为L和R。
2. 本轮的输出左半部分L’直接等于上一轮的右半部分R。
3. 本轮的输出右半部分R’等于上一轮的左半部分L与一个轮函数F(R, K)的结果进行异或（XOR）。这里的K是本轮的子密钥。

用公式表示就是：L’ = RR’ = L XOR F(R, K)

看到这里你可能会想，解密时怎么办？神奇之处就在于，由于XOR运算的特性（A XOR B XOR B = A），解密过程只需要将密文作为输入，并逆序使用子密钥K，套用完全相同的Feistel结构即可还原出明文。这意味着我们只需要实现一个F函数和一个密钥调度算法，加密和解密的主循环结构可以复用。

2.2 轮函数F：算法的“心脏”

轮函数F是DES安全性的关键，它接受32位的右半部分R和48位的子密钥K，输出一个32位的结果。其内部步骤是标准且固定的：

1. 扩展置换（E-box）：将32位的R扩展为48位。这不是简单填充，而是通过重复某些位来实现的。目的是为了与48位的子密钥进行异或，同时让输出的一位能影响到下一轮多个S盒的输入，实现“扩散”。
2. 与子密钥异或：将扩展后的48位结果与48位的子密钥K进行按位异或。
3. S盒替代（S-box）：这是DES中唯一的非线性变换，是算法保密性的核心。将异或后的48位数据分成8组，每组6位，送入8个不同的S盒。每个S盒是一个固定的4行16列的查找表，它接收6位输入，输出4位。这一步将48位数据压缩回32位，并且提供了至关重要的非线性特性。
4. P盒置换（P-box）：将S盒输出的32位数据进行一次固定的位置置换，进一步打乱数据位之间的关系。

2.3 密钥调度：从主密钥到轮密钥

DES的加密强度很大程度上依赖于每一轮使用的子密钥都不同。密钥调度算法负责从56位有效密钥（64位密钥去掉奇偶校验位）生成16个48位的子密钥。

1. 置换选择1（PC-1）：首先，64位初始密钥经过PC-1置换，去掉8位奇偶校验位，并对剩下的56位进行位置重排，生成C0和D0各28位。
2. 循环左移：在每一轮，C和D分别进行循环左移，移位数根据轮数而定（第1、2、9、16轮左移1位，其余轮左移2位）。
3. 置换选择2（PC-2）：将移位后的C和D合并成56位，再经过PC-2置换，压缩并重排，最终输出48位的本轮子密钥。

注意：所有置换表（IP, IP-1, E, P, PC-1, PC-2）和S盒都是公开的、固定的。我们的实现就是将这些表格“翻译”成C++中的数组，并严格按照其定义进行位操作。

3. C++实现的核心数据结构与设计思路

用C++实现DES，本质上是在用程序语言精确地描述上述的数学和逻辑过程。选择合适的数据结构来“表示”位和数据块，是决定代码是否清晰、高效的关键。

3.1 数据表示：为何选择std::bitset

在C++中，处理位级操作有几种选择：unsigned long long配合位运算符、std::vector<bool>、或者std::bitset。对于DES这种固定位长的算法，我强烈推荐使用std::bitset<N>。

• 类型安全与长度固定：bitset<64>明确表示一个64位的数据块，bitset<48>表示48位子密钥。编译器会在编译期确保长度，避免了运行时越界的风险，意图表达非常清晰。
• 丰富的位操作：它重载了所有的位运算符（&,|,^,~,<<,>>），并且提供test(),set(),reset(),flip()等成员函数，操作比特位比直接操作整数更直观。
• 易于调试：你可以直接cout一个bitset对象，它会以“00101101...”这样的二进制字符串形式输出，在调试跟踪数据流时无比方便。

当然，你也可以使用uint64_t，通过掩码和移位来操作特定位，性能可能稍好，但代码的可读性和可维护性会大打折扣。对于学习和理解算法而言，清晰比那一点性能更重要。

3.2 核心类设计

一个良好的面向对象设计能让代码结构清晰。我建议设计一个DES类，将加密解密的核心逻辑封装起来。

class DES { public: DES(const std::string& key); // 构造函数，接受字符串密钥 std::string encrypt(const std::string& plaintext); std::string decrypt(const std::string& ciphertext); private: std::bitset<64> key; // 存储初始密钥（64位，含校验） std::vector<std::bitset<48>> roundKeys; // 存储16轮子密钥 // 内部核心过程 void generateRoundKeys(); // 密钥调度 std::bitset<32> feistel(const std::bitset<32>& R, const std::bitset<48>& K); // 轮函数F std::bitset<64> processBlock(const std::bitset<64>& block, bool isEncrypt); // 处理单个64位块 // 置换函数（工具函数） template<size_t IN, size_t OUT> std::bitset<OUT> permute(const std::bitset<IN>& input, const int table[OUT]); };

设计思路解析：

• 构造函数：接受一个字符串密钥。我们需要将其转换为bitset<64>。如果密钥长度不足8字节，需要填充；如果超过，可以截取或使用哈希衍生。这里简单处理，可以取前8字节。
• generateRoundKeys：这是一个关键私有函数，在构造函数或首次加密时被调用，生成16轮子密钥并存入roundKeys向量，避免每次加密重复计算。
• processBlock：加密和解密的公共部分。参数isEncrypt用于控制是使用roundKeys[0]到roundKeys[15]（加密），还是roundKeys[15]到roundKeys[0]（解密）。这完美体现了Feistel网络的优势。
• 模板化置换函数：这是一个技巧。IP、E、P、PC-1、PC-2置换都是同样的操作：根据一张表，将输入特定位映射到输出特定位。我们可以写一个模板函数，通过IN和OUT模板参数适应不同大小的输入输出，table参数传入对应的置换表数组。这能极大减少重复代码。

3.3 置换表与S盒的代码化

这是最“体力”但也必须最细心的一部分。你需要将标准文档中的置换表和S盒逐行翻译成C++的二维数组。例如，初始置换IP表：

const int IP_Table[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, // ... 其余56个数字 };

注意，表格中的数字通常是从1开始计数的，表示输入数据块的第N位。而std::bitset的索引是从0开始的（最右边是第0位）。这是一个极易出错的点！你需要在置换函数中做减1转换，或者直接定义表格时就用0起始的索引。我强烈建议采用后者，即根据算法描述先减1再填入数组，让代码逻辑更直接。

S盒的定义更复杂一些，它是一个8x4x16的三维数组（8个盒子，每个盒子4行16列）。

const int S_Box[8][4][16] = { // S1 { {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7}, {0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8}, {4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0}, {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13} }, // S2 ... S8 以此类推 };

使用S盒时，6位输入的第一位和最后一位组成行号（0-3），中间4位组成列号（0-15），然后查找对应的4位输出值。

4. 分步实现与关键代码剖析

有了清晰的设计和数据结构，我们就可以开始动手实现了。整个过程就像搭积木，从最小的置换函数开始，逐步构建轮函数，最后完成整个加密流程。

4.1 基础工具：通用置换函数的实现

这是所有置换操作的基础。我们利用C++模板，写一个函数处理所有情况。

template<size_t IN, size_t OUT> std::bitset<OUT> DES::permute(const std::bitset<IN>& input, const int table[OUT]) { std::bitset<OUT> result; for (size_t i = 0; i < OUT; ++i) { // table[i] 表示输出位i的值来自输入位的第 table[i] 位。 // 假设我们的table已经是以0为起始索引定义的。 size_t originalPos = table[i]; if (originalPos < IN && input.test(originalPos)) { result.set(i); } } return result; }

这个函数遍历输出位的每一个位置i，查看置换表table[i]指定的输入位是否为1，如果是，则将输出位i设为1。test()和set()是bitset的成员函数，分别用于测试和设置特定位。

4.2 密钥调度算法的实现

在构造函数中调用generateRoundKeys()。

void DES::generateRoundKeys() { roundKeys.clear(); // 1. PC-1置换，56位有效密钥 std::bitset<56> pc1Key = permute<64, 56>(key, PC1_Table); // 分割成C0和D0，各28位 std::bitset<28> C = (pc1Key >> 28).to_ulong(); // 取高28位 std::bitset<28> D = (pc1Key.to_ulong() & 0x0FFFFFFF); // 取低28位，通过掩码 // 每轮的左移位数表 const int shiftTable[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}; for (int i = 0; i < 16; ++i) { // 2. 循环左移 C = (C << shiftTable[i]) | (C >> (28 - shiftTable[i])); D = (D << shiftTable[i]) | (D >> (28 - shiftTable[i])); // 3. 合并并PC-2置换，生成48位子密钥 std::bitset<56> combinedKey; // 将C（28位）和D（28位）合并回56位。需要一些位操作技巧。 // 一种方法是先转成unsigned long long再拼接，更清晰的方法是逐位设置。 // 这里为了清晰，使用一个辅助函数或直接操作。 // 假设我们有一个合并函数 mergeBitsets std::bitset<56> CD = mergeBitsets(C, D); // C放在高28位，D放在低28位 std::bitset<48> roundKey = permute<56, 48>(CD, PC2_Table); roundKeys.push_back(roundKey); } }

实操心得：bitset的<<和>>运算符是逻辑移位，对于固定位长的bitset，超出部分会被丢弃，另一侧补0。这正是我们想要的循环左移效果（先左移，再或上右移的“溢出”部分）。但要注意，bitset的to_ulong()在值超出unsigned long范围时会抛出异常，在处理大bitset时要小心。对于28位的C和D，其值肯定在unsigned long范围内，所以是安全的。

4.3 轮函数F的实现

这是算法的灵魂所在，需要严格按照扩展、异或、S盒、P盒的顺序实现。

std::bitset<32> DES::feistel(const std::bitset<32>& R, const std::bitset<48>& K) { // 1. 扩展置换 E: 32 -> 48 std::bitset<48> expandedR = permute<32, 48>(R, E_Table); // 2. 与子密钥异或 std::bitset<48> xored = expandedR ^ K; // 3. S盒替代: 48 -> 32 std::bitset<32> sBoxOutput; int sBoxPos = 0; for (int i = 0; i < 8; ++i) { // 取出6位 int block = (xored >> (42 - i*6)).to_ulong() & 0x3F; // 每次取6位，注意bitset的索引方向 // 计算行号和列号 int row = ((block & 0x20) >> 4) | (block & 0x01); // 第一位和最后一位 int col = (block >> 1) & 0x0F; // 中间四位 // 查找S盒 int sBoxValue = S_Box[i][row][col]; // 将4位输出拼接到结果中 sBoxOutput <<= 4; // 左移4位为新结果腾出空间 sBoxOutput |= std::bitset<32>(sBoxValue); } // 注意：上面的拼接逻辑需要根据bitset的位序调整。更稳妥的方法是逐位设置。 // 另一种清晰的做法是：先计算好sBoxValue，然后从第 (31 - i*4) 位开始设置4位。 // 4. P盒置换 std::bitset<32> result = permute<32, 32>(sBoxOutput, P_Table); return result; }

关键细节与避坑：S盒处理是最大的难点。一是位序问题，bitset的operator>>是向低位移动，而我们在概念上通常把最高位写在左边。在取6位块和拼接4位输出时，必须非常清楚当前数据的位序。我建议在关键步骤插入调试输出，打印出bitset的二进制字符串，对照算法手册逐步验证。二是S盒的行列计算，一定要确认算法描述中是如何用6位输入定位的，不同的资料可能索引方式略有不同。

4.4 主流程：单个数据块的加密/解密

processBlock函数串联起所有步骤。

std::bitset<64> DES::processBlock(const std::bitset<64>& block, bool isEncrypt) { // 1. 初始置换IP std::bitset<64> permutedBlock = permute<64, 64>(block, IP_Table); // 2. 分割成L0和R0 std::bitset<32> L = (permutedBlock >> 32).to_ulong(); std::bitset<32> R = permutedBlock.to_ulong() & 0xFFFFFFFF; // 3. 16轮Feistel迭代 for (int i = 0; i < 16; ++i) { std::bitset<32> oldL = L; L = R; // 决定使用第几轮子密钥 int keyIndex = isEncrypt ? i : 15 - i; R = oldL ^ feistel(R, roundKeys[keyIndex]); } // 4. 最后交换（第16轮后不交换，但算法描述中通常先交换再合并，这里在循环中已经完成交换） // 合并 R16 和 L16 (注意：经过16轮后，L和R已经是R16和L16) std::bitset<64> combinedBlock; // 将R（作为高32位）和L（作为低32位）合并。需要位操作。 // 例如：combinedBlock = (std::bitset<64>(R.to_ulong()) << 32) | std::bitset<64>(L.to_ulong()); // 5. 末置换IP-1 std::bitset<64> outputBlock = permute<64, 64>(combinedBlock, IP1_Table); return outputBlock; }

4.5 外围工作：模式与填充

一个完整的加密程序不能只处理恰好64位（8字节）的数据。我们需要处理任意长度的明文，并选择合适的分组工作模式（如ECB、CBC）和填充方式（如PKCS#7）。

• ECB模式（电子密码本）：最简单，每个块独立加密。缺点是相同的明文块会生成相同的密文块，模式化明显，不安全。实现简单，直接分割、填充、加密每个块即可。
• CBC模式（密码分组链接）：更安全。每个明文块在加密前，先与前一个密文块（或初始向量IV）进行异或。这破坏了模式的重复性。解密时，需要先解密，再与上一个密文块异或。强烈建议在实际学习项目中至少实现CBC模式，它能让你理解初始化向量（IV）的重要性。
• 填充：如果数据不是8字节的整数倍，需要在末尾填充。PKCS#7是常用标准，如果缺n个字节，就填充n个值为n的字节。例如，数据差3字节，则填充0x03 0x03 0x03。

实现一个带CBC模式和PKCS#7填充的encrypt函数：

std::string DES::encrypt(const std::string& plaintext) { // 1. PKCS#7填充 size_t padLen = 8 - (plaintext.length() % 8); if (padLen == 0) padLen = 8; // 如果长度正好是8的倍数，额外填充一个完整块 std::string paddedText = plaintext + std::string(padLen, static_cast<char>(padLen)); // 2. 生成随机初始化向量IV（这里用固定值示例，实际应用必须用密码学安全的随机数） std::bitset<64> iv(0x0123456789ABCDEFULL); std::string ciphertext; std::bitset<64> previousBlock = iv; // 3. CBC模式加密 for (size_t i = 0; i < paddedText.length(); i += 8) { // 将8字节字符串转换为64位bitset uint64_t blockData = 0; memcpy(&blockData, paddedText.data() + i, 8); std::bitset<64> plainBlock(blockData); // CBC: 明文块与上一个密文块（或IV）异或 plainBlock ^= previousBlock; // 加密 std::bitset<64> cipherBlock = processBlock(plainBlock, true); // 将密文块转换为字符串并追加 uint64_t cipherValue = cipherBlock.to_ullong(); ciphertext.append(reinterpret_cast<char*>(&cipherValue), 8); // 更新“上一个密文块” previousBlock = cipherBlock; } // 4. 返回密文（通常是二进制数据，可以Base64编码后返回字符串） return ciphertext; // 注意这是二进制字符串 }

解密函数是逆过程，需要注意填充的移除。

5. 测试、验证与性能考量

实现完成后，必须进行严格的测试。

5.1 使用标准测试向量验证

NIST或其他标准机构提供了DES的已知答案测试（KAT）向量。找一组标准的（密钥，明文，密文）三元组，用你的程序加密明文，看结果是否与标准密文一致；再用你的程序解密密文，看是否能还原明文。这是验证算法实现正确性的黄金标准。

void testDES() { DES des("01234567"); // 8字节密钥 std::string plain = "helloDES"; std::string cipher = des.encrypt(plain); std::string decrypted = des.decrypt(cipher); std::cout << "Plain: " << plain << std::endl; std::cout << "Cipher (hex): "; for (char c : cipher) printf("%02X ", (unsigned char)c); std::cout << std::endl; std::cout << "Decrypted: " << decrypted << std::endl; // 对比decrypted和plain，并去除填充后是否一致 }

5.2 常见问题与调试技巧

1. 结果完全不对：首先检查所有置换表、S盒的数据是否录入错误。这是最常见的问题。建议写一个小程序，用已知的输入（比如全0或全1数据）手动计算一轮，并打印出每一步的中间结果（二进制形式），与标准计算过程对比。
2. 只有最后几位不对：很可能是位序（Endian）或拼接顺序问题。在合并左右半部分、处理S盒输入输出时，要特别注意最高位（MSB）和最低位（LSB）在bitset和你的思维模型中的对应关系。bitset的operator<<是向高位移动，输出时bitset的字符串表示是高位在左。
3. 加密解密不互逆：检查Feistel轮函数在加密和解密时子密钥的使用顺序是否正确。加密用K0~K15，解密必须用K15~K0。检查初始置换IP和末置换IP-1是否互为逆过程。
4. 多块数据时出错：检查填充逻辑是否正确，特别是在解密后移除填充时，是否正确地读取了最后一个字节的值并验证了填充的合法性。检查CBC模式中IV的处理，加解密双方必须使用相同的IV。

5.3 性能与优化思考

我们使用std::bitset的实现重在清晰和教育意义，但性能并非最优。bitset的位操作是安全的，但可能不是最快的。生产级别的C++实现可能会：

• 使用uint64_t和uint32_t等基本类型，通过掩码和移位直接操作。
• 将置换操作实现为查表法（Look-up Table），尤其是将多个步骤（如E盒+S盒+P盒）合并成一张大表，用空间换时间。这是许多加密库的优化手段。
• 使用编译器内部函数（Intrinsics）或SIMD指令进行并行优化。
• 但无论如何优化，DES本身56位密钥在当今计算能力下已不再安全，绝对不应用于实际的敏感数据加密。这个项目的价值在于学习原理。

5.4 从DES到3DES和AES的延伸

理解了DES，再去看3DES（Triple DES）就非常容易了。它本质上就是用两个或三个密钥对数据块进行三次DES加密（加密-解密-加密），以此来增加有效密钥长度，对抗暴力破解。你可以尝试修改你的DES类，轻松封装出一个3DES类。

而AES（Rijndael算法）虽然不再是Feistel结构，而是SPN（代换-置换网络）结构，但其设计思想——字节替代（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）、轮密钥加（AddRoundKey）——与DES的混淆、扩散一脉相承。实现过DES后，你会对状态（State）、轮密钥扩展等概念有更直观的理解，再学习AES会事半功倍。

最后，我个人在实现这个项目时最大的体会是，密码学算法的实现就像在代码中构建一座精密的机械钟表。每一个置换表、每一次移位、每一个S盒查找都必须分毫不差。调试过程虽然繁琐，但当你的程序第一次成功通过标准测试向量时，那种透过代码窥见数学之美和设计者智慧的感觉，是无与伦比的。它锻炼的不仅仅是编程能力，更是极端严谨的逻辑思维和对细节的掌控力。如果你在实现过程中卡住了，不妨放下代码，拿起笔和纸，手动演算一小轮，很多时候，答案就在那一步步的推算之中。