SHA-1 算法在FPGA上的實現 - 1

背景介紹

散列函數（英語：Hash function）又稱散列算法、哈希函數，是一種從任何一種數據中創建小的數字“指紋”的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。散列值通常用一個短的隨機字母和數字組成的字符串來代表。SHA-1 (全稱：Secure Hash Algorithm - 1，安全散列算法-1）是一種密碼散列函數，是由美國國家安全局設計。SHA-1可以使一個不固定長度的消息生成160位的消息摘要，用于驗證消息在傳輸的過程中沒有被攻擊或者篡改。2005年，密碼分析人員發現了對SHA-1的有效攻擊方法，2020年后，針對SHA-1的選擇前綴攻擊已經證明實際可行，建議盡可能使用SHA-2或者SHA-3取代SHA-1。在這里介紹SHA-1算法是因為其對SHA家族算法有代表性，其余算法與SHA-1差別不大。

應用場景舉例

SHA-1作為安全散列算法家族的一員，主要作用是用于驗證消息在傳遞的過程中是否被篡改，是被視作驗證碼。初學者在學習的過程中，經常會將Hash函數與密文、密鑰、加密等概念混淆。需要值得注意的是，Hash算法并不能夠加密消息或者掩蓋消息的真實樣貌，技術人員或者學者使用SHA家族算法，只是為了通過移位、異或、交換寄存器內數值、使用消息參與計算的方式，將不固定長度的消息轉化為固定長度的消息摘要，用于驗證消息的完整性以及可靠性，確認其在傳輸的過程中沒有被修改。于此同時這個消息的計算過程也是不可逆的，因此可以保證了消息的不泄露。

SHA-1算法，在實際生活中的應用場景如下：
1.密碼驗證：服務器端存儲用戶密碼加密后的內容，每次密碼校驗比較的是密文是否相同，確保服務器管理員也無法獲取到用戶使用的密碼。
2.文件的完整性比較：當下載一個文件時，服務器返回的信息中包括這個文件的MD5（或者SHA1），在本地下載完畢將其進行MD5加密，之后比較兩個MD5只進行比較，如果一直則說明文件完整不存在丟包現象。
3.文件上傳：在上傳文件信息的時候，將該文件的MD5同時上傳給服務器。服務器中存儲了這個文件MD5（或者SHA1)，并存儲這個MD5只對應的已上傳的字節長度，比如未上傳為0，已完成為-1，已上傳200自己，則值為200。可以用于匹配該文件在服務器中的狀態，方便斷點再傳。只要源文件沒有改，就算文件改了名字，換個賬戶都可以在服務器中找到對應的文件，避免存儲多份相同文件，并可以提高二次上傳時的速度。

SHA-1的計算流程

以上所示的流程圖是SHA-1算法實現的流程圖。我把它分為了四部分：
第一部分：哈希初始值的輸入；
第二部分：消息塊的填充，分塊；
第三部分：哈希運算；
第四部分：將最后所得的哈希值與哈希初始值相加，得到最終哈希值。

一.哈希初始值輸入 (Initial Value Input)：

SHA-1算法的特點之一就是將不固定長度的消息塊轉化為固定長度的驗證碼，實現這一特點的過程其實就是將5個哈希初始值通過移位、相加、交換位置的方式得到最終的5個散列值。在這個過程中等待處理的消息將參與哈希值的計算，最后得到所需的哈希值進行驗證。
哈希初始值一般為：
Initial variables:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0
哈希初始值也可以根據需要自行更改。

二.消息塊的填充和分塊(Message Padding)：

每條輸入消息的長度不固定，但每一次輸入的消息被分塊為512位（16個字）作為一組進行處理。很多情況下，消息長度并不是512的整數倍,這時候就要對原始消息進行補填充。假設消息的長度M為L位。將“ 1”附加到消息末尾，后跟k個零位，其中k是方程的最小非負解L+1 + k” 448mod 512。然后附加用二進制表示形式等于的數字L的64位的消息塊。例如，（8位ASCII）消息“ abc”的長度8·3 = 24，用"1"填充消息一位，然后填充448-（24 +1）= 423個零位，然后消息長度，成為512位填充消息。效果如圖所示。

整個過程可以詳細分解為以下兩步：
1.補位
原始消息必須進行補位，以使其長度在對512取模以后的余數是448。也就是說，（補位后的消息長度）%512 = 448。即使長度已經滿足對512取模后余數是448，補位也必須要進行。
補位是這樣進行的：先補一個1，然后再補0 ，直到長度滿足對512取模后余數是448。總而言之，補位是至少補一位，最多補512位。
2.補長度
就是將原始數據的長度補到已經進行了補位操作的消息后面。通常用兩個字（64位）來表示原始消息的長度。如果消息長度不大于2^64，那么第一個字就是0。

三. 哈希運算(Hash Function)：

SHA-1算法運算從初始值開始到最終所得哈希值，會進行80輪運算。上圖所示的是每一輪運算的具體操作。

SHA-1 Function

SHA-1使用一系列邏輯函數進行計算，一共計算80輪，分別為f0，f1，…，f79。每個函數ft，其中 ft <79，舉個例子，當對三個32位字x，y和z進行運算，并產生一個32位字作為輸出。 ft功能（x，y，z）定義如下：

SHA-1 Processing

SHA-1哈希計算使用先前定義的函數和常量進行計算，（+）指的是模 2³²。
第1輪到第80輪，每一輪都要按順序用一個32位的消息參與運算，消息本身有512位，也就是16個字。剩余的輪數，通過特殊的算法，將消息擴展為32*80位。算法如下：

具體每一輪的計算方法，如下圖所示：

圖中的ROTLⁿ(x)為下圖所示：

四. 最終哈希值計算

最終哈希值計算為下圖所示：

五個初始值與80輪計算后所得哈希值一同計算，所得的值就是我們需要的散列值。

總結

在SHA-1的FPGA實現（1）中，我介紹了SHA-1的歷史和作用，并詳細的描述了SHA-1算法的運算過程，在下一篇中，我將開始介紹如何將SHA-1算法在FPGA上實現，以及需要注意的事項。

參考資料

[1] SECURE HASH STANDARD https://csrc.nist.gov/csrc/media/publications/fips/180/2/archive/2002-08-01/documents/fips180-2.pdf

總結

以上是生活随笔為你收集整理的硬件安全 (1) —— SHA-1算法在FPGA上的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。