01

SHA256簡(jiǎn)介

SHA256是SHA-2下細(xì)分出的一種算法

SHA-2，名稱來(lái)自于安全散列算法2（英語(yǔ)：Secure Hash Algorithm 2）的縮寫，一種密碼散列函數(shù)算法標(biāo)準(zhǔn)，由美國(guó)國(guó)家安全局研發(fā)，屬于SHA算法之一，是SHA-1的后繼者。

SHA-2下又可再分為六個(gè)不同的算法標(biāo)準(zhǔn)

包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

這些變體除了生成摘要的長(zhǎng)度 、循環(huán)運(yùn)行的次數(shù)等一些微小差異外，算法的基本結(jié)構(gòu)是一致的。

回到SHA256上，說(shuō)白了，它就是一個(gè)哈希函數(shù)。

哈希函數(shù)，又稱散列算法，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來(lái)。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值（或哈希值）的指紋。散列值通常用一個(gè)短的隨機(jī)字母和數(shù)字組成的字符串來(lái)代表。

對(duì)于任意長(zhǎng)度的消息，SHA256都會(huì)產(chǎn)生一個(gè)256bit長(zhǎng)的哈希值，稱作消息摘要。

這個(gè)摘要相當(dāng)于是個(gè)長(zhǎng)度為32個(gè)字節(jié)的數(shù)組，通常用一個(gè)長(zhǎng)度為64的十六進(jìn)制字符串來(lái)表示

來(lái)看一個(gè)例子：

干他100天成為區(qū)塊鏈程序員，紅軍大叔帶領(lǐng)著我們，fighting!

這句話，經(jīng)過(guò)哈希函數(shù)SHA256后得到的哈希值為：

A7FCFC6B5269BDCCE571798D618EA219A68B96CB87A0E21080C2E758D23E4CE9

這里找到了一個(gè)SHA256在線驗(yàn)證工具，可以用來(lái)進(jìn)行SHA256哈希結(jié)果的驗(yàn)證，后面也可以用來(lái)檢驗(yàn)自己的SHA256代碼是否正確。用起來(lái)很方便，不妨感受下。

02

SHA256原理詳解

為了更好的理解SHA256的原理，這里首先將算法中可以單獨(dú)抽出的模塊，包括常量的初始化、信息預(yù)處理、使用到的邏輯運(yùn)算分別進(jìn)行介紹，甩開(kāi)這些理解上的障礙后，一起來(lái)探索SHA256算法的主體部分，即消息摘要是如何計(jì)算的。

2.1 常量初始化

SHA256算法中用到了8個(gè)哈希初值以及64個(gè)哈希常量

其中，SHA256算法的8個(gè)哈希初值如下：

這些初值是對(duì)自然數(shù)中前8個(gè)質(zhì)數(shù)（2,3,5,7,11,13,17,19）的平方根的小數(shù)部分取前32bit而來(lái)

舉個(gè)例子來(lái)說(shuō)，$ \sqrt{2} $小數(shù)部分約為0.414213562373095048，而

于是，質(zhì)數(shù)2的平方根的小數(shù)部分取前32bit就對(duì)應(yīng)出了0x6a09e667

在SHA256算法中，用到的64個(gè)常量如下：

428a2f98 71374491 b5c0fbcf e9b5dba53956c25b 59f111f1 923f82a4 ab1c5ed5d807aa98 12835b01 243185be 550c7dc372be5d74 80deb1fe 9bdc06a7 c19bf174e49b69c1 efbe4786 0fc19dc6 240ca1cc2de92c6f 4a7484aa 5cb0a9dc 76f988da983e5152 a831c66d b00327c8 bf597fc7c6e00bf3 d5a79147 06ca6351 1429296727b70a85 2e1b2138 4d2c6dfc 53380d13650a7354 766a0abb 81c2c92e 92722c85a2bfe8a1 a81a664b c24b8b70 c76c51a3d192e819 d6990624 f40e3585 106aa07019a4c116 1e376c08 2748774c 34b0bcb5391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3748f82ee 78a5636f 84c87814 8cc7020890befffa a4506ceb bef9a3f7 c67178f2

和8個(gè)哈希初值類似，這些常量是對(duì)自然數(shù)中前64個(gè)質(zhì)數(shù)(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…)的立方根的小數(shù)部分取前32bit而來(lái)。

2.2 信息預(yù)處理(pre-processing)

SHA256算法中的預(yù)處理就是在想要Hash的消息后面補(bǔ)充需要的信息，使整個(gè)消息滿足指定的結(jié)構(gòu)。

信息的預(yù)處理分為兩個(gè)步驟：附加填充比特和附加長(zhǎng)度

STEP1：附加填充比特

在報(bào)文末尾進(jìn)行填充，使報(bào)文長(zhǎng)度在對(duì)512取模以后的余數(shù)是448

填充是這樣進(jìn)行的：先補(bǔ)第一個(gè)比特為1，然后都補(bǔ)0，直到長(zhǎng)度滿足對(duì)512取模后余數(shù)是448。

需要注意的是，信息必須進(jìn)行填充，也就是說(shuō)，即使長(zhǎng)度已經(jīng)滿足對(duì)512取模后余數(shù)是448，補(bǔ)位也必須要進(jìn)行，這時(shí)要填充512個(gè)比特。

因此，填充是至少補(bǔ)一位，最多補(bǔ)512位。

