9-認(rèn)證理論與技術(shù)-Hash函數(shù)

1第7章認(rèn)證理論與技術(shù)

----Hash函數(shù)2上講內(nèi)容回顧公鑰密碼算法概念RSA公鑰密碼算法3本章主要內(nèi)容單向函數(shù)Hash函數(shù)的定義及發(fā)展現(xiàn)狀SHA-1算法hash函數(shù)的用途消息認(rèn)證碼簡(jiǎn)介CBC-MAC算法HMAC算法4定義.

函數(shù)若滿足下列兩個(gè)條件，則稱之為強(qiáng)單向函數(shù)：1計(jì)算是容易的，即是多項(xiàng)式時(shí)間可計(jì)算的；2計(jì)算函數(shù)的逆是困難的，即對(duì)每一多項(xiàng)式時(shí)間概率算法，每一多項(xiàng)式和充分大的有單向函數(shù)5單向函數(shù)注.1可能有少量x給出的f(x)可用多項(xiàng)式時(shí)間概率算法求逆；2單向函數(shù)的存在性沒(méi)有理論上的證明，但是有些函數(shù)，經(jīng)過(guò)實(shí)踐檢驗(yàn)，至今沒(méi)有發(fā)現(xiàn)多項(xiàng)式時(shí)間的求逆算法，仍在使用.例1偽隨機(jī)數(shù)生成器(種子密鑰—密鑰流)例2因子分解問(wèn)題（因子—合數(shù)）6Hash函數(shù)定義消息是任意有限長(zhǎng)度，哈希值是固定長(zhǎng)度.Hash的概念起源于1956年，Dumey用它來(lái)解決symboltablequestion(符號(hào)表問(wèn)題)。使得數(shù)據(jù)表的插入、刪除、查詢操作可以在平均常數(shù)時(shí)間完成。1A3FD4128A198FB3CA345932Thisisaninputtoacrypto-graphichashfunction.Theinputisaverylongstring,thatisreducedbythehashfunctiontoastringoffixedlength.Thereareadditionalsecurityconditions:itshouldbeveryhardtofindaninputhashingtoagivenvalue(apreimage)ortofindtwocollidinginputs(acollision).h7Hash函數(shù)的定義單向性（抗原像）：對(duì)干任意給定的消息，計(jì)算其哈希值容易.但是，對(duì)于給定的哈希值h，要找到M使得H(M)＝h在計(jì)算上是不可行的.

弱抗碰撞（抗二次原像）：對(duì)于給定的消息M1，要發(fā)現(xiàn)另一個(gè)消息M2，滿足H(M1)＝H(M2)在計(jì)算上是不可行的.強(qiáng)抗碰撞：找任意一對(duì)不同的消息M1，M2

，使H(M1)＝H(M2)在計(jì)算上是不可行的.隨機(jī)性.8Hash函數(shù)的定義Moutputh由m計(jì)算h(m)容易H(M)outputhM由h(m)計(jì)算上m不容易H(M)9Hash函數(shù)的定義outputhH抗弱碰撞性M給定H(M)mm‘10Hash函數(shù)的定義outputH(m)=H(m’)H抗強(qiáng)碰撞性Mmm‘11Hash函數(shù)的定義Hash函數(shù)的分類不帶密鑰的哈希函數(shù)主要用于消息完整性帶密鑰的哈希函數(shù)主要用于消息源認(rèn)證和消息完整性通常說(shuō)Hash函數(shù)，就是不帶密鑰的hash函數(shù)12Hash函數(shù)的用途消息完整性檢測(cè)Hash鏈用于口令認(rèn)證數(shù)字簽名（速度快；防止消息偽造）消息源認(rèn)證（MAC）。。。。。。13Hash函數(shù)的用途消息完整性檢測(cè)

