現代密碼學5.2--域擴張：Merkle-Damgard Transform

• Merkle-Damgard Transform

博主正在學習INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯誤請指正。整理成一個系列現代密碼學，方便檢索。

• 第二章定義了完美安全及其對應的密碼方案“一次一密”，
• 第三章介紹了安全定義和滿足安全定義的密碼方案：
  • 3.1-3.3 計算安全，PRG和基于PRG構造的滿足計算安全的密碼方案；
  • 3.4-3.5 CPA安全，PRF和基于PRF構造的滿足CPA安全的密碼方案
  • 3.6 基于PRG和PRF構造的流密碼和分組密碼；
  • 3.7 CCA安全，對非CCA安全密碼方案的攻擊
• 第五章介紹哈希函數：
  • 5.1節介紹了哈希函數的定義
  • 5.2節將介紹一種域擴張，可以將固定長度的輸入擴張到任意長度的輸入，這樣我們就可以只考慮固定長度輸入的哈希函數，簡化了問題。

Merkle-Damgard Transform

• 根據5.1節哈希函數的定義，我們知道哈希函數是將任意長度的字符串映射到固定長度的字符串：$\{0,1{\}}^{?}\to \{0,1{\}}^l,?>l$，
• 但是實際中我們去構建一個哈希函數往往不會考慮對任意長度的輸入，這樣需要考慮的范圍太廣了
• 我們考慮固定長度的輸入，比如$2n\to n$，壓縮一半長度的哈希函數
• 因為有域擴張，考慮固定長度輸入與任意長度輸入在抗碰撞性上是等價的，所以我們可以只考慮固定長度輸入。

現在證明考慮固定長度輸入$(Gen,h)$與任意長度輸入$(Gen,H)$在抗碰撞性上是等價的：

• 假設$(Gen,h)：\{0,1{\}}^{2n}\to \{0,1{\}}^n$
• $(Gen,H)：x\in \{0,1{\}}^{?}\to \{0,1{\}}^n，|x|=L<2^n$
• 定義$(Gen,H)$：設置$B:=?\frac{L}{n}?$，原始輸入$x$被劃分成$B$個$n$-比特塊，令$x_{B+1}=L$，$z_0=0^n$，$z_i=h^s(z_{i?1}||x_i)$，輸出$z_{B+1}$。

我們只要說明$?s$，$H^s$上的碰撞是$h^s$上的碰撞。

• 假設$H^s$上有一對碰撞對$(x,x^{\prime })$，$x_{B+1}=L$，$x_{B^{\prime }+1}^{\prime }=L^{\prime }$
• 考慮兩種情況
  • case1：$L=L^{\prime }$
    • $H^s(x)=z_{B+1}=h^s(z_B||L)$
    • $H^s(x^{\prime })=z_{B^{\prime }+1}^{\prime }=h^s(z_{B^{\prime }}^{\prime }||L^{\prime })$
    • 因為$H^s(x)=H^s(x^{\prime })$，則$h^s(z_B||L)=h^s(z_{B^{\prime }}^{\prime }||L^{\prime })$。
    • 因為$L=L^{\prime }$，所以$z_B||L=z_{B^{\prime }}^{\prime }||L^{\prime }$，所以這是$h^s$上的碰撞對。
  • case2：$L=L^{\prime }$
    • 類似地，因為最后輸出是一樣的，而$x=x^{\prime }$，所以一定有某個中間輸入是不一樣的

總結

以上是生活随笔為你收集整理的现代密码学5.2--域扩张：Merkle-Damgard Transform的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。