简介基于C的六轮DES算法差分分析实现面向密码学课程设计与差分密码分析入门者完整呈现选择明文攻击的工程化落地流程。代码按模块划分为四部分6轮DES加解密模块用于产生明密文对与最终验证差分分析表生成模块用于统计输入差分到输出差分的分布明密文对生成与筛选模块用于检查是否满足选择明文攻击条件差分分析主程序负责完成六轮DES的差分破解并展示结果。压缩包共11个文件以C源文件.cpp/.h和Markdown说明为主另有运行结果截图、工程图片及许可证文件整体仅86KB轻量且便于携带。已有238人学习适合作为课程作业参考、实验复现或进一步扩展到更高轮数DES与线性分析的过渡基础。1. 六轮 DES 差分分析为什么是六轮以及这个题在做什么如果你已经写过 C 的 DES 加解密大概率觉得 DES 只是位运算的堆砌但把 DES 看成一组 S 盒查表后进攻它的方式会完全不同。六轮 DES 是经典差分分析的理想靶子轮数少到可以枚举候选子密钥又没有少到像单轮那样可以从密文差直接猜出密钥位。这篇文章要解决的问题很具体给定一对差值固定的明文/密文对如何用 C 实现差分分布表、构造差分特征并对最后一轮子密钥做投票恢复。适合对分组密码有基本概念、想在工程里复现算法而不只是读公式的读者。2. 差分密码分析基础与六轮 DES 的差分特征2.1 DES 轮函数与 F 函数的差分传播差分分析的观测对象是 XOR。在 Feistel 轮中密钥通过异或进入 F 函数而异或不改变两路输入的差分所以密钥位置对差分传播来说是透明的。真正非线性、需要重点处理的是 8 个 S 盒。F 函数由扩展置换 E、8 个 S 盒和置换 P 组成其中只有 S 盒会产生概率性的差分传播。一个 S 盒的差分传播可以用一张 64×16 的表描述每一行对应输入差分 δ每一列对应输出差分 Δ表项是输入差分 δ 出现的次数。标准 DES 算法里每个 S 盒都是 6 位输入、4 位输出所以这张表就是 64 行 16 列。构造这张表不需要密钥只需要把 S 盒当成一个普通映射枚举全部可能的输入对。我在做 C 实现时不会手动去翻 S 盒的差分性质而是先写一个生成差分分布表的小程序。这样既能验证标准参考实现里的 S 盒定义是否抄对也能为后面的特征选择提供数据依据。2.2 用 C 生成 S 盒差分分布表DDT下面这段代码生成 DES 中第一个 S 盒的差分分布表并打印输入差分为0x01时的输出差分分布#include array #include iostream // DES 的 S1 盒定义按 4 行 16 列线性展开 static const std::arrayuint8_t, 64 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 }; int main() { std::arraystd::arrayint, 16, 64 ddt{}; for (int x1 0; x1 64; x1) { for (int x2 0; x2 64; x2) { int din x1 ^ x2; int dout S1[x1] ^ S1[x2]; ddt[din][dout]; } } for (int dout 0; dout 16; dout) { if (ddt[0x01][dout] ! 0) { std::cout delta_out dout count ddt[0x01][dout] \n; } } }逻辑很简单x1和x2穷举 S1 的全部 2^6 个输入它们的输入差分是din输出差分是dout每遇到一次就给对应格子加一。由于输入只有 64 种组合任何一行din的所有列计数之和必然等于 64。对于差分分析来说你关注的是count占 64 的比例这个比例就是该差分路径的条件概率。比如输出差分delta_out...的count...意味着随机输入满足这个差分的概率是count/64。代码里只打印了din0x01的行实际使用时可以循环打印全部行或者把统计结果导出为 CSV 供后续脚本读取。需要注意这张表不是 DES 的胜负手真正麻烦的是如何把单个 S 盒的差分拼接成覆盖多轮的完整特征。因为扩展置换 E 会把相邻 S 盒的输入位串起来一个din并不总能独立落在某个 S 盒上后面会在 2.3 节专门处理。2.3 构造覆盖前 5 轮的差分特征六轮 DES 差分攻击的常见做法是先找一条覆盖第 1 轮到第 5 轮的差分特征然后在第 6 轮做部分解密。原因是最后一轮可以用枚举子密钥的方法剥掉不需要知道完整密钥。差分特征的结构是明文差分(ΔL0, ΔR0)每一轮经过 Feistel 后的差分传播到第 5 轮输出时我们希望看到的目标差分targetR5。一次轮传播可以抽象成下式ΔL_i ΔR_{i-1} ΔR_i ΔL_{i-1} xor ΔF_{i-1}其中ΔF_{i-1}是 S 盒和 P 置换联合贡献的输出差分。由于密钥异或不影响差分ΔF_{i-1}完全由上一轮的右半输入差分和 S 盒的差分分布决定。在 C 里我会把特征存储成一个结构体避免在攻击代码里散落魔数struct DiffPath { uint32_t dl; // 明文左半差分 uint32_t dr; // 明文右半差分 uint32_t targetR5; // 解密第6轮后期望看到的第5轮输出差分 int sboxIndex; // 活跃 S 盒编号0~7 int pairsNeeded; // 成功攻击所需明文对数量的经验值 };targetR5的选取原则是只保留活跃 S 盒对应的输出位其他位全部置零。因为在部分解密时只有活跃 S 盒对应的 6 位子密钥需要枚举其他 S 盒既增加噪声也扩大搜索空间。把targetR5限定到单个 S 盒对应的输出位可以把候选密钥空间从 2^48 降到 2^6这是差分分析能实际跑起来的关键。构造特征这一步我会先用 2.2 节的程序列出每个 S 盒的高概率差分再手工拼一条 5 轮路径。对于六轮 DES一条 5 轮特征的概率通常在 2^-12 到 2^-16 量级意味着选择明文对数 N 至少要大于等于该概率的倒数才能保证真实密钥在投票中有统计优势。3. 在 C 中搭建六轮 DES 加解密与随机明文对生成3.1 六轮 DES 的最小实现差分攻击不需要完整的 DES 密钥调度因为明文对和密文对都是使用固定密钥加密出来的攻击过程只关心最后一轮子密钥。下面这个类实现了六轮 Feistel 加解密的骨架f函数就是标准 DES F 函数具体 E 扩展表、S 盒和 P 置换可以直接从 FIPS 46-3 标准复制。#include cstdint class SixRoundDES { public: explicit SixRoundDES(const uint32_t roundKeys[6]) { for (int i 0; i 6; i) K[i] roundKeys[i]; } // 标准一轮F(R, K) P(S(E(R) xor K)) static uint32_t f(uint32_t r, uint32_t k) { // 1. E 扩展 32-48 // 2. 与子密钥异或 // 3. 8 个 S 盒分别查表输出 4 位拼接为 32 位 // 4. P 置换 uint64_t e E(r); e ^ k; uint32_t s SBOX_lookup(e); return P(s); } void encrypt(uint32_t l, uint32_t r) const { for (int i 0; i 6; i) { uint32_t nl r; uint32_t nr l ^ f(r, K[i]); l nl; r nr; } // 最后一轮不交换输出 (L5, R5) 即可 } private: uint32_t K[6]; static uint64_t E(uint32_t r); // 48 位扩展 static uint32_t SBOX_lookup(uint64_t e); // 8 个 S 盒查表 static uint32_t P(uint32_t s); // 32 位置换 };注意加密结束后我没有做左右交换。标准 DES 的最后一步有交换但差分分析中交换是线性的而且会影响后续部分解密的索引。为了避免混淆我统一约定六轮 DES 的密文就是(L5, R5)不再交换。攻击代码也按这个约定来写。E、SBOX_lookup和P三处实现与标准 DES 完全一致。建议在写攻击代码之前先用一组已知的测试向量验证这个encrypt的行为取L0x12345678, R0x9ABCDEF0六个子密钥都用0x12345678打印每一轮输出与手工 Feistel 推导对照。这个调试步骤很值得做因为后面所有差分投票都依赖部分解密的方向。3.2 随机明文对生成攻击需要选择明文对所以生成器必须能按指定差分(dl, dr)构造大量输入并返回加密后的密文对。常见做法是用std::mt19937生成随机基值再用基值异或差分得到第二个明文#include random #include vector struct Pair { uint32_t l1, r1, l2, r2; uint32_t c1l, c1r, c2l, c2r; }; std::vectorPair generatePairs(int n, const DiffPath path, const SixRoundDES des) { std::mt19937 rng(0x1D3A5EED); std::vectorPair out; out.reserve(n); while ((int)out.size() n) { uint32_t l rng(); uint32_t r rng(); Pair p; p.l1 l; p.r1 r; p.l2 l ^ path.dl; p.r2 r ^ path.dr; p.c1l p.l1; p.c1r p.r1; p.c2l p.l2; p.c2r p.r2; des.encrypt(p.c1l, p.c1r); des.encrypt(p.c2l, p.c2r); out.push_back(p); } return out; }参数n是明文对数量。注意我先把基值明文存入p.l1等字段然后加密的是c1l系列变量这样密文和明文可以同时保留。实际攻击中明文本身不再需要但保留下来有助于调试你可以检查生成出的明文对是否真的满足指定的dl/dr。mt19937的种子固定能保证每次运行得到相同数据集这对复现别人的攻击结果很有帮助。如果你需要更真实的实验可以把种子改成std::random_device但要记住这会让结果不可复现。3.3 参数说明与常见误区差分分析程式的很多错误不在密码学逻辑而在明文/密文表示的偏差。下面是几个我经常检查的参数参数含义常见误区dl明文左半 32 位差分只设右半差分忘了 Feistel 会交换dr明文右半 32 位差分把差分写进 64 位整数的低 32 位导致端序问题n明文对数量太依赖特征概率忽略了噪声投票targetR5第 6 轮部分解密后应见的差分混入了非活跃 S 盒的位导致候选密钥空间膨胀最容易踩的坑是左右交换。在 3.1 节的实现里每一轮先把旧r赋给新l所以明文差分(dl, dr)经过第一轮后变成(dr, dl xor F_diff(dr))。如果攻击代码里按另一种轮函数方向写密文差分就会对不上。另一个坑是targetR5的位数。把targetR5设成完整 32 位看似更严格但实际中只会让正确密钥和错误密钥都很难匹配因为非活跃 S 盒的输出差分本来就是随机的。通常做法是生成一个 32 位掩码只保留与活跃 S 盒输出对应的比特位。4. 差分攻击实战恢复最后一轮子密钥 K6 的 C 实现4.1 攻击流程与候选密钥空间六轮 DES 的最后一轮子密钥 K6 有 48 位直接枚举会爆内存。但差分特征只激活一个 S 盒所以攻击只针对该 S 盒对应的 6 位子密钥。整个流程分四步读入预先算好的特征获取dl、dr、targetR5和活跃 S 盒编号。用generatePairs生成 N 对选择明文并得到密文对。对每个候选的 6 位密钥k对每个密文对做部分解密检查第 5 轮输出差分是否落在目标位。统计通过检查的次数得票最高的候选即为活跃 S 盒对应的真实子密钥片段。部分解密的方向要特别小心。在 3.1 节的表示中最后一轮加密为L5 上一轮 R4 R5 上一轮 L4 xor F(上一轮 R4, K6)密文是(L5, R5)。解最后一轮时因为L5 R4而R4就是 F 的输入所以可以算出F_input L5 L4 R5 xor F(F_input, K6)攻击者不需要完整解出L4只需要解出与活跃 S 盒相关的输出比特再和第 5 轮期望差分比对。4.2 过滤密文对与子密钥投票代码下面这段代码展示单 S 盒的投票过程。decryptPartial只计算活跃 S 盒对输出的贡献不关心其他 S 盒#include array #include cstdint // 取 32 位输入中第 sboxIndex 个 S 盒的 6 位输入 uint8_t extractSboxInput(uint32_t x, int sboxIndex) { // E 扩展后每个 S 盒输入位来自原 32 位的若干位置 // 这里略去查表返回 0~63 uint64_t e E(x); return (e (6 * sboxIndex)) 0x3F; } // 把某个 S 盒的 4 位输出放回 32 位输出中非活跃位全部为 0 uint32_t placeSboxOutput(uint8_t sboxOut, int sboxIndex) { uint32_t buf[8] {}; buf[sboxIndex] sboxOut; return P_combine(buf); // 按 P 置换的位置放回去 } int runVote(const std::vectorPair pairs, int sboxIndex, uint32_t targetMask, uint32_t targetValue) { std::arrayint, 64 votes{}; for (int k6 0; k6 64; k6) { for (const auto p : pairs) { // 用候选 k6 解最后一轮得到 L4 的活跃位差分 uint8_t in1 extractSboxInput(p.c1l, sboxIndex) ^ k6; uint8_t in2 extractSboxInput(p.c2l, sboxIndex) ^ k6; uint32_t partial1 placeSboxOutput(SBOX(sboxIndex, in1), sboxIndex); uint32_t partial2 placeSboxOutput(SBOX(sboxIndex, in2), sboxIndex); uint32_t l4_diff (p.c1r ^ partial1) ^ (p.c2r ^ partial2); if ((l4_diff targetMask) targetValue) { votes[k6]; } } } int bestKey 0; for (int k 1; k 64; k) { if (votes[k] votes[bestKey]) bestKey k; } return bestKey; }这段代码的关键是extractSboxInput和placeSboxOutput必须严格使用标准 DES 的 E 盒与 P 盒索引。targetMask是只覆盖活跃 S 盒输出位的掩码targetValue是targetR5 targetMask的结果。错误候选密钥由于 S 盒查表结果随机只有约1/2^{bit_count}的概率通过过滤而正确密钥会以特征概率通过因此正确密钥的票数会明显偏高。votes数组长度为 64因为每个 S 盒的 6 位输入密钥共有 2^6 种。最终得到的bestKey是该 S 盒对应的 6 位子密钥片段其他 42 位需要换其他活跃 S 盒或换差分特征继续恢复。4.3 结果验证与信噪比攻击完成后先别急着认为bestKey就是正确密钥。需要看票数分布正确候选的票数应该接近N * p_feature错误候选的平均票数大约等于N / 2^{bit_count}。如果正确候选没有形成明显峰值说明特征概率太低或者明文对数不够。可以打印候选密钥的完整票数直方图来验证。正确密钥通常只比第二名高几个百分点因为差分特征本身是概率性的噪声候选也会偶然匹配。为了提高置信度我会用同一组明文对再攻击一次但把活跃 S 盒换成同一个 S 盒的另一个特征然后比较两次恢复结果是否一致。如果两次得出同一个 6 位密钥片段基本可以认为恢复正确。信噪比的简化估算用下面这个式子S/N ≈ (p_feature * N) / (N / 2^{bit_count})其中bit_count是过滤掩码覆盖的比特数。单 S 盒输出 4 位过滤 4 位时错误候选通过率约 1/16。如果特征概率是 2^-10那么信噪比大约为 2^-10 / 2^-4 1/64这时正确候选只有噪声的 1/6 左右攻击会不稳定。所以实践中通常选择特征概率不低于 2^-8或者同时使用多个特征做交叉验证。5. 从六轮到完整 DES提高成功率与降低复杂度的三个技巧5.1 用 Early Abort 按 S 盒逐块检查部分解密最后一轮时如果同时激活多个 S 盒不要一次性计算完整 32 位输出。正确的做法是按 S 盒分块检查每算出一个 S 盒的输出位就立即比较对应掩码位不匹配就跳过整个候选密钥。这样可以把大量错误候选提前过滤掉减少SBOX_lookup的调用次数。实现上就是把runVote的内层循环拆成先查第一个 S 盒再查第二个最后一个 S 盒通过后才做投票计数。5.2 用 OpenMP 并行化候选密钥循环候选密钥只有 64 个单进程串行可能也就几秒钟但完整恢复 48 位密钥需要多次攻击累计开销不小。常见做法是在k6的 for 循环上加上#pragma omp parallel for for (int k6 0; k6 64; k6) { // 投票逻辑 }需要注意votes数组的并发写。可以让每个线程维护一份局部votes最后再归并避免std::atomic的开销。这样在多核机器上能直接获得接近线性的加速比尤其当pairs很大时效果明显。5.3 用多条差分特征合并投票单个 S 盒特征往往信噪比不足。更稳健的做法是准备多条不同 S 盒的差分特征分别攻击同一组明文对然后把每个候选密钥的得票归一化后相加。由于不同特征对错误候选的随机偏差会互相抵消合并后的峰值比单一特征更容易识别。代价是特征之间的兼容性所有特征必须都覆盖第 1 轮到第 5 轮且targetR5对应的目标位不重叠否则攻击复杂度会上升。实际做时我倾向先用 2 条特征跑通流程再逐渐增加到 4 条观察峰值是否稳定。本文还有配套的精品资源点击获取 六轮DES差分分析：用C++实现S盒差分表与子密钥投票恢复
简介基于C的六轮DES算法差分分析实现面向密码学课程设计与差分密码分析入门者完整呈现选择明文攻击的工程化落地流程。代码按模块划分为四部分6轮DES加解密模块用于产生明密文对与最终验证差分分析表生成模块用于统计输入差分到输出差分的分布明密文对生成与筛选模块用于检查是否满足选择明文攻击条件差分分析主程序负责完成六轮DES的差分破解并展示结果。压缩包共11个文件以C源文件.cpp/.h和Markdown说明为主另有运行结果截图、工程图片及许可证文件整体仅86KB轻量且便于携带。已有238人学习适合作为课程作业参考、实验复现或进一步扩展到更高轮数DES与线性分析的过渡基础。1. 六轮 DES 差分分析为什么是六轮以及这个题在做什么如果你已经写过 C 的 DES 加解密大概率觉得 DES 只是位运算的堆砌但把 DES 看成一组 S 盒查表后进攻它的方式会完全不同。六轮 DES 是经典差分分析的理想靶子轮数少到可以枚举候选子密钥又没有少到像单轮那样可以从密文差直接猜出密钥位。这篇文章要解决的问题很具体给定一对差值固定的明文/密文对如何用 C 实现差分分布表、构造差分特征并对最后一轮子密钥做投票恢复。适合对分组密码有基本概念、想在工程里复现算法而不只是读公式的读者。2. 差分密码分析基础与六轮 DES 的差分特征2.1 DES 轮函数与 F 函数的差分传播差分分析的观测对象是 XOR。在 Feistel 轮中密钥通过异或进入 F 函数而异或不改变两路输入的差分所以密钥位置对差分传播来说是透明的。真正非线性、需要重点处理的是 8 个 S 盒。F 函数由扩展置换 E、8 个 S 盒和置换 P 组成其中只有 S 盒会产生概率性的差分传播。一个 S 盒的差分传播可以用一张 64×16 的表描述每一行对应输入差分 δ每一列对应输出差分 Δ表项是输入差分 δ 出现的次数。标准 DES 算法里每个 S 盒都是 6 位输入、4 位输出所以这张表就是 64 行 16 列。构造这张表不需要密钥只需要把 S 盒当成一个普通映射枚举全部可能的输入对。我在做 C 实现时不会手动去翻 S 盒的差分性质而是先写一个生成差分分布表的小程序。这样既能验证标准参考实现里的 S 盒定义是否抄对也能为后面的特征选择提供数据依据。2.2 用 C 生成 S 盒差分分布表DDT下面这段代码生成 DES 中第一个 S 盒的差分分布表并打印输入差分为0x01时的输出差分分布#include array #include iostream // DES 的 S1 盒定义按 4 行 16 列线性展开 static const std::arrayuint8_t, 64 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 }; int main() { std::arraystd::arrayint, 16, 64 ddt{}; for (int x1 0; x1 64; x1) { for (int x2 0; x2 64; x2) { int din x1 ^ x2; int dout S1[x1] ^ S1[x2]; ddt[din][dout]; } } for (int dout 0; dout 16; dout) { if (ddt[0x01][dout] ! 0) { std::cout delta_out dout count ddt[0x01][dout] \n; } } }逻辑很简单x1和x2穷举 S1 的全部 2^6 个输入它们的输入差分是din输出差分是dout每遇到一次就给对应格子加一。由于输入只有 64 种组合任何一行din的所有列计数之和必然等于 64。对于差分分析来说你关注的是count占 64 的比例这个比例就是该差分路径的条件概率。比如输出差分delta_out...的count...意味着随机输入满足这个差分的概率是count/64。代码里只打印了din0x01的行实际使用时可以循环打印全部行或者把统计结果导出为 CSV 供后续脚本读取。需要注意这张表不是 DES 的胜负手真正麻烦的是如何把单个 S 盒的差分拼接成覆盖多轮的完整特征。因为扩展置换 E 会把相邻 S 盒的输入位串起来一个din并不总能独立落在某个 S 盒上后面会在 2.3 节专门处理。2.3 构造覆盖前 5 轮的差分特征六轮 DES 差分攻击的常见做法是先找一条覆盖第 1 轮到第 5 轮的差分特征然后在第 6 轮做部分解密。原因是最后一轮可以用枚举子密钥的方法剥掉不需要知道完整密钥。差分特征的结构是明文差分(ΔL0, ΔR0)每一轮经过 Feistel 后的差分传播到第 5 轮输出时我们希望看到的目标差分targetR5。一次轮传播可以抽象成下式ΔL_i ΔR_{i-1} ΔR_i ΔL_{i-1} xor ΔF_{i-1}其中ΔF_{i-1}是 S 盒和 P 置换联合贡献的输出差分。由于密钥异或不影响差分ΔF_{i-1}完全由上一轮的右半输入差分和 S 盒的差分分布决定。在 C 里我会把特征存储成一个结构体避免在攻击代码里散落魔数struct DiffPath { uint32_t dl; // 明文左半差分 uint32_t dr; // 明文右半差分 uint32_t targetR5; // 解密第6轮后期望看到的第5轮输出差分 int sboxIndex; // 活跃 S 盒编号0~7 int pairsNeeded; // 成功攻击所需明文对数量的经验值 };targetR5的选取原则是只保留活跃 S 盒对应的输出位其他位全部置零。因为在部分解密时只有活跃 S 盒对应的 6 位子密钥需要枚举其他 S 盒既增加噪声也扩大搜索空间。把targetR5限定到单个 S 盒对应的输出位可以把候选密钥空间从 2^48 降到 2^6这是差分分析能实际跑起来的关键。构造特征这一步我会先用 2.2 节的程序列出每个 S 盒的高概率差分再手工拼一条 5 轮路径。对于六轮 DES一条 5 轮特征的概率通常在 2^-12 到 2^-16 量级意味着选择明文对数 N 至少要大于等于该概率的倒数才能保证真实密钥在投票中有统计优势。3. 在 C 中搭建六轮 DES 加解密与随机明文对生成3.1 六轮 DES 的最小实现差分攻击不需要完整的 DES 密钥调度因为明文对和密文对都是使用固定密钥加密出来的攻击过程只关心最后一轮子密钥。下面这个类实现了六轮 Feistel 加解密的骨架f函数就是标准 DES F 函数具体 E 扩展表、S 盒和 P 置换可以直接从 FIPS 46-3 标准复制。#include cstdint class SixRoundDES { public: explicit SixRoundDES(const uint32_t roundKeys[6]) { for (int i 0; i 6; i) K[i] roundKeys[i]; } // 标准一轮F(R, K) P(S(E(R) xor K)) static uint32_t f(uint32_t r, uint32_t k) { // 1. E 扩展 32-48 // 2. 与子密钥异或 // 3. 8 个 S 盒分别查表输出 4 位拼接为 32 位 // 4. P 置换 uint64_t e E(r); e ^ k; uint32_t s SBOX_lookup(e); return P(s); } void encrypt(uint32_t l, uint32_t r) const { for (int i 0; i 6; i) { uint32_t nl r; uint32_t nr l ^ f(r, K[i]); l nl; r nr; } // 最后一轮不交换输出 (L5, R5) 即可 } private: uint32_t K[6]; static uint64_t E(uint32_t r); // 48 位扩展 static uint32_t SBOX_lookup(uint64_t e); // 8 个 S 盒查表 static uint32_t P(uint32_t s); // 32 位置换 };注意加密结束后我没有做左右交换。标准 DES 的最后一步有交换但差分分析中交换是线性的而且会影响后续部分解密的索引。为了避免混淆我统一约定六轮 DES 的密文就是(L5, R5)不再交换。攻击代码也按这个约定来写。E、SBOX_lookup和P三处实现与标准 DES 完全一致。建议在写攻击代码之前先用一组已知的测试向量验证这个encrypt的行为取L0x12345678, R0x9ABCDEF0六个子密钥都用0x12345678打印每一轮输出与手工 Feistel 推导对照。这个调试步骤很值得做因为后面所有差分投票都依赖部分解密的方向。3.2 随机明文对生成攻击需要选择明文对所以生成器必须能按指定差分(dl, dr)构造大量输入并返回加密后的密文对。常见做法是用std::mt19937生成随机基值再用基值异或差分得到第二个明文#include random #include vector struct Pair { uint32_t l1, r1, l2, r2; uint32_t c1l, c1r, c2l, c2r; }; std::vectorPair generatePairs(int n, const DiffPath path, const SixRoundDES des) { std::mt19937 rng(0x1D3A5EED); std::vectorPair out; out.reserve(n); while ((int)out.size() n) { uint32_t l rng(); uint32_t r rng(); Pair p; p.l1 l; p.r1 r; p.l2 l ^ path.dl; p.r2 r ^ path.dr; p.c1l p.l1; p.c1r p.r1; p.c2l p.l2; p.c2r p.r2; des.encrypt(p.c1l, p.c1r); des.encrypt(p.c2l, p.c2r); out.push_back(p); } return out; }参数n是明文对数量。注意我先把基值明文存入p.l1等字段然后加密的是c1l系列变量这样密文和明文可以同时保留。实际攻击中明文本身不再需要但保留下来有助于调试你可以检查生成出的明文对是否真的满足指定的dl/dr。mt19937的种子固定能保证每次运行得到相同数据集这对复现别人的攻击结果很有帮助。如果你需要更真实的实验可以把种子改成std::random_device但要记住这会让结果不可复现。3.3 参数说明与常见误区差分分析程式的很多错误不在密码学逻辑而在明文/密文表示的偏差。下面是几个我经常检查的参数参数含义常见误区dl明文左半 32 位差分只设右半差分忘了 Feistel 会交换dr明文右半 32 位差分把差分写进 64 位整数的低 32 位导致端序问题n明文对数量太依赖特征概率忽略了噪声投票targetR5第 6 轮部分解密后应见的差分混入了非活跃 S 盒的位导致候选密钥空间膨胀最容易踩的坑是左右交换。在 3.1 节的实现里每一轮先把旧r赋给新l所以明文差分(dl, dr)经过第一轮后变成(dr, dl xor F_diff(dr))。如果攻击代码里按另一种轮函数方向写密文差分就会对不上。另一个坑是targetR5的位数。把targetR5设成完整 32 位看似更严格但实际中只会让正确密钥和错误密钥都很难匹配因为非活跃 S 盒的输出差分本来就是随机的。通常做法是生成一个 32 位掩码只保留与活跃 S 盒输出对应的比特位。4. 差分攻击实战恢复最后一轮子密钥 K6 的 C 实现4.1 攻击流程与候选密钥空间六轮 DES 的最后一轮子密钥 K6 有 48 位直接枚举会爆内存。但差分特征只激活一个 S 盒所以攻击只针对该 S 盒对应的 6 位子密钥。整个流程分四步读入预先算好的特征获取dl、dr、targetR5和活跃 S 盒编号。用generatePairs生成 N 对选择明文并得到密文对。对每个候选的 6 位密钥k对每个密文对做部分解密检查第 5 轮输出差分是否落在目标位。统计通过检查的次数得票最高的候选即为活跃 S 盒对应的真实子密钥片段。部分解密的方向要特别小心。在 3.1 节的表示中最后一轮加密为L5 上一轮 R4 R5 上一轮 L4 xor F(上一轮 R4, K6)密文是(L5, R5)。解最后一轮时因为L5 R4而R4就是 F 的输入所以可以算出F_input L5 L4 R5 xor F(F_input, K6)攻击者不需要完整解出L4只需要解出与活跃 S 盒相关的输出比特再和第 5 轮期望差分比对。4.2 过滤密文对与子密钥投票代码下面这段代码展示单 S 盒的投票过程。decryptPartial只计算活跃 S 盒对输出的贡献不关心其他 S 盒#include array #include cstdint // 取 32 位输入中第 sboxIndex 个 S 盒的 6 位输入 uint8_t extractSboxInput(uint32_t x, int sboxIndex) { // E 扩展后每个 S 盒输入位来自原 32 位的若干位置 // 这里略去查表返回 0~63 uint64_t e E(x); return (e (6 * sboxIndex)) 0x3F; } // 把某个 S 盒的 4 位输出放回 32 位输出中非活跃位全部为 0 uint32_t placeSboxOutput(uint8_t sboxOut, int sboxIndex) { uint32_t buf[8] {}; buf[sboxIndex] sboxOut; return P_combine(buf); // 按 P 置换的位置放回去 } int runVote(const std::vectorPair pairs, int sboxIndex, uint32_t targetMask, uint32_t targetValue) { std::arrayint, 64 votes{}; for (int k6 0; k6 64; k6) { for (const auto p : pairs) { // 用候选 k6 解最后一轮得到 L4 的活跃位差分 uint8_t in1 extractSboxInput(p.c1l, sboxIndex) ^ k6; uint8_t in2 extractSboxInput(p.c2l, sboxIndex) ^ k6; uint32_t partial1 placeSboxOutput(SBOX(sboxIndex, in1), sboxIndex); uint32_t partial2 placeSboxOutput(SBOX(sboxIndex, in2), sboxIndex); uint32_t l4_diff (p.c1r ^ partial1) ^ (p.c2r ^ partial2); if ((l4_diff targetMask) targetValue) { votes[k6]; } } } int bestKey 0; for (int k 1; k 64; k) { if (votes[k] votes[bestKey]) bestKey k; } return bestKey; }这段代码的关键是extractSboxInput和placeSboxOutput必须严格使用标准 DES 的 E 盒与 P 盒索引。targetMask是只覆盖活跃 S 盒输出位的掩码targetValue是targetR5 targetMask的结果。错误候选密钥由于 S 盒查表结果随机只有约1/2^{bit_count}的概率通过过滤而正确密钥会以特征概率通过因此正确密钥的票数会明显偏高。votes数组长度为 64因为每个 S 盒的 6 位输入密钥共有 2^6 种。最终得到的bestKey是该 S 盒对应的 6 位子密钥片段其他 42 位需要换其他活跃 S 盒或换差分特征继续恢复。4.3 结果验证与信噪比攻击完成后先别急着认为bestKey就是正确密钥。需要看票数分布正确候选的票数应该接近N * p_feature错误候选的平均票数大约等于N / 2^{bit_count}。如果正确候选没有形成明显峰值说明特征概率太低或者明文对数不够。可以打印候选密钥的完整票数直方图来验证。正确密钥通常只比第二名高几个百分点因为差分特征本身是概率性的噪声候选也会偶然匹配。为了提高置信度我会用同一组明文对再攻击一次但把活跃 S 盒换成同一个 S 盒的另一个特征然后比较两次恢复结果是否一致。如果两次得出同一个 6 位密钥片段基本可以认为恢复正确。信噪比的简化估算用下面这个式子S/N ≈ (p_feature * N) / (N / 2^{bit_count})其中bit_count是过滤掩码覆盖的比特数。单 S 盒输出 4 位过滤 4 位时错误候选通过率约 1/16。如果特征概率是 2^-10那么信噪比大约为 2^-10 / 2^-4 1/64这时正确候选只有噪声的 1/6 左右攻击会不稳定。所以实践中通常选择特征概率不低于 2^-8或者同时使用多个特征做交叉验证。5. 从六轮到完整 DES提高成功率与降低复杂度的三个技巧5.1 用 Early Abort 按 S 盒逐块检查部分解密最后一轮时如果同时激活多个 S 盒不要一次性计算完整 32 位输出。正确的做法是按 S 盒分块检查每算出一个 S 盒的输出位就立即比较对应掩码位不匹配就跳过整个候选密钥。这样可以把大量错误候选提前过滤掉减少SBOX_lookup的调用次数。实现上就是把runVote的内层循环拆成先查第一个 S 盒再查第二个最后一个 S 盒通过后才做投票计数。5.2 用 OpenMP 并行化候选密钥循环候选密钥只有 64 个单进程串行可能也就几秒钟但完整恢复 48 位密钥需要多次攻击累计开销不小。常见做法是在k6的 for 循环上加上#pragma omp parallel for for (int k6 0; k6 64; k6) { // 投票逻辑 }需要注意votes数组的并发写。可以让每个线程维护一份局部votes最后再归并避免std::atomic的开销。这样在多核机器上能直接获得接近线性的加速比尤其当pairs很大时效果明显。5.3 用多条差分特征合并投票单个 S 盒特征往往信噪比不足。更稳健的做法是准备多条不同 S 盒的差分特征分别攻击同一组明文对然后把每个候选密钥的得票归一化后相加。由于不同特征对错误候选的随机偏差会互相抵消合并后的峰值比单一特征更容易识别。代价是特征之间的兼容性所有特征必须都覆盖第 1 轮到第 5 轮且targetR5对应的目标位不重叠否则攻击复杂度会上升。实际做时我倾向先用 2 条特征跑通流程再逐渐增加到 4 条观察峰值是否稳定。本文还有配套的精品资源点击获取