第十講-密碼Hash函數(shù)課件

第十講密碼Hash函數(shù)1謝謝您的觀賞2019-8-29第十講密碼Hash函數(shù)1謝謝您的觀賞2019-8-29本講提要分類與架構(gòu)基本構(gòu)造修改發(fā)現(xiàn)碼(MDC)

消息認(rèn)證碼(MAC)2謝謝您的觀賞2019-8-29本講提要分類與架構(gòu)2謝謝您的觀賞2019-8-291分類與架構(gòu)

定義1Hash函數(shù)(在不嚴(yán)格意義下)是至少滿足下列兩條性質(zhì)的函數(shù)h。(1)壓縮：h將任意有限比特長度的輸入x映射為固定長度為n的輸出h(x)。(2)容易計算：給定h和輸入x，容易計算出h(x)。1.1基本性質(zhì)與定義3謝謝您的觀賞2019-8-291分類與架構(gòu)定義1Hash函數(shù)(在不嚴(yán)格意義下)1分類與架構(gòu)(續(xù))

密碼中使用的Hash函數(shù)主要為兩類：

(1)修改發(fā)現(xiàn)碼(MDC)：不帶密鑰的Hash函數(shù)，主要用于提供消息完整性檢查。

(2)消息認(rèn)證碼(MAC)：帶密鑰的Hash函數(shù)，主要用于認(rèn)證消息源及保證其完整性。1.1基本性質(zhì)與定義(續(xù))4謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))密碼中使用的Hash函數(shù)主要為兩類1分類與架構(gòu)(續(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，找到另一個輸入xx，且滿足h(x)=h(x)，在計算上不可能。(3)抵抗碰撞：找到兩個不同的輸入x和x，滿足h(x)=h(x)，在計算上不可能(注意：這里兩個輸入可以自由選擇)。1.1基本性質(zhì)與定義(續(xù))5謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義2修改發(fā)現(xiàn)碼(MDC)是H1分類與架構(gòu)(續(xù))定義1和定義2的說明：(1)“容易”和“計算上不可能”都留下來沒有準(zhǔn)確定義。“容易”意味著多項式時間和空間；“計算上不可能”意味著超越多項式的計算需求。(2)一般認(rèn)為，抗原像單向；抗二次原像抗弱碰撞；抵抗碰撞抗強碰撞。1.1基本性質(zhì)與定義(續(xù))6謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義1和定義2的說明：1.1基本性1分類與架構(gòu)(續(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.1基本性質(zhì)與定義(續(xù))7謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義3單向Hash函數(shù)(OWH

1.1基本性質(zhì)與定義(續(xù))

攻擊者攻擊MDC的主要目標(biāo)如下：(1)給定Hash值y，發(fā)現(xiàn)原像x滿足y=h(x)；或者給定對(x，h(x))發(fā)現(xiàn)另一個像x滿足h(x)=h(x)。(2)發(fā)現(xiàn)兩個Hash輸入x和x滿足h(x)=h(x)。1分類與架構(gòu)(續(xù))8謝謝您的觀賞2019-8-291.1基本性質(zhì)與定義(續(xù))1分類與架構(gòu)(續(xù))8謝謝您的1分類與架構(gòu)(續(xù))

定義5

消息認(rèn)證碼(MAC)算法是帶有密鑰k的函數(shù)族hk，其具有如下性質(zhì)：(1)易于計算：對于任何已知函數(shù)hk，給定值k和輸入x，值hk(x)容易計算出來。這個值被稱做MAC值或MAC。1.1基本性質(zhì)與定義(續(xù))9謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義5消息認(rèn)證碼(MAC)算法是(2)壓縮：函數(shù)hk可以將任意有限比特長度的輸入x映射為固定n比特長度的位串。進一步，給出函數(shù)族h的算法描述，對于任何一個固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質(zhì)：(3)計算抵抗：給定0個或多個消息-MAC值對(xi，hk(xi))，找到任意消息-MAC值對(x，hk(x))滿足xxi在計算上不可能(當(dāng)然也包括某些i滿足hk(x)=hk(xi)的可能性)。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))10謝謝您的觀賞2019-8-29(2)壓縮：函數(shù)hk可以將任意有限比特長度的輸入x

評述.

(1)計算抵抗隱含了密鑰k是不可恢復(fù)的性質(zhì)，但密鑰不可恢復(fù)并不意味著計算抵抗。

(2)定義5并沒有顯示攻擊者知道密鑰k的情況下是否要抗原像和抗碰撞，但對不知道密鑰k的情況下，應(yīng)該滿足這些性質(zhì)。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))11謝謝您的觀賞2019-8-29評述.1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))攻擊者攻擊MAC的目標(biāo)為：在不知道密鑰k的情況下，給定一個或多個消息-MAC值對(xi，hk(xi))，計算出一個或多個新消息-MAC值對(x，hk(x))，滿足xxi。

