《新編密碼學(xué)》課件第4章 哈希函數(shù)

4.1Hash函數(shù)與隨機(jī)預(yù)言模型在實(shí)際的通信保密中，除了要求實(shí)現(xiàn)數(shù)據(jù)的保密性之外，對(duì)傳輸數(shù)據(jù)安全性的另一個(gè)基本要求是保證數(shù)據(jù)的完整性。密碼學(xué)中的Hash函數(shù)的主要功能是提供有效的數(shù)據(jù)完整性檢驗(yàn)。數(shù)據(jù)的完整性是指數(shù)據(jù)從發(fā)送方產(chǎn)生后，經(jīng)過(guò)傳輸或存儲(chǔ)以后，未被以未授權(quán)的方式修改的性質(zhì)。

4.1.1Hash函數(shù)Hash函數(shù)是一個(gè)將任意長(zhǎng)度的消息序列映射為較短的、固定長(zhǎng)度的一個(gè)值的函數(shù)。密碼學(xué)上的Hash函數(shù)能夠保障數(shù)據(jù)的完整性。通常被用來(lái)構(gòu)造數(shù)據(jù)的“指紋”（即函數(shù)值），當(dāng)被檢驗(yàn)的數(shù)據(jù)發(fā)生改變的時(shí)候，對(duì)應(yīng)的“指紋”信息也將發(fā)生變化。對(duì)于Hash函數(shù)的安全要求，如果對(duì)于原像問(wèn)題第二原像問(wèn)題碰撞問(wèn)題這三個(gè)問(wèn)題都是難解的，則認(rèn)為該Hash函數(shù)是安全的。X—消息集合Y—消息摘要集合不能有效解決原像問(wèn)題的Hash函數(shù)稱為單向的或原像穩(wěn)固的。不能有效解決第二原像問(wèn)題的Hash函數(shù)稱為第二原像穩(wěn)固的。不能有效解決碰撞問(wèn)題的Hash函數(shù)稱為碰撞穩(wěn)固的。實(shí)際應(yīng)用中的Hash函數(shù)可分為:簡(jiǎn)單的Hash函數(shù)帶密鑰的Hash函數(shù)一個(gè)帶密鑰的Hash函數(shù)通常用來(lái)作為消息認(rèn)證碼MAC（Messageauthenticationcode）定義4.1.4 一個(gè)帶密鑰的Hash函數(shù)包括以下構(gòu)成要素：X:所有消息的集合（有限級(jí)或無(wú)限級(jí)）Y:所有消息摘要構(gòu)成的有限集合K:密鑰集合對(duì)任意的都存在一個(gè)Hash函數(shù)如果

則二元組稱為在密鑰k下是有效的Hash函數(shù)的性質(zhì)：（1）能夠用于任何大小的數(shù)據(jù)分組（2）能產(chǎn)生定長(zhǎng)的輸出（3）易于計(jì)算，便于軟硬件實(shí)現(xiàn)（4）原像穩(wěn)固（5）第二原像穩(wěn)固（6）碰撞穩(wěn)固這3個(gè)條件是用于消息認(rèn)證的基本要求單向性防止偽造防止生日攻擊Hash函數(shù)的目的是確定消息是否被修改。對(duì)Hash函數(shù)攻擊的目標(biāo)是生成這樣的修改后消息：其Hash函數(shù)值與原始消息的Hash函數(shù)值相等。生日攻擊生日攻擊的思想來(lái)源于概率論中一個(gè)著名的問(wèn)題----生日問(wèn)題。該問(wèn)題是問(wèn)一個(gè)班級(jí)中至少要有多少個(gè)學(xué)生才能夠使得有兩個(gè)學(xué)生生日相同的概率大于1/2。該問(wèn)題的答案是23。即只要班級(jí)中學(xué)生的人數(shù)大于23人，則班上有兩個(gè)人生日相同的概率就將大于1/2。2024/5/1811基于生日問(wèn)題的生日攻擊意味著要保證消息摘要對(duì)碰撞問(wèn)題是安全的，則安全消息摘要的長(zhǎng)度就有一個(gè)下界。如果消息摘要為m位長(zhǎng)度，則總的消息數(shù)為2m，因此需要檢查大約2m/2個(gè)消息，可使兩條消息具有相同Hash函數(shù)值的概率大于50%。Oscar可以生成下述形式的可接受消息：例也可以生成下述形式的不可接受的消息：在對(duì)所有512條消息取Hash函數(shù)值后，Oscar也許會(huì)發(fā)現(xiàn)，“Ipromisetolend25dollarstomybestfriendOscarwhichhewillreturntomein10daysorlessYours,Alice”“Iagreetooffertwenty-fivedollarstomygoodfriendOscarassgiftwhichheshouldnotrepaybecauseIknowheneedsthisaidSincerely,Alice”有相同的Hash函數(shù)值。這意味著Oscar可用后者來(lái)替換前者。4.1.2隨機(jī)預(yù)言模型由Bellare和Rogaway提出的隨機(jī)預(yù)言模型（RandomOracleModel）是一種“理想化”的Hash函數(shù)數(shù)學(xué)模型。2024/5/1817在這個(gè)模型中，隨機(jī)從Fx,y中選出一個(gè)Hash函數(shù)

