概述

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

SHA家族的算法，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布，是美国的政府标准，其分别是：

• SHA-0：1993年发布，当时称做安全散列标准（Secure Hash Standard），发布之后很快就被NSA撤回，是SHA-1的前身。
• SHA-1：1995年发布，SHA-1在许多安全协议中广为使用，包括TLS、GnuPG、SSH、S/MIME和IPsec，是MD5的后继者。但SHA-1的安全性在2010年以后已经不被大多数的加密场景所接受。2017年荷兰密码学研究小组CWI和Google正式宣布攻破了SHA-1。
• SHA-2：2001年发布，包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-2目前没有出现明显的弱点。虽然至今尚未出现对SHA-2有效的攻击，但它的算法跟SHA-1基本上仍然相似。
• SHA-3：2015年正式发布，由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的SHA-3。

SHA-1

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

2005年，密码分析人员发现了对SHA-1的有效攻击方法，这表明该算法可能不够安全，不能继续使用，自2010年以来，许多组织建议用SHA-2或SHA-3来替换SHA-1。Microsoft、Google以及Mozilla都宣布，它们旗下的浏览器将在2017年停止接受使用SHA-1算法签名的SSL证书。

2017年2月23日，CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击，发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

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

算法实现伪代码

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating

//初始化（h0,h1,h2,h3跟 MD5 保持一致）
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

//补全消息，首先必须添加一位 1，之后补 0，使得消息长度(bits) % 512 = 448
//然后把 message 的字节长度模上 2^64，以 64 位大端序的方式拼在尾部，总比特位数恰好可以被 512 整除
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append original length in bits as 64-bit big-endian integer to message

//每次处理 512 位
for each 512-bit chunk of message
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
    
    //扩展 16 位的 w 数组为 80 位
    for i from 16 to 79
        w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
    
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    
    //Main loop:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f := (b and c) or ((not b) and d)
            k := 0x5A827999
        else if 20 ≤ i ≤ 39
            f := b xor c xor d
            k := 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f := (b and c) or (b and d) or(c and d)
            k := 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f := b xor c xor d
            k := 0xCA62C1D6
        temp := (a leftrotate 5) + f + e + k + w[i]
        e := d
        d := c
        c := b leftrotate 30
        b := a
        a := temp
    
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e

//Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4

与 MD5 的实现过程是基本一致， 不一样的地方主要如下（实现的差异）：

• 输入消息的比特长度： MD5 没有限制的，SHA-1 最长 2^64 - 1 位（消息比特长度填充到消息尾部过程中，MD5 需要模 2^64 后填充最后 64 位，SHA-1 直接填充最后 64 位）；
• 输出 16 进制数的长度：MD5 是 32 位，SHA-1 是 40 位（增加一个 h4，其他 4 个初始值是一样的）；
• k 常量：MD5 是通过正弦函数获取的，SHA-1 是固定四个常量 0x5A827999，0x6ED9EBA1，0x8F1BBCDC，0xCA62C1D6，这四个常量分别是素数 2, 3, 5, 10，先开根号，再乘上 2^30，最后向下取整。比如：floor(sqrt(2) * 2^30) -> floor(1518500249.9880) -> 1518500249 -> 0x5A827999

SHA-2

SHA-2，名称来自于安全散列算法2（英语：Secure Hash Algorithm 2）的缩写，一种密码散列函数算法标准，由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在2001年发布。属于SHA算法之一，是SHA-1的后继者。其下又可再分为六个不同的算法标准，包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

SHA-2 系列的算法主要思路和 SHA-1 基本一致

SHA-256 的伪代码

//前 8 个素数（2, 3, 5, 7, 11, 13, 17, 19），依次通过 floor(sqrt_小数部分(x) * 2^32) 运算
//比如：h0 = floor(sqrt_小数部分(2) * 2^32) = floor(0.414213562373095 * 2^32) 
//        = floor(1779033703.952099) = 1779033703 = 0x6a09e667
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

//前 64 个素数，依次通过 floor(cbrt_小数部分(x) * 2^32) 运算
//比如：k[0] = floor(cbrt_小数部分(2) * 2^32) = floor(0.259921049894873 * 2^32) 
//          = floor(1116352408.840464) = 1116352408 = 0x428a2f98
k[0..63] :=
   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2


// 跟 SHA-1 一样的处理
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append original length in bits as 64-bit big-endian integer to message

