Home 存档 照片墙 年度计划
Home 存档 照片墙 年度计划

手把手教你SHA-256

安全

前言

SHA-256是SHA-2协议簇的一部分，也是当前最流行的协议算法之一。在本篇文章中，我们会了解这个密码学算法的每一个步骤，并且通过实例演示。SHA-2因它的安全性（比SHA-1强很多）和速度为人所知。在没有键（keys）生成的情况下，例如挖掘比特币，像SHA-2这样的快速哈希算法很有优势。

什么是hash 函数？

hash函数有三个主要功能：

  • 保证数据的完整性
  • 接受任意长度的输入并输出一个固定长度的结果
  • 不可逆的处理数据，保证无法从输出反向推导出输入

SHA-2是非常著名且强大的hash函数群，能够为你提供以上所有功能

SHA-2家族 vs SHA-256

SHA-2是一种广义上如何处理hash数据的算法。SHA-2有好几种变体，它们使用同一种算法但是使用不同的常量。例如SHA-256，设置了许多额外的定义SHA-2算法行为的常量，其中一个常量就是用来控制输出长度的，没错就是256。SHA-256和SHA-512中的256和512指的就是各自的摘要的比特长度

SHA-2家族 vs SHA-1

SHA-2是SHA-1的继承者，并且保留了其中一个最强大的hash函数，至今仍在使用。但SHA-256并没有像SHA-1一样在安全性上有所妥协。因此，如今没有理由继续使用不安全的SHA-1了。SHA-2灵活的输出长度（224、256、512等等）使其能很好适应流行的KDFs和AES-256

NIST的正式验收

SHA-256是由**美国国家标准与技术研究院的**FIPS 180-4正式发布的。除了标准化和规范化之外，还有一个测试向量列表，允许开发人员确保他们已经正确地实现了算法。

手把手实现“hello world”的SHA-256 hash

第一步：预处理

  • 将“hello world”转移成二进制：
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100
  • 末尾添加一个1
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 1
  • 对消息进行补位处理，使得最终的长度是 512 位的倍数，现在只有64比特（在我们的例子中现在需要增加到448比特，后面一步还需要增加64比特）
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • 末尾再加64位，这64位代表原始输入的长度的二进制表达方式。在我们这个例子中，是88，或者二进制“1011000”
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01011000

现在我们就有了我们的输入数据，并且肯定可以被512整除。

第二步：初始化hash值（h）

现在我们新建8组hash值，它们是硬编码的常量，表示前8个素数（2、3、5、7、11、13、17、19）的平方根的小数部分的前32位

h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

第三步：初始化圆常数（k）

类似于第二步，我们定义一些常数。这次有64个。它们表示前64个素数（2-311）的立方根的小数部分的前32位

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

第四步：区块循环

以 512 位为单位对我们的输入进行分块，每块都将进行接下来的步骤。在我们的例子中，因为“hello world”太短了，所以我们只有一个区块。在每一次循环迭代中，我们都会改变hash值h0-h7，形成最终输出

第五步：创建消息附表（w）

  • 将第一步的数据放入一个新的数组，每项都为32位
01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
  • 再另外加48项数据，都初始化为0，这样我们就得到了数组 w[0…63]