H，我們僅僅允許預(yù)言器訪問(wèn)函數(shù)H這表示對(duì)于任一個(gè)消息x，隨機(jī)預(yù)言模型都不會(huì)給出一個(gè)公式或者算法來(lái)計(jì)算消息摘要H(x)的值。計(jì)算H(x)值的惟一方法是詢問(wèn)預(yù)言器相當(dāng)于根據(jù)給出的消息x，在一本關(guān)于隨機(jī)數(shù)的書中查詢H(x)的值對(duì)于每一個(gè)x，都有一個(gè)完全隨機(jī)的H(x)與之對(duì)應(yīng)2024/5/1818M的值越大，相應(yīng)的產(chǎn)生碰撞的概率就越小。

4.2迭代的Hash函數(shù)1979年，Merkle基于數(shù)據(jù)壓縮函數(shù)建議了一個(gè)Hash函數(shù)的通用模式。數(shù)據(jù)值由消息分組組成，對(duì)所有數(shù)據(jù)分組進(jìn)行迭代處理。m位壓縮值t位數(shù)據(jù)值ym位輸出圖4-1迭代Hash函數(shù)系統(tǒng)結(jié)構(gòu)compresscompresscompressZ0Y1Z1Y2Zn-1Yn-1Zn輸入Yn-1基于消息x構(gòu)造y=y1||y2||…

yr

，yr長(zhǎng)度為t4.3MDMD（MessageDigest，消息摘要）算法由RonRivest在1990年10月提出，1992年4月，RonRivest公布了相應(yīng)的改進(jìn)算法。人們通常把RonRivest在1990年提出的算法稱為MD4把相應(yīng)的改進(jìn)算法稱為MD5

4.3.1MD5MD5以512位的分組長(zhǎng)度來(lái)處理消息，每一個(gè)分組又被劃分為16個(gè)32位的子分組。算法的輸出由4個(gè)32位的分組組成，它們串聯(lián)成一個(gè)128位的消息摘要。MD5將任意長(zhǎng)度的“字節(jié)串”變換成一個(gè)128bit的大整數(shù)，并且是一個(gè)不可逆的字符串變換算法。圖4-2MD5產(chǎn)生報(bào)文摘要的過(guò)程具體步驟：(1)填充消息使其長(zhǎng)度正好為512位的整數(shù)倍末尾處附上64比特消息長(zhǎng)度的二進(jìn)制表示然后在消息后面填充一個(gè)“1”和多個(gè)“0”填充后的消息恰好是512比特的整倍長(zhǎng)L。64比特2024/5/1825消息長(zhǎng)度為704位M0M1M2…M13M14M15消息704填充256位消息長(zhǎng)度64位1000000……00000……10110000002x512=1024分組M0M1M2…M13M14M15消息704填充256位消息長(zhǎng)度64位512512例2024/5/1826(2)初始化緩沖區(qū)算法中使用了128位的緩沖區(qū)，每個(gè)緩沖區(qū)由4個(gè)32比特的寄存器A，B，C，D組成，先把這4個(gè)寄存器初始化為：A=01234567B=89ABCDEFC=FEDCBA98D=76543210單個(gè)分組的MD5處理過(guò)程(3)處理512位消息塊Yq，進(jìn)入主循環(huán)第一輪中的Mi為填充之后的M0……M15第二，三四輪中的Mi由公式計(jì)算得出包含4輪操作，每一輪由16次迭代操作組成，上一輪的輸出作為下一輪的輸入。消息塊第q次輸出第q+1次輸出MiMiMiMiMi為Yq中的16個(gè)字AABBCCDD4輪循環(huán)中每一輪用的16個(gè)Mi如下表所示M0M1

M2

M3

M4

M5

M6

M7M8M9M10M11M12M13M14M15M1

M6

M11

M0

M5

M10

M15M4M9M14M3M8M13M2M7M12M5M8

M11

M14

M1

M4

M7

M10M13M0M3M6M9M12M15M2M0M7

M14

M5

