四轮DES差分密码分析：Python实现轮密钥恢复与搜索

简介围绕 DES 四轮差分密码分析的 Python 项目资源以算法源码与说明文档为核心演示如何借助输入输出差异和基本密钥搜索分析 4-round DES 的密码弱点。四轮 DES 是完整 16 轮迭代的中间阶段通过对截断后的简化版本开展攻击能够更直观地暴露差分分析的核心逻辑。适用于密码学课程设计、安全方向入门实验或对分组密码分析感兴趣的研究者参考。压缩包约 79KB共 7 个条目以 Python 脚本和 Markdown 文档为主结构紧凑可直接对照阅读与运行代码中涵盖 DES 加解密、56 位密钥与 42 位密钥变体处理以及差分对构造和密钥筛选过程。该资源目前已有 151 人学习/浏览关注度较高通过学习这份项目既能理解 DES 被更安全算法替代的历史原因也能掌握差分密码分析的基本研究思路具有不错的实践与教学价值。1. 四轮DES差分密码分析为破解“过时”算法写的搜索代码DES早在生产环境退役但四轮版本至今仍是密码分析课最常练手的对象。差分密码分析不靠穷举全部密钥而是跟踪一对明文之间的差分如何穿过Feistel结构用S盒差分分布表制造概率偏差最后把第四轮子密钥从错误候选中“顶”出来。这个仓库用Python写了一个面向四轮DES的差分分析实验code.py负责主流程DES_Key_42bits.py和56_Bit_Key.py分别处理42位实验密钥与标准56位主密钥。适合想弄懂S盒差分特征、轮密钥恢复和搜索空间折衷的人读完就能把轮函数拆开看。2. Feistel结构与S盒差分特征四轮DES差分传播怎么算2.1 轮函数中的差分不变量DES每轮由左半、右半和轮密钥驱动。F函数先把32位右半做扩展置换E盒变成48位与48位轮密钥异或后进入8个S盒每个S盒把6位输入映射成4位输出最后经过P置换。差分分析关心的是当输入差分为Δ时S盒输出的差分分布必然存在频率偏差。标准S盒每个输入差分对应64种输入x输出差分y的出现次数不平均这些次数就是S盒的差分分布表DDT。对4轮DES而言攻击者不需要直接解S盒方程而是构造大量明文对让它们的差分以高概率走同一条路径。路径越短、概率越高需要选择的明文对就越少。四轮版本是最适合演示“概率路径加计数器”的中间形态比单轮多出轮间混合又比十六轮版本少了很多噪声扩散。2.2 用DDT找到单条S盒高概率路径先写一段生成标准S盒DDT的代码后续差分路径选择全部依赖这张表。实际项目中不会把8个S盒都打印出来但生成逻辑是同一个。# 标准DES S盒S[0] 只列1个实际请补全8个4x16表 S [ [ [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] ], ] def sbox_lookup(sbox, x): row ((x 0x20) 4) | (x 1) col (x 1) 0x0F return sbox[row][col] def build_ddt(sbox): ddt [[0] * 16 for _ in range(64)] for x in range(64): for dx in range(64): y0 sbox_lookup(sbox, x) y1 sbox_lookup(sbox, x ^ dx) ddt[dx][y0 ^ y1] 1 return ddt for dx in [0x01, 0x02, 0x04, 0x08]: row build_ddt(S[0])[dx] best max(row) print(fdx{dx:02X} 最高计数{best} 对应输出差分{row.index(best):02X})这段代码统计的是在固定输入差分dx下6位输入x遍历全空间S盒输出差分y0 ^ y1的分布。计数越高该S盒差分路径概率越大。标准S盒大部分输入差分在64个样本里最高计数在14到20之间意味着单盒概率约0.22到0.31。真正做4轮DES攻击时要把这样一条单盒路径通过E扩展和P置换接到多轮中去形成完整的32位差分特征。2.3 三轮差分特征与攻击参数第3章的攻击代码需要两个常量它们来自差分路径枚举EXPECTED_R3_DIFF表示经过前三轮后右半差分EXPECTED_L3_DIFF表示左半差分。这两个值不是猜出来的而是把轮函数差分路径逐轮拼接后得到的预测值。仓库的README.md里一般会写明预设的明文差分和期望中间差分建议先阅读它再跑code.py。参数位宽含义PLAINTEXT_DIFF32位选择明文对的初始右半差分EXPECTED_R3_DIFF32位第三轮输出右半差分等于第四轮F函数输入差分EXPECTED_L3_DIFF32位第三轮输出左半差分用于计算第四轮F函数输出差分ROUND_KEY_COUNT48位第四轮子密钥由8组6位候选拼接得到新手容易直接把任意明文差分丢进代码。差分特征的概率决定了攻击是否成立如果特征概率是2^-18那么明文对要远多于这个倒数的两倍计数器才有统计意义。后面第3章代码里的过滤条件就是拿EXPECTED_R3_DIFF去筛密文对。3. 基于基本搜索的第四轮子密钥恢复计数器统计出48位密钥3.1 攻击流程选择明文对和差分过滤四轮DES差分攻击的最终目标是恢复第四轮子密钥K4。流程分四步准备明文对、执行四轮加密、过滤不符合差分特征的密文对、逐S盒猜测6位子密钥并计数。这里的“基本搜索”指的是对每个S盒只搜索64种6位子密钥而不是直接搜索2^56主密钥。具体来说选择一组满足PLAINTEXT_DIFF的明文对(P, P*)用真实密钥加密得到(C, C*)。由于四轮DES的密文(L4, R4)满足L4 R3和R4 L3 ^ F(R3, K4)所以密文左半差分L4 ^ L4*就是第四轮F函数的输入差分。如果这组明文对符合前三轮的高概率差分特征那么第四轮F函数的输出差分应该等于R4 ^ R4* ^ EXPECTED_L3_DIFF。过滤条件有两个一是L4 ^ L4* EXPECTED_R3_DIFF二是计算出的F函数输出差分不能为全零随机值。过滤后留下来的明文对数量远少于原始数量但正确子密钥在这些样本上会稳定命中。3.2code.py中第四轮子密钥恢复核心逻辑下面给出一个可运行的恢复逻辑它把P置换的逆变换先作用在F函数输出差分上再逐S盒独立计数。这样每个S盒只需要搜索64个6位密钥总搜索量只有8 * 64 512次而不是2^48次。from collections import defaultdict # 假设 E_BOX, P_BOX, S_BOXES 已在 code.py 中定义 INV_P [P_BOX.index(i) for i in range(32)] # P置换的逆索引 def p_diff_to_sbox_diff(f_out_diff): 把F函数输出的32位差分反P置换得到S盒输出差分 diff 0 for i in range(32): bit (f_out_diff i) 1 diff | bit INV_P[i] return diff def recover_subkey(pairs, expected_r3_diff, expected_l3_diff): stats [defaultdict(int) for _ in range(8)] for (L, R), (Ls, Rs) in pairs: if (L ^ Ls) ! expected_r3_diff: continue f_diff (R ^ Rs) ^ expected_l3_diff sbox_target p_diff_to_sbox_diff(f_diff) ER, ERs expand(L), expand(Ls) for i in range(8): target (sbox_target (4 * i)) 0xF x (ER (6 * i)) 0x3F xs (ERs (6 * i)) 0x3F for k in range(64): y sbox_lookup(S_BOXES[i], x ^ k) ys sbox_lookup(S_BOXES[i], xs ^ k) if (y ^ ys) target: stats[i][k] 1 return stats逻辑说明expand(L)将密文左半作为第四轮F函数的输入因为第四轮的F输入就是上一轮的右半即密文左半。f_diff是F函数输出的实际差分经过p_diff_to_sbox_diff后变成8组4位S盒输出差分。每组子密钥候选k的6位值与扩展后的输入异或进入S盒比较输出差分是否等于目标。一旦匹配当前候选计数加一。参数说明expected_r3_diff来自差分特征表它过滤掉大量不满足路径的明文对是降低噪声的关键。expected_l3_diff用于从密文差分中剥离F函数的贡献直接决定每个S盒目标差分是否正确。运行时建议把stats输出为每个S盒的Top候选正确子密钥通常会在某个值上出现明显峰值。3.3 候选密钥排序与拼接每组6位密钥恢复后把8组值按S盒编号拼成48位第四轮子密钥。实际输出可能像下面这样S盒编号正确候选计数次高候选计数差距01234倍1924.5倍21443.5倍31125.5倍410110倍51334.3倍6824倍71234倍如果某个S盒的正确候选计数没有明显领先先检查明文对数量是否足够再检查该S盒对应的输入差分是不是被过滤条件误伤了。差分分析的特征概率不是1所以总会有一部分明文对走别的路径统计上正确密钥的峰值必须稳定高于噪声水平。4. 从56位到42位四轮DES差分分析的主密钥搜索与速度取舍4.1 轮密钥恢复后还要不要搜索主密钥差分分析直接恢复的是第四轮子密钥K4而不是主密钥。DES密钥扩展算法是确定性的从任何一轮48位轮密钥都能反推主密钥的部分信息。但完整反推需要至少两轮轮密钥或者对剩余未知位枚举。四轮实验里拿到K4后如果还想恢复完整56位主密钥通常做法是固定K4枚举主密钥中与K4无关的位再用其他轮密钥或已知明文验证。这就是为什么仓库里会出现DES_Key_42bits.py。42位并不是DES标准里的格式而是实验者为了控制搜索量故意截短的密钥。把主密钥压缩到42位后从K4反推剩余14位主密钥只需要枚举2^14个候选在单机上几秒就能跑完。56_Bit_Key.py则处理标准56位主密钥用于验证差分特征本身不让主密钥搜索成为瓶颈。4.2 42位和56位脚本如何配合使用实际项目中两个脚本通常作为模块被code.py导入。DES_Key_42bits.py负责把42位主密钥扩展成DES密钥扩展算法需要的56位格式再生成各轮回密钥56_Bit_Key.py直接接收标准56位密钥。下面这段代码展示了两者的分工。from DES_Key_42bits import expand_42_to_56 from 56_Bit_Key import derive_round_keys from code import recover_subkey # 42位配置先恢复第四轮子密钥再枚举剩余14位主密钥 k4_48bits recover_subkey(all_pairs, EXPECTED_R3_DIFF, EXPECTED_L3_DIFF) known_42 0x3F2C9A1B7D # 示例42位密钥 candidates [] for tail in range(1 14): master56 expand_42_to_56(known_42, tail) subkeys derive_round_keys(master56) if subkeys[3] k4_48bits: candidates.append(master56) print(len(candidates))逻辑说明recover_subkey返回第四轮子密钥expand_42_to_56把已知42位和14位枚举位合并成56位主密钥derive_round_keys生成4轮子密钥。只有第4轮子密钥匹配时才保留候选。参数tail取值范围是0到2^14-1正好覆盖全部未知位如果仓库里42位版本另有约定以实际函数签名为准。4.3 搜索空间与时间折衷配置主密钥位宽从K4反推未知位枚举量单机耗时估计标准56位5614位2^14秒级42位实验4214位2^14秒级完整56位暴力56562^56不可行上表的关键是差分分析已经把密钥搜索从2^56降到2^14这是攻击价值的核心。如果你在自己的机器上跑code.py时发现长时间无输出先别怀疑差分路径去看明文对数量是否足够。特征概率越低需要的明文对越多。实践中我会先用5000对明文跑一遍观察每个S盒Top候选的计数差如果峰值不明显再把明文对数量翻倍而不是盲目增加到百万级。内存方面计数器只有8组64个整数占用的空间可以忽略。有一个容易忽略的坑DES_Key_42bits.py里的42位密钥可能已经按“去校验位”或者“去掉S盒无关位”做了处理直接拿标准56位密钥截断会导致后续子密钥不匹配。使用前先读文件头注释确认42位到56位是左补零、右补零还是按特定位置插入奇偶校验位。5. 验证恢复结果四轮DES差分分析常见踩坑与检查清单恢复出第四轮子密钥后第一件事不是急着找主密钥而是验证这个48位K4真的能解释所有密文差分。最直接的验证方法是拿测试明文再加密一次比较密文是否一致。for p, ref in test_vectors.items(): c des4_round(p, master_candidate) assert c ref, fmismatch for {p:016X}如果这一步失败优先检查三个地方。第一E盒和P盒的索引是否按DES标准从0开始很多实现把置换表写成1到32的基数差一位整个F函数全错。第二四轮DES加密后是否做了左右交换标准DES最后一轮不交换但有的教学实现会交换导致密文左右半与差分推导对不上。处理办法是在加密函数入口写一行注释说明返回的(L, R)是交换前还是交换后攻击代码保持一致即可。第三差分过滤条件太严。EXPECTED_R3_DIFF是概率意义上的期望值不是每个密文对都满足。如果你把不满足条件的明文对全部丢弃正确子密钥的计数来源变少峰值自然不明显。常见做法是先不过滤直接统计所有明文对让错误候选的计数被随机噪声拉低正确候选因为路径概率优势仍会领先。另一种做法是降低筛选阈值比如允许密文左半差分与期望值的汉明距离小于等于2再用计数结果反向修正特征。还有一个值得验证的点8组6位子密钥拼接顺序。stats[0]对应哪个S盒不是按数组顺序而是要跟E盒扩展后的48位分组顺序一致。出错时表现为每个S盒单独看都有峰值但拼出的48位子密钥在密钥扩展逆推时找不到任何合法主密钥。这时可以用DES密钥扩展的已知关系做快速校验K4的每6位应该分布在主密钥的若干固定位上如果多位冲突就说明有一个S盒的分组顺序错了。整个项目跑通后回看S盒DDT你会明白为什么差分分析把搜索空间压缩得这么狠。本文还有配套的精品资源点击获取