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演算法流程圖
以上所示的流程圖是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計算具體程序
SHA-1演算法運算從初始值開始到最終所得哈希值，會進行80輪運算，上圖所示的是每一輪運算的具體操作，

SHA-1 Function

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

SHA-1 Processing

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