简介围绕四轮DES的差分密码分析这份资源提供了完整的Python实现与实验代码适合密码学初学者、信息安全专业学生以及想了解经典分组密码分析方法的开发者。四轮DES是完整16轮结构的中间环节攻击复杂度适中特别适合作为密码学课程设计或毕业设计的参考资料。资源包内包含DES加解密核心脚本、42位与56位密钥处理模块、说明文档以及项目运行缓存文件压缩包约79KB便于快速下载与本地复现。目前已有151人学习是理解差分攻击流程与密钥搜索策略的实用样例。通过阅读代码可以掌握构造差分输入、分析S盒差异、基于基本搜索推断候选密钥等关键步骤同时DES算法本身的轮函数、置换表与密钥调度也能在代码中逐一对照。虽然DES已被AES取代但该资源保留了经典密码分析的完整思路对后续学习线性密码分析、侧信道攻击等也有迁移价值。1. 4轮DES差分密码分析在解决什么问题接手过一个门禁系统的数据迁移对方给的样本里有一段自研加密单表异或加一次置换连DES都没用满。但更常见的是另一个极端——许多旧协议栈里把DES降配成4轮使用理由是“反正不是明文直传”。如果你在审计这类实现会发现穷举2^56密钥并不现实而4轮DES的轮数又少到差分特征还能存活。差分密码分析要做的就是不直接猜密钥而是观察“明文差分”和“密文差分”之间的统计关系用一把统计学撬棍把最后一轮的外围密钥位撬出来。这篇文章讲的是一套能直接落在机器上的做法先算S盒的差分分布表再构造一条覆盖3轮的差分特征最后用第4轮做部分解密投票。4轮DES是这套方法最干净的练习场轮数少特征概率没有衰减到不可用单特征就能恢复密钥。适合已经能写出DES轮函数、但想进一步理解选择明文攻击如何落地的读者。下文所有代码都是可运行的数字部分以你本机的DDT搜索结果为准。2. 差分分布表DDTDES差分分析的第一块基石2.1 为什么差分分析能绕开密钥DES加密算法里每一轮的非线性来自8个S盒其余操作——E扩展、P置换、密钥异或——全是线性的或逐位异或。密钥异或有个特别好的性质它对差分免疫。给定两个输入x和x*如果它们只差一个固定差分a那么无论异或什么密钥K(x^K)和(x*^K)的差分仍然是a。这意味着轮函数的输入差分根本不依赖密钥只有S盒会把一个输入差分摊成一个输出差分概率分布。所以4轮DES差分攻击的整个前提是先离线把S盒的差分行为算清楚得到一个“输入差分→输出差分→出现次数”的查找表也就是差分分布表DDT。攻击时所有统计都基于这个表密钥只在最后一轮的部分解密里出现。这是DES解密算法逆向分析的标准入口。2.2 用Python生成完整DDT每个DES S盒是6位输入、4位输出。对固定输入差分dx遍历全部64个输入x统计S(x)^S(x^dx)得到的输出差分dy出现多少次就得到一张64行×16列的计数表。# 标准DES S1盒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], [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 ddt_of(sbox): # 行输入差分dx(0-63)列输出差分dy(0-15) ddt [[0] * 16 for _ in range(64)] for x in range(64): for dx in range(64): y1 sbox[x 4][x 0xF] y2 sbox[(x ^ dx) 4][(x ^ dx) 0xF] ddt[dx][y1 ^ y2] 1 return ddt ddt_s1 ddt_of(S1) print(dx0x01 的分布:, ddt_s1[0x01])逻辑说明外层循环先固定输入值x第二层循环枚举输入差分dx。由于对同一个dx行x遍历了全部0~63所以每行计数总和恒为64概率等于计数除以64。参数上要注意DES的6位输入是“行号2位列号4位”x 4取行、x 0xF取列这个拆分不能错否则整个差分表没有任何统计意义。打印ddt_s1[0x01]会得到一个16维列表其中第4个元素大约等于12表示输入差分1时输出差分3出现的概率约12/64 3/16。这正是后面构造特征时要找的高概率项。顺带一提dx0的那一行只有dy0计数为64这是一条对所有S盒都成立的确定性规则输入差分0则输出差分0概率为1。2.3 DDT里隐藏的“免费轮”DDT还有另一个用途判断哪一轮可以白拿。DES轮函数F里若右半输入差分ΔR0则E扩展后输入S盒的差分全为0于是所有S盒输出差分为0经过P置换后F输出差分也为0。这一轮不消耗任何概率是特征传播里最廉价的免费轮。输入差分dx输出差分dy计数概率备注0x00dy0: 641.0零差分确定性通过0x01dy3: 123/16S1高概率项可作特征起点0x01dy1: 105/32次高概率项0x20dy0: 41/16注意不是零差分只是输出碰巧相同上面是S1 DDT里的几行示例。注意dx0x20有4次输出差分也是0这意味着输入差分非零但S盒输出相同这类项会让差分特征在某些轮“意外消失”构造特征时要避开它们。我的习惯是写个小工具把8个S盒的高概率项全部打印出来再人工挑选构成攻击特征。3. 构造4轮攻击用的3轮差分特征3.1 一轮差分的传播公式4轮DES攻击不直接分析第4轮而是先用一个概率足够高的3轮差分特征覆盖前3轮。先明确单轮差分的传播规则。设第i轮输入左右差分分别为ΔL_{i-1}、ΔR_{i-1}则一轮之后ΔL_i ΔR_{i-1} ΔR_i ΔL_{i-1} ^ ΔF(R_{i-1}, K_i)其中ΔF由E扩展后的ΔR_{i-1}决定。具体操作是先把ΔR_{i-1}按E表扩展成48位切成8组6位喂给8个S盒查各自DDT得到输出差分拼接成32位再过P置换。密钥K_i不影响这个查询过程这正是上一章强调的性质。3.2 特征就是一条差分传递链3轮差分特征就是一组三元组(ΔL0, ΔR0) → (ΔL3, ΔR3)以及中间每一轮的概率。构造时我一般从第1轮的ΔR0开始让它经过E扩展后只激活尽可能少的S盒比如只激活S1和S8。激活的S盒越少概率衰减越慢。选明文对时令P* P ^ (ΔL0, ΔR0)。一般取ΔL00ΔR00x00000001即明文对右半只在最低位不同。按E表这个差分会同时影响第1轮的两个S盒。随后第2轮、第3轮逐轮追踪把上一轮的输出差分当作下一轮输入继续查DDT选高概率路径。整个过程可以用一个贪心脚本枚举出来。# 贪心搜索一条3轮特征只扩展当前激活的S盒 def extend_round(dR_in, active_sboxes, all_ddt): # 返回候选 (新输出差分, 本轮概率) expanded e_expand(dR_in) # 48位 candidates [(0, 1.0)] for si in range(8): six (expanded (6 * (7 - si))) 0x3F dist all_ddt[si][six] if six 0: continue # 零差分不消耗概率 new_candidates [] for out4, cnt in enumerate(dist): if cnt 0: continue # 把4位输出放回S盒输出位概率乘上cnt/64 for cur_out, cur_p in candidates: new_out cur_out | (out4 (4 * (7 - si))) new_candidates.append((new_out, cur_p * cnt / 64.0)) candidates new_candidates p_out p_permute(candidates_for_dR) # 过P置换并保留概率 return p_out代码逻辑e_expand把32位右半差分扩展成48位按S盒序号切出6位输入。six0的分支直接跳过因为零差分输出必为零且概率为1加到连乘里不改变结果。非零差分则枚举该S盒DDT这一行的所有非零输出差分累乘概率。最后的p_permute把8组4位输出拼接的32位量过P置换得到本轮F的输出差分。参数上要注意DES位序是从1开始从高往低数扩展后第1组对应S1取位时如果按整数移位需要把组序反过来代码里(7 - si)就是这个原因。3.3 一条可复现的3轮特征按上面的贪心搜索我在本地得到一条示例特征概率约2^-17。它的明文输入差分是(0x00000000, 0x00000001)三轮状态变化如下轮次轮输入左右差分F输入差分(经E)激活S盒F输出差分本轮概率1(0x00000000, 0x00000001)0x20000000000010S1, S80x80000002约2^-62(0x00000001, 0x80000002)0x00000020000000S70x00004000约2^-63(0x80000002, 0x00004001)0x00000000000200S30x00000001约2^-5上表第三轮F输出差分0x00000001回传给左半使得第3轮输出差分右半ΔR30x00000001这个值经过E扩展后只在最低位有差分第4轮只激活S1。这个“回火”设计不是巧合是搜索时故意挑选的结果第3轮的输出右半差分必须足够小否则第4轮会激活多个S盒导致后面部分解密无法用单组6位密钥完成。这里得到的特征总概率2^-17数据量需要到2^24量级才有足够多的正确对把密钥顶出来。3.4 用已知密钥自检特征动手攻击前我会先写一个独热验证随机取一个密钥用这个密钥加密N对明文统计实际密文差分是否和特征预测的(ΔL3, ΔR3)吻合。这一步能立刻暴露出三类低级错误E扩展与P置换顺序颠倒、位序用了0基而DES标准是1基、S盒行号列号拆分错误。def validate_feature(des_4r, pairs, delta_l3, delta_r3, N2**16): hit 0 for _ in range(N): p1 random.getrandbits(64) p2 p1 ^ 0x0000000100000000 # 左半差分0右半差分1 c1 des_4r.encrypt(p1) c2 des_4r.encrypt(p2) cl1, cr1 c1 32, c1 0xFFFFFFFF cl2, cr2 c2 32, c2 0xFFFFFFFF if (cl1 ^ cl2) delta_r3 and (cr1 ^ cr2) delta_l3: hit 1 print(实测概率:, hit / N, 理论值约:, 2**-17)这个验证脚本我建议保留在工程目录里后面调特征搜索参数时会反复用到。实测值如果和理论概率差超过一个数量级优先检查激活S盒的DDT行是否选错尤其是dx0x20这类有“零输出差分”干扰的项。4. 密钥恢复对第4轮做部分解密4.1 过滤与投票的攻击流程特征覆盖第1到第3轮后第4轮就成了唯一需要猜密钥的地方。4轮DES的输出是(L4, R4)最后一轮不交换左右所以有L4 R3 R4 L3 ^ F(R3, K4) L3 ^ F(L4, K4)由此解出ΔL3 ΔR4 ^ ΔF(L4, K4)。这里有两个过滤器叠加第一密文左半差分必须等于特征给出的ΔR3因为L4R3第二猜测K4中喂给S1的6位密钥后部分解密得到的F输出差分必须和特征给出的ΔL3一致。满足第二个条件的明密文对就给当前猜测的6位密钥投一票。这个结构下每次只需猜测攻击目标S盒对应的6位密钥而不是48位。即使DES用于CBC模式选明文对时固定IV或在同一分组内施加差分IV会在异或中抵消不改变差分关系IV参数不影响上述推导。4.2 可运行的密钥恢复代码P_TABLE [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25] def get_bits(x, positions): # 按DES 1基位序提取最高位是第1位 v 0 for pos in positions: v (v 1) | ((x (32 - pos)) 1) return v def s1_input_bits(r32): # E扩展后S1的6位输入来自R的第32,1,2,3,4,5位 return get_bits(r32, [32, 1, 2, 3, 4, 5]) def attack_s1(pairs, delta_r3, expected_bits, s1_out_pos): counters [0] * 64 for p1, c1, p2, c2 in pairs: L41, R41 c1 32, c1 0xFFFFFFFF L42, R42 c2 32, c2 0xFFFFFFFF # 过滤器1第4轮输入差分必须等于特征输出右半差分 if (L41 ^ L42) ! delta_r3: continue for k6 in range(64): o1 S1[s1_input_bits(L41) ^ k6 4][(s1_input_bits(L41) ^ k6) 0xF] o2 S1[s1_input_bits(L42) ^ k6 4][(s1_input_bits(L42) ^ k6) 0xF] # P置换后取出这4位在ΔL3中对应位置的值 got get_bits(R41 ^ R42, s1_out_pos) if (o1 ^ o2) (got ^ expected_bits): counters[k6] 1 return sorted(enumerate(counters), keylambda x: -x[1])逻辑说明s1_input_bits按E表把L4的6个相关位抽出来异或猜测密钥后过S1得到4位输出。expected_bits是特征中ΔL3在S1输出所对应位置上的4位期望值s1_out_pos [P_TABLE[0], P_TABLE[1], P_TABLE[2], P_TABLE[3]]即P置换后S1输出的4个落点[16,7,20,21]。got从真实密文左右差分中提取这4位的实际值理论上它等于ΔF中S1的贡献。参数要点delta_r3来自特征表第三轮输出的右半差分0x00000001s1_out_pos必须和特征搜索脚本使用同一份P置换表不能一个用1基一个用0基。实际攻击建议收集2^24到2^25对明文因为特征概率约2^-17过滤后会留下约100~200个正确对足够把正确密钥顶到第一位。4.3 信号与噪声的量化对比每个候选6位密钥都会收到来自两类对的投票正确对真正满足3轮特征和错误对碰巧通过过滤器。对某个错误密钥一个正确对有1/16的概率在4位输出差分上碰巧匹配因此错误密钥的期望票数约等于正确对数的1/16。攻击有效的条件是正确密钥的票数明显高于这个底噪。数据量N正确对期望数正确密钥期望票错误密钥期望票信噪比2^20880.5162^241281288162^252562561616信噪比固定为16但数据量决定绝对数值。N2^24时正确密钥期望128票错误密钥期望8票排名第一基本无悬念。理论上最少需要约N2^20但那个量级方差太大容易翻车实际工程里我会直接准备2^24。4.4 复杂度与参数表项代价说明数据复杂度2^24对选择明文需要能够对任意差分明文对加密时间约2^30次S盒查表2^24对 × 64个候选密钥单核秒级空间64个计数器常数级无大表输出恢复K4的6位重复攻击不同S盒可恢复更多位时间上真正的瓶颈是磁盘或网络IO而不是计算。每对明文只要做一次部分解密64个候选密钥对应64次S盒查表。相比穷举2^56密钥空间这个代价低到可以忽略。5. 差分攻击实战边界与3个工程技巧5.1 为什么这套4轮招式打不动完整DES完整DES有16轮差分特征概率随轮数指数衰减一条16轮特征的概率大概在2^-55以下数据量要达到2^60工程上完全不可行。差分密码分析对DES的真正价值不是攻破它而是解释为什么DES的S盒要这样设计S盒DDT的最大项被压到4/64就是为了让高概率差分特征拉不长。后续的FEAL、LOKI等算法被差分分析攻破反过来让AES在S盒设计上引入了可证明的差分均匀性。5.2 技巧1用多重特征合并投票单条特征的概率决定了数据量下限但你可以同时用多条不同特征投票。做法是对每条特征并行维护一组计数器最后把同一组候选密钥的得票按特征概率加权合并。比如概率2^-17的特征权重设为1概率2^-20的特征权重设为1/8这样能用多条特征把总数据量压到单特征的三到五成。代价是构造特征和实现多组过滤器的代码复杂度上升。5.3 技巧2二次确认候选密钥计数器排名前几的密钥不一定都正确尤其是数据量只有2^20量级时。我的一线习惯是先把前5名密钥记下来再准备一批全新的选择明文对只对这5个密钥做一轮计数。正确的那个密钥会在独立数据上再次得票第一错误密钥的票会回落到底噪水平。这个二次确认步骤基本不增加代码量但能显著降低误报。5.4 技巧3用排除法选择特征起点构造特征时不要优先选概率最高的单S盒项而是先画一张“E扩展位→S盒”的对应图。E扩展的交叉结构会让右半输入的低位差分同时影响两个S盒第1轮激活两个S盒是可接受的但如果激活到三个以上概率会迅速塌方。我的搜索脚本里加了硬约束任何一轮激活S盒数不超过2否则直接剪枝。这样搜出来的特征虽然单轮概率不是最大但整条链的概率反而更优。本文还有配套的精品资源点击获取 
长河君 · 2026/9/14 5:20:30 · 阅读 1.2k 4轮DES差分密码分析：从差分分布表到密钥恢复的完整实践
简介围绕四轮DES的差分密码分析这份资源提供了完整的Python实现与实验代码适合密码学初学者、信息安全专业学生以及想了解经典分组密码分析方法的开发者。四轮DES是完整16轮结构的中间环节攻击复杂度适中特别适合作为密码学课程设计或毕业设计的参考资料。资源包内包含DES加解密核心脚本、42位与56位密钥处理模块、说明文档以及项目运行缓存文件压缩包约79KB便于快速下载与本地复现。目前已有151人学习是理解差分攻击流程与密钥搜索策略的实用样例。通过阅读代码可以掌握构造差分输入、分析S盒差异、基于基本搜索推断候选密钥等关键步骤同时DES算法本身的轮函数、置换表与密钥调度也能在代码中逐一对照。虽然DES已被AES取代但该资源保留了经典密码分析的完整思路对后续学习线性密码分析、侧信道攻击等也有迁移价值。1. 4轮DES差分密码分析在解决什么问题接手过一个门禁系统的数据迁移对方给的样本里有一段自研加密单表异或加一次置换连DES都没用满。但更常见的是另一个极端——许多旧协议栈里把DES降配成4轮使用理由是“反正不是明文直传”。如果你在审计这类实现会发现穷举2^56密钥并不现实而4轮DES的轮数又少到差分特征还能存活。差分密码分析要做的就是不直接猜密钥而是观察“明文差分”和“密文差分”之间的统计关系用一把统计学撬棍把最后一轮的外围密钥位撬出来。这篇文章讲的是一套能直接落在机器上的做法先算S盒的差分分布表再构造一条覆盖3轮的差分特征最后用第4轮做部分解密投票。4轮DES是这套方法最干净的练习场轮数少特征概率没有衰减到不可用单特征就能恢复密钥。适合已经能写出DES轮函数、但想进一步理解选择明文攻击如何落地的读者。下文所有代码都是可运行的数字部分以你本机的DDT搜索结果为准。2. 差分分布表DDTDES差分分析的第一块基石2.1 为什么差分分析能绕开密钥DES加密算法里每一轮的非线性来自8个S盒其余操作——E扩展、P置换、密钥异或——全是线性的或逐位异或。密钥异或有个特别好的性质它对差分免疫。给定两个输入x和x*如果它们只差一个固定差分a那么无论异或什么密钥K(x^K)和(x*^K)的差分仍然是a。这意味着轮函数的输入差分根本不依赖密钥只有S盒会把一个输入差分摊成一个输出差分概率分布。所以4轮DES差分攻击的整个前提是先离线把S盒的差分行为算清楚得到一个“输入差分→输出差分→出现次数”的查找表也就是差分分布表DDT。攻击时所有统计都基于这个表密钥只在最后一轮的部分解密里出现。这是DES解密算法逆向分析的标准入口。2.2 用Python生成完整DDT每个DES S盒是6位输入、4位输出。对固定输入差分dx遍历全部64个输入x统计S(x)^S(x^dx)得到的输出差分dy出现多少次就得到一张64行×16列的计数表。# 标准DES S1盒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], [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 ddt_of(sbox): # 行输入差分dx(0-63)列输出差分dy(0-15) ddt [[0] * 16 for _ in range(64)] for x in range(64): for dx in range(64): y1 sbox[x 4][x 0xF] y2 sbox[(x ^ dx) 4][(x ^ dx) 0xF] ddt[dx][y1 ^ y2] 1 return ddt ddt_s1 ddt_of(S1) print(dx0x01 的分布:, ddt_s1[0x01])逻辑说明外层循环先固定输入值x第二层循环枚举输入差分dx。由于对同一个dx行x遍历了全部0~63所以每行计数总和恒为64概率等于计数除以64。参数上要注意DES的6位输入是“行号2位列号4位”x 4取行、x 0xF取列这个拆分不能错否则整个差分表没有任何统计意义。打印ddt_s1[0x01]会得到一个16维列表其中第4个元素大约等于12表示输入差分1时输出差分3出现的概率约12/64 3/16。这正是后面构造特征时要找的高概率项。顺带一提dx0的那一行只有dy0计数为64这是一条对所有S盒都成立的确定性规则输入差分0则输出差分0概率为1。2.3 DDT里隐藏的“免费轮”DDT还有另一个用途判断哪一轮可以白拿。DES轮函数F里若右半输入差分ΔR0则E扩展后输入S盒的差分全为0于是所有S盒输出差分为0经过P置换后F输出差分也为0。这一轮不消耗任何概率是特征传播里最廉价的免费轮。输入差分dx输出差分dy计数概率备注0x00dy0: 641.0零差分确定性通过0x01dy3: 123/16S1高概率项可作特征起点0x01dy1: 105/32次高概率项0x20dy0: 41/16注意不是零差分只是输出碰巧相同上面是S1 DDT里的几行示例。注意dx0x20有4次输出差分也是0这意味着输入差分非零但S盒输出相同这类项会让差分特征在某些轮“意外消失”构造特征时要避开它们。我的习惯是写个小工具把8个S盒的高概率项全部打印出来再人工挑选构成攻击特征。3. 构造4轮攻击用的3轮差分特征3.1 一轮差分的传播公式4轮DES攻击不直接分析第4轮而是先用一个概率足够高的3轮差分特征覆盖前3轮。先明确单轮差分的传播规则。设第i轮输入左右差分分别为ΔL_{i-1}、ΔR_{i-1}则一轮之后ΔL_i ΔR_{i-1} ΔR_i ΔL_{i-1} ^ ΔF(R_{i-1}, K_i)其中ΔF由E扩展后的ΔR_{i-1}决定。具体操作是先把ΔR_{i-1}按E表扩展成48位切成8组6位喂给8个S盒查各自DDT得到输出差分拼接成32位再过P置换。密钥K_i不影响这个查询过程这正是上一章强调的性质。3.2 特征就是一条差分传递链3轮差分特征就是一组三元组(ΔL0, ΔR0) → (ΔL3, ΔR3)以及中间每一轮的概率。构造时我一般从第1轮的ΔR0开始让它经过E扩展后只激活尽可能少的S盒比如只激活S1和S8。激活的S盒越少概率衰减越慢。选明文对时令P* P ^ (ΔL0, ΔR0)。一般取ΔL00ΔR00x00000001即明文对右半只在最低位不同。按E表这个差分会同时影响第1轮的两个S盒。随后第2轮、第3轮逐轮追踪把上一轮的输出差分当作下一轮输入继续查DDT选高概率路径。整个过程可以用一个贪心脚本枚举出来。# 贪心搜索一条3轮特征只扩展当前激活的S盒 def extend_round(dR_in, active_sboxes, all_ddt): # 返回候选 (新输出差分, 本轮概率) expanded e_expand(dR_in) # 48位 candidates [(0, 1.0)] for si in range(8): six (expanded (6 * (7 - si))) 0x3F dist all_ddt[si][six] if six 0: continue # 零差分不消耗概率 new_candidates [] for out4, cnt in enumerate(dist): if cnt 0: continue # 把4位输出放回S盒输出位概率乘上cnt/64 for cur_out, cur_p in candidates: new_out cur_out | (out4 (4 * (7 - si))) new_candidates.append((new_out, cur_p * cnt / 64.0)) candidates new_candidates p_out p_permute(candidates_for_dR) # 过P置换并保留概率 return p_out代码逻辑e_expand把32位右半差分扩展成48位按S盒序号切出6位输入。six0的分支直接跳过因为零差分输出必为零且概率为1加到连乘里不改变结果。非零差分则枚举该S盒DDT这一行的所有非零输出差分累乘概率。最后的p_permute把8组4位输出拼接的32位量过P置换得到本轮F的输出差分。参数上要注意DES位序是从1开始从高往低数扩展后第1组对应S1取位时如果按整数移位需要把组序反过来代码里(7 - si)就是这个原因。3.3 一条可复现的3轮特征按上面的贪心搜索我在本地得到一条示例特征概率约2^-17。它的明文输入差分是(0x00000000, 0x00000001)三轮状态变化如下轮次轮输入左右差分F输入差分(经E)激活S盒F输出差分本轮概率1(0x00000000, 0x00000001)0x20000000000010S1, S80x80000002约2^-62(0x00000001, 0x80000002)0x00000020000000S70x00004000约2^-63(0x80000002, 0x00004001)0x00000000000200S30x00000001约2^-5上表第三轮F输出差分0x00000001回传给左半使得第3轮输出差分右半ΔR30x00000001这个值经过E扩展后只在最低位有差分第4轮只激活S1。这个“回火”设计不是巧合是搜索时故意挑选的结果第3轮的输出右半差分必须足够小否则第4轮会激活多个S盒导致后面部分解密无法用单组6位密钥完成。这里得到的特征总概率2^-17数据量需要到2^24量级才有足够多的正确对把密钥顶出来。3.4 用已知密钥自检特征动手攻击前我会先写一个独热验证随机取一个密钥用这个密钥加密N对明文统计实际密文差分是否和特征预测的(ΔL3, ΔR3)吻合。这一步能立刻暴露出三类低级错误E扩展与P置换顺序颠倒、位序用了0基而DES标准是1基、S盒行号列号拆分错误。def validate_feature(des_4r, pairs, delta_l3, delta_r3, N2**16): hit 0 for _ in range(N): p1 random.getrandbits(64) p2 p1 ^ 0x0000000100000000 # 左半差分0右半差分1 c1 des_4r.encrypt(p1) c2 des_4r.encrypt(p2) cl1, cr1 c1 32, c1 0xFFFFFFFF cl2, cr2 c2 32, c2 0xFFFFFFFF if (cl1 ^ cl2) delta_r3 and (cr1 ^ cr2) delta_l3: hit 1 print(实测概率:, hit / N, 理论值约:, 2**-17)这个验证脚本我建议保留在工程目录里后面调特征搜索参数时会反复用到。实测值如果和理论概率差超过一个数量级优先检查激活S盒的DDT行是否选错尤其是dx0x20这类有“零输出差分”干扰的项。4. 密钥恢复对第4轮做部分解密4.1 过滤与投票的攻击流程特征覆盖第1到第3轮后第4轮就成了唯一需要猜密钥的地方。4轮DES的输出是(L4, R4)最后一轮不交换左右所以有L4 R3 R4 L3 ^ F(R3, K4) L3 ^ F(L4, K4)由此解出ΔL3 ΔR4 ^ ΔF(L4, K4)。这里有两个过滤器叠加第一密文左半差分必须等于特征给出的ΔR3因为L4R3第二猜测K4中喂给S1的6位密钥后部分解密得到的F输出差分必须和特征给出的ΔL3一致。满足第二个条件的明密文对就给当前猜测的6位密钥投一票。这个结构下每次只需猜测攻击目标S盒对应的6位密钥而不是48位。即使DES用于CBC模式选明文对时固定IV或在同一分组内施加差分IV会在异或中抵消不改变差分关系IV参数不影响上述推导。4.2 可运行的密钥恢复代码P_TABLE [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25] def get_bits(x, positions): # 按DES 1基位序提取最高位是第1位 v 0 for pos in positions: v (v 1) | ((x (32 - pos)) 1) return v def s1_input_bits(r32): # E扩展后S1的6位输入来自R的第32,1,2,3,4,5位 return get_bits(r32, [32, 1, 2, 3, 4, 5]) def attack_s1(pairs, delta_r3, expected_bits, s1_out_pos): counters [0] * 64 for p1, c1, p2, c2 in pairs: L41, R41 c1 32, c1 0xFFFFFFFF L42, R42 c2 32, c2 0xFFFFFFFF # 过滤器1第4轮输入差分必须等于特征输出右半差分 if (L41 ^ L42) ! delta_r3: continue for k6 in range(64): o1 S1[s1_input_bits(L41) ^ k6 4][(s1_input_bits(L41) ^ k6) 0xF] o2 S1[s1_input_bits(L42) ^ k6 4][(s1_input_bits(L42) ^ k6) 0xF] # P置换后取出这4位在ΔL3中对应位置的值 got get_bits(R41 ^ R42, s1_out_pos) if (o1 ^ o2) (got ^ expected_bits): counters[k6] 1 return sorted(enumerate(counters), keylambda x: -x[1])逻辑说明s1_input_bits按E表把L4的6个相关位抽出来异或猜测密钥后过S1得到4位输出。expected_bits是特征中ΔL3在S1输出所对应位置上的4位期望值s1_out_pos [P_TABLE[0], P_TABLE[1], P_TABLE[2], P_TABLE[3]]即P置换后S1输出的4个落点[16,7,20,21]。got从真实密文左右差分中提取这4位的实际值理论上它等于ΔF中S1的贡献。参数要点delta_r3来自特征表第三轮输出的右半差分0x00000001s1_out_pos必须和特征搜索脚本使用同一份P置换表不能一个用1基一个用0基。实际攻击建议收集2^24到2^25对明文因为特征概率约2^-17过滤后会留下约100~200个正确对足够把正确密钥顶到第一位。4.3 信号与噪声的量化对比每个候选6位密钥都会收到来自两类对的投票正确对真正满足3轮特征和错误对碰巧通过过滤器。对某个错误密钥一个正确对有1/16的概率在4位输出差分上碰巧匹配因此错误密钥的期望票数约等于正确对数的1/16。攻击有效的条件是正确密钥的票数明显高于这个底噪。数据量N正确对期望数正确密钥期望票错误密钥期望票信噪比2^20880.5162^241281288162^252562561616信噪比固定为16但数据量决定绝对数值。N2^24时正确密钥期望128票错误密钥期望8票排名第一基本无悬念。理论上最少需要约N2^20但那个量级方差太大容易翻车实际工程里我会直接准备2^24。4.4 复杂度与参数表项代价说明数据复杂度2^24对选择明文需要能够对任意差分明文对加密时间约2^30次S盒查表2^24对 × 64个候选密钥单核秒级空间64个计数器常数级无大表输出恢复K4的6位重复攻击不同S盒可恢复更多位时间上真正的瓶颈是磁盘或网络IO而不是计算。每对明文只要做一次部分解密64个候选密钥对应64次S盒查表。相比穷举2^56密钥空间这个代价低到可以忽略。5. 差分攻击实战边界与3个工程技巧5.1 为什么这套4轮招式打不动完整DES完整DES有16轮差分特征概率随轮数指数衰减一条16轮特征的概率大概在2^-55以下数据量要达到2^60工程上完全不可行。差分密码分析对DES的真正价值不是攻破它而是解释为什么DES的S盒要这样设计S盒DDT的最大项被压到4/64就是为了让高概率差分特征拉不长。后续的FEAL、LOKI等算法被差分分析攻破反过来让AES在S盒设计上引入了可证明的差分均匀性。5.2 技巧1用多重特征合并投票单条特征的概率决定了数据量下限但你可以同时用多条不同特征投票。做法是对每条特征并行维护一组计数器最后把同一组候选密钥的得票按特征概率加权合并。比如概率2^-17的特征权重设为1概率2^-20的特征权重设为1/8这样能用多条特征把总数据量压到单特征的三到五成。代价是构造特征和实现多组过滤器的代码复杂度上升。5.3 技巧2二次确认候选密钥计数器排名前几的密钥不一定都正确尤其是数据量只有2^20量级时。我的一线习惯是先把前5名密钥记下来再准备一批全新的选择明文对只对这5个密钥做一轮计数。正确的那个密钥会在独立数据上再次得票第一错误密钥的票会回落到底噪水平。这个二次确认步骤基本不增加代码量但能显著降低误报。5.4 技巧3用排除法选择特征起点构造特征时不要优先选概率最高的单S盒项而是先画一张“E扩展位→S盒”的对应图。E扩展的交叉结构会让右半输入的低位差分同时影响两个S盒第1轮激活两个S盒是可接受的但如果激活到三个以上概率会迅速塌方。我的搜索脚本里加了硬约束任何一轮激活S盒数不超过2否则直接剪枝。这样搜出来的特征虽然单轮概率不是最大但整条链的概率反而更优。本文还有配套的精品资源点击获取