近日筆者在學習區塊鏈的相關知識，接觸到SHA-256算法，這里做一個知識梳理和總結。

強烈推薦大家自行去學習下面鏈接github上的工程，作者的動畫演示和解釋做的非常出色，邏輯非常清晰，B站搬運的對應的油管的講解視頻也放在下面，本文也是基于此github工程和作者學習過程的思路進行呈現。

github：

https://github.com/in3rsha/sha256-animation

B站講解視頻：

https://www.bilibili.com/video/BV1Jg411G7tc

ruby（windows）安裝教程：

https://www.cnblogs.com/minisayo/p/14015747.html

可以先將github工程下載到本地，因為作者是用的ruby進行動畫展示，所以需要再windows/Linux系統上安裝ruby，之后在工程目錄下調用ruby xxx.rb指令即可啦。

下面是整個工程的流程圖，也對應著SHA-256算法的設計思路。

一、運算定義

為了后續分析思路與流程的連貫性，在這里先統一聲明一下一些運算的定義，后續一些函數會直接對這些運算進行封裝使用。

1、右移Right Shift?(shr.rb)

這里的右移會產生兩種結果，第一種結果是左側移動完之后位為0，右側被移走的位丟失，如上圖所示SHR 32的操作，原數據為32位，在右移32位之后原數據都被右移丟失，剩下的左側移動完的位全為0。

2、旋轉右移Right Shift?(rotr.rb)

這里要尤其注意和SHR右移的區別，觀察演示圖可以發現對于旋轉右移而言數據組成了一個環形，移動位數只是改變位的絕對位置，并不會丟棄數據，所以原數據32位，再進行ROTR 32的操作實際上就是所有數據位旋轉了一整圈，又回到了原來的位置。

3、異或XOR (xor.rb)

按位異或，0^0 = 0，1^0 = 1，0^1 = 1，1^1 = 0。

4、加法Addition (add.rb)?

這里和二進制加法一樣，但是由于多個32位的數據相加，最終的存在著溢出的風險，因此最終的結果進行取模2*32將其約束在32位輸出。

二、函數定義

第一部分的運算被封裝組合起來就是這部分的函數，在這里先列出一些后續算法流程分析會用到的函數，讀者可以先有個大概印象，后面第三部分算法流程分析的時候再回看也可以。

前四個函數使用希臘符號 Sigma（小寫 σ，大寫 Σ）命名。這些名稱沒有特殊含義，只是為了方便給一些組合運算命名。

1、σ0 (sigma0.rb)

σ0(x) = ROTR7(x) ^ ROTR18(x) ^ SHR3(x)

先分別計算ROTR 7位和ROTR18位和SHR 3位，再將三者異或

2、σ1 (sigma1.rb)

σ1(x) = ROTR17(x) ^ ROTR19(x) ^ SHR10(x)

先分別計算ROTR 17位和ROTR 19位和SHR 10位，再將三者異或

3、Σ0 (usigma0.rb)

Σ0(x) = ROTR2(x) ^ ROTR13(x) ^ ROTR22(x)

先分別計算ROTR 2位和ROTR 13位和ROTR?22位，再將三者異或

4、Σ1 (usigma1.rb)?

Σ1(x) = ROTR6(x) ^ ROTR11(x) ^ ROTR25(x)

先分別計算ROTR 6位和ROTR 11位和ROTR?25位，再將三者異或

5、Choice (ch.rb)

這個函數使用x位在y位和z位之間進行選擇。如果x=1，則選擇y位；如果x=0，則選擇z位。

6、Majority (maj.rb)??

這個函數返回三位中的多數位。

7、常量Constants (constants.rb)

SHA-256 使用六十四個常量?Kt?來幫助在主哈希計算過程中混合比特。

首先計算前64個質數的立方根，然后取其小數部分乘2^32，將得到的常量作為Kt使用，其中t表示第t個質數運算后的結果。

這些立方根的小數部分是無理數（它們無限延伸），因此它們是用于常量的良好隨機比特選擇。這比使用特別選擇的常量更好，因為這降低了哈希函數被設計成具有后門的可能。

三、算法流程分析?

在這里message的內容是可以自己指定的，我們以message = dyq 為例（在每個rb文件的開頭可以自定義默認輸入）

