C++实战：从零跑通差分分析与线性分析入门

简介：这份资源面向密码学与信息安全方向的初学者，围绕Howard M. Heys教授发表于Cryptologia的经典教程《A Tutorial on Linear and Differential Cryptanalysis》展开，借助一个仅5轮、16比特的玩具密码，直观讲解差分分析与线性分析两大分组密码攻击方法的核心原理。压缩包共6个文件，约662KB，包含教程PDF原文、线性分析与差分分析的C++源码及对应可执行程序，以及一份文件说明文本，便于读者边读论文边动手复现算法，在代码调试中加深对S盒、特征概率与密钥恢复过程的理解。目前已有553人学习下载。对于从《分组密码的攻击方法与实例分析》等教材入门、希望把抽象理论落到实处的读者，这份资料提供了从论文到可运行代码的完整链路，是建立差分与线性分析直觉认知的实用起点。

1. 从零搞懂差分分析：它到底在解什么题

你可能听过「差分分析」这四个字，第一反应是数学课上的差分方程，或者是数据分析里的差分运算。但在密码学这个圈子里，它指的是一件很具体的事：观察输入数据改了一位之后，输出数据会跟着怎么变，然后利用这个变化规律去反推密钥。打个比方，你有一台自动售货机，你投进去的硬币重量稍微变了一点点，掉出来的饮料却总是固定地偏向某一侧——差分分析就是研究「投币重量差多少，出货偏移多少」的学问。它不要求你懂高深代数，入门阶段只需要你会写 C++ 循环、会看二进制，就能亲手跑出一个完整的分析例子。这份资源就是给「完全没接触过密码分析、但会一点编程」的人准备的，它把差分分析和线性分析从论文里的公式，拆成了你能编译、能改参数、能看到结果的代码。你不需要先成为数学家，只需要跟着走一遍，就能明白这两个方法到底在干什么。

2. 为什么值得学：差分与线性分析的入门价值

2.1 它们是最经典的两把「尺子」

密码学里设计一个加密算法，不能只说「我觉得它安全」，得有人去量它到底有多安全。差分分析和线性分析就是最早、也最常用的两把尺子。差分分析看的是「输入差异如何影响输出差异」，线性分析看的是「输入和输出之间有没有近似线性的关系」。如果你以后想读懂分组密码的设计文档、想理解为什么某个算法要加那么多轮，这两把尺子就是你绕不开的基础工具。很多现代密码的攻击方法，本质上都是这两个思路的变种或组合。入门阶段先把最原始版本搞明白，后面再看进阶内容就不会觉得是空中楼阁。

2.2 对新手友好：不需要高深数学也能上手

很多人一听「密码分析」就觉得要先学数论、抽象代数、概率论。其实差分分析和线性分析的入门版本，核心操作非常朴素：选两个明文，让它们只差一个比特，然后看加密后的密文差了多少个比特。你只需要会写 C++ 的位运算、会统计频率，就能跑出第一条差分特征。这份资源里的 C++ 实现就是按这个思路写的，没有模板元编程，没有复杂继承，就是循环加数组。我第一次学的时候，最怕的就是打开一个项目看到几十个文件不知道从哪读起，所以这里建议你从最简单的那个源文件开始，先跑通一个 4 轮的小例子，再去看更长的轮数。

2.3 能帮你建立「攻击者视角」

平时写代码是「我输入什么，程序就输出什么」，但差分分析让你反过来想：如果我想要某个输出，我应该怎么构造输入？这种逆向思维在安全领域非常值钱。哪怕你以后不做密码分析，去做协议测试、漏洞挖掘，这种「构造特定输入观察输出偏差」的习惯也会让你比别人更快找到问题。入门阶段不用追求攻击完整算法，先在一个简化版的加密函数上跑出偏差，你就能体会到这种视角的转变。

3. 第一个例子：用 C++ 跑通一条差分路径

3.1 先准备一个最小的加密函数

为了让你专注在差分分析本身，我们先不碰真实算法，而是写一个 8 比特的简化加密函数：把输入分成左右各 4 比特，做几轮异或和替换。这个函数足够小，小到你可以在纸上推演，也足够让你看到差分传播的效果。下面这段代码就是最基础的版本，你可以直接复制到一个.cpp文件里编译。

