密碼Hash函數(shù)教學(xué)課件

第十講密碼Hash函數(shù)本講提要口分類與架構(gòu)口基木構(gòu)造口修改發(fā)現(xiàn)碼(MDC)口消息認證碼(MAC)1分類與架構(gòu)(續(xù))11基本性質(zhì)與定義(續(xù))密碼中使用的Hash函數(shù)主要為兩類(1)修改發(fā)現(xiàn)碼(MDC):不帶密鑰的Hash函數(shù),主要用于提供消息完整性檢査2)消息認證碼(MAC:帶密鑰的Hash函數(shù),主要用于認證消息源及保證其完整性。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))定義2修改發(fā)現(xiàn)碼(MDC是Hash函數(shù)h,對于輸入x和x以及相應(yīng)輸出y和y滿足如下性質(zhì)(1)原像不可逆:對于幾乎所有的Hash輸出不可能計算出其的Hash輸入。也就是,在不知道輸入的情況下給定任意一個輸出y,找到任意一個輸入x滿足h(x)=y是計算不可能的。(2)二次原像不可逆:對于任何一個給定的輸入x,找到另一個輸入xκx,且滿足h(x)=h(x),在計算上不可能3)抵抗碰撞:找到兩個不同的輸入x和x,滿足h(x)=h(x2),在計算上不可能(注意:這里兩個輸入可以自由選擇)。分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))定義1和定義2的說明:1)“容易”和“計算上不可能”都留下來沒有準(zhǔn)確定義?！叭菀住币馕吨囗検綍r間和空間;“計算上不可能”意味著超越多項式的計算需求。(2)一般認為,抗原像=單向;抗二次原像≡抗弱碰撞;抵抗碰撞≡抗強碰撞。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))定義3單向Hash函數(shù)(OWHF)是滿足定義1以及定義2中(1)和(2)的Hash函數(shù)。定義4抗碰撞Hash函數(shù)(CRHF是滿足定義1以及定義2中(2)和(3)的Hash函數(shù)。#雖然幾乎所有實際使用的CRHF都有抗原像攻擊的性質(zhì),但由于技術(shù)原因定義4并未給出。1分類與架構(gòu)(續(xù))11基本性質(zhì)與定義(續(xù))攻擊者攻擊MDC的主要目標(biāo)如下:)給定Hash值y,發(fā)現(xiàn)原像x滿足y=h(x)或者給定對(x,hx)發(fā)現(xiàn)另一個像x滿足h(x)=h(x)。2)發(fā)現(xiàn)兩個Hash輸入x和x滿足h(x)=h(x)。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))定義5消息認證碼(MAC)算法是帶有密鑰k的函數(shù)族h,其具有如下性質(zhì)(1)易于計算:對于任何已知函數(shù)h2,給定值k和輸入x,值h(x)容易計算出來。這個值被稱做MAC值或MAC。1分類與架構(gòu)(續(xù))1基本性質(zhì)與定義(續(xù))(2)壓縮:函數(shù)h2可以將任意有限比特長度的輸入x映射為固定n比特長度的位串。進步,給出函數(shù)族h的算法描述,對于任何個固定符合要求的密鑰值k(攻擊者不知其值)需要滿足如下性質(zhì):3)計算抵抗:給定0個或多個消息MAC值對(x,h(x)