SHA-1 哈希算法的填充与迭代过程详解
字数 2595 2025-12-19 12:50:09

SHA-1 哈希算法的填充与迭代过程详解

我将为您详细讲解 SHA-1 哈希算法的填充与迭代过程。SHA-1（Secure Hash Algorithm 1）是一种曾经广泛使用但现已不推荐用于安全用途的哈希算法，了解其结构仍对学习密码学有重要意义。

一、算法概述

SHA-1 输入任意长度消息（最大 \(2^{64}-1\) 位），输出固定长度160位（20字节）的哈希值。其核心处理流程分为两步：消息填充、迭代压缩。

二、消息填充（Padding）

目标：将任意长度的原始消息，填充为长度是512位（64字节）整数倍的数据块。
填充规则如下：

  1. 附加比特“1”：在原始消息末尾直接添加一个“1”比特。

    • 例如原始消息是“abc”（二进制01100001 01100010 01100011，24位），先在其后附加一个“1”比特，变成 01100001 01100010 01100011 1。

  2. 附加 k 个“0”比特：k 是满足以下等式的最小非负整数：

\[ (\text{原始消息长度} + 1 + k) \equiv 448 \pmod{512} \]

  • 即填充“1”和“0”后，总长度对512取模等于448位。
  • 计算示例：原始“abc”长24位，则 24+1+k ≡ 448 (mod 512)。24+1=25，需加423个“0”使得总长448位，即 k=423。
  1. 附加64位长度字段：最后附加一个64位的无符号整数，表示原始消息的位长度（填充前的长度）。
    • 注意：这个长度是原始消息的比特长度，而不是填充后的长度。
    • 对于“abc”，原始长度24位（二进制 000…00011000，共64位，高位补0）。
    • 这64位按照大端序（big-endian）存储，即高位字节在低地址。

填充完成后：总长度是512位的整数倍。我们将填充后的消息分割成连续的512位块 \(M^{(1)}, M^{(2)}, …, M^{(N)}\)，N 是块数。

实例计算“abc”的填充：

  • 原始消息“abc”：二进制 01100001 01100010 01100011 （24位）
  • 附加“1”：01100001 01100010 01100011 1 （25位）
  • 附加423个“0”：使总长达到 25+423=448 位
  • 附加64位长度“24”：二进制 000…00011000 （64位，高位补0）
  • 最终块长度为 448+64=512 位（1块）。

三、初始化哈希值

SHA-1 使用5个32位寄存器（A, B, C, D, E）作为哈希状态，初始值（十六进制）为：

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
E = 0xC3D2E1F0

这5个值连接起来就是160位的初始哈希值 \(H^{(0)}\)。

四、迭代压缩过程

对每个512位消息块 \(M^{(i)}\)（i 从1到N）进行处理，更新哈希值。

步骤1：消息扩展

将512位块 \(M^{(i)}\) 扩展为 80 个32位字 \(W_0, W_1, …, W_{79}\)，供80轮压缩使用。

  • 前16个字 \(W_0\) 到 \(W_{15}\) 直接取自 \(M^{(i)}\)，按大端序解释为32位整数。
  • 剩余字 \(W_{16}\) 到 \(W_{79}\) 通过递推公式计算：

\[ W_t = (W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16}) \lll 1 \]

其中 \(\oplus\) 是异或，\(\lll 1\) 是循环左移1位。

步骤2：压缩函数

压缩函数执行80轮运算，每轮更新寄存器 A, B, C, D, E。设当前块处理前的哈希值为 \(H^{(i-1)}\)，将其赋值给：

A = H0, B = H1, C = H2, D = H3, E = H4

然后进行80轮变换，每轮 t（从0到79）执行：

  1. 计算轮函数 f_t：

    • 0 ≤ t ≤ 19: \(f_t(B,C,D) = (B \land C) \lor (\lnot B \land D)\)
    • 20 ≤ t ≤ 39: \(f_t(B,C,D) = B \oplus C \oplus D\)
    • 40 ≤ t ≤ 59: \(f_t(B,C,D) = (B \land C) \lor (B \land D) \lor (C \land D)\)
    • 60 ≤ t ≤ 79: \(f_t(B,C,D) = B \oplus C \oplus D\)
      （其中 \(\land\) 是与，\(\lor\) 是或，\(\lnot\) 是非）

  2. 计算临时变量：

