简介由 Howard M. Heys 发表于 Cryptologia 的经典教程及配套 C 实现组成的入门资料面向密码学初学者、信息安全专业学生以及希望理解分组密码分析思路的开发者。内容以仅 5 轮、16 比特分组的玩具密码为案例循序渐进讲解差分分析与线性分析的基本原理、攻击流程与推演方法并给出可直接运行的代码实现。压缩包共 6 个文件约 662KB包含教程 PDF、两份 C 源码、对应可执行程序及一份说明文本PDF 用于梳理理论cpp 与 exe 便于对照复现实验说明文本辅助理解程序用途。已有 553 人学习下载。读者可借助理论讲解与代码实践建立直观认识掌握差分特征、线性逼近等核心概念的实验验证方式适合作为课堂之外的补充材料与动手入门练习。1. 从一张16×16的表说起差分分析与线性分析到底在算什么很多人第一次听到差分分析和线性分析反应是合上教材——满页概率下标和 Walsh 谱符号不知道从哪下手。我的转折点是把一个4位S盒丢进C把差分分布表和线性逼近表打出来盯着两个16×16矩阵看哪一格数字大哪条路径就值得追。这个项目做的就是这件事不依赖任何密码学库几百行C把两条经典分析链路各走一遍从S盒统计表到多轮特征搜索再到小轮数暴力验证。它适合想动手理解分组密码分析原理的学生也适合需要给自己轮函数做快速评估的实现者。会写基础C、知道异或和按位与就够不需要先读教材。2. 项目结构与数据模型三个头文件撑起一个分析器这个项目的骨架非常轻。整个分析器围绕一个16位分组、每轮4个并行4位S盒的玩具轮函数展开因为分组小所有统计可以精确算出来不像真实密码那样只能靠估计。选择自己搭轮函数而不是直接拿现成标准密码是为了让每一步传播都能被打印出来对照出了问题能一眼定位到是哪一层。2.1 目录划分表、搜索、入口分成三块目录结构我按「静态数据 → 搜索逻辑 → 命令行入口」三层来切这样后面想加新的搜索策略只要往src/里塞文件不用动头文件。cipher-analyst/ ├── include/ │ ├── sbox.h # S盒常量、位操作、轮函数 │ ├── ddt.h # 差分分布表接口 │ ├── lat.h # 线性逼近表接口 │ └── trail.h # 差分/线性迹的数据结构 ├── src/ │ ├── ddt.cpp │ ├── lat.cpp │ ├── diff_trail.cpp │ ├── lin_trail.cpp │ └── main.cpp ├── test/ │ └── verify.cpp # 单轮暴力验证 └── Makefile分层的理由是DDT 和 LAT 这两个表对给定S盒只算一次但搜索会跑很多次、很多组参数。把表独立成模块在main.cpp里构造一次然后传引用给搜索函数既省时间也避免全局状态污染。差分迹和线性迹的搜索骨架高度相似但目标函数和剪枝方向相反我最后选择写成两个独立实现而不是模板抽象——教学代码里能直接读懂的重复比绕来绕去的复用更值钱。2.2 数据结构为什么用 uint16_t 而不是 bitset16位状态如果用std::bitset16打印好看但做异或、半字节提取、置换时每次都要转换搜索里这些操作会跑上百万次。所以内部统一用uint16_t只在调试打印时写一个dumpBits转成字符串。// include/sbox.h #pragma once #include cstdint #include string constexpr int BLOCK_BITS 16; // 分组长度 constexpr int NIBBLE_BITS 4; // S盒宽度 constexpr int NIBBLES BLOCK_BITS / NIBBLE_BITS; // 并行 S 盒个数 constexpr int SBOX_SIZE 1 NIBBLE_BITS; // 16 // 教学用的 4 位 S 盒输入输出均为 0..15 的双射 inline constexpr uint8_t SBOX4[SBOX_SIZE] { 0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2 }; // 比特置换表输出位 PERM[i] 来源于输入位 i必须是 0..15 的排列 inline constexpr uint8_t PERM[BLOCK_BITS] { 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11 }; inline uint16_t sboxLayer(uint16_t s) { uint16_t out 0; for (int i 0; i NIBBLES; i) { uint8_t nib (s (NIBBLE_BITS * i)) 0xF; out | static_castuint16_t(SBOX4[nib]) (NIBBLE_BITS * i); } return out; } // out[PERM[i]] in[i] inline uint16_t pLayer(uint16_t s) { uint16_t out 0; for (int i 0; i BLOCK_BITS; i) if (s (1u i)) out | 1u PERM[i]; return out; } // 一轮完整轮函数异或轮密钥 - S盒层 - 线性层 inline uint16_t roundFunction(uint16_t s, uint16_t rk) { return pLayer(sboxLayer(s ^ rk)); }roundFunction里有个值得先记住的性质异或轮密钥这一步对差分完全透明。如果两个输入x和x的差是Δ x ^ x那(x^rk) ^ (x^rk)还是Δ。所以差分迹的搜索里轮密钥直接当0处理就行这一点很多人第一次实现时会绕进去后面避坑那章会细说。PERM必须是双射这是硬约束。如果漏写或写重某个下标pLayer就不是可逆置换差分传播会出现多条路径合并或凭空消失搜出来的特征概率看着像模像样但全是错的。main.cpp启动时我加了一句static_assert风格的运行时自检把PERM排序后逐项比对 0..15不通过直接退出。2.3 构建与命令行入口编译用最朴素的 Makefile不开 CMake因为项目就五个源文件-O2和-Wall两个开关足够。CXX : g CXXFLAGS : -O2 -stdc17 -Wall -Wextra SRC : $(wildcard src/*.cpp) OBJ : $(SRC:.cpp.o) analyze: $(OBJ) $(CXX) $(CXXFLAGS) $^ -o $ %.o: %.cpp $(CXX) $(CXXFLAGS) -Iinclude -c $ -o $ clean: rm -f $(OBJ) analyze-O2对深度优先搜索影响很明显四轮搜索的耗时能差三到五倍。-Wall -Wextra主要用来抓位宽截断uint16_t和int混算时如果忘了强制转换高位的废弃位会悄悄污染半字节。跑起来的样子make analyze ./analyze --mode ddt # 打印 16x16 差分分布表 ./analyze --mode lat # 打印 16x16 线性逼近表 ./analyze --mode diff-trail --rounds 4 --top 10 --bound 3e-4 ./analyze --mode lin-trail --rounds 4 --top 10 --bound 2e-3 ./analyze --mode verify --rounds 1 # 单轮暴力核对参数含义--rounds是搜索的轮数--top是输出前几名--bound是剪枝门限差分用概率线性用绝对偏差。门限给太小搜索会跑很久给太大可能把最好的解一起剪掉。我的经验是从空跑一遍拿到最优值再把它调低一到两个数量级做二次搜索比一上来就拍脑袋设门限靠谱。3. 差分分析链路从S盒差分分布表到一条高概率特征差分分析的整套流程可以压缩成一句话算一张表然后在这张表铺开的图上找一条概率最大的路径。表是S盒的差分分布表路径就是所谓的差分特征。这一章把这两步拆开写。3.1 差分分布表16×16个计数对每个输入差分Δin和输出差分Δout统计有多少个输入x满足S(x) ^ S(x^Δin) Δout。这个计数值除以16就是该S盒上这一对差分传播的概率。// src/ddt.cpp #include ddt.h #include array using Table std::arraystd::arrayint, SBOX_SIZE, SBOX_SIZE; Table buildDDT(const uint8_t sbox[SBOX_SIZE]) { Table ddt{}; for (int dx 0; dx SBOX_SIZE; dx) { // 输入差分 for (int x 0; x SBOX_SIZE; x) { // 遍历全部输入 int dy sbox[x] ^ sbox[x ^ dx]; // 实际输出差分 ddt[dx][dy]; } } return ddt; }两层循环的边界都是16所以整张表65536次运算瞬间算完。三个性质可以直接用来做自检每一行的计数之和必须等于16因为对固定的Δin遍历所有的x恰好走16次。Δin 0那一行只有ddt[0][0] 16其余全为0。输入没差别输出当然也没差别。由于S盒是双射x和x^Δin在Δin ≠ 0时必然不同所以S(x) ≠ S(x^Δin)Δin ≠ 0的行里ddt[dx][0]一定是0。第三条是很多人写完DDT没意识到的东西如果一个双射S盒的DDT里出现了非零行首元素说明数组越界或者S盒表里混进了重复值。这个检查我直接写进单元测试比肉眼看表快得多。拿Δin 1这一行举例输出差分的分布大致是这样的只列非零项输出差分 Δout计数概率100221/8441/4521/8621/8921/8B21/8C11/16D11/16最大的那一格概率 1/4就是这一轮最值得追的方向。3.2 单轮传播S盒层带概率线性层是确定的一轮里S盒层的每个活跃半字节都有多个候选输出差分各有概率P层是纯置换一个输入差分只对应一个输出差分概率恒为1。所以「展开一轮」本质上是做一次四元笛卡尔积。// src/diff_trail.cpp struct RoundExpansion { uint16_t outDiff; // 经过 P 层之后的差分 double prob; // 本轮概率 int active; // 本轮活跃 S 盒个数 }; std::vectorRoundExpansion expandOneRound(uint16_t inDiff, const Table ddt) { std::vectorstd::vectorstd::pairint,int cand(NIBBLES); for (int i 0; i NIBBLES; i) { int dx (inDiff (NIBBLE_BITS * i)) 0xF; if (dx 0) { cand[i].push_back({0, 1}); // 不活跃概率因子为 1 } else { for (int dy 0; dy SBOX_SIZE; dy) if (ddt[dx][dy] 0) cand[i].push_back({dy, ddt[dx][dy]}); } } std::vectorRoundExpansion res; for (int a 0; a (int)cand[0].size(); a) for (int b 0; b (int)cand[1].size(); b) for (int c 0; c (int)cand[2].size(); c) for (int d 0; d (int)cand[3].size(); d) { int picks[4] {a, b, c, d}; uint16_t sboxOut 0; int count 1, active 0; for (int i 0; i NIBBLES; i) { auto [dy, cnt] cand[i][picks[i]]; sboxOut | static_castuint16_t(dy) (NIBBLE_BITS * i); count * cnt; if (((inDiff (NIBBLE_BITS * i)) 0xF) ! 0) active; } double p count * std::pow(static_castdouble(SBOX_SIZE), -active); res.push_back({pLayer(sboxOut), p, active}); } return res; }关键点是count用整数累乘、最后才转浮点。四个半字节的计数乘起来可能到几十万先用double一路乘会有累积误差而差分概率的最后比较往往就差在很小的相对误差上。std::pow(16, -active)里的active是本轮活跃S盒数——注意是活跃数不是固定值4也不是轮数这个区别后面避坑章还会提。性能上必须心里有数四个半字节全活跃时每个最多15个候选一轮就是 15⁴ ≈ 5万条。四轮不剪枝直接跑分支数会到 10¹⁸ 量级跑一晚上都出不来。所以下一步的搜索必须带剪枝。3.3 多轮搜索带概率上界的深度优先最朴素的剪枝是「当前概率已经低于门限就返回」但这样只能剪掉搜索树的深处前面几层还是会疯狂展开。真正有效的是给一个乐观上界假设剩余每轮都以最理想的方式传播算出一个上界当前概率乘上界还够不到门限就整枝砍掉。// 剩余 r 轮的乐观概率上界假设每轮只激活一个 S 盒且取到最大计数 double optimisticBound(int remainRounds, const Table ddt) { int bestCount 0; for (int dx 1; dx SBOX_SIZE; dx) for (int dy 0; dy SBOX_SIZE; dy) bestCount std::max(bestCount, ddt[dx][dy]); double bestP static_castdouble(bestCount) / SBOX_SIZE; return std::pow(bestP, remainRounds); } void dfsDiffTrail(uint16_t inDiff, int round, int maxRound, double curProb, double probBound, const Table ddt, std::vectoruint16_t path, std::vectorTrail out) { if (round maxRound) { // 搜到底收一条迹 out.push_back({path, curProb}); return; } if (curProb * optimisticBound(maxRound - round, ddt) probBound) return; // 上界都够不到剪枝 for (const auto e : expandOneRound(inDiff, ddt)) { double np curProb * e.prob; if (np probBound) continue; path.push_back(e.outDiff); dfsDiffTrail(e.outDiff, round 1, maxRound, np, probBound, ddt, path, out); path.pop_back(); } }path里存的是每轮的输入差分或输出差分全篇统一一种写法混用是灾难。probBound建议先用 0 跑一遍拿到最优值P*再用P*/100做门限二次搜索这样既不会漏掉量级接近的解又能把搜索时间压下来。optimisticBound是个偏松的界理论上可以做到更紧比如根据输入差分的汉明重量限制活跃S盒个数但松界的好处是实现简单不容易写错实际跑四轮已经够用了。3.4 结果验证单轮必须精确对上多轮只能抽样搜出来的迹不能直接信。第一轮的特征是最容易验证的固定输入差分遍历全部 65536 个明文统计实际输出差分符合预期的次数除以总数。// test/verify.cpp double measureOneRound(uint16_t dx, uint16_t expectedDy) { int hit 0; const int total 1 BLOCK_BITS; for (int x 0; x total; x) { uint16_t y1 roundFunction(static_castuint16_t(x), 0); uint16_t y2 roundFunction(static_castuint16_t(x) ^ dx, 0); if ((y1 ^ y2) expectedDy) hit; } return static_castdouble(hit) / total; }这个函数返回的实测概率必须和ddt[dx][dy] / 16完全相等一位都不差。如果不等问题一定出在pLayer或者半字节切分上不用怀疑统计逻辑。我后来养成一个习惯任何新S盒、新置换先跑这个单轮验证通过了再往下做多轮。多轮就没法穷举了2¹⁶ 个明文两两配对是 2³² 级别的组合。折中办法是用随机抽样抽一万个随机明文构造(x, x^Δin)对看经过 r 轮后差分命中预期值的比例。样本量小实测值会围绕理论概率上下波动但只要数量级对得上比如理论 2⁻¹²、实测一千个样本里中零到两个就说明整条链路是通的。真要精确验证把分组砍到8位再跑穷举也是常规做法。4. 线性分析链路从Walsh谱到偏差最大的线性迹线性分析和差分分析像一对镜像。差分追的是「输入差分经过S盒后输出差分等于某值的概率」线性追的是「输入某些位的异或等于输出某些位的异或」这个等式成立的概率偏离 1/2 有多远。两条链路的代码结构几乎对称但几个符号和方向上的细节完全相反写错一个地方不会崩只会给你一堆看起来正常的结果。4.1 线性逼近表偏差与相关性对输入掩码a和输出掩码b统计满足parity(a x) parity(b S(x))的x有多少个再减去 8即 16 的一半。// src/lat.cpp inline int parity(int v) { v ^ v 2; v ^ v 1; return v 1; } Table buildLAT(const uint8_t sbox[SBOX_SIZE]) { Table lat{}; for (int a 0; a SBOX_SIZE; a) { for (int b 0; b SBOX_SIZE; b) { int cnt 0; for (int x 0; x SBOX_SIZE; x) if (parity(a x) parity(b sbox[x])) cnt; lat[a][b] cnt - SBOX_SIZE / 2; // 偏差 × 2^n } } return lat; }lat[a][b]的取值范围是 -8 到 8都是偶数。它表示的是「偏差 × 16」所以真正的偏差ε lat[a][b] / 16而做连乘时用的是相关性c 2ε lat[a][b] / 8这个换算关系整个项目里只用一处就是下面的roundCorrelation。表里有几个固定规律可以当自检lat[0][0] 8即输入不取任何位、输出也不取任何位等式恒成立偏差0.5。这条在搜索里必须排除否则任何迹的总偏差都会被它拉满。因为S盒是双射a 0且b ≠ 0时lat 0反过来b 0且a ≠ 0时也是0。这在传播时可以用来快速判定「此路不通」。4.2 掩码通过线性层用逆置换方向别搞反这是整章最容易翻车的地方。pLayer的定义是out[PERM[i]] in[i]即输入的第 i 位被搬到输出的第 PERM[i] 位。现在假设我们在 P 层的输出侧用一个掩码β去取某些位做异或那等价于在输入侧用掩码α其中α[i] β[PERM[i]]。// 把输出侧掩码映射回输入侧即 P 层的逆 inline uint16_t invPLayer(uint16_t mask) { uint16_t out 0; for (int i 0; i BLOCK_BITS; i) if (mask (1u PERM[i])) out | 1u i; return out; }对比一下pLayer和invPLayerpLayer是「读第 i 位写第 PERM[i] 位」invPLayer是「读第 PERM[i] 位写第 i 位」。两行代码长得像作用正好相反。写反了搜索照样能跑出结果但线性迹对应的位位置全错最后拿去做密钥恢复一个都命不中而且中间过程没有任何报错提示属于典型的黑匣子 bug。4.3 单轮偏差与 piling-up 合成一轮里每个活跃S盒贡献一个相关性c_i lat[a_i][b_i] / 8四个半字节独立近似整轮相关性就是它们相乘。// 返回本轮相关性无信息时返回 0 double roundCorrelation(uint16_t inMask, uint16_t outMask, const Table lat) { double corr 1.0; bool any false; for (int i 0; i NIBBLES; i) { int a (inMask (NIBBLE_BITS * i)) 0xF; int b (outMask (NIBBLE_BITS * i)) 0xF; if (a 0 b 0) continue; // 该 S 盒不参与 if (a 0 || b 0) return 0.0; // 单边为 0双射下无信息 double c static_castdouble(lat[a][b]) / (SBOX_SIZE / 2); if (c 0.0) return 0.0; corr * c; any true; } return any ? corr : 0.0; }跨轮合成用 piling-up 引理若有 n 个独立偏差ε_i总偏差ε 2^(n-1) · ∏ε_i。把它改写成相关性形式就是ε (1/2) · ∏(2ε_i)。所以代码里只需要把所有轮的相关性一路乘下去最后一并除以2// 每轮先各自算 corr跨轮连乘最后统一除以 2 inline double totalBias(double totalCorr) { return totalCorr / 2.0; }这里的 n 是参与近似的活跃S盒总数不是轮数也不是分组长度。很多人直观地写成2^(轮数-1)在每轮只激活一个S盒时刚好相等一旦某轮激活两个就开始偏轮数越多偏得越离谱。piling-up 本身是个近似前提是各轮近似互相独立真实密码里这个假设并不成立所以理论值和实测值有偏差是正常的但公式里的指数不能用错。4.4 搜索目标最大化绝对偏差而不是概率差分的剪枝是「概率越小越该剪」线性同样是「越小越该剪」但比较的是偏差的绝对值因为偏差可以是负数负偏差和正偏差一样有用只是符号会影响到后续的密钥恢复判断。void dfsLinTrail(uint16_t inMask, int round, int maxRound, double curCorr, double corrBound, const Table lat, std::vectoruint16_t path, std::vectorTrail out) { if (round maxRound) { out.push_back({path, totalBias(curCorr)}); return; } if (std::fabs(curCorr) * optimisticLinBound(maxRound - round, lat) corrBound) return; for (const auto e : expandOneRoundLinear(inMask, lat)) { double nc curCorr * e.corr; if (std::fabs(nc) corrBound) continue; path.push_back(e.outMask); dfsLinTrail(invPLayer(e.outMask), round 1, maxRound, nc, corrBound, lat, path, out); path.pop_back(); } }注意递归参数传的是invPLayer(e.outMask)——输出侧掩码要先逆回到输入侧才能和下一轮的S盒输入掩码对齐。这是线性和差分在代码层面最大的结构差异差分的 P 层传播是正向的pLayer线性的掩码传播是逆向的invPLayer。把两条链路放在一起对照差异一目了然维度差分分析线性分析核心统计表差分分布表 DDT线性逼近表 LAT表的元素含义计数除以16得概率偏差×16除以8得相关性传播对象异或差分按位内积掩码本文还有配套的精品资源点击获取