攻擊者潛在的能力有：(1)已知消息攻擊。(2)選擇消息攻擊：掌握一個或多個由攻擊者選擇的xi對應(yīng)的消息-MAC值對(xi，hk(xi))。(3)適應(yīng)性選擇消息攻擊：允許根據(jù)前面的詢問結(jié)果連續(xù)做出消息選擇。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))12謝謝您的觀賞2019-8-29攻擊者攻擊MAC的目標(biāo)為：1分類與架構(gòu)(續(xù))1.1在實際中造成的破壞程度取決于攻擊者控制消息x并偽造其MAC值的程度，依此可以做如下分類。(1)選擇性偽造攻擊：攻擊者可以根據(jù)選擇，控制消息的內(nèi)容偽造出消息-MAC值對(或者至少為部分控制消息內(nèi)容)。(2)存在性偽造攻擊：攻擊者雖然可以偽造出消息-MAC值對，但無法控制消息的內(nèi)容。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))13謝謝您的觀賞2019-8-29在實際中造成的破壞程度取決于攻擊者控制消息x并偽與特定性質(zhì)聯(lián)系在一起的是開銷，如CRHF一般比OWHF要難于構(gòu)造，且其Hash值應(yīng)是OWHF的比特長度的兩倍。因此，考慮具體應(yīng)用十分重要。假如可由不可信方控制Hash函數(shù)的輸入的準(zhǔn)確內(nèi)容，則可能需要CRHF，如數(shù)字簽名。假如只是可信方的單方應(yīng)用，使用OWHF就足夠了，如口令表的應(yīng)用。1分類與架構(gòu)(續(xù))1.2特定應(yīng)用需要的性質(zhì)14謝謝您的觀賞2019-8-29與特定性質(zhì)聯(lián)系在一起的是開銷，如CRHF一般比OW

事實1

Hash函數(shù)的抗碰撞隱含抗二次原像。

事實2Hash函數(shù)抗碰撞不能保證抗原像。

事實3

Hash函數(shù)抗二次原像不能保證抗原像，抗原像也不能保證抗二次原像。事實4

hk是MAC，hk符合計算抵抗性質(zhì)。若攻擊者不知道密鑰k，hk抗選擇消息攻擊，則應(yīng)該抗二次原像、抗碰撞、抗原像。1分類與架構(gòu)(續(xù))1.3性質(zhì)之間的關(guān)系15謝謝您的觀賞2019-8-29事實1Hash函數(shù)的抗碰撞隱含抗二次原像。1MDC的其他應(yīng)用

(1)知識確認(rèn)。

(2)密鑰產(chǎn)生。

(3)偽隨機數(shù)發(fā)生。

#這些MDC可能需要滿足一些超過之前定義的附加性質(zhì)。1分類與架構(gòu)(續(xù))1.4其他應(yīng)用16謝謝您的觀賞2019-8-29MDC的其他應(yīng)用1分類與架構(gòu)(續(xù))1.4其他應(yīng)用12基本構(gòu)造2.1迭代結(jié)構(gòu)的一般模型高級視圖輸出可選輸出變換迭代壓縮函數(shù)任意長度輸入固定長度輸出17謝謝您的觀賞2019-8-292基本構(gòu)造2.1迭代結(jié)構(gòu)的一般模型高級視圖輸出可選輸出變2基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))詳細(xì)視圖fHash函數(shù)h初始輸入x預(yù)處理附加長度分組附加填充比特迭代處理壓縮函數(shù)fHiHi-1Htgxi輸出h(x)=g(Ht)格式化輸入x=x1x2…xt18謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))詳細(xì)視圖f2基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))Hi表示第i步的部分結(jié)果，輸入為x=x1x2…xt的迭代函數(shù)的一般模型為

H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=g(Ht)。

Hi-1表示第i-1步和第i步之間的n比特鏈變量，H0是預(yù)定義的開始值或初始值(IV)。最后一步用可選的輸出變換g將n比特鏈變量映射為m比特結(jié)果g(Ht)，通常g(Ht)=Ht。19謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))H2基本構(gòu)造(續(xù))2.2實際安全需要的輸出比特大小

事實5

一個n比特輸出的不帶密鑰Hash函數(shù)是理想安全的，如果：(1)給定一個Hash輸出，產(chǎn)生一個原像和二次原像需要大約2n次操作規(guī)模；(2)產(chǎn)生一個碰撞需要大約2n/2次操作規(guī)模。

事實6

假定n比特輸出的Hash函數(shù)，280次操作在計算上不可能，則有：(1)OWHF要求n80；(2)CRHF要求n160；(3)MAC對大部分環(huán)境要求n64以及64-80比特的密鑰，如果有特別控制，可小到n=32或64。20謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.2實際安全需要的輸出比特大小事在分組密碼基礎(chǔ)上建立Hash函數(shù)的主要動機是：如果系統(tǒng)已經(jīng)擁有了非常有效的分組密碼，那么以分組密碼作為實現(xiàn)Hash函數(shù)的主要部件，將既可以提供Hash函數(shù)的功能，又能使額外開銷最小。3無密鑰密碼Hash函數(shù)：MDC3.1基于分組密碼的Hash函數(shù)：MDC-221謝謝您的觀賞2019-8-29在分組密碼基礎(chǔ)上建立Hash函數(shù)的主要動機是：如果系統(tǒng)3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))22謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))23謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i3無密鑰密碼Hash函數(shù)：MDC(續(xù))3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))24謝謝您的觀賞2019-8-29Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iC3.2定制的Hash函數(shù)：SHA-1

