現(xiàn)代密碼學(xué)5.4--對(duì)哈希函數(shù)的攻擊

• 生日攻擊
• • 生日問(wèn)題

博主正在學(xué)習(xí)INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯(cuò)誤請(qǐng)指正。整理成一個(gè)系列現(xiàn)代密碼學(xué)，方便檢索。

• 第二章定義了完美安全及其對(duì)應(yīng)的密碼方案“一次一密”，
• 第三章介紹了多種安全定義
  • 3.1-3.3 計(jì)算安全，PRG和基于PRG構(gòu)造的滿足計(jì)算安全的密碼方案；
  • 3.4-3.5 CPA安全，PRF和基于PRF構(gòu)造的滿足CPA安全的密碼方案
  • 3.6 基于PRG和PRF構(gòu)造的流密碼和分組密碼；
  • 3.7 CCA安全，對(duì)非CCA安全密碼方案的攻擊
• 第四章介紹消息驗(yàn)證碼/MAC
  • 4.1節(jié)介紹了什么是消息完整性
  • 4.2節(jié)介紹MAC的定義以及安全性定義
• 第五章介紹哈希函數(shù)
  • 5.1節(jié)介紹了哈希函數(shù)的定義
  • 5.2節(jié)介紹了域擴(kuò)張：固定長(zhǎng)度輸入$\to$任意長(zhǎng)度輸入
  • 5.3節(jié)介紹基于Hash和固定長(zhǎng)度輸入MAC構(gòu)造的任意長(zhǎng)度輸入MAC
  • 5.4節(jié)將介紹對(duì)哈希函數(shù)的攻擊
    • 生日攻擊
    • 小空間生日攻擊
    • 求逆函數(shù)的時(shí)間/空間權(quán)衡

生日攻擊

攻擊哈希函數(shù)$H:\{0,1{\}}^{?}\to \{0,1{\}}^l$，可以通過(guò)：

• 計(jì)算$2^l+1$種不同輸入的哈希值，可以找到碰撞

希望簡(jiǎn)化問(wèn)題

• 原始問(wèn)題：對(duì)于$q$個(gè)不同輸入$x_1,\dots \dots x_q$，計(jì)算$y_i=H(x_i)$，檢查是否有兩個(gè)$y_i$相等
• 簡(jiǎn)化問(wèn)題：把$H$看作隨機(jī)函數(shù)，$y_i\in \{0,1{\}}^l$，隨機(jī)選擇$y_1\dots \dots y_q$，找到$y_i=y_j$的概率

生日問(wèn)題

一個(gè)房間里有$q$個(gè)人，其中有兩個(gè)人生日相同的概率是多少？$y_i\in \{1,\dots \dots ,365\}$

• 概率

• 計(jì)算過(guò)程

總結(jié)

以上是生活随笔為你收集整理的现代密码学5.4--对哈希函数的攻击的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。