从子密钥逆推到完整密钥：DES算法在CTF中的实战密钥恢复指南

1. DES算法与CTF竞赛的奇妙碰撞

在CTF竞赛中，密码学题目往往是最考验选手基本功和技术深度的部分。DES（Data Encryption Standard）作为经典的对称加密算法，虽然现在已经被AES取代，但在CTF中依然频繁出现。特别是在一些需要逆向思维的题目中，理解DES的密钥生成机制往往成为解题的关键。

我第一次接触DES相关的CTF题目是在2018年的某场比赛，当时题目给出了加密过程中的部分子密钥，要求恢复出完整的主密钥。那时候我对DES的理解还停留在"黑盒"阶段，只知道输入输出，对内部细节一知半解。结果自然是铩羽而归，但也正是这次失败，让我下定决心要彻底吃透DES算法。

DES算法的密钥生成过程就像是一个精密的齿轮传动系统。主密钥经过PC-1置换后，被分成C0和D0两部分，每轮通过循环左移和PC-2置换生成48位的子密钥。这个过程中最有趣的是，由于PC-2置换会丢弃8位信息，所以从子密钥逆向推导主密钥时，会产生256种可能，这也就是我们需要爆破的空间。

2. 从子密钥逆推主密钥的核心思路

2.1 理解密钥生成流程

要逆向推导主密钥，首先必须完全掌握正向的密钥生成过程。DES的密钥生成可以分解为以下几个步骤：

1. 64位主密钥经过PC-1置换，去除8位校验位，得到56位有效密钥
2. 这56位被均分为C0和D0两部分，各28位
3. 每轮根据移位表对C和D进行循环左移
4. 移位后的C和D合并，经过PC-2置换生成48位子密钥

这里的关键在于PC-2置换会从56位输入中选择48位输出，这意味着有8位信息被丢弃了。正是这8位信息，成为了逆向推导时的"不确定因素"。

# DES密钥生成的核心代码示例 def get_sub_key(key): key = PC_1(key) # 64位->56位 L, R = key[:28], key[28:] # 分为C0和D0 sub_keys = [] for i in range(16): # 循环左移 for j in range(ROTATIONS[i]): L.append(L.pop(0)) R.append(R.pop(0)) combined = L + R sub_key = PC_2(combined) # 56位->48位 sub_keys.append(sub_key) return sub_keys

2.2 逆向推导的数学原理

从子密钥逆推主密钥的核心在于理解PC-2置换的可逆性。虽然PC-2丢弃了8位信息，但我们可以：

1. 根据PC-2的置换表，确定子密钥中每一位对应原始56位中的位置
2. 对于PC-2没有选中的8位，我们需要暴力枚举所有可能性（2^8=256种）
3. 通过已知的明文-密文对来验证哪种猜测是正确的

在实际CTF题目中，通常会给出最后一轮的子密钥（K16），因为这样可以通过反向推导得到所有轮次的子密钥。从K16推导K15的过程，其实就是密钥生成过程的逆过程 - 将循环左移改为循环右移。

3. 实战演练：NepCTF simpleDES题解

3.1 题目分析

让我们以2023年NepCTF中的simpleDES题目为例，演示如何从子密钥恢复主密钥。题目给出了以下关键信息：

1. 加密过程中的最后一轮子密钥的部分比特（LL和Rr）
2. 第一段加密后的密文
3. 提示明文以"Nep"开头

我们的目标是利用这些信息恢复出完整的主密钥，进而解密整个消息。

3.2 解题步骤详解

第一步：从给出的LL和Rr重建K16

题目中给出了LL和Rr，这实际上是C16和D16的部分比特。我们需要：

1. 补全缺失的比特（题目中有9位缺失）
2. 将C16和D16合并后通过PC-2置换得到K16

def guess_CiDi16(sbkey, t): res = re_PC2(sbkey) # 48位->56位 # 补全PC-2未选中的8位 for i in range(8): res[not_in_PC2[i]] = guess_8bit[t][i] return res