#include <cstdint> #include <iostream> #include <vector> // 一个极简的 8 比特加密函数：左 4 位和右 4 位各做一轮异或和替换 uint8_t simple_encrypt(uint8_t plain, uint8_t key) { uint8_t left = (plain >> 4) & 0x0F; // 高 4 位 uint8_t right = plain & 0x0F; // 低 4 位 // 第 1 轮：右半部分异或密钥低 4 位，然后与左半部分交换 right ^= (key & 0x0F); uint8_t temp = left; left = right; right = temp; // 第 2 轮：再次异或密钥高 4 位，再交换 right ^= ((key >> 4) & 0x0F); temp = left; left = right; right = temp; // 合并回 8 比特 return (left << 4) | right; } int main() { uint8_t key = 0x3A; // 随便选一个密钥 uint8_t p1 = 0x12; // 第一个明文 uint8_t p2 = p1 ^ 0x01; // 第二个明文，只差最低位 uint8_t c1 = simple_encrypt(p1, key); uint8_t c2 = simple_encrypt(p2, key); std::cout << "明文差: " << (p1 ^ p2) << "\n"; std::cout << "密文差: " << (c1 ^ c2) << "\n"; return 0; }

这段代码里，simple_encrypt就是我们的「黑匣子」。p1和p2只差一个比特，c1和c2的异或值就是密文差。你运行一次会看到，输入差是0x01，输出差可能不是0x01，而是某个固定的值。这个固定值就是一条差分特征。代码里的key你可以随便改，但注意：差分分析的目标是在不知道密钥的情况下预测这个输出差，所以后面我们会用统计的方法去猜密钥。

3.2 统计输出差，找到最可能的那条路

单次实验只能看到一个结果，要确认一条差分路径是否稳定，需要跑很多组明文。下面这段代码在原来的基础上加了一个循环，统计 1000 组只差一个比特的明文对，看输出差出现的频率。

#include <cstdint> #include <iostream> #include <map> uint8_t simple_encrypt(uint8_t plain, uint8_t key) { uint8_t left = (plain >> 4) & 0x0F; uint8_t right = plain & 0x0F; right ^= (key & 0x0F); uint8_t temp = left; left = right; right = temp; right ^= ((key >> 4) & 0x0F); temp = left; left = right; right = temp; return (left << 4) | right; } int main() { uint8_t key = 0x3A; std::map<uint8_t, int> diff_count; // 遍历所有高 4 位，低 4 位固定为 0，这样输入差始终是 0x01 for (int hi = 0; hi < 16; ++hi) { uint8_t p1 = (hi << 4) | 0x00; uint8_t p2 = p1 ^ 0x01; uint8_t c1 = simple_encrypt(p1, key); uint8_t c2 = simple_encrypt(p2, key); diff_count[c1 ^ c2]++; } // 打印出现次数最多的输出差 for (auto& kv : diff_count) { std::cout << "输出差 " << (int)kv.first << " 出现 " << kv.second << " 次\n"; } return 0; }

运行后你会看到某个输出差出现的次数明显高于其他值。这个最高的那个就是「最可能的差分路径」。在真正的差分分析里，我们会用这个高概率路径去给密钥打分：猜一个密钥，解密一轮，看输出差是否符合预期，符合就加分，最后得分最高的密钥就是正确密钥。入门阶段你不需要马上做完整密钥恢复，先把这个统计过程跑通，理解「概率偏差」是怎么来的，就已经迈过了最难的那道坎。

提示：如果你把key改成别的值，输出差的分布会变，但通常仍有一个峰值。这说明差分路径的概率和密钥有关，但攻击者可以在不知道密钥的情况下通过大量统计找到它。

3.3 线性分析入门：换个角度看偏差

差分分析看的是「差」，线性分析看的是「和」。具体说，它找的是明文的某些比特异或起来，和密文的某些比特异或起来，两者相等的概率偏离 50%。如果偏离得足够多，就能用来猜密钥。下面这段代码在同一个加密函数上，统计一个最简单的线性关系：明文最低位异或密文最低位等于 0 的概率。

#include <cstdint> #include <iostream> uint8_t simple_encrypt(uint8_t plain, uint8_t key) { uint8_t left = (plain >> 4) & 0x0F; uint8_t right = plain & 0x0F; right ^= (key & 0x0F); uint8_t temp = left; left = right; right = temp; right ^= ((key >> 4) & 0x0F); temp = left; left = right; right = temp; return (left << 4) | right; } int main() { uint8_t key = 0x3A; int count_zero = 0; int total = 0; for (int p = 0; p < 256; ++p) { uint8_t c = simple_encrypt((uint8_t)p, key); // 取明文最低位和密文最低位 int bit_p = p & 1; int bit_c = c & 1; if ((bit_p ^ bit_c) == 0) { count_zero++; } total++; } double prob = (double)count_zero / total; std::cout << "线性关系成立的概率: " << prob << "\n"; return 0; }

如果概率正好是 0.5，说明这个线性关系没有用。如果明显大于或小于 0.5，就说明存在线性偏差，可以用来做密钥恢复。你可以改密钥、改取的比特位置，多试几次，感受一下偏差是怎么随密钥变化的。线性分析的入门难点在于找「好的线性逼近」，但第一步永远是先会算这个概率。

