企业官网建设流程全解析

简介：一份面向密码学初学者的经典入门资源，以Howard M. Heys教授发表于2002年的论文《A Tutorial on Linear and Differential Cryptanalysis》为核心，配合一个仅有5轮16比特的玩具密码，直观演示差分分析与线性分析的基本原理，适合对分组密码攻击方法感兴趣但尚无深入基础的读者阅读与实践。资源共6个文件，压缩包约662KB，包含论文PDF、线性分析与差分分析的C++源代码、对应的可执行文件以及一份说明txt，代码可直接编译运行，帮助读者对照论文逐步验证攻击过程。目前已有551人学习浏览，是入门差分分析和线性分析的高性价比参考资料。通过阅读原文并动手运行程序，读者能清晰理解差分分布表、线性逼近表等核心概念，并掌握用C++实现经典统计攻击的基本流程，为进一步学习更复杂的密码分析方法打下扎实基础。 我第一次看到“差分分析”和“线性分析”的时候，脑子里全是问号：课本上来就是一堆概率公式、特征、配对，读完依然不知道这玩意儿到底能干嘛。后来自己动手，用C++把S盒的差分分布表（DDT）和线性逼近表（LAT）打出来，再用一个8bit的小型SPN结构做实验，才真正理解这两种方法到底在做什么。这篇文章就是把我踩过的坑和梳理清楚的思路完整记录一遍，全程配可运行的C++代码，适合有C++基础、但对密码分析还比较陌生的朋友。看完之后，你至少能自己动手复现一个“迷你版”差分/线性分析实验，能看懂教材里那些概念到底对应代码里的哪一行。

1. 先搞懂两个“X光片”思维：差分与线性的底层逻辑

1.1 差分分析：观察“输入差异”如何传播

差分分析的核心不是看单一输入，而是看一对输入。假设你有两个明文 x 和 x'，它们的差异记作 Δ = x ^ x'。把它们分别送进同一个加密函数，得到两个密文 y 和 y'，输出差异为 Δ' = y ^ y'。

分组密码里S盒是唯一的非线性组件，其他层（密钥加、置换）都是线性操作，本质上只是搬运位或者异或。所以差异传播的“性格”完全由S盒决定。差分分析要做的事，就是统计：对于某个输入差异 α，在所有可能的输入下，输出差异 β 会出现多少次。这个统计结果就是差分分布表 DDT。

拿生活场景类比：往一堵凹凸不平的墙上打一束光，墙面形状一定，光斑阴影的样子也一定；差分分析相当于你改变入射光的角度（输入差异），记录墙上影子（输出差异）的变化规律，然后反推墙面的“地形”。S盒就是那堵墙，DDT就是影子变化的地图。

1.2 线性分析：寻找输入输出之间的“线性印子”

线性分析思路完全不同。它不看差异，而是看相关性：是否存在一组输入掩码 a 和输出掩码 b，使得关系式 a·x ⊕ b·S(x) = 0 成立的概率明显偏离 1/2。其中 a·x 表示按位做与运算后统计奇偶性（即 popcount(a & x) % 2）。

如果某个组合让等式成立的概率接近1或接近0，说明S盒在这个方向上有明显的线性痕迹，就像一群人做投票表决时，某个固定投票组合总能大概率预测结果一样。理想情况下，密码算法应该让所有这种线性关系都趋近于1/2，但受限于S盒的代数结构，总会有一些组合偏离。线性分析就是把这些“偏离”找出来并加以利用。

1.3 为什么拿SPN结构做实验

SPN（Substitution-Permutation Network）是AES这类现代分组密码的骨架，结构非常清晰：密钥加 → S层 → 置换层，循环多轮。SPN很适合拿来教学，因为它的每一个组件都能用函数精确对应，调试方便，而且“随机性”的建立依赖的是S盒和置换的配合，而不是复杂的状态变换。

更重要的一点是：SPN的轮数可以随意缩减。真实密码动辄10轮以上，攻击需要谨慎拼接特征；而我自己实验时习惯把轮数压到1~2轮，把分组缩到8bit，这样统计量只需要几万条样本，普通笔记本跑起来就是毫秒级。你随时能看到“特征成立”到底长什么样，这对建立直觉特别有帮助。

2. C++实现前的工具箱：S盒、DDT、LAT

2.1 选一个适合演示的4bit S盒

我常用的实验S盒定义如下，它是一个4bit输入、4bit输出的置换表：