第二步：从K16推导所有子密钥

有了K16后，我们可以反向推导出所有轮次的子密钥。这是因为DES的密钥生成是对称过程，只需要将左移改为右移即可。

def guess_allsbkey(roundkey, r, t): sbkey = [[]]*16 sbkey[r] = roundkey # 设置已知的K16 CiDi = guess_CiDi16(roundkey, t) Ci, Di = CiDi[:28], CiDi[28:] # 反向推导15轮 for i in range(r+1,r+16): # 循环右移恢复上一轮的C和D Ci, Di = LR_reverse(Ci, Di, i%16) sbkey[i%16] = PC_2(Ci+Di) return sbkey

第三步：暴力破解缺失的比特

由于有8位信息缺失，我们需要枚举所有256种可能性。对于每种可能性：

1. 尝试解密第一段密文
2. 检查解密结果是否以"Nep"开头
3. 如果匹配，则说明找到了正确的子密钥

def try_des(cipher, roundkey): for t in range(256): # 枚举256种可能 allkey = guess_allsbkey(roundkey, 15, t) # 使用反向的子密钥解密 plain = long_des_enc(cipher, allkey[::-1]) if plain.startswith(b'Nep'): return plain

第四步：利用已知信息解密后续段落

成功解密第一段后，我们可以利用已知的明文和密文关系来解密后续段落。这是因为题目中的加密模式是：

key_i = key ^ plaintext_{i-1}

所以一旦知道第一段的明文，就可以推导出用于加密第二段的密钥。

4. 编写高效的Python破解脚本

4.1 密钥恢复的核心函数

在实际解题过程中，我们需要编写高效的Python脚本来实现上述思路。以下是几个关键函数：

def recover_key_from_subkey(subkey): """从子密钥恢复主密钥""" for t in range(256): # 尝试补全缺失的8位 full_key = complete_missing_bits(subkey, t) # 验证密钥是否正确 if validate_key(full_key): return full_key return None def validate_key(key): """验证密钥是否正确""" # 使用已知的明文-密文对进行验证 test_plain = b"KnownPlain" test_cipher = des_encrypt(test_plain, key) return test_cipher == known_cipher

4.2 性能优化技巧

在CTF比赛中，时间往往很宝贵。对于DES密钥恢复这类需要暴力破解的任务，可以考虑以下优化：

1. 使用多线程/多进程并行处理256种可能性
2. 预先计算并缓存S盒等置换表
3. 使用Cython或numba加速关键代码段
4. 尽早终止无效的猜测（如解密结果明显不符合预期时）

from multiprocessing import Pool def parallel_bruteforce(): """并行化暴力破解""" with Pool(processes=4) as pool: results = pool.map(try_guess, range(256)) return [r for r in results if r is not None]

4.3 完整的解题脚本架构

一个完整的DES密钥恢复脚本通常包含以下模块：

1. DES算法实现（加密/解密函数）
2. 密钥生成与逆向函数
3. 暴力破解控制器
4. 结果验证与输出

建议采用模块化设计，这样既方便调试，也便于复用代码到其他类似题目中。

5. 防御措施与出题思路

5.1 如何防止此类攻击

作为CTF选手，了解攻击方法很重要；但作为出题人，更需要知道如何设计安全的密码题目。要防止子密钥恢复攻击，可以考虑：

1. 使用更强的加密算法（如AES）
2. 增加密钥派生函数的复杂度
3. 采用适当的加密模式（如CBC、CTR）
4. 避免泄露任何中间状态信息

5.2 进阶出题思路

如果想设计更难的DES相关题目，可以考虑：

1. 只泄露部分子密钥比特（而非完整子密钥）
2. 使用自定义的S盒或置换表
3. 结合其他密码学原语（如哈希函数）
4. 设计多层加密结构

这类题目既能考察选手对DES算法的深入理解，又能测试他们的综合分析和解决问题的能力。