安全Hash算法(SHA)是美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)設(shè)計，并于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS180)發(fā)布的。后做修改，于1995年再次公布修訂后的SHA，通常稱為SHA-1。3無密鑰密碼Hash函數(shù)：MDC(續(xù))25謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1安全Hash算法3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1算法的輸入為小于264比特長的任意消息，輸出為160比特的消息摘要，算法處理過程如下圖。YL-13無密鑰密碼Hash函數(shù)：MDC(續(xù))HSHAIV(160比特)Y0(512比特)HSHAY1CV1(160比特)…HSHACVqYq…CV2HSHACVL-1消息摘要26謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數(shù)減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數(shù)在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。這形成了長度為512比特的一系列分組Y0，Y1，…，YL-1。需要產(chǎn)生Hash值的消息100…0消息長度K填充長度1-512比特K比特L×512比特3無密鑰密碼Hash函數(shù)：MDC(續(xù))27謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))

(2)初始化。SHA-1使用160比特的緩沖區(qū)存儲中間和最終Hash值，可用5個32比特寄存器A，B，C，D，E表示，初始值為(十六進制)A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。3無密鑰密碼Hash函數(shù)：MDC(續(xù))28謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))(2)初3.2定制的Hash函數(shù)：SHA-1(續(xù))

(3)處理。每個分組Yq經(jīng)過壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過程構(gòu)成。每一輪又由20步迭代組成。4輪處理結(jié)構(gòu)一樣，但基本邏輯函數(shù)不同，分別為f1，f2，f3，f4。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D、E的當(dāng)前值，輸出仍放在對應(yīng)緩沖區(qū)。每一輪處理有一個加法常量Ki，其中t表示迭代步數(shù)，0≤t≤79。第4輪的輸出與第1輪的輸入CVq依5個緩沖區(qū)對應(yīng)進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是160比特消息摘要。3無密鑰密碼Hash函數(shù)：MDC(續(xù))29謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))(3)3.2定制的Hash函數(shù)：SHA-1(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))CVq160位Yq512位f1,K1,W[0…19]20步BADCEf2,K2,W[20…39]20步BADCEf3,K3,W[40…59]20步BADCEf4,K4,W[60…79]20步BADCE++++CVq+1160位+30謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))3無密鑰密碼H3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1的壓縮函數(shù)各個20步迭代運算的每一步運算可以表示為

A，B，C，D，E←(E+fi(B，C，D)+CLS5(A)+Wt+Ki)，A，CLS30(B)，C，D

其中，t是迭代的步數(shù)(0≤t≤79)，+是模232相加，fi是i(1≤i≤4)輪的基本邏輯函數(shù)，CLSs表示循環(huán)左移s位，Wt是當(dāng)前512比特分組導(dǎo)出的一個32比特字。3無密鑰密碼Hash函數(shù)：MDC(續(xù))31謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-1的壓縮函數(shù)(續(xù))基本邏輯函數(shù)f1，f2，f3，f4分別定義為：f1(X，Y，Z)=(XY)(XZ)f2(X，Y，Z)=f4(X，Y，Z)=XYZf3(X，Y，Z)=(XY)(XZ)(YZ)其中，是與，是或，是異或，是非。3無密鑰密碼Hash函數(shù)：MDC(續(xù))32謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-1的壓縮3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1的壓縮函數(shù)(續(xù))

加法常量(十六進制)

K1=5a827999，對應(yīng)0≤t≤19

K2=6ed9eba1，對應(yīng)20≤t≤39

K3=8f1bbcdc

，對應(yīng)40≤t≤59

K4=

ca62c1d6，對應(yīng)60≤t≤79

字?jǐn)U展前16個字W0，W1，…，W15，直接由輸入得到。其余由公式Wt=CLS1(Wt-3Wt-8Wt-14Wt-16)依次得到。3無密鑰密碼Hash函數(shù)：MDC(續(xù))33謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-3.3定制的Hash函數(shù)：MD5

MD5是1992年由Rivest提出的無密鑰Hash函數(shù)。MD5是MD4(1990年提出)的增強版本。MD5對任意長度的消息產(chǎn)生128比特的Hash值。MD4在280次壓縮函數(shù)計算下已經(jīng)找到了碰撞，因此，不在被推薦用做抗碰撞的Hash函數(shù)。近年來，MD5也發(fā)現(xiàn)了一些弱點。3無密鑰密碼Hash函數(shù)：MDC(續(xù))34謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5MD5是1992年由3.3定制的Hash函數(shù)：MD5(續(xù))MD5算法的輸入為任意比特長的消息，輸出為128比特的消息摘要，算法處理過程如下圖。3無密鑰密碼Hash函數(shù)：MDC(續(xù))HMD5IV(128比特)Y0(512比特)HMD5Y1CV1(128比特)…HMD5CVqYq…CV2HMD5CVL-1YL-1消息摘要35謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5算法的3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))MD5消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數(shù)減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數(shù)在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。如果消息長度大于264，則以264取模。這形成了長度為512比特的一系列分組Y0，Y1，…