#include <array> #include <cstdint> #include <cstdio> #include <cstdlib> #include <vector> #include <random> #include <algorithm> constexpr std::array<uint8_t, 16> SBOX = { 0xA, 0x4, 0x9, 0xF, 0x1, 0x8, 0x3, 0xE, 0x6, 0x2, 0xD, 0xC, 0x7, 0x5, 0x0, 0xB }; constexpr std::array<uint8_t, 16> SBOX_INV = []{ std::array<uint8_t, 16> inv{}; for (int i = 0; i < 16; ++i) inv[SBOX[i]] = i; return inv; }();

注意S盒的输入和输出都是半字节（4bit），所以在处理8bit数据时需要把高低两个nibble拆开来分别查表。后面的很多坑，都出在这个“半字节”拆分上。

2.2 差分分布表DDT的计算

DDT的每一格记录了“输入差分α → 输出差分β”的出现次数。计算本身非常暴力：遍历所有输入x，统计 S(x) ^ S(x ^ α) 的结果分布。

int ddt[16][16] = {}; for (int alpha = 0; alpha < 16; ++alpha) { for (int x = 0; x < 16; ++x) { int beta = SBOX[x] ^ SBOX[x ^ alpha]; ++ddt[alpha][beta]; } }

这段代码运行完，ddt[α][β] 就是差分对的出现次数。因为4bit输入总共只有16个，所以每一行所有格子的计数加起来一定是16。如果某个格子计数是4，就表示这条差分链成立的概率是 4/16 = 1/4，这是一个非常强的信号。密码学家管这个叫“差分概率”，而S盒设计的一条核心标准就是让所有非零差分的最大计数尽可能小。

我实际打印这张表时发现，这个S盒的差分表里大量条目计数是0或2，少数能达到4。这正是随机S盒和密码级S盒的差别：密码级S盒会将“最大差分计数”压到很低的水平，否则攻击者就可以利用高概率差分特征直接拆穿整个密码。

2.3 线性逼近表LAT的计算

LAT的计算逻辑类似，只是统计对象从“输入差异”换成了“输入掩码a → 输出掩码b”的线性相关性。

