信息技術(shù)-趙澤茂-第四章

1、4.1 Hash函數(shù)4.2 消息認(rèn)證碼4.3 MD5算法4.4 SHA-1算法4.5 Hash函數(shù)的攻擊分析小結(jié)習(xí)題消息摘要要函數(shù)、散列函函數(shù)或雜雜湊函數(shù)數(shù)，記為為h=H(M)。我們們把Hash函函數(shù)值h稱為輸輸入數(shù)據(jù)據(jù)M的“數(shù)字指指紋”。Hash函函數(shù)的這這種單向向性特征征和輸出出數(shù)據(jù)長長度固定定的特征征使得它它可以用用于檢驗(yàn)驗(yàn)消息的的完整性性是否遭遭到破壞壞。如果果消息或或數(shù)據(jù)被被篡改，那么數(shù)數(shù)字指紋紋就不正正確了。4.1Hash函函數(shù)用做消息息認(rèn)證的的Hash函數(shù)數(shù)具有如如下一些些性質(zhì): (1)消消息M可可以是任任意長度度的數(shù)據(jù)據(jù)。(2)給給定消息息M，計(jì)計(jì)算它的的Hash函數(shù)數(shù)值h=H

2、(M)是很很容易的的。(3) 任意意給定，則很很難找到到M使得得h=H(M)，即給給出Hash函函數(shù)值，要求輸輸入M在在計(jì)算上上是不可可行的。 這說說明Hash函函數(shù)的運(yùn)運(yùn)算過程程是不可可逆的，這種性性質(zhì)被稱稱為函數(shù)數(shù)的單向向性。(4)給給定消息息M和其其Hash函數(shù)數(shù)值H(M)，要找到到另一個(gè)個(gè)M，且MM，使得H(M)=H(M) 在計(jì)計(jì)算上是是不可行行的，這這條性質(zhì)質(zhì)被稱為為抗弱碰碰撞性?？谷跖鲎沧残员ＷC證對(duì)于一一個(gè)消息息M及其其Hash函數(shù)數(shù)值，無無法找到到一個(gè)替替代消息息M，使它的的Hash函數(shù)數(shù)值與給給定的Hash函數(shù)值值相同。這條性性質(zhì)可用用于防止止偽造?？箍箯?qiáng)強(qiáng)碰撞性性對(duì)于消消息H

3、ash函函數(shù)的安安全性要要求更高高。這這條性質(zhì)質(zhì)保證了了對(duì)生日日攻擊方方法的防防御能力力。碰撞性是是指對(duì)于于兩個(gè)不不同的消消息M和和M，如果它它們的摘摘要值相相同，則則發(fā)生了了碰撞。雖雖然可可能的消消息是無無限的，但可能能的摘要要值卻是是有限的的。如Hash函數(shù)MD5，其Hash函函數(shù)值長長度為128位位，不同同的Hash函函數(shù)值個(gè)個(gè)數(shù)為2128。因此，不同的的消息可可能會(huì)產(chǎn)產(chǎn)生同一一摘要，碰撞是是可能存存在的。但是，Hash函數(shù)數(shù)要求用用戶不能能按既定定需要找找到一個(gè)個(gè)碰撞，意外的的碰撞更更是不太太可能的的。顯然然，從安安全性的的角度來來看，Hash函數(shù)輸輸出的比比特越長長，抗碰碰撞的安安全

4、強(qiáng)度度越大。4.1.1一一個(gè)簡簡單的Hash函數(shù)基于安全全強(qiáng)度的的需要，現(xiàn)有的的Hash函數(shù)數(shù)一般都都十分復(fù)復(fù)雜。本本節(jié)我們們介紹一一個(gè)簡單單的Hash函函數(shù)，便便于建立立對(duì)Hash函函數(shù)的感感性認(rèn)識(shí)識(shí)。對(duì)對(duì)于明文文m，按按每組n比特進(jìn)進(jìn)行劃分分，如果果最后一一組長度度不夠，則補(bǔ)充充0。不不妨設(shè)劃劃分為r組，mi=mi1，mi2， ，min，1ir，mij=0或1，然后后將各分分組逐比比特進(jìn)行行模2加加運(yùn)算，則輸出出為h=h1，h2，hn，其中中h1=m11+m21+mr1(mod 2)，hn=m1n+m2n+mm(mod 2)。從從定義可可見，hi表示所有有分組的的第i比比特進(jìn)行行模2加加，

