30. SHA 1 哈希算法解析

SHA 1 的全称是 Secure Hash Algorithm 1, 即安全散列算法 1, 是由美国国家安全局设计的一种哈希算法, 它可以针对输入的比特流产生长度为 160 bit 的消息摘要, SHA 1 的 Secure 体现在首先针对一段 SHA 1 输出的消息摘要反推出原文是几乎不可计算的, 另外, 对于不同的输入产生相同的输出的概率也是极低的, 与 MD5 类似, 其可以用来作为文件标识或数据签名, 本文讨论 SHA 1 算法的运行原理

SHA 1 数据结构

在正式讨论 SHA 1 算法之前, 首先给出一些相关定义, 这些定义将在下面用到, SHA 1 针对输入的比特流是按块 (block) 依次进行处理的, 每个块的长度固定为 512 bit, SHA 1 算法允许的最大输入长度为 $2^{64} - 1$ bit, 在 SHA 1 算法中, 我们将 32 bit 定义为字 (word), 所以每个字可以用 8 位十六进制来表示, 例如对于字 1010 0001 0000 0011 1111 1110 0010 0011 可表示为 A103FE23, 对于一个长度在 [0, $2^{32} - 1$ ] 的整数便可以用一个字来表示, 整数的最低有效 4 位为字的最右侧的十六进制字符, 对于一个整数 z, 若 $0 \leq z < 2^{64}$ , 则 $z = (2^{32}x + y)$ , 其中 $0 \leq x, y < 2^{32}$ , 于是 $x$ , $y$ 都分别可以用一个字来表示, 我们记这两个字分别为 $X$ , $Y$ , 此时整数 z 便可以使用这对字来表示, 我们记为 $(X, Y)$

我们将可以针对 bit 的逻辑运算符 (与或非异或等) 拓展定义到字上,

X AND Y 为两个字按位逻辑与
X OR Y 为两个字按位逻辑或
X XOR Y 为两个字按位异或
NOT X 为对字 X 的每一位按位取反

除了逻辑运算, 我们还可以定义字上的算术运算,

X + Y 定义为 (x + y) mod $2^{32}$

最后我们定义字上的循环左移运算 (逻辑移位), 循环左移即是将字的比特整体向左移动 n 位, 左侧溢出的比特位补到右侧空出来的比特位, 我们将这一运算记作 S^n(X), 循环左移可以使用逻辑表达式来描述, 如下所示

S^n(X) = (X << n) OR (X >> 32 -n)

上面提到, SHA 1 算法是按照块 (block) 依次处理输入的比特流的, 每个块的长度固定为 512 bit, 但 SHA 1 并不限制算法输入的长度必须是 512 的整数倍, SHA 1 算法首先会对输入的比特流的进行预处理, 将比特流填充为 512 的整数倍, 具体的做法是这样

首先, SHA 1 处理的最后一个块的最后 64 bit 是保留位, 保留位用来描述输入信息的长度 (这里的长度指的是消息的原始长度, 不包括预处理过程中填充的比特), SHA 1 首先会对输入的比特流填充一个 1, 然后填充 n 个 0, 最后填充 64 位的保留位, 整个填充操作完成之后必须保证整体比特流的长度为 512 的整数倍, 因此所填充的 0 的个数 n 是不固定的, 需要根据消息的实际长度来确定, 举例来说, 假设输入的比特流为 01100001 01100010 01100011 01100100 01100101, 一共 40 位, 我们首先在其后添加一个 1, 得到 41 位的 01100001 01100010 01100011 01100100 01100101 1, 最后 64 位 (即两个字) 为保留位, 用于指示原消息长度, 特别地, 当消息长度不足 $2^{32}$ 时, 其第一个字 (即倒数 64 位至倒数 32 位) 全部置为 0, 最后 32 位指示原消息的长度, 所以对于当前这个例子, 原消息长度为 40 bit, 我们在填充比特 1 和 64 位的保留位后还剩下 512 - 40 - 1 - 64 = 407, 即中间我们需要填充 407 bit 的 0, 最终预处理结束后的比特流 (十六进制表示) 为

61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000028

此外, SHA 1 定义了 4 个逻辑函数和 4 个常量 (Magic Number), 每个逻辑函数都针对 3 个字作为输入, 函数的输出为一个字, 其中 t (0 ≤ t ≤ 79) 是变量, 函数的表达式如下

  f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)

  f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)

  f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)

  f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79)

4 个常量分别如下 (十六进制表示)

  K(t) = 5A827999         ( 0 <= t <= 19)

  K(t) = 6ED9EBA1         (20 <= t <= 39)

  K(t) = 8F1BBCDC         (40 <= t <= 59)

  K(t) = CA62C1D6         (60 <= t <= 79)

SHA 1 算法解析

上面我们给出了 SHA 1 定义的概念及相关的运算, 以及逻辑函数与常量, 现在我们详细展开讨论 SHA 1 算法的处理过程, 首先我们定义 5 个字, 分别记为 $H_0$ , $H_1$ , $H_2$ , $H_3$ , $H_4$ , 并分别赋予它们给定的初始值, 如下所示

  H0 = 67452301

  H1 = EFCDAB89

  H2 = 98BADCFE

  H3 = 10325476

  H4 = C3D2E1F0

经过预处理后, 所要处理的比特流被切割成固定 512 bit 的块的序列, 将块序列记为 M(0), M(1), ... , M(n-1), 我们按顺序依次处理每一个块, 对于块 M(i), 其中 $i \in [0, n)$ , 我们进行如下操作:

将块切割为 16 个字, 分别记为 W(0), W(2), ... , W(15)
定义循环变量 t, 对 t 从 16 到 79 依次赋值, 每一次循环计算 W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)), 循环完成后我们此时已得到 80 个字
定义 5 个字, 分别记为 A, B, C, D, E, 依次将 $H_0$ , $H_1$ , ... , $H_4$ 赋值给它们, 即 A = H0, B = H1, C = H2, D = H3, E = H4
定义循环变量 t, 对 t 从 0 到 79 依次赋值, 每一次循环执行如下操作:
- TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
- E = D;
- D = C;
- C = S^30(B);
- B = A;
- A = TEMP;
分别令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E

从 M(0) 开始每一轮计算后会得到新的 $H_0$ , $H_1$ , ... , $H_4$ , 下一轮计算中使用上一次产生的新值, 对最后一个块计算完毕后得到的 $H_0$ , $H_1$ , ... , $H_4$ 便是算法的输出, 即原文的 SHA 1 哈希值

代码实现

现代编程语言的标准库通常都内置了 SHA 1 算法的实现, 也可以阅读这里的 C 实现

SHA 1 数据结构

SHA 1 算法解析

代码实现

更多地