哈希演算法與MD5、SHA

哈希演算法

哈希演算法(Hash Algorithm)又稱散列演算法、散列函數、哈希函數，是一種從任何一種數據中創建小的數字「指紋」的方法。哈希演算法將數據重新打亂混合，重新創建一個哈希值。

哈希演算法通常有以下幾個特點：

1. 正像快速：原始數據可以快速計算出哈希值
2. 逆向困難：通過哈希值基本不可能推導出原始數據
3. 輸入敏感：原始數據只要有一點變動，得到的哈希值差別很大
4. 衝突避免：很難找到不同的原始數據得到相同的哈希值

哈希演算法主要用來保障數據真實性(即完整性)，即發信人將原始消息和哈希值一起發送，收信人通過相同的哈希函數來校驗原始數據是否真實。

註：

1. 以上不能保證數據被惡意篡改，原始數據和哈希值都可能被惡意篡改，要保證不被篡改，可以使用RSA公鑰私鑰方案，再配合哈希值。
2. 哈希演算法主要用來防止計算機傳輸過程中的錯誤，早期計算機通過前7位數據第8位奇偶校驗碼來保障（12.5%的浪費效率低），對於一段數據或文件，通過哈希演算法生成128bit或者256bit的哈希值，如果校驗有問題要求重傳。

哈希演算法主要有MD4、MD5、SHA。

1. MD4 1990年 輸出128位 （已經不安全）
2. MD5 1991年 輸出128位 （已經不安全）
3. SHA-0 1993年 輸出160位 （發布之後很快就被NSA撤回，是SHA-1的前身）
4. SHA-1 1995年 輸出160位 （已經不安全）
5. SHA-2包括SHA-224、SHA-256、SHA-384，和 SHA-512，分別輸出224、256、384、512位。 (目前安全)

衝突避免：

• 2的128次方為340282366920938463463374607431768211456，也就是10的39次方級別
• 2的160次方為1.4615016373309029182036848327163e+48，也就是10的48次方級別
• 2的256次方為1.1579208923731619542357098500869 × 10的77次方，也就是10的77次方

宇宙中原子數大約在10的60次方到80次方之間，所以2的256次方有足夠的空間容納所有的可能，演算法好的情況下衝突碰撞的概率很低。

MD5

1、數據填充

對消息進行數據填充，使消息的長度對512取模得448，設消息長度為X，即滿足X mod 512=448。根據此公式得出需要填充的數據長度。

填充方法：在消息後面進行填充，填充第一位為1，其餘為0。

2、添加消息長度

在第一步結果之後再填充上原消息的長度，可用來進行的存儲長度為64位。如果消息長度大於264，則只使用其低64位的值，即（消息長度 對 264取模）。

在此步驟進行完畢後，最終消息長度就是512的整數倍。

3、數據處理

準備需要用到的數據：

4個常數： A = 0x67452301, B = 0x0EFCDAB89, C = 0x98BADCFE, D = 0x10325476; 4個函數：F(X,Y,Z)=(X & Y) | ((~X) & Z); G(X,Y,Z)=(X & Z) | (Y & (~Z)); H(X,Y,Z)=X ^ Y ^ Z; I(X,Y,Z)=Y ^ (X | (~Z)); 把消息分以512位為一分組進行處理，每一個分組進行4輪變換，以上面所說4個常數為起始變數進行計算，重新輸出4個變數，以這4個變數再進行下一分組的運算，如果已經是最後一個分組，則這4個變數為最後的結果，即MD5值。

代碼實現：MD5演算法C代碼實現

SHA-1

2017年2月23日，CWI Amsterdam與Google宣布了一個成功的SHA-1碰撞攻擊[12][13]，發布了兩份內容不同但SHA-1散列值相同的PDF文件作為概念證明。

1. 將512位的明文分組劃分為16個子明文分組，每個子明文分組為32位。
2. 申請5個32位的鏈接變數，記為A、B、C、D、E。
3. 16份子明文分組擴展為80份。
4. 80份子明文分組進行4輪運算。
5. 鏈接變數與初始鏈接變數進行求和運算。
6. 鏈接變數作為下一個明文分組的輸入重複進行以上操作。
7. 最後，5個鏈接變數裡面的數據就是SHA1摘要。

SHA1的分組過程

