查找雜湊函式的衝突
我正在嘗試為以下（修改後的）Merkle–Damgård 雜湊函式找到衝突。
假設我們已經有一個雜湊函式 $ h : \mathbb{Z}_2^{2·n} \to \mathbb{Z}_2^n $ 對於固定長度的位串，使用 $ h(0\ldots 0)= 0\ldots 0 $ .
輸入 $ x $ (bit string, variable size) 分成塊 $ x_j $ 的 $ n $ 位，如有必要，用零填充最後一個塊：
$$ \overbrace{x_0}^{n \text{ bit}}|| \overbrace{x_1}^{n \text{ bit}}|| \ldots|| \overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1}|| 0\ldots 0}^{n \text{ bit}} $$ 我們添加另一個塊 $ x_{i} $ 的 $ n $ 位，包含的二進製表示 $ |x| $ （x的長度），導致：
$$ \overbrace{x_0}^{n \text{ bit}}||\overbrace{x_1}^{n \text{ bit}}||\ldots||\overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1} 0\ldots 0}^{n \text{ bit}}||\overbrace{|x|}^{n \text{ bit}} $$ 因此我們有 $ i+1 $ 塊 $ n $ 咬一口。為了 $ 0\leq j\leq i $ , 參考 $ j $ 第塊為 $ b_j $ .
定義 $ y_0 := 0\ldots 0||b_0 $ 和 $ y_j := h(y_{j-1})||b_j $ 為了 $ 1\leq j\leq i $
( $ 0\ldots 0||b_0 $ 和分別 $ h(y_{j-1})||b_j $ 意味著將所有內容連接在一起）。
雜湊函式 $ h^* $ 然後定義為
$$ h^*(x) := h(y_i) $$
如何找到碰撞 $ h^* $ 沒有一個 $ h $ ?
答案是你不能；如果你有碰撞 $ h^* $ ，你也有碰撞 $ h $ .
證明基於抗散列原語的抗衝突散列的標準方法是表明，如果在完整散列中給定一個衝突，我們可以證明它在原語中給我們一個衝突。因此，如果我們認為我們無法在原語中找到衝突，那麼我們就無法在完整雜湊中找到衝突。
這種技術在這裡似乎工作得很好。
假設我們收到兩條衝突消息 $ M $ 和 $ M’ $ ， 那是 $ M \neq M’ $ 和 $ h^(M) = h^(M’) $ . 我們將展示如何檢查這兩個消息 $ M $ 和 $ M’ $ 被處理 $ h^* $ 表明在其中一個呼叫中一定存在一些內部衝突 $ h $ .
首先，考慮以下情況 $ y_i \ne y’_i $ . 如果是這種情況，那麼我們會立即發生碰撞，因為 $ h(y_i) = h^(M) = h^(M’) = h(y’_i) $
另一種可能的情況是 $ y_i = y’_i $ . 這意味著消息的長度 $ M, M’ $ 是相同的（因為長度 $ M, M’ $ 包含在值中 $ y_j, y’_j $ .
我們也知道 $ M, M’ $ 在某處有所不同，也就是說，至少在一個 $ n $ 位塊。讓我們打電話 $ j $ 的職位之一 $ M $ 和 $ M’ $ 不同; 那是， $ b_j \neq b’_j $ . 這立即意味著 $ y_j \neq y’_j $ （因為 $ y_j, y’_j $ 包含 $ b_j, b’_j $ 作為子字元串）。
因為 $ y_j \ne y’_j $ 和 $ y_i = y’i $ 和 $ j<i $ ，這意味著必須有一個 $ j \le k < i $ 在哪裡 $ y_k \ne y’k $ 和 $ y{k+1} = y’{k+1} $ . 這立即給了我們 h 中的雜湊衝突，因為 $ h(y_k) = h(y’_k) $