，YL-1。需要產(chǎn)生Hash值的消息100…0消息長度Kmod264填充長度1-512比特K比特L×512比特=N×32比特36謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))

(2)初始化。MD5使用128比特的緩沖區(qū)存儲中間和最終Hash值，可用4個32比特寄存器A，B，C，D表示，初始值為(十六進制)A=01234567，B=89abcdef，C=fedcba98，D=76543210。3無密鑰密碼Hash函數(shù)：MDC(續(xù))37謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))(2)初始化3.3定制的Hash函數(shù)：MD5(續(xù))

(3)處理。每個分組Yq經(jīng)過壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過程構(gòu)成。每一輪又由16步迭代組成。4輪處理結(jié)構(gòu)一樣，但基本邏輯函數(shù)不同，分別為F，G，H，I

。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D的當(dāng)前值，輸出仍放在對應(yīng)緩沖區(qū)。每一輪處理有一個常量T[i]，其中i表示迭代步數(shù)，1≤i≤64。第4輪的輸出與第1輪的輸入CVq依4個緩沖區(qū)對應(yīng)進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是128比特消息摘要。3無密鑰密碼Hash函數(shù)：MDC(續(xù))38謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))(3)處理。3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))CVq128位Yq512位F,T[1…16],X[i],16步BADCBADCBADCBADC++++CVq+1128位G,T[17…32],X[p2(i)],16步H,T[33…48],X[p3(i)],16步I,T[49…64],X[p4(i)],16步39謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))MD5的壓縮函數(shù)一步迭代壓縮函數(shù)如下圖。ACBD+++<<<s+RACBDX[k]T[i]

R表示函數(shù)F、G、H、I中的一個，它們依次在連續(xù)16步中使用<<<s表示循環(huán)左移s比特X[k]表示在第q個長度為512比特分組中的第k個32比特分組T[i]表示常數(shù)中的第i個字

+表示模232相加40謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))

MD5的壓縮函數(shù)(續(xù))邏輯函數(shù)F，G，H，I分別定義為：

F(X，Y，Z)=(XY)(XZ)G(X，Y，Z)=(XY)(YZ)H(X，Y，Z)=XYZI(X，Y，Z)=Y(XZ)

T[i]定義為：

T[i]=232|sin(i)|，i=1,2,…,64，這里，i是弧度。

3無密鑰密碼Hash函數(shù)：MDC(續(xù))41謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數(shù)：MD5(續(xù))

MD5的壓縮函數(shù)(續(xù))

MD5壓縮的每個512比特消息分組要經(jīng)過4輪處理，第1輪以其32比特連續(xù)分組的初始順序使用，而第2至4輪處理按如下三個置換計算出的順序使用：

p2(i)=(1+5i)mod16p3(i)=(5+3i)mod16

p4(i)=7imod16，這里i=0,1,…,15。3無密鑰密碼Hash函數(shù)：MDC(續(xù))42謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數(shù)：MD5(續(xù))

MD5的壓縮函數(shù)(續(xù))

4輪中每一步的循環(huán)左移位數(shù)見下表。3無密鑰密碼Hash函數(shù)：MDC(續(xù))43謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5的壓縮函4.1基于分組密碼的Hash函數(shù)：CBC的MAC4帶密鑰密碼Hash函數(shù)：MAC44謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數(shù)：CBC的MAC4帶密鑰4.1基于分組密碼的Hash函數(shù)：CBC的MAC(續(xù))M10EkH1M2EkH2…Ht-1MtEkHtEkDk'Ht可選4帶密鑰密碼Hash函數(shù)：MAC(續(xù))45謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數(shù)：CBC的MAC(續(xù))M1

4.1基于分組密碼的Hash函數(shù)：CBC的MAC(續(xù))

評論.(1)