對於任意長度的明文，SHA1的明文分組過程與MD5相類似，首先需要對明文添加位數，使明文總長度為448（mod512）位。在明文後添加位的方法是第一個添加位是l，其餘都是0。然後將真正明文的長度（沒有添加位以前的明文長度）以64位表示，附加於前面已添加過位的明文後，此時的明文長度正好是512位的倍數。與MD5不同的是SHA1的原始報文長度不能超過2的64次方，另外SHA1的明文長度從低位開始填充。

經過添加位數處理的明文，其長度正好為512位的整數倍，然後按512位的長度進行分組（block），可以劃分成L份明文分組，我們用Y0，Y1，……YL-1表示這些明文分組。對於每一個明文分組，都要重複反覆的處理，這些與MD5是相同的。

對於512位的明文分組，SHA1將其再分成16份子明文分組（sub-block），每份子明文分組為32位，我們使用M[k]（k= 0, 1,……15）來表示這16份子明文分組。之後還要將這16份子明文分組擴充到80份子明文分組，我們記為W[k]（k= 0, 1,……79），擴充的方法如下。

W t = M t , 當0≤t≤15

W t = ( W t-3 ⊕ W t-8⊕ W t-14⊕ W t-16 ) ?< 1, 當16≤t≤79

SHA1有4輪運算，每一輪包括20個步驟（一共80步），最後產生160位摘要，這160位摘要存放在5個32位的鏈接變數中，分別標記為A、B、C、D、E。這5個鏈接變數的初始值以16進位位表示如下。

A=0x67452301

B=0xEFCDAB89

C=0x98BADCFE

D=0x10325476

E=0xC3D2E1F0

SHA1的4輪運算

SHA1有4輪運算，每一輪包括20個步驟，一共80步，當第1輪運算中的第1步驟開始處理時，A、B、C、D、E五個鏈接變數中的值先賦值到另外5個記錄單元A′，B′，C′，D′，E′中。這5個值將保留，用於在第4輪的最後一個步驟完成之後與鏈接變數A，B，C，D，E進行求和操作。

SHA1的4輪運算，共80個步驟使用同一個操作程序，如下：

A,B,C,D,E←[(A?<5)+ ft(B,C,D)+E+Wt+Kt],A,(B?<30),C,D

其中 ft(B,C,D)為邏輯函數，Wt為子明文分組W[t]，Kt為固定常數。這個操作程序的意義為：

● 將[(A?<5)+ ft(B,C,D)+E+Wt+Kt]的結果賦值給鏈接變數A；

● 將鏈接變數A初始值賦值給鏈接變數B；

● 將鏈接變數B初始值循環左移30位賦值給鏈接變數C；

● 將鏈接變數C初始值賦值給鏈接變數D；

● 將鏈接變數D初始值賦值給鏈接變數E。

代碼實現：SHA-1演算法C代碼實現

SHA-256

SHA-256 演算法輸入報文的最大長度不超過2^64 bit，輸入按512-bit 分組進行處理，產生的輸出是一個256-bit 的報文摘要。

1. 附加填充比特。對報文進行填充使報文長度與448 模512 同餘（長度=448 mod 512），填充的比特數範圍是1 到512，填充比特串的最高位為1，其餘位為0。就是先在報文後面加一個 1，再加很多個0，直到長度 滿足 mod 512=448.為什麼是448，因為448+64=512. 第二步會加上一個 64bit的 原始報文的 長度信息。
2. 附加長度值。將用64-bit 表示的初始報文（填充前）的位長度附加在步驟1 的結果後（低位位元組優先）。
3. 初始化緩存。使用一個256-bit 的緩存來存放該散列函數的中間及最終結果。該緩存表示為A=0x6A09E667 , B=0xBB67AE85 , C=0x3C6EF372 , D=0xA54FF53A, E=0x510E527F , F=0x9B05688C , G=0x1F83D9AB , H=0x5BE0CD19 。
4. 處理512-bit（16 個字）報文分組序列。該演算法使用了六種基本邏輯函數，由64 步迭代運算組成。每步都以256-bit 緩存值ABCDEFGH 為輸入，然後更新緩存內容。 每步使用一個32-bit 常數值Kt 和一個32-bit Wt。

1. 所有的512-bit分組處理完畢後，對於SHA-256演算法最後一個分組產生的輸出便是256-bit的報文摘要。

代碼實現：SHA-256演算法C代碼實現

參考

簡書：Hash演算法總結

維基百科：哈希函數散列函數

維基百科：MD5演算法

百度百科：MD5

CNBlogs: SHA1演算法原理

CSDN：SHA-256演算法實現