\[ \text{temp} = (A \lll 5) + f_t(B,C,D) + E + K_t + W_t \]

  • \(A \lll 5\) 是 A 循环左移5位
  • \(K_t\) 是轮常数（见下文）
  • 所有加法是模 \(2^{32}\) 加法
  1. 更新寄存器： 
    E = D
D = C
C = B \lll 30
B = A
A = temp

轮常数 \(K_t\) 取值：

  • 0 ≤ t ≤ 19: \(K_t = 0x5A827999\)
  • 20 ≤ t ≤ 39: \(K_t = 0x6ED9EBA1\)
  • 40 ≤ t ≤ 59: \(K_t = 0x8F1BBCDC\)
  • 60 ≤ t ≤ 79: \(K_t = 0xCA62C1D6\)

步骤3：更新哈希值

80轮后，将当前寄存器的值模 \(2^{32}\) 加到旧哈希值上：

\[\begin{aligned} H_0^{(i)} &= H_0^{(i-1)} + A \\ H_1^{(i)} &= H_1^{(i-1)} + B \\ H_2^{(i)} &= H_2^{(i-1)} + C \\ H_3^{(i)} &= H_3^{(i-1)} + D \\ H_4^{(i)} &= H_4^{(i-1)} + E \end{aligned} \]

结果作为处理下一个消息块的输入哈希值 \(H^{(i)}\)。

五、最终输出

处理完所有 N 个块后，得到的 \(H^{(N)}\) 就是最终哈希值，将 \(H_0, H_1, H_2, H_3, H_4\) 按大端序连接成160位输出。

六、总结

SHA-1 的过程可概括为：填充消息至512位倍数 → 初始化5个哈希寄存器 → 对每个块进行80轮压缩（使用消息扩展和轮函数）→ 输出连接后的哈希值。尽管 SHA-1 因碰撞攻击已被弃用，但其填充和迭代结构是理解经典哈希算法的基础。