很明顯，在生成CBC-MAC值(由運行CBC模式的分組密碼構(gòu)造的MAC)的計算中包括了不可求逆的數(shù)據(jù)壓縮(本質(zhì)上，CBC-MAC是整個消息的“短摘要”)，因此CBC-MAC是一個單向變換。所有的分組密碼加密算法的混合變換性質(zhì)為這個單向函數(shù)變換增加了一個雜湊特點(也就是說，將MAC分布到MAC空間與分組密碼加密算法將密文分布到密文空間同樣均勻)。4帶密鑰密碼Hash函數(shù)：MAC(續(xù))46謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數(shù)：CBC的MAC((2)如果考慮窮舉密鑰搜索攻擊，可以考慮最后僅輸出n比特中的m比特作為MAC數(shù)值。

(3)單分組消息x1，x2的兩個文本消息-MAC對(x1,H1)和(x2,H2)。對一個2分組的第三個消息x1||z請求MAC值M，產(chǎn)生文本消息-MAC對(x1||z,M)。由此，知新2分組的消息X=x2||(H1zH2)的MAC值也是M。(4)可選處理減少了窮舉密鑰搜索攻擊的威脅，阻止了選擇文本攻擊的存在性偽造，由于沒有在整個過程中使用三重加密，所以不會特別影響效率。4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.1基于分組密碼的Hash函數(shù)：CBC的MAC(續(xù))47謝謝您的觀賞2019-8-29(2)如果考慮窮舉密鑰搜索攻擊，可以考慮最后僅輸出

由MDC算法構(gòu)造MAC算法的一個建議是簡單地把秘密密鑰k作為MDC的輸入的一部分。但因為MDC和MAC的定義并不完全一致，因此這種設(shè)計必須細(xì)致分析。

(1)消息為x=x1x2…xt和使用迭代函數(shù)f的迭代MDCh：定義H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=Ht。(1.1)如果建議的MAC對x的值是M=h(k||x)，則攻擊者可以計算M=h(k||x||y)=f(M||y)作為x||y的MAC值。(1.2)如果建議的MAC對x的值是M=h(x||k)輸出是n比特，則產(chǎn)生x和x滿足M=h(x||k)=h(x||k)的復(fù)雜度為O(2n/2)，n是h函數(shù)的輸出比特長度。4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.2由MDC構(gòu)造的MAC48謝謝您的觀賞2019-8-29由MDC算法構(gòu)造MAC算法的一個建議是簡單地把秘密密鑰

(2)對密鑰為k和MDC為h，可按如下方式計算消息x的MAC值hk(x)=h(k||p||x||k)。其中p將用于將k填充為一個分組長度，從而保證內(nèi)部至少進行兩次分組計算。

(3)對密鑰為k和MDC為h，另一種計算消息x的MAC值的方式是hk(x)=h(k||p1||h(k||p2||x))。其中p1，p2用于將k填充為一個分組長度。4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.2由MDC構(gòu)造的MAC(續(xù))49謝謝您的觀賞2019-8-29(2)對密鑰為k和MDC為h，可按如下方式計算消息4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC：MD5-MAC50謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC：MD5-MAC(續(xù))51謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC4帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC：MD5-MAC(續(xù))52謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數(shù)：MAC(續(xù))4.3定制的MAC謝謝!53謝謝您的觀賞2019-8-29謝謝!53謝謝您的觀賞2019-8-29第十講密碼Hash函數(shù)54謝謝您的觀賞2019-8-29第十講密碼Hash函數(shù)1謝謝您的觀賞2019-8-29本講提要分類與架構(gòu)基本構(gòu)造修改發(fā)現(xiàn)碼(MDC)

消息認(rèn)證碼(MAC)55謝謝您的觀賞2019-8-29本講提要分類與架構(gòu)2謝謝您的觀賞2019-8-291分類與架構(gòu)

定義1Hash函數(shù)(在不嚴(yán)格意義下)是至少滿足下列兩條性質(zhì)的函數(shù)h。(1)壓縮：h將任意有限比特長度的輸入x映射為固定長度為n的輸出h(x)。(2)容易計算：給定h和輸入x，容易計算出h(x)。1.1基本性質(zhì)與定義56謝謝您的觀賞2019-8-291分類與架構(gòu)定義1Hash函數(shù)(在不嚴(yán)格意義下)1分類與架構(gòu)(續(xù))

密碼中使用的Hash函數(shù)主要為兩類：

(1)修改發(fā)現(xiàn)碼(MDC)：不帶密鑰的Hash函數(shù)，主要用于提供消息完整性檢查。

(2)消息認(rèn)證碼(MAC)：帶密鑰的Hash函數(shù)，主要用于認(rèn)證消息源及保證其完整性。1.1基本性質(zhì)與定義(續(xù))57謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))密碼中使用的Hash函數(shù)主要為兩類1分類與架構(gòu)(續(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，找到另一個輸入xx，且滿足h(x)=h(x)，在計算上不可能。(3)抵抗碰撞：找到兩個不同的輸入x和x，滿足h(x)=h(x)，在計算上不可能(注意：這里兩個輸入可以自由選擇)。1.1基本性質(zhì)與定義(續(xù))58謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義2修改發(fā)現(xiàn)碼(MDC)是H1分類與架構(gòu)(續(xù))定義1和定義2的說明：(1)“容易”和“計算上不可能”都留下來沒有準(zhǔn)確定義?！叭菀住币馕吨囗検綍r間和空間；“計算上不可能”意味著超越多項式的計算需求。(2)一般認(rèn)為，抗原像單向；抗二次原像抗弱碰撞；抵抗碰撞抗強碰撞。1.1基本性質(zhì)與定義(續(xù))59謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義1和定義2的說明：1.1基本性1分類與架構(gòu)(續(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.1基本性質(zhì)與定義(續(xù))60謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義3單向Hash函數(shù)(OWH

1.1基本性質(zhì)與定義(續(xù))

攻擊者攻擊MDC的主要目標(biāo)如下：(1)給定Hash值y，發(fā)現(xiàn)原像x滿足y=h(x)；或者給定對(x，h(x))發(fā)現(xiàn)另一個像x滿足h(x)=h(x)。(2)發(fā)現(xiàn)兩個Hash輸入x和x滿足h(x)=h(x)。1分類與架構(gòu)(續(xù))61謝謝您的觀賞2019-8-291.1基本性質(zhì)與定義(續(xù))1分類與架構(gòu)(續(xù))8謝謝您的1分類與架構(gòu)(續(xù))

定義5

消息認(rèn)證碼(MAC)算法是帶有密鑰k的函數(shù)族hk，其具有如下性質(zhì)：(1)易于計算：對于任何已知函數(shù)hk，給定值k和輸入x，值hk(x)容易計算出來。這個值被稱做MAC值或MAC。1.1基本性質(zhì)與定義(續(xù))62謝謝您的觀賞2019-8-291分類與架構(gòu)(續(xù))定義5消息認(rèn)證碼(MAC)算法是(2)壓縮：函數(shù)hk可以將任意有限比特長度的輸入x映射為固定n比特長度的位串。進一步，給出函數(shù)族h的算法描述，對于任何一個固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質(zhì)：(3)計算抵抗：給定0個或多個消息-MAC值對(xi，hk(xi))，找到任意消息-MAC值對(x，hk(x))滿足xxi在計算上不可能(當(dāng)然也包括某些i滿足hk(x)=hk(xi)的可能性)。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))63謝謝您的觀賞2019-8-29(2)壓縮：函數(shù)hk可以將任意有限比特長度的輸入x

評述.

(1)計算抵抗隱含了密鑰k是不可恢復(fù)的性質(zhì)，但密鑰不可恢復(fù)并不意味著計算抵抗。

(2)定義5并沒有顯示攻擊者知道密鑰k的情況下是否要抗原像和抗碰撞，但對不知道密鑰k的情況下，應(yīng)該滿足這些性質(zhì)。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))64謝謝您的觀賞2019-8-29評述.1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))攻擊者攻擊MAC的目標(biāo)為：在不知道密鑰k的情況下，給定一個或多個消息-MAC值對(xi，hk(xi))，計算出一個或多個新消息-MAC值對(x，hk(x))，滿足xxi。

