SHA-256 哈希算法中 Ch 和 Maj 位运算函数的定义、作用与计算过程

今天我们来深入探讨 SHA-256 哈希算法压缩函数中的两个核心比特逻辑函数：Ch 和 Maj。它们是 SHA-256 实现高扩散、强非线性和安全性的关键组成部分。

一、函数定义与符号约定

在讲解之前，我们明确几个符号约定。SHA-256 以 32 位字（word）为基本运算单位。x, y, z 均代表 32 位的无符号整数。位运算符号含义如下：

• &：按位与 (AND)
• |：按位或 (OR)
• ^：按位异或 (XOR)
• ~：按位取反 (NOT)
• ⊕：也代表按位异或 (XOR)

1. 条件函数 (Choice function) - Ch(x, y, z)
其定义式为：

Ch(x, y, z) = (x & y) ⊕ (~x & z)

你可以这样理解它的逻辑：它根据输入 x 的每个比特位，选择 y 或 z 对应位置上的比特。

• 如果 x 的某一位是 1，则结果比特等于 y 对应位的比特。
• 如果 x 的某一位是 0，则结果比特等于 z 对应位的比特。

用伪代码表示其逻辑是：

if x[i] == 1:
    result[i] = y[i]
else: // x[i] == 0
    result[i] = z[i]

2. 多数函数 (Majority function) - Maj(x, y, z)
其定义式为：

Maj(x, y, z) = (x & y) ⊕ (x & z) ⊕ (y & z)

它的逻辑很简单：对于 x, y, z 三个输入在相同位置上的比特，输出这三个比特中的多数值（即，如果至少有两位是 1，则输出 1；如果至少有两位是 0，则输出 0）。

用真值表（1比特的情况）可以验证：

可以看到，当且仅当至少有两个输入为 1 时，输出为 1，这就是“多数”的含义。

二、它们在 SHA-256 压缩函数中的作用

这两个函数是 SHA-256 压缩函数核心处理逻辑的一部分，具体出现在每一轮（共 64 轮）的计算中。

SHA-256 的压缩函数维护一个 8 个 32 位字的状态寄存器，通常记为 A, B, C, D, E, F, G, H。在每一轮 t 的迭代中，会计算两个临时中间值：

1. T1：这是该轮的主要“工作”值，计算公式为：
   T1 = H + Σ1(E) + Ch(E, F, G) + K_t + W_t
   其中：

   • H, E, F, G 是当前轮的状态寄存器值。
   • Σ1(E) 是一个对 E 进行循环右移和异或的函数（用于位扩散）。
   • K_t 是第 t 轮的轮常数。
   • W_t 是第 t 轮的扩展消息字。

2. T2：这是状态更新的“辅助”值，计算公式为：
   T2 = Σ0(A) + Maj(A, B, C)
   其中：

   • A, B, C 是当前轮的状态寄存器值。
   • Σ0(A) 是另一个对 A 进行循环右移和异或的函数。

功能作用分析：

• Ch(E, F, G) 的作用：

  • 非线性来源：Ch 函数提供了 SHA-256 压缩函数中最主要的非线性（Non-linearity）。注意，& 和 ~ 运算的组合不是线性的，无法用简单的模加或异或来近似。非线性是抵抗线性密码分析的关键。
  • 条件传播：它将寄存器 E, F, G 的比特以条件选择的方式混合，使得输出同时依赖于三个状态字。E 在这里充当“选择器”，决定了是 F 还是 G 的比特流向输出，这大大增加了比特间依赖关系的复杂度。

• Maj(A, B, C) 的作用：

  • 非线性与扩散：Maj 是另一个非线性函数，但其结构不同于 Ch。它计算三个输入的“多数”，这同样是一个非线性操作。
  • 雪崩效应：Maj 的输出取决于三个输入。改变 A, B, C 中的任何一个或几个比特，都有 50% 的概率（在特定输入模式下）改变 Maj 的输出比特。这有助于微小的输入差异迅速扩散到整个状态，即实现“雪崩效应”。
  • 对称性与平衡性：Maj 函数对其三个输入是对称的（Maj(x, y, z) = Maj(y, x, z) 等），这使得它对所有三个输入的依赖是平等的，有助于在压缩函数的“前向”路径（涉及 A, B, C）上实现均匀的比特混合。

三、一个逐步计算实例

让我们通过一个具体的、简化的小例子（使用 4 位而不是 32 位）来演示计算过程，以便直观理解。

