★ FEATURED ARTICLE 简介围绕 Howard M. Heys 发表于 Cryptologia 的经典教程《A Tutorial on Linear and Differential Cryptanalysis》整理而成的密码学入门资料面向具备基础编程能力、希望直观理解差分分析与线性分析原理的初学者。资料以 5 轮 16 比特玩具密码为主线把差分特征传播、区分器构造、线性逼近偏差分析与末轮密钥恢复等关键环节讲得较为清楚并配有可编译运行的 C 实现便于读者在读懂推导后复现攻击流程观察明文结构、样本规模与轮数对成功率的影响。压缩包共 6 个文件约 662KB含 1 篇 PDF 教程、2 份 C 源码、2 个可执行程序及 1 份说明文本分别服务于原理阅读、代码研读、运行验证与操作提示。已有 553 人学习下载适合作为分组密码分析课程的课外补充也能为后续研读更深入的差分与线性分析文献建立直观基础对入门阶段的实验复现尤有帮助可降低公式与代码之间的理解门槛。1. 从一张 16×16 的表说起第一次啃差分分析我盯着一张 S 盒差分分布表看了半小时没看明白直到把 C 那段三重循环敲完跑起来看着DDT[0xB][0x2]稳稳打印出 8才反应过来讲义里那句「概率 1/2」是怎么算出来的。这份资源走的就是这条路两篇差分分析与线性分析的入门长文配一套能编译运行的 C 实现把 DDT、LAT、特征搜索、末轮密钥恢复全部落成可打印、可对拍的代码。它适合已经会写 C、看得懂异或和位运算但每次读到「特征概率」「偏差」就卡住的开发者。讲义不长代码也不多胜在两边能对上号表里的每个数字你都能自己重新算一遍。2. 资源结构与工程骨架两份讲义、一套 C 源码以及一次编译打开这份资源先别急着看攻击脚本从结构看起会舒服很多。资源分成两块一块是讲义差分分析和线性分析各一条线各自按「定义 → S 盒统计表 → 单轮特征 → 多轮拼接 → 密钥恢复 → 复杂度估算」推进另一块是 C 实现按讲义章节切成几个独立模块每个模块都能单独跑、单独验证。两块的对应关系是这份资源最有价值的地方——讲义里出现的每张表、每个概率代码里都有一个函数把它算出来。我一般拿到这类教学资源第一件事不是读而是先编译、先让它输出点东西有了输出再回头读讲义效率会高很多。后面几节就按这个顺序走先认目录再编译最后用几个不变量自检。2.1 两份讲义的分工一条差分线一条线性线差分篇解决的是「输入差分会以多大概率造成某个输出差分」。它的核心对象是差分分布表围绕这张表展开的内容包括为什么要选高概率转移、怎么把单轮高概率转移拼成多轮特征、多轮概率为什么要连乘、以及拿到一条概率够高的特征之后怎么从倒数第二轮倒推最后一轮的子密钥。这条线逻辑是顺的从计数出发最后落到计数中间不需要太多概率论工具所以放在前面比较友好。线性篇解决的是「输入掩码和输出掩码之间存在一个多强的线性逼近」。它的核心对象是线性逼近表展开路径是线性逼近的偏差定义 → 单轮最大偏差掩码 → 多轮偏差的拼接规则堆积引理→ 用偏差最大的掩码做统计判决。这条线比差分线抽象难在「偏差」这个词的口径——不同讲义有的减 8有的减 16有的干脆存原始计数混着看必然判断错倍率。两篇讲义之间有一处呼应点值得留意差分是「异或差」线性是「奇偶校验」两者都不是在追踪具体的比特值而是在追踪某种统计性质。想明白这一点后面的代码就不容易写歪。2.2 源码目录六个文件对应讲义的四节这份实现没有用任何第三方库纯标准 C目录结构也很朴素文件职责对应讲义位置src/box.h/box.cpp4 bit S 盒、逆盒、位置换 P、密钥扩展预备知识src/ddt.cpp差分分布表构建与最大转移查询差分篇第 2 节src/lat.cpp线性逼近表构建、快速 Walsh 变换线性篇第 2 节src/spn.cppSPN 加密/解密、轮函数两篇共用的实验对象src/trail.cpp单轮展开、多轮特征递归搜索差分篇第 3 节 / 线性篇第 3 节src/attack.cpp末轮部分密钥打分与排序差分篇第 4 节 / 线性篇第 4 节src/main.cpp命令行入口子命令分发——实验对象是一个 16 bit 分组、4 个 4 bit S 盒并行、带位置换 P 的 SPN。选这个参数不是随便定的4 bit 盒让 DDT 和 LAT 都是 16×16刚好能整张打印出来对照16 bit 分组意味着明文空间只有 65536暴力枚举在调试阶段完全够用你可以随时拿暴力结果去校验统计结果。这个「小到能看清」的尺寸是整份资源最实用的设计。2.3 一次编译跑通从 g 到第一条命令不需要 CMake直接一行 g 就能过对新手来说少一层障碍# 全部源码都在 src/ 下无外部依赖 g -stdc17 -O2 -Wall -Wextra \ src/main.cpp src/box.cpp src/ddt.cpp src/lat.cpp \ src/spn.cpp src/trail.cpp src/attack.cpp \ -o spn # 先看子命令确认编译产物正常 ./spn --help # 打印 S 盒差分分布表 ./spn ddt # 打印线性逼近表 ./spn lat # 跑一次 4 轮差分密钥恢复实验4096 组明文对固定随机种子便于复现 ./spn diff-attack --rounds 4 --pairs 4096 --seed 20240501-O2不是可有可无的特征搜索是递归加分支不开优化跑 4 轮以上会明显卡顿。--seed这个参数建议每次都显式带上这类统计实验最怕结果不可复现出问题时连「到底是不是随机性导致的」都判断不了那真是连后悔药都没得吃。--pairs决定采样规模256 组时结果基本靠运气4096 组以后正确子密钥才会稳定领先。跑起来之后ddt子命令会打出整张 16×16 的计数表。建议第一眼先看DDT[0][0]是不是 16、每一行加起来是不是 16——这两条能立刻判断出实现的计数口径对不对。2.4 先自检再谈分析三个不变量跑通不等于跑对。我习惯在动攻击脚本之前先加一段自检把已知的数学不变量钉死。S 盒是双射的时候差分分布表和线性逼近表都有硬性约束违反了就说明代码有问题而不用等到分析结果不对再回头查。// 差分分布表自检每一行固定输入差分的计数和恒为 16 bool checkDDT(const Table16 ddt) { for (int din 0; din 16; din) { int rowSum 0; for (int dout 0; dout 16; dout) rowSum ddt[din][dout]; if (rowSum ! 16) { // 16 S 盒定义域大小 std::printf(DDT row %X sum %d\n, din, rowSum); return false; } } return true; } // 线性逼近表自检零掩码行/列全零每行平方和为 644 bit 盒 bool checkLAT(const Table16 lat) { if (lat[0][0] ! 8) return false; // 零掩码恒成立偏差记作 8 for (int a 0; a 16; a) { int sq 0; for (int b 0; b 16; b) { if (a ! 0 b 0 lat[a][b] ! 0) return false; sq lat[a][b] * lat[a][b]; } if (sq ! 64) { std::printf(LAT row %X sq %d\n, a, sq); return false; } } return true; }这三条约束分别是DDT 行和恒等于 S 盒定义域大小LAT 的零掩码行和零掩码列除[0][0]外全为 0因为双射 S 盒的输出奇偶性均匀分布LAT 每行平方和等于 64来自 Walsh 变换的 Parseval 关系。提示如果你把 S 盒换成 8 bit 的盒这三个数字要跟着改行和变成 256LAT 每行平方和变成 65536lat[0][0]变成 128。尺寸一变很多硬编码常数就是翻车源头。3. 差分分析链路从 DDT 到末轮密钥打分差分分析在代码里其实是三段互不耦合的活算表、搜特征、打分。分开写的好处是每一段都能单独验证——表算错了特征一定不对特征不对打分一定发散。我第一次写的时候把三段揉在一个函数里结果输出不对完全不知道锅在哪一段最后花了一晚上才定位到是置换方向写反。3.1 差分的口径DDT 是计数表不是概率表先统一口径。对 4 bit S 盒S输入差分din、输出差分dout差分分布表定义为DDT[din][dout] #{ x ∈ [0,16) | S(x) ⊕ S(x ⊕ din) dout }关键在于x取满 0 到 15 全部 16 个值也就是有序对。这样当din 0时所有 16 个x都给出dout 0该行DDT[0][0] 16当din ! 0时x和x ⊕ din会成对出现同一对的两端各贡献一次所以某个dout的计数一定是对称的偶数。行和恒为 16 这条是后面所有概率的来源P(dout | din) DDT[din][dout] / 16。很多人第一次手算容易只枚举一半的x比如只取x x ⊕ din得到的结果正好是应有值的一半然后概率算出 1/4 而不是 1/2接着照着这个错误概率去估算数据量成倍偏大。这不是玄学纯粹是口径没对齐。3.2 C 实现 DDT 并读出可用转移有了定义代码几乎是逐字翻译#include array #include cstdint #include cstdio // 4 bit - 4 bit 示例 S 盒与讲义里的表保持一致 constexpr std::arrayuint8_t, 16 SBOX { 0xE,0x4,0xD,0x1,0x2,0xF,0xB,0x8, 0x3,0xA,0x6,0xC,0x5,0x9,0x0,0x7 }; using Table16 std::arraystd::arrayint, 16, 16; Table16 buildDDT(const std::arrayuint8_t, 16 s) { Table16 ddt{}; for (int din 0; din 16; din) { for (int x 0; x 16; x) { // x 取满 16 个值天然构成有序对计数口径与讲义一致 uint8_t dout s[x] ^ s[x ^ din]; ddt[din][dout] 1; } } return ddt; } // 查某一行里计数最大的若干转移用来挑高概率特征起点 void topTransitions(const Table16 ddt, int din, int keep 3) { std::arrayint, 16 order{}; for (int i 0; i 16; i) order[i] i; std::sort(order.begin(), order.end(), [](int a, int b) { return ddt[din][a] ddt[din][b]; }); for (int i 0; i keep; i) { int dout order[i]; std::printf(din%X - dout%X count%d p%.4f\n, din, dout, ddt[din][dout], ddt[din][dout] / 16.0); } }buildDDT的时间复杂度是 16×16对 4 bit 盒根本不用考虑效率所以代码优先写清楚而不是写快。topTransitions是配套的小工具作用是快速回答「这个输入差分最可能变到哪个输出差分」。以示例 S 盒跑一遍输入差分0xB那一行会打出dout0x2, count8, p0.5000。这就解释了讲义里那条「概率 1/2 的单轮特征」——不是凑出来的数字是从表里直接读出来的。换成 8 bit 盒时count8会变成count128因为它们都对应「恰好一半」这个最大化情形。3.3 多轮特征递归展开、概率剪枝与 P 置换单轮转移概率再高也就 1/2要打多轮必须把若干轮的转移串起来总概率是各轮概率的乘积。问题在于搜索空间4 个并行 S 盒每个都有多个候选输出差分四轮下来分支爆炸。常见的做法是深度优先加剪枝剪枝条件用「当前累计概率已经低于目前最优」// 位置换 P输出第 i 位取自输入第 P[i] 位 constexpr std::arrayint, 16 P {0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15}; uint16_t permute(uint16_t x) { uint16_t y 0; for (int i 0; i 16; i) y | ((x P[i]) 1u) i; // 先提升到 unsigned 再移位 return y; } // 展开一轮对每个活跃半字节枚举输出差分返回输出差分, 本轮概率 void expandRound(uint16_t din, const Table16 ddt, std::vectorstd::pairuint16_t, double out) { out.assign(1, {0u, 1.0}); for (int i 0; i 4; i) { uint8_t sub (din (4 * i)) 0xF; if (sub 0) continue; // 该盒输入差分为 0输出必然为 0 std::vectorstd::pairuint16_t, double next; for (auto [cur, prob] : out) { for (int dout 0; dout 16; dout) { int cnt ddt[sub][dout]; if (cnt 0) continue; uint16_t nd cur | (uint16_t(dout) (4 * i)); next.push_back({nd, prob * cnt / 16.0}); } } out.swap(next); } }permute里那句「先提升到 unsigned 再移位」不是多余的uint16_t参与移位时会被整型提升成int如果最高位被解释成符号位x 15在某些写法下会得到全 1 而不是 0 或 1。这类坑在调试统计实验时特别隐蔽因为大部分数据下结果看着都是对的。expandRound只处理 S 层P 置换在外层单独做。原因是 P 是纯位操作对异或差分同样线性P(a ⊕ b) P(a) ⊕ P(b)所以差分穿过多轮时直接调用permute就行不需要求逆。这一点和线性分析那边不一样那边掩码要被 P 反向搬运必须用P^{-1}写混了就会出现「概率算得挺对但特征跑不通」的诡异局面。struct Trail { std::vectoruint16_t diff; // 每轮进入 S 层之前的差分 double prob 0.0; }; void searchTrail(uint16_t cur, int round, int rounds, double p, const Table16 ddt, Trail now, Trail best) { if (round rounds) { if (p best.prob) { best now; best.prob p; } return; } std::vectorstd::pairuint16_t, double outs; expandRound(cur, ddt, outs); for (auto [d, q] : outs) { double np p * q; if (np best.prob) continue; // 比当前最优还差直接砍掉 now.diff.push_back(permute(d)); // 过 P作为下一轮输入差分 searchTrail(permute(d), round 1, rounds, np, ddt, now, best); now.diff.pop_back(); } }三个参数值得说cur是当前轮进入 S 层的差分p是到目前为止的累计概率best是全局最优解引用传递边走边更新。剪枝条件用严格小于而不是小于等于是为了不误杀概率相同但路径不同的候选——概率相同不代表后续展开的潜力相同。注意这个搜索是精确搜索轮数一上去就会指数爆炸。4 轮 4 个盒勉强能跑想试 6 轮以上就得改成保留 top-K 的束搜索或者先按活跃盒数量做一轮粗筛。3.4 末轮部分密钥恢复给 16 个候选打分有了高概率特征最后一步是最有工程味道的一步拿这个特征去检验真实数据反推最后一轮的子密钥。思路很直接——特征只覆盖前面几轮最后一轮不做 P 置换密文的某个半字节就等于S(u) ⊕ k所以对每个候选k把密文半字节异或掉k再查逆盒就能还原出最后一轮的 S 层输入u然后看u的差分是否符合特征预测。std::arrayuint8_t, 16 invertSbox(const std::arrayuint8_t, 16 s) { std::arrayuint8_t, 16 inv{}; for (int x 0; x 16; x) inv[s[x]] static_castuint8_t(x); return inv; } // pairs: 采样得到的明文, 密文对已按特征的输入差分筛过 // idx: 最后一轮要猜的半字节下标expectDin: 特征预测的该盒输入差分 std::arrayint, 16 scoreLastNibble( const std::vectorstd::pairuint16_t, uint16_t pairs, int idx, uint8_t expectDin) { const auto INV invertSbox(SBOX); std::arrayint, 16 score{}; for (int guess 0; guess 16; guess) { int hit 0; for (auto pr : pairs) { uint8_t c1 (pr.second (4 * idx)) 0xF; uint8_t c2 (pr.second (4 * idx)) 0xF; uint8_t u1 INV[c1 ^ guess]; // 还原最后一轮 S 层输入 uint8_t u2 INV[c2 ^ guess]; if ((u1 ^ u2) expectDin) hit; } score[guess] hit; } return score; }参数说明idx取 0 到 3对应四个并行 S 盒expectDin是特征中进入最后一轮时该盒的输入差分返回的 16 个计数里正确密钥应该明显领先于其他候选差距随采样量增大而拉大。实践中正确的做法是先用一条概率较弱的特征做粗筛取排名前几的候选再用一条更强的特征对这些候选做二次判别。一把梭只靠单条特征在采样量不够的时候最高分抖来抖去看着像代码有 bug其实是数据量不够——这个坑我在第一次跑的时候踩得很瓷实。4. 线性分析链路LAT、掩码搜索与堆积引理线性分析和差分分析看着对称实际写起来差别不小。差分那边追踪的是「两个值之间的差」天然适合用计数线性这边追踪的是「单个值的奇偶性」所有结论都建立在统计偏差上同一份数据要反复采样才能看出倾向。代码结构因此也不同差分是「算表 → 搜特征 → 打分」线性是「算表 → 算偏差 → 估数据量 → 打分」中间多了数据量估计这一步。4.1 线性逼近的偏差口径与 Walsh 变换对 4 bit S 盒输入掩码a、输出掩码b定义W(a,b) Σ_{x∈[0,16)} (-1)^{ a·x ⊕ b·S(x) }其中a·x表示按位与之后取奇偶校验即 popcount 的奇偶。W取值在 -16 到 16 之间W 16表示a·x b·S(x)对所有x恒成立W 0表示毫无关系。线性逼近表一般存LAT[a][b] W(a,b) / 2范围 -8 到 8含义是「等式成立次数减 8」也就是偏差乘 16。三种口径必须挑一种并贯彻到底存W-16~16、存W/2-8~8、存成立次数0~16。讲义里写「偏差 1/8」的时候对应的是LAT 2。我见过把W/2当成概率直接拿去算数据量的写法得到的结果差了一个量级以上跑起来就是「怎么采样都不收敛」。4.2 两种 LAT 实现按定义数和快速 Walsh慢速版直接按定义数和讲义对拍最方便inline int parity(unsigned v) { return __builtin_popcount(v) 1; } // 直接按定义数 a·x b·S(x) 成立的 x 有多少个减去 8 Table16 buildLATSlow(const std::arrayuint8_t, 16 p a hrefhttps://download.csdn.net/download/peterhao89/5016587 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p
阅读完成 · 觉得有帮助？
