★ FEATURED ARTICLE 简介这份资源面向密码学与信息安全方向的初学者围绕Howard M. Heys教授发表于Cryptologia的经典教程《A Tutorial on Linear and Differential Cryptanalysis》展开借助一个仅5轮、16比特的玩具密码把差分分析与线性分析的原理讲得深入浅出。压缩包共6个文件约662KB包含教程PDF原文、线性分析与差分分析的C源码及对应可执行程序另有文件说明文本便于读者边读论文边动手复现算法直观理解两种经典攻击方法的推导与实现过程。目前已有553人学习下载。对于刚接触分组密码攻击的读者而言这份材料既能提供权威的入门理论讲解又能通过可运行的代码验证分析结果是打通从公式推导到程序实现之间认知断层的实用起点适合作为课程学习或自学密码分析的配套实践资料。1. 差分分析入门从 S 盒差分分布表到 C 实现这份资源把密码学门槛拆了很多做安全或后端的同行第一次听到「差分分析」「线性分析」是在论文摘要里翻两页就被 S 盒、活性 S 盒、特征概率这些词劝退。这份资源不一样它是一份面向入门者的差分分析与线性分析讲义配了一套可直接编译运行的 C 实现把分组密码最核心的两类分析方法从数学定义一路落到代码。它解决的不是「看懂一个公式」而是「自己能跑出一张差分分布表、能算出一条差分特征的传播概率、能验证一个简化密码的抵抗强度」。适合三类人想补密码学分析基础的开发、做安全评估需要动手验证的工程师、以及被课程设计卡住的学生。我拆完这套代码后最大的感受是它把黑匣子拆成了可调试的白盒。2. 差分分析的核心机制S 盒差分分布表怎么算、怎么读差分分析的起点不是密码算法本身而是非线性部件——通常是 S 盒。整个方法的逻辑链条是明文差分经过线性层保持不变或可预测地扩散经过 S 盒时按差分分布表的概率输出某个输出差分把所有轮的概率乘起来就得到一条差分特征的传播概率。理解这条链关键在两张表差分分布表DDT和线性逼近表LAT。这一章先把 DDT 讲透因为它是后面所有代码的基础。2.1 差分分布表的数学定义与手工推演设 S 盒是 n 比特输入到 n 比特输出的映射 S(x)。对输入差分 Δin 和输出差分 ΔoutDDT 的第 (Δin, Δout) 项定义为满足 S(x) ⊕ S(x ⊕ Δin) Δout 的 x 的个数。注意这里 x 遍历所有 2^n 个可能输入所以每一项是 0 到 2^n 之间的整数。把每一项除以 2^n就得到条件概率 P(Δout | Δin)。拿一个 4 比特 S 盒举例输入 16 种对每个 Δin 遍历 16 个 x统计输出差分。手工算一遍你会发现两个规律第一Δin 0 时只有 Δout 0 有计数 16其余为 0第二DDT 关于主对角线不对称但每一行的和恒等于 2^n。这两个性质是后面写代码时验证正确性的天然断言。提示DDT 里计数越大说明该差分路径越「容易」发生差分分析就是找计数最大的那条路径。2.2 用 C 生成 DDT 并验证行和下面这段代码是资源里 DDT 生成的核心逻辑我按自己的习惯补了断言和输出格式。它接收一个 S 盒数组输出二维计数表。#include vector #include cstdint #include cassert #include iostream // sbox: 长度为 2^n 的 S 盒元素为 n 比特输出 // 返回 DDTddt[din][dout] 满足条件的输入个数 std::vectorstd::vectorint buildDDT(const std::vectoruint8_t sbox) { int n 0; while ((1 n) (int)sbox.size()) n; // 推导比特宽度 int size 1 n; std::vectorstd::vectorint ddt(size, std::vectorint(size, 0)); for (int din 0; din size; din) { for (int x 0; x size; x) { int x2 x ^ din; // 配对的另一个输入 int dout sbox[x] ^ sbox[x2]; // 输出差分 ddt[din][dout]; } // 断言每一行的计数和必须等于 2^n int rowSum 0; for (int dout 0; dout size; dout) rowSum ddt[din][dout]; assert(rowSum size); } return ddt; }逻辑说明外层循环固定输入差分 din内层遍历所有 x用异或算出配对输入 x2再对两个 S 盒输出异或得到 dout最后在对应位置累加。参数说明sbox 必须是 2 的幂长度元素值不能超过 size-1否则异或结果会越界。断言那行是血泪经验——我见过有人把 S 盒写成 0 起始但长度填错DDT 行和不对却浑然不觉后面所有概率全错。2.3 从 DDT 读出差分特征概率有了 DDT一条 r 轮差分特征的概率就是各轮概率的乘积。单轮概率 ddt[Δin][Δout] / 2^n。资源里给了一个简化 SPN 结构的例子4 轮特征概率算下来是 2^-12 量级。这个数字意味着什么意味着理论上需要约 2^12 对明文才能以较高信噪比区分正确密钥。实际攻击里还要考虑差分特征的聚类效应但入门阶段先把单条路径算准。我一般会写一个小函数把概率转成以 2 为底的指数方便比较#include cmath // 返回 log2(概率)避免浮点下溢 double log2Prob(int count, int n) { return std::log2((double)count) - n; }参数说明count 是 DDT 里的计数值n 是 S 盒比特宽度。用对数表示的好处是多轮概率相乘变成指数相加不会因为轮数多而变成 0。这个技巧在写多轮特征搜索时几乎是标配。3. 线性分析的核心机制线性逼近表与偏差的 C 计算差分分析看的是差分传播线性分析看的是输入输出比特的线性相关性。两者对偶但线性分析里有个容易翻车的点偏差bias和相关性correlation不是一回事很多入门代码把两者混用导致最后算出来的优势符号都反了。这一章把 LAT 的构造、偏差的定义、以及掩码的选取讲清楚。3.1 线性逼近表的定义与 Walsh 变换线性逼近表 LAT 的第 (a, b) 项定义为满足 a·x b·S(x) 的 x 的个数减去 2^(n-1)其中 a 是输入掩码b 是输出掩码· 是比特内积异或后求奇偶。这个值就是偏差乘以 2^n。等价地LAT 可以用 Walsh-Hadamard 变换从 S 盒的真值表快速算出复杂度从 O(2^(2n)) 降到 O(n·2^n)。资源里两种实现都给了暴力版适合理解定义Walsh 版适合实际用。我建议新手先跑暴力版把每个 (a,b) 对应的计数打印出来和手工算的小 S 盒对一遍确认理解无误再换快速版。3.2 暴力构造 LAT 的 C 实现#include vector #include cstdint // 计算比特内积的奇偶返回 0 或 1 int parity(uint32_t v) { v ^ v 16; v ^ v 8; v ^ v 4; v ^ v 2; v ^ v 1; return v 1; } // 暴力构造 LATlat[a][b] 偏差 * 2^n std::vectorstd::vectorint buildLAT(const std::vectoruint8_t sbox) { int n 0; while ((1 n) (int)sbox.size()) n; int size 1 n; std::vectorstd::vectorint lat(size, std::vectorint(size, 0)); for (int a 0; a size; a) { for (int b 0; b size; b) { int count 0; for (int x 0; x size; x) { // a·x 与 b·S(x) 相等则计数 if (parity(a x) parity(b sbox[x])) count; } lat[a][b] count - (size / 2); // 减去 2^(n-1) 得偏差*2^n } } return lat; }逻辑说明三层循环分别遍历输入掩码 a、输出掩码 b、所有输入 x用 parity 函数算内积奇偶相等就累加最后减去 2^(n-1)。参数说明a 和 b 的取值范围是 0 到 2^n - 1parity 函数用的是标准的位运算折叠比逐位循环快。注意 lat[a][b] 可能是负数负偏差表示线性关系取反这在后面算多轮线性特征时符号必须保留。3.3 多轮线性特征的偏差叠加单轮线性逼近的偏差记作 ε多轮串联时如果各轮相互独立总偏差近似等于各轮偏差乘积的 2^(r-1) 倍r 为轮数。这个公式是线性分析里最容易记错的地方。资源里用 3 轮例子演示了推导我把它整理成代码里的累乘逻辑// biases: 每轮的偏差已归一化为 [-0.5, 0.5] // 返回多轮总偏差的近似值 double combineBias(const std::vectordouble biases) { double prod 1.0; for (double e : biases) prod * (2 * e); // 每轮贡献 2*ε return prod / 2.0; // 最后除以 2 }参数说明biases 里存的是归一化偏差即 LAT 值除以 2^n。那个 2 倍因子来自 piling-up 引理漏掉它总偏差会差一个 2^(r-1) 的系数攻击需要的明文量估算就全偏了。我踩过这个坑当时算出来需要的明文量比实际少了一个数量级调了半天才发现是公式记漏了。4. 避坑与排查差分/线性分析实现里最容易翻车的五处这套代码逻辑不算复杂但密码学实现的坑往往不在语法而在定义和边界。下面五条是我自己复现和帮人排查时反复遇到的按「现象 → 原因 → 解决」写。4.1 DDT 行和不为 2^n现象跑断言直接挂掉或者去掉断言后概率算出来大于 1。原因S 盒数组长度不是 2 的幂或者元素值超出了 n 比特范围导致 x2 越界访问到未初始化内存。解决在 buildDDT 入口加长度和值域检查长度必须是 2 的幂每个元素必须小于长度。别嫌麻烦这个检查能省你两小时。4.2 线性分析偏差符号搞反现象多轮偏差算出来符号和论文对不上攻击时密钥候选排序完全颠倒。原因parity 函数返回的是 0/1而偏差定义里相等计数减 2^(n-1) 后负值代表线性关系取反很多实现把负偏差直接取了绝对值。解决全程保留符号只在最后比较优势时看绝对值。中间任何一步取绝对值都会让多轮叠加的符号逻辑失效。4.3 多轮概率用浮点直接连乘下溢现象轮数一多概率变成 0日志里全是 0。原因每轮概率小于 1十几轮连乘后超出 double 的下溢阈值。解决改用 log2 表示乘法变加法最后需要真实概率时再 exp2 还原。前面给的 log2Prob 就是干这个的。4.4 把差分特征概率当成攻击成功率现象算出特征概率 2^-12就以为 2^12 对明文一定能攻破。原因特征概率只是单条路径的传播概率实际攻击还受信噪比、密钥计数、错误配对影响。解决入门阶段先把特征概率算准理解它和攻击数据复杂度的区别别急着下结论。资源里专门有一节讲这个区别值得细读。4.5 S 盒比特宽度推导写死现象换一个 8 比特 S 盒代码还算 4 比特结果全错。原因n 被硬编码成 4。解决用 while 循环从数组长度推导 n或者直接传参。我一般会在函数签名里加一个 n 参数并加断言 (1n)sbox.size()双保险。5. 进阶用法用这套 C 代码验证自定义 S 盒的抵抗强度把基础跑通之后这套资源真正的价值在于它能当验证工具用。你设计或拿到一个自定义 S 盒想知道它的差分和线性抵抗强度不用去翻论文直接调 buildDDT 和 buildLAT看两个指标DDT 里除第一行第一列外的最大计数值以及 LAT 里除 (0,0) 外的最大绝对偏差。前者越小差分抵抗越强后者越小线性抵抗越强。我一般会写一个评估函数把这两个指标一起打出来#include algorithm #include cstdlib // 返回 {最大差分计数, 最大线性绝对偏差} std::pairint,int evaluateSbox(const std::vectoruint8_t sbox) { auto ddt buildDDT(sbox); auto lat buildLAT(sbox); int size (int)sbox.size(); int maxDDT 0, maxLAT 0; for (int din 0; din size; din) for (int dout 0; dout size; dout) { if (din 0 dout 0) continue; // 跳过平凡项 maxDDT std::max(maxDDT, ddt[din][dout]); } for (int a 0; a size; a) for (int b 0; b size; b) { if (a 0 b 0) continue; maxLAT std::max(maxLAT, std::abs(lat[a][b])); } return {maxDDT, maxLAT}; }参数说明返回的两个值都是原始计数不是归一化概率。对 4 比特 S 盒理想情况下最大差分计数接近 4即概率 1/4最大线性绝对偏差接近 4。如果某个 S 盒这两个值明显偏大说明存在高概率差分或强线性逼近设计上要警惕。这个评估不能替代完整的安全性证明但作为快速筛选足够用。再进一步你可以把多轮特征搜索也接进来从 DDT 里挑计数最大的若干条单轮差分按轮拼接用 log2 累加算总概率排序后看最优路径。资源里给了一个简化版的搜索框架我照着改成了支持任意轮数的版本跑一个 8 轮 SPN 大概几秒出结果。这里的关键是剪枝——每轮只保留概率高于阈值的差分否则分支爆炸。注意特征搜索出来的最优路径只是候选实际攻击还要考虑聚类和密钥恢复阶段的计数别把搜索结果直接当结论。从那以后我每次拿到新 S 盒都强制先跑一遍 evaluateSbox把两个指标记在文档里再决定要不要深入分析。这个习惯帮我省了很多事后返工。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
