企业官网建设流程全解析

简介：这份资源面向密码学与信息安全方向的初学者，围绕Howard M. Heys教授发表于Cryptologia的经典教程《A Tutorial on Linear and Differential Cryptanalysis》展开，借助一个仅5轮、16比特的玩具密码，把差分分析与线性分析的原理讲得深入浅出。压缩包共6个文件，约662KB，包含教程PDF原文、线性分析与差分分析的C++源码各一份，以及对应的可执行程序和一个说明文本，方便读者边读论文边动手复现算法，直观体会两种经典攻击方法的推导与实现过程。目前已有553人学习下载。对于从《分组密码的攻击方法与实例分析》等教材入门、希望把抽象理论落到代码上的读者，这份资料能提供一条从论文阅读到程序验证的完整路径，是理解分组密码分析思想的实用起点。

1. 从一次被密码学作业卡住的深夜说起

有个做安全方向的朋友跟我吐槽，说他第一次接触差分分析和线性分析时，对着教材上那堆概率公式看了整整三个晚上，愣是没搞明白 S 盒的差分分布表到底怎么算出来的。教材讲原理讲得很漂亮，但一到“动手实现”就只剩几行伪代码，连个能编译的完整例子都没有。这份资源就是冲着这个痛点来的——它把差分分析和线性分析这两大分组密码分析方法的入门原理，配上可以直接编译运行的 C++ 实现，从 S 盒的差分分布表构建，到多轮特征搜索，再到线性逼近的偏差计算，一条链路走通。适合正在学密码学课程、准备 CTF 密码方向、或者做安全协议分析需要补这块基础的开发者。不是那种只讲概念的科普文，而是能让你把代码跑起来、把中间结果打印出来、亲眼看到差分概率怎么随轮数衰减的实操材料。

2. 差分分析核心模块拆解：从 S 盒到多轮特征

2.1 差分分析到底在算什么

差分分析的核心思想其实一句话能说清：找到一条高概率的输入差分到输出差分的传播路径，利用这条路径把密钥猜测问题转化成统计偏差问题。但落到代码上，第一步就得把 S 盒的差分分布表（DDT，Difference Distribution Table）算出来。DDT 是一个 2^n × 2^n 的矩阵，其中 n 是 S 盒的输入比特数。矩阵中第 (i, j) 个元素表示：当输入差分为 i 时，输出差分为 j 的输入对数量。

这个表是整个差分分析的地基。没有它，后面所有的特征搜索都是空中楼阁。我见过不少人直接跳过 DDT 去抄现成的差分特征，结果换一个 S 盒就完全不知道怎么改了。所以这份资源里，DDT 的构建是第一个要啃下来的模块。

2.2 S 盒差分分布表的 C++ 实现

先看核心代码。这里假设 S 盒是 4 比特输入输出（比如 PRESENT 的 S 盒），实际项目中可能是 8 比特（AES），但逻辑完全一样。

#include <vector> #include <cstdint> #include <iostream> #include <iomanip> // 4-bit S-box example (PRESENT-like) const uint8_t SBOX[16] = { 0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2 }; // Build Difference Distribution Table // ddt[input_diff][output_diff] = count of pairs std::vector<std::vector<int>> buildDDT(const uint8_t* sbox, int size) { std::vector<std::vector<int>> ddt(size, std::vector<int>(size, 0)); for (int inDiff = 0; inDiff < size; ++inDiff) { for (int x = 0; x < size; ++x) { int y1 = sbox[x]; int y2 = sbox[x ^ inDiff]; int outDiff = y1 ^ y2; ddt[inDiff][outDiff]++; } } return ddt; } void printDDT(const std::vector<std::vector<int>>& ddt) { int size = ddt.size(); std::cout << " "; for (int j = 0; j < size; ++j) std::cout << std::hex << std::setw(3) << j; std::cout << "\n"; for (int i = 0; i < size; ++i) { std::cout << std::hex << std::setw(3) << i << ": "; for (int j = 0; j < size; ++j) std::cout << std::dec << std::setw(3) << ddt[i][j]; std::cout << "\n"; } } int main() { auto ddt = buildDDT(SBOX, 16); printDDT(ddt); return 0; }