攻擊者潛在的能力有：(1)已知消息攻擊。(2)選擇消息攻擊：掌握一個或多個由攻擊者選擇的xi對應(yīng)的消息-MAC值對(xi，hk(xi))。(3)適應(yīng)性選擇消息攻擊：允許根據(jù)前面的詢問結(jié)果連續(xù)做出消息選擇。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))65謝謝您的觀賞2019-8-29攻擊者攻擊MAC的目標(biāo)為：1分類與架構(gòu)(續(xù))1.1在實際中造成的破壞程度取決于攻擊者控制消息x并偽造其MAC值的程度，依此可以做如下分類。(1)選擇性偽造攻擊：攻擊者可以根據(jù)選擇，控制消息的內(nèi)容偽造出消息-MAC值對(或者至少為部分控制消息內(nèi)容)。(2)存在性偽造攻擊：攻擊者雖然可以偽造出消息-MAC值對，但無法控制消息的內(nèi)容。1分類與架構(gòu)(續(xù))1.1基本性質(zhì)與定義(續(xù))66謝謝您的觀賞2019-8-29在實際中造成的破壞程度取決于攻擊者控制消息x并偽與特定性質(zhì)聯(lián)系在一起的是開銷，如CRHF一般比OWHF要難于構(gòu)造，且其Hash值應(yīng)是OWHF的比特長度的兩倍。因此，考慮具體應(yīng)用十分重要。假如可由不可信方控制Hash函數(shù)的輸入的準(zhǔn)確內(nèi)容，則可能需要CRHF，如數(shù)字簽名。假如只是可信方的單方應(yīng)用，使用OWHF就足夠了，如口令表的應(yīng)用。1分類與架構(gòu)(續(xù))1.2特定應(yīng)用需要的性質(zhì)67謝謝您的觀賞2019-8-29與特定性質(zhì)聯(lián)系在一起的是開銷，如CRHF一般比OW

事實1

Hash函數(shù)的抗碰撞隱含抗二次原像。

事實2Hash函數(shù)抗碰撞不能保證抗原像。

事實3

Hash函數(shù)抗二次原像不能保證抗原像，抗原像也不能保證抗二次原像。事實4

hk是MAC，hk符合計算抵抗性質(zhì)。若攻擊者不知道密鑰k，hk抗選擇消息攻擊，則應(yīng)該抗二次原像、抗碰撞、抗原像。1分類與架構(gòu)(續(xù))1.3性質(zhì)之間的關(guān)系68謝謝您的觀賞2019-8-29事實1Hash函數(shù)的抗碰撞隱含抗二次原像。1MDC的其他應(yīng)用

(1)知識確認(rèn)。

(2)密鑰產(chǎn)生。

(3)偽隨機數(shù)發(fā)生。

#這些MDC可能需要滿足一些超過之前定義的附加性質(zhì)。1分類與架構(gòu)(續(xù))1.4其他應(yīng)用69謝謝您的觀賞2019-8-29MDC的其他應(yīng)用1分類與架構(gòu)(續(xù))1.4其他應(yīng)用12基本構(gòu)造2.1迭代結(jié)構(gòu)的一般模型高級視圖輸出可選輸出變換迭代壓縮函數(shù)任意長度輸入固定長度輸出70謝謝您的觀賞2019-8-292基本構(gòu)造2.1迭代結(jié)構(gòu)的一般模型高級視圖輸出可選輸出變2基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))詳細(xì)視圖fHash函數(shù)h初始輸入x預(yù)處理附加長度分組附加填充比特迭代處理壓縮函數(shù)fHiHi-1Htgxi輸出h(x)=g(Ht)格式化輸入x=x1x2…xt71謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))詳細(xì)視圖f2基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))Hi表示第i步的部分結(jié)果，輸入為x=x1x2…xt的迭代函數(shù)的一般模型為