1、message.rb?

輸入一個message字符串時，我們將每個字符轉換為 ASCII 表中的對應數字。這些數字被轉換為二進制，我們使用這些二進制數據作為哈希函數的輸入。?

2、padding.rb

SHA-256 哈希函數以 512 位的block數據塊為單位進行操作，因此所有消息都需要用零填充至最接近的 512 位的倍數，可以是512、1024等，這里先填充到448位，后64位預留出用來表示message的比特位數。

為了防止相似輸入哈希到相同的結果，我們用?1?位將消息與零分隔開，并在填充的最后 64 位中包含消息的大小。?

以上這種用?1?分隔消息并在填充中包含消息大小的方法被稱為 Merkle–Damg?rd 加強（MD 加強）。?

3、blocks.rb

消息經過填充后，我們將其切割成等長的 512 位消息塊?Mi?以便哈希函數處理。

每個消息塊也可以進一步分成 16 個詞Wj (?512 / 32 = 16 words?)，每個詞的長度為32bit，這將在后續使用。?

4、schedule.rb

?對于前16個word，每個word有32個bit，相當于是把原本的block0分為了32*16。

從第17個word開始根據下面的公式進行計算

Wt = σ1(Wt-2) + Wt-7 + σ0(Wt-15) + Wt-16

其中σ1和σ0在第二部分可以找到函數的定義。

5、expansion.rb

這一步展示的是上面最后一個word W63生成的運算過程。?

6、initial.rb

初始哈希值使用了前八個質數的平方根的小數部分。我們將這八個字母作為狀態寄存器，我們可以將其作為開始哈希計算的起點（初始狀態）

7、t1.rb t2.rb

我們需要先使用狀態寄存器中的當前值來計算兩個新的臨時詞（?T1?和?T2?），為后續的壓縮過程做準備。

T1 = Σ1(e) + Ch(e, f, g) + h + Kt + Wt

其中Σ1和Ch函數在第二部分，h為h狀態寄存器存儲的值，Kt為第二部分的64個常數值，Wt為schedule.rb求得的word。

T2 = Σ0(a) + Maj(a, b, c)

其中Σ0函數和Maj函數均在第二部分。

8、compression.rb

壓縮是整個算法的核心。我們再將其細化進行分析

（1） step1：計算出T1和T2

?（2） step2：所有寄存器下移一個

?（3） step3：更新a和e寄存器的值

以上三步可以概括為計算T1,T2；下移寄存器；更新a和e值，至此我們稱為完成一輪壓縮。這樣的壓縮要對一共64個word都進行一遍。

以上就是第二輪的step1開始以此類推。?

壓縮完64輪之后，將最終的abcdefgh寄存器的值和initial.rb中的abcdefgh中的值相加得到最后的寄存器值

如果還有進一步要處理的消息塊（block1，block2……），按照下圖當前的哈希值將作為下一個壓縮的初始哈希值。?

9、final.rb

?最終將8個32位的寄存器值轉化為8個16進制的哈希值并拼接在一起，最終得到message的哈希值

?

使用哈希計算器驗證一下是沒問題的

10、sha256.rb?

# 直接進行哈希運算
ruby sha256.rb abc# 也可以輸出二進制和十六進制數據
ruby sha256.rb 0b01100001
ruby sha256.rb 0xaabbccdd# 哈希一個文件 (請注意，文件末尾將有一個換行符)
ruby sha256.rb file.txt# 添加不同的命令行參數
ruby sha256.rb abc normal # 默認
ruby sha256.rb abc fast   # 加速演示
ruby sha256.rb abc enter  # 每按一次回車，步進一次動畫

sha256.rb是一個集成上述功能的完整代碼，除此之外，還可以指定命令行參數實現不同操作。

將sha-256.rd的輸出改成可分為多個block的長message，測試多個block條件下hash算法?

觀察以上代碼運行后的結果發現，進行了多個block的流水線運算，最終的結果正確，真是太吊了。但是這里注意改變輸入時不能直接在命令行輸入段落，因為作者的代碼中不能識別空格，所以只能在rb文件里改變input，但是也無傷大雅，筆者有時間會完善一下這個小bug的。