Substitution-box (S-box) 详解

在现代对称密钥密码算法，特别是分组密码 (Block Ciphers) 中，Substitution-box (S-box) 是一个至关重要的组件。S-box 的引入是为了提供算法的非线性性 (Non-linearity)，这是确保密码安全性的核心要素之一。如果一个密码算法是线性的，攻击者可以利用线性代数方法轻松破解它。S-box 通过将输入位模式映射到不同的输出位模式，使得整个加密过程变得高度复杂和混沌，从而抵抗各种密码分析攻击。

核心思想：S-box 的核心作用是在分组密码中引入非线性变换，将输入位序列替换为与输入不呈线性关系的输出位序列，从而增强密码的混淆性 (confusion) 和扩散性 (diffusion)，抵抗线性密码分析和差分密码分析等攻击。

一、什么是 S-box？

1.1 定义

Substitution-box (S-box)，也称为替换盒，是一个查找表 (lookup table)，它接受一个固定长度的输入位序列（通常是若干位），并生成一个不同或相同长度的输出位序列。S-box 的设计目的是实现非线性变换：它不是一个简单的位移、异或 (XOR) 或加法运算，而是通过预定义的映射表，将每个可能的输入模式唯一地映射到一个输出模式。

1.2 类型

S-box 通常有两种类型：

定长 S-box (Fixed S-box)：输入和输出的位数相同 (例如，一个 $n \times n$ 的 S-box 将 $n$ 位输入映射到 $n$ 位输出)。例如，AES (Advanced Encryption Standard) 使用的是 $8 \times 8$ 的 S-box。
变长 S-box (Variable S-box)：输入和输出的位数不同 (例如，一个 $n \times m$ 的 S-box 将 $n$ 位输入映射到 $m$ 位输出，其中 $n \neq m$)。DES (Data Encryption Standard) 使用的就是 $6 \times 4$ 的 S-box。

1.3 示例：一个 $4 \times 4$ S-box

考虑一个将 4 位输入映射到 4 位输出的 S-box。其通常以表格形式表示，输入是行号和/或列号，表格内容是对应的输出值。

例如，这是一个简化的 $4 \times 4$ S-box 表示：

Input ($x_3 x_2 x_1 x_0$)	Output ($y_3 y_2 y_1 y_0$)	16进制输入	16进制输出
0000	1110	0	E
0001	0100	1	4
0010	1101	2	D
0011	0001	3	1
0100	0010	4	2
0101	1111	5	F
0110	1011	6	B
0111	1000	7	8
1000	0011	8	3
1001	1010	9	A
1010	0110	A	6
1011	1100	B	C
1100	0101	C	5
1101	1001	D	9
1110	0000	E	0
1111	0111	F	7

如果输入是 0110 (二进制)，查找表可知其输出为 1011 (二进制)。

1.4 S-box 在分组密码中的位置

在分组密码（如 Feistel 网络或 SPN (Substitution-Permutation Network) 结构）中，S-box 通常用于每一轮的固定位置，对子块进行替换操作。

SPN 结构中的 S-box 示例：

    graph TD
    A[明文块] --> B{"SubBytes (S-boxes)"};
    B --> C{ShiftRows};
    C --> D{MixColumns};
    D --> E{AddRoundKey};
    E --> B; 
    %% 多轮循环

    subgraph "SubBytes (S-boxes 内部)"
        S1[输入块1] --> S_BOX_1(S-box 1);
        S2[输入块2] --> S_BOX_2(S-box 2);
        S3[输入块3] --> S_BOX_3(S-box 3);
        S4[输入块4] --> S_BOX_4(S-box 4);
        S_BOX_1 --> O1[输出块1];
        S_BOX_2 --> O2[输出块2];
        S_BOX_3 --> O3[输出块3];
        S_BOX_4 --> O4[输出块4];
    end

在 AES 算法中，SubBytes 步骤就广泛使用了 S-box。每个字节作为一个 8 位输入进入 $8 \times 8$ 的 S-box, 并输出一个 8 位结果。

二、S-box 的核心作用：非线性性

2.1 非线性变换的必要性

线性变换的弱点：如果一个密码算法只包含线性操作（如异或、位移、矩阵乘法），那么加密过程可以表示为一个线性方程组。攻击者可以收集足够多的明文/密文对，建立这些方程组并解出密钥，从而破解密码。
非线性 S-box 的作用：S-box 的映射关系是非线性的。这意味着即使输入只改变了一个位 (bit)，输出的多个位也可能发生变化，而且这种变化没有简单的数学线性关系。这使得攻击者难以通过分析输入输出之间的位模式变化来推断密钥或逆向还原加密过程。

2.2 混淆性 (Confusion)

定义：混淆性是指密文与密钥之间的关系变得复杂且模糊，使得攻击者难以从密文中推断出密钥。
S-box 的贡献：S-box 正是提供混淆性的主要机制。它的非线性映射使得密钥的每一个位对密文的多个位产生影响，反之亦然，从而模糊了密钥与密文之间的统计关系。