这段代码的逻辑很直白：外层循环遍历所有可能的输入差分inDiff，内层循环遍历所有可能的明文输入x，计算x和x ^ inDiff经过 S 盒后的输出差分，然后在 DDT 对应位置加一。注意x ^ inDiff这个操作——它保证了两个输入之间的差分恰好是inDiff。

参数说明：sbox是 S 盒数组，size是 S 盒的大小（4 比特就是 16）。返回的ddt是一个二维向量，行索引是输入差分，列索引是输出差分。打印函数用十六进制显示索引，十进制显示计数值，方便对照。

跑出来之后你会看到，第一行（输入差分为 0）只有ddt[0][0]等于 16，其余全是 0——这是必然的，输入相同输出必然相同。其他行里，每个非零输入差分对应的输出差分分布是不均匀的，有些格子数值明显偏高，这些高值格子就是差分特征搜索的起点。

2.3 多轮差分特征搜索

有了 DDT，下一步就是找多轮特征。对于 SPN 结构的分组密码，一轮通常包括：轮密钥加、S 盒替换、线性层（P 盒或矩阵乘法）。差分特征搜索要做的就是：给定第一轮的输入差分，通过 DDT 找到概率最高的输出差分，再经过线性层传播，作为下一轮的输入差分，如此迭代。

// Simple linear layer: bit permutation for 16-bit block // pLayer[i] = destination bit index for source bit i const int PLAYER[16] = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 }; // Apply linear layer to a difference value uint16_t applyLinearLayer(uint16_t diff) { uint16_t result = 0; for (int i = 0; i < 16; ++i) { if (diff & (1 << i)) { result |= (1 << PLAYER[i]); } } return result; } // Find best differential characteristic for given rounds struct DifferentialStep { uint16_t inputDiff; uint16_t outputDiff; int probability; // count out of 16 }; std::vector<DifferentialStep> findCharacteristic( const std::vector<std::vector<int>>& ddt, uint16_t startDiff, int rounds) { std::vector<DifferentialStep> characteristic; uint16_t currentDiff = startDiff; for (int r = 0; r < rounds; ++r) { // Split 16-bit diff into four 4-bit nibbles uint16_t sboxOutDiff = 0; int totalProb = 1; for (int nib = 0; nib < 4; ++nib) { int inNibble = (currentDiff >> (nib * 4)) & 0xF; // Find best output diff for this nibble int bestOut = 0, bestCount = 0; for (int out = 0; out < 16; ++out) { if (ddt[inNibble][out] > bestCount) { bestCount = ddt[inNibble][out]; bestOut = out; } } sboxOutDiff |= (bestOut << (nib * 4)); totalProb *= bestCount; } // Apply linear layer uint16_t nextDiff = applyLinearLayer(sboxOutDiff); characteristic.push_back({currentDiff, sboxOutDiff, totalProb}); currentDiff = nextDiff; } return characteristic; }

这段代码做了三件事：把 16 比特差分拆成四个 4 比特 nibble，每个 nibble 独立查 DDT 找最优输出差分，然后把四个 nibble 的结果拼回去，再经过线性层传播到下一轮。totalProb是这一轮所有 nibble 概率的乘积，单位是“每 16 个输入对中有多少个满足”。

参数说明：ddt是前面构建的差分分布表，startDiff是起始输入差分，rounds是要搜索的轮数。返回的characteristic是一个向量，每一步记录了该轮的输入差分、S 盒输出差分和概率计数。

这里有个容易翻车的地方：每个 nibble 独立选最优输出差分，并不保证全局最优。因为线性层会把不同 nibble 的比特混在一起，下一轮的输入差分可能因此变得很差。真正严谨的做法要用分支定界或者 MILP 来搜索全局最优特征。但作为入门实现，这种贪心策略足够让你理解整个流程，而且跑起来快，适合反复实验。

