从零实现DES加密算法：Feistel网络与C语言实战详解

2026/6/22 8:15:40

1. 项目概述：为什么我们今天还要聊DES？

如果你刚接触密码学，或者正在寻找一个经典的对称加密算法来练手，DES（Data Encryption Standard）绝对是一个绕不开的名字。尽管在今天的应用场景中，它早已因为56位的密钥长度被AES（Advanced Encryption Standard）等更安全的算法取代，但理解DES，就像是学习计算机科学时去理解一台老式计算机的架构——它奠定了现代分组密码的许多基础思想和结构。我当年啃下DES的实现后，再去看AES、SM4这些现代算法，感觉就像打通了任督二脉，很多复杂的概念（比如Feistel网络、S盒）一下子就清晰了。

这个项目，就是带你从零开始，彻底搞懂DES加密算法的原理，并用C语言亲手实现它。这不仅仅是为了完成一个“第1关：对称加密算法”的作业，更是为了让你掌握密码学核心的“积木块”。你会发现，网络上很多关于DES的代码要么过于简略，要么存在理解偏差。我将结合自己踩过的坑，把每个步骤掰开揉碎，从密钥生成到最后的加解密流程，让你不仅能写出代码，更能明白每一行代码背后的数学和逻辑。准备好了吗？我们开始这场从原理到实现的深度之旅。

2. DES算法核心原理深度拆解

DES是一种分组密码算法，它采用64位为一组进行加密和解密，密钥长度名义上是64位，但实际有效的只有56位，另外8位用于奇偶校验。它的核心设计思想是混淆（Confusion）和扩散（Diffusion），通过重复的替代和置换操作，使得密文与明文、密文与密钥之间的关系变得极其复杂。

2.1 核心结构：Feistel网络

DES的整体结构采用了经典的Feistel网络（Feistel Cipher）。这是理解DES乃至许多其他对称加密算法的钥匙。它的精妙之处在于，加密和解密可以使用完全相同的结构，只是子密钥的使用顺序相反。这极大地简化了硬件和软件的实现。

Feistel网络将输入的64位明文分成左右两半，各32位，记为L0和R0。然后进行16轮完全相同的操作。在每一轮i（i从1到16）中：

右半部分Ri-1直接成为下一轮的左半部分Li。
左半部分Li-1与一个轮函数F作用于Ri-1和本轮子密钥Ki的结果进行异或（XOR），得到下一轮的右半部分Ri。

用公式表示就是： Li = Ri-1 Ri = Li-1 XOR F(Ri-1, Ki)

经过16轮后，得到L16和R16，注意，最后还需要进行一次左右交换，输出（R16, L16）作为最终的64位密文。

注意：这个“最后交换”的步骤非常关键，它保证了Feistel网络的对称性，使得解密过程只需倒序使用子密钥即可，而无需设计一个逆函数F^-1。这是Feistel结构最伟大的贡献之一。

2.2 心脏部件：轮函数F(R, K)详解

轮函数F是DES安全性的核心，它接受32位的右半部分输入R和48位的子密钥K，输出一个32位的结果。它包含了DES几乎所有的精华操作：扩展置换、密钥混合、S盒替代和P盒置换。

第一步：扩展置换（E盒）将32位的输入R通过一个固定的扩展置换表（E盒）扩展为48位。这个操作有两个目的：一是让数据长度与48位的子密钥匹配以便进行异或；二是实现“扩散”，让R中的一位能影响下一轮两个S盒的输入。

第二步：与子密钥异或（Key Mixing）将扩展后的48位结果与本轮48位的子密钥Ki进行按位异或（XOR）操作。这是将密钥引入加密过程的关键步骤。

第三步：S盒替代（Substitution）这是DES中唯一的非线性操作，是“混淆”的主要来源。将上一步得到的48位数据分成8组，每组6位，分别送入8个不同的S盒（Substitution Box）。每个S盒是一个4行16列的查找表，它将6位输入映射为4位输出。具体规则是：6位输入的头尾两位组成一个2位数，决定行号（0-3）；中间4位组成一个4位数，决定列号（0-15）。根据行列坐标，在S盒表中查找对应的4位输出值。8个S盒总共输出32位。

实操心得：S盒的实现是DES代码中最容易出错的地方之一。一定要仔细核对S盒的表格数据（标准中有明确定义），并确保你的索引计算是正确的。一个常见的错误是将二进制索引直接当作十进制使用，或者行、列索引计算反了。

第四步：P盒置换（Permutation）将S盒输出的32位结果，通过一个固定的置换表（P盒）进行重新排列。这是进一步的“扩散”，使得S盒的输出位被散布到下一轮的不同位置。

