C语言实现DES算法：从Feistel网络到S盒的完整加密引擎构建

1. 项目概述：从零构建DES算法的核心引擎

如果你正在学习密码学，或者想深入理解对称加密的底层运作，那么动手用C语言实现一遍DES（Data Encryption Standard）算法，绝对是一个里程碑式的项目。DES虽然现在已不再是高安全场景的首选，但它作为现代分组密码的基石，其精巧的Feistel网络结构、复杂的S盒置换思想，至今仍在AES等算法中闪耀。网上开源实现很多，但“看懂”和“亲手实现”之间隔着巨大的鸿沟。自己写一遍，你会对位操作、数据分块、密钥调度这些抽象概念有肌肉记忆般的理解。

这个项目适合有一定C语言基础（熟悉指针、位运算、内存操作）的开发者，尤其是对系统安全、嵌入式开发或密码学原理感兴趣的朋友。最终，你将获得一个完全由自己掌控的、可以加密解密任意文本或文件的DES核心引擎。这不仅是一个练习，更是一个可以嵌入到更大项目（如自定义文件加密工具、通信协议模拟）中的可靠模块。接下来，我会带你从原理到代码，一步步拆解，并分享那些只有踩过坑才知道的实操细节。

2. DES算法原理与C语言实现的核心思路

2.1 DES算法骨架：Feistel网络的精妙之处

DES是一种分组密码，一次处理64位（8字节）的明文数据块，使用56位有效密钥（外加8位奇偶校验位，共64位）。其核心结构是Feistel网络，这种结构有一个绝佳的特性：加密和解密可以使用几乎相同的代码流程，只需调整子密钥的使用顺序即可。这大大降低了实现的复杂度。

整个DES过程分为三个大阶段：

1. 初始置换（IP）：对输入的64位明文进行一个固定的位置重排。
2. 16轮Feistel迭代：这是算法的核心。每一轮中，数据被分成左右两半（各32位），右半部分经过一个复杂的F函数处理后，与左半部分进行异或操作，然后左右交换，进入下一轮。
3. 末置换（IP⁻¹）：进行初始置换的逆操作，得到最终的64位密文。

F函数是DES的灵魂，它包含了扩展置换（E）、与子密钥异或、S盒替换（S-Box）和P盒置换（P）四个步骤。其中，S盒是唯一的非线性部件，是DES安全性的关键。

在C语言中实现，我们需要用unsigned char数组或unsigned long long类型来表示这些位数据。考虑到可读性和教学目的，我们将主要使用unsigned char数组来模拟位操作，这样每一步的变换都能看得清清楚楚。

2.2 C语言实现的策略选择：清晰优先于极致优化

面对DES，有两种实现策略：一是追求极致的运行效率，使用查表法和大量的位运算宏；二是追求极致的清晰度，每一步变换都通过函数明确实现，便于理解和调试。对于学习项目，我强烈建议选择后者。

我们的核心思路是：

• 数据表示：使用unsigned char data[8]表示一个64位分组。每个元素存储一个字节（8位）。
• 位操作：我们将实现一系列辅助函数，如get_bit,set_bit，用于对data数组进行按位读写。虽然效率不如直接整型移位，但逻辑无比清晰。
• 模块化：将IP置换、PC-1置换、循环左移、PC-2置换、F函数等每一个步骤都封装成独立的函数。
• 密钥调度：提前计算好16轮的子密钥并存储起来，供加解密时使用。

这样做的优点是，你可以在任何一步打印出数据的二进制形式，亲眼看到比特是如何流动和变化的，这对于调试和理解算法至关重要。等完全吃透后，你可以再尝试用unsigned long long和查表法进行优化，那是另一个层次的挑战。

3. 核心模块的C语言实现与细节剖析

3.1 基础位操作工具函数的实现

任何对数据的置换、选择操作，归根结底都是对特定位的读取和设置。我们先打造好这些“螺丝刀”和“扳手”。