H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=g(Ht)。

Hi-1表示第i-1步和第i步之間的n比特鏈變量，H0是預(yù)定義的開始值或初始值(IV)。最后一步用可選的輸出變換g將n比特鏈變量映射為m比特結(jié)果g(Ht)，通常g(Ht)=Ht。72謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.1迭代結(jié)構(gòu)的一般模型(續(xù))H2基本構(gòu)造(續(xù))2.2實際安全需要的輸出比特大小

事實5

一個n比特輸出的不帶密鑰Hash函數(shù)是理想安全的，如果：(1)給定一個Hash輸出，產(chǎn)生一個原像和二次原像需要大約2n次操作規(guī)模；(2)產(chǎn)生一個碰撞需要大約2n/2次操作規(guī)模。

事實6

假定n比特輸出的Hash函數(shù)，280次操作在計算上不可能，則有：(1)OWHF要求n80；(2)CRHF要求n160；(3)MAC對大部分環(huán)境要求n64以及64-80比特的密鑰，如果有特別控制，可小到n=32或64。73謝謝您的觀賞2019-8-292基本構(gòu)造(續(xù))2.2實際安全需要的輸出比特大小事在分組密碼基礎(chǔ)上建立Hash函數(shù)的主要動機是：如果系統(tǒng)已經(jīng)擁有了非常有效的分組密碼，那么以分組密碼作為實現(xiàn)Hash函數(shù)的主要部件，將既可以提供Hash函數(shù)的功能，又能使額外開銷最小。3無密鑰密碼Hash函數(shù)：MDC3.1基于分組密碼的Hash函數(shù)：MDC-274謝謝您的觀賞2019-8-29在分組密碼基礎(chǔ)上建立Hash函數(shù)的主要動機是：如果系統(tǒng)3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))75謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))76謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))3無Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i3無密鑰密碼Hash函數(shù)：MDC(續(xù))3.1基于分組密碼的Hash函數(shù)：MDC-2(續(xù))77謝謝您的觀賞2019-8-29Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iC3.2定制的Hash函數(shù)：SHA-1

安全Hash算法(SHA)是美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)設(shè)計，并于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS180)發(fā)布的。后做修改，于1995年再次公布修訂后的SHA，通常稱為SHA-1。3無密鑰密碼Hash函數(shù)：MDC(續(xù))78謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1安全Hash算法3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1算法的輸入為小于264比特長的任意消息，輸出為160比特的消息摘要，算法處理過程如下圖。YL-13無密鑰密碼Hash函數(shù)：MDC(續(xù))HSHAIV(160比特)Y0(512比特)HSHAY1CV1(160比特)…HSHACVqYq…CV2HSHACVL-1消息摘要79謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數(shù)減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數(shù)在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。這形成了長度為512比特的一系列分組Y0，Y1，…，YL-1。需要產(chǎn)生Hash值的消息100…0消息長度K填充長度1-512比特K比特L×512比特3無密鑰密碼Hash函數(shù)：MDC(續(xù))80謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))

(2)初始化。SHA-1使用160比特的緩沖區(qū)存儲中間和最終Hash值，可用5個32比特寄存器A，B，C，D，E表示，初始值為(十六進制)A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。3無密鑰密碼Hash函數(shù)：MDC(續(xù))81謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))(2)初3.2定制的Hash函數(shù)：SHA-1(續(xù))

(3)處理。每個分組Yq經(jīng)過壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過程構(gòu)成。每一輪又由20步迭代組成。4輪處理結(jié)構(gòu)一樣，但基本邏輯函數(shù)不同，分別為f1，f2，f3，f4。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D、E的當(dāng)前值，輸出仍放在對應(yīng)緩沖區(qū)。每一輪處理有一個加法常量Ki，其中t表示迭代步數(shù)，0≤t≤79。第4輪的輸出與第1輪的輸入CVq依5個緩沖區(qū)對應(yīng)進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是160比特消息摘要。3無密鑰密碼Hash函數(shù)：MDC(續(xù))82謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))(3)3.2定制的Hash函數(shù)：SHA-1(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))CVq160位Yq512位f1,K1,W[0…19]20步BADCEf2,K2,W[20…39]20步BADCEf3,K3,W[40…59]20步BADCEf4,K4,W[60…79]20步BADCE++++CVq+1160位+83謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))3無密鑰密碼H3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1的壓縮函數(shù)各個20步迭代運算的每一步運算可以表示為

A，B，C，D，E←(E+fi(B，C，D)+CLS5(A)+Wt+Ki)，A，CLS30(B)，C，D

