哈希函数SHA-1计算过程

SHA-1是一种密码散列函数

英文全称：Secure Hash Algorithm 1

中文名：安全散列算法1

设计者： 美国国家安全局

摘要长度：160位

分组长度：512位

计算轮数：80轮

首次发布：1993年(SHA-0)/1995年(SHA-1)

安全性：2020年，针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。

位运算符说明

\( \lnot \) 取反

\(\land\) 按位与

\(\lor\) 按位或

\(\oplus\) 异或

\( \verb|<<| \) 左移

\( \lll \) 循环左移

\( \ggg \) 循环右移

原始消息：abc

转为二进制

a 二进制 01100001

b 二进制 01100010

c 二进制 01100011

对消息分组，每组512位长度

abc 的二进制 01100001 01100010 01100011

总长度24位，不够512位，需要补位

\( \begin{align*} \underbrace{01100001}_{a} \quad \underbrace{01100010}_{b} \quad \underbrace{01100011}_{c} \quad 1 \quad \overbrace{00...00}^{423} \quad \overbrace{00...0\underbrace{11000}_{l=24} }^{64} \end{align*} \)

补位说明：

<1> 先在abc后面补1

<2> 规定末尾64位表示原始消息的长度

abc的二进制长度为24，24的二进制为11000，末尾就是 \(\overbrace{00...0\underbrace{11000}_{l=24} }^{64} \hspace{1em}\)

<3>中间剩下423个空位全部补0

(3x8) + 1 + 423 + 64 = 512

这样补位后总长度为512位,刚好凑足1组。

补位完毕，此时消息为：

\( \begin{align*} M^1 = 01100001 01100010 01100011 1 <423个0> <59个0> 11000 \end{align*} \)

补位举例：

如果消息长度为447，补1后，刚好448，此时不需要补0，直接补末尾64位即可，消息被分为1组。

如果消息长度为448，补1后，达到449位，这个时候第1组剩下63位，不够64位，就需要补63位0，再继续补448个0，最后补64位消息长度，消息被分为2组。

如果消息被分为多组，记为 \( \begin{align*} {M^1, M^2 ,M^3, ..., M^i} \end{align*} \) ，对于消息abc，只用到\(M^1\)

将\(M^1\)按32位切割为16组，标记为

\(\begin{align*} W_0 = 01100001011000100110001110000000\end{align*}\)

\(\begin{align*} W_1 = 00000001011000100110001110000000\end{align*}\)

\(\begin{align*} W_2 = 00000001011000100110001110000000\end{align*}\)

\(\begin{align*} ...... \end{align*}\)

\(\begin{align*} W_{15} = 00000001011000100110001110011000\end{align*}\)

现在已经有了\(W_0到W_{15}\)，还需要生成 \(W_{16} 到 W_{79}\)

生成函数：

\( \begin{align*} W_t = \begin{cases} M_t^{i} & 0 \leq t \leq 15 \\[2ex] ROTL^1(W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16} ) & 16 \leq t \leq 79 \\ \end{cases} \end{align*} \)

\( \begin{align*} 例如：W_{16} = ROTL^1(W_{13} \oplus W_{8} \oplus W_{2} \oplus W_{0}) \end{align*} \)

\(ROTL\)函数的定义:

\( \begin{align*} & ROTL^n(x) = (x \ll n) \lor (x \gg w-n) \\ & w 为 x 的位长,本例中w=32 \\ \end{align*} \)

按照上面的函数最终生成块\( W_0 到 W_{79} \) 共80组。

设定初始哈希值

\(H_0^{(0)}=67452301\)

\(H_1^{(0)}=EFCDAB89\)

\(H_2^{(0)}=98BADCFE\)

\(H_3^{(0)}=10325476\)

\(H_4^{(0)}=C3D2E1F0\)

这5个初始哈希值是算法设定不变的

仅用于第一组消息，处理后续分组的时候使用前一组计算的结果

定义5个临时变量\(A,B,C,D,E\)并赋值

\(A=H_0^{(0)}\)

\(B=H_1^{(0)}\)

\(C=H_2^{(0)}\)

\(D=H_3^{(0)}\)

\(E=H_4^{(0)}\)

然后开始80轮的循环计算(轮次用t表示)

算法逻辑图

常数\(K_t\)定义

\( \begin{align*} K_t = \begin{cases} 5a827999 \qquad & 0 \leq t \leq 19 \\ 6ed9eba1 & 20 \leq t \leq 39 \\ 8f1bbcdc & 40 \leq t \leq 59 \\ ca62c1d6 & 60 \leq t \leq 79 \\ \end{cases} \end{align*} \)

F函数定义

\( \begin{align*} f_t(x,y,z) = \begin{cases} (x \land y ) \oplus ( \lnot x \land z ) \quad & 0 \leq t \leq 19 \\ x \oplus y \oplus z \quad & 20 \leq t \leq 39 \\ (x \land y ) \oplus ( x \land z ) \oplus (y \land z) \quad \quad & 40 \leq t \leq 59 \\ x \oplus y \oplus z \quad & 60 \leq t \leq 79 \\ \end{cases} \end{align*} \)

以第一轮计算举例(T为临时变量):

\( \begin{align*} & T = A\lll5 + f_0(B,C,D) + E + K_0 + W_0 \\ & E = D \\ & D = C \\ & C = B \lll 30 \\ & B = A \\ & A = T \\ \end{align*} \)

以上步骤循环计算80轮，最后把\(A,B,C,D,E\)的结果和其初始值相加

\(H_0^{(1)} = A + H_0^{(0)} \)

\(H_1^{(1)} = B + H_1^{(0)} \)

\(H_2^{(1)} = C + H_2^{(0)} \)

\(H_3^{(1)} = D + H_3^{(0)} \)

\(H_4^{(1)} = E + H_4^{(0)} \)

依次顺序拼接\(H_0^{(1)},H_1^{(1)},H_2^{(1)},H_3^{(1)},H_4^{(1)}\)就是\(M^1\)的哈希值

如果有分组\(M^2\)将\(M^1\)的结果作为\(M^2\)的初始哈希值继续计算

参考文献