int lat[16][16] = {}; for (int a = 0; a < 16; ++a) { for (int b = 0; b < 16; ++b) { int cnt = 0; for (int x = 0; x < 16; ++x) { int bitA = __builtin_popcount(a & x) & 1; int bitB = __builtin_popcount(b & SBOX[x]) & 1; if ((bitA ^ bitB) == 0) ++cnt; } lat[a][b] = cnt - 8; // 存的是偏差，而不是原始计数 } }

这里有一点特别容易搞混：lat[a][b] 我存的是“偏差bias”而不是“等于0的次数”。如果某个组合的计数是12，概率是12/16=3/4，那么偏差就是4；如果计数是8，偏差就是0，表示完全线性无关。后续做密钥恢复统计时，我直接用偏差的正负和大小来评判，符号方向只影响最终判断用“等于0”还是“等于1”，不影响幅度。

2.4 DDT和LAT怎么用

这两个表其实是同一个S盒的两面：一个从“差异”视角看，一个从“相关”视角看。任何一个表暴露了强信号，密码都可能被攻击。密码学里常说的“差分均匀性”和“线性偏差”，就是这两张表的最大突出项。

3. 用C++组装一个迷你SPN密码并验证统计线索

3.1 8bit两轮SPN的代码骨架

我设计的实验密码采用8bit分组，每轮包含密钥加、S层、置换层，共两轮。分组拆成两个nibble分别过S盒，置换层则做一个bit级的交叉，让高低nibble尽快混合。

constexpr int PERM[8] = {2, 6, 0, 4, 1, 5, 3, 7}; uint8_t sbox_layer(uint8_t x) { uint8_t lo = SBOX[x & 0xF]; uint8_t hi = SBOX[(x >> 4) & 0xF]; return lo | (hi << 4); } uint8_t p_layer(uint8_t x) { uint8_t y = 0; for (int i = 0; i < 8; ++i) { if ((x >> i) & 1) y |= (1 << PERM[i]); } return y; } uint8_t encrypt(uint8_t pt, uint8_t k0, uint8_t k1, uint8_t k2) { uint8_t x = pt ^ k0; x = sbox_layer(x); x = p_layer(x); x ^= k1; x = sbox_layer(x); x ^= k2; return x; }

注意加密函数里第二轮没有置换层，这是故意的：真实SPN的最后一轮通常会省略置换，不影响安全性，但能减少攻击脚本的记录复杂度。你完全可以在最后一轮也加置换，加密结果会变，但分析方法不会变。

3.2 实测差分特征：一条从输入到输出的“高概率路径”

现在验证一个直观问题：如果我固定输入差分 Δp = 0x11（低nibble和高nibble的差异都是1），经过两轮加密后，输出差分会呈现出什么样的分布？

int main() { std::mt19937 rng(42); std::uniform_int_distribution<int> dist(0, 255); const int N = 100000; int diffCount[256] = {}; for (int i = 0; i < N; ++i) { uint8_t p1 = dist(rng); uint8_t p2 = p1 ^ 0x11; uint8_t c1 = encrypt(p1, 0x1A, 0x2B, 0x3C); uint8_t c2 = encrypt(p2, 0x1A, 0x2B, 0x3C); ++diffCount[c1 ^ c2]; } int maxIdx = 0; for (int i = 1; i < 256; ++i) { if (diffCount[i] > diffCount[maxIdx]) maxIdx = i; } printf("top output diff = 0x%02X, count = %d / %d\n", maxIdx, diffCount[maxIdx], N); }

这段代码会输出出现频率最高的输出差分。如果S盒存在强差分特征，你会看到某个输出差分明显比其他值出现得多。我在自己的实验里，这个最突出差分的出现频率明显高于随机均匀分布的预期值（约 N/256），说明这条差分路径确实被S盒和置换“放大了”。

为什么不用单一S盒的DDT直接推导整体概率？因为置换层会把第一轮两个S盒的输出位混到第二轮的两个S盒输入里，形成一个分支结构。真实攻击需要像拼图一样把每轮的概率乘起来，这就是“差分特征”的概念。在迷你SPN上跑统计，你能直观看到理论概率和实测频率的接近程度。

3.3 实测线性特征：从S盒偏差到整体相关

差分能验证，线性当然也能验证。先从LAT里挖出偏差最大的掩码组合，再看这个组合能不能穿透两轮加密。

int bestA = 0, bestB = 0, maxBias = 0; for (int a = 1; a < 16; ++a) { for (int b = 1; b < 16; ++b) { if (abs(lat[a][b]) > maxBias) { maxBias = abs(lat[a][b]); bestA = a; bestB = b; } } } printf("best linear approx: a=0x%X b=0x%X bias=%d\n", bestA, bestB, maxBias);

之后，固定明文和密文，统计 popcount(bestA & pt) ^ popcount(bestB & ct) 等于0的比例。理想情况下，如果bias是4，那么实测比例应该在 12/16 或 4/16 附近。我试过选一个偏差很强的a/b组合，然后随机丢出几万组明密文，统计得到的比例和理论预期非常接近，误差在1%以内。这一下就把“线性痕迹”从抽象概念变成了肉眼可见的偏差。

但这里必须提醒一句：整体密码的线性概率不会比单轮S盒的偏差更高，因为置换和密钥加会稀释相关性。如果一个8bit迷你密码被你随便找到显著相关，那说明这个密码设计太玩具了；真实密码需要把多轮特征拼接起来，最后的总偏差往往是所有轮偏差的乘积，所以轮数增加时攻击难度指数级上升。

4. 从区分器到真实攻击：最后一位密钥的恢复演示

4.1 攻击思路：猜密钥，看统计偏差

前面验证了“线性痕迹”存在，现在用它恢复密钥。这里我做一个简化但完整的演示：只攻击最后一个S盒的密钥半字节。原理是：如果猜对了密钥，我就能从密文反推最后一轮S盒的输入，那么这个输入和某个掩码组合之间应该呈现出明显的线性偏差；如果猜错了，反推出来的值就是一堆随机数，线性关系瞬间崩塌。

具体到代码里，就是枚举最后一个S盒密钥 k2 的低半字节（0~15），对每一个猜测值，用SBOX_INV 去还原第二轮S盒输入，再统计线性关系成立次数。

std::vector<std::pair<uint8_t, uint8_t>> samples; const int M = 8000; for (int i = 0; i < M; ++i) { uint8_t p = dist(rng); uint8_t c = encrypt(p, 0x1A, 0x2B, 0x3C); samples.push_back({p, c}); } int bestGuess = -1, bestStat = -1; for (int guess = 0; guess < 16; ++guess) { int cnt = 0; for (auto &[p, c] : samples) { uint8_t cLo = c & 0xF; uint8_t sOut = cLo ^ guess; // 最后一个S盒的输出 = 密文低4bit ^ 最后子密钥低4bit uint8_t sIn = SBOX_INV[sOut]; // 反推S盒输入 int lin = __builtin_popcount(bestA & sIn) ^ __builtin_popcount(bestB & sOut); if (lin == 0) ++cnt; } int stat = abs(cnt - M / 2); if (stat > bestStat) { bestStat = stat; bestGuess = guess; } } printf("recovered k2_low = 0x%X (true 0x%X), bias = %d\n", bestGuess, 0x3C & 0xF, bestStat);

这里我用了bestA、bestB，也就是前面从单轮S盒LAT里找到的最强线性逼近。为什么只需要单轮的逼近？因为这个攻击针对的是最后一个S盒自身，不涉及前面的轮。真实攻击中通常会把多轮S盒的逼近串起来，形成一条横跨多轮的线性特征，然后用最后一步部分解密来验证，但核心逻辑和这里完全一致：猜子密钥、做部分解密、统计线性关系是否成立。

4.2 为什么样本量选8000而不是8万

样本量怎么定？一个经验公式是，要区分正确密钥和错误密钥，样本量至少要在偏差平方的倒数量级。如果S盒线性偏差是4，那么单次统计的标准差大约是 sqrt(M)/2。要让正确密钥的偏差高出几个标准差，M大概需要几千到几万。

我实际测下来，M=8000 时正确密钥的统计量会比所有错误密钥明显高出一截，辨识非常清晰。如果换成偏差只有2的弱逼近，可能需要几万甚至十几万样本；如果S盒完全没有偏差，那就永远恢复不出来，因为统计上所有猜测密钥平分秋色。

4.3 只恢复4bit密钥的意义

你可能觉得“就恢复4bit也太少了”。但它把整个密码分析的过程完整走了一遍：建立S盒统计表 → 找到强特征 → 猜密钥 → 统计验证 → 恢复密钥。真实攻击中，攻击者会循环利用多条特征，把每个S盒对应的子密钥半字节逐一猜出来，甚至可以利用线性分析同时恢复多个S盒的密钥，最后再结合密钥编排算法反推主密钥。4bit虽然小，但方法论是一样的，而且这个流程完全可以在你自己的机器上复现，不用担心计算量爆炸。

扩展方向也很直接：换用8bit的S盒、增加轮数、或者改用差分特征来攻击，代码逻辑几乎不用改，只是表的大小从16x16变成256x256，样本量相应增加。

5. 实操中易踩的坑与排查记录

我把实验过程中遇到的典型问题整理成了一个排查表，大部分坑都是模型没建对，或者统计口径不一致。

5.1 一个最隐蔽的坑：LAT符号方向

LAT里存偏差时，有人存的是“等于0的次数减一半”，有人存的是“等于1的次数减一半”，两者只差一个负号。后续统计时如果你用了错误的符号，最直接的表现是：理论上应该有正偏差的组合统计出来却接近0，或者相反。判断方法很简单：先拿单个S盒的已知明密文验证，确认统计量和偏差方向能对上，再做整体攻击。

我自己第一次做线性攻击时，正是因为符号没对齐，盯着统计结果看了半天，还以为算法有问题，最后逐条打印LAT才定位到是符号方向搞反了。

5.2 置换层方向也很容易写反

p_layer的写法有两种风格：一种是把输入的第i位移动到输出的第perm[i]位，另一种是把输出的第i位写成输入的第perm[i]位。方向写反会导致加密结果完全不同，但代码编译不报错，很难发现。我建议在perm函数设计时统一写成“输入位i → 输出位perm[i]”，并在打印测试向量时手动验证几个固定输入的输出，能省下大量调试时间。

5.3 样本全部用同一密钥的误区

做差分或线性实验时，所有样本必须使用同一个固定密钥，否则多层密钥加会破坏你想要的差分/线性关系。这个坑对新手很常见：为了追求“随机性”，在每对样本之间切换密钥，结果统计出来的概率被彻底平均掉，任何特征都会被淹没。正确做法是固定密钥，只让明文随机变化。

最后说点实操体会

把这套代码跑通之后，我对“密码分析”这四个字的敬畏感反而淡了一点。它没有想象中那么高不可攀，本质上就是“统计偏差”加上“密钥猜测”的组合拳。但我也因此更清楚，为什么现代分组密码的S盒设计要如此小心翼翼地控制DDT和LAT的最大值，因为任何一点统计上的漏洞，都可能被攻击者用心收集几百万条样本之后放大成完整的密钥恢复。

如果你也想自己动手试试，我建议先不要急着上真实密码，就把我上面这个迷你SPN玩熟：换S盒、改轮数、换置换层，观察这些改动对DDT和LAT的影响。最后分享一个小技巧：在打印DDT和LAT的时候，用类似printf("%3d", table[i][j])的固定宽度输出，比Excel看表格舒服得多；调试时再配合二进制打印函数，把每个字节的bit位拆出来对照着看，很多隐蔽错误一眼就能发现。

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