4. 避坑指南：新手最容易翻车的五个地方

4.1 把「差分」和「微分」搞混

现象：看到差分分析，以为是求导数那种微分。原因：中文里「差分」和「微分」只差一个字，但密码学里的差分指的是异或差，不是数学分析里的微分。解决：记住一个口诀——差分分析里，差就是异或，两个数异或的结果就是它们的差。你不需要极限，不需要导数，只需要位运算。

4.2 一上来就啃完整算法

现象：打开资料直接看 16 轮甚至 32 轮的完整攻击，看了三天还在第一页。原因：完整攻击的轮数多、概率低、需要大量明文对，新手没有直观感受。解决：先用 2 到 4 轮的简化版本跑通，看到概率偏差，再逐步加轮数。这份资源里的 C++ 实现就是按轮数分层的，建议从最少轮数的那个函数开始读。

4.3 忽略密钥调度的影响

现象：在简化函数上跑通了差分路径，换到真实算法上发现概率完全不对。原因：真实算法的密钥调度会让每一轮的密钥不同，差分路径的概率会随轮数衰减。解决：入门阶段先假设每轮密钥相同，把核心传播规律搞清楚。等你理解了单轮偏差，再去处理密钥调度，就不会被细节淹没。

4.4 统计样本太少就下结论

现象：跑了 10 组数据，看到某个输出差出现 3 次，就以为找到了高概率路径。原因：随机波动在样本少的时候非常大。解决：至少跑几千组，最好上万组。上面代码里用 16 组只是演示，你实际做的时候把循环改成 10000 次，结果才稳定。我第一次跑的时候只用了 100 组，结果峰值飘来飘去，后来加到 5000 组才固定下来。

4.5 不写注释，过两天自己都看不懂

现象：代码跑通了，过一周回头看，不知道哪个变量是明文差、哪个是密文差。原因：差分分析的变量命名很容易混，p1、p2、c1、c2、diff如果不写清楚，回头就是一团乱麻。解决：在每个变量后面加一行注释，比如uint8_t p2 = p1 ^ 0x01; // 与 p1 只差最低位。别嫌麻烦，这是血泪经验。

5. 下一步学什么：从跑通例子到独立分析

5.1 先把轮数加一，观察概率怎么掉

你现在跑的是 2 轮版本，输出差的峰值可能很明显。试着把simple_encrypt复制一份，改成 3 轮、4 轮，再跑同样的统计。你会看到峰值出现的次数逐渐下降，其他输出差的次数慢慢上升。这个下降速度就是差分路径的概率衰减。入门阶段不需要推导公式，只要亲手看到这个趋势，你就理解了为什么轮数越多越安全。

5.2 尝试恢复一个密钥比特

在 2 轮版本上，你可以做一件很有成就感的事：只猜密钥的最低 4 位。具体做法是，对每个候选密钥（0 到 15），用密文反推一轮，看反推后的输出差是否符合你统计到的高概率路径。符合次数最多的那个候选，就是正确密钥。下面是一个骨架代码，你可以自己补全。

// 假设你已经统计出高概率输出差为 target_diff // 对每个候选密钥 k 打分 for (int k = 0; k < 16; ++k) { int score = 0; for (每个明文对) { // 用 k 对 c1 和 c2 各反推一轮 // 如果反推后的差等于 target_diff，score++ } // 记录 score，最后选最大的 }

这个骨架里最关键的是「反推一轮」的函数，它其实就是加密函数里最后一轮的逆操作。你写的时候注意异或的逆还是异或，交换的逆还是交换。写完之后跑一遍，看看得分最高的候选是不是你最初设的密钥。如果是，恭喜你，你已经完成了一次完整的密钥恢复。

5.3 线性分析也照这个路子走

线性分析的下一步是找多条线性逼近，然后合并它们的偏差。入门阶段你可以先固定一条逼近，改变密钥，看概率怎么变。然后试着用这条逼近去给密钥打分：对每个候选密钥，解出一部分密文，算线性关系的成立次数，选偏差最大的那个。你会发现，和差分分析一样，核心操作就是统计加打分，没有魔法。

5.4 推荐的学习节奏

这张表只是参考，你完全可以按自己的节奏来。关键是每一步都要亲手跑代码，不要只看不练。我从开始学差分分析到能独立恢复一个简化算法的密钥，用了大概三周，中间翻车无数次，最常见的就是统计样本不够和变量搞混。从那以后我每次写分析代码，都强制自己在每个变量后面写注释，并且先跑 1000 组看趋势，再决定要不要加样本。希望这份资源能帮你少走一点弯路，也希望你跑通第一个例子之后，会想继续往更深的地方走。

本文还有配套的精品资源，点击获取