例：以信息“abc”為例顯示補(bǔ)位的過(guò)程。

a,b,c對(duì)應(yīng)的ASCII碼分別是97,98,99

于是原始信息的二進(jìn)制編碼為：01100001 01100010 01100011

補(bǔ)位第一步，首先補(bǔ)一個(gè)“1” ：0110000101100010 01100011 1

補(bǔ)位第二步,補(bǔ)423個(gè)“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

補(bǔ)位完成后的數(shù)據(jù)如下（為了簡(jiǎn)介用16進(jìn)制表示）：

為什么是448?

因?yàn)樵诘谝徊降念A(yù)處理后，第二步會(huì)再附加上一個(gè)64bit的數(shù)據(jù)，用來(lái)表示原始報(bào)文的長(zhǎng)度信息。而448+64=512，正好拼成了一個(gè)完整的結(jié)構(gòu)。

STEP2：附加長(zhǎng)度值

附加長(zhǎng)度值就是將原始數(shù)據(jù)（第一步填充前的消息）的長(zhǎng)度信息補(bǔ)到已經(jīng)進(jìn)行了填充操作的消息后面。

wiki百科中給出的原文是：append length of message (before pre-processing), in bits, as 64-bit big-endian integer

SHA256用一個(gè)64位的數(shù)據(jù)來(lái)表示原始消息的長(zhǎng)度。

因此，通過(guò)SHA256計(jì)算的消息長(zhǎng)度必須要小于$ 2^64 $，當(dāng)然絕大多數(shù)情況這足夠大了。

長(zhǎng)度信息的編碼方式為64-bit big-endian integer

關(guān)于Big endian的含義，文末給出了補(bǔ)充

回到剛剛的例子，消息“abc”，3個(gè)字符，占用24個(gè)bit

因此，在進(jìn)行了補(bǔ)長(zhǎng)度的操作以后，整個(gè)消息就變成下面這樣了（16進(jìn)制格式）

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

2.3 邏輯運(yùn)算

SHA256散列函數(shù)中涉及的操作全部是邏輯的位運(yùn)算

包括如下的邏輯函數(shù)：

2.4 計(jì)算消息摘要

現(xiàn)在來(lái)介紹SHA256算法的主體部分，即消息摘要是如何計(jì)算的。

首先：將消息分解成512-bit大小的塊

(break message into 512-bit chunks)

假設(shè)消息M可以被分解為n個(gè)塊，于是整個(gè)算法需要做的就是完成n次迭代，n次迭代的結(jié)果就是最終的哈希值，即256bit的數(shù)字摘要。

一個(gè)256-bit的摘要的初始值H0，經(jīng)過(guò)第一個(gè)數(shù)據(jù)塊進(jìn)行運(yùn)算，得到H1，即完成了第一次迭代

H1經(jīng)過(guò)第二個(gè)數(shù)據(jù)塊得到H2，……，依次處理，最后得到Hn，Hn即為最終的256-bit消息摘要

將每次迭代進(jìn)行的映射用$ Map(H_{i-1}) = H_{i} $表示，于是迭代可以更形象的展示為：

圖中256-bit的Hi被描述8個(gè)小塊，這是因?yàn)镾HA256算法中的最小運(yùn)算單元稱為“字”（Word），一個(gè)字是32位。

此外，第一次迭代中，映射的初值設(shè)置為前面介紹的8個(gè)哈希初值，如下圖所示：

下面開(kāi)始介紹每一次迭代的內(nèi)容，即映射$ Map(H_{i-1}) = H_{i} $的具體算法

STEP1：構(gòu)造64個(gè)字（word）

break chunk into sixteen 32-bit big-endian words w[0], …, w[15]

對(duì)于每一塊，將塊分解為16個(gè)32-bit的big-endian的字，記為w[0], …, w[15]

也就是說(shuō)，前16個(gè)字直接由消息的第i個(gè)塊分解得到

其余的字由如下迭代公式得到：

STEP2：進(jìn)行64次循環(huán)

映射 $ Map(H_{i-1}) = H_{i} $ 包含了64次加密循環(huán)

即進(jìn)行64次加密循環(huán)即可完成一次迭代

每次加密循環(huán)可以由下圖描述：

圖中，ABCDEFGH這8個(gè)字（word）在按照一定的規(guī)則進(jìn)行更新，其中

深藍(lán)色方塊是事先定義好的非線性邏輯函數(shù)，上文已經(jīng)做過(guò)鋪墊

紅色田字方塊代表 mod $ 2^{32} $ addition，即將兩個(gè)數(shù)字加在一起，如果結(jié)果大于$ 2^{32} ，你必須除以 ，你必須除以，你必須除以 2^{32} $并找到余數(shù)。

ABCDEFGH一開(kāi)始的初始值分別為$ H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7) $

Kt是第t個(gè)密鑰，對(duì)應(yīng)我們上文提到的64個(gè)常量

Wt是本區(qū)塊產(chǎn)生第t個(gè)word。原消息被切成固定長(zhǎng)度512-bit的區(qū)塊，對(duì)每一個(gè)區(qū)塊，產(chǎn)生64個(gè)word，通過(guò)重復(fù)運(yùn)行循環(huán)n次對(duì)ABCDEFGH這八個(gè)字循環(huán)加密。

最后一次循環(huán)所產(chǎn)生的八個(gè)字合起來(lái)即是第i個(gè)塊對(duì)應(yīng)到的散列字符串$ H_{i} $