M12

M3

M10

M1M8M15M6M13M4M11M2M9圖4-4基本MD5操作(單步)回合數(shù)運(yùn)算函數(shù)g12344個(gè)非線性函數(shù)分別為：一輪具體操作Mi常數(shù)b）常數(shù)tj：常數(shù)表T[i]共有64個(gè)元素，每個(gè)元素32位長(zhǎng)，tj＝232abs(sin(i))的整數(shù)部分,其中j是弧度。處理每一個(gè)消息塊Yi時(shí)，每一輪使用常數(shù)表T[i]中的16個(gè)，正好用4輪。c)循環(huán)左移數(shù)：每輪中每步左循環(huán)移位的位數(shù)按下表執(zhí)行。步數(shù)輪數(shù)123456789101112131415161234754612911101714161522202321754612911101714161522202321754612911101714161522202321754612911101714161522202321每一輪不斷地更新緩沖區(qū)A，B，C，D中的內(nèi)容4輪之后進(jìn)入下一個(gè)主循環(huán)，直到處理完所有消息塊為止。輸出得到128位的消息摘要MD5相對(duì)MD4進(jìn)行了以下一些改進(jìn)：增加了主循環(huán)中的操作次數(shù)，由三輪操作改進(jìn)為四輪操作；操作的每一步均有惟一的加法常數(shù)；減弱函數(shù)的對(duì)稱性；改變了第二輪和第三輪中訪問(wèn)消息子分組的次序，使得其形式更加不相似；近似優(yōu)化了每一輪中循環(huán)移位的位移量，各輪的位移量各不相同。

MD5算法有以下性質(zhì)：Hash函數(shù)的每一位均是輸入消息序列中每一位的函數(shù)。保證了在Hash函數(shù)計(jì)算過(guò)程中產(chǎn)生基于消息x的混合重復(fù)，從而使得生成的Hash函數(shù)結(jié)果混合得非常理想。也就是說(shuō)，隨機(jī)選取兩個(gè)有著相似規(guī)律性的兩組消息序列，也很難產(chǎn)生相同的Hash函數(shù)值。

4.4SHA-1SHA-1（SHA：SecurityHashAlgorithm，安全Hash算法）是一個(gè)產(chǎn)生160位消息摘要的迭代Hash函數(shù)。由美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)（NIST）提出，并作為聯(lián)邦信息處理標(biāo)準(zhǔn)在1993年公布。SHA-1的設(shè)計(jì)基于MD4算法，并且它在設(shè)計(jì)方面也很大程度上是模仿MD5算法的。2002年，NIST在SHA-1的基礎(chǔ)上，進(jìn)一步推出了SHA-256、SHA-394、SHA-512三個(gè)版本的安全Hash算法，它們的消息摘要長(zhǎng)度分別為256位、394位和512位。這些改進(jìn)算法不僅增強(qiáng)了Hash算法的安全性能，而且便于與AES算法相結(jié)合。SHA-1算法算法輸入消息的最大長(zhǎng)度不超過(guò)264位，輸入的消息按照512位的分組進(jìn)行處理。圖4-5SHA-1產(chǎn)生報(bào)文摘要的過(guò)程(1)填充消息首先將消息填充為512的整數(shù)倍，填充方法與MD5相同。與MD5不同的是SHA-1的輸入為長(zhǎng)度小于264比特的消息。64bit2024/5/1839消息長(zhǎng)度為704位M0M1M2…M13M14M15消息704填充256位消息長(zhǎng)度64位1000000……00000……10110000002x512=1024分組M0M1M2…M13M14M15消息704填充256位消息長(zhǎng)度64位512512例(2)初始化緩沖區(qū)初始化160位的消息摘要緩沖區(qū)（即設(shè)定IV值），每個(gè)緩沖區(qū)由5個(gè)32比特的寄存器A，B，C，D，E組成，初始化為：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C2D2E1F0(3)處理512位消息塊Yq，進(jìn)入主循環(huán)主循環(huán)有四輪，每輪20次操作（MD5有四輪，每輪16次操作）。每次操作對(duì)A、B、C、D和E中的三個(gè)做一次非線性函數(shù)運(yùn)算然后進(jìn)行與MD5中類似的移位運(yùn)算和加運(yùn)算。單個(gè)分組的處理過(guò)程消息塊Yq填充字節(jié)之后每個(gè)512分成16個(gè)子分組Mi，每一輪的Mi都不相同，由公式得出80個(gè)子分組包含4輪操作，每一輪由20次迭代操作組成，上一輪的輸出作為下一輪的輸入。消息塊第q次輸出第q+1次輸出MiMiMiMiabcde四個(gè)常量原消息長(zhǎng)度只有16個(gè)序列，要通過(guò)相應(yīng)的算法生成80個(gè)序列，每輪循環(huán)用20個(gè)單元運(yùn)算次數(shù)tft的運(yùn)算操作SHA-1算法中的非線性函數(shù)定義為：函數(shù)、、、的真值表

