可搜索加密技術 – 學習筆記（二）- 預備知識：HMAC-SHA256函數
由於在之後的算法中會用到HMAC-SHA256函數，這裡先簡單對其進行一個介紹。
一、HMAC算法
- 什麼是HMAC算法？
HMAC是密鑰相關的哈希運算消息認證碼（Hash-based Message Authentication Code）的縮寫，由H.Krawezyk，M.Bellare，R.Canetti於1996年提出的一種基於Hash函數和密鑰進行消息認證的方法，並於1997年作為RFC2104被公布，並在IPSec和其他網絡協議（如SSL）中得以廣泛應用，現在已經成為事實上的Internet安全標準。它可以與任何迭代散列函數捆綁使用。[3]
簡單地說就是：HMAC是一種使用單向散列函數來構造消息認證碼的算法。
HMAC算法利用哈希運算，以一個密鑰和一個消息為輸入，生成一個消息摘要作為輸出。其安全性是建立在Hash加密算法基礎上的。它要求通信雙方共享密鑰、約定算法、對報文進行Hash運算，形成固定長度的認證碼。通信雙方通過認證碼的校驗來確定報文的合法性。HMAC算法可以用來作加密、數字簽名、報文驗證等[2]。HMAC使用的Hahs函數並不僅限於一種，任何高強度的單向散列函數都可以被用於HMAC，如果將來設計出的新的單向散列函數，也同樣可以使用。使用SHA-1、SHA-224、SHA-256、SHA-384、SHA-512所構造的HMAC，分別稱為HMAC-SHA1、HMAC-SHA-224、HMAC-SHA-256、HMAC-SHA-384、HMAC-SHA-512[1]。其中HMAC-SHA256就是接下來要重點介紹的。
定義1 HMAC算法
HMAC算法的數學公式為：
HMAC ( k , m ) = H ( k』 ⊕ opad , H ( k』 ⊕ ipad, m ) )
其中：
H 為密碼Hash函數（如MD5或SHA-2），能夠對明文進行分組循環壓縮；
k 為密鑰（secret key）；
m 為要認證的消息；
k』 是從原始密鑰 k 導出的另一個密鑰（如果 k 短於散列函數的輸入塊大小，則向右填充零；如果比該塊大小更長，則對 k 進行散列）
ipad 內部填充（0x5C5C5C…5C5C，一段十六進制常量）；
opad 外部填充（0x363636…3636，一段十六進制常量）。
1.1 HMAC的計算步驟
HMAC計算步驟如下圖所示：
① 密鑰處理
如果密鑰比單向散列函數分組長度要短，就需要在末尾填充0，直到其長度達到單向散列函數的分組長度為止。
如果密鑰比分組長度要長，則要用單向散列函數求出密鑰的散列值，然後將這個散列值用作HMAC的密鑰。
② 處理後的密鑰與ipad進行XOR
將處理後的密鑰與被稱為ipad的比特序列進行XOR運算。ipad是將00110110這一比特序列不斷循環反覆直到達到分組長度所形成的比特序列，其中ipad的i是inner的意思。
XOR運算所得到的值，是一個和單向散列函數的分組長度相同，且和密鑰相關的比特序列。這裡將這個比特序列稱為ipadkey。
③ 與消息組合
隨後，將ipadkey與消息組合，也就是將和密鑰相關的比特序列（ipadkey）附加在消息的開頭。
④ 計算散列值
將步驟③的結果作為單向散列函數的輸入，並計算出散列值。
⑤ 處理後的密鑰與opad進行XOR
將填充後的密鑰與被稱為opad的比特序列進行XOR運算，opad是將01011100這一比特序列不斷循環反覆直到達到分組長度所形成的比特序列，其中opad的o是outer的意思。
XOR運算所得到的結果也是一個和單向散列函數的分組長度相同，且和密鑰相關的比特序列。這裡將這個比特序列稱為opadkey。
⑥ 與散列值組合
將步驟④的結果拼在opadkey的後面。
⑦ 計算散列值
將步驟⑥的結果輸入單向散列函數，並計算出散列值，這個散列值就是最終的MAC值。
通過上述流程可以看出，最後得到的MAC值，一定是一個和輸入的消息以及密鑰都相關的長度固定的比特序列。
二、SHA-256算法
- 什麼是SHA-256算法？
散列函數它被認為是一種單向函數——根據函數輸出的結果，極難回推輸入的數據。散列函數把消息數據打亂混合，壓縮成散列值（摘要），使得數據量變小。
SHA-256由美國國家安全局研發，是SHA-2下細分出的一種算法，屬於SHA算法之一，是SHA-1的後繼者。SHA-256（Secure Hash Algorithm 256，安全散列算法256）是散列函數（或哈希函數）的一種，對於任意長度的消息，SHA256都會產生一個256-bit（32-byte數組）的哈希值，稱作消息摘要。。摘要通常用一個長度為64位的十六進制字符串來表示。當接收到消息的時候，這個消息摘要可以用來驗證數據是否發生改變，即驗證其完整性。[2]
2.1 SHA-256的算法描述
首先進行信息預處理，如下圖所示，將原始消息分成若干個512-bit大小的消息塊。最後一個消息塊需要進行信息補全，並附上原消息的長度信息。消息被分成n塊後，需要進行n次迭代，最後一次的結果就是最終的哈希值，即256bit的數字摘要。
SHA256算法的最小運算單元為「字」（word, 32-bit）。下圖的256-bit的中間狀態Hi被描述為8個字。512-bit的消息塊Mi將由16個字擴展為64個字，並與Hi混合，壓縮成新的散列值Hi+1。第i塊數據經Map函數映射的結果，將作為第i+1塊的輸入，即Map(H_(i-1))=H_i。H0是預設好的hash初值（自然數中前8個質數的平方根的小數部分，取前32-bit），依次對數據進行Hash映射，得到的最後一個狀態Hn便是最終的數字摘要。
而其中最關鍵的操作為映射函數Map，其內部相當於是一個循環加密的過程，不斷將原始信息進行打亂。
2.2 SHA-256的算法步驟
下面兩個表列出了SHA256散列函數中涉及到的所有邏輯運算，運算均是按位進行的。
設原始消息為M，原始消息長度LM，消息塊Mi，哈希初值H0，SHA-256常量K[0]~K[63]（自然數中前64個質數的立方根的小數部分，取前32-bit）。則SHA-256算法的加密步驟具體如下：
① 消息（M）預處理
在消息末尾進行添加一位「1」和t位「0」，使得：
(L_M+t+1) mod 512=448,0≤t<512
將LM表示為64位大端存儲格式，並添加到M末尾，組成新的消息M^』；
② 分解
將M^’按照每塊512-bit大小分解為Mi；
③ 拓展Mi到64字：W[0]~W[63]
將Mi分解為16個32-bit的大端存儲的字（word），存為W[0], …, W[15]，其餘字由以下公式得到：
W_t=σ_1 (W_(t-2))+W_(t-7)+σ_0 (W_(t-15))+W_(t-16)
④ 迭代
進行64次加密循環即可完成一次迭代。加密過程如圖4所示：ABCDEFGH這8個字最開始分別是8個哈希初值，之後按照圖示規則進行更新；深藍色方塊是事先定義好的非線性邏輯函數；紅色方塊代表加法（若結果大於232，則進行一次mod 232運算）；Kt為SHA-256常量，Wt為本區塊產生第t個word，0≤t<64；最後一次循環所產生的八段字符串合起來即是此區塊對應到的散列字符串；
⑤ 若原消息包含數個區塊，則最後還要將這些區塊產生的散列字符串加入迭代才能產生最後的散列字符串。
三、HMAC-SHA256算法
3.1 HMAC-SHA256的算法描述
HMAC-SHA256算法，即使用SHA-256生成哈希值的HMAC算法。依據HMAC算法和SHA-256算法內容，可知HMAC-SHA256算法的明文分組長度B為512-bit，可通過任意長度密鑰K（最小推薦長度為256-bit，一般應大於B），得出長度為256-bit散列值（摘要）。定義為：
〖HMAC〗_SHA256 (k,m)= SHA256(k』⊕opad∥SHA256(k』⊕ipad∥m))
其中：
SHA256 為SHA-256加密算法，其輸出散列值長度256-bit；
|| 拼接操作，將兩個字符串拼接在一起；
B Hash函數明文分組長度，SHA-256算法中為512-bit；
k 為密鑰（secret key）；
m 為要認證的消息；
k』 是從原始密鑰 k 導出的另一個密鑰（若 k 短於B，則向右填充零，直到與B相同；若k長於B，則對 k 進行一次SHA256散列計算）
ipad 內部填充（0x5C5C5C…5C5C，512-bit常量）；
opad 外部填充（0x363636…3636，512-bit常量）。
3.2 HMAC-SHA256的算法步驟
HMAC-SHA256計算步驟如下圖所示：
① 密鑰處理
如果密鑰比SHA-256分組長度(512-bit)要短，就需要在末尾填充0，直到其長度達到單向散列函數的分組長度為止。
如果密鑰比SHA-256分組長度(512-bit)要長，則要用SHA-256算法求出密鑰的散列值，然後將這個散列值用作HMAC的密鑰。
② 處理後的密鑰與ipad進行XOR
將處理後的密鑰與被稱為ipad的比特序列進行XOR運算。ipad是將00110110這一比特序列不斷循環反覆直到達到SHA-256分組長度(512-bit)所形成的比特序列，其中ipad的i是inner的意思。
XOR運算所得到的值，是一個和SHA-256分組長度(512-bit)相同，且和密鑰相關的比特序列。這裡將這個比特序列稱為ipadkey。
③ 與消息組合
隨後，將ipadkey與消息組合，也就是將和密鑰相關的比特序列（ipadkey）附加在消息的開頭。
④ 計算散列值
將步驟③的結果作為SHA-256函數的輸入，並計算出散列值。
⑤ 處理後的密鑰與opad進行XOR
將填充後的密鑰與被稱為opad的比特序列進行XOR運算，opad是將01011100這一比特序列不斷循環反覆直到達到SHA-256分組長度(512-bit)所形成的比特序列，其中opad的o是outer的意思。
XOR運算所得到的結果也是一個和SHA-256分組長度(512-bit)相同，且和密鑰相關的比特序列。這裡將這個比特序列稱為opadkey。
⑥ 與散列值組合
將步驟④的結果拼在opadkey的後面。
⑦ 計算散列值
將步驟⑥的結果輸入SHA-256函數，並計算出散列值，這個散列值就是最終的摘要內容。
通過上述流程可以看出，最後得到的摘要內容，一定是一個和輸入的消息以及密鑰都相關的長度固定的比特序列。
參考：
[2] 從零入門HMAC-SHA256
[3] HMAC百度百科
