SHA-3 (Keccak) 海绵结构中的 $\\chi$ (Chi) 步骤详解
字数 3936 2025-12-16 00:14:49

SHA-3 (Keccak) 海绵结构中的 \(\\chi\) (Chi) 步骤详解

您好，我将为您详细讲解 SHA-3（Keccak）算法中核心的置换函数 Keccak-f 的一个非线性步骤——\(\\chi\) (Chi) 步骤。这个步骤是 Keccak 非线性特性的主要来源，对算法的安全性至关重要。

1. 题目背景与定位

SHA-3 是美国国家标准与技术研究院（NIST）在 2015 年发布的标准哈希算法，其核心是 Keccak 海绵结构。海绵结构内部有一个“置换函数”（Permutation Function），用于对内部状态进行混淆和扩散。最常用的 Keccak-f[1600] 函数，其内部状态是一个 5×5×64 的三维比特数组（共 1600 比特）。

Keccak-f 函数由多轮迭代组成，每轮包含 5 个步骤，记为 \(\\theta\), \(\\rho\), \(\\pi\), \(\\chi\), \(\\iota\)。我们今天聚焦 \(\\chi\) 步骤。它本质上是一个按位的非线性变换，作用于状态的每一行，是 Keccak 算法中唯一的非线性操作，为整个算法提供了抵抗线性密码分析和差分密码分析的关键安全性。

2. 状态表示与行、列的约定

理解 \(\\chi\) 之前，必须明确 Keccak 的状态表示。状态可以看作一个 5×5 的“面”（sheet），每个“单元”（cell）是一个 64 比特的“道”（lane），但 \(\\chi\) 步骤是按比特、逐行独立操作的。为了描述方便，我们通常将状态看作 5×5×w 的比特立方体（对于 Keccak-f[1600]，w=64）。我们用坐标 (x, y, z) 表示一个比特，其中：

  • \(x\) (0-4): 列索引
  • \(y\) (0-4): 行索引
  • \(z\) (0-63): 比特在“道”中的深度索引

在 \(\\chi\) 步骤中，操作单位是“行”，即固定 \(y\) 和 \(z\) 坐标，遍历 \(x\) 从 0 到 4 的 5 个比特。每个这样的 5 比特“行切片”独立地进行相同的非线性变换。

3. \(\\chi\) 步骤的数学定义

\(\\chi\) 步骤对状态中的每一个比特 \(a[x][y][z]\) 进行变换。其操作是逐行进行的，也就是说，对于每一对固定的 \((y, z)\) 值，我们取出该行的 5 个比特（x=0,1,2,3,4），然后按照一个固定的 5 比特输入/输出映射（即一个 5 位的 S 盒）进行变换。

其变换公式为：