XYZ00000101001110010111011100001101010110100101001010101111

4.5MD5與SHA-1的比較抗窮舉搜索攻擊的強(qiáng)度：

SHA-1強(qiáng)速度：MD5運(yùn)算速度快簡(jiǎn)潔與緊致性：都較為簡(jiǎn)單小數(shù)在前結(jié)構(gòu)與大數(shù)在前結(jié)構(gòu)：MD5使用小數(shù)在前方案來(lái)解釋32bit字序列的報(bào)文，而SHA-1則使用大數(shù)在前。2024/5/182004年8月17日的美國(guó)加州圣巴巴拉的國(guó)際密碼學(xué)會(huì)議（Crypto’2004）上，來(lái)自中國(guó)山東大學(xué)的王小云教授做了破譯MD5、HAVAL-128、MD4和RIPEMD算法的報(bào)告，公布了MD系列算法的破解結(jié)果。宣告了固若金湯的世界通行密碼標(biāo)準(zhǔn)MD5的堡壘轟然倒塌，引發(fā)了密碼學(xué)界的軒然大波。令世界頂尖密碼學(xué)家想象不到的是，破解MD5之后，2005年2月，王小云教授又破解了另一國(guó)際密碼SHA－1。HASH函數(shù)基本用法之一MH(M)MHashEKM’H(M)M’DKHash比較MCEk[M,H(M)]算法符號(hào)描述A→B:Ek[M‖H(M)]B：Dk[Ek[M‖H(M)]]=[M’‖H(M)]；H(M’)，判斷：H(M’)是否等于H(M)。服務(wù)功能提供鑒別——使用信息摘要H(M)與H(M’)的比較完成信息完整性鑒別提供加密——使用對(duì)稱加密密鑰K加密原始信息和信息摘要過(guò)程描述H(M’)HASH函數(shù)基本用法之二MMHashEKM’DKHash比較MEkH(M)M’EkH(M)算法符號(hào)描述：A：M‖Ek[H(M)]→BB：Dk[Ek[H(M)]]=H(M)；H(M’)，判斷：H(M’)是否等于H(M)？服務(wù)功能提供加密服務(wù)——對(duì)H(M)使用加密保護(hù)提供鑒別服務(wù)——使用信息摘要H(M)與H(M’)的比較完成信息完整性鑒別過(guò)程描述H(M)H(M)H(M’)HASH函數(shù)基本用法之三算法符號(hào)描述：A：H(M)→B（預(yù)先發(fā)送或存儲(chǔ)信息摘要）A：H(M’)→B（臨時(shí)提供的信息摘要）B：判斷：H(M’)是否等于H(M)？服務(wù)功能提供身份鑒別——使用信息摘要H(M)與H(M’)的比較，判斷發(fā)送方是否掌握原始信息以鑒別其身份的真實(shí)性。過(guò)程描述MH(M)HashHash比較H(M)H(M’)H(M’)M’HASH函數(shù)基本用法之四MMHashEKSaM’DKPaHash比較MEkH(M)M’EkH(M)H(M)H(M)算法符號(hào)描述A：[M‖EkSa[H(M)]]→BB：DkPa[EkSa[H(M)]]=H(M)；H(M’),判斷：H(M’)是否等于H(M)？服務(wù)功能提供簽名服務(wù)——A用自己的私鑰KSa加密H(M)完成對(duì)M的數(shù)字簽名，B用A的公鑰KPa驗(yàn)證該數(shù)字簽名提供鑒別服務(wù)——通過(guò)信息摘要H(M)與H(M’)的比較，完成被簽名信息的完整性鑒別過(guò)程描述H(M’)HASH函數(shù)基本用法之五算法符號(hào)描述：A：EKPb[M‖EKSa[H(M)]]→BB：DKSb[EKPb[M‖EKSa[H(M)]]]=[M’‖EKSa[H(M)]]；DKPa[EKSa[H(M)]]=H(M)；H(M’)，判斷：H(M’)是否等于H(M)？服務(wù)功能提供鑒別——比較H(M)數(shù)字簽名——A用自己的私鑰加密H(M)，B用A的公鑰驗(yàn)證簽名提供加密——A用B的公鑰對(duì)信息和簽名一起加密過(guò)程描述MMHashEKSaM’DKPaHash比較MEkH(M)M’EkH(M)H(M)H(M)EKPbDKSbCEkPb[M,EKSa[H(M)]]H(M’)

