硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

基於數學難題的構造方法

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

MASH-1 (Modular Arithmetic Secure Hash) 是一個基於 RSA 算法的哈希算法,在 1995 年提出,入選國際標準 ISO/IEC 10118-4;MASH-2 是 MASH-1 的改進,把第四步中的 2 換成了 28+1;由於涉及模乘 / 平方運算,計算速度慢,非常不實用。

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

利用對稱密碼體制設計哈希函數

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

分組密碼的工作模式是:根據不同的數據格式和安全性要求, 以一個具體的分組密碼算法爲基礎構造一個分組密碼系統的方法。

基於分組的對稱密碼算法比如 DES/AES 算法只是描述如何根據祕鑰對一段固定長度 (分組塊) 的數據進行加密,對於比較長的數據,分組密碼工作模式描述瞭如何重複應用某種算法安全地轉換大於塊的數據量。

簡單的說就是,DES/AES 算法描述怎麼加密一個數據塊,分組密碼工作模式模式瞭如果重複加密比較長的多個數據塊。常見的分組密碼工作模式有五種:

  • 電碼本 ( Electronic Code Book,ECB) 模式

  • 密文分組鏈接 (Cipher Block Chaining,CBC) 模式

  • 密文反饋 (Cipher Feed Back ,CFB) 模式

  • 輸出反饋 (Output Feed Back ,OFB) 模式

  • 計數器 (Counter, CTR) 模式

ECB 工作模式

加密:輸入是當前明文分組。

解密:每一個密文分組分別解密。

具體公式爲:

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

ECB 工作模式示意圖

CBC 工作模式

加密:輸入是當前明文分組和前一次密文分組的異或。

解密:每一個密文分組被解密後,再與前一個密文分組異或得明文。

具體公式爲:

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

CBC 工作模式示意圖

CFB 工作模式

  • 加密算法的輸入是 64 比特移位寄存器,其初值爲某個初始向量 IV。

  • 加密算法輸出的最左 (最高有效位)j 比特與明文的第一個單元 P1 進行異或,產生出密文的第 1 個單元 C1,並傳送該單元。

  • 然後將移位寄存器的內容左移 j 位並將 C1 送入移位寄存器最右邊 (最低有效位)j 位。

  • 這一過程繼續到明文的所有單元都被加密爲止。

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

CFB 工作模式示意圖

OFB 工作模式

OFB 模式的結構類似於 CFB

不同之處:

  • OFB 模式是將加密算法的輸出反饋到移位寄存器

  • CFB 模式中是將密文單元反饋到移位寄存器

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

OFB 工作模式示意圖

CTR 工作模式

加密:輸入是當前明文分組和計數器密文分組的異或。

解密:每一個密文分組被解密後,再與計數器密文分組異或得明文。

具體公式爲:

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

CTR 工作模式示意圖

工作模式比較

  • ECB 模式,簡單、高速,但最弱、易受重發攻擊,一般不推薦。

  • CBC 模式適用於文件加密,比 ECB 模式慢,安全性加強。當有少量錯誤時,不會造成同步錯誤。

  • OFB 模式和 CFB 模式較 CBC 模式慢許多。每次迭代只有少數比特完成加密。若可以容忍少量錯誤擴展,則可換來恢復同步能力,此時用 CFB 或 OFB 模式。在字符爲單元的流密碼中多選 CFB 模式。

  • CTR 模式用於高速同步系統,不容忍差錯傳播。

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

直接設計哈希函數

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

Merkle 在 1989 年提出迭代型哈希函數的一般結構;(另外一個工作是默克爾哈希樹),Ron Rivest 在 1990 年利用這種結構提出 MD4。(另外一個工作是 RSA 算法),這種結構在幾乎所有的哈希函數中使用,具體做法爲:

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

迭代型哈希函數的一般結構示意圖

  • 把所有消息 M 分成一些固定長度的塊 Yi

  • 最後一塊 padding 並使其包含消息 M 的長度

  • 設定初始值 CV0

  • 循環執行壓縮函數 f,CVi=f(CVi -1||Yi -1)

  • 最後一個 CVi 爲哈希值

  • 算法中重複使用一個壓縮函數 f

  • f 的輸入有兩項,一項是上一輪輸出的 n 比特值 CVi-1,稱爲鏈接變量,另一項是算法在本輪的 b 比特輸入分組 Yi-1

  • f 的輸出爲 n 比特值 CVi,CVi 又作爲下一輪的輸入

  • 算法開始時還需對鏈接變量指定一個初值 IV,最後一輪輸出的鏈接變量 CVL 即爲最終產生的雜湊值

  • 通常有 b>n,因此稱函數 f 爲壓縮函數

  • 算法可表達如下:CV0=IV= n 比特長的初值

  • CVi=f(CVi-1,Yi-1);1≤i≤L

  • H(M)=CVL

  • 算法的核心技術是設計難以找到碰撞的壓縮函數 f,而敵手對算法的攻擊重點是 f 的內部結構

  • f 和分組密碼一樣是由若干輪處理過程組成

  • 對 f 的分析需要找出 f 的碰撞。由於 f 是壓縮函數,其碰撞是不可避免的,因此在設計 f 時就應保證找出其碰撞在計算上是困難的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

硬核丨一文讀懂區塊鏈中的哈希函數是如何構造的

來源鏈接:mp.weixin.qq.com