RIPEMD-160 哈希算法的压缩函数设计详解
题目描述
RIPEMD-160 是一种经典的哈希函数，输出长度为 160 比特，广泛应用于比特币等系统。它的核心是压缩函数，这个函数将 512 比特的消息块和 160 比特的中间状态（链接变量）作为输入，并输出一个新的 160 比特状态。我们需要深入理解其压缩函数的具体设计，包括其双管线并行结构、轮函数的计算、逻辑函数的使用、常数和循环移位的设计等。
解题过程（逐步详解）
步骤 1：理解压缩函数的输入与输出
- 输入：
- 一个 512 比特的消息块。在哈希计算中，原始消息经过填充和分块，每个块长度为 512 比特。
- 一个 160 比特的链接变量，通常由前一个块的输出或初始值（IV）提供。它可以被看作 5 个 32 比特的寄存器
(A, B, C, D, E)。
- 输出：
- 新的 160 比特链接变量，同样被表示为 5 个 32 比特的字
(A', B', C', D', E')，用于下一个消息块的处理或最终的哈希结果。
- 新的 160 比特链接变量，同样被表示为 5 个 32 比特的字
步骤 2：掌握压缩函数的整体双管线结构
RIPEMD-160 压缩函数的核心特点是并行处理两条管线，分别称为左管线和右管线。这种设计增强了其抗密码分析攻击（如差分攻击）的能力。
- 每条管线独立处理相同的 512 比特消息块，但使用不同的消息字顺序、逻辑函数、常数和循环移位。
- 每条管线包含 5 轮，每轮包含 16 步，总共 80 步。每一步更新 5 个寄存器中的一个。
- 在压缩函数末尾，两条管线的输出经过一个最终合并，产生新的链接变量。
初始时，链接变量被复制到两条管线的寄存器中：
- 左管线：
(A_L, B_L, C_L, D_L, E_L) = (A, B, C, D, E) - 右管线：
(A_R, B_R, C_R, D_R, E_R) = (A, B, C, D, E)
步骤 3：理解单条管线的单步运算
以左管线的单步为例。每一步的通用形式是：
A = (A + f(B, C, D) + X[k] + K) <<< s + E
B = A
C = B <<< 10
D = C
E = D
之后，寄存器被轮换：(A, B, C, D, E) = (E, A, B <<< 10, C, D)。
让我们详细分解：
-
逻辑函数 f：这是一个非线性函数，在 5 轮中每轮使用不同的定义（与 MD4/MD5/SHA-1 系列类似但不同）。对于左管线：
- 第 1 轮：
f(x, y, z) = x XOR y XOR z - 第 2 轮：
f(x, y, z) = (x ∧ y) ∨ (¬x ∧ z)（IF 函数） - 第 3 轮：
f(x, y, z) = (x ∨ ¬y) XOR z - 第 4 轮：
f(x, y, z) = (x ∧ z) ∨ (y ∧ ¬z)（类似于 IF，但参数顺序不同） - 第 5 轮：
f(x, y, z) = x XOR (y ∨ ¬z)
- 第 1 轮：
-
消息字 X[k]：这是从 512 比特消息块中提取的 32 比特字。消息块被划分为 16 个 32 比特字
X[0]到X[15]。在每一步，会从这 16 个字中按特定顺序选择一个。左管线和右管线使用的顺序不同，这是设计的关键之一，确保消息块被充分混合。 -
常数 K：每轮使用一个不同的 32 比特十六进制常数（以左管线为例）：
- 第 1 轮：
0x00000000 - 第 2 轮：
0x5A827999 - 第 3 轮：
0x6ED9EBA1 - 第 4 轮：
0x8F1BBCDC - 第 5 轮：
0xA953FD4E
（右管线的常数不同，例如第 1 轮是0x50A28BE6等）
- 第 1 轮：
-
循环左移 s：每步的循环移位位数是固定的，但不同轮、不同步的位数不同，增强了扩散。
-
加法运算：所有运算（加法、函数结果、消息字、常数）都是模 2^32 加法。
步骤 4：跟踪左右管线的不同参数
为了抵抗攻击，两条管线在以下方面故意不同：
- 逻辑函数 f：左右管线的 f 在每轮的定义相同，但应用顺序不同（例如，右管线第 1 轮的 f 等同于左管线第 5 轮的 f 等）。实际上，设计者通过交换和调整，使两条管线在代数上互补。
- 消息字顺序：每条管线在 80 步中，16 个消息字
X[0..15]被以特定置换顺序使用。左管线使用一个置换ρ，右管线使用另一个置换π。这确保了消息块的每个比特在两个管线中被不同地处理。 - 常数 K：如步骤 3 所述，常数不同。
- 循环移位 s：左右管线对应的步数使用的循环移位值通常不同。
步骤 5：完成 80 步后的最终合并
在每条管线完成 5 轮（共 80 步）后，得到两个结果：
- 左管线输出：
(A_L, B_L, C_L, D_L, E_L) - 右管线输出：
(A_R, B_R, C_R, D_R, E_R)
最终的链接变量更新为：
A' = B_L + C_R + A_initial
B' = C_L + D_R + B_initial
C' = D_L + E_R + C_initial
D' = E_L + A_R + D_initial
E' = A_L + B_R + E_initial
其中加法是模 2^32 加法，(A_initial, B_initial, C_initial, D_initial, E_initial) 是压缩函数开始时的链接变量输入。这个合并步骤将两条管线的结果与原始输入混合，产生最终输出。
步骤 6：理解设计的安全目标
- 抗碰撞性：双管线结构和不同的参数使得寻找两个不同消息产生相同哈希值（碰撞）的计算复杂度非常高，目标安全性为 2^80 次操作（由于生日攻击，160 比特输出的理论碰撞阻力是 2^80，但双管线设计旨在抵御已知的攻击方法）。
- 扩散性：消息块中一个比特的改变，通过 80 步的复杂运算和最终合并，会扩散到所有输出比特中。
- 非线性：逻辑函数 f 和模加法提供了非线性，防止从输出反推输入。
总结
RIPEMD-160 的压缩函数通过一个精心设计的双管线并行结构，结合不同的消息字顺序、逻辑函数、常数和移位，对每个 512 比特消息块进行 80 步处理，最终合并结果。这个设计平衡了效率和安全性，使其成为构建 160 比特哈希值的可靠核心。理解这个压缩函数是掌握 RIPEMD-160 算法的关键。