1. 项目概述从零手搓一个经典的对称加密算法最近在整理一些老项目的代码发现不少地方还在用DESData Encryption Standard做简单的数据混淆。虽然现在AES是主流但DES作为密码学史上的一个里程碑其精巧的Feistel网络结构和完整的加解密流程依然是理解现代对称加密算法的绝佳入门案例。用Python从头实现一遍DES不仅能让你彻底搞懂分组加密、轮函数、密钥编排这些核心概念更能让你在面试或技术讨论时对“为什么DES被淘汰”、“AES做了哪些改进”这类问题有底气十足的回答。这篇文章我就带你用纯Python不依赖pycryptodome这样的重型库一步步把DES算法“造”出来。我们会深入每一行代码背后的数学原理和设计意图并分享我在实现过程中踩过的坑和调试技巧。无论你是刚学完Python语法想找个有挑战性的练手项目还是对密码学感兴趣但被各种数学符号劝退的开发者这篇详解都能让你有所收获。2. DES算法核心原理与设计思路拆解在动手写代码之前我们必须先吃透DES算法的“设计图纸”。DES是一种分组密码每次处理64位8字节的明文数据块输出64位的密文。它的密钥长度是64位但实际有效的只有56位另外8位是奇偶校验位。整个加密过程就像一条精密的流水线包含初始置换、16轮Feistel迭代、最终置换三大阶段。而其中最核心、最精妙的部分就是这16轮迭代所采用的Feistel网络结构。2.1 为什么是Feistel网络一个天才的设计Feistel结构是DES乃至许多经典密码如Blowfish的基石。它的核心思想在于将输入块分成左右两半L0, R0在每一轮中右半部分Ri-1经过一个轮函数F处理后与左半部分Li-1进行异或操作得到新的右半部分Ri而旧的右半部分则直接成为新的左半部分Li。用公式表示就是 Li Ri-1 Ri Li-1 ⊕ F(Ri-1, Ki)这里Ki是每一轮的子密钥。这个结构的绝妙之处在于无论轮函数F本身设计得多么简单甚至不可逆整个加解密过程都是可逆的。解密时只需要使用相同的子密钥但按相反的顺序应用即可。这极大地降低了对轮函数设计的要求让我们可以把精力集中在让F函数足够“混乱”和“扩散”上。在DES中这个F函数包含了扩展置换、与子密钥异或、S盒替换和P盒置换四个步骤是算法安全性的核心。注意理解Feistel网络的可逆性是关键。你可以自己用纸笔推导一下假设已知Li和Ri以及Ki如何还原出Li-1和Ri-1。这个练习能让你真正理解加解密为何对称。2.2 密钥编排算法从一把主钥匙生成16把子钥匙DES的加密强度很大程度上依赖于每一轮使用的子密钥Ki都不同。密钥编排算法Key Schedule就是负责从初始的64位密钥实际56位生成这16个48位子密钥的流程。这个过程同样充满了置换和移位操作。首先一个称为“置换选择1”PC-1的固定表格会丢弃8个校验位并将剩下的56位打乱重排分成两个28位的半密钥C0和D0。接下来在每一轮iC(i-1)和D(i-1)会根据一个预定义的左循环移位表对于第1, 2, 9, 16轮移1位其他轮移2位进行移位得到Ci和Di。最后将Ci和Di合并后的56位通过另一个“置换选择2”PC-2的表格压缩并重排成48位的子密钥Ki。这个设计确保了子密钥之间具有高度的非线性关系即使攻击者破解了某一轮的子密钥也很难反推出主密钥或其他轮的子密钥。在代码实现时我们需要预先定义好PC-1、PC-2以及循环移位表这三个核心表格。3. 核心模块的Python实现与细节剖析理论清晰后我们就可以开始搭建DES的各个功能模块了。我将按照数据处理的流程逐一实现置换、S盒、密钥生成等核心函数。这里会用到大量的位操作Python的整数类型和位运算符,|,^,,,~将是我们的主要工具。3.1 位操作工具函数一切的基础由于DES算法处处都在处理特定位的提取、设置和置换我们先封装几个底层工具函数会让后续代码清晰很多。def bit_string_to_int(bit_string): 将二进制字符串如1101转换为整数 return int(bit_string, 2) def int_to_bit_string(n, length64): 将整数转换为指定位长度的二进制字符串左侧补零 return format(n, f0{length}b) def get_bit(block, pos, block_size64): 从数据块整数表示中提取特定位。 DES中位序通常从1开始最左位为第1位且是Big-Endian。 pos: 位的位置1-indexed # 将目标位移到最低位然后与1进行与操作 if pos 1 or pos block_size: raise ValueError(fPosition {pos} out of range for block size {block_size}) # 注意我们假设block的二进制形式最高位MSB对应位置1 return (block (block_size - pos)) 1 def set_bit(block, pos, value, block_size64): 将数据块整数表示的特定位设置为0或1 if value not in (0, 1): raise ValueError(Bit value must be 0 or 1) current_bit get_bit(block, pos, block_size) if current_bit value: return block # 通过异或翻转特定位 mask 1 (block_size - pos) return block ^ mask def permute(block, permutation_table, input_size): 通用的置换函数。 block: 输入数据块整数表示 permutation_table: 置换表列表元素为位置序号通常1-indexed input_size: 输入块的位数 返回置换后的新整数。 result 0 for i, pos in enumerate(permutation_table): bit get_bit(block, pos, input_size) if bit: # 将提取到的位设置到结果的新位置上新位置是i1 result set_bit(result, i1, 1, len(permutation_table)) return resultpermute函数是DES的瑞士军刀初始置换、扩展置换、P盒置换、各种密钥置换都是靠它完成的。理解它的关键在于置换表permutation_table中的每个数字指定了输出结果的第i位应该从输入数据的第几位取。比如[58, 50, 42, ...]这个初始置换表意思是结果的第一位是输入的第58位第二位是输入的第50位以此类推。3.2 实现S盒替换非线性混淆的核心S盒Substitution-box是DES算法中唯一的非线性部件也是其安全性的关键。它将6位输入映射为4位输出。DES共有8个不同的S盒S1到S8每个都是一个4行16列的查找表。S盒的查表规则有点特别6位输入中首尾两位bits 1 6组成一个2位数决定行号0-3中间四位bits 2-5组成一个4位数决定列号0-15。然后从表中对应位置取出一个0-15的数字转换为4位二进制输出。# DES的8个S盒定义 (来自FIPS PUB 46-3标准) S_BOXES [ # 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 此处省略实际代码需完整列出 ] def s_box_substitution(input_48bit): 对48位输入进行S盒替换输出32位 output_32bit 0 # 将48位分成8组每组6位 for i in range(8): # 提取6位 start_bit 48 - i * 6 # 注意我们的位序是从左到右MSB到LSB six_bits 0 for j in range(6): six_bits (six_bits 1) | get_bit(input_48bit, start_bit - j, 48) # 计算行号和列号 row ((six_bits 5) 0b10) | ((six_bits 0) 0b01) # 取首尾位 col (six_bits 1) 0b1111 # 取中间4位 # 查表 s_box_value S_BOXES[i][row][col] # 将4位输出拼接到结果中 output_32bit (output_32bit 4) | s_box_value return output_32bit实操心得S盒的实现最容易出错的地方就是位提取的顺序。一定要对照标准文档确认你的位编号方式是MSB为1还是LSB为1和分组顺序是从左到右还是从右到左。我建议在函数开头用一组固定的测试数据如全零输入验证输出是否符合标准测试向量。3.3 密钥生成器按轮次生产子密钥密钥生成器是一个有状态的类它接收初始密钥然后能按需生成每一轮需要的子密钥。class KeyScheduler: # PC-1置换表56位输出忽略校验位 PC1 [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, ... # 省略完整表格 ] # PC-2置换表48位输出 PC2 [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, ... # 省略完整表格 ] # 每轮左循环移位位数 SHIFT_SCHEDULE [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1] def __init__(self, initial_key): # 初始密钥是64位整数包含8位校验位 self.initial_key initial_key # 应用PC-1置换得到56位有效密钥并分成C0和D0 key_56 permute(initial_key, self.PC1, 64) self.C key_56 28 # 高28位 self.D key_56 ((1 28) - 1) # 低28位 self.round 0 def get_next_key(self): 生成下一轮的子密钥48位 if self.round 16: raise StopIteration(All 16 round keys have been generated.) # 根据轮次移位 shift self.SHIFT_SCHEDULE[self.round] self.C ((self.C shift) | (self.C (28 - shift))) ((1 28) - 1) self.D ((self.D shift) | (self.D (28 - shift))) ((1 28) - 1) # 合并C和D然后应用PC-2置换 combined_56 (self.C 28) | self.D round_key permute(combined_56, self.PC2, 56) self.round 1 return round_key def reset(self): 重置调度器状态用于解密或重新加密 self.__init__(self.initial_key)密钥生成器的逻辑是线性的但要注意循环移位的实现。((self.C shift) | (self.C (28 - shift))) ((1 28) - 1)这行代码实现了28位整数内的循环左移 ((1 28) - 1)是为了确保结果仍然在28位以内丢弃可能溢出的高位。4. 完整的DES加解密流程实现有了所有零部件现在我们可以组装完整的DES引擎了。我们将实现一个DES类它提供encrypt_block和decrypt_block方法用于处理单个64位数据块。4.1 定义所有置换表首先我们需要把所有标准置换表定义成常量。这是最枯燥但必须精确无误的一步。这里以初始置换IP和其逆置换IP^-1为例# 初始置换IP表 IP [58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7] # 最终置换IP逆置换 IP_INV [40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25] # 扩展置换E表将32位扩展到48位 E [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, ... # 省略完整表格 ] # P盒置换表 P [16, 7, 20, 21, 29, 12, 28, 17, ... # 省略完整表格 ]4.2 轮函数F的实现轮函数F是每一轮加密的核心它接收32位的右半部分R和48位的子密钥K输出32位。def f_function(r_block_32bit, round_key_48bit): DES的轮函数F # 1. 扩展置换32位 - 48位 expanded permute(r_block_32bit, E, 32) # 2. 与轮密钥异或 xored expanded ^ round_key_48bit # 3. S盒替换48位 - 32位 substituted s_box_substitution(xored) # 4. P盒置换 output permute(substituted, P, 32) return output4.3 加密单块的核心逻辑现在我们可以实现加密一个64位数据块的主函数了。class DES: def __init__(self, key): # 密钥可以是64位整数也可以是8字节的字节串 if isinstance(key, bytes): if len(key) ! 8: raise ValueError(DES key must be 8 bytes (64 bits)) self.key int.from_bytes(key, big) # 大端序 else: self.key key # 假设是整数 self.key_scheduler KeyScheduler(self.key) def encrypt_block(self, plaintext_block): 加密一个64位的明文块返回64位密文块整数 if isinstance(plaintext_block, bytes): if len(plaintext_block) ! 8: raise ValueError(Plaintext block must be 8 bytes) block int.from_bytes(plaintext_block, big) else: block plaintext_block # 1. 初始置换IP block permute(block, IP, 64) # 2. 拆分成左右两部分各32位 L block 32 R block 0xFFFFFFFF # 3. 16轮Feistel迭代 self.key_scheduler.reset() # 确保从第一轮密钥开始 for i in range(16): round_key self.key_scheduler.get_next_key() new_R L ^ f_function(R, round_key) L R R new_R # 4. 最后一轮结束后交换左右DES标准要求 # 注意第16轮后不交换但我们的循环结束时已经交换了所以需要再换回来 # 实际上在循环中第16次迭代后L保存的是R15R保存的是L15^F(R15,K16) # 根据标准最终组合前需要交换。所以 final_block (R 32) | L # 5. 最终置换IP^-1 ciphertext permute(final_block, IP_INV, 64) return ciphertext def decrypt_block(self, ciphertext_block): 解密一个64位的密文块返回64位明文块整数 # 解密过程与加密几乎相同唯一区别是子密钥的使用顺序相反 if isinstance(ciphertext_block, bytes): if len(ciphertext_block) ! 8: raise ValueError(Ciphertext block must be 8 bytes) block int.from_bytes(ciphertext_block, big) else: block ciphertext_block # 初始置换 block permute(block, IP, 64) L block 32 R block 0xFFFFFFFF # 关键预先生成所有轮密钥并逆序使用 self.key_scheduler.reset() round_keys [self.key_scheduler.get_next_key() for _ in range(16)] for i in range(15, -1, -1): # 从第16轮密钥反向到第1轮 round_key round_keys[i] new_R L ^ f_function(R, round_key) L R R new_R final_block (R 32) | L plaintext permute(final_block, IP_INV, 64) return plaintext注意事项加解密的对称性体现在子密钥的使用顺序上。加密时按K1, K2, ..., K16顺序使用解密时则按K16, K15, ..., K1顺序使用。Feistel网络的结构保证了其他部分完全一致。很多初学者在这里搞错导致解密失败。一个简单的记忆方法是加密和解密函数可以共用绝大部分代码只需在迭代循环中反转round_keys列表的顺序即可。4.4 工作模式与填充让DES处理任意长度数据上面的encrypt_block和decrypt_block只能处理恰好64位8字节的数据。现实中我们需要加密任意长度的消息。这就需要引入工作模式和填充方案。最经典的模式是ECB电子密码本和CBC密码块链接。ECB模式最简单就是将消息分割成多个8字节块分别加密然后拼接。但其安全性较差因为相同的明文块会产生相同的密文块容易暴露模式。CBC模式则更安全。它在加密前先将当前明文块与前一个密文块或一个初始向量IV进行异或然后再加密。这样即使明文相同加密结果也会因上下文不同而不同。我们以CBC模式为例实现一个完整的加密/解密函数并处理PKCS#7填充。def des_cbc_encrypt(key, iv, plaintext_bytes): 使用DES-CBC模式加密任意长度的字节数据。 key: 8字节的密钥 iv: 8字节的初始化向量 plaintext_bytes: 明文字节串 返回密文字节串。 des DES(key) block_size 8 # 1. PKCS#7填充 padding_len block_size - (len(plaintext_bytes) % block_size) if padding_len 0: padding_len block_size # 如果长度正好是块大小的倍数则填充一个完整的块 padded_plaintext plaintext_bytes bytes([padding_len] * padding_len) # 2. 分割成块 cipher_blocks [] previous_block iv # 第一个块的前一个“密文块”是IV for i in range(0, len(padded_plaintext), block_size): block padded_plaintext[i:iblock_size] # 与前一密文块或IV异或 block_int int.from_bytes(block, big) xor_int block_int ^ int.from_bytes(previous_block, big) # 加密 encrypted_int des.encrypt_block(xor_int) encrypted_block encrypted_int.to_bytes(block_size, big) cipher_blocks.append(encrypted_block) previous_block encrypted_block return b.join(cipher_blocks) def des_cbc_decrypt(key, iv, ciphertext_bytes): 使用DES-CBC模式解密 des DES(key) block_size 8 if len(ciphertext_bytes) % block_size ! 0: raise ValueError(Ciphertext length must be a multiple of block size) plaintext_blocks [] previous_cipher_block iv for i in range(0, len(ciphertext_bytes), block_size): cipher_block ciphertext_bytes[i:iblock_size] cipher_int int.from_bytes(cipher_block, big) # 解密 decrypted_int des.decrypt_block(cipher_int) # 与前一密文块异或注意是前一个密文块不是解密后的块 xor_int decrypted_int ^ int.from_bytes(previous_cipher_block, big) plaintext_block xor_int.to_bytes(block_size, big) plaintext_blocks.append(plaintext_block) previous_cipher_block cipher_block # 更新前一个密文块 # 去除PKCS#7填充 padded_data b.join(plaintext_blocks) padding_len padded_data[-1] # 简单的填充验证 if padding_len 1 or padding_len block_size: raise ValueError(Invalid padding) if padded_data[-padding_len:] ! bytes([padding_len]) * padding_len: raise ValueError(Invalid padding) return padded_data[:-padding_len]实操心得CBC模式的安全性依赖于IV初始化向量。IV必须每次加密都随机生成并且不需要保密但绝不能重复使用同一个IV和密钥对不同的消息进行加密。你可以将IV和密文一起存储或传输。解密时使用相同的IV即可。另外填充错误是常见的攻击向量在解密后一定要严格验证填充的合法性但要注意避免“填充预言攻击”即不要因为填充错误就立即返回错误信息最好统一处理。5. 测试、验证与性能优化实现完成后我们必须进行严格的测试确保算法正确无误。同时纯Python实现的DES性能肯定无法与C语言库相比但我们可以探讨一些优化思路。5.1 使用标准测试向量验证NIST美国国家标准与技术研究院等机构提供了标准的DES测试向量用于验证实现的正确性。最经典的测试是使用全零的密钥和全零的明文。def test_des_known_answers(): 使用已知答案测试DES实现 # 测试1: 全零密钥和全零明文 key bytes([0x00] * 8) plaintext bytes([0x00] * 8) des DES(key) ciphertext_int des.encrypt_block(plaintext) ciphertext_hex format(ciphertext_int, 016x) print(f全零测试 - 密文: {ciphertext_hex}) # 已知标准密文应该是: 0x8CA64DE9C1B123A5 (具体值需查标准文档) # assert ciphertext_hex 8ca64de9c1b123a5 # 解密验证 decrypted_int des.decrypt_block(ciphertext_int) decrypted_bytes decrypted_int.to_bytes(8, big) assert decrypted_bytes plaintext, 解密结果与原始明文不符 print(加解密自洽测试通过。) # 测试2: 使用一个随机密钥和明文 import os test_key os.urandom(8) test_plain os.urandom(8) des2 DES(test_key) ct des2.encrypt_block(test_plain) pt des2.decrypt_block(ct) assert pt.to_bytes(8, big) test_plain print(随机数据测试通过。) # 测试3: CBC模式测试 iv os.urandom(8) message bThis is a test message for DES-CBC! ciphertext des_cbc_encrypt(test_key, iv, message) decrypted des_cbc_decrypt(test_key, iv, ciphertext) assert decrypted message print(CBC模式测试通过。) print(所有基础测试通过)如果测试通过说明你的DES核心实现基本正确。你还可以在网上找到更全面的测试向量集进行更彻底的验证。5.2 常见问题与调试技巧实录在实现DES的过程中我遇到了不少坑这里总结一下帮你快速排雷位序问题这是最大的坑。标准文档中的位编号通常是从左到右MSB为1而我们在代码中用整数表示时二进制字符串的最左边是最高位。我的get_bit和set_bit函数就是按照这个约定实现的。务必确保你所有的置换表、S盒查表逻辑都遵循同一套位序约定。一个有效的调试方法是单独测试初始置换IP输入一个只有第1位是1的明文即0x8000000000000000看输出是否等于置换表第一个元素58所指示的位置为1。S盒输出错误S盒的输入是6位输出是4位。确保你正确地从6位中提取了行和列。行号由第1位和第6位组成注意是1-indexed列号由中间4位组成。可以写一个单元测试对每个S盒遍历所有64种输入将输出与标准值对比。密钥生成错误子密钥不对会导致整个加解密失败。检查PC-1和PC-2置换表是否准确特别是循环移位表SHIFT_SCHEDULE。可以打印出每一轮生成的子密钥十六进制与已知正确的密钥调度结果对比。Feistel网络最后一轮交换DES标准规定在16轮迭代后左右两部分需要交换一次然后再进行最终置换。但在具体实现时由于循环结构你可能在循环结束时已经得到了交换后的结果。仔细跟踪你代码中L和R的赋值逻辑确保最终组合成64位块时顺序是正确的。一个简单的检查方法是加密一个块后立即解密看是否能还原。性能瓶颈纯Python的位操作和循环比较慢。对于需要高性能的场景这个实现仅适用于学习和验证。如果必须用Python且需要一定性能可以考虑以下优化预计算对于固定的置换操作可以预先计算好查找表Look-up Table。例如可以将8位输入的256种可能经过P盒置换后的结果全部算好存起来这样运行时只需要一次查表而不是32次位操作。这对S盒同样有效但S盒本身已经是查表了。使用位切片技术将64位数据用Python的int表示利用整数运算的并行性。我们现在的permute函数是逐位操作的可以优化为同时处理多个位。但这会大大增加代码复杂度。使用numpy或ctypes调用C库对于生产环境最好的选择是使用pycryptodome或cryptography这些封装了C语言实现的库。我们的手搓实现核心价值在于理解原理。5.3 DES的安全性讨论与当代应用最后我们必须清醒地认识到DES在今天已经不再安全。其56位的密钥长度在现代计算能力特别是GPU和专用硬件面前可以在合理时间内被暴力破解。1999年电子前沿基金会EFF制造的“Deep Crack”机器就在不到3天的时间里破解了一个DES密钥。因此绝对不要在任何需要真正安全性的新系统中使用DES。那为什么我们还要学习它呢原因有三教学价值DES结构清晰是理解分组密码、Feistel网络、混淆与扩散等概念的完美教材。历史兼容一些遗留系统可能还在使用DES或它的变体3DESTriple DES。3DES通过使用两个或三个密钥进行三次加密将有效密钥长度提升到112或168位安全性有所提高但速度慢了三倍且仍有理论上的攻击可能。理解演进学习DES的弱点密钥短、S盒设计有争议能更好地理解其继任者AESAdvanced Encryption Standard在设计上的改进如更大的分组128位、更长的密钥128/192/256位、以及基于置换-置换网络SPN的更简洁结构。如果你需要在Python项目中使用加密请使用现代算法如AES通过pycryptodome库。但通过亲手实现DES你获得的底层洞察力是单纯调用Cipher_AES.new(key, AES.MODE_CBC)所无法比拟的。下次当你配置TLS或者讨论加密算法时你就能清晰地知道数据在底层经历了怎样一场精心设计的“混乱之旅”。