5、因此此，若消消息改變變，摘要要值也會(huì)會(huì)隨之改改變。一個(gè)例外外的情況況是，若若消息出出錯(cuò)，而而摘要值值仍然不不變的概概率為2-n。當(dāng)n充充分大時(shí)時(shí)，出錯(cuò)錯(cuò)的概率率或者說說消息被被篡改的的概率非非常小，視為小小概率事事件，可可忽略不不計(jì)。4.1.2完完整性性檢驗(yàn)的的一般方方法消息完整整性檢驗(yàn)驗(yàn)的一般般機(jī)制如如圖4-1-1所示。無論是是存儲(chǔ)文文件還是是傳輸文文件，都都需要同同時(shí)存儲(chǔ)儲(chǔ)或發(fā)送送該文件件的數(shù)字字指紋; 驗(yàn)證證時(shí)，對(duì)對(duì)于實(shí)際際得到的的文件重重新產(chǎn)生生其數(shù)字字指紋，再與原原數(shù)字指指紋進(jìn)行行對(duì)比，如果一一致，則則說明文文件是完完整的，否則，是不完完整的。圖 4-1-1 消息完整性檢驗(yàn)的一般機(jī)制

6、 在4.1節(jié)中我我們簡單單介紹了了消息的的完整性性檢驗(yàn)，這只能能檢驗(yàn)消消息是否否是完整整的，不不能說明明消息是是否是偽偽造的。因?yàn)?，一個(gè)偽偽造的消消息與其其對(duì)應(yīng)的的數(shù)字指指紋也是是匹配的的。消息息認(rèn)證具具有兩層層含義: 一是是檢驗(yàn)消消息的來來源是真真實(shí)的，即對(duì)消消息的發(fā)發(fā)送者的的身份進(jìn)進(jìn)行認(rèn)證證;二二是檢驗(yàn)驗(yàn)消息是是完整的的，即驗(yàn)驗(yàn)證消息息在傳送送或存儲(chǔ)儲(chǔ)過程中中未被篡篡改、刪刪除或插插入等。4.2消消息息認(rèn)認(rèn) 證碼碼產(chǎn)生消息息的數(shù)字字指紋的的方法很很多。當(dāng)當(dāng)需要進(jìn)進(jìn)行消息息認(rèn)證時(shí)時(shí)，僅有有消息作作為輸入入是不夠夠的，需需要加入入密鑰K，這就就是消息息認(rèn)證的的原理。能否認(rèn)認(rèn)證，關(guān)關(guān)鍵在于于信息

7、發(fā)發(fā)送者或或信息提提供者是是否擁有有密鑰K。消消息認(rèn)證證碼(Message Authentication Code，MAC)通常常表示為為MAC=CK(M)其中中:M是長度度可變的的消息; K是是收、發(fā)發(fā)雙方共共享的密密鑰;函函數(shù)數(shù)值CK(M)是是定長的的認(rèn)證碼碼，也稱稱為密碼碼校驗(yàn)和和。MAC是帶帶密鑰的的消息摘摘要函數(shù)數(shù)，即一一種帶密密鑰的數(shù)數(shù)字指紋紋，它與與不帶密密鑰的數(shù)數(shù)字指紋紋是有本本質(zhì)區(qū)別別的。1.消消息認(rèn)認(rèn)證認(rèn)認(rèn)證碼被被附加到到消息后后以MMAC方式一一并發(fā)送送，接收收方通過過重新計(jì)計(jì)算MAC以實(shí)實(shí)現(xiàn)對(duì)M的認(rèn)證證，如圖圖4-2-1所所示。圖 4-2-1 消息認(rèn)證假定收、發(fā)雙方方共

8、享密密鑰K，如果接接收方收收到的MAC與與計(jì)算得得出的MAC一一致，那那么可以以得出如如下結(jié)論論:(1) 接收收方確信信消息M未被篡篡改。此此為完整整性驗(yàn)證證。(2)接接收方方確信消消息來自自所聲稱稱的發(fā)送送者，因因?yàn)闆]有有其他人人知道這這個(gè)共享享密鑰，所以其其他人也也就不可可能為消消息M附附加合適適的MAC。此此為消息息源驗(yàn)證證。2.消消息認(rèn)認(rèn)證與保保密在在消息認(rèn)認(rèn)證中，消息以以明文方方式傳送送，這一一過程只只提供認(rèn)認(rèn)證而不不具備保保密性。如圖4-2-2所示示提供了了一種既既加密又又認(rèn)證的的方式，發(fā)送方方發(fā)送EK2(M)CK1(M)。該該種處處理方式式除具備備息認(rèn)證證的功能能外，還還具有保保