SHA-1 哈希算法的填充与迭代过程详解 我将为您详细讲解 SHA-1 哈希算法的填充与迭代过程。SHA-1（Secure Hash Algorithm 1）是一种曾经广泛使用但现已不推荐用于安全用途的哈希算法，了解其结构仍对学习密码学有重要意义。 一、算法概述 SHA-1 输入任意长度消息（最大 $2^{64}-1$ 位），输出固定长度160位（20字节）的哈希值。其核心处理流程分为两步：消息填充、迭代压缩。 二、消息填充（Padding） 目标：将任意长度的原始消息，填充为长度是512位（64字节）整数倍的数据块。 填充规则如下： 附加比特“1” ：在原始消息末尾直接添加一个“1”比特。 例如原始消息是“abc”（二进制01100001 01100010 01100011，24位），先在其后附加一个“1”比特，变成 01100001 01100010 01100011 1。 附加 k 个“0”比特 ：k 是满足以下等式的最小非负整数： \[ (\text{原始消息长度} + 1 + k) \equiv 448 \pmod{512} \] 即填充“1”和“0”后，总长度对512取模等于448位。 计算示例：原始“abc”长24位，则 24+1+k ≡ 448 (mod 512)。24+1=25，需加423个“0”使得总长448位，即 k=423。 附加64位长度字段 ：最后附加一个64位的无符号整数，表示原始消息的位长度（填充前的长度）。 注意：这个长度是原始消息的比特长度，而不是填充后的长度。 对于“abc”，原始长度24位（二进制 000…00011000，共64位，高位补0）。 这64位按照 大端序 （big-endian）存储，即高位字节在低地址。 填充完成后 ：总长度是512位的整数倍。我们将填充后的消息分割成连续的512位块 $M^{(1)}, M^{(2)}, …, M^{(N)}$，N 是块数。 实例计算“abc”的填充 ： 原始消息“abc”：二进制 01100001 01100010 01100011 （24位） 附加“1”：01100001 01100010 01100011 1 （25位） 附加423个“0”：使总长达到 25+423=448 位 附加64位长度“24”：二进制 000…00011000 （64位，高位补0） 最终块长度为 448+64=512 位（1块）。 三、初始化哈希值 SHA-1 使用5个32位寄存器（A, B, C, D, E）作为哈希状态，初始值（十六进制）为： 这5个值连接起来就是160位的初始哈希值 $H^{(0)}$。 四、迭代压缩过程 对每个512位消息块 $M^{(i)}$（i 从1到N）进行处理，更新哈希值。 步骤1：消息扩展 将512位块 $M^{(i)}$ 扩展为 80 个32位字 $W_ 0, W_ 1, …, W_ {79}$，供80轮压缩使用。 前16个字 $W_ 0$ 到 $W_ {15}$ 直接取自 $M^{(i)}$，按大端序解释为32位整数。 剩余字 $W_ {16}$ 到 $W_ {79}$ 通过递推公式计算： \[ W_ t = (W_ {t-3} \oplus W_ {t-8} \oplus W_ {t-14} \oplus W_ {t-16}) \lll 1 \] 其中 $\oplus$ 是异或，$\lll 1$ 是循环左移1位。 步骤2：压缩函数 压缩函数执行80轮运算，每轮更新寄存器 A, B, C, D, E。设当前块处理前的哈希值为 $H^{(i-1)}$，将其赋值给： 然后进行80轮变换，每轮 t（从0到79）执行： 计算轮函数 f_ t ： 0 ≤ t ≤ 19: $f_ t(B,C,D) = (B \land C) \lor (\lnot B \land D)$ 20 ≤ t ≤ 39: $f_ t(B,C,D) = B \oplus C \oplus D$ 40 ≤ t ≤ 59: $f_ t(B,C,D) = (B \land C) \lor (B \land D) \lor (C \land D)$ 60 ≤ t ≤ 79: $f_ t(B,C,D) = B \oplus C \oplus D$ （其中 $\land$ 是与，$\lor$ 是或，$\lnot$ 是非） 计算临时变量 ： \[ \text{temp} = (A \lll 5) + f_ t(B,C,D) + E + K_ t + W_ t \] $A \lll 5$ 是 A 循环左移5位 $K_ t$ 是轮常数（见下文） 所有加法是模 $2^{32}$ 加法 更新寄存器 ： 轮常数 $K_ t$ 取值： 0 ≤ t ≤ 19: $K_ t = 0x5A827999$ 20 ≤ t ≤ 39: $K_ t = 0x6ED9EBA1$ 40 ≤ t ≤ 59: $K_ t = 0x8F1BBCDC$ 60 ≤ t ≤ 79: $K_ t = 0xCA62C1D6$ 步骤3：更新哈希值 80轮后，将当前寄存器的值模 $2^{32}$ 加到旧哈希值上： \[ \begin{aligned} H_ 0^{(i)} &= H_ 0^{(i-1)} + A \\ H_ 1^{(i)} &= H_ 1^{(i-1)} + B \\ H_ 2^{(i)} &= H_ 2^{(i-1)} + C \\ H_ 3^{(i)} &= H_ 3^{(i-1)} + D \\ H_ 4^{(i)} &= H_ 4^{(i-1)} + E \end{aligned} \] 结果作为处理下一个消息块的输入哈希值 $H^{(i)}$。 五、最终输出 处理完所有 N 个块后，得到的 $H^{(N)}$ 就是最终哈希值，将 $H_ 0, H_ 1, H_ 2, H_ 3, H_ 4$ 按大端序连接成160位输出。 六、总结 SHA-1 的过程可概括为：填充消息至512位倍数 → 初始化5个哈希寄存器 → 对每个块进行80轮压缩（使用消息扩展和轮函数）→ 输出连接后的哈希值。尽管 SHA-1 因碰撞攻击已被弃用，但其填充和迭代结构是理解经典哈希算法的基础。