其中，t是迭代的步數(shù)(0≤t≤79)，+是模232相加，fi是i(1≤i≤4)輪的基本邏輯函數(shù)，CLSs表示循環(huán)左移s位，Wt是當(dāng)前512比特分組導(dǎo)出的一個32比特字。3無密鑰密碼Hash函數(shù)：MDC(續(xù))84謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-13.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-1的壓縮函數(shù)(續(xù))基本邏輯函數(shù)f1，f2，f3，f4分別定義為：f1(X，Y，Z)=(XY)(XZ)f2(X，Y，Z)=f4(X，Y，Z)=XYZf3(X，Y，Z)=(XY)(XZ)(YZ)其中，是與，是或，是異或，是非。3無密鑰密碼Hash函數(shù)：MDC(續(xù))85謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-1的壓縮3.2定制的Hash函數(shù)：SHA-1(續(xù))

SHA-1的壓縮函數(shù)(續(xù))

加法常量(十六進制)

K1=5a827999，對應(yīng)0≤t≤19

K2=6ed9eba1，對應(yīng)20≤t≤39

K3=8f1bbcdc

，對應(yīng)40≤t≤59

K4=

ca62c1d6，對應(yīng)60≤t≤79

字?jǐn)U展前16個字W0，W1，…，W15，直接由輸入得到。其余由公式Wt=CLS1(Wt-3Wt-8Wt-14Wt-16)依次得到。3無密鑰密碼Hash函數(shù)：MDC(續(xù))86謝謝您的觀賞2019-8-293.2定制的Hash函數(shù)：SHA-1(續(xù))SHA-3.3定制的Hash函數(shù)：MD5

MD5是1992年由Rivest提出的無密鑰Hash函數(shù)。MD5是MD4(1990年提出)的增強版本。MD5對任意長度的消息產(chǎn)生128比特的Hash值。MD4在280次壓縮函數(shù)計算下已經(jīng)找到了碰撞，因此，不在被推薦用做抗碰撞的Hash函數(shù)。近年來，MD5也發(fā)現(xiàn)了一些弱點。3無密鑰密碼Hash函數(shù)：MDC(續(xù))87謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5MD5是1992年由3.3定制的Hash函數(shù)：MD5(續(xù))MD5算法的輸入為任意比特長的消息，輸出為128比特的消息摘要，算法處理過程如下圖。3無密鑰密碼Hash函數(shù)：MDC(續(xù))HMD5IV(128比特)Y0(512比特)HMD5Y1CV1(128比特)…HMD5CVqYq…CV2HMD5CVL-1YL-1消息摘要88謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5算法的3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))MD5消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數(shù)減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數(shù)在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。如果消息長度大于264，則以264取模。這形成了長度為512比特的一系列分組Y0，Y1，…

，YL-1。需要產(chǎn)生Hash值的消息100…0消息長度Kmod264填充長度1-512比特K比特L×512比特=N×32比特89謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))

(2)初始化。MD5使用128比特的緩沖區(qū)存儲中間和最終Hash值，可用4個32比特寄存器A，B，C，D表示，初始值為(十六進制)A=01234567，B=89abcdef，C=fedcba98，D=76543210。3無密鑰密碼Hash函數(shù)：MDC(續(xù))90謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))(2)初始化3.3定制的Hash函數(shù)：MD5(續(xù))

(3)處理。每個分組Yq經(jīng)過壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過程構(gòu)成。每一輪又由16步迭代組成。4輪處理結(jié)構(gòu)一樣，但基本邏輯函數(shù)不同，分別為F，G，H，I

。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D的當(dāng)前值，輸出仍放在對應(yīng)緩沖區(qū)。每一輪處理有一個常量T[i]，其中i表示迭代步數(shù)，1≤i≤64。第4輪的輸出與第1輪的輸入CVq依4個緩沖區(qū)對應(yīng)進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是128比特消息摘要。3無密鑰密碼Hash函數(shù)：MDC(續(xù))91謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))(3)處理。3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))CVq128位Yq512位F,T[1…16],X[i],16步BADCBADCBADCBADC++++CVq+1128位G,T[17…32],X[p2(i)],16步H,T[33…48],X[p3(i)],16步I,T[49…64],X[p4(i)],16步92謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Hash函數(shù)：MDC(續(xù))MD5的壓縮函數(shù)一步迭代壓縮函數(shù)如下圖。ACBD+++<<<s+RACBDX[k]T[i]

R表示函數(shù)F、G、H、I中的一個，它們依次在連續(xù)16步中使用<<<s表示循環(huán)左移s比特X[k]表示在第q個長度為512比特分組中的第k個32比特分組T[i]表示常數(shù)中的第i個字

+表示模232相加93謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數(shù)：MD5(續(xù))

MD5的壓縮函數(shù)(續(xù))邏輯函數(shù)F，G，H，I分別定義為：

F(X，Y，Z)=(XY)(XZ)G(X，Y，Z)=(XY)(YZ)H(X，Y，Z)=XYZI(X，Y，Z)=Y(XZ)

T[i]定義為：

T[i]=232|sin(i)|，i=1,2,…,64，這里，i是弧度。

3無密鑰密碼Hash函數(shù)：MDC(續(xù))94謝謝您的觀賞2019-8-293.3定制的Hash函數(shù)：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數(shù)：