假设我们正在计算 SHA-256 的第 t 轮。为了演示 Ch 和 Maj，我们给定以下 4 位值（为简便起见）：

A = 1010 (二进制，十进制 10)
B = 1100 (二进制，十进制 12)
C = 0110 (二进制，十进制 6)
E = 1001 (二进制，十进制 9)
F = 0011 (二进制，十进制 3)
G = 0101 (二进制，十进制 5)

步骤 1：计算 Ch(E, F, G)

公式：Ch(E, F, G) = (E & F) ⊕ (~E & G)

a) 计算 E & F (按位与)：

    E:  1 0 0 1
    F:  0 0 1 1
    -----------
E & F: 0 0 0 1

b) 计算 ~E (E 按位取反)：

    E:  1 0 0 1
   ~E:  0 1 1 0

c) 计算 ~E & G：

   ~E:  0 1 1 0
    G:  0 1 0 1
    ------------
~E & G: 0 1 0 0

d) 将 a) 和 c) 的结果进行异或 ⊕：

E & F:  0 0 0 1
~E & G: 0 1 0 0
         ------------
Ch:      0 1 0 1  (二进制 0101，十进制 5)

验证：根据 Ch 的“选择”逻辑，逐位检查：

• 比特3 (最高位)：E=1，所以选 F=0 -> 结果 0 ✔
• 比特2：E=0，所以选 G=1 -> 结果 1 ✔
• 比特1：E=0，所以选 G=0 -> 结果 0 ✔
• 比特0：E=1，所以选 F=1 -> 结果 1 ✔
  结果 0101，与计算一致。

步骤 2：计算 Maj(A, B, C)

公式：Maj(A, B, C) = (A & B) ⊕ (A & C) ⊕ (B & C)

a) 计算 A & B：

    A:  1 0 1 0
    B:  1 1 0 0
    -----------
A & B: 1 0 0 0

b) 计算 A & C：

    A:  1 0 1 0
    C:  0 1 1 0
    -----------
A & C: 0 0 1 0

c) 计算 B & C：

    B:  1 1 0 0
    C:  0 1 1 0
    -----------
B & C: 0 1 0 0

d) 将 a), b), c) 的结果进行异或 ⊕：

A & B: 1 0 0 0
A & C: 0 0 1 0
B & C: 0 1 0 0
         ------------
        1 1 1 0  (注意：这里是三个数的异或，先两两异或，或直接三个数按位模2加)

我们按位计算（模2加，即异或）：

• 比特3: 1 ⊕ 0 ⊕ 0 = 1
• 比特2: 0 ⊕ 0 ⊕ 1 = 1
• 比特1: 0 ⊕ 1 ⊕ 0 = 1
• 比特0: 0 ⊕ 0 ⊕ 0 = 0
  所以 Maj = 1110 (二进制 1110，十进制 14)。

验证：根据“多数”逻辑，逐位检查：

• 比特3: A=1, B=1, C=0 -> 多数为 1 ✔
• 比特2: A=0, B=1, C=1 -> 多数为 1 ✔
• 比特1: A=1, B=0, C=1 -> 多数为 1 ✔
• 比特0: A=0, B=0, C=0 -> 多数为 0 ✔
  结果 1110，与计算一致。

步骤 3：在 SHA-256 压缩轮中的使用

在真实的 SHA-256 轮函数中，我们会得到：

• T1 的一部分是 Ch(E, F, G)，我们算得是 5 (4位示例值)。
• T2 的一部分是 Maj(A, B, C)，我们算得是 14 (4位示例值)。

之后，T1 和 T2 会与轮常数、消息字以及其他状态字进行模 2³² 加法，最终用于更新 8 个状态寄存器 A...H，完成一轮的压缩。

四、小结与安全意义

• Ch 和 Maj 是 SHA-256 非线性、扩散和混淆的核心。如果没有它们，SHA-256 将退化为一个线性变换，极易被攻破。
• 它们的运算（位与、位或、位非、位异或）在现代 CPU 上执行效率极高，使得 SHA-256 在提供高安全性的同时保持了优秀的软件性能。
• 这两个函数与循环移位函数 Σ0, Σ1 以及模 2³² 加法结合，构成了 SHA-256 强大的抗碰撞性和原像抵抗性的基础。任何对输入消息的微小修改，都会通过这两个函数与其它运算的迭代，迅速、复杂地传播到最终的哈希值中。

通过这个详细的拆解，希望你能清晰地理解 SHA-256 中这两个看似简单但至关重要的逻辑函数。