for each 512-bit chunk of message
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
    
    for i from 16 to 63
        s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3)
        s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7
    
    for i from 0 to 63
        s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22)
        maj := (a and b) xor (a and c) xor(b and c)
        t2 := s0 + maj
        s1 := (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        t1 := h + s1 + ch + k[i] + w[i]
        
        h := g
        g := f
        f := e
        e := d + t1
        d := c
        c := b
        b := a
        a := t1 + t2
        
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h
    
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

SHA-512 的伪代码

//与 SHA-256 相比，把之前的 32-bit 改成 64-bit
h[0..7] := 0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1, 
           0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179

// 前 80 个素数
k[0..79] := [ 0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, 
              0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, 0x12835b0145706fbe, 
              0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 
              0xc19bf174cf692694, 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 
              0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 0x983e5152ee66dfab, 
              0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 0xc6e00bf33da88fc2, 0xd5a79147930aa725, 
              0x06ca6351e003826f, 0x142929670a0e6e70, 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 
              0x53380d139d95b3df, 0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b, 
              0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30, 0xd192e819d6ef5218, 
              0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8, 0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 
              0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 
              0x682e6ff3d6b2b8a3, 0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec, 
              0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 0xca273eceea26619c, 
              0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 0x06f067aa72176fba, 0x0a637dc5a2c898a6, 
              0x113f9804bef90dae, 0x1b710b35131c471b, 0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 
              0x431d67c49c100d4c, 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817]

append "1" bit to message
append "0" bits until message length in bits ≡ 896 (mod 1024)
append original length in bits as 128-bit big-endian integer to message

for each 1024-bit chunk of message
    break chunk into sixteen 64-bit big-endian words w[i], 0 ≤ i ≤ 15
    
    for i from 16 to 79
        s0 := (w[i-15] rightrotate 1) xor (w[i-15] rightrotate 8) xor (w[i-15] rightshift 7)
        s1 := (w[i-2] rightrotate 19) xor (w[i-2] rightrotate 61) xor (w[i-2] rightshift 6)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7
    
    for i from 0 to 79
        S0 := (a rightrotate 28) xor (a rightrotate 34) xor (a rightrotate 39)
        maj := (a and b) xor (a and c) xor(b and c)
        t2 := S0 + maj
        S1 := (e rightrotate 14) xor (e rightrotate 18) xor (e rightrotate 41)
        ch := (e and f) xor ((not e) and g)
        t1 := h + S1 + ch + k[i] + w[i]
        
        h := g
        g := f
        f := e
        e := d + t1
        d := c
        c := b
        b := a
        a := t1 + t2
        
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h
    
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

前 100 个素数表

2   3   5   7   11  13  17  19  23  29
31  37  41  43  47  53  59  61  67  71
73  79  83  89  97  101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541

SHA-224

SHA-224 和 SHA-256 基本上是相同的，除了：

• h0 到 h7 的初始值不同；
• SHA-224 输出时截掉 h7 的函数值。

// 生成规则与 SHA-256 一样，取第 9 至第 16 个素数
h[0..7] :=
    0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939, 
    0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4

SHA-512

SHA-512 和 SHA-256 的结构相同，除了：

• SHA-512 所有的数字都是 64 位；
• SHA-512 运行 80 次加密循环而非 64 次；
• SHA-512 初始值和常量拉长成 64 位；
• 二者比特的偏移量和循环位移量不同。

SHA-384

SHA-384 和 SHA-512 基本上是相同的，除了：

• h0 到 h7 的初始值不同；
• SHA-384 输出时截掉 h6 和 h7 的函数值。

// 生成规则与 SHA-512 一样，取第 9 至第 16 个素数
h[0..7] := 0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939, 
           0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4

SHA-512/224 和 SHA-512/256

SHA-512/224、SHA-512/256 和 SHA-512 基本上是相同的，除了：

• h0 到 h7 的初始值不同；
• 输出时，h0 到 h7 组成的比特中，分别取前 244 位和前 256 位。

h0 到 h7 的生成过程中（以 SHA-512/224 为例）

1. 先把 SHA-512 对应的 h[0..7] 依次与 0xa5a5a5a5a5a5a5a5 进行异或运算，得到 h'[0..7]；
2. SHA-512 使用 h'[0..7] 对 "SHA-512/224" 字符串进行加密处理，得到 512-bit 的 data；
3. 把 data 分成 8 个 64-bit 的组成新的 h"[0..7]

SHA-3

SHA-3 第三代安全散列算法(Secure Hash Algorithm 3)，之前名为 Keccak 算法。

Keccak 是一个加密散列算法，由 Guido Bertoni，Joan Daemen，Michaël Peeters，以及 Gilles Van Assche 在 RadioGatún 上设计。

2012年10月2日，Keccak 被选为 NIST 散列函数竞赛的胜利者。SHA-2 目前没有出现明显的弱点。由于对 MD5、SHA-0 和 SHA-1 出现成功的破解，NIST 感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的 SHA-3。

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。

海绵结构

海绵函数允许输入长度和输出长度都可变。所以海绵函数可以用于设计 Hash 函数（固定输出长度）。

SHA-3 的设计者将 SHA-3 使用的基本迭代结构称为海绵结构方案。

海绵结构分“吸收过程”和“挤出过程”两个过程。

• 吸收过程：把一个长度为 n 的消息，填充后，分成 k 组，每个分组的长度为 r，通过分组尾部补 0 扩展其长度为 b（c = b - r，c 定义为容量），每个分组依次作为每轮迭代的输入丢进一个函数 f 中，同时上轮迭代的输出也反馈至下轮的迭代中，最终产生一组长度为 b 的输出块 S
• 挤出过程：假设输出的长度为 d，Z₀ 为 S 的前 r 位
  • 如果 d <= r，则直接输出块 Z₀ 的前 d 位
  • 如果 d > r， 令 c = ceil(d/r)，再进行 c - 1 次函数 f 操作，一共有产生 c 个长度为 r 的输出块，依次为 Z₀, Z₁, ... Z_c-1，拼接取前 d 位输出

sha_img01.jpg

海绵函数由三组参数定义：

• pad = 填充算法
• r = 输入分组的位长度，称其为位速率，r 越大，海绵结构处理消息的速度就越快
• f = 迭代函数，用于处理每轮的输入分组，输出一个等长的分组

关于填充算法 pad

一般海绵结构推荐两种填充方案

• 简单填充：用 pad 10* 表示，用一个 1 后面跟若干个 0 进行填充， 0 的个数是使得总长度为分组长度整倍数的最小值；
• 多重位速率填充：用 pad 10*1 表示，用一个 1 后面跟若干个 0，再跟一个 1 进行填充， 0 的个数是使得总长度为分组长度整倍数的最小值。

注意：为了格式统一，任意消息都需要进行填充。因此如果 n mod r = 0，那么将填充一个 r 位的完整块。

关于 SHA3 的海绵结构

接下来主要看一下轮函数 f 的实现，轮函数 f 每次处理块的长度为 1600 位（即：b = 1600）。

轮函数 f 的主要功能是，输入一个长度为 b 的 s，经过轮函数 f 处理后，返回一个同样长度的 s'。

可以表示为：s'_b = f(s_b)

在轮函数 f 中，会把 1600 位的输入 s，转换成 5 * 5 * 64 的矩阵 a，然后对矩阵 a 循环 24 轮处理，每轮处理包含 5 个步骤分别是：θ, ρ, π, χ, ι。

θ 步函数

输入一个 5 * 5 * 64 的矩阵 A，输出 5 * 5 * 64 的矩阵 A'

C[x, z] = A[x, 0, z] ⊕ A[x, 1, z] ⊕ A[x, 2, z] ⊕ A[x, 3, z] ⊕ A[x, 4, z] （0≤x<5 and 0≤z<64）
D[x, z]=C[(x-1) mod 5, z] ⊕ C[(x+1) mod 5, (z–1) mod 64] （0≤x<5 and 0≤z<64）
A′[x, y, z] = A[x, y, z] ⊕ D[x, z] (0≤x<5, 0≤y<5, and 0≤z<64)

ρ 步函数

输入一个 5 * 5 * 64 的矩阵 A，输出 5 * 5 * 64 的矩阵 A'

ρ 步函数主要是对 A[x, y, z] 中的 z 进行置换

if x == 0 && y == 0
    A'[0, 0, z] = A[0, 0, z]
else
    A'[x, y, z] = A[x, y, (z-(t+1)(t+2)/2) mod 64]

x、y、t 之间的关系，满足在 GF(5)^2*2 上：

sha_img02.png

其中 0 <= t < 24，并且 t 决定了 x 和 y 值。

比如 t = 3，会得到 x = 1 和 y = 2

sha_img03.png

矩阵中各字的循环移位值

sha_img04.png

π 步函数

输入一个 5 * 5 * 64 的矩阵 A，输出 5 * 5 * 64 的矩阵 A'

// 0≤x<5, 0≤y<5, and 0≤z<64
A′[x, y, z] = A[(x + 3y) mod 5, x, z]

χ 步函数

输入一个 5 * 5 * 64 的矩阵 A，输出 5 * 5 * 64 的矩阵 A'

// 0≤x<5, 0≤y<5, and 0≤z<64
A′[x, y, z] = A[x, y, z] ⊕ ((A[(x+1) mod 5, y, z] ⊕ 1) AND A[(x+2) mod 5, y, z])

ι 步函数

输入一个 5 * 5 * 64 的矩阵 A，输出 5 * 5 * 64 的矩阵 A'

A′[x, y] = A[x, y] ⊕ RC[i_r], 0<= i_r < 24

其中 A[x, y] 表示一个 64 位的纵，z 为 0..63

sha_img05.png

对比

对于 Hash 函数 h = H(x)，称 x 是 h 的原像。

抗原像攻击（单向性）：对任意给定的 Hash 码 h，找到满足 H(y) = h 的 y 在计算上是不可行的

抗第二原像攻击（抗弱碰撞性）：对任何给定的分块x，找到满足 y != x 且 H(x) = H(y) 的 y 在计算上是不可行的

抗碰撞攻击（抗强碰撞性）：找到任何满足 H(x) = H(y) 的偶对 (x,y) 在计算上是不可行的

参考资料

• MD5
• 维基百科(zh)-SHA家族
• 维基百科(zh)-SHA-1
• 维基百科(zh)-SHA-2
• 维基百科(zh)-SHA-3
• 维基百科(en)-SHA-1
• 维基百科(en)-SHA-2
• NIST.FIPS.180-4.pdf
• NIST.FIPS.202.pdf
• 密码编码学与网络安全第七版