至此，轮函数F执行完毕，输出32位结果，用于与左半部分进行异或。

2.3 密钥调度算法：从56位到16个子密钥

DES的初始密钥是64位，但每8位中的最后1位是奇偶校验位，实际参与运算的只有56位。密钥调度算法负责将这56位有效密钥生成16轮所需的16个48位子密钥。

流程如下：

置换选择1（PC-1）：对64位输入密钥进行置换，并去掉8个校验位，得到56位的密钥。这56位被分成两个28位的半密钥C0和D0。
循环左移：对于每一轮i，C(i-1)和D(i-1)分别进行循环左移。左移的位数根据轮数而定：第1、2、9、16轮左移1位，其余轮次左移2位。得到Ci和Di。
置换选择2（PC-2）：将Ci和Di合并成的56位中间密钥，通过PC-2置换，压缩并重排，输出48位的本轮子密钥Ki。

正是由于每轮循环左移的位数不同，才产生了16个不同的子密钥。解密时，只需将子密钥的使用顺序倒置（K16, K15, ..., K1）即可。

3. DES加密/解密的完整流程实现

理解了核心原理，我们就可以用代码来构建整个DES引擎了。下面我将以C语言为例，分模块实现。为了清晰，我们会将各个置换表、S盒定义为常量数组。

3.1 数据结构与常量定义

首先，我们需要定义所有DES标准中规定的固定表格。这里只列出关键部分示例，完整表格需参考标准文档。

// 示例：IP初始置换表（64位输入，64位输出） const int IP_Table[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, // ... 省略后续56个元素 }; // 示例：第一个S盒 S1 const int S1_Box[4][16] = { {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} }; // 其他S盒（S2-S8）、扩展置换表E、P盒置换表、逆初始置换表IP^-1、 // 密钥置换PC-1、PC-2表、循环左移位数表等都需要完整定义。

为了方便操作，我们通常将64位数据用两个32位无符号整数（uint32_t）来表示高低位，或者用一个64位无符号整数（uint64_t）来表示。这里我们使用uint64_t来简化位操作。

3.2 核心工具函数实现

我们需要一些基础的位操作函数，例如置换函数和循环左移函数。

#include <stdint.h> /** * 通用置换函数 * @param src 源数据（64位或更少） * @param table 置换表指针 * @param table_size 置换表大小（也是输出位数） * @return 置换后的结果 */ uint64_t permute(uint64_t src, const int *table, int table_size) { uint64_t result = 0; for (int i = 0; i < table_size; i++) { int src_pos = table[i] - 1; // 表格中位置是从1开始计数，转换为从0开始 uint64_t bit = (src >> (64 - src_pos)) & 0x01; // 取出src中对应位 result = (result << 1) | bit; // 将bit放到result的最低位 } // 注意：如果table_size不是64，result的高位是0。对于输出小于64位的置换（如PC-2），需要额外处理。 // 更严谨的做法是让result的类型和移位位数随table_size动态变化，这里为简化使用uint64_t。 return result; } /** * 对28位数据进行循环左移 * @param data 28位数据（存放在uint32_t的低28位） * @param shift 左移位数（1或2） * @return 循环左移后的28位数据 */ uint32_t leftRotate28(uint32_t data, int shift) { // 确保只操作低28位 uint32_t mask = 0x0FFFFFFF; data &= mask; return ((data << shift) | (data >> (28 - shift))) & mask; }

3.3 密钥生成模块实现

这是DES的第一步，也是独立于加解密过程可以预先计算的。

// 假设已经定义了 PC1_Table[56], PC2_Table[48], shift_schedule[16] void generate_subkeys(uint64_t initial_key, uint64_t subkeys[16]) { uint64_t permuted_key_56; uint32_t C, D; int i; // 1. 通过PC-1置换，得到56位密钥（实际存储在64位变量的低56位） permuted_key_56 = permute(initial_key, PC1_Table, 56); // 2. 分割成C0和D0（各28位） C = (uint32_t)((permuted_key_56 >> 28) & 0x0FFFFFFF); // 取高28位 D = (uint32_t)(permuted_key_56 & 0x0FFFFFFF); // 取低28位 // 3. 生成16轮子密钥 for (i = 0; i < 16; i++) { // 3.1 循环左移 C = leftRotate28(C, shift_schedule[i]); D = leftRotate28(D, shift_schedule[i]); // 3.2 合并C和D（56位） uint64_t combined_CD = ((uint64_t)C << 28) | (uint64_t)D; // 3.3 通过PC-2置换，压缩成48位子密钥 subkeys[i] = permute(combined_CD, PC2_Table, 48); } }