“網(wǎng)站衛(wèi)士”是一個(gè)網(wǎng)絡(luò)安全軟件產(chǎn)品。它的主要功能是通過(guò)網(wǎng)絡(luò)掃描網(wǎng)站的網(wǎng)頁(yè)，監(jiān)測(cè)網(wǎng)頁(yè)是否被修改，當(dāng)發(fā)現(xiàn)網(wǎng)頁(yè)被修改后，系統(tǒng)能夠自動(dòng)報(bào)警和恢復(fù)。初始化過(guò)程（1）對(duì)監(jiān)視網(wǎng)站的文件備份到監(jiān)控主機(jī)上。（2）對(duì)每個(gè)備份的文件生成一個(gè)結(jié)構(gòu)：文件位置、文件的哈希值。監(jiān)控過(guò)程監(jiān)控主機(jī)對(duì)監(jiān)控網(wǎng)站進(jìn)行輪回掃描，對(duì)掃描的文件進(jìn)行如下操作：（1）計(jì)算文件的哈希值，并與備份的文件哈希值進(jìn)行比較，如果相同，轉(zhuǎn)（4）步。（2）如果不同，上載備份文件替換網(wǎng)站現(xiàn)有文件，轉(zhuǎn)（4）步。（3）如果備份文件不存在，則刪除網(wǎng)站上這個(gè)文件，轉(zhuǎn)（4）步。（4）監(jiān)控程序掃描下一文件。14Hash函數(shù)的用途消息完整性檢測(cè)15Hash函數(shù)的用途口令認(rèn)證

常見(jiàn)的Unix系統(tǒng)口令以及多數(shù)論壇/社區(qū)系統(tǒng)口令都是經(jīng)MD5處理后保存其摘要信息串；16不帶密鑰的哈希函數(shù)的發(fā)展1978年，Merkle和Damagad設(shè)計(jì)MD迭代結(jié)構(gòu)

1993年，來(lái)學(xué)嘉和Messay改進(jìn)為MD加強(qiáng)結(jié)構(gòu)17不帶密鑰的哈希函數(shù)的發(fā)展1．MessageDigest（MD）系列MD系列是由國(guó)際著名密碼學(xué)家圖靈獎(jiǎng)獲得者兼公鑰加密算法RSA的創(chuàng)始人Rivest設(shè)計(jì)，包括MD2（1989年針對(duì)8位計(jì)算機(jī)上實(shí)現(xiàn)），MD4（1990年針對(duì)32位計(jì)算機(jī)上實(shí)現(xiàn)）和MD5（1991年提出的，是對(duì)MD4的改進(jìn)版，包括其哈希值為128位）。18不帶密鑰的哈希函數(shù)的發(fā)展SHA系列算法是NIST根據(jù)Rivest設(shè)計(jì)的MD4和MD5開(kāi)發(fā)的算法.國(guó)家安全當(dāng)局發(fā)布SHA作為美國(guó)政府標(biāo)準(zhǔn).SHA表示安全散列算法.

SHA（SecurityHashAlgorithm）系列SHA-0

SHA-0正式地稱作SHA，這個(gè)版本在發(fā)行后不久被指出存在弱點(diǎn).SHA-1SHA-1是NIST于1994年發(fā)布的，它與MD4和MD5散列算法非常相似，被認(rèn)為是MD4和MD5的后繼者.散列值為160bitsSHA-2

SHA-2實(shí)際上分為SHA-224、SHA-256、SHA-384和SHA-512算法.SHA-3SHA-3實(shí)際上分為SHA3-224、SHA3-256、SHA3-384和SHA3-512算法.

193.其它算列算法HAVAL可以用來(lái)實(shí)現(xiàn)可變成的輸出，RIPEMD-128、RIPEMD-160是歐洲研究者提出，替代MD5和MD4算法，Tiger算法主要是設(shè)計(jì)思想是在64位和32位計(jì)算機(jī)上能夠很好的使用Hash算法。不帶密鑰的哈希函數(shù)的發(fā)展20不帶密鑰的哈希函數(shù)