2.3 扩散性 (Diffusion)

定义：扩散性是指明文的每一个位对密文的许多位产生影响，以及密文的每一个位也受到明文的许多位的影响。理想情况下，明文的一个微小改变（例如改变一位）会导致密文的巨大改变。
S-box 的贡献：虽然 S-box 自身主要提供混淆性，但当 S-box 与置换层 (Permutation Layer) 结合使用时，它能有效地实现扩散性。置换层将 S-box 的输出位重新排列，使得 S-box 的一个输出位在下一轮输入时能影响不同的 S-box，从而迅速将输入明文的微小变化扩散到整个密文中。

三、S-box 的设计准则和密码学属性

一个好的 S-box 必须满足一系列严格的密码学属性，以有效抵抗已知的密码分析攻击。

3.1 抵抗线性密码分析 (Linear Cryptanalysis)

线性密码分析：通过寻找明文、密文和密钥之间的高概率线性关系来攻击密码。
S-box 属性：一个好的 S-box 需要具有低线性近似表 (Low Linear Approximation Table)。这意味着 S-box 的输入位和输出位之间，能够被近似为线性关系的概率应该尽可能地接近 $0.5$ (随机猜测的概率)，即不能存在高概率的线性偏差。

3.2 抵抗差分密码分析 (Differential Cryptanalysis)

差分密码分析：通过分析输入明文对的差分（异或值）与相应密文对的差分之间的统计关系来攻击密码。
S-box 属性：一个好的 S-box 需要具有低差分均匀性 (Low Differential Uniformity)，最好是完美非线性 (Perfectly Nonlinear) 或几乎完美非线性 (Almost Perfectly Nonlinear, APN)。这意味着对于任何非零输入差分 $\Delta x$，输出差分 $\Delta y = S(x) \oplus S(x \oplus \Delta x)$ 的可能值分布应该尽可能均匀，并且每个输出差分 $\Delta y$ 最多只出现两次（APN 属性）。

$$
\forall \Delta x \neq 0, \forall \Delta y, |{x \mid S(x) \oplus S(x \oplus \Delta x) = \Delta y}| \leq 2
$$

3.3 雪崩效应 (Avalanche Effect)

定义：雪崩效应是指明文或密钥的微小改变（例如改变一位）应导致密文的显著且不可预测的巨大改变（例如改变一半的位）。
S-box 的贡献：S-box 的非线性特性，与置换层结合，能够迅速传播微小的输入变化，从而实现强大的雪崩效应。一个好的 S-box 应该保证当输入改变一位时，输出有尽可能多的位改变。

3.4 严格雪崩准则 (Strict Avalanche Criterion, SAC)

定义：SAC 是雪崩效应的一个更严格的版本。它要求如果输入的一个位被反转，输出的每个位都应该以 $0.5$ 的概率被反转。
S-box 的贡献：好的 S-box 设计需要满足 SAC 或其他类似属性，以确保其输出对输入变化的充分混淆。

3.5 双射性 (Bijectivity)

对于 $n \times n$ 的 S-box (输入和输出位数相同)，它通常要求是双射 (bijective)，即每个输入都有唯一的输出，并且每个输出也由唯一的输入产生。这在 SPN 结构中是重要的，因为它保证了变换是可逆的，从而可以进行解密。
DES 的 S-box 是一个例外，它是 $6 \times 4$ 的，因此不是双射的。

四、S-box 的数学构造

设计一个具有良好密码学属性的 S-box 是一项复杂的数学任务。常用的构造方法包括：

基于有限域运算：这是 AES S-box 的构造方式。它定义在一个有限域（伽罗瓦域）$GF(2^8)$ 上：
- 首先对输入字节执行求逆运算 $y = x^{-1}$ （如果 $x=0$，则 $y=0$）。
- 然后对结果 $y$ 应用一个仿射变换（即一个矩阵乘法和异或一个常数向量的组合）。
AES 的 S-box 通过这种方式在数学上被证明具有很好的密码学属性。
基于布尔函数：将 S-box 视为一组布尔函数的集合，然后优化这些布尔函数的非线性性、差分均匀性等属性。
随机生成与测试：对于较小的 S-box，可以随机生成并测试其密码学属性，直到找到一个满足要求的。然而，随着 S-box 规模的增加，这种方法变得不切实际。
混沌映射：利用一些混沌系统生成 S-box。

五、S-box 的逆运算

在分组密码解密时，加密过程中使用的 S-box 操作也需要逆转。对于双射的 $n \times n$ S-box，其逆运算就是查找其逆 S-box (Inverse S-box)。逆 S-box 的表是原 S-box 的翻转：如果原 S-box 将输入 $x$ 映射到输出 $y$，那么逆 S-box 将输入 $y$ 映射回输出 $x$。

例如，AES 包含一个 InvSubBytes 步骤，它使用一个与 SubBytes 对应的逆 S-box 来完成解密。