SHA消息摘要

安全散列算法（英语：Secure Hash Algorithm，缩写为SHA）是一个密码散列函数家族，是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。且若输入的消息不同，它们对应到不同字符串的几率很高。

1. SHA简介

SHA目前有SHA-0、SHA-1、SHA-2、SHA-3四个算法版本，目前广泛使用的是SHA-2。

SHA函数对比
算法和变体 输出散列值长度
（bits） 		中继散列值长度
（bits） 		资料区块长度
（bits） 		最大输入消息长度
（bits） 		循环次数 使用到的运算符 碰撞攻击
（bits） 		性能示例[3]
(MiB/s)
MD5（作为参考） 128 128
(4 × 32)		 512 无限[4] 64 And, Xor, Rot, Add (mod 232), Or ≤18
（发现碰撞）		 335
SHA-0 160 160
(5 × 32)		 512 264 − 1 80 And, Xor, Rot, Add (mod 232), Or <34
（发现碰撞）		 -
SHA-1 160 160
(5 × 32)		 512 264 − 1 80 <63[5]
（发现碰撞[6]）		 192
SHA-2 SHA-224
SHA-256		 224
256		 256
(8 × 32)		 512 264 − 1 64 And, Xor, Rot, Add (mod 232), Or, Shr 112
128		 139
SHA-384
SHA-512
SHA-512/224
SHA-512/256		 384
512
224
256		 512
(8 × 64)		 1024 2128 − 1 80 And, Xor, Rot, Add (mod 264), Or, Shr 192
256
112
128		 154
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512		 224
256
384
512		 1600
(5 × 5 × 64)		 1152
1088
832
576		 无限[7] 24[8] And, Xor, Rot, Not 112
128
192
256		 -
SHAKE128
SHAKE256		 d (arbitrary)
d (arbitrary)		 1344
1088		 min(d/2, 128)
min(d/2, 256)		 -

由于SHA-2算法的各种变体除了生成摘要的长度 、循环运行的次数等一些微小差异外，算法的基本结构是一致的，且网上关于SHA256的算法解析较多，故在此以SHA256作简要说明。

原文引自《一文读懂SHA256算法原理及其实现》。为便于理解，提供SHA256算法步骤可视化，推荐对照可视化步骤逐步进行理解。

2. 原理解析

2.1. 常量初始化

初始哈希值$H^{(0)}$取自自然数中前面8个素数$(2,3,5,7,11,13,17,19)$的平方根的小数部分，并且取前面的32位。下面举个例子：$\sqrt{2}$小数部分约为$0.414213562373095048$，而其中

$$0.414213562373095048\approx6*16^{-1}+a*16^{-2}+0*16^{-3}+\cdots$$

于是，质数2的平方根的小数部分取前32位就对应0x6a09e667。

以此类推，初始哈希值$H^{(0)}$由以下8个32位的哈希初值构成：

$$H_{1}^{(0)}=6a09e667$$ $$H_{2}^{(0)}=bb67ae85$$ $$H_{3}^{(0)}=3c6ef372$$ $$H_{4}^{(0)}=a54ff53a$$ $$H_{5}^{(0)}=510e527f$$ $$H_{6}^{(0)}=9b05688c$$ $$H_{7}^{(0)}=1f83d9ab$$ $$H_{8}^{(0)}=5be0cd19$$

SHA256算法当中还使用到64个常数，取自自然数中前面64个素数的立方根的小数部分的前32位，如果用16进制表示，则相应的常数序列如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

428a2f98 71374491 b5c0fbcf e9b5dba5
3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3
72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc
2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7
c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13
650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3
d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5
391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208
90befffa a4506ceb bef9a3f7 c67178f2

2.2. 消息预处理

首先对消息进行补位处理，使得最终的长度是512位的倍数。然后以512位为一组对消息进行分块为：$M^{(1)},M^{(2)},\cdots,M^{(N)}$。

假设消息$M$的二进制编码长度为$l$位. 首先在消息末尾补上一位“$1$”，然后再补上$k$个“$0$”，其中$k$为下列方程的最小非负整数:

$$l+1+k=448\ mod\ 512$$

因为最后需要将长度$l$转换为64位二进制补位在消息最后，所以此处补位至$512-64=448$位，以确保补位后消息二进制位数的长度是$512$的整数倍。

这里需要注意的两点是

  • 不管原来的消息长度是多少，即使长度已经满足对512取模后余数是448，补位也必须要进行，这时要填充512位。
  • 另外，考虑到最后要将消息长度$l$转换为64位二进制编码，因此，长度的必须小于$2^{64}$，绝大多数情况，这个值足够大了。

将补码处理后的消息以512位为单位分块为：$M^{(1)},M^{(2)},\cdots,M^{(N)}$，其中第$i$个消息块的前32位表示为：$M_{0}^{(i)}$，接着32位为：$M_{1}^{(i)}$，以此类推，最后32位的消息块可表示为：$M_{15}^{(i)}$。我们采用$Big\ endian$（大端）约定对数据进行编码，即认为第一个字节是最高位字节，因此，对于每一个32位字节，最最左边的比特是最大的比特位。