碰撞攻擊復(fù)雜度Hash函數(shù)哈希值長(zhǎng)度安全強(qiáng)度Collision原像第二原像SHA-1160<80160160-L(M)SHA-224224112224Min(224,256-L(M))SHA-256256128256256-L(M)SHA-384384192384384SHA-512512256512512-L(M)SHA3-224224112224224SHA3-256256128256256SHA3-384384192384384SHA3-512512256512512表7-6SHA系列算法安全參數(shù)列表21主要hash算法：HAVALMD5SHA-1SHA-2Ext.MD4RIPEMDRIPEMD-160MD4TigerWhirlpool不帶密鑰的哈希函數(shù)的發(fā)展SHA-322SHA系列(SecureHashAlgorithm)SHA-1，SHA-256，SHA-384，SHA-512SHA-1，SHA-256的分組大小是512SHA-384，SHA-512的分組大小是1024SHA-1輸出的摘要是160bitSHA-256輸出的摘要是256bitSHA-384輸出的摘要是384bitSHA-512輸出的摘要是512bit23SHA1

算法原理

分段運(yùn)算：512bits

雜湊值長(zhǎng)度：160bits

初始向量：160bitsSHA-1哈希算法每個(gè)分塊512比特，最后一個(gè)分塊中最后64比特記錄數(shù)據(jù)長(zhǎng)度。任意有限長(zhǎng)度消息輸入，如何分512比特的塊。SHA-1哈希算法24填充之后的消息M’是512bit的整數(shù)倍初始變量IV，160bits，分為5個(gè)緩沖區(qū)存放。采用十六進(jìn)制表示25數(shù)據(jù)擴(kuò)充之后，總共80個(gè)字總共循環(huán)80次，邏輯函數(shù)ft和常量K[4]每20次變換一次26

SHA-1算法第一步：填充消息

27填充實(shí)例

abc填充數(shù)據(jù)消息長(zhǎng)度64bits填充后消息是512bits的整數(shù)倍（原始消息比特長(zhǎng)度+填充數(shù)據(jù)比特長(zhǎng)度）mod512=448（原始消息字節(jié)長(zhǎng)度+填充數(shù)據(jù)字節(jié)長(zhǎng)度）mod64=56

（2）被填充消息分組

28512bits分為16塊，每塊32bits（1個(gè)字）（3）初始化變量

2930SHA-1算法512-bit分塊處理過(guò)程SHA-1算法

FIPSPUB180與

FIPSPUB180-1

哈希值：160bits總共循環(huán)80次，邏輯函數(shù)ft和常量K[4]每20次變換一次，因此劃分為4個(gè)回合，每個(gè)回合20次循環(huán)中，邏輯函數(shù)和常量一樣31f1-4邏輯函數(shù)的定義32

回合步驟序號(hào)輸入常數(shù)取值方式(整數(shù))第一回合0≦t≦19K1=5A82799[230×2^0.5]第二回合20≦t≦39K2=6ED9EBA1[230×3^0.5]第三回合40≦t≦59K3=8F1BBCDC[230×5^0.5]第四回合60≦t≦79K4=CA62C1D6[230×10^0.5]SHA-1算法——Kt的取值輸入常數(shù)整數(shù)的功能（3）數(shù)據(jù)擴(kuò)展

3334SHA-1算法——數(shù)據(jù)擴(kuò)充

3536處理程序：4回合，共計(jì)

80次；5個(gè)緩存器

A=E+f1-4(t,B,C,D)+S5(A)+W[t]+K1-4

B=AC=S30(B)D=CE=DSHA-1壓縮函數(shù)37上圖表達(dá)式的說(shuō)明其中

f1-4(t,B,C,D)=步t的基本邏輯函數(shù)Sk=循環(huán)左移k位Wt=一個(gè)從當(dāng)前512位輸入數(shù)據(jù)塊導(dǎo)出的32位字K1-4＝一個(gè)用于加法的常量，四個(gè)不同值+=模232加38SHA算法實(shí)例[例7-5]：對(duì)ASCII字符串"abc"，運(yùn)用SHA-1，求哈希值。解:首先”abc”二進(jìn)制表示為：011000010110001001100011，共24位長(zhǎng)度，按照SHA-1要求，填充數(shù)據(jù)512-64-24＝424（填充1位“1”，423位“0”，及1000…000)

