哈希摘要算法

tain335 發布于2019-08-23 16:53 / 3389人閱讀

摘要：哈希摘要算法哈希函數也稱散列函數，是一種根據任意長度數據計算出固定簽名長度的算法，比如，系列。除了算法，還存在很多其他形式的哈希函數算法，比如系列，他們的設計思路大體相同。

前言

最近在看一些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系列，他們的設計思路大體相同。

參考資料

阮一峰講解操作符
按位移動操作符
各種進制在線轉換
維基百科MD5
維基百科SHA2
NPM MD5

云服務器 GPU云服務器消息摘要算法哈希算法最小哈希算法一致性哈希算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103457.html

當我們在談論前端加密時，我們在談些什么

摘要：所以我們今天只談前端加密，一個部分人認為沒有意義的工作。在中，認證過程使用了非對稱加密算法，非認證過程中使用了對稱加密算法。非對稱加密上文中我們討論了前端的哈希加密以及應用的場景。 showImg(https://segmentfault.com/img/bVAhTC); 當然在談安全。前端安全是Web安全的一部分，常見的安全問題會有XSS、CSRF、SQL注入等，然而這些已經在程師...

wizChen 2019-08-01 15:36 評論0 收藏0
python模塊之hashlib

摘要：使用算法名稱構造函數較使用更快所有平臺的模塊都支持的算法的名稱集合。的結果集總是結果集的子集對象的字節長度對象的內部塊大小對象的名稱傳遞類字節參數通常是更新對象。表示的哈希摘要算法的名稱，比如或。表示迭代次數，基于算法以及機器計算能力設置。 hashlib模塊實現了多種安全哈希和信息摘要算法的通用接口，包括FIPS中定義的SHA1, SHA224, SHA256, SHA384, SH...

luodongseu 2019-07-30 18:01 評論0 收藏0
區塊鏈學習之密碼學安全技術（五）

摘要：非對稱加密算法的安全性往往需要基于數學問題來保障，目前主要有基于大數質因子分解離散對數橢圓曲線等經典數學難題進行保護。消息認證碼基于對稱加密，可以用于對消息完整性進行保護。 Hash 算法與數字摘要 Hash （哈希或散列）算法它能將任意長度的二進制明文串映射為較短的（通常是固定長度的）二進制串（Hash值），并且不同的明文很難映射為相同的Hash值。 Hash 定義 Hash （哈希...

aboutU 2019-06-27 18:29 評論0 收藏0
區塊鏈記賬原理

摘要：本文首發于深入淺出區塊鏈社區原文鏈接區塊鏈記賬原理原文已更新，請讀者前往原文閱讀區塊鏈是一個基于密碼學安全的分布式賬本，是一個方便驗證，不可篡改的賬本。哈希函數在講區塊鏈記賬之前，先說明一下哈希函數。本文首發于深入淺出區塊鏈社區原文鏈接:區塊鏈記賬原理原文已更新，請讀者前往原文閱讀區塊鏈(1.0)是一個基于密碼學安全的分布式賬本，是一個方便驗證，不可篡改的賬本。通常認為與智能合約...

mumumu 2019-06-27 18:23 評論0 收藏0