雜湊摘要演算法
最近在看一些NPM庫的時候總是看到各種雜湊簽名演算法,之前工作中也有用到過簽名演算法,但並沒有深入理解過其中的原理,於是找了點資料稍微瞭解了一下,總結了這篇文章。
雜湊摘要演算法
雜湊函式(也稱雜湊函式),是一種根據任意長度資料計算出固定簽名長度的演算法,比如MD5,SHA系列。
雜湊簽名摘要演算法特點
- 不是加密演算法,而是一種摘要演算法
- 不可逆,“單向”函式
- 簽名長度固定
- 存在2的N次方種結果,N表示簽名長度
以MD5為例
MD5是由美國密碼學家羅納德·李維斯特(Ronald Linn Rivest)設計一種加密演算法。
- 128個bits長度,也就是16個位元組
- 輸出結果由為“0-F”字元組成,不區分大小寫
- 存在2的128次方種輸出結果
MD5演算法
一、源資料處理
計算原文長度(bits)對512求餘的結果,需要填充原文使得原文對512求餘的結果等於448, 填充的方法是第一位填充1,其餘位填充0。填充完後,資訊的長度為512 * N + 448。
剩餘64bits儲存空間用來填充源資訊長度,填充在448byte 資料之後。
最終經過處理後的資料長度為 512 * N。
動手畫了一張簡單的圖來說明:
)
二、處理資料
1、資料進行處理前,會定義4個常量,作為初始值
這4個常量分別是
var a = 0x67452301; var b = 0xEFCDAB89; var c = 0x98BADCFE; var d = 0x10325476;
翻譯成二進位制就是
var a =1732584193; var b = -271733879; var c = -1732584194; var d =271733878;
2、將處理後的資料,外迴圈處理N次,N為第一步中512的整數倍。
每次外迴圈處理的會產生新的“a、b、c、d”值,每次新產生的“a、b、c、d”值會再一次提供給下一次外迴圈使用
3、在每個外迴圈中又進行內迴圈處理64次,在這64次資料處理中會不停的將 512 bytes 資料中的 16個小單元不停的通過4個函式進行交叉處理,共計進行64輪計算。
4、最終生成新的“a、b、c、d”,新的“a、b、c、d”分別是佔用32bytes的資料
5、最終生成的“a、b、c、d”轉換為對應的ascll佔用的位元組,32 bytes * 4 = 128 bytes, 一個位元組佔用8個bytes, 也就是16個位元組,16個位元組轉換為ASCII碼,再將ASCII碼轉換為16進位制資料,即可得到一個32個位元組長度的hash值。
內外迴圈程式碼
function binl_md5(x, len) { /* append padding */ x[len >> 5] = x[len >> 5] | 0x80 << (len % 32); x[(((len + 64) >>> 9) << 4) + 14] = len; var i, olda, oldb, oldc, oldd, a =1732584193, b = -271733879, c = -1732584194, d =271733878; // 每次計算位移值,可以理解為是常量 var ffShift = [7, 12, 17, 22,7, 12, 17, 22,7, 12, 17, 22,7, 12, 17, 22]; var ggShift = [5,9, 14, 20,5,9, 14, 20,5,9, 14, 20,5,9, 14, 20]; var hhShift = [4, 11, 16, 23,4, 11, 16, 23,4, 11, 16, 23,4, 11, 16, 23]; var iiShift = [6, 10, 15, 21,6, 10, 15, 21,6, 10, 15, 21,6, 10, 15, 21]; // Todo: 四個位元組一組,每個組別之間不停的交叉計算,不停的根據已計算出來的值多次計算賦值 // x[i]裝的是4個位元組的資料 // x.length 為 512 * N / 32 // i += 16 每512bits長度的資料分為了16組,而每次迴圈的計算單位是以512為一個單元的,所以每次都是+16 for (i = 0; i < x.length; i += 16) { olda = a; oldb = b; oldc = c; oldd = d; // 64輪計算中包含原始“a、b、c、d”值。 // 以及位移值,以及一個計算常量,這兩個是MD5規範中所定義的常量 a = md5_ff(a, b, c, d, x[i],ffShift[0], -680876936); d = md5_ff(d, a, b, c, x[i +1], ffShift[1], -389564586); c = md5_ff(c, d, a, b, x[i +2], ffShift[2],606105819); b = md5_ff(b, c, d, a, x[i +3], ffShift[3], -1044525330); a = md5_ff(a, b, c, d, x[i +4], ffShift[4], -176418897); d = md5_ff(d, a, b, c, x[i +5], ffShift[5],1200080426); c = md5_ff(c, d, a, b, x[i +6], ffShift[6], -1473231341); b = md5_ff(b, c, d, a, x[i +7], ffShift[7], -45705983); a = md5_ff(a, b, c, d, x[i +8], ffShift[8],1770035416); d = md5_ff(d, a, b, c, x[i +9], ffShift[9], -1958414417); c = md5_ff(c, d, a, b, x[i + 10], ffShift[10], -42063); b = md5_ff(b, c, d, a, x[i + 11], ffShift[11], -1990404162); a = md5_ff(a, b, c, d, x[i + 12], ffShift[12],1804603682); d = md5_ff(d, a, b, c, x[i + 13], ffShift[13], -40341101); c = md5_ff(c, d, a, b, x[i + 14], ffShift[14], -1502002290); b = md5_ff(b, c, d, a, x[i + 15], ffShift[15],1236535329); a = md5_gg(a, b, c, d, x[i +1], ggShift[0], -165796510); d = md5_gg(d, a, b, c, x[i +6], ggShift[1], -1069501632); c = md5_gg(c, d, a, b, x[i + 11], ggShift[2],643717713); b = md5_gg(b, c, d, a, x[i],ggShift[3], -373897302); a = md5_gg(a, b, c, d, x[i +5], ggShift[4], -701558691); d = md5_gg(d, a, b, c, x[i + 10], ggShift[5],38016083); c = md5_gg(c, d, a, b, x[i + 15], ggShift[6], -660478335); b = md5_gg(b, c, d, a, x[i +4], ggShift[7], -405537848); a = md5_gg(a, b, c, d, x[i +9], ggShift[8],568446438); d = md5_gg(d, a, b, c, x[i + 14], ggShift[9], -1019803690); c = md5_gg(c, d, a, b, x[i +3], ggShift[10], -187363961); b = md5_gg(b, c, d, a, x[i +8], ggShift[11],1163531501); a = md5_gg(a, b, c, d, x[i + 13], ggShift[12], -1444681467); d = md5_gg(d, a, b, c, x[i +2], ggShift[13], -51403784); c = md5_gg(c, d, a, b, x[i +7], ggShift[14],1735328473); b = md5_gg(b, c, d, a, x[i + 12], ggShift[15], -1926607734); a = md5_hh(a, b, c, d, x[i +5], hhShift[0], -378558); d = md5_hh(d, a, b, c, x[i +8], hhShift[1], -2022574463); c = md5_hh(c, d, a, b, x[i + 11], hhShift[2],1839030562); b = md5_hh(b, c, d, a, x[i + 14], hhShift[3], -35309556); a = md5_hh(a, b, c, d, x[i +1], hhShift[4], -1530992060); d = md5_hh(d, a, b, c, x[i +4], hhShift[5],1272893353); c = md5_hh(c, d, a, b, x[i +7], hhShift[6], -155497632); b = md5_hh(b, c, d, a, x[i + 10], hhShift[7], -1094730640); a = md5_hh(a, b, c, d, x[i + 13], hhShift[8],681279174); d = md5_hh(d, a, b, c, x[i],hhShift[9], -358537222); c = md5_hh(c, d, a, b, x[i +3], hhShift[10], -722521979); b = md5_hh(b, c, d, a, x[i +6], hhShift[11],76029189); a = md5_hh(a, b, c, d, x[i +9], hhShift[12], -640364487); d = md5_hh(d, a, b, c, x[i + 12], hhShift[13], -421815835); c = md5_hh(c, d, a, b, x[i + 15], hhShift[14],530742520); b = md5_hh(b, c, d, a, x[i +2], hhShift[15], -995338651); a = md5_ii(a, b, c, d, x[i],iiShift[0], -198630844); d = md5_ii(d, a, b, c, x[i +7], iiShift[1],1126891415); c = md5_ii(c, d, a, b, x[i + 14], iiShift[2], -1416354905); b = md5_ii(b, c, d, a, x[i +5], iiShift[3], -57434055); a = md5_ii(a, b, c, d, x[i + 12], iiShift[4],1700485571); d = md5_ii(d, a, b, c, x[i +3], iiShift[5], -1894986606); c = md5_ii(c, d, a, b, x[i + 10], iiShift[6], -1051523); b = md5_ii(b, c, d, a, x[i +1], iiShift[7], -2054922799); a = md5_ii(a, b, c, d, x[i +8], iiShift[8],1873313359); d = md5_ii(d, a, b, c, x[i + 15], iiShift[9], -30611744); c = md5_ii(c, d, a, b, x[i +6], iiShift[10], -1560198380); b = md5_ii(b, c, d, a, x[i + 13], iiShift[11],1309151649); a = md5_ii(a, b, c, d, x[i +4], iiShift[12], -145523070); d = md5_ii(d, a, b, c, x[i + 11], iiShift[13], -1120210379); c = md5_ii(c, d, a, b, x[i +2], iiShift[14],718787259); b = md5_ii(b, c, d, a, x[i +9], iiShift[15], -343485551); a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); } // 最終生成4個佔用32 bytes控制的值 return [a, b, c, d]; }
四輪計算線性函式
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))
6、第五點可以解釋為什麼生成的hash值中只會包含“0-F”,且不區分大小寫的原因,長度為16。
function rstr2hex(input) { var hex_tab = '0123456789abcdef', output = '', x, i; for (i = 0; i < input.length; i += 1) { x = input.charCodeAt(i); output += hex_tab.charAt((x >>> 4) & 0x0F) + hex_tab.charAt(x & 0x0F); x:${input.charCodeAt(i)}, output: ${output}`); } return output; }
以上程式碼來自https://github.com/blueimp/JavaScript-MD5 ,稍有改動。
適用場景:
- 私密資料加密,比如使用者密碼一般都不會明文儲存,而是通過加密後存入資料庫
- 賭場開盤前將開票結果公佈,開盤後通過簽名對比校驗是否存在作弊行為
- 檢測檔案是否下載完成,比如迅雷下載
如何破解
MD5中,雖然由源文可以推匯出簽名,反過來,並不能由簽名推匯出源文。但MD5並不是堅不可摧,目前有兩種破解方式
- 碰撞法,雖然MD5簽名存在2的128次方種輸出結果,但每個簽名對應的原文並不是唯一的,只要計算機效能夠強大,給予充足的時間,總能找到能輸出相同簽名的資料來源。
- 對映法,把常規字串對應的簽名儲存,比如常用的“123456”,“abcdefg”等。當得到MD5簽名時,就可以映射出源資料。
如何防範:
- 使用安全性更高的SHA256,並不是說SHA256不能被破解,只是相對於MD5來說演算法步驟更多,也更復雜,破解難度更大。
- 源資料 + KEY,比如“123456”加上KEY就變成了“123456@#DFF23DS”,其中“@#DFF23DS”就是服務端儲存的KEY。“源資料 + KEY” => 簽名。
- 源資料 + KEY + 動態資料,KEY有可能會被猜到,如果再加上動態資料的話,破解難度會進一步提升,比如使用者名稱、動態密碼。“源資料 + KEY + 動態密碼” => 簽名。
- 多次MD5,MD5(“123456”)很容易被猜到,MD5(MD5(“123456”)),將MD5後的簽名再進行一次MD5呢,如果進行三次,十次,是不是破解的難度會更大,當然這麼做會增加計算時間,需要權衡。
其他:
- 中文編碼需要轉碼,否則前端與後端編碼後的值可能不一致。
- 除了MD5演算法,還存在很多其他形式的雜湊函式演算法,比如SHA系列,他們的設計思路大體相同。