\[a'[x][y][z] = a[x][y][z] \\oplus ((\\neg a[x+1][y][z]) \\land a[x+2][y][z]) \]

其中：

  • \(a[x][y][z]\) 是变换前的比特值。
  • \(a'[x][y][z]\) 是变换后的比特值。
  • \(\\oplus\) 表示按位异或（XOR）操作。
  • \(\\neg\) 表示按位取反（NOT）操作。
  • \(\\land\) 表示按位与（AND）操作。
  • 索引 \(x+1\) 和 \(x+2\) 是在模 5 的意义下计算的。也就是说，当 \(x=3\) 时，\(x+1=4\)，\(x+2=0\)；当 \(x=4\) 时，\(x+1=0\)，\(x+2=1\)。这确保了操作始终在一行（5个比特）的“循环移位”意义上进行。

4. 逐步拆解变换过程

让我们用一个具体的例子来演示。假设对于某一行（y=2, z=10），变换前的 5 个比特是：
\(a[0][2][10] = 1\)
\(a[1][2][10] = 0\)
\(a[2][2][10] = 1\)
\(a[3][2][10] = 1\)
\(a[4][2][10] = 0\)

我们可以用数组 \(A = [a_0, a_1, a_2, a_3, a_4] = [1,0,1,1,0]\) 表示这一行。

现在我们计算每个新比特 \(a'_x\)：

  • 对于 \(x=0\): \(a'_0 = a_0 \\oplus ((\\neg a_1) \\land a_2)\)

    • \(a_0 = 1\)
    • \(a_1 = 0\)，\(\\neg a_1 = 1\)
    • \(a_2 = 1\)
    • \((\\neg a_1) \\land a_2 = 1 \\land 1 = 1\)
    • \(a'_0 = 1 \\oplus 1 = 0\)

  • 对于 \(x=1\): \(a'_1 = a_1 \\oplus ((\\neg a_2) \\land a_3)\)

    • \(a_1 = 0\)
    • \(a_2 = 1\)，\(\\neg a_2 = 0\)
    • \(a_3 = 1\)
    • \((\\neg a_2) \\land a_3 = 0 \\land 1 = 0\)
    • \(a'_1 = 0 \\oplus 0 = 0\)

  • 对于 \(x=2\): \(a'_2 = a_2 \\oplus ((\\neg a_3) \\land a_4)\)

    • \(a_2 = 1\)
    • \(a_3 = 1\)，\(\\neg a_3 = 0\)
    • \(a_4 = 0\)
    • \((\\neg a_3) \\land a_4 = 0 \\land 0 = 0\)
    • \(a'_2 = 1 \\oplus 0 = 1\)

  • 对于 \(x=3\): \(a'_3 = a_3 \\oplus ((\\neg a_4) \\land a_0)\)

    • \(a_3 = 1\)
    • \(a_4 = 0\)，\(\\neg a_4 = 1\)
    • \(a_0 = 1\)
    • \((\\neg a_4) \\land a_0 = 1 \\land 1 = 1\)
    • \(a'_3 = 1 \\oplus 1 = 0\)

  • 对于 \(x=4\): \(a'_4 = a_4 \\oplus ((\\neg a_0) \\land a_1)\)

    • \(a_4 = 0\)
    • \(a_0 = 1\)，\(\\neg a_0 = 0\)
    • \(a_1 = 0\)
    • \((\\neg a_0) \\land a_1 = 0 \\land 0 = 0\)
    • \(a'_4 = 0 \\oplus 0 = 0\)

所以，变换后的行 \(A‘ = [a’_0, a‘_1, a’_2, a‘_3, a’_4] = [0, 0, 1, 0, 0]\)。

这个过程会对每一对 (y, z) 值（共 5 * 64 = 320 行）独立地执行一遍。这就是 \(\chi\) 步骤的全部工作。

5. 从另一个视角理解：5 位 S 盒

我们可以预先计算这个变换所有可能的 32 种（2^5）输入输出对。实际上，\(\chi\) 就是一个固定的 5 位 S 盒。将行看作一个 5 位整数，其真值表如下（部分）：

  • 输入 00000 (0) -> 输出 00000 (0)
  • 输入 00001 (1) -> 输出 00101 (5)
  • 输入 00010 (2) -> 输出 01010 (10)
  • ...
  • 输入 11111 (31) -> 输出 11111 (31)

硬件实现时，可以直接用查找表实现这个 S 盒，但 Keccak 的设计者选择用上面那个简单的逻辑门组合来实现，因为它在硬件上非常高效（仅涉及异或、与、非门），且比特级并行性极高。

6. \(\\chi\) 步骤的设计目标与安全性作用

  1. 非线性：这是 \(\chi\) 的核心。公式中的 “(\(\\neg a[x+1]) \\land a[x+2]\)” 是一个“与非”结构，是密码学中一种基本的非线性组件。非线性是破坏输入与输出之间线性关系的关键，使算法能够抵抗线性密码分析。如果没有非线性步骤，整个置换将是一系列线性变换的组合，安全性会大大降低。

  2. 可逆性：\(\chi\) 变换是可逆的（即存在逆变换）。这是置换函数必须满足的性质，以确保海绵结构的吸收和挤压过程是可计算的。虽然它是一个复杂的非线性操作，但其逆运算可以通过求解一个小型方程组得到。

  3. 与其它步骤配合：单独看 \(\chi\)，它只在“行”的局部（5比特）内进行混淆。它的威力需要与另外四个步骤结合才能发挥：

    • \(\\theta\) (Theta)：在列上进行全局混合，引入扩散。
    • \(\\rho\) (Rho) 和 \(\\pi\) (Pi)：对“道”（lane）进行循环移位和位置置换，将行内的局部非线性效应扩散到状态的其它部分。
    • \(\\iota\) (Iota)：为每轮添加不同的轮常数，打破对称性。
    • 经过多轮迭代后，局部的非线性效应被充分扩散到整个 1600 比特的状态中，形成了极强的混淆效果。

  4. 硬件效率：与 AES 的 S 盒（基于有限域逆运算）相比，\(\chi\) 步骤的逻辑运算非常简单，使得 Keccak 算法在硬件（如 ASIC, FPGA）上实现面积小、功耗低、速度快，这也是其能在哈希算法竞赛中胜出的重要原因之一。

7. 总结

\(\\chi\) 步骤是 SHA-3 (Keccak) 算法安全性的基石。它通过一个精巧的、基于比特的逻辑运算（\(a‘ = a \\oplus (\\neg b \\land c)\)），为算法注入了必不可少的非线性特性。这个步骤设计简洁、可逆且在硬件实现上极其高效。它独立地作用于状态的每一“行切片”，并与 Keccak-f 的其他四个步骤（\(\\theta\), \(\\rho\), \(\\pi\), \(\\iota\)）紧密协作，经过多轮迭代后，最终实现了强大的密码学混淆与扩散，从而能够构造出安全的哈希函数。

SHA-3 (Keccak) 海绵结构中的 $\\chi$ (Chi) 步骤详解 您好，我将为您详细讲解 SHA-3（Keccak）算法中核心的置换函数 Keccak-f 的一个非线性步骤——$\\chi$ (Chi) 步骤。这个步骤是 Keccak 非线性特性的主要来源，对算法的安全性至关重要。 1. 题目背景与定位 SHA-3 是美国国家标准与技术研究院（NIST）在 2015 年发布的标准哈希算法，其核心是 Keccak 海绵结构 。海绵结构内部有一个“置换函数”（Permutation Function），用于对内部状态进行混淆和扩散。最常用的 Keccak-f[ 1600 ] 函数，其内部状态是一个 5×5×64 的三维比特数组（共 1600 比特）。 Keccak-f 函数由多轮迭代组成，每轮包含 5 个步骤，记为 $\\theta$, $\\rho$, $\\pi$, $\\chi$, $\\iota$。我们今天聚焦 $\\chi$ 步骤 。它本质上是一个 按位的非线性变换 ，作用于状态的每一行，是 Keccak 算法中 唯一的非线性操作 ，为整个算法提供了抵抗线性密码分析和差分密码分析的关键安全性。 2. 状态表示与行、列的约定 理解 $\\chi$ 之前，必须明确 Keccak 的状态表示。状态可以看作一个 5×5 的“面”（sheet），每个“单元”（cell）是一个 64 比特的“道”（lane），但 $\\chi$ 步骤是 按比特、逐行独立 操作的。为了描述方便，我们通常将状态看作 5×5×w 的比特立方体（对于 Keccak-f[ 1600 ]，w=64）。我们用坐标 (x, y, z) 表示一个比特，其中： $x$ (0-4): 列索引 $y$ (0-4): 行索引 $z$ (0-63): 比特在“道”中的深度索引 在 $\\chi$ 步骤中， 操作单位是“行” ，即固定 $y$ 和 $z$ 坐标，遍历 $x$ 从 0 到 4 的 5 个比特。每个这样的 5 比特“行切片”独立地进行相同的非线性变换。 3. $\\chi$ 步骤的数学定义 $\\chi$ 步骤对状态中的每一个比特 $a[ x][ y][ z]$ 进行变换。其操作是 逐行 进行的，也就是说，对于 每一对固定的 $(y, z)$ 值 ，我们取出该行的 5 个比特（x=0,1,2,3,4），然后按照一个固定的 5 比特输入/输出映射（即一个 5 位的 S 盒）进行变换。 其变换公式为： $$a'[ x][ y][ z] = a[ x][ y][ z] \\oplus ((\\neg a[ x+1][ y][ z]) \\land a[ x+2][ y][ z ])$$ 其中： $a[ x][ y][ z ]$ 是变换前的比特值。 $a'[ x][ y][ z ]$ 是变换后的比特值。 $\\oplus$ 表示按位异或（XOR）操作。 $\\neg$ 表示按位取反（NOT）操作。 $\\land$ 表示按位与（AND）操作。 索引 $x+1$ 和 $x+2$ 是在 模 5 的意义下计算的。也就是说，当 $x=3$ 时，$x+1=4$，$x+2=0$；当 $x=4$ 时，$x+1=0$，$x+2=1$。这确保了操作始终在一行（5个比特）的“循环移位”意义上进行。 4. 逐步拆解变换过程 让我们用一个具体的例子来演示。假设对于某一行（y=2, z=10），变换前的 5 个比特是： $a[ 0][ 2][ 10 ] = 1$ $a[ 1][ 2][ 10 ] = 0$ $a[ 2][ 2][ 10 ] = 1$ $a[ 3][ 2][ 10 ] = 1$ $a[ 4][ 2][ 10 ] = 0$ 我们可以用数组 $A = [ a_ 0, a_ 1, a_ 2, a_ 3, a_ 4] = [ 1,0,1,1,0 ]$ 表示这一行。 现在我们计算每个新比特 $a'_ x$： 对于 $x=0$ : $a'_ 0 = a_ 0 \\oplus ((\\neg a_ 1) \\land a_ 2)$ $a_ 0 = 1$ $a_ 1 = 0$，$\\neg a_ 1 = 1$ $a_ 2 = 1$ $(\\neg a_ 1) \\land a_ 2 = 1 \\land 1 = 1$ $a'_ 0 = 1 \\oplus 1 = 0$ 对于 $x=1$ : $a'_ 1 = a_ 1 \\oplus ((\\neg a_ 2) \\land a_ 3)$ $a_ 1 = 0$ $a_ 2 = 1$，$\\neg a_ 2 = 0$ $a_ 3 = 1$ $(\\neg a_ 2) \\land a_ 3 = 0 \\land 1 = 0$ $a'_ 1 = 0 \\oplus 0 = 0$ 对于 $x=2$ : $a'_ 2 = a_ 2 \\oplus ((\\neg a_ 3) \\land a_ 4)$ $a_ 2 = 1$ $a_ 3 = 1$，$\\neg a_ 3 = 0$ $a_ 4 = 0$ $(\\neg a_ 3) \\land a_ 4 = 0 \\land 0 = 0$ $a'_ 2 = 1 \\oplus 0 = 1$ 对于 $x=3$ : $a'_ 3 = a_ 3 \\oplus ((\\neg a_ 4) \\land a_ 0)$ $a_ 3 = 1$ $a_ 4 = 0$，$\\neg a_ 4 = 1$ $a_ 0 = 1$ $(\\neg a_ 4) \\land a_ 0 = 1 \\land 1 = 1$ $a'_ 3 = 1 \\oplus 1 = 0$ 对于 $x=4$ : $a'_ 4 = a_ 4 \\oplus ((\\neg a_ 0) \\land a_ 1)$ $a_ 4 = 0$ $a_ 0 = 1$，$\\neg a_ 0 = 0$ $a_ 1 = 0$ $(\\neg a_ 0) \\land a_ 1 = 0 \\land 0 = 0$ $a'_ 4 = 0 \\oplus 0 = 0$ 所以，变换后的行 $A‘ = [ a’_ 0, a‘_ 1, a’_ 2, a‘_ 3, a’_ 4] = [ 0, 0, 1, 0, 0 ]$。 这个过程会对每一对 (y, z) 值（共 5 * 64 = 320 行）独立地执行一遍。这就是 $\chi$ 步骤的全部工作。 5. 从另一个视角理解：5 位 S 盒 我们可以预先计算这个变换所有可能的 32 种（2^5）输入输出对。实际上，$\chi$ 就是一个固定的 5 位 S 盒。将行看作一个 5 位整数，其真值表如下（部分）： 输入 00000 (0) -> 输出 00000 (0) 输入 00001 (1) -> 输出 00101 (5) 输入 00010 (2) -> 输出 01010 (10) ... 输入 11111 (31) -> 输出 11111 (31) 硬件实现时，可以直接用查找表实现这个 S 盒，但 Keccak 的设计者选择用上面那个简单的逻辑门组合来实现，因为它在硬件上非常高效（仅涉及异或、与、非门），且比特级并行性极高。 6. $\\chi$ 步骤的设计目标与安全性作用 非线性 ：这是 $\chi$ 的核心。公式中的 “($\\neg a[ x+1]) \\land a[ x+2]$” 是一个“与非”结构，是密码学中一种基本的非线性组件。非线性是破坏输入与输出之间线性关系的关键，使算法能够抵抗 线性密码分析 。如果没有非线性步骤，整个置换将是一系列线性变换的组合，安全性会大大降低。 可逆性 ：$\chi$ 变换是 可逆的 （即存在逆变换）。这是置换函数必须满足的性质，以确保海绵结构的吸收和挤压过程是可计算的。虽然它是一个复杂的非线性操作，但其逆运算可以通过求解一个小型方程组得到。 与其它步骤配合 ：单独看 $\chi$，它只在“行”的局部（5比特）内进行混淆。它的威力需要与另外四个步骤结合才能发挥： $\\theta$ (Theta)：在列上进行全局混合，引入扩散。 $\\rho$ (Rho) 和 $\\pi$ (Pi)：对“道”（lane）进行循环移位和位置置换，将行内的局部非线性效应扩散到状态的其它部分。 $\\iota$ (Iota)：为每轮添加不同的轮常数，打破对称性。 经过多轮迭代后，局部的非线性效应被充分扩散到整个 1600 比特的状态中，形成了极强的混淆效果。 硬件效率 ：与 AES 的 S 盒（基于有限域逆运算）相比，$\chi$ 步骤的逻辑运算非常简单，使得 Keccak 算法在硬件（如 ASIC, FPGA）上实现面积小、功耗低、速度快，这也是其能在哈希算法竞赛中胜出的重要原因之一。 7. 总结 $\\chi$ 步骤是 SHA-3 (Keccak) 算法安全性的基石。它通过一个精巧的、基于比特的逻辑运算（$a‘ = a \\oplus (\\neg b \\land c)$），为算法注入了必不可少的非线性特性。这个步骤设计简洁、可逆且在硬件实现上极其高效。它独立地作用于状态的每一“行切片”，并与 Keccak-f 的其他四个步骤（$\\theta$, $\\rho$, $\\pi$, $\\iota$）紧密协作，经过多轮迭代后，最终实现了强大的密码学混淆与扩散，从而能够构造出安全的哈希函数。