2.4 概率衰减与轮数关系

把上面几个模块串起来跑一下，打印每一轮的概率，你会看到一个很直观的现象：随着轮数增加，特征概率指数级衰减。比如 4 比特 S 盒单轮最优概率可能是 6/16，两轮变成 36/256，三轮回落到 216/4096 左右。这个衰减速度直接决定了差分分析能覆盖多少轮——概率太低的话，需要的明文对数量会大到不现实。

我一般会在这个模块加一个简单的输出，把每轮概率用分数和浮点数都打出来，方便观察趋势。这个数据也是后面判断“这条特征能不能用”的依据。

3. 线性分析模块：从掩码到偏差计算

3.1 线性逼近的基本构造

线性分析走的是另一条路：找输入比特和输出比特之间的线性关系，使得这个关系成立的概率偏离 1/2 尽可能大。偏离量叫偏差（bias），偏差越大，攻击越有效。和差分分析一样，第一步是构建线性逼近表（LAT，Linear Approximation Table）。

LAT 的维度也是 2^n × 2^n，其中 n 是 S 盒输入比特数。第 (a, b) 个元素表示：输入掩码为 a、输出掩码为 b 时，满足线性关系a·x = b·S(x)的输入 x 的数量减去 2^(n-1)。这个值就是偏差的 2 倍。

3.2 线性逼近表的 C++ 实现

// Build Linear Approximation Table // lat[inputMask][outputMask] = count - size/2 std::vector<std::vector<int>> buildLAT(const uint8_t* sbox, int size) { std::vector<std::vector<int>> lat(size, std::vector<int>(size, 0)); int half = size / 2; for (int inMask = 0; inMask < size; ++inMask) { for (int outMask = 0; outMask < size; ++outMask) { int count = 0; for (int x = 0; x < size; ++x) { int y = sbox[x]; // Compute parity of (inMask & x) XOR (outMask & y) int parity = __builtin_parity(inMask & x) ^ __builtin_parity(outMask & y); if (parity == 0) count++; } lat[inMask][outMask] = count - half; } } return lat; }

逻辑说明：对每一对掩码(inMask, outMask)，遍历所有可能的输入x，计算inMask & x的奇偶性和outMask & sbox[x]的奇偶性，如果两者相等（异或为 0），计数器加一。最后减去size/2得到偏差的 2 倍。

参数说明：__builtin_parity是 GCC 内置函数，返回整数二进制表示中 1 的个数的奇偶性。如果编译器不支持，可以自己写一个循环来算。lat矩阵中绝对值大的元素就是好的线性逼近。

跑出来之后，第一行第一列（输入掩码 0，输出掩码 0）的值是size/2，因为恒等式永远成立。其他格子中，绝对值越大说明线性关系越强。比如某个格子的值是 6，意味着偏差是 3/16，比随机猜测好不少。

3.3 多轮线性特征的拼接

和差分特征类似，多轮线性特征需要把单轮的线性逼近串起来。这里的关键是“掩码传播”：上一轮的输出掩码经过线性层的逆变换后，成为下一轮的输入掩码。对于 SPN 结构，线性层通常是比特置换，逆变换就是反向置换。

// Find best linear characteristic struct LinearStep { int inputMask; int outputMask; int bias; // lat value }; std::vector<LinearStep> findLinearCharacteristic( const std::vector<std::vector<int>>& lat, int startMask, int rounds) { std::vector<LinearStep> characteristic; int currentMask = startMask; for (int r = 0; r < rounds; ++r) { int sboxOutMask = 0; int totalBias = 1; for (int nib = 0; nib < 4; ++nib) { int inNibble = (currentMask >> (nib * 4)) & 0xF; int bestOut = 0, bestBias = 0; for (int out = 0; out < 16; ++out) { if (std::abs(lat[inNibble][out]) > std::abs(bestBias)) { bestBias = lat[inNibble][out]; bestOut = out; } } sboxOutMask |= (bestOut << (nib * 4)); totalBias *= bestBias; } // Inverse linear layer for mask propagation int nextMask = applyLinearLayer(sboxOutMask); characteristic.push_back({currentMask, sboxOutMask, totalBias}); currentMask = nextMask; } return characteristic; }