01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
...
...
00000000000000000000000000000000 00000000000000000000000000000000

  • 使用以下算法修改数组末尾的置零索引:

    • For i from w[16…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
      • （rightrotate：循环右移，最右侧移到最左侧；rightshift：右移，最右侧移除，最左侧补0；xor：异或运算）

我们以w[16]为例，来看如何运行：

w[1] rightrotate 7:
  01101111001000000111011101101111 -> 11011110110111100100000011101110
w[1] rightrotate 18:
  01101111001000000111011101101111 -> 00011101110110111101101111001000
w[1] rightshift 3:
  01101111001000000111011101101111 -> 00001101111001000000111011101101

s0 = 11011110110111100100000011101110 XOR 00011101110110111101101111001000 XOR 00001101111001000000111011101101

s0 = 11001110111000011001010111001011

w[14] rightrotate 17:
  00000000000000000000000000000000 -> 00000000000000000000000000000000
w[14] rightrotate19:
  00000000000000000000000000000000 -> 00000000000000000000000000000000
w[14] rightshift 10:
  00000000000000000000000000000000 -> 00000000000000000000000000000000

s1 = 00000000000000000000000000000000 XOR 00000000000000000000000000000000 XOR 00000000000000000000000000000000

s1 = 00000000000000000000000000000000

w[16] = w[0] + s0 + w[9] + s1

w[16] = 01101000011001010110110001101100 + 11001110111000011001010111001011 + 00000000000000000000000000000000 + 00000000000000000000000000000000

// addition is calculated modulo 2^32

w[16] = 00110111010001110000001000110111

这样我们就能得到信息列表中的全部64个数组对象

01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
00110111010001110000001000110111 10000110110100001100000000110001
11010011101111010001000100001011 01111000001111110100011110000010
00101010100100000111110011101101 01001011001011110111110011001001
00110001111000011001010001011101 10001001001101100100100101100100
01111111011110100000011011011010 11000001011110011010100100111010
10111011111010001111011001010101 00001100000110101110001111100110
10110000111111100000110101111101 01011111011011100101010110010011
00000000100010011001101101010010 00000111111100011100101010010100
00111011010111111110010111010110 01101000011001010110001011100110
11001000010011100000101010011110 00000110101011111001101100100101
10010010111011110110010011010111 01100011111110010101111001011010
11100011000101100110011111010111 10000100001110111101111000010110
11101110111011001010100001011011 10100000010011111111001000100001
11111001000110001010110110111000 00010100101010001001001000011001
00010000100001000101001100011101 01100000100100111110000011001101
10000011000000110101111111101001 11010101101011100111100100111000
00111001001111110000010110101101 11111011010010110001101111101111
11101011011101011111111100101001 01101010001101101001010100110100
00100010111111001001110011011000 10101001011101000000110100101011
01100000110011110011100010000101 11000100101011001001100000111010
00010001010000101111110110101101 10110000101100000001110111011001
10011000111100001100001101101111 01110010000101111011100000011110
10100010110101000110011110011010 00000001000011111001100101111011
11111100000101110100111100001010 11000010110000101110101100010110

第六步：压缩

  • 初始化变量a, b, c, d, e, f, g, h并将初始值分别设定为当前的hash值h0, h1, h2, h3, h4, h5, h6, h7

  • 开始压缩循环，压缩循环会改变a-h的变量的值，压缩循环步骤如下：

  • for i from 0 to 63

    • S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    • ch = (e and f) xor ((not e) and g)
    • temp1 = h + S1 + ch + k[i] + w[i]
    • S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    • maj = (a and b) xor (a and c) xor (b and c)
    • temp2 := S0 + maj
    • h = g
    • g = f
    • f = e
    • e = d + temp1
    • d = c
    • c = b
    • b = a
    • a = temp1 + temp2

下面以第一次迭代为例，所有的加法都是按2^32的模计算的:

a = 0x6a09e667 = 01101010000010011110011001100111
b = 0xbb67ae85 = 10111011011001111010111010000101
c = 0x3c6ef372 = 00111100011011101111001101110010
d = 0xa54ff53a = 10100101010011111111010100111010
e = 0x510e527f = 01010001000011100101001001111111
f = 0x9b05688c = 10011011000001010110100010001100
g = 0x1f83d9ab = 00011111100000111101100110101011
h = 0x5be0cd19 = 01011011111000001100110100011001

e rightrotate 6:
  01010001000011100101001001111111 -> 11111101010001000011100101001001
e rightrotate 11:
  01010001000011100101001001111111 -> 01001111111010100010000111001010
e rightrotate 25:
  01010001000011100101001001111111 -> 10000111001010010011111110101000
S1 = 11111101010001000011100101001001 XOR 01001111111010100010000111001010 XOR 10000111001010010011111110101000
S1 = 00110101100001110010011100101011

e and f:
    01010001000011100101001001111111
  & 10011011000001010110100010001100 =
    00010001000001000100000000001100
not e:
  01010001000011100101001001111111 -> 10101110111100011010110110000000
(not e) and g:
    10101110111100011010110110000000
  & 00011111100000111101100110101011 =
    00001110100000011000100110000000
ch = (e and f) xor ((not e) and g)
   = 00010001000001000100000000001100 xor 00001110100000011000100110000000
   = 00011111100001011100100110001100

// k[i] is the round constant
// w[i] is the batch
temp1 = h + S1 + ch + k[i] + w[i]
temp1 = 01011011111000001100110100011001 + 00110101100001110010011100101011 + 00011111100001011100100110001100 + 01000010100010100010111110011000 + 01101000011001010110110001101100
temp1 = 01011011110111010101100111010100

a rightrotate 2:
  01101010000010011110011001100111 -> 11011010100000100111100110011001
a rightrotate 13:
  01101010000010011110011001100111 -> 00110011001110110101000001001111
a rightrotate 22:
  01101010000010011110011001100111 -> 00100111100110011001110110101000
S0 = 11011010100000100111100110011001 XOR 00110011001110110101000001001111 XOR 00100111100110011001110110101000
S0 = 11001110001000001011010001111110

a and b:
    01101010000010011110011001100111
  & 10111011011001111010111010000101 =
    00101010000000011010011000000101
a and c:
    01101010000010011110011001100111
  & 00111100011011101111001101110010 =
    00101000000010001110001001100010
b and c:
    10111011011001111010111010000101
  & 00111100011011101111001101110010 =
    00111000011001101010001000000000
maj = (a and b) xor (a and c) xor (b and c)
    = 00101010000000011010011000000101 xor 00101000000010001110001001100010 xor 00111000011001101010001000000000 
    = 00111010011011111110011001100111

temp2 = S0 + maj
      = 11001110001000001011010001111110 + 00111010011011111110011001100111
      = 00001000100100001001101011100101

h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e = 10100101010011111111010100111010 + 01011011110111010101100111010100
  = 00000001001011010100111100001110
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a = 01011011110111010101100111010100 + 00001000100100001001101011100101
  = 01100100011011011111010010111001

整个计算过程又进行了63次，修改了变量a-h。我们不会详列所有步骤，直接给出最后的结果：

h0 = 6A09E667 = 01101010000010011110011001100111
h1 = BB67AE85 = 10111011011001111010111010000101
h2 = 3C6EF372 = 00111100011011101111001101110010
h3 = A54FF53A = 10100101010011111111010100111010
h4 = 510E527F = 01010001000011100101001001111111
h5 = 9B05688C = 10011011000001010110100010001100
h6 = 1F83D9AB = 00011111100000111101100110101011
h7 = 5BE0CD19 = 01011011111000001100110100011001

a = 4F434152 = 01001111010000110100000101010010
b = D7E58F83 = 11010111111001011000111110000011
c = 68BF5F65 = 01101000101111110101111101100101
d = 352DB6C0 = 00110101001011011011011011000000
e = 73769D64 = 01110011011101101001110101100100
f = DF4E1862 = 11011111010011100001100001100010
g = 71051E01 = 01110001000001010001111000000001
h = 870F00D0 = 10000111000011110000000011010000

第七步：调整最终结果

到目前为止，结束了当前区块循环中的压缩循环，我们调整一下hash值，分别加上对应的变量a-h。此次运算依旧按2^32的模计算

h0 = h0 + a = 10111001010011010010011110111001
h1 = h1 + b = 10010011010011010011111000001000
h2 = h2 + c = 10100101001011100101001011010111
h3 = h3 + d = 11011010011111011010101111111010
h4 = h4 + e = 11000100100001001110111111100011
h5 = h5 + f = 01111010010100111000000011101110
h6 = h6 + g = 10010000100010001111011110101100
h7 = h7 + h = 11100010111011111100110111101001

第八步：连接最终的hash值

最后，将上面所有的hash值连接起来

digest = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
       = B94D27B9934D3E08A52E52D7DA7DABFAC484EFE37A5380EE9088F7ACE2EFCDE9

完成了！我们已经完成SHA-256每一步的细节了。真棒！

原文：https://qvault.io/cryptography/how-sha-2-works-step-by-step-sha-256/

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 (CC BY-NC-ND 4.0) 进行许可。