3.4 轮函数F的实现

这是DES算法最核心的函数。

// 假设已经定义了 E_Table[48], P_Table[32], 以及8个S盒 S1_Box 到 S8_Box uint32_t F_function(uint32_t R, uint64_t K) { uint64_t expanded_R; uint64_t mixed; uint32_t output = 0; int i; // 1. 扩展置换：32位 -> 48位 expanded_R = permute((uint64_t)R, E_Table, 48); // 注意类型转换 // 2. 与子密钥异或 mixed = expanded_R ^ K; // 都是48位数据（存在于64位变量的低48位） // 3. S盒替代：48位 -> 32位 // 将48位mixed分成8个6位组 for (i = 0; i < 8; i++) { int shift = 42 - i * 6; // 获取第i个6位组（从最高位开始） uint8_t six_bits = (mixed >> shift) & 0x3F; // 取出6位 // 计算S盒的行和列索引 int row = ((six_bits & 0x20) >> 4) | (six_bits & 0x01); // 首位和末位组成行 int col = (six_bits >> 1) & 0x0F; // 中间4位组成列 uint8_t four_bits; // 根据i选择对应的S盒 switch (i) { case 0: four_bits = S1_Box[row][col]; break; case 1: four_bits = S2_Box[row][col]; break; // ... 补充 case 2 到 case 7 case 7: four_bits = S8_Box[row][col]; break; default: four_bits = 0; break; } // 将4位输出合并到最终的32位结果中 output = (output << 4) | four_bits; } // 4. P盒置换 output = (uint32_t)permute((uint64_t)output, P_Table, 32); return output; }

3.5 加密主函数实现

现在，我们可以组装完整的加密流程了。