这段代码和差分特征搜索结构几乎一样，区别在于：查的是 LAT 而不是 DDT，选的是绝对值最大的偏差而不是计数最大的输出差分，掩码传播用的是线性层的逆变换（对于比特置换，逆变换就是反向映射）。

参数说明：lat是线性逼近表，startMask是起始输入掩码，rounds是轮数。返回的characteristic记录了每轮的输入掩码、输出掩码和偏差乘积。

这里有个血泪经验：线性特征的偏差乘积会随着轮数增加迅速趋近于零，但符号会交替变化。如果你在拼接时忽略了符号，最后得到的偏差可能被错误地放大或抵消。所以totalBias一定要用有符号整数，并且在每一步都保留符号信息。

3.4 用已知明文验证线性逼近

代码写完了，怎么验证它是对的？最直接的办法是拿一组已知明文-密文对，手动计算线性逼近两边的奇偶性，统计满足等式的比例。如果比例接近1/2 + bias/2，说明你的 LAT 和特征搜索是对的。

// Verify linear approximation with known plaintext-ciphertext pairs double verifyLinearApprox( const std::vector<std::pair<uint16_t, uint16_t>>& pairs, int inMask, int outMask) { int count = 0; for (auto& [pt, ct] : pairs) { int parity = __builtin_parity(inMask & pt) ^ __builtin_parity(outMask & ct); if (parity == 0) count++; } return (double)count / pairs.size(); }

这个函数返回的是线性关系成立的实际频率。如果你用完整的加密函数生成大量明文-密文对，然后传入正确的输入输出掩码，得到的频率应该接近理论值。如果差很远，要么是掩码传播算错了，要么是加密函数的线性层实现和特征搜索用的不一致。

4. 避坑与常见问题排查

4.1 DDT 第一行全是零，是不是代码写错了

现象：打印 DDT 时发现第一行除了ddt[0][0]等于 S 盒大小，其余全是 0。

原因：这是正确的。输入差分为 0 意味着两个输入完全相同，经过 S 盒后输出也完全相同，输出差分必然为 0。所以ddt[0][0]等于 S 盒大小，其他位置为 0。

解决：不用改，这是预期行为。如果你看到第一行有其他非零值，那才是真的写错了——大概率是x ^ inDiff写成了x + inDiff或者循环边界搞错了。

4.2 多轮特征概率算出来是整数，但实际攻击效果很差

现象：特征搜索给出的概率看起来还不错，但拿去做密钥恢复时统计偏差不明显。

原因：贪心搜索找到的是每轮局部最优，不是全局最优。而且实际攻击中，你用的是“特征”而不是“差分”，特征概率是整条路径的概率乘积，但实际差分传播可能走其他路径，导致观测到的概率和理论值有偏差。

解决：用分支定界或 MILP 工具（比如 Gurobi、CP-SAT）做全局搜索。如果只是学习用，可以在每轮多保留几个候选输出差分，做一个小规模的广度优先搜索，看看有没有概率更高的组合。

4.3 LAT 的偏差值出现负数，怎么处理

现象：打印 LAT 时看到很多负数，不知道该怎么选。

原因：LAT 中的值表示的是“满足线性关系的输入数量减去一半”，这个差值可以是负的。负值意味着线性关系成立的概率小于 1/2，但偏差的绝对值一样有意义。

解决：选特征时看绝对值，不要只看正数。但在拼接多轮特征时，符号必须保留，因为正负偏差在乘积时会相互影响。我一般会在结构体里存有符号整数，最后算总偏差时再取绝对值判断强度。

4.4 线性层实现和特征搜索不一致导致验证失败

现象：用已知明文验证线性逼近时，实际频率和理论值差很远。

原因：特征搜索里用的线性层和加密函数里用的线性层不是同一个实现，或者比特序搞反了。