填充后512bits數(shù)據(jù)為：6162638000000000，……,00000018(十六進(jìn)制表示)，而W0=61626380,W1=W2=…=W14=00000000,W15=0000001839

40

41哈希函數(shù)網(wǎng)絡(luò)表述方法誤區(qū)資料和網(wǎng)絡(luò)上，經(jīng)常說(shuō)法MD5加密算法，SHA-1加密算法？或者M(jìn)D5單向加密42“MD5加密算法”、“SHA-1加密算法”這種表述不妥?！癕D5單向加密”，這種表述嚴(yán)格來(lái)說(shuō)沒(méi)有錯(cuò)誤，哈希函數(shù)確實(shí)是單向的變換。但是一般說(shuō)來(lái)在密碼學(xué)上，稱加密算法，一般意味著要能解密。而哈希函數(shù)是不能夠解密，所以我們?cè)诿艽a學(xué)上，一般哈希函數(shù)，不會(huì)說(shuō)成MD5加密、SHA-1加密，而是說(shuō)哈希算法。哈希出來(lái)的結(jié)果，一般也成為摘要值，哈希值，散列值，而不會(huì)說(shuō)“密文”。43消息認(rèn)證消息認(rèn)證是一個(gè)過(guò)程，用以驗(yàn)證接收消息的真實(shí)性（的確是由它所聲稱的實(shí)體發(fā)來(lái)的）和完整性（未被篡改、插入、刪除），同時(shí)還用于驗(yàn)證消息的順序性和時(shí)間性（未重排、重放、延遲）。消息認(rèn)證過(guò)程中檢驗(yàn)內(nèi)容應(yīng)包括：（1）證實(shí)報(bào)文的源和宿；（2）報(bào)文內(nèi)容是否曾受到偶然的或有意的篡改；（3）報(bào)文的序號(hào)和時(shí)間先后。

2023/11/2244消息認(rèn)證碼MessageAuthenticationCode，MAC也叫消息認(rèn)證碼利用密鑰來(lái)生成一個(gè)固定長(zhǎng)度的短數(shù)據(jù)塊，并將該數(shù)據(jù)塊附加在消息之后。45消息認(rèn)證使接收者能識(shí)別：消息的源，內(nèi)容的真?zhèn)?，時(shí)間性和信宿。這種認(rèn)證只在相應(yīng)通信的雙方之間進(jìn)行，而不允許第三者進(jìn)行上述認(rèn)證。認(rèn)證不一定是實(shí)時(shí)的，可用消息認(rèn)證碼MAC（Messageauthenticacode）對(duì)消息做認(rèn)證,主要有：（1）基于分組密碼的MAC

（2）基于散列函數(shù)（HASH）的MAC46基于分組密碼的MACCBC-MAC算法是最常用的一種基于分組的MAC算法2023/11/2247消息認(rèn)證碼MAC的特點(diǎn)接收方可以相信消息未被修改接收方可以相信消息來(lái)自真正的發(fā)送方如果消息中含有序列號(hào)，那么接收方可以相信消息順序是正確的MAC函數(shù)與加密的區(qū)別之一是，MAC算法不要求可逆性MAC不能提供數(shù)字簽名2023/11/2248消息認(rèn)證碼使用消息認(rèn)證只保證消息的完整性，不保證消息的保密性密鑰只能收發(fā)雙方有MCMCC比較2023/11/2249消息認(rèn)證碼使用消息認(rèn)證和保密：與明文有關(guān)的認(rèn)證MCCMCMCC比較K1K1K2K22023/11/2250消息認(rèn)證碼使用消息認(rèn)證和保密：與密文有關(guān)的認(rèn)證MEMC比較CECK2K2K1K12023/11/2251哈希函數(shù)+對(duì)稱密碼算法的消息認(rèn)證消息認(rèn)證MCHMHMHH比較認(rèn)證+保密2023/11/2252消息認(rèn)證MHH比較MC相當(dāng)于MAC哈希函數(shù)+對(duì)稱密碼算法的消息認(rèn)證53本節(jié)要點(diǎn)小結(jié)單向函數(shù)Hash函數(shù)的定義hash函數(shù)的用途SHA-1算法例題MD5和SHA-1能處理消息的最大長(zhǎng)度對(duì)字符長(zhǎng)度“0123456789”采用SHA-1算法進(jìn)行哈希，首先進(jìn)行消息填充，填充的數(shù)據(jù)的長(zhǎng)度為多少bit（填充多少個(gè)二進(jìn)制的0和1）？數(shù)據(jù)擴(kuò)充之后的字W0，W1，……,W16？54例題1講解MD5和SHA-1數(shù)據(jù)長(zhǎng)度為64比特，MD5可以任意長(zhǎng)度，SHA-1最大為264-1bitsMD5最大消息長(zhǎng)度SHA-1的最大消息長(zhǎng)度例題2講解