9、密性。圖 4-2-2 消息認(rèn)證與保密3.密密文認(rèn)認(rèn)證改變消息息認(rèn)證與與保密中中加密的的位置，得到另另外一種種消息保保密與認(rèn)認(rèn)證方式式，即密密文認(rèn)證證，如圖圖4-2-3所所示。該該種處理理方式先先對(duì)消息息進(jìn)行加加密，然然后再對(duì)對(duì)密文計(jì)計(jì)算MAC，傳傳送EK2(M)CK1(EK2(M)給接收收方。接接收方先先對(duì)收到到的密文文進(jìn)行認(rèn)認(rèn)證，認(rèn)認(rèn)證成功功后，再再解密。圖 4-2-3 密文認(rèn)證MD表示示消息摘摘要(Message Digest，MD)。 MD4算法法是1990年年由RonRivest設(shè)設(shè)計(jì)的一一個(gè)消息息摘要算算法，該該算法的的設(shè)計(jì)不不依賴于于任何密密碼體制制，采用用分組方方式進(jìn)行行各種邏邏

10、輯運(yùn)運(yùn)算而得得到。1991年MD4算法法又得到到了進(jìn)一一步的改改進(jìn)，改改進(jìn)后的的算法就就是MD5算法法。MD5算法法以512bit為為一塊的的方式處處理輸入入的消息息文本，每個(gè)塊塊又劃分分為16個(gè)32 bit的子子塊。算算法的輸輸出是由由4個(gè)32bit的的塊組成成的，將將它們級(jí)級(jí)聯(lián)成一一個(gè)128bit的的摘要值值。MD5算法法如圖4-3-1所示示，包括括以下幾幾個(gè)步驟驟。4.3MD5算法法圖 4-3-1 MD5算法(1)填填充消消息使其其長度正正好為512bit的整數(shù)數(shù)倍L。首首先在在消息的的末尾處處附上64bit的的消息長長度的二二進(jìn)制表表示，大大小為n(mod264)，n表表示消息息長度。

11、然后在在消息后后面填充充一個(gè)“1”和和多個(gè)“0”，填充后后的消息息恰好是是512 bit的整整數(shù)倍倍長L。Y0，Y1，YL-1表示不同同的512bit長長的消息息塊，用用M0，M1，MN1表示各各個(gè)Yq中按32bit分分組的字字，N一一定是16的整整數(shù)倍。(2)初初始化化緩沖區(qū)區(qū)。算算法法中使用用了128bit的的緩沖區(qū)區(qū)，每個(gè)個(gè)緩沖區(qū)區(qū)由4個(gè)個(gè)32bit的寄存存器A、B、C、D組組成，先先把這4個(gè)寄存存器初始始化為A=01234567B=89ABCDEFC=FEDCBA98D=76543210(3)處處理512bit消息塊塊Yq，進(jìn)入主主循環(huán)。主主循環(huán)環(huán)的次數(shù)數(shù)正好是是消息中中512 bit

12、的塊塊的數(shù)目目L。先先從Y0開開始，上上一循環(huán)環(huán)的輸出出作為下下一循環(huán)環(huán)的輸入入，直到到處理完完YL-1為止。消消息塊塊Yq的處理，以當(dāng)前前的512bit數(shù)數(shù)據(jù)塊Yq和128 bit緩沖沖值A(chǔ)、B、C、D作作為輸入入，并修修改緩沖沖值的內(nèi)內(nèi)容。消消息塊的的處理包包含4輪輪操作，每一輪輪由16次迭代代操作組組成，上上一輪的的輸出出作為下下一輪的的輸入，如圖4-3-2所示示。4輪輪處理具具有相似似的結(jié)構(gòu)構(gòu)，但每每輪處理理使用不不同的非非線性函函數(shù)，如如圖4-3-3所示。圖 4-3-2 消息塊處理的主循環(huán)圖 4-3-3 某一輪的執(zhí)行過程4個(gè)非線線性函數(shù)數(shù)分別為為F(X，Y，Z)=(XY)(Z)G(X

13、，Y，Z)=(XZ)(Y)H(X，Y，Z)=XYZI(X，Y，Z)=Y(X)各各種運(yùn)運(yùn)算符號(hào)號(hào)的含義義:XY表示示X與Y按位邏邏輯“與與”;XY表示示X與Y按位邏邏輯“或或”;XY表表示X與與Y按位位邏輯“異或”;表表示X按按位邏輯輯“補(bǔ)”;X+Y表示整整數(shù)模232加法運(yùn)運(yùn)算;Xs表示將X循環(huán)左左移s個(gè)個(gè)位置。常數(shù)表Ti(1i64)共共有64個(gè)元素素，每個(gè)個(gè)元素長長為32 bit，Ti232ABS(sin(i)，其中i是弧度度。處處理每每一個(gè)消消息塊Yi時(shí)，每一一輪使用用常數(shù)表表Ti中的的16個(gè)個(gè)，正好好用4輪輪。(4)輸輸出。每每一輪輪不斷地地更新緩緩沖區(qū)A、B、C、D中的內(nèi)內(nèi)容，4輪之后后

14、進(jìn)入下下一個(gè)主主循環(huán)，直到處處理完所所有消息息塊為止止。最后后輸出的的就是運(yùn)運(yùn)算結(jié)束束時(shí)緩沖沖區(qū)中的的內(nèi)容。SHA(Secure Hash Algorithm，SHA)由美國NIST開發(fā)，作為聯(lián)邦信息處理標(biāo)準(zhǔn)于1993年發(fā)表，1995年修訂后，成為SHA1版本。SHA1算法在設(shè)計(jì)方面基本上是模仿MD5算法，如圖4-4-1所示，包含以下幾個(gè)過程。4.4 SHA-1算法圖 4-4-1 SHA1算法(1)填填充消消息。首首先將消消息填充充為512的整整數(shù)倍，填充方方法與MD5算算法相同同。與MD5算算法不同同的是SHA-1的輸輸入為長長度小于于264 bit的消消息。(2)初初始化緩緩沖區(qū)。初初始化

15、化160 bit的消消息摘要要緩沖區(qū)區(qū)(即設(shè)設(shè)定IV值)，該緩沖沖區(qū)用于于保存中中間和最最終摘要要結(jié)果。每個(gè)緩緩沖區(qū)由由5個(gè)32bit的的寄存器器A、B、C、D、E組成，初始化化為A=67452301B=EFCDAB89C=98BADCFED=10325476E=C2D2E1F0(3)處處理512bit消息塊塊Yq，進(jìn)入主主循環(huán)。主主循環(huán)環(huán)的次數(shù)數(shù)正好是是消息中中512 bit的塊塊的數(shù)目目L。先先從Y0開始，以以上一循循環(huán)的輸輸出作為為下一循循環(huán)的輸輸入，直直到處理理完YL-1為止。主主循環(huán)環(huán)有4輪輪，每輪輪20次次操作(MD5算法有4輪，每每輪16次操作作)。每每次操作作對(duì)A、B、C、D和

16、E中的3個(gè)做一一次非線線性函數(shù)數(shù)運(yùn)算，然后進(jìn)進(jìn)行與MD5算算法中類類似的移移位運(yùn)算算和加運(yùn)運(yùn)算。四個(gè)非線線性函數(shù)數(shù)為ft(X，Y，Z)=(XY)(Z)(0t19)ft(X，Y，Z)=XYZ(20t39)ft(X，Y，Z)=(XY)(XZ)(YZ)(40t59)ft(X，Y，Z)=XYZ(60t79)該該算法使使用了常常數(shù)序列列Kt(0t79)，分分別為Kt=5a827999(0t19)Kt=6ed9eba1(20t39)Kt=8f1bbcdc(40t59)Kt=ca62c1d6(60t79)用下面的的算法將將消息塊塊從16個(gè)32 bit子塊塊變成80個(gè)32bit子子塊(W0到W79):Wt=M

17、t(0t15)Wt=(Wt-3Wt-8Wt-14Wt-16)1(16t79)該算法主主循環(huán)4輪，每每輪20次，0t79，每一一次的變變換的基基本形式式是相同同的:A(E+ft(B，C，D)+(A5)+Wt+KtB=AC=(B30)D=CE=D其其中:(A5)表示寄寄存器A循環(huán)左左移5bit，(B30)表示寄寄存器K循環(huán)左左移30 bit。80次次處理完完后，處處理下一一個(gè)512bit的的數(shù)據(jù)塊塊，直到到處理完完YL-1為止。最最后輸出出ABCDE級(jí)聯(lián)聯(lián)后的結(jié)結(jié)果。SHA-1算法法與MD5算法法的比較較如表4-4-1所示示。表4-4-1 SHA-1算法與MD5算法的比較 Hash函數(shù)須須滿足4.

18、1節(jié)節(jié)的5條條性質(zhì)，然而，抗強(qiáng)碰碰撞性對(duì)對(duì)于消息息Hash函數(shù)數(shù)的安全全性要求求是非常常高的。例如，MD5算法輸輸出的Hash函數(shù)值值總數(shù)為為2128，SHA-1算算法輸出出的Hash函函數(shù)值總總數(shù)為2160，這說明明可能Hash函數(shù)值值是有限限的，而而輸入的的消息是是無限的的，因此此，函數(shù)數(shù)的碰撞撞性是可可能存在在的。評(píng)評(píng)價(jià)Hash函數(shù)的的一個(gè)最最好的方方法是看看攻擊者者找到一一對(duì)碰撞撞消息所所花的代代價(jià)有多多大。一一般地，假設(shè)攻攻擊者知知道Hash函函數(shù)，攻攻擊者的的主要目目標(biāo)是找找到一對(duì)對(duì)或更多多對(duì)碰撞撞消息。目前前已有一一些攻擊擊Hash函數(shù)數(shù)的方案案和計(jì)算算碰撞消消息的方方法，這這些

19、方法法中的生生日攻擊擊方法可可用于攻攻擊任何何類型的的Hash函數(shù)數(shù)方案。4.5Hash函函數(shù)的攻攻擊分析析生日攻擊擊方法只只依賴于于消息摘摘要的長長度，即即Hash函數(shù)數(shù)值的長長度。生生日攻擊擊給出消消息摘要要長度的的一個(gè)下下界。一一個(gè)40 bit長的的消息摘摘要是很很不安全全的，因因?yàn)閮H僅僅用220(大約一一百萬)次Hash函函數(shù)值的的隨機(jī)計(jì)計(jì)算就可可至少以以1/2的概率率找到一一對(duì)碰撞撞。為了了抵抗生生日攻擊擊，通常常建議消消息摘要要的長度度至少應(yīng)應(yīng)為128bit，此時(shí)生生日攻擊擊需要約約264次Hash函數(shù)數(shù)值的計(jì)計(jì)算。除生日攻攻擊法外外，對(duì)一一些類型型的Hash函函數(shù)還有有一些特特殊

20、的攻攻擊方法法，例如如，中間間相遇攻攻擊法、修正分分組攻擊擊法和差差分分析析法等。值得一一提的是是，山東東大學(xué)王王小云教教授等人人于2004年年8月在在美國加加州召開開的國際際密碼大大會(huì)(Crypto2004)上上所做的的Hash函數(shù)數(shù)研究報(bào)報(bào)告中指指出，他他們已成成功破譯譯了MD4、MD5、HAVAL128、RIPEMD128等等Hash算法法。最近近國際密密碼學(xué)家家Lenstra利用用王小云云等人提提供的MD5碰碰撞，偽偽造了符符合X.509標(biāo)準(zhǔn)的的數(shù)字證證書，這這就說明明了MD5算法法的破譯譯已經(jīng)不不僅僅是是理論破破譯結(jié)果果，而是是可以導(dǎo)導(dǎo)致實(shí)際際的攻擊擊，MD5算法法的撤出出迫在眉眉睫

21、。他他們的研研究成果果得到了了國際密密碼學(xué)界界專家的的高度評(píng)評(píng)價(jià)，他他們找到到的碰撞撞基本上上宣布了了MD5算法的的終結(jié)，這一成成就或許許是近年年來密碼碼學(xué)界最最具實(shí)質(zhì)質(zhì)性的研研究進(jìn)展展。在MD5算法被被以王小小云為代代表的中中國專家家攻破之之后，世世界密碼碼學(xué)界仍仍然認(rèn)為為SHA-1算算法是安安全的。2006年2月，美美國國家家標(biāo)準(zhǔn)技技術(shù)研究究院發(fā)表表申明，SHA-1算算法沒有有被攻破破，并且且沒有足足夠的理理由懷疑疑它會(huì)很很快被攻攻破，開開發(fā)人員員在2010年年前應(yīng)該該轉(zhuǎn)向更更為安全全的SHA-256和和SHA-512算法法。然而而，一周周之后，王小云云就宣布布了攻破破SHA-1算算法的消消息。因因?yàn)镾HA-1算法在在美國等等國家有有更加廣廣泛的應(yīng)應(yīng)用，密密碼被破破的消息息一出，在國際際上的反反響可謂謂石破天天驚。換換句話說說，王小小云的研研究成果果表明了了電子簽簽名從理理論上講講是可以以偽造的的，必須須及時(shí)添添加限制制條件，或者重重新選用用更為安安全的密密碼標(biāo)準(zhǔn)準(zhǔn)，以保保證電子子商務(wù)的的安全。(1)用用做消消息認(rèn)證證的摘要要函數(shù)具具有單向向性、抗抗碰撞性性。單向向函數(shù)的的優(yōu)良性性質(zhì)，使使其成為為公鑰密密碼、消消息壓縮縮的數(shù)學(xué)學(xué)基礎(chǔ)。(2)消消息認(rèn)證證碼特指指使用收收、發(fā)雙雙方共享享的密鑰鑰K和長長度可變變的消息息M，輸輸出長度度固定的