雜湊 - SHA家族（二）

我們接下來就把完全不同的SHA3講完吧。

這部份其實難度也還好，而且發布的標準文檔也寫得很清楚就是了。

但還是很有趣的，我們就一步一步來看吧。

SHA3

我們還是搭配論文一起來分析。

SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

接下來我們所使用的圖片都是來自2015年所發布的，SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions 文檔，在此標記。

我接下來不會以論文的順序（你們應該都知道吧，其實我都不是以論文的順序在寫）。

論文中的程式是先準備完所有的Function，才開始處理其他的。

那我們照著資料處理流程來寫。

資料分塊

這邊要先把資料作分塊。

SHA3 是以5*5的資料塊陣列下去做的。

假設資料為S，並把資料排成一列從0開始到資料長度n。

則資料有S[0]～S[n-1]。

w為資料每一個資料塊的長度，w的總量是會變動的，w的計算為b/25。

而b是由25、50、100、200、400、800、1600挑出來的。

也就是說SHA3最多25塊資料塊，每塊的資料則是變動的，由上述數值決定。

因此可以做成一個3維的樣子，以公式寫成：

A[x,y,z] = S[w*(5y+x)+z]

x跟y表示資料塊因此：x<=5、y<=5。
z則是：z<=w-1。

我們可以看一下圖一跟圖二，這樣比較清楚：

圖一

圖二

海綿函數

資料因為有可能很長很長，因此必須使用海綿函式。

海綿函式將會使資料變成固定的長度。

我們看一下圖三

圖三

這就是海綿函式的整個流程，輸出固定長度。

好，我們先來看一下SHA3的海綿函式的流程圖（圖四）。

圖四

這邊說一下代號：

• N：資料。
• r：處理資料的速率。
• b：b其實是f回傳的資料長度。
• f：表示處理資料的方程式，會回傳固定長度（這是晚點要說的SHA3的核心）。

還有一個很重要的東西「pad」，我們先介紹它：

Pad

一樣先看流程，圖五：

圖五

照著公式做，第二個步驟其實是：'1' 串連 j個'0' 再串連 '1'。

海綿函數（續）

我們繼續接著講『海綿函數』回去看『圖四』。

1. P的生成其實也就是圖四，資料串接Pad資料。
2. n就是P的長度除速率（r）。
3. c就是f回傳的資料長度（b）減掉速率（r）。
4. 這邊在說把P分成長度為r，共n-1塊。
5. 初始化S，S的空間長度為f回傳的資料長度（b），全部填'0'。
6. 從0到n-1，把『S XOR （P串接c的'0'）』丟入f函數中，不斷地更新S。
7. 創建一個空的Z字串。
8. 取S最右邊的r筆資料，串接在Z的後面。
9. 當Z大於d的話，輸出Z最右邊的d筆資料。
10. 再把S丟入f函數，回到第8步驟。

我們這樣就把『資料』變成了『SHA3 Hash』了。

那我們的核心是在『f』身上。

那我們來說說f。

KECCAK-f

上面的f函數就是SHA3的KECCAK-f。

其實KECCAK-f 是從 KECCAK-p[b, 12+2l]來的。

那b跟l是什麼，一樣看圖六：

圖六

b為想要處理的資料長度，而這個可以從25、50、100、200、400、800、1600挑出來，由開發者決定。

再看圖六，從選定的b選擇l。

那我們要看KECCAK-p了。

KECCAK-p

我們先看圖七。

圖七

1. S就是資料，A就是最前面介紹的塊。
2. nr就是12+2l，剛剛看面說了。
   我們從nr-nr＝0到nr-1，把A跟做到的回數輸入到Red函數裡，然後不斷的覆蓋A。
3. 接著就把A的塊還原成S資料。
4. 把S回傳出去。

那我們看到了一個Red的函數，那Red函數是什麼？看圖八。

圖八

看來有5個函數，θ、ρ、π、χ、ι。

那就表示我們必須把資料塊A放入5個函數裡做計算。

我們一個一個介紹，我們由內向外介紹。

函數θ

我們先看流程，圖九：

圖九

1. 把一列的資料做圖上的XOR公式，存成C。
2. 把C的資料再做圖上的XOR，存成D。
3. 最後把每一塊的資料跟D做XOR。

公式化應該不難。

這邊有演示圖（圖十）：

圖十

函數ρ

我們先看流程，圖十一：

圖十一

1. 其實就是第一塊不變。
2. 從第二塊開始做。
3. 把每一塊的『資料』做位移，再把每一塊做位移，做24次，資料的位移程度會跟著次數改變位移的程度。
4. 回傳跑完的資料。

這邊的公式化也不難吧。

這邊有演示（圖十二）：

圖十二

函數π

我們先看流程，圖十三：

圖十三

1. 這邊就是做所有的x、y、z，並把z當成轉軸，交換x、y的資料。
2. 把資料回傳。

這邊也簡單，但很有意思。

這邊有演示（圖十四）：

圖十四

函數χ

我們先看流程，圖十五：

圖十五

1. 把每一列裡面做AND跟XOR來混淆資料。
2. 回傳資料。

這邊看演示圖才比較清楚在做什麼，請往下看。

這邊有演示（圖十六）：

圖十六

函數ι

我們先看流程，圖十七：

圖十七

1. 這邊跟你說不會變動任何的位置。
2. 做一個RC填w個'0'。（w是b/25，上面也有表能查。）
3. 從0到l，每一回（j）+7*ir做rc的函數，並覆蓋RC的第2^j-1。
4. 再來把第0塊的資料跟RC做XOR。
5. 回傳資料。

這邊有一個rc函數請看下面：

我們看rc流程，圖十八：

圖十八

1. 傳進來的數字t跟255做模運算後，要是等於0，直接回傳1。
2. 設一個R為'10000000'。
3. 從1到『傳進來的數字t跟255做模運算』，把每一塊的R最圖上的動作。
   • 最後一個Trunc8的意思是，取最左邊的8位。
4. 回傳R[0]。

SHA 輸出

如圖十九：

圖十九

這邊的448、512、768、1024是c，c就是f回傳的資料長度（b）減掉速率（r）。
用這邊的c並選定b之後就能回推r了，這樣就能做『海綿函數』了。
然後()裡面的是，資料串接一個01與要的長度d。

那圖二十，這邊是可以自由選擇出長度的。

圖二十

這邊的128跟256是c就是f回傳的資料長度（b）減掉速率（r），也就是說固定了r，也就是固定速度。

SHA3 結論

終於……我們把SHA3講完了。

SHA3的文檔雖然寫得很完整了，但因為它的流程是先準備好要用的Function。

讀起來有點累，同時除了SHA3的文檔，有些部分還要參考一下虛擬碼。

但有了這樣的介紹，應該大家也能把程式寫出來吧～

那麼，明天開始就來說說下一個特別的Hash，CRC的部分。

這個Hash是作快速的校驗跟修復用的。

而且簡單的CRC原理其實很簡單的。

那就留到明天來說吧～大家明天見～

參考資料

SHA-3

SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

Keccak specifications summary