現代密碼學5.3--Hash and MAC

• 構造
• 安全性證明

博主正在學習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安全密碼方案的攻擊
• 第四章介紹消息驗證碼/MAC
  • 4.1節介紹了什么是消息完整性
  • 4.2節介紹MAC的定義以及安全性定義
• 第五章介紹哈希函數
  • 5.1節介紹了哈希函數的定義
  • 5.2節介紹了域擴張：固定長度輸入$\to$任意長度輸入
  • 5.3節將介紹基于Hash和固定長度輸入MAC構造的任意長度輸入MAC

構造

• ${\Pi }_H=($Gen${}_H,H)$：輸出長度為$l(n)$的哈希函數
• $\Pi =($Mac, Vrfy$)$：固定長度$l(n)$信息的MAC
• ${\Pi }^{\prime }=($Gen’,Mac’,Vrfy’$)$：任意長度信息

用${\Pi }_H=($Gen${}_H,H)$, $\Pi =($Mac, Vrfy$)$構造${\Pi }^{\prime }=($Gen’,Mac’,Vrfy’$)$。

• Gen’：輸入$1^n$，隨機選擇$k\in \{0,1{\}}^n$，運行Gen${}_H(1^n)$獲得$s$，密鑰是$k^{\prime }=<k,s>$
• Mac’：輸入密鑰$<k,s>$和明文$m\in \{0,1{\}}^{?}$，輸出$t\leftarrow$ Mac${}_k(H^s(m))$
• Vrfy’：輸入密鑰$<k,s>$，明文$m\in \{0,1{\}}^{?}$，MAC tag $t$，當僅當Vrfy${}_k(H^s(m),t)=1$，輸出1。

安全性證明

條件

• 固定長度信息MAC是安全的
• 哈希函數是抗碰撞的

結論

• 任意長度信息MAC是安全的

證明思路

• 令$Q$為已經問過的集合，假設敵手$\mathcal{A}$可以對一個新信息$m^{?}\in /Q$偽造一個有效的tag
• 分成兩種情況來考慮：$H^s(m^{?})=H^s(m)$和$H^s(m^{?})=H^s(m)$，定義事件"coll"為"$?m\in Q,H^s(m^{?})=H^s(m)$"
• Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}=1$]
  $=$Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge$ coll]+Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge \overline{coll}$]
  $\le$Pr[coll]+Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge \overline{coll}$]
• 只需要證明
  • Pr[coll]$\le$negl
  • Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge \overline{coll}$]$\le$ negl

證明過程

• 要證明Pr[coll]$\le$negl
  • 只需證明Pr[Hash-coll${}_{\mathcal{C},{\Pi }_H}(n)=1$]=Pr[coll]
    • 通過${\mathcal{A}}^{\prime }$構造$\mathcal{C}$
• 要證明Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge \overline{coll}$]$\le$ negl
  • 只需證明Pr[Mac-forge${}_{\mathcal{A},\Pi }(n)=1$]=Pr[Mac-forge${}_{{\mathcal{A}}^{\prime },{\Pi }^{\prime }}(n)=1\wedge \overline{coll}$]
    • 通過${\mathcal{A}}^{\prime }$構造$\mathcal{A}$

總結

以上是生活随笔為你收集整理的现代密码学5.3--Hash and MAC的全部內容，希望文章能夠幫你解決所遇到的問題。

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