*4.6消息認(rèn)證碼（MAC）消息鑒別是用來(lái)鑒別接收方收到的消息的真實(shí)性和完整性鑒別消息的順序和時(shí)間性消息認(rèn)證碼：秘密密鑰k簇函數(shù)Hk性質(zhì)容易計(jì)算壓縮強(qiáng)抗碰撞性發(fā)送端接收端消息x摘要密鑰k做MAC運(yùn)算摘要消息x摘要消息x提取密鑰k摘要MAC運(yùn)算摘要對(duì)比摘要相同—是原信息x摘要不同—原信息被改發(fā)送提取構(gòu)造MAC的常用方法是把密鑰作為輸入消息的一部分，從而在一個(gè)不帶密鑰的Hash函數(shù)中介入一個(gè)密鑰。構(gòu)造消息認(rèn)證碼不能夠簡(jiǎn)單地將密鑰參數(shù)和消息x進(jìn)行拼接，然后直接計(jì)算相應(yīng)的Hash函數(shù)值來(lái)處理?；贒ES的消息認(rèn)證碼——數(shù)據(jù)認(rèn)證算法MAC函數(shù)類似于加密。一個(gè)區(qū)別是MAC函數(shù)無(wú)需是可逆的，而對(duì)解密則必須是可逆的。以MAC作為數(shù)據(jù)認(rèn)證算法最為廣泛的用法是基于DES的，該算法已作為FIPSPublication(FIPSPUB113)并被ANSI作為X9.17標(biāo)準(zhǔn)。算法基于CBC模式的DES算法，其初始向量取為零向量。需被認(rèn)證的數(shù)據(jù)（消息、記錄、文件或程序）被分為64比特長(zhǎng)的分組，其中最后一個(gè)分組若不夠64比特的話，可在其右邊填充一些0，然后按以下過(guò)程計(jì)算數(shù)據(jù)認(rèn)證碼利用CBC模式下DES的認(rèn)證碼

數(shù)據(jù)認(rèn)證碼取為ON或者取為ON的最左M個(gè)比特，其中16≤M≤64。HMAC近年來(lái)，人們?cè)絹?lái)越感興趣于利用密碼Hash函數(shù)來(lái)設(shè)計(jì)MAC，因?yàn)?(l)一般象MD5和SHA-1這樣的Hash函數(shù)，其軟件執(zhí)行速度比諸如DES和AES這樣的分組密碼算法要快。(2)可利用密碼Hash函數(shù)代碼庫(kù)。(3)美國(guó)或其他國(guó)家對(duì)密碼Hash函數(shù)沒(méi)有出口限制，而對(duì)即使是用于MAC的對(duì)稱分組密碼都有出口限制。Hash函數(shù)不依賴于密鑰，所以不能將其直接用于MAC。目前已經(jīng)提出了許多將密鑰加到Hash函數(shù)中的方案，包括UMAC和HMAC等。其中，HMAC是目前最受歡迎的方案，它被選為IP安全解決方案中實(shí)現(xiàn)MAC必須使用的方法，并且其它功Iternet協(xié)議，如安全套接協(xié)議ssl中也使用了HMAC。HMAC是由H.Krawczyk，M.Bellare，R.Canetti于1996年提出的一種基于Hash函數(shù)和密鑰進(jìn)行消息認(rèn)證的方法。HMAC所能提供的消息認(rèn)證包括兩方面的內(nèi)容:(l)消息完整性認(rèn)證:能夠證明消息內(nèi)容在傳送過(guò)程中沒(méi)有被修改。(2)信源身份認(rèn)證:因?yàn)橥ㄐ烹p方共享了認(rèn)證的密鑰，接收方能夠認(rèn)證發(fā)送該數(shù)據(jù)的信源與所宣稱的一致，即能夠可靠的確認(rèn)接收的消息與發(fā)送的一致。RFC2104給出的HMAC算法的設(shè)計(jì)目標(biāo)如下:(l)不必修改而直接使用現(xiàn)有Hash函數(shù)。特別地，很容易免費(fèi)得到軟件上執(zhí)行速度較快的Hash函數(shù)及其代碼;(2)如果找到或者需要更快或更安全的Hash函數(shù)，應(yīng)能很容易地替代原來(lái)嵌入的Hash函數(shù);(3)應(yīng)保持Hash函數(shù)原有的性能，不能過(guò)分降低其性能;(4)對(duì)密鑰的使用和處理應(yīng)較簡(jiǎn)