SP结构（Substitution-Permutation Network，替代-置换网络）与以其为蓝本设计的AES（Advanced Encryption Standard）算法，不仅是工业标准，更集中体现了可证明安全的设计思想
SP结构
SP结构是分组密码的一种基础设计框架，其核心思想是通过交替的替代层（S-box层）和置换层（P-layer），实现香农提出的混淆与扩散两大安全原则。
- 替代层（S盒层）：提供非线性变换，实现混淆。将输入的比特（或字节）通过一个固定的非线性查找表（S盒）进行映射，使得输入与输出之间的代数关系变得复杂，难以用线性方程逼近
- 置换层（扩散层）：提供线性变换，实现扩散。通过比特的重新排列或线性混合操作，将单个输入比特的影响快速扩散到多个输出比特，从而消除明文的统计特征
宽轨迹策略与可证明的安全性
AES的设计精髓在于宽轨迹策略。核心目标是通过系统的扩散层设计，确保在若干轮加密后，任意差分或线性路径中激活的S盒数量足够多，从而使攻击复杂度超过穷举攻击。
宽轨迹策略
确保在若干轮迭代后，任何有意义的差分或线性路径都会激活足够多数量的S盒。
扩散层设计：
- 行移位（ShiftRows）：实现行内字节扩散
- 列混合（MixColumns）：实现列内字节扩散，基于GF(2⁸)上的矩阵乘法
可证明的安全下界
通过严格的数学推导可以证明，在AES的4轮加密中，任何差分或线性特征路径激活的S盒数量不少于25个。结合AES的S盒已知的最佳特性（最大差分概率为2⁻⁶，最大线性逼近优势为2⁻³），我们可以计算出：
- 4轮差分概率上界 ≤ \((2^{-6})^{25} = 2^{-150}\)
- 4轮线性优势上界 ≤ \((2^{-3})^{25} · 2 ≈ 2^{-73}\)（考虑线性掩码组合）
穷举搜索复杂度（2¹²⁸），理论上保证了足够的安全冗余。
3. 实现方式
单轮结构：
字节替代(S盒) → 行移位 → 列混合 → 轮密钥加↓ ↓ ↓ ↓非线性混淆 行内扩散 列内扩散 密钥混合
4轮扩散示例：
输入差分 → 激活1个S盒 → 行移位扩散到4列 → 列混合激活全列4个S盒
→ 下一轮至少激活16个S盒 → 依此类推，4轮后至少25个活动S盒
差分分析（Differential Cryptanalysis）
1. 基本原理
- 核心思想：研究输入差异（ΔX） 导致输出差异（ΔY） 的概率分布
- 差分路径：一系列中间状态的差异传播路径
- 差分概率：特定输入差异产生特定输出差异的概率
2. 对AES的分析
- S盒差分特性：
- AES的S盒最大差分概率为2⁻⁶
- 平均每个S盒的差分概率约2⁻⁷
- 宽轨迹防御：
- 4轮最小25个活动S盒 → 差分概率 ≤ \(2^{-150}\)
- 远低于穷举攻击门槛（\(2^{-128}\) for AES-128）
- 实际攻击进展：
- 7轮AES-128：差分攻击需要2¹²⁶.¹选择明文
- 8轮AES-256：需要2²⁴⁴.⁶选择明文
- 全轮AES：目前没有可行差分攻击
3. 差分路径示例
一轮差分传播：
ΔX = (a,0,0,0) // 仅第一字节有差异
→ 字节替代：ΔS = (S(a),0,0,0)
→ 行移位：ΔS' = (S(a),0,0,0) // 第一行不移位
→ 列混合：ΔY = M·ΔS' = (M₀₀·S(a), M₁₀·S(a), M₂₀·S(a), M₃₀·S(a))
→ 全列4个字节被激活
不可能差分分析（Impossible Differential Cryptanalysis）
1. 基本思想
- 核心悖论：寻找概率为0的差分路径（不可能发生的差分传播）
- 攻击逻辑：利用某些输入差分→输出差分绝对不可能发生的特性，排除错误密钥
- 与传统差分对比：
- 传统差分：利用高概率路径
- 不可能差分：利用零概率路径（排除法）
2. 攻击步骤
1. 寻找不可能差分区分器（r₁轮）
2. 在区分器前后增加若干轮（r₂+r₃轮）
3. 对每个候选密钥：- 加密前向r₂轮，解密密文后向r₃轮- 检查中间状态是否满足不可能差分- 若满足⇒该密钥错误（排除）
4. 剩余密钥即为正确密钥
3. AES中的不可能差分
- 4轮不可能差分区分器：
- 数学原理：
- 单字节差分 → 列混合激活全列4字节
- 经过4轮扩散，输出不可能全零
- 具体路径：1→4→16→25个活动S盒，输出必非零
宽轨迹防御机制：
- 扩散层使不可能差分路径长度受限（≤4轮）
- 增加前后攻击轮数时，密钥猜测复杂度指数增长
- 全轮AES（10/12/14轮）不可能差分攻击不可行
积分攻击（Integral Cryptanalysis）
1. 基本思想
- 核心概念：研究明文集合经过加密后的统计特性
- 原名：Square攻击（针对Square算法，AES前身）
- 核心特性：某些字节取所有值（Active），其他字节固定（Passive）
2. 基本概念
明文结构（以4字节为例）：
A A A A ← Active（遍历所有值）
P P P P ← Passive（固定值）
C C C C ← Constant（常数）
B B B B ← Balanced（异或和为0）
3. AES中的积分区分器
- 3轮积分区分器：
输入：2^{8}个明文，其中一字节Active，其余15字节Constant
加密3轮后：
所有16字节 → Balanced（每字节异或和=0）
概率：1
- 4轮积分区分器：
输入：2^{32}个明文，其中一列（4字节）Active
加密4轮后：
无法保证Balanced，但呈现部分规律
可构造5轮攻击
4. 攻击步骤示例（5轮AES攻击）
1. 选择2^{32}个明文，第一列Active，其余列Constant
2. 加密5轮获取密文
3. 猜测第5轮轮密钥的4字节
4. 对每个密钥猜测：- 解密密文最后一轮- 检查第4轮输出是否满足Balanced特性- 不满足⇒排除该密钥
5. 重复攻击其他字节