解决：把线性层的输入输出打印出来，用几个简单的测试向量手动验证。比如输入只有第 0 位是 1，看看输出是不是PLAYER[0]对应的位置。确认无误后再跑特征搜索。这个坑我踩过不止一次，后来养成了习惯：任何线性层实现，先写三个测试用例跑通再往下走。

4.5 编译时__builtin_parity报错

现象：在 MSVC 或者某些嵌入式编译器上，__builtin_parity找不到。

原因：这是 GCC/Clang 的内置函数，不是标准 C++。

解决：自己写一个可移植的版本：

int parity(uint32_t x) { x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; return x & 1; }

这个函数返回 1 表示奇数个 1，返回 0 表示偶数个 1。逻辑和__builtin_parity一致，但可以在任何编译器上跑。

5. 二次开发与扩展：把这份代码变成你自己的分析工具

这份资源的代码结构很清晰，DDT、LAT、特征搜索、验证四个模块各自独立，改起来不费劲。如果你想把它扩展成一个更通用的分析工具，有几个方向可以走。

第一个方向是支持任意 S 盒和分组长度。现在的代码硬编码了 4 比特 S 盒和 16 比特分组，但实际密码可能是 8 比特 S 盒、64 比特甚至 128 比特分组。改造思路是把 S 盒大小和分组大小做成模板参数或者运行时配置，DDT 和 LAT 的维度动态分配。线性层也要从硬编码的PLAYER数组改成可配置的置换表或矩阵。

第二个方向是加入自动化特征搜索。现在的贪心搜索只能找局部最优，你可以接入 MILP 求解器，把差分和线性特征的搜索问题建模成整数规划问题。具体做法是：为每个 S 盒的输入输出差分定义 0-1 变量，用 DDT 中的可行转移作为约束，目标函数最大化整条路径的概率。这样能找到全局最优特征，而且可以处理多轮、多分支的复杂结构。

第三个方向是加一个简单的攻击验证模块。用特征搜索的结果，生成大量明文-密文对，然后实现密钥恢复的统计测试。比如对于差分分析，你可以对最后一轮的候选密钥进行部分解密，统计每个候选密钥对应的差分概率，概率最高的那个就是正确密钥。这个模块能让你直观感受到“特征概率”和“实际攻击成功率”之间的关系。

下面是一个简单的密钥恢复验证框架，展示改造思路：

// Simple key recovery using differential characteristic // Assume last round key is 4 bits (one nibble) int recoverLastRoundKey( const std::vector<std::pair<uint16_t, uint16_t>>& pairs, uint16_t inputDiff, uint16_t expectedOutputDiff, const uint8_t* invSbox) { int bestKey = -1; int bestCount = 0; for (int guessKey = 0; guessKey < 16; ++guessKey) { int count = 0; for (auto& [pt, ct] : pairs) { // Partial decrypt last round for one nibble int ctNibble = (ct >> 0) & 0xF; int decrypted = invSbox[ctNibble ^ guessKey]; // Check if the differential holds // (simplified: compare with expected output diff) if ((decrypted ^ (decrypted ^ (expectedOutputDiff & 0xF))) == (expectedOutputDiff & 0xF)) { count++; } } if (count > bestCount) { bestCount = count; bestKey = guessKey; } } return bestKey; }

这段代码只是一个骨架，实际使用时需要根据具体的密码结构补全部分解密逻辑。但思路是通用的：遍历候选密钥，对每个密钥统计满足差分特征的明文对数量，数量最多的就是正确密钥。

我自己的习惯是，每次改完特征搜索模块，都会先用一个已知的测试向量跑一遍完整流程——从 DDT 构建到特征搜索再到验证——确认输出和预期一致，再往下做更复杂的改造。这个习惯帮我省了很多调试时间，因为一旦某一步的输出不对，我能立刻定位到是哪个模块出了问题，而不是在一堆代码里大海捞针。希望这份资源和这些改造思路能帮你把差分分析和线性分析真正跑起来、用起来。

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