2.3. 摘要计算主循环

为便于表示，约定如下算符（以下所有的操作都是针对32位二进制数据）：

算符 操作
$\oplus$ 按位异或
$\wedge$ 按位与
$\vee$ 按位或
$\neg$ 补位
$+$ 相加以后对$2^{32}$求余
$R^{n}$ 右移$n$位
$S^{n}$ 循环右移$n$位

约定如下函数： $$Ch(x,y,z)=(x \wedge y) \oplus (\neg x \wedge z)$$ $$M_{aj}(x,y,z)=(x \wedge y) \oplus (x \wedge z) \oplus (y \wedge z)$$ $$\Sigma_{0}(x)=S^{2}(x) \oplus S^{13}(x) \oplus S^{22}(x)$$ $$\Sigma_{1}(x)=S^{6}(x) \oplus S^{11}(x) \oplus S^{25}(x)$$ $$\sigma_{0}(x)=S^{7}(x) \oplus S^{18}(x) \oplus R^{3}(x)$$ $$\sigma_{1}(x)=S^{17}(x) \oplus S^{19}(x) \oplus R^{10}(x)$$

2.3.1. 扩展消息块计算

对源消息分块后的每个块$M^{(i)}$由512位扩展至2048位进行计算，其中每32个二进制位为一个$W_{j}$。

扩展消息块$W_{0},W_{1},\cdots,W_{63}$的计算方式如下：

  • $for\ j = 0 \rightarrow 15$ $$W_{j}=M_{j}^{(i)}$$

  • $for\ j = 16 \rightarrow 63$ $$W_{j}=W_{j-16}+\sigma_{0}(W_{j-15})+W_{j-7}+\sigma_{1}(W_{j-2})$$

全部计算完毕后进入下一步。

2.3.2. 中间哈希值计算

在常量初始化一节给出了初始哈希值$H^{(0)}$以及64个常数$K_{0},K_{1},\cdots,K_{63}$，在本节的计算中将会用到。同时在此引出$a,b,c,d,e,f,g,h$作为工作变量。

  • $for\ i = 1 \rightarrow N（N=补位后消息块个数）$ $$a=H_{1}^{(i-1)}$$ $$b=H_{2}^{(i-1)}$$ $$\vdots$$ $$h=H_{8}^{(i-1)}$$

    也即对于第一个块（当$i=1$时），用$H^{(0)}$初始化$a,b,c,d,e,f,g,h$，对于其后的每个块都用中间哈希值$H^{(i-1)}$初始化$a,b,c,d,e,f,g,h$。

    • $for\ j = 0 \rightarrow 63$

      首先给出$T_{1},T_{2}$的计算方法： $$T_{1}=h+\Sigma_{1}(e)+Ch(e,f,g)+K_{j}+W_{j}$$ $$T_{2}=\Sigma_{0}(a)+M_{aj}(a,b,c)$$

      对于扩展消息块$W_{0},W_{1},\cdots,W_{63}$的每一个$W_{j}$，进行一次如下运算： $$h=g$$ $$g=f$$ $$f=e$$ $$e=d+T_{1}$$ $$d=c$$ $$c=b$$ $$b=a$$ $$a=T_{1}+T_{2}$$

      全部计算完毕后，得出该块内$a,b,c,d,e,f,g,h$的终值，进行如下运算： $$H_{1}^{(i)}=a+H_{1}^{(i-1)}$$ $$H_{2}^{(i)}=b+H_{2}^{(i-1)}$$ $$\vdots$$ $$H_{8}^{(i)}=h+H_{8}^{(i-1)}$$

      $H_{1}^{(i)},H_{2}^{(i)},\cdots,H_{8}^{(i)}$即为该块中间哈希值结果，同时也是下一个块$a,b,c,d,e,f,g,h$的初值。

2.4. 得出哈希结果

对补位后的每个512位消息块进行上述计算，最终得出$H_{1}^{(N)},H_{2}^{(N)},\cdots,H_{8}^{(N)}$。以16进制表示并拼接在一起，以$H_{1}^{(N)}$作为最高位，其后依次是$H_{2}^{(N)},H_{3}^{(N)},\cdots,H_{8}^{(N)}$，其中$H_{8}^{(N)}$为最低位。拼接后得出的16进制数据即为结果，表示为大端模式。

2.5. 汇总

SHA256算法汇总如下：

  • 对消息进行补位使其最终的长度是512位的整数倍，然后以512位为单位进行分块。
  • 从一个固定的初始哈希$H^{(0)}$开始逐个处理消息区块，进行如下计算： $$H^{(i)}=H^{(i-1)}+C_{M^{(i)}}(H^{(i-1)})$$ 其中$C$是SHA256的压缩函数，$+$是$mod\ 2^{32}$加法，即将两个数字加在一起，结果对$2^{32}$取余，$H^{(N)}$是消息区块的哈希值。

引用