简介：围绕差分分析与线性分析的经典入门材料，以Howard M. Heys发表于Cryptologia的教程文章为核心，面向密码学初学者及信息安全专业学生，借助仅5轮、16比特的玩具密码把两种经典分析方法讲得直观可感。压缩包共6个文件，约662KB，包含教程PDF、两份C++源码及对应可执行程序，另有说明文本，便于边读原理边运行验证。已有553人学习下载，说明该主题在入门学习中具有一定关注度。读者可先通过文章理解差分特征、线性逼近与轮函数构造，再对照C++实现观察明文样本生成、正确对与错误对筛选、末轮子密钥恢复及成功率统计等环节，从而把抽象公式落到可编译、可调试的代码上；也可配合分组密码攻击方法相关教材同步阅读。对刚接触分组密码分析的人来说，这份材料能提供从概念到动手实践的完整起点。
1. 差分分析与线性分析入门：先用一张 16×16 的表把「概率」这件事坐实
很多人学差分分析和线性分析，卡在同一个位置：书上的推导能跟上，合上书却写不出一行代码。原因不是数学难，而是入门材料大多停在「引理 + 证明」，没人告诉你一个 4 比特 S 盒的差分分布表怎么打出来、一条三轮特征怎么用程序搜、最后一轮那 4 bit 子密钥到底怎么被统计出来的。这份材料正好补这一段：一份讲原理的入门文章，配一套可以直接编译运行的 C++ 实现，覆盖打表、特征搜索、部分解密、计数器密钥恢复，以及对偶的线性攻击一侧。它适合已经知道分组密码基本结构、想动手把差分分析和线性分析跑通一遍的人。下面我按自己复现的顺序拆，代码照抄能跑，参数我会标清楚在哪一行改。
2. 差分分布表与线性逼近表：两个 256 格的表决定了后面一切
2.1 为什么先打表：差分传递靠的是概率不是函数
差分分析的核心观察很朴素：对一对明文施加同一个差分，经过一轮非线性层后，输出差分不是一个确定值，而是一个分布。之所以有分布，是因为 S 盒对某个固定输入差分 $\alpha$，会有多个输出差分 $\beta$ 可能，各自命中若干个输入。把这件事量化下来，就是差分分布表 DDT：
$$\mathrm{DDT}[\alpha][\beta] = #{x \in {0,1}^n : S(x) \oplus S(x \oplus \alpha) = \beta}$$
行和恒等于 $2^n$。对 4 比特 S 盒来说，$2^n = 16$，所以每格的值是 0 到 16 之间的偶数（$\alpha = 0$ 时 $\beta$ 只能为 0，那一行是 16）。相邻两条差分路径的概率相乘，乘出来就是这个特征的概率。
线性分析走的是对偶的一条路：不去看差分，看「输入位的异或」和「输出位的异或」之间的相关性。用线性逼近表 LAT 描述：
$$\mathrm{LAT}[a][b] = \sum_{x}(-1)^{a \cdot x \oplus b \cdot S(x)}$$
值域是 $[-16, 16]$，除以 16 就是相关系数，除以 2 就是偏差 $\varepsilon$。线性攻击的样本量大致按 $1/\varepsilon^2$ 走，所以这张表的极值直接决定你能不能跑得动。
入门阶段最容易忽略的一点是：这两张表必须由程序算出来，不能抄。抄来的表一旦跟你的 S 盒、位序对不上，后面所有统计都是噪声，而你还看不出来——计数器一样会给出一个「最大值」，只是那个最大值是错的。
2.2 DDT 的构造与 C++ 实现
先定 S 盒。这里用一个 4 比特 S 盒（公开教材里的常见例子，各项性质都够用），下标是输入，值是输出：
#include <cstdint> #include <cstdio> // 4-bit S box: S[x] 就是 x 的非线性替换结果 static const uint8_t S[16] = { 0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2 }; // 由 S 直接反推逆表，别手写，手写必错 static uint8_t S_INV[16]; static void build_inv() { for (int x = 0; x < 16; ++x) S_INV[S[x]] = (uint8_t)x; } // DDT[a][b] = #{x : S(x) ^ S(x^a) == b} static void build_ddt(int ddt[16][16]) { for (int a = 0; a < 16; ++a) for (int b = 0; b < 16; ++b) ddt[a][b] = 0; for (int a = 0; a < 16; ++a) { for (int x = 0; x < 16; ++x) { int b = S[x] ^ S[x ^ a]; ddt[a][b] += 1; } } }这段代码没有任何技巧，但有两个细节值得说。第一，内层循环枚举的是 $x$ 从 0 到 15 全部，而不是只枚举「$x$ 和 $x\oplus\alpha$ 中较小者」，两者结果相同但前者更不容易写错边界。第二，S_INV一定用循环反推，手写逆表是血泪经验——16 个数字看起来不多，错一位你会在三天后才发现。
跑一下ddt[0x1][0x3]，结果应该是 2。意思是输入差分为0x1时，16 个输入里有 2 个让输出差分恰好等于0x3，概率 $2/16 = 1/8$。作为对照，ddt[0x1][0x0]是 0——输入差分非零，输出差分不可能是 0，因为 S 盒是置换。这两条数你可以当成自检点：如果ddt[0]那一行不是「16, 0, 0, ...」，或者任何一行的行和不是 16，那 S 盒或者循环写错了。
参数上唯一可改的是 S 盒本身。想换成 8 比特 S 盒，把16全部改成256、uint8_t保持、二维数组改成int ddt[256][256]（约 256 KB，栈上放不下，要改成static或堆分配）。这是新手第一个翻车点：int ddt[256][256]局部变量直接爆栈，程序还没打印就段错误，而错误信息完全看不出来是因为表大了。
2.3 LAT 与 Walsh 变换：线性偏差怎么量化
有了 DDT 的经验，LAT 就是同一个套路换个内积：
static inline int parity(uint8_t x) { return __builtin_popcount((unsigned)x) & 1; } // LAT[a][b] = sum_x (-1)^(a·x ^ b·S(x))，取值 -16..16 static void build_lat(int lat[16][16]) { for (int a = 0; a < 16; ++a) { for (int b = 0; b < 16; ++b) { int sum = 0; for (int x = 0; x < 16; ++x) { int p = parity((uint8_t)(a & x)) ^ parity((uint8_t)(b & S[x])); sum += (p ? -1 : 1); } lat[a][b] = sum; } } }parity用__builtin_popcount是 GCC/Clang 的内建函数，MSVC 上换成手写循环或者std::popcount（C++20）。这一步不涉及性能，纯粹是写法习惯。
跑出来你会看到lat[0][0] = 16（恒等式，相关为 1），lat[a][0]全为 0（$a \ne 0$ 时输入掩码和常函数不相关），对角线上有若干非零值。这张表的最大绝对值是 4，对应相关系数 $4/16 = 1/4$、偏差 $\varepsilon = 4/16$（注意不同教材对偏差的定义差一个因子 2，我这里按「相关系数/2」算偏差，写攻击脚本时以相关系数为准最不易混）。
如果你算出来的最大值不是 4，先别怀疑算法，回去核对 S 盒。这一步是整个流程里最值得反复确认的地方，因为它决定了后续所有「这条线性壳够不够用」的判断。
顺便说一句 Walsh 变换。对 4 比特 S 盒逐格求和完全够快（16×16×16 = 4096 次操作），不需要 FFT 那套快速 Walsh-Hadamard。但对于 8 比特 S 盒，朴素的 $256 \times 256 \times 256 \approx 1.7 \times 10^7$ 也还能接受，十几毫秒的事。真正需要快速变换的是你在做大规模搜索、要对几千个 S 盒批量评估的场景，入门阶段不用碰。
2.4 从表里挑特征：看什么数、什么算「够用」
表打完了，接下来的问题是读表。差分侧的判据是「概率 $\times$ 活跃 S 盒数」：一条经过 $r$ 轮、每轮有 $n_i$ 个活跃 S 盒的特征，总概率是各轮概率之积。入门玩具结构里，一轮通常只有一个 S 盒活跃（差分还没扩散开），此时单轮概率就是 $DDT[\alpha][\beta]/16$。如果某个 $\beta$ 对应的值是 8，那这一轮概率就是 1/2，非常划算；如果是 2，就是 1/8，三轮下来 1/512，需要几千对明文才能让信噪比站住。
线性侧的判据是偏差的绝对值：$\varepsilon$ 越大，需要的样本量越少，粗略按 $N \approx c/\varepsilon^2$ 估，$c$ 取 8 到 16 之间比较稳。$\varepsilon = 1/4$ 时 $N$ 在几百量级，$\varepsilon = 1/16$ 时就要上万了。
提示：入门阶段选特征，宁可选一条概率高但轮数少的，也别贪轮数。三轮 + 一轮部分解密的组合，只要数据量给够，成功率很稳定；四轮 + 一轮的链路一旦某处概率估错，你会得到一条「看起来跑了但结果随机」的曲线，排查成本高得多。
3. 特征搜索到密钥恢复：把四轮 ToyCipher 的最后一轮密钥啃下来
3.1 ToyCipher 的结构定义与轮密钥生成
要在上面动手，得有一个具体的靶子。这里定义一个 16 比特分组、4 轮的 SPN 结构（下文叫 ToyCipher），结构足够小以至于能穷举验证，又足够完整以至于差分和线性两条路都走得通。
每轮三步：4 个并行的 4 比特 S 盒替换（SubCells）、一个比特级置换（PermBit）、异或轮密钥（AddRoundKey）。最后一轮为了攻击方便，去掉 PermBit，只做 SubCells 加白化密钥——这也是真实分组密码设计的常见做法。
// 位序约定：bit i 表示第 i 位，nibble j = bits[4j .. 4j+3]，LSB 是 bit 0 static inline uint16_t sub_layer(uint16_t x) { uint16_t y = 0; for (int i = 0; i < 4; ++i) y |= (uint16_t)S[(x >> (4 * i)) & 0xF] << (4 * i); return y; } static inline uint16_t inv_sub_layer(uint16_t x) { uint16_t y = 0; for (int i = 0; i < 4; ++i) y |= (uint16_t)S_INV[(x >> (4 * i)) & 0xF] << (4 * i); return y; } // 小 nibble 的第 j 位搬到第 4j+i 位：第 i 个 S 盒的第 j 个输出位 // 落到第 j 个 nibble 的第 i 位，保证扩散到下一轮不同 S 盒 static inline uint16_t perm_bit(uint16_t x) { uint16_t y = 0; for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) { uint16_t bit = (x >> (4 * i + j)) & 1; y |= (uint16_t)(bit << (4 * j + i)); } return y; } static inline uint16_t inv_perm_bit(uint16_t x) { uint16_t y = 0; for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) { uint16_t bit = (x >> (4 * j + i)) & 1; y |= (uint16_t)(bit << (4 * i + j)); } return y; }轮函数和加解密骨架：
struct ToyCipher { uint16_t rk[5]; // rk[0] 白化，rk[1..3] 前三轮，rk[4] 最后一轮 uint16_t encrypt(uint16_t p) const { uint16_t s = p ^ rk[0]; for (int r = 1; r <= 3; ++r) { s = sub_layer(s); s = perm_bit(s); s ^= rk[r]; } s = sub_layer(s); // 最后一轮无 PermBit return s ^ rk[4]; } uint16_t decrypt(uint16_t c) const { uint16_t s = inv_sub_layer(c ^ rk[4]); for (int r = 3; r >= 1; --r) { s ^= rk[r]; s = inv_perm_bit(s); s = inv_sub_layer(s); } return s ^ rk[0]; } };这段代码唯一需要理解的是perm_bit：它把第 $i$ 个 S 盒的第 $j$ 个输出位搬到第 $j$ 个 nibble 的第 $i$ 位。这样做的作用是让每个 S 盒的输出位分散到下一轮的 4 个不同 S 盒里，而不是原地不动。如果置换写得不够「散」，差分会在同一个 S 盒里反复打转，搜不出有效特征——这是设计层面的事，复现时直接按上面的写法即可。
encrypt和decrypt一定要能对上。编译后第一件事就是拿随机明文跑decrypt(encrypt(p)) == p，跑个几万次。这行自检能省掉后面几小时的困惑。
3.2 特征搜索：按轮做分支定界
特征搜索本质是树上找最大概率路径。每一层做一次差分传递：状态是 16 比特差分，对每个活跃 nibble 查 DDT 得到若干可能的输出差分，乘上概率，再走perm_bit，进入下一轮。
朴素穷举会爆。4 个活跃 nibble、每个 nibble 有十几个可能的输出差分，三轮下来是天文数字。用两个剪枝压住：一是概率阈值，只保留单轮概率 $\ge 4/16$ 的转移；二是总量上限，每层最多保留BEAM条候选。
struct Trail { uint16_t din; // 本轮输入差分 uint16_t dout; // 本轮输出差分（过 PermBit 之后） double prob; // 累计概率 }; static const int BEAM = 40000; // 对单个 nibble 差分 a，返回所有 (b, 计数) 并过滤掉计数过低的 static std::vector<std::pair<uint8_t,int>> diff_of_nibble(int a, const int ddt[16][16], int min_cnt) { std::vector<std::pair<uint8_t,int>> out; for (int b = 0; b < 16; ++b) if (ddt[a][b] >= min_cnt) out.push_back({(uint8_t)b, ddt[a][b]}); return out; } static std::vector<Trail> search_trail(uint16_t start_diff, int rounds, const int ddt[16][16], int min_cnt = 4) { std::vector<Trail> cur{{start_diff, start_diff, 1.0}}; std::vector<Trail> next; std::vector<Trail> best; for (int r = 0; r < rounds; ++r) { next.clear(); for (const auto& t : cur) { // 每个 nibble 独立展开，组合起来 std::vector<std::pair<uint16_t,double>> layer{{t.din, t.prob}}; for (int i = 0; i < 4; ++i) { int a = (t.din >> (4 * i)) & 0xF; if (a == 0) continue; // 未激活，差分保持 0 auto opts = diff_of_nibble(a, ddt, min_cnt); std::vector<std::pair<uint16_t,double>> grow; for (auto& [s, p] : layer) for (auto& [b, cnt] : opts) { uint16_t ns = (uint16_t)(s & ~(0xF << (4 * i))); ns |= (uint16_t)(b << (4 * i)); grow.push_back({ns, p * cnt / 16.0}); } layer.swap(grow); } for (auto& [s, p] : layer) next.push_back({s, perm_bit(s), p}); } // 按概率降序截断，控制搜索宽度 std::sort(next.begin(), next.end(), [](const Trail& x, const Trail& y){ return x.prob > y.prob; }); if ((int)next.size() > BEAM) next.resize(BEAM); cur = next; best = cur; } return best; // 调用方按 prob 取第一条 }min_cnt = 4是剪枝的关键参数，含义是「单个 S 盒的差分转移至少在 16 个输入里命中 4 次」，也就是单轮概率下限 1/4。这个阈值调高搜得快但可能漏掉好特征，调低搜得全但树会膨胀。经验上 4 是个不错的起点，改成 2 会让BEAM迅速被打满，改成 8 又几乎搜不到东西。
BEAM = 40000控制每层保留的候选数。跑三轮、起始差分只有一个 nibble 活跃的情况下，实际膨胀到几千就到顶了，这个上限主要是防御性写法。
调用方式：
auto trails = search_trail(0x0001, 3, ddt, 4); printf("best 3-round prob = %.6f, dout = %04X\n", trails[0].prob, trails[0].din);输出的dout是第 3 轮结束、经过perm_bit之后的差分。这个值很关键——它决定了你攻击时用密文的哪些 nibble 去做部分解密。如果搜出来的特征只有一个 nibble 的输出差分非零，那最后一轮只需要猜 4 bit 子密钥；如果是两个 nibble 都非零，猜测量就变成 8 bit，样本量和耗时会一起涨。
3.3 部分解密与计数器：只猜 4 bit 的理由
拿到了 3 轮特征 $(d_0, d_3, p)$，攻击流程是标准的：生成 $N$ 对明文 $(p, p \oplus d_0)$，全部加密，只保留密文对中「对应位置」满足某个条件的样本，然后对候选子密钥做部分解密、计数、取最大。
关键在于「对应位置」怎么定。因为最后一轮没有perm_bit，密文的第 $i$ 个 nibble 直接由第 3 轮输出的第 $i$ 个 nibble 经过 S 盒和密钥异或得到：
$$c_i = S(s_{3,i}) \oplus rk_{4,i}$$
所以只要知道 $rk_{4,i}$，就能反推 $s_{3,i} = S^{-1}(c_i \oplus rk_{4,i})$。对一对密文 $(c, c')$，分别反推得到 $s_{3,i}$ 和 $s'_{3,i}$，它们的异或就是第 3 轮输出差分。如果特征成立，这个值应该等于 $d_3$ 的第 $i$ 个 nibble。
于是攻击退化成一个 16 选 1 的问题：
// 用一条三轮特征恢复最后一轮第 idx 个 nibble 的子密钥 static int recover_last_nibble(const uint16_t* pt, const uint16_t* ct, int N, uint16_t d0, uint16_t d3, int idx, const ToyCipher& tc) { int cnt[16] = {0}; uint8_t target = (uint8_t)((d3 >> (4 * idx)) & 0xF); for (int i = 0; i < N; ++i) { // 明文对已经在外部按 d0 构造好并加密，这里只用密文对 uint16_t c1 = ct[2 * i], c2 = ct[2 * i + 1]; for (int k = 0; k < 16; ++k) { uint8_t s1 = S_INV[(c1 >> (4 * idx)) & 0xF ^ k]; uint8_t s2 = S_INV[(c2 >> (4 * idx)) & 0xF ^ k]; if ((uint8_t)(s1 ^ s2) == target) cnt[k] += 1; } } int best = 0; for (int k = 1; k < 16; ++k) if (cnt[k] > cnt[best]) best = k; // 返回的 best 是「离正确值还有多远」的反推值，调用方异或一下 return best; }这段代码里有几件事需要解释清楚，否则抄过去容易错。
pt参数实际上没用到——明文对是在调用前就按 $d_0$ 构造好的，因为开头我假设 $d_0$ 只有一个 nibble 活跃，那么直接让 $p_2 = p_1 \oplus d_0$ 就行，不需要任何筛选。如果 $d_0$ 有两个 nibble 活跃，且你想省样本，可以加一道「明文中被 $d_0$ 覆盖的 nibble 满足某个约束」的过滤，代价是样本利用率下降 $2^{k}$ 倍，收益是信噪比提升 $2^{k}$ 倍，入门阶段通常不做这个优化。
best的语义要小心。计数器统计的是「让第 3 轮输出差分等于target的次数」，正确的子密钥 $k^*$ 会让特征成立的那些样本全部命中，计数最高。但它返回的best是候选值本身，跟真实rk[4]的对应 nibble 之间的换算关系要在外部验证——我的习惯是直接打印cnt[]全表，肉眼看一下 16 个数里是不是有一个明显凸起，这比在代码里绕来绕去更直观。
统计量上，正确密钥的期望计数是 $N \cdot p_{\text{trail}}$（还要乘一次 $1/2^{4(1-\text{活跃 nibble 数})}$ 之类的筛选因子，入门结构里可以忽略），错误密钥的期望是 $N/16$。要让按此分开，需要 $N$ 满足 $N \cdot p \gg N/16$，也就是 $p \gg 1/16$。3 轮概率如果落在 $10^{-3}$ 量级，$N = 10000$ 对就够。
3.4 线性一侧：两阶段法的落法与坑
线性攻击的结构是差分攻击的镜像。找一条线性逼近
$$a \cdot p ; \oplus ; b \cdot c = k \cdot K$$
要求它成立的偏差 $\varepsilon$ 足够大。对 ToyCipher 来说，3 轮线性壳 + 一轮部分解密就是最自然的选择，跟差分侧的「3 轮特征 + 一轮」完全对称。
作弊的地方在于，线性壳的搜索比差分壳简单得多：差分要求每轮都有一个具体的中间差分值传递，线性壳只需要每轮掩码能「连上」——上一轮输出掩码经过perm_bit之后变成下一轮的输入掩码，逐轮相乘相关系数。而perm_bit是位置换，掩码的传播是确定性的，没有分支。
// 3 轮线性壳搜索：枚举起始掩码，逐轮求最大相关系数 struct LinTrail { uint16_t a0; // 明文掩码 uint16_t b3; // 第 3 轮输出掩码 double corr; // 相关系数（带符号） }; static LinTrail search_linear(int rounds, const int lat[16][16]) { LinTrail best{0, 0, 0.0}; for (int a0 = 1; a0 < 0x10000; ++a0) { double corr = 1.0; uint16_t mask = (uint16_t)a0; for (int r = 0; r < rounds; ++r) { double bestc = 0.0; uint16_t bestm = 0; for (int i = 0; i < 4; ++i) { int a = (mask >> (4 * i)) & 0xF; if (a == 0) continue; for (int b = 0; b < 16; ++b) { double c = lat[a][b] / 16.0; if (c * (corr > 0 ? 1 : -1) > bestc * (corr > 0 ? 1 : -1)) { // 简化：逐 nibble 独立挑最大绝对值，实际要整体评估 } } } (void)bestm; corr *= bestc; // 占位，真实实现见说明 } (void)corr; } return best; }上面这段故意留了个「占位」——因为逐 nibble 独立取最大是错的做法。真实的线性壳搜索必须对整条链路的相关系数整体连乘再比较：一个 nibble 上取次优的 $b$，可能让下一轮 mask 传播到更好的位置，整体反而更优。正确的写法是把每轮每个 nibble 的 $(b, c)$ 全部展开成笛卡尔积，用跟差分搜索同款的 beam 剪枝。
我把这个错误写法放在这里，是因为它是线性分析入门里最常见的翻车点：很多人拿到 LAT 就开始对每行取最大值，拼出一条「相关系数看起来很美」的壳，结果攻击跑出来毫无信号。逐 nibble 取最大，等于假设各个 nibble 的最优选择互不影响，而perm_bit恰恰把它们绑在一起。
正确写法是：
static LinTrail search_linear_beam(int rounds, const int lat[16][16], int beam = 20000) { struct S { uint16_t mask; double corr; }; std::vector<S> cur{{0x0001, 1.0}}, next; LinTrail best{0, 0, 0.0}; for (int r = 0; r < rounds; ++r) { next.clear(); for (auto& st : cur) { std::vector<std::pair<uint16_t,double>> layer{{st.mask, st.corr}}; for (int i = 0; i < 4; ++i) { int a = (st.mask >> (4 * i)) & 0xF; if (a == 0) continue; std::vector<std::pair<uint16_t,double>> grow; for (auto& [m, c] : layer) for (int b = 0; b < 16; ++b) { if (lat[a][b] == 0) continue; // 零相关，剪掉 uint16_t nm = (uint16_t)(m & ~(0xF << (4 * i))); nm |= (uint16_t)(b << (4 * i)); grow.push_back({nm, c * lat[a][b] / 16.0}); } layer.swap(grow); } // 掩码过 perm_bit 进入下一轮 for (auto& [m, c] : layer) next.push_back({perm_bit(m), c}); } std::sort(next.begin(), next.end(), [](const S& x, const S& y){ return std::abs(x.corr) > std::abs(y.corr); }); if ((int)next.size() > beam) next.resize(beam); cur = next; } for (auto& st : cur) if (std::abs(st.corr) > std::abs(best.corr)) best = {0, st.mask, st.corr}; return best; }注意if (lat[a][b] == 0) continue;这个剪枝——LAT 里有大量零，剪掉之后分支因子小一个量级，这是让搜索能跑完的关键。
拿到壳之后，攻击构造样本量 $N \approx 16/\varepsilon^2$（$\varepsilon$ 是偏差，即corr/2），对每个候选 $k$ 计算
$$T_k = \left| \sum_{i=1}^{N} (-1)^{a \cdot p_i \oplus b \cdot c'_i(k)} \right|$$
其中 $c'_i(k)$ 是用候选密钥部分解密后的第 3 轮输出。正确密钥对应的 $T_k$ 会有明显偏离，其余在 0 附近抖动。
注意：线性攻击的符号很容易搞混。LAT 里正相关和负相关对攻击都有效，取绝对值即可；但在多轮连乘时符号必须保留，否则一条「负相关链」会被误判成低质量而被剪掉，白白丢掉好壳。
4. C++ 工程化细节：位序、随机源和跑得完的复杂度
4.1 位序约定与接口：一个 nibble 对不上就全盘白跑
上面所有代码都依赖同一套位序约定：第 $i$ 个 nibble 占 bits $[4i, 4i+3]$，每个 nibble 内 LSB 是低位。这套约定本身没有对错，但必须从头到尾一致——打表用它、加解密用它、部分解密用它、打印调试也用它。
我见过最耗时的错误是：perm_bit写反了（把 $i \to 4j+i$ 写成了 $4i+j$），结果encrypt和decrypt自己内部还自洽（因为inv_perm_bit是按同一个错公式推的），但差分在轮间的传播位置全变了。搜出来的特征看起来挺正常，攻击却永远跑不出信号，因为特征描述的是「另一个结构」的差分。
防御手段只有一条：写一个打印函数，把每一轮的中间状态打出来，人工核对第一轮。
static void trace(uint16_t p, const ToyCipher& tc) { uint16_t s = p ^ tc.rk[0]; printf("rk0 ^ p = %04X\n", s); for (int r = 1; r <= 3; ++r) { s = sub_layer(s); printf("r%d sub = %04X\n", r, s); s = perm_bit(s); printf("r%d perm = %04X\n", r, s); s ^= tc.rk[r]; printf("r%d ark = %04X\n", r, s); } s = sub_layer(s); printf("final sub= %04X\n", s); printf("cipher = %04X\n", s ^ tc.rk[4]); }拿一个只有 bit 0 为 1 的明文跑一遍，验证 S 盒输出是不是落在第 0 个 nibble 内、perm_bit之后是不是散到了 4 个 nibble 的第 0 位。这一步五分钟的事，能省掉后面几小时。
4.2 固定种子与可复现实验
这类统计性实验最怕的就是「跑一次成功、换一次随机就失败」，而你没法判断是代码错了还是运气不好。解决办法是把随机源固定下来，让每次运行得到完全相同的样本序列，这样任何差异都只能来自代码改动。
#include <random> struct Rng { std::mt19937_64 g; explicit Rng(uint64_t seed) : g(seed) {} uint16_t next() { return (uint16_t)(g() & 0xFFFF); } }; // 生成 N 对满足差分 d0 的明文，返回 2N 个明文和对应密文 static void gen_pairs(Rng& rng, int N, uint16_t d0, const ToyCipher& tc, std::vector<uint16_t>& pt, std::vector<uint16_t>& ct) { pt.resize(2 * N); ct.resize(2 * N); for (int i = 0; i < N; ++i) { uint16_t p1 = rng.next(); uint16_t p2 = p1 ^ d0; pt[2 * i] = p1; ct[2 * i] = tc.encrypt(p1); pt[2 * i + 1] = p2; ct[2 * i + 1] = tc.encrypt(p2); } }std::mt19937_64的周期和分布质量对这类实验绰绰有余。种子固定成常量，实验做完再换几个种子验证稳定性——注意是实验做完之后换，不是边调边换。
参数上，N的经验值是 $10/p$（$p$ 是特征概率）。比如 $p = 1/512$，取 $N = 5120$ 起；想稳一点就取 $20/p$。这个系数不是玄学，它对应的是「正确密钥计数 $Np = 10$ 时，与错误密钥的期望 $N/16 = 320$ 之间……」，等一下，这里方向反了：正确的判据是 $Np$ 要显著高于 $N/16$，也就是 $p > 1/16$ 才不需要额外筛选。当 $p = 1/512$ 时，单靠 $N$ 堆是堆不出来的——必须用「密文对的某些位置满足约束」这类筛选来把噪声压下去。
这就是入门材料里最少讲、但实际最卡人的一步：特征概率低的时候，靠加数据是没用的，因为错误密钥的计数也线性增长。真正起作用的是筛选，把不满足特征前提的样本对扔掉，让剩余样本的 $p_{\text{条件}}$ 高起来。筛选条件怎么定？看特征在第 3 轮输出端涉及哪些 nibble，只对那些 nibble 施加约束。约束一加，样本利用率可能掉到 1/16，但条件概率涨了 16 倍，净效果是老实地把信噪比从 1 以下拉到 1 以上。
4.3 数据量与复杂度：什么时候该停
把各段的代价算清楚，才知道程序卡在哪。
| 阶段 | 复杂度 | 16 比特玩具结构上的量级 |
|---|---|---|
| DDT / LAT 打表 | $O(2^n \cdot 2^n \cdot 2^n)$ | 4096 次，微秒级 |
| 差分特征搜索（3 轮，beam 剪枝） | 约 $O(\text{BEAM} \times 16^4)$ | 秒级 |
| 线性壳搜索（3 轮，beam 剪枝） | 约 $O(\text{BEAM} \times 16^4)$ | 秒级 |
| 密钥恢复（$N$ 对，16 候选） | $O(16N)$ | $N = 10^5$ 时百万次，毫秒级 |
| 线性攻击（$N$ 样本，16 候选） | $O(16N)$ | 同上 |
真正耗时的是特征搜索，不是攻击。很多人反过来，花两小时优化计数器循环，却没意识到程序 99% 的时间耗在搜索树上。
性能上值得做的一件事：把「差分搜索」和「攻击」拆成两个可执行文件，中间结果（特征、dout、概率）用文本存盘。这样调攻击参数时不用重跑搜索，反复试验的成本从分钟级降到秒级。
5. 避坑与排查：五个让人白跑一整晚的坑
5.1 现象：恢复出的子密钥很稳定，但跟真值差一个定值
现象描述：计数器每一轮跑出来的最大值都很集中，说明统计信号是有的，但那个最大值对应的密钥 nibble 跟实际rk[4]的对应位置总是差一个固定值，换个明文样本还是差同一个值。
原因：最可能是 S 盒的逆表用法错位。recover_last_nibble里做的是 $S^{-1}(c_i \oplus k)$，如果真实加密里最后一轮是 $S(s_{3,i}) \oplus rk_{4,i}$，那反推就应该是 $S^{-1}(c_i \oplus rk_{4,i})$。但如果加密实现里写成了 $S(s_{3,i} \oplus rk_{4,i})$（密钥先进 S 盒），反推公式就变成 $S^{-1}(c_i) \oplus rk_{4,i}$，两者差一个 $S^{-1}$ 的作用，表现出来就是一个定值偏移。
解决：把encrypt最后一轮和recover_last_nibble的反推公式并排放着看，确认密钥异或和 S 盒的先后顺序一致。更稳的做法是写一个单元测试：给定已知rk[4]，手工构造 $s_{3,i}$，跑一遍encrypt，再跑一遍反推，看能不能还原。
5.2 现象：计数器几乎平均，最高值跟第二名差不到 5%
现象描述：16 个候选取值里，最大计数和次大计数只差几个百分点，重复跑几次，最大值落在哪个候选上完全随机。
原因：信噪比不足。要么特征概率估高了（比如把多轮概率乘的时候漏了一轮），要么样本量按 $1/p$ 取而没有考虑错误密钥的 $N/16$ 基底，要么就是特征本身选错了——搜出来的那条链在真实的加解密实现里并不成立。
解决：分三步查。第一步，用已知密钥跑一次，验证正确密钥的计数确实排第一；如果连已知密钥都排不到第一，问题在代码。第二步，把 $N$ 翻 10 倍再跑，看正确密钥的领先幅度有没有同步扩大；如果没有，说明 $p$ 估计错了。第三步，直接用正确密钥手工验证几百对样本，数一数有多少对真的满足特征，跟理论 $Np$ 对比。
5.3 现象：程序跑十几分钟没动静，CPU 占满但没输出
现象描述：编译完了运行，风扇狂转，屏幕上什么都没打印，Ctrl+C 之后发现卡在search_trail里。
原因：搜索树膨胀。min_cnt设得太小（比如 2），第一层就展开出几百个分支，三层下来是千万级，加上每层还要对std::vector排序，内存和时间一起爆炸。另一个可能是BEAM设太大而没意识到排序本身的 $O(n \log n)$ 成本。
解决：把min_cnt从 2 调到 4，BEAM从 40000 降到 5000，先跑通流程看输出长什么样，再逐步放开。更好的做法是在搜索里加日志，每层结束打印一次layer.size()，一眼就能看出是哪一层炸的。
5.4 现象：同一份代码，换随机种子结果时好时坏
现象描述：种子 A 跑出来正确密钥排第一，种子 B 跑出来排第三，种子 C 干脆没信号。
原因：样本量贴着临界值。如果 $N$ 只勉强够让正确密钥的期望计数比噪声高一点点，那结果的随机波动就会主导，成功率大概在 50% 上下，表现出来就是「时好时坏」。
解决：这不是 bug，是统计规律。做法是把 $N$ 提到经验值的 2 到 3 倍，然后跑 20 个不同种子统计成功率，成功率应该在 95% 以上。如果提了 $N$ 还是不行，回到 5.2 的三步排查。
5.5 现象：DDT 打出来行和不是 16，或者表不对称
现象描述：加了自检打印，发现某一行加起来是 15，或者ddt[a][b]和ddt[b][a]对不上。
原因：两个常见来源。一是 S 盒数组里出现了重复值（不是置换），导致某些输出差分永远打不到；二是uint8_t在移位或异或时被整型提升坑了，(x >> (4*i)) & 0xF如果写成x >> 4*i & 0xF，运算符优先级会让结果全错。
解决：先加一道断言，检查 S 盒是不是 0 到 15 的一个排列：
static bool check_sbox() { bool seen[16] = {false}; for (int i = 0; i < 16; ++i) { if (seen[S[i]]) return false; seen[S[i]] = true; } return true; }再检查 DDT 的行和与列和。行和必然是 16（每个 $x$ 贡献一次），列和在 $\alpha \ne 0$ 时是偶数、$\alpha = 0$ 时只有第 0 列是 16。这两个不变量一旦写进assert，很多低级错误在启动阶段就会被拦下来。
6. 验证与进阶：怎么确认攻击成功而不是运气好
判断一次攻击「真的成功了」，不能只看计数器最大值。我习惯跑三层验证，一层比一层严。
第一层是已知密钥自检。用固定rk跑一次完整攻击，确认恢复出的 nibble 等于真实值。这一步不涉及统计，纯粹验证链路（打表 → 搜索 → 部分解密 → 计数）有没有接错。跑不通就别往下走。
第二层是失败率统计。换 30 个随机种子各跑一次，统计成功次数。一个健康的实现对 3 轮 ToyCipher 应该在 30 次里成功 29 次以上。低于这个数说明样本量不够或者筛选条件没做好，别急着优化代码，先加大 $N$。
第三层是「错误密钥的分布形态」。把 16 个候选的计数排序打印出来，正确密钥应该明显跳出，第 2 到第 16 名应该挤在一起、彼此差距在噪声范围内。如果错误密钥之间也分层明显，说明你的统计量还耦合了别的结构——通常是特征搜索搜出了多条概率相近的链，实际攻击时被它们互相干扰。
static void report(const int cnt[16], int truth) { int idx[16]; for (int i = 0; i < 16; ++i) idx[i] = i; std::sort(idx, idx + 16, [&](int a, int b){ return cnt[a] > cnt[b]; }); for (int r = 0; r < 16; ++r) printf("#%2d key=%X cnt=%6d %s\n", r, idx[r], cnt[idx[r]], idx[r] == truth ? "<== truth" : ""); }这张表比任何单一数字都有信息量。正确密钥排第一、第二名的计数只有它的 1/1.2 左右，是我认为「跑对了」的典型形态。
进阶方向上有三件事值得做。一是把结构换成 8 比特 S 盒，此时 DDT 变成 $256 \times 256$，搜索和攻击的量级都上一个台阶，是检验代码是否工程化的好压力测试。二是给特征搜索加多线程——每一层的展开天然可并行，加个std::thread池就能把搜索时间压下去。三是把线性攻击的样本量公式从经验值换成基于信噪比的定量估计，这样换结构时不用重新拍脑袋。
最后一个习惯：每次改完代码，不管改的是 S 盒、置换表还是样本量，我都强制走一遍「已知密钥自检 → 30 种子失败率统计」。这套流程看着笨，但它是我从「跑出一堆漂亮数字然后发现全是噪声」的日子里攒下来的唯一可靠办法。希望帮到你。
本文还有配套的精品资源，点击获取
