从CTF实战出发：手把手教你用Python复现DES算法（附完整代码与NepCTF题解）
从CTF实战出发：手把手教你用Python复现DES算法（附完整代码与NepCTF题解）
在网络安全竞赛（CTF）中，密码学题目一直是考察选手基本功的重要环节。DES（Data Encryption Standard）作为经典的对称加密算法，虽然现在已被AES取代，但在CTF比赛中仍然频繁出现。本文将从实战角度出发，带你用Python一步步实现DES算法，并结合NepCTF中的simpleDES题目，讲解如何利用代码实现进行密钥逆推和明文恢复。
1. DES算法核心原理与Python实现
DES算法采用64位分组对数据进行加密，密钥长度为56位（实际输入64位，其中8位用于奇偶校验）。其核心流程包括初始置换、16轮Feistel网络结构、以及最终置换。
1.1 初始置换与Feistel结构
我们先来看DES的初始置换（IP）实现：
_IP = [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, 56, 48, 40, 32, 24, 16, 8, 0, 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6] def IP(plain: List[int]) -> List[int]: return [plain[x] for x in _IP]Feistel结构是DES的核心，其特点是加密和解密过程对称。每轮操作包括：
- 将64位数据分为左右两部分（L0和R0）
- 右半部分R0经过扩展置换（E盒）变为48位
- 与子密钥Ki进行异或
- 通过S盒替换压缩为32位
- 经过P盒置换
- 与左半部分L0异或得到新的R1
- 原始R0成为新的L1
1.2 密钥生成过程
DES的密钥生成过程同样重要，它决定了16轮加密使用的子密钥：
__pc1 = [56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3] def PC_1(key: List[int]) -> List[int]: return [key[x] for x in __pc1]密钥生成主要步骤：
- 通过PC-1置换选择56位有效密钥位
- 分成左右两部分C0和D0，各28位
- 根据轮数进行循环左移（1或2位）
- 通过PC-2置换选择48位作为子密钥
1.3 S盒与P盒实现
S盒是DES中唯一的非线性部件，6位输入通过查表转为4位输出：
def S_box(data: List[int]) -> List[int]: output = [] for i in range(0, 48, 6): row = data[i] * 2 + data[i + 5] col = reduce(add, [data[i + j] * (2 ** (4 - j)) for j in range(1, 5)]) output += [int(x) for x in format(__s_box[i // 6][row][col], '04b')] return outputP盒则是对S盒输出进行置换：
__p = [15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24] def P(data: List[int]) -> List[int]: return [data[x] for x in __p]2. 完整DES加密实现
结合上述组件，我们可以实现完整的DES加密流程：
def encrypt(plain: List[int], sub_keys: List[List[int]]) -> List[int]: plain = IP(plain) L, R = plain[:32], plain[32:] for i in range(16): prev_L = L L = R expanded_R = EP(R) xor_result = [a ^ b for a, b in zip(expanded_R, sub_keys[i])] substituted = S_box(xor_result) permuted = P(substituted) R = [a ^ b for a, b in zip(permuted, prev_L)] cipher = R + L cipher = [cipher[x] for x in [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, 32, 0, 40, 8, 48, 16, 56, 24]] return cipher3. NepCTF simpleDES题解实战
NepCTF中的simpleDES题目提供了一个很好的实战场景。题目给出了加密过程中的部分中间状态（C16和D16），我们需要利用这些信息恢复原始密钥。
3.1 子密钥逆推原理
DES的子密钥生成过程是可逆的。已知某一轮的子密钥，可以推导出原始密钥。具体步骤：
- 通过PC-2逆推得到C16和D16的56位组合
- 对未知的8位进行爆破（因为PC-2会丢弃8位）
- 根据移位表反向推导C0和D0
- 通过PC-1逆推得到原始密钥
关键代码实现：
def re_PC2(sbkey): res = ['*']*56 for i in range(len(sbkey)): res[__pc2[i]] = sbkey[i] return res def guess_CiDi16(sbkey, t): res = re_PC2(sbkey) for i in range(8): res[not_in_PC2[i]] = guess_8bit[t][i] return res3.2 实际解题步骤
针对NepCTF题目，解题流程如下：
- 从题目给出的C16和D16开始
- 逆向推导所有16轮子密钥
- 使用推导出的子密钥解密密文
- 验证解密结果是否符合预期（如已知明文前缀）
def try_des(cipher, roundkey): for t in range(256): combined,allkey = guess_allsbkey(roundkey, 15, t) plain = long_des_enc(cipher, allkey[::-1]) if plain.startswith(b'Nep'): print(combined,plain) exit()4. 完整解题代码与优化技巧
在实际CTF比赛中，我们需要考虑代码的效率和准确性。以下是几个优化技巧：
- 并行计算：对于256种可能的8位组合，可以使用多进程并行处理
- 提前终止：一旦发现符合预期的明文，立即终止其他计算
- 缓存中间结果：对于重复计算的步骤，使用缓存提高效率
完整解题代码结构：
# 第一部分：从C16D16推导子密钥 LL = [0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1] Rr = [0,0,0,1,1,0,0,0,1,1,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0] for i in range(2**9-1,2**7,-1): tmp = list(bin(i)[2:].rjust(9,'0')) L = LL + [int(u) for u in tmp] R = Rr combined = L+R sub_key = PC_2(combined) try_des(t, sub_key) # 第二部分：从C1D1推导完整密钥 combined = [0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0, 0,0,1,1,0,0,0,1,1,0,0,1,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0] C0D0 = combined[-2:-1] + combined[:-1] for i in range(256): KEY = guess(C0D0,i) # 使用KEY解密后续密文段通过这样的实战演练，我们不仅理解了DES算法的内部机制，还掌握了在CTF比赛中解决类似密码学题目的方法。DES虽然看似简单，但其设计精巧，深入理解后对学习其他加密算法也有很大帮助。