57課后作業(yè)(電子版本）采用SHA-1哈希算法，輸入各自學(xué)號(hào)，例如10個(gè)字符“2015062070”，請(qǐng)問(wèn)需要填充多少比特，并寫(xiě)出填充之后的512比特塊，W0，W1，W2，W14，W15，以及W16（用十六進(jìn)制表示）字符“0”對(duì)于的ASCII值為48，對(duì)應(yīng)十六進(jìn)制為0x30。58補(bǔ)充內(nèi)容59SHA-2561.消息填充首先將比特“1”添加到消息的末尾，再添加k個(gè)零，這里k是方程l+1+k≡448mod512的最小的非負(fù)解.然后再添加一個(gè)64比特長(zhǎng)的塊，其值等于消息M的長(zhǎng)度l的二進(jìn)制表示.使得填充后的消息的長(zhǎng)度為512比特的倍數(shù).60SHA-256

2SHA-256的初始變量

這些初值由計(jì)算前8個(gè)素?cái)?shù)的平方根的小數(shù)部分的前32位(二進(jìn)制)生成3壓縮函數(shù)的消息分組長(zhǎng)度為512比特，壓縮函數(shù)共64步變換.4輸出散列值長(zhǎng)度為256比特.61SHA-25662SHA-256SHA-256壓縮函數(shù)第(i-1)塊的輸出鏈接變量a、b、c、d、e、f、g和h分別賦值：fort=0to63計(jì)算第i個(gè)Hash值H(i)：需要臨時(shí)寄存器T1和T263SHA-256SHA-256的消息編排當(dāng)消息填充完成后，將消息塊M(1)，M(2)，…，M(N)按序排列，然后執(zhí)行以下步驟：Fori=1toN{6464SHA-256SHA-256使用了6個(gè)邏輯函數(shù)，設(shè)x,y和z為3個(gè)32比特長(zhǎng)的自變量，輸出結(jié)果都是32比特長(zhǎng)的字，邏輯函數(shù)定義如下：65SHA-256SHA-256的常數(shù)共使用了64個(gè)32位字長(zhǎng)的常數(shù)，它們分別由最小的64個(gè)素?cái)?shù)的三次方根的小數(shù)部分的前32位產(chǎn)生（二進(jìn)制表示）428a2f9871374491b5c0fbcfe9b5dba53956c25b59f111f1923f82a4ab1c5ed5d807aa9812835b01243185be550c7dc372be5d7480deb1fe9bdc06a7c19bf174e49b69c1efbe47860fc19dc6240ca1cc2de92c6f4a7484aa5cb0a9dc76f988da983e5152a831c66db00327c8bf597fc7c6e00bf3d5a7914706ca63511429296766SHA-25627b70a852e1b21384d2c6dfc53380d13650a7354766a0abb81c2c92e92722c85a2bfe8a1a81a664bc24b8b70c76c51a3d192e819d6990624f40e3585106aa07019a4c1161e376c082748774c34b0bcb5391c0cb34ed8aa4a5b9cca4f682e6ff3748f82ee78a5636f84c878148cc7020890befffaa4506cebbef9a3f7c67178f267SHA-512填充消息M,將消息填充到1024的整數(shù)倍.將填充消息分割為N個(gè)1024比特長(zhǎng)的消息塊M(1)，M(2)，…，M(N).設(shè)置初始Hash值H(0).迭代壓縮，壓縮函數(shù)消息分塊長(zhǎng)度為1024比特，壓縮函數(shù)為80步運(yùn)算.N次迭代后的輸出512比特鏈接變量作為消息散列值輸出.6768SHA-384SHA-384算法可用來(lái)Hash任意l(0≤l≤2128)位長(zhǎng)的消息M。算法的具體實(shí)現(xiàn)和SHA-512是一樣的，惟一不同的是以下兩點(diǎn)：