uint64_t des_encrypt(uint64_t plaintext, uint64_t initial_key) { uint64_t subkeys[16]; uint64_t permuted_text; uint32_t L, R, temp; int i; // 0. 生成16轮子密钥 generate_subkeys(initial_key, subkeys); // 1. 初始置换IP permuted_text = permute(plaintext, IP_Table, 64); // 2. 分割成L0和R0 L = (uint32_t)(permuted_text >> 32); // 高32位 R = (uint32_t)(permuted_text & 0xFFFFFFFF); // 低32位 // 3. 16轮Feistel迭代 for (i = 0; i < 16; i++) { temp = R; // R = L XOR F(R, K) R = L ^ F_function(R, subkeys[i]); L = temp; // L = 旧的R } // 4. 最后交换（第16轮后本应是L16,R16，交换后为R16,L16） // 注意：因为最后一轮结束后我们已经做了 L=R_old, R=L_old^F(...) // 所以此时 (L, R) 实际是 (R16, L16)？ 不，需要仔细分析。 // 标准的Feistel最后一轮后，数据是 (L16, R16)，其中： // L16 = R15 // R16 = L15 XOR F(R15, K16) // 然后需要交换左右两部分，得到 (R16, L16) 作为预输出。 // 在我们的循环中，循环结束后，L保存的是R15，R保存的是L15^F(R15,K16)。 // 所以我们需要交换L和R。 temp = L; L = R; R = temp; // 此时，(L, R) 就是 (R16, L16) // 5. 合并为64位预输出 uint64_t pre_output = ((uint64_t)L << 32) | (uint64_t)R; // 6. 逆初始置换IP^-1，得到最终密文 uint64_t ciphertext = permute(pre_output, IP_Inverse_Table, 64); return ciphertext; }

3.6 解密函数实现

得益于Feistel网络的完美对称性，解密函数与加密函数几乎完全相同，唯一的区别是子密钥的使用顺序是反的。

uint64_t des_decrypt(uint64_t ciphertext, uint64_t initial_key) { uint64_t subkeys[16]; uint64_t permuted_text; uint32_t L, R, temp; int i; // 生成子密钥（和加密一样） generate_subkeys(initial_key, subkeys); // 初始置换IP permuted_text = permute(ciphertext, IP_Table, 64); L = (uint32_t)(permuted_text >> 32); R = (uint32_t)(permuted_text & 0xFFFFFFFF); // 16轮Feistel迭代，但子密钥逆序使用（K16, K15, ..., K1） for (i = 15; i >= 0; i--) { temp = R; R = L ^ F_function(R, subkeys[i]); // 使用 subkeys[i]， i从15递减到0 L = temp; } // 最后交换 temp = L; L = R; R = temp; // 合并并逆初始置换 uint64_t pre_output = ((uint64_t)L << 32) | (uint64_t)R; uint64_t plaintext = permute(pre_output, IP_Inverse_Table, 64); return plaintext; }

4. 从DES到现代算法的思考与常见问题

实现一个可工作的DES是学习的第一步。但在实际应用和深入理解密码学的道路上，你会遇到更多问题。

4.1 工作模式：如何加密超过64位的数据？

我们实现的DES是基础的电码本（ECB, Electronic Codebook）模式。它有一个致命缺点：相同的明文块会加密成相同的密文块。这对于有规律的数据（如图像）来说，会留下明显的纹理特征，安全性很低。

因此，实际应用中必须使用更安全的工作模式，例如：

CBC（Cipher Block Chaining）：每个明文块先与前一个密文块异或，再进行加密。需要一个初始化向量IV。这是过去非常常用的模式。
CTR（Counter）：将计数器加密后与明文异或。它可以并行计算，非常适合现代处理器。

实操心得：永远不要在生产环境中使用ECB模式。即使你只是内部测试，也养成使用CBC或CTR等模式的好习惯。IV（初始化向量）必须是随机且不可预测的，但不需要保密。

4.2 DES的安全性为何不足？3DES又是什么？

DES被淘汰的根本原因是其56位的密钥长度。在算力飞速发展的今天，暴力破解56位密钥（2^56种可能）对于大型组织或国家力量已非难事。为此，催生了3DES（Triple DES）。

3DES并非设计一个全新算法，而是用DES进行三次加密，以增加有效密钥长度。常见的有两种方式：

EDE（Encrypt-Decrypt-Encrypt）：Ciphertext = E(K3, D(K2, E(K1, Plaintext)))。如果K1=K2=K3，则退化为单DES，提供了向后兼容性。
EEE（Encrypt-Encrypt-Encrypt）：使用三个不同的密钥。

3DES的有效密钥长度可达112位（当K1和K3独立，K2用于解密时），安全性大大增强。但它也有明显缺点：速度慢（是DES的三倍），且分组长度仍是64位，在某些场景下可能受到“生日攻击”的影响。因此，它最终也被更高效、更安全的AES所取代。

4.3 常见实现陷阱与调试技巧

在编写和调试DES代码时，我踩过不少坑，这里分享几个关键点：

位序问题：DES标准文档中，数据位通常是从左到右、从1开始编号（MSB first）。而在我们的代码和计算机内存中，字节序和位序可能不同。确保你的置换函数permute正确地处理了这种映射。上面的示例代码采用了一种常见方法：假设输入src的最高位（第63位）对应位置1。这需要与你定义置换表时的预期保持一致。
S盒索引计算：这是最高频的错误点。务必反复确认行、列索引的计算公式。row = ((six_bits >> 4) & 0x02) | (six_bits & 0x01)和row = ((six_bits & 0x20) >> 4) | (six_bits & 0x01)是等价的，都是取首尾位。col = (six_bits >> 1) & 0x0F是取中间4位。
测试向量：一定要使用官方或广泛认可的测试向量来验证你的实现。例如，可以使用NIST（美国国家标准与技术研究院）发布的已知答案测试（KAT）向量。输入特定的明文和密钥，看输出的密文是否完全一致。这是验证算法实现正确性的唯一可靠方法。
密钥生成验证：单独测试你的generate_subkeys函数。找一组测试密钥，手动计算或对照可靠实现，检查每一轮生成的子密钥是否正确。密钥错了，整个加解密过程就全错了。
最后交换与合并：在16轮迭代结束后，一定要进行左右交换，再进行逆初始置换。这个步骤很容易被忽略或写错，导致解密失败。

4.4 DES在当今的定位与学习价值

今天，DES本身已不再适用于需要安全保护的场合。但它的学习价值丝毫没有减弱：

密码学入门基石：它完整包含了分组密码的所有基本概念：置换、替代、混淆、扩散、Feistel结构、密钥调度、工作模式。
理解现代算法的基础：学习AES时，你会对比其SPN结构（Substitution-Permutation Network）与Feistel网络的区别；学习SM4时，你会发现其整体结构与DES的相似与不同。有了DES的底子，这些理解起来会快得多。
实现能力的锻炼：手动实现DES是一次对位操作、数据结构和算法逻辑的绝佳训练。

当你成功运行自己的DES程序，并完成一个完整的加密-解密循环后，那种对密码学从抽象到具体的掌控感，是只看论文和公式无法获得的。这或许就是这个经典项目历经数十年，依然值得每一位对安全感兴趣的程序员去亲手实现的原因。它不仅仅是一个算法，更是一把打开密码学大门的钥匙。