/** * 从数据数组中获取特定位的值 * @param data 数据数组（每字节8位） * @param pos 位的位置（从1开始计数，范围1-64） * @return 该位的值（0或1） */ int get_bit(const unsigned char *data, int pos) { // 数组下标从0开始，位位置从1开始，需要转换 // 第pos位位于 data[(pos-1)/8] 字节的第 (pos-1)%8 位（从高位到低位） int byte_index = (pos - 1) / 8; int bit_index = 7 - ((pos - 1) % 8); // 假设我们按MSB（最高位）在先的顺序 return (data[byte_index] >> bit_index) & 0x01; } /** * 设置数据数组中特定位的值 * @param data 数据数组 * @param pos 位的位置（从1开始） * @param bit 要设置的值（0或1） */ void set_bit(unsigned char *data, int pos, int bit) { int byte_index = (pos - 1) / 8; int bit_index = 7 - ((pos - 1) % 8); if (bit) { data[byte_index] |= (1 << bit_index); // 置1 } else { data[byte_index] &= ~(1 << bit_index); // 置0 } }

注意：这里有一个关键约定：位序。我们约定pos=1表示整个64位数据的最高位（Most Significant Bit, MSB），pos=64表示最低位（LSB）。在data[0]中，最高位（bit 7）对应pos=1~8中的pos=1。这个约定必须贯穿整个项目，否则所有置换表都会错乱。这是第一个容易踩的坑。

3.2 置换与选择函数的通用实现

DES充满了各种置换表（IP, IP⁻¹, E, P, PC-1, PC-2）。我们可以写一个通用函数来处理它们。

/** * 通用置换函数 * @param src 源数据数组 * @param dst 目标数据数组 * @param table 置换表指针 * @param len 置换表的长度（也是输出数据的位数） */ void permute(const unsigned char *src, unsigned char *dst, const int *table, int len) { int i; // 先清空目标数组 for (i = 0; i < (len + 7) / 8; ++i) { dst[i] = 0; } // 根据置换表，从src取位，设置到dst的对应位置 for (i = 0; i < len; ++i) { int src_pos = table[i]; // 置换表的值表示源数据中的位位置（从1开始） int bit_value = get_bit(src, src_pos); set_bit(dst, i + 1, bit_value); // 目标位置从1顺序排列 } }

有了这个函数，我们只需要定义好各种置换表，就能轻松完成IP、E、P等操作。例如，初始置换IP表（64位到64位）：

// IP 初始置换表 (64位 -> 64位) static const int IP_Table[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, // ... 省略中间部分 15, 7, 62, 54, 46, 38, 30, 22 };

使用时：permute(plaintext, after_ip, IP_Table, 64);

3.3 密钥调度：生成16轮子密钥

密钥调度是DES独立于数据的一部分，它决定了加密和解密时子密钥的使用顺序不同。

步骤分解：

1. PC-1置换：64位初始密钥（含8位奇偶校验）经过PC-1置换，选出56位有效密钥，并分成C0（左28位）和D0（右28位）。
2. 循环左移：每一轮，C和D分别根据规则循环左移1位或2位。
3. PC-2置换：将移位后的C和D合并成56位，再经过PC-2置换压缩成48位的子密钥Kn。

C语言实现要点：

• 我们需要存储16个子密钥，可以定义一个二维数组unsigned char sub_keys[16][6]（因为48位=6字节）。
• 循环左移函数需要特别注意边界。因为C和D是28位，存储在unsigned char数组中，移位时需要跨字节操作。

/** * 对28位数据块进行循环左移 * @param data 4字节数组（实际只用28位） * @param n 左移的位数（1或2） */ void left_shift_28bit(unsigned char *data, int n) { // 将4字节数据看作一个28位的整体进行循环左移 unsigned int combined = (data[0] << 20) | (data[1] << 12) | (data[2] << 4) | (data[3] >> 4); combined = ((combined << n) | (combined >> (28 - n))) & 0x0FFFFFFF; // 循环左移并掩码 // 写回数组 data[0] = (combined >> 20) & 0xFF; data[1] = (combined >> 12) & 0xFF; data[2] = (combined >> 4) & 0xFF; data[3] = ((combined & 0x0F) << 4) | (data[3] & 0x0F); // 保留原第四字节的低4位 }

实操心得：密钥移位的规则是固定的：第1、2、9、16轮移1位，其他轮移2位。建议用一个数组int shift_schedule[16] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};来管理，这样代码更清晰，不易出错。

3.4 F函数的实现：DES的核心非线性变换

F函数接受32位的右半部分R和48位的子密钥K，输出32位结果。它是单轮加密中唯一产生混淆和扩散的部分。

四步流程：

1. 扩展置换E：将32位R扩展为48位。这是通过重复R的某些位实现的，查表即可。
2. 与子密钥异或：将扩展后的48位结果与48位子密钥K进行按位异或。
3. S盒替换：这是DES最精妙也是最容易出错的地方。将异或后的48位数据分成8组，每组6位。每组输入一个特定的S盒（共8个），输出4位。6位输入中，头尾两位组成行号（0-3），中间四位组成列号（0-15），查表得到一个0-15的数，转为4位二进制输出。这样，48位输入被压缩为32位输出。
4. P盒置换：对S盒输出的32位进行一个固定置换。

S盒实现的技巧：S盒是一个8x4x16的三维数组（8个盒子，每个4行16列）。在C中我们可以这样定义：

static 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}, // ... 省略其他行 }, // S2 ... S8 };

实现时，计算行号和列号的代码必须准确：

int sbox_input = ... // 6位输入 int row = ((sbox_input & 0x20) >> 4) | (sbox_input & 0x01); // 取第1和第6位 int col = (sbox_input & 0x1E) >> 1; // 取中间4位 int output = S_Box[box_index][row][col]; // 查表

踩坑警告：S盒的行列索引一定要按标准定义来。有些资料的行列顺序可能不同，务必使用权威的、经过验证的S盒数据。一个错误的S盒会导致整个加密结果面目全非，且极难调试。

4. 完整的加密解密流程串联与调试

4.1 加密主流程的代码组织

将上述模块组合起来，加密函数的伪代码逻辑如下：

void des_encrypt_block(const unsigned char *plaintext, const unsigned char *key, unsigned char *ciphertext) { unsigned char ip_out[8]; // IP置换后 unsigned char L[4], R[4]; // 左右各32位（4字节） unsigned char sub_keys[16][6]; // 16轮子密钥 // 1. 生成子密钥 generate_subkeys(key, sub_keys); // 2. 初始置换IP permute(plaintext, ip_out, IP_Table, 64); // 3. 分割成L0和R0 split_lr(ip_out, L, R); // 自定义函数，将64位分成两个32位 // 4. 16轮Feistel迭代 for (int i = 0; i < 16; i++) { unsigned char f_out[4]; // F函数输出 unsigned char temp_r[4]; // 保存旧的R memcpy(temp_r, R, 4); // R(i-1) 保存 // F(R[i-1], K[i]) f_function(R, sub_keys[i], f_out); // L[i] = R[i-1] // R[i] = L[i-1] XOR F(R[i-1], K[i]) xor_bytes(L, f_out, R, 4); // R = L XOR f_out memcpy(L, temp_r, 4); // L = 旧的R } // 5. 最后一轮后不交换，但我们的循环已经交换了，所以需要再交换回来？ // 注意：标准DES在16轮后需要交换L16和R16，但我们的循环内每次迭代结束时都交换了L和R。 // 因此，第16轮迭代后，L持有R16，R持有L16。我们需要在合并前交换回来。 unsigned char final_data[8]; combine_lr(R, L, final_data); // 注意参数顺序：先R后L // 6. 末置换IP⁻¹ permute(final_data, ciphertext, IP_Inverse_Table, 64); }

关键细节：Feistel网络在最后一轮后不交换左右部分。但在我们上面的循环实现中，每一轮结束都执行了L=旧R和R=L异或F，这实际上隐含了交换。所以循环结束后，L中保存的是R16，R中保存的是L16。我们需要在合并成64位进行末置换前，将它们交换回来（即合并成R16+L16）。这是实现中最容易混淆的逻辑点之一。很多自己实现的DES跑不通，问题就出在这里。

4.2 解密流程的实现

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

因此，我们可以复用des_encrypt_block函数的大部分代码，只需在调用f_function时传入相反顺序的子密钥即可。更优雅的做法是，在生成子密钥后，解密时直接反转子密钥数组的传入顺序。

void des_decrypt_block(const unsigned char *ciphertext, const unsigned char *key, unsigned char *plaintext) { // ... 前面的步骤（生成子密钥、IP置换、分割）与加密完全相同 ... generate_subkeys(key, sub_keys); // 16轮迭代，子密钥逆序使用 for (int i = 0; i < 16; i++) { // 关键在这里：使用 sub_keys[15 - i] f_function(R, sub_keys[15 - i], f_out); // ... 其余操作与加密相同 ... } // ... 后续合并和IP⁻¹置换与加密相同 ... }

4.3 工作模式与数据填充：让算法处理任意长度数据

基本的DES函数一次只处理一个64位（8字节）的分组。要加密一个文件或一段长文本，我们需要选择一种工作模式，并处理不是8字节整数倍的数据（填充）。

常用工作模式：

• ECB（电子密码本）：每个分组独立加密。简单，但相同的明文块会生成相同的密文块，安全性低，不建议用于加密有模式的数据（如图像）。
• CBC（密码分组链接）：每个明文块先与前一个密文块异或，再加密。需要一个初始化向量（IV）。安全性好，是常用的模式。

填充方案：最常用的是PKCS#7填充。如果数据长度是8的倍数，则额外填充一个完整的分组（8个0x08）。例如，一个13字节的数据，需要填充3个0x03使其达到16字节。

CBC模式加密流程（C语言伪代码）：

void des_cbc_encrypt(const unsigned char *input, int len, const unsigned char *key, const unsigned char *iv, unsigned char *output) { unsigned char block[8]; unsigned char prev_cipher[8]; // 上一个密文块，初始为IV memcpy(prev_cipher, iv, 8); for (int i = 0; i < len; i += 8) { // 1. 取出（或填充）一个明文块到`block` int bytes_to_copy = (len - i) > 8 ? 8 : (len - i); memcpy(block, input + i, bytes_to_copy); if (bytes_to_copy < 8) { // 执行PKCS#7填充 unsigned char pad_value = 8 - bytes_to_copy; memset(block + bytes_to_copy, pad_value, pad_value); } // 2. CBC模式：明文块与上一个密文块异或 xor_bytes(block, prev_cipher, block, 8); // 3. 加密当前块 des_encrypt_block(block, key, output + i); // 4. 更新上一个密文块为当前输出 memcpy(prev_cipher, output + i, 8); } }

注意事项：IV不需要保密，但必须是不可预测的（通常随机生成），且解密端必须使用相同的IV。对于文件加密，通常将IV保存在文件头部。

5. 调试技巧、常见问题与性能优化

5.1 如何验证你的DES实现是正确的？

这是项目中最关键的一步。不要等到整个程序写完才测试。

1. 使用标准测试向量：NIST或其他标准机构提供了DES的已知答案测试（KAT）向量。找一组标准的明文、密钥和密文（例如，全零明文和密钥），用你的程序加密，看结果是否匹配。这是最权威的验证。
2. 分模块测试：
   • 测试密钥调度：输入一个测试密钥，打印出每一轮的16个子密钥（十六进制），与已知正确的子密钥对比。
   • 测试单轮加密：手动计算或使用可靠工具得到第一轮加密后的L1和R1，与你的程序输出对比。
   • 测试F函数：给定特定的R和K，手动计算F函数的输出进行对比。
3. 加密-解密循环测试：对一个随机数据块，用随机密钥加密，再立即解密，看是否能还原出原始数据。这是最基本的自洽性测试。
4. 与现有库交叉验证：用OpenSSL的DES函数（虽然已废弃）加密同一段数据，对比结果。但要注意工作模式和填充方式必须完全一致。

5.2 常见问题排查清单

当你发现加密结果不对时，可以按这个清单从上到下检查：

5.3 从清晰版到优化版：性能提升技巧

当你有一个正确且清晰的实现后，可以考虑优化。优化主要围绕减少函数调用开销和利用处理器特性。

1. 查表法：将各种置换（如IP, E, P）的结果预先计算成表。例如，一个8位输入有256种可能，E扩展置换可以将结果预先算好存成uint64_t数组。这样，原本需要循环64次的permute操作，变成几次内存读取和位操作。
2. 整型运算：使用uint64_t来表示64位数据块，uint32_t表示32位半块。这样，很多位操作（如移位、异或）可以直接用C语言运算符完成，速度极快。
3. 合并操作：将F函数中的E扩展、与K异合、S盒查找、P置换合并成少数几个大的查表操作。这是专业加密库的做法，但会牺牲代码可读性。
4. 循环展开：手动展开16轮循环，消除循环判断的开销。
5. 内联函数：将所有小的工具函数（如get_bit）声明为static inline，鼓励编译器内联展开。

一个简单的优化示例——使用整型的Feistel轮函数：

uint32_t feistel(uint32_t r, uint64_t k) { // 1. E扩展：通过位操作和预计算掩码实现，非常快 uint64_t expanded = ((uint64_t)E_TABLE[(r >> 24) & 0xFF] << 40) | ((uint64_t)E_TABLE[(r >> 16) & 0xFF] << 32) | ... // 类似地处理其他字节 // 2. 异或子密钥 expanded ^= k; // 3. S盒查找（使用8个预计算的32位S盒表） uint32_t substituted = SBOX1[(expanded >> 42) & 0x3F] | SBOX2[(expanded >> 36) & 0x3F] | ... // 合并8个S盒输出 // 4. P置换（同样可以通过查表或位操作快速完成） return P_TABLE[substituted]; }

个人建议：除非有极高的性能需求（如实时加密大量数据），否则学习阶段清晰可读的代码价值远高于那一点性能提升。先保证正确，再考虑优化。优化后的代码往往像天书，难以调试和维护。

实现一个完整的DES算法，就像亲手搭建了一座精密的机械钟表。从比特的流动到S盒的非线性变换，每一个齿轮的咬合都必须分毫不差。这个过程会强迫你理解密码学教材上那些抽象的图表和公式。当你第一次用自己写的程序成功加密一段文字，又完美地将其解密回来时，那种成就感是无可替代的。这个项目带给你的，远不止一个加密工具，更是一种对复杂系统进行分解、实现和调试的底层能力。