1)初始Hash值H(0)的設(shè)置不同；

2)輸出384比特長(zhǎng)的消息摘要，即剪切H(N)的左邊384比特位產(chǎn)生：6869SHA-384和SHA-5121消息填充假設(shè)消息M的長(zhǎng)度為l,首先將比特“1”添加到消息的末尾，再添加k個(gè)零。這里k是方程l+1+k≡896mod1024

的最小的非負(fù)解。然后再添加一個(gè)128比特長(zhǎng)的塊，其值等于消息M的長(zhǎng)度l的二進(jìn)制表示。例如，消息“abc”,其8比特的ASCII表示長(zhǎng)度為，因此，首先填充一個(gè)“1”，再填充896-(24+1)=871個(gè)零，然后再填充一個(gè)長(zhǎng)度l=24的128位的二進(jìn)制，即可得一長(zhǎng)度1024位的二進(jìn)制對(duì)SHA-384和SHA-512來(lái)說(shuō)，填充消息被分為N個(gè)1024比特的塊，.011000010110001001100011100…00 00…011000“a”“b”“c”871128l=247070SHA-384和SHA-5122SHA-384初始連接變量

這些初值由計(jì)算第九個(gè)至第十六個(gè)素?cái)?shù)的平方根的小數(shù)部分的前64位(二進(jìn)制)生成7171SHA-384和SHA-5122SHA-512初始鏈接變量

這些初值由計(jì)算前八個(gè)素?cái)?shù)的平方根的小數(shù)部分的前64位(二進(jìn)制)生成72SHA-384和SHA-5123SHA-384和SHA-512中的函數(shù)SHA-384和SHA-512都使用了6個(gè)邏輯函數(shù)，x,y和z為3個(gè)64比特長(zhǎng)自變量，輸出結(jié)果都是64比特長(zhǎng)的字73SHA-384和SHA-5124SHA-238和SHA-512的常數(shù)SHA-238和SHA-512使用了80個(gè)64位字長(zhǎng)的常數(shù)，這些常數(shù)由最小的80個(gè)素?cái)?shù)的三次方根的小數(shù)部分的前64位產(chǎn)生（二進(jìn)制表示）。在十六進(jìn)制的情況下，其值為：428a2f98d728ae227137449123ef65cdb5c0fbcfec4d3b2fe9b5dba58189dbbc3956c25bf348b53859f111f1b605d019923f82a4af194f9bab1c5ed5da6d8118d807aa98a303024212835b0145706fbe243185be4ee4b28c550c7dc3d5ffb4e272be5d74f27b896f80deb1fe3b1696b19bdc06a725c71235c19bf174cf692694e49b69c19ef14ad2efbe4786384f25e30fc19dc68b8cd5b5240ca1cc77ac9c652de92c6f592b02754a7484aa6ea6e4835cb0a9dcbd41fbd476f988da831153b5983e5152ee66dfaba831c66d2db43210b00327c898fb213fbf597fc7beef0ee4c6e00bf33da88fc2d5a79147930aa72506ca6351e003826f14292967