SHA256
1. SHA256簡介
SHA256是SHA-2下細分出的一種算法
SHA-2，名稱來自于安全散列算法2（英語：Secure Hash Algorithm 2）的縮寫，一種密碼散列函數算法標準，由美國國家安全局研發，屬于SHA算法之一，是SHA-1的后繼者。
SHA-2下又可再分為六個不同的算法標準
包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。
這些變體除了生成摘要的長度 、循環運行的次數等一些微小差異外，算法的基本結構是一致的。
回到SHA256上，說白了，它就是一個哈希函數。
哈希函數，又稱散列算法，是一種從任何一種數據中創建小的數字“指紋”的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值（或哈希值）的指紋。散列值通常用一個短的隨機字母和數字組成的字符串來代表。
對于任意長度的消息，SHA256都會產生一個256bit長的哈希值，稱作消息摘要。
這個摘要相當于是個長度為32個字節的數組，通常用一個長度為64的十六進制字符串來表示
來看一個例子：
干他100天成為區塊鏈程序員，紅軍大叔帶領著我們，fighting!
這句話，經過哈希函數SHA256后得到的哈希值為：
A7FCFC6B5269BDCCE571798D618EA219A68B96CB87A0E21080C2E758D23E4CE9
這里找到了一個SHA256在線驗證工具，可以用來進行SHA256哈希結果的驗證，后面也可以用來檢驗自己的SHA256代碼是否正確。用起來很方便，不妨感受下。
2. SHA256原理詳解
為了更好的理解SHA256的原理，這里首先將算法中可以單獨抽出的模塊，包括常量的初始化、信息預處理、使用到的邏輯運算分別進行介紹，甩開這些理解上的障礙后，一起來探索SHA256算法的主體部分，即消息摘要是如何計算的。
2.1 常量初始化
SHA256算法中用到了8個哈希初值以及64個哈希常量
其中，SHA256算法的8個哈希初值如下：
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19
這些初值是對自然數中前8個質數（2,3,5,7,11,13,17,19）的平方根的小數部分取前32bit而來
舉個例子來說，$ \sqrt{2} $小數部分約為0.414213562373095048，而
0.414213562373095048≈6?16?1+a?16?2+0?16?3+... 0.414213562373095048 \approx 6*16^{-1} + a*16^{-2} + 0*16^{-3} + ...
0.414213562373095048≈6?16?
?1
?+a?16?
?2
?+0?16?
?3
?+...
于是，質數2的平方根的小數部分取前32bit就對應出了0x6a09e667
在SHA256算法中，用到的64個常量如下：
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
和8個哈希初值類似，這些常量是對自然數中前64個質數(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…)的立方根的小數部分取前32bit而來。
2.2 信息預處理(pre-processing)
SHA256算法中的預處理就是在想要Hash的消息后面補充需要的信息，使整個消息滿足指定的結構。
信息的預處理分為兩個步驟：附加填充比特和附加長度
STEP1：附加填充比特
在報文末尾進行填充，使報文長度在對512取模以后的余數是448
填充是這樣進行的：先補第一個比特為1，然后都補0，直到長度滿足對512取模后余數是448。
需要注意的是，信息必須進行填充，也就是說，即使長度已經滿足對512取模后余數是448，補位也必須要進行，這時要填充512個比特。
因此，填充是至少補一位，最多補512位。
例：以信息“abc”為例顯示補位的過程。
a,b,c對應的ASCII碼分別是97,98,99
于是原始信息的二進制編碼為：01100001 01100010 01100011
補位第一步，首先補一個“1” ： 0110000101100010 01100011 1
補位第二步,補423個“0”：01100001 01100010 01100011 10000000 00000000 … 00000000
補位完成后的數據如下（為了簡介用16進制表示）：
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
為什么是448?
因為在第一步的預處理后，第二步會再附加上一個64bit的數據，用來表示原始報文的長度信息。而448+64=512，正好拼成了一個完整的結構。
STEP2：附加長度值
附加長度值就是將原始數據（第一步填充前的消息）的長度信息補到已經進行了填充操作的消息后面。
wiki百科中給出的原文是：append length of message (before pre-processing), in bits, as 64-bit big-endian integer
SHA256用一個64位的數據來表示原始消息的長度。
因此，通過SHA256計算的消息長度必須要小于$ 2^64 $，當然絕大多數情況這足夠大了。
長度信息的編碼方式為64-bit big-endian integer
關于Big endian的含義，文末給出了補充
回到剛剛的例子，消息“abc”，3個字符，占用24個bit
因此，在進行了補長度的操作以后，整個消息就變成下面這樣了（16進制格式）
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018
2.3 邏輯運算
SHA256散列函數中涉及的操作全部是邏輯的位運算
包括如下的邏輯函數：
Ch(x,y,z)=(x∧y)⊕(?x∧z) Ch(x,y,z) = (x \land y) \oplus (\neg x \land z)
Ch(x,y,z)=(x∧y)⊕(?x∧z)
Ma(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z) Ma(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)
Ma(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)
Σ0(x)=S2(x)⊕S13(x)⊕S22(x) \Sigma_{0}(x) = S^{2}(x) \oplus S^{13}(x) \oplus S^{22}(x)
Σ?
0
??? ?
?(x)=S?
2
?(x)⊕S?
13
?(x)⊕S?
22
?(x)
Σ1(x)=S6(x)⊕S11(x)⊕S25(x) \Sigma_{1}(x) = S^{6}(x) \oplus S^{11}(x) \oplus S^{25}(x)
Σ?
1
??? ?
?(x)=S?
6
?(x)⊕S?
11
?(x)⊕S?
25
?(x)
σ0(x)=S7(x)⊕S18(x)⊕R3(x) \sigma_{0}(x) = S^{7}(x) \oplus S^{18}(x) \oplus R^{3}(x)
σ?
0
??? ?
?(x)=S?
7
?(x)⊕S?
18
?(x)⊕R?
3
?(x)
σ1(x)=S17(x)⊕S19(x)⊕R10(x) \sigma_{1}(x) = S^{17}(x) \oplus S^{19}(x) \oplus R^{10}(x)
σ?
1
??? ?
?(x)=S?
17
?(x)⊕S?
19
?(x)⊕R?
10
?(x)
其中：
邏輯運算?? ?含義
∧ \land
∧
按位“與”
? \neg
?
按位“補”
⊕ \oplus
⊕
按位“異或”
Sn S^{n}
S?
n
?
循環右移n個bit
Rn R^{n}
R?
n
?
右移n個bit
2.4 計算消息摘要
現在來介紹SHA256算法的主體部分，即消息摘要是如何計算的。
首先：將消息分解成512-bit大小的塊
(break message into 512-bit chunks)
假設消息M可以被分解為n個塊，于是整個算法需要做的就是完成n次迭代，n次迭代的結果就是最終的哈希值，即256bit的數字摘要。
一個256-bit的摘要的初始值H0，經過第一個數據塊進行運算，得到H1，即完成了第一次迭代
H1經過第二個數據塊得到H2，……，依次處理，最后得到Hn，Hn即為最終的256-bit消息摘要
將每次迭代進行的映射用$ Map(H_{i-1}) = H_{i} $表示，于是迭代可以更形象的展示為：
圖中256-bit的Hi被描述8個小塊，這是因為SHA256算法中的最小運算單元稱為“字”（Word），一個字是32位。
此外，第一次迭代中，映射的初值設置為前面介紹的8個哈希初值，如下圖所示：
下面開始介紹每一次迭代的內容，即映射$ Map(H_{i-1}) = H_{i} $的具體算法
STEP1：構造64個字（word）
break chunk into sixteen 32-bit big-endian words w[0], …, w[15]
對于每一塊，將塊分解為16個32-bit的big-endian的字，記為w[0], …, w[15]
也就是說，前16個字直接由消息的第i個塊分解得到
其余的字由如下迭代公式得到：
Wt=σ1(Wt?2)+Wt?7+σ0(Wt?15)+Wt?16 W_{t} = \sigma_{1}(W_{t-2}) + W_{t-7} + \sigma_{0}(W_{t-15}) + W_{t-16}
W?
t
??? ?
?=σ?
1
??? ?
?(W?
t?2
??? ?
?)+W?
t?7
??? ?
?+σ?
0
??? ?
?(W?
t?15
??? ?
?)+W?
t?16
??? ?
?
STEP2：進行64次循環
映射 $ Map(H_{i-1}) = H_{i} $ 包含了64次加密循環
即進行64次加密循環即可完成一次迭代
每次加密循環可以由下圖描述：
圖中，ABCDEFGH這8個字（word）在按照一定的規則進行更新，其中
深藍色方塊是事先定義好的非線性邏輯函數，上文已經做過鋪墊
紅色田字方塊代表 mod $ 2^{32} $ addition，即將兩個數字加在一起，如果結果大于$ 2^{32} ，你必須除以 ，你必須除以，你必須除以 2^{32} $并找到余數。
ABCDEFGH一開始的初始值分別為$ H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7) $
Kt是第t個密鑰，對應我們上文提到的64個常量
Wt是本區塊產生第t個word。原消息被切成固定長度512-bit的區塊，對每一個區塊，產生64個word，通過重復運行循環n次對ABCDEFGH這八個字循環加密。
最后一次循環所產生的八個字合起來即是第i個塊對應到的散列字符串$ H_{i} $
由此變完成了SHA256算法的所有介紹
3. SHA256算法偽代碼
現在我們可以結合SHA256算法的偽代碼,將上述的所有步驟進行梳理整合：
Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19
Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
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
Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
? ? length (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
? ? break chunk into sixteen 32-bit big-endian words w[0..15]
? ? Extend the sixteen 32-bit words into sixty-four 32-bit words:
? ? 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
? ? Initialize hash value for this chunk:
? ? a := h0
? ? b := h1
? ? c := h2
? ? d := h3
? ? e := h4
? ? f := h5
? ? g := h6
? ? h := h7
? ? Main loop:
? ? 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
? ? Add this chunk's hash to result so far:
? ? h0 := h0 + a
? ? h1 := h1 + b
? ? h2 := h2 + c
? ? h3 := h3 + d
? ? h4 := h4 + e
? ? h5 := h5 + f
? ? h6 := h6 + g
? ? h7 := h7 + h
Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
4. 參考文獻
本篇筆記主要參考整合的資料如下：
SHA-2 wiki
比特幣算法——SHA256算法介紹
SHA-256算法實現
操作指南：驗證SHA256
知識填補
大端和小端（Big endian and Little endian）
對于整型、長整型等數據類型，都存在字節排列的高低位順序問題。
Big endian 認為第一個字節是最高位字節（按照從低地址到高地址的順序存放數據的高位字節到低位字節）
而 Little endian 則相反，它認為第一個字節是最低位字節（按照從低地址到高地址的順序存放據的低位字節到高位字節）。
例如，假設從內存地址 0x0000 開始有以下數據：
地址?? ?數據
…?? ?…
0x0000?? ?0x12
0x0001?? ?0x34
0x0002?? ?0xab
0x0003?? ?0xcd
…?? ?…
假設我們去讀取一個地址為 0x0000 的四個字節變量
若字節序為big-endian，則讀出結果為0x1234abcd；
若字節序為little-endian，則讀出結果為0xcdab3412。
如果我們將0x1234abcd 寫入到以 0x0000 開始的內存中，則Little endian 和 Big endian 模式的存放結果如下：
地址?? ?0x0000?? ?0x0001?? ?0x0002?? ?0x0003
big-Big_endian?? ?0x12?? ?0x34?? ?0xab?? ?0xcd
little-endian?? ?0xcd?? ?0xab?? ?0x34?? ?0x12
---------------------?
作者：隨煜而安?
來源：CSDN?
原文：https://blog.csdn.net/u011583927/article/details/80905740?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
- 上一篇： 趣图：菜鸟多线程 vs 老鸟多线程
- 下一篇： 速达3000 自动导入工具