現(xiàn)代密碼學(xué)第6章

1、第第6章章 消息認證和雜湊算法消息認證和雜湊算法6.1 消息認證碼消息認證碼6.2 雜湊函數(shù)雜湊函數(shù)6.3 MD5雜湊算法雜湊算法6.4 安全雜湊算法安全雜湊算法6.5 HMAC算法算法習(xí)題習(xí)題第第1章曾介紹過信息安全所面臨的基本攻擊類型，包章曾介紹過信息安全所面臨的基本攻擊類型，包括被動攻擊（獲取消息的內(nèi)容、業(yè)務(wù)流分析）和主括被動攻擊（獲取消息的內(nèi)容、業(yè)務(wù)流分析）和主動攻擊（假冒、重放、消息的篡改、業(yè)務(wù)拒絕）。動攻擊（假冒、重放、消息的篡改、業(yè)務(wù)拒絕）?？箵舯粍庸舻姆椒ㄊ乔懊嬉呀榻B過的加密，本章抗擊被動攻擊的方法是前面已介紹過的加密，本章介紹的介紹的消息認證則是用來抗擊主動攻擊消息認證則是

2、用來抗擊主動攻擊的。消息認的。消息認證是一個過程，用以驗證接收消息的證是一個過程，用以驗證接收消息的真實性真實性（的確（的確是由它所聲稱的實體發(fā)來的）和是由它所聲稱的實體發(fā)來的）和完整性完整性（未被篡改、（未被篡改、插入、刪除），同時還用于驗證消息的插入、刪除），同時還用于驗證消息的順序性順序性和和時時間性間性（未重排、重放、延遲）。除此之外，在考慮（未重排、重放、延遲）。除此之外，在考慮信息安全時還需考慮業(yè)務(wù)的信息安全時還需考慮業(yè)務(wù)的不可否認性不可否認性，即防止通，即防止通信雙方中的某一方對所傳輸消息的否認。實現(xiàn)消息信雙方中的某一方對所傳輸消息的否認。實現(xiàn)消息的不可否認性可通過數(shù)字簽字，數(shù)字

3、簽字也是一種的不可否認性可通過數(shù)字簽字，數(shù)字簽字也是一種認證技術(shù)，它也可用于抗擊主動攻擊。認證技術(shù)，它也可用于抗擊主動攻擊。消息認證機制和數(shù)字簽字機制都需有產(chǎn)生認證符的消息認證機制和數(shù)字簽字機制都需有產(chǎn)生認證符的基本功能，這一基本功能又作為認證協(xié)議的一個組基本功能，這一基本功能又作為認證協(xié)議的一個組成部分。認證符是用于認證消息的數(shù)值，它的產(chǎn)生成部分。認證符是用于認證消息的數(shù)值，它的產(chǎn)生方法又分為消息認證碼方法又分為消息認證碼MAC（message authentication code）和雜湊函數(shù)（和雜湊函數(shù)（hash function）兩大類，兩大類，消息認證碼是指消息被一密鑰控制的公開函數(shù)

4、作用消息認證碼是指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的、用作認證符的、固定長度的數(shù)值后產(chǎn)生的、用作認證符的、固定長度的數(shù)值，也稱，也稱為密碼校驗和。此時需要通信雙方為密碼校驗和。此時需要通信雙方A和和B共享一密鑰共享一密鑰K。設(shè)設(shè)A欲發(fā)送給欲發(fā)送給B的消息是的消息是M，A首先計算首先計算MAC=CK(M)，其中其中CK()是密鑰控制的公開函數(shù)，是密鑰控制的公開函數(shù)，然后向然后向B發(fā)送發(fā)送MMAC，B收到后做與收到后做與A相同的計算，相同的計算，求得一新求得一新MAC，并與收到的并與收到的MAC做比較，如圖做比較，如圖6.1(a)所示。所示。6.1 消息認證碼消息認證碼 6.1.1 消息認證碼

5、的定義及使用方式消息認證碼的定義及使用方式如果僅收發(fā)雙方知道如果僅收發(fā)雙方知道K，且且B計算得到的計算得到的MAC與接收到的與接收到的MAC一致，則這一系統(tǒng)就實現(xiàn)了以一致，則這一系統(tǒng)就實現(xiàn)了以下功能：下功能： 接收方相信發(fā)送方發(fā)來的消息未被篡改接收方相信發(fā)送方發(fā)來的消息未被篡改，這是因，這是因為攻擊者不知道密鑰，所以不能夠在篡改消息后相為攻擊者不知道密鑰，所以不能夠在篡改消息后相應(yīng)地篡改應(yīng)地篡改MAC，而如果僅篡改消息，則接收方計算而如果僅篡改消息，則接收方計算的新的新MAC將與收到的將與收到的MAC不同。不同。 接收方相信發(fā)送方不是冒充的接收方相信發(fā)送方不是冒充的，這是因為除收發(fā)，這是因為除

6、收發(fā)雙方外再無其他人知道密鑰，因此其他人不可能對雙方外再無其他人知道密鑰，因此其他人不可能對自己發(fā)送的消息計算出正確的自己發(fā)送的消息計算出正確的MAC。AC函數(shù)與加密算法類似，不同之處為函數(shù)與加密算法類似，不同之處為MAC函數(shù)不必函數(shù)不必是可逆的，因此與加密算法相比更不易被攻破。是可逆的，因此與加密算法相比更不易被攻破。上述過程中，由于消息本身在發(fā)送過程中是明文形上述過程中，由于消息本身在發(fā)送過程中是明文形式，所以這一過程只提供認證性而未提供保密性。式，所以這一過程只提供認證性而未提供保密性。為提供保密性可在為提供保密性可在MAC函數(shù)以后函數(shù)以后(如圖如圖6.1(b)或以前或以前(如圖如圖6.

7、1(c)進行一次加密，而且加密密鑰也需被收進行一次加密，而且加密密鑰也需被收發(fā)雙方共享。在圖發(fā)雙方共享。在圖6.1(b)中，中，M與與MAC鏈接后再被整鏈接后再被整體加密，在圖體加密，在圖6.1(c)中，中，M先被加密再與先被加密再與MAC鏈接后鏈接后發(fā)送。通常希望直接對明文進行認證，因此圖發(fā)送。通常希望直接對明文進行認證，因此圖6.1(b)所示的使用方式更為常用。所示的使用方式更為常用。圖圖6.1 MAC的基本使用方式的基本使用方式圖圖6.1 MAC的基本使用方式的基本使用方式使用加密算法（單鑰算法或公鑰算法）加密消息時，使用加密算法（單鑰算法或公鑰算法）加密消息時，其安全性一般取決于密鑰的

8、長度。如果加密算法沒其安全性一般取決于密鑰的長度。如果加密算法沒有弱點，則敵手只能使用窮搜索攻擊以測試所有可有弱點，則敵手只能使用窮搜索攻擊以測試所有可能的密鑰。如果密鑰長為能的密鑰。如果密鑰長為k比特，則窮搜索攻擊平均比特，則窮搜索攻擊平均將進行將進行2k-1個測試。特別地，對惟密文攻擊來說，敵個測試。特別地，對惟密文攻擊來說，敵手如果知道密文手如果知道密文C，則將對所有可能的密鑰值則將對所有可能的密鑰值Ki執(zhí)行執(zhí)行解密運算解密運算Pi=DKi(C)，直到得到有意義的明文。直到得到有意義的明文。6.1.2 產(chǎn)生產(chǎn)生MAC的函數(shù)應(yīng)滿足的要求的函數(shù)應(yīng)滿足的要求對對MAC來說，由于產(chǎn)生來說，由于產(chǎn)

9、生MAC的函數(shù)一般都為多到一的函數(shù)一般都為多到一映射，如果產(chǎn)生映射，如果產(chǎn)生n比特長的比特長的MAC，則函數(shù)的取值范圍則函數(shù)的取值范圍即為即為2n個可能的個可能的MAC，函數(shù)輸入的可能的消息個數(shù)函數(shù)輸入的可能的消息個數(shù)N2n，而且如果函數(shù)所用的密鑰為而且如果函數(shù)所用的密鑰為k比特，則可能比特，則可能的密鑰個數(shù)為的密鑰個數(shù)為2k。如果系統(tǒng)不考慮保密性，即敵手能如果系統(tǒng)不考慮保密性，即敵手能獲取明文消息和相應(yīng)的獲取明文消息和相應(yīng)的MAC，那么在這種情況下要那么在這種情況下要考慮敵手使用窮搜索攻擊來獲取產(chǎn)生考慮敵手使用窮搜索攻擊來獲取產(chǎn)生MAC的函數(shù)所的函數(shù)所使用的密鑰。使用的密鑰。假定假定kn，且

10、敵手已得到且敵手已得到M1和和MAC1，其中其中MAC1=CK1（M1），），敵手對所有可能的密鑰值敵手對所有可能的密鑰值Ki求求MACi=CKi(M1)，直到找到某個直到找到某個Ki使得使得MACi=MAC1。由于不同的密鑰個數(shù)為由于不同的密鑰個數(shù)為2k，因此將產(chǎn)生因此將產(chǎn)生2k個個MAC，但其中僅有但其中僅有2n個不同，由于個不同，由于2k2n，所以有很多密鑰所以有很多密鑰（平均有（平均有2k/2n=2k-n個）都可產(chǎn)生出正確的個）都可產(chǎn)生出正確的MAC1，而而敵手無法知道進行通信的兩個用戶用的是哪一個密敵手無法知道進行通信的兩個用戶用的是哪一個密鑰，還必須按以下方式重復(fù)上述攻擊：鑰，還必

11、須按以下方式重復(fù)上述攻擊：第第1輪輪已知已知M1、MAC1，其中其中MAC1=CK(M1)。對所有對所有2k個可能的密鑰計算個可能的密鑰計算MACi=CKi(M1)，得得2k-n個可能的個可能的密鑰。密鑰。第第2輪輪已知已知M2、MAC2，其中其中MAC2=CK(M2)。對上一對上一輪得到的輪得到的2k-n個可能的密鑰計算個可能的密鑰計算MACi=CKi(M2)，得得2k-2n個可能的密鑰。個可能的密鑰。如此下去，如果如此下去，如果k=n，則上述攻擊方式平均需要則上述攻擊方式平均需要輪。輪。例如，密鑰長為例如，密鑰長為80比特，比特，MAC長為長為32比特，則第比特，則第1輪輪將產(chǎn)生大約將產(chǎn)生

12、大約248個可能密鑰，第個可能密鑰，第2輪將產(chǎn)生輪將產(chǎn)生216個可能的個可能的密鑰，第密鑰，第3輪即可找出正確的密鑰。輪即可找出正確的密鑰。如果密鑰長度小于如果密鑰長度小于MAC的長度，則第的長度，則第1輪就有可能找輪就有可能找出正確的密鑰，也有可能找出多個可能的密鑰，如出正確的密鑰，也有可能找出多個可能的密鑰，如果是后者，則仍需執(zhí)行第果是后者，則仍需執(zhí)行第2輪搜索。輪搜索。所以對消息認證碼的窮搜索攻擊比對使用相同長度所以對消息認證碼的窮搜索攻擊比對使用相同長度密鑰的加密算法的窮搜索攻擊的代價還要大。然而密鑰的加密算法的窮搜索攻擊的代價還要大。然而有些攻擊法卻不需要尋找產(chǎn)生有些攻擊法卻不需要尋

13、找產(chǎn)生MAC所使用的密鑰。所使用的密鑰。例如，設(shè)例如，設(shè)M=(X1X2Xm)是由是由64比特長的分組比特長的分組Xi(i=1,m)鏈接得到的，其消息認證碼由以下方式鏈接得到的，其消息認證碼由以下方式得到：得到：其中其中表示異或運算，加密算法是電碼本模式的表示異或運算，加密算法是電碼本模式的DES。因此，密鑰長為因此，密鑰長為56比特，比特，MAC長為長為64比特，如果敵比特，如果敵手得到手得到MCK(M)，那么敵手使用窮搜索攻擊尋找那么敵手使用窮搜索攻擊尋找K將將需做需做256次加密。然而敵手還可用以下方式攻擊系統(tǒng)：次加密。然而敵手還可用以下方式攻擊系統(tǒng)： 將將X1到到Xm-1分別用自己選取的

14、分別用自己選取的Y1到到Y(jié)m-1替換，求出替換，求出Ym=Y1Y2Ym-1(M)，并用并用Ym替換替換Xm。因因此敵手可成功偽造一新消息此敵手可成功偽造一新消息M=Y1Ym，且且M的的MAC與原消息與原消息M的的MAC相同。相同。12()()()mKKMXXXCMEM考慮到考慮到MAC所存在的以上攻擊類型，可知它應(yīng)滿足所存在的以上攻擊類型，可知它應(yīng)滿足以下要求，其中假定敵手知道函數(shù)以下要求，其中假定敵手知道函數(shù)C，但不知道密鑰但不知道密鑰K： 如果敵手得到如果敵手得到M和和CK(M)，則構(gòu)造一滿足則構(gòu)造一滿足CK(M)=CK(M)的新消息的新消息M在計算上是不可行的。在計算上是不可行的。 CK

15、(M)在以下意義下是均勻分布的：在以下意義下是均勻分布的： 隨機選取兩隨機選取兩個消息個消息M、M，PrCK(M)=CK(M)=2-n，其中其中n為為MAC的長。的長。 若若M是是M的某個變換，即的某個變換，即M=f(M)，例如例如f為插入為插入一個或多個比特，那么一個或多個比特，那么PrCK(M)=CK(M)= 2-n。第第1個要求是針對上例中的攻擊類型的，此要求是說個要求是針對上例中的攻擊類型的，此要求是說敵手不需要找出密鑰敵手不需要找出密鑰K而偽造一個與截獲的而偽造一個與截獲的MAC相相匹配的新消息在計算上是不可行的。第匹配的新消息在計算上是不可行的。第2個要求是說個要求是說敵手如果截獲

16、一個敵手如果截獲一個MAC，則偽造一個相匹配的消息則偽造一個相匹配的消息的概率為最小。最后一個要求是說函數(shù)的概率為最小。最后一個要求是說函數(shù)C不應(yīng)在消息不應(yīng)在消息的某個部分或某些比特弱于其他部分或其他比特，的某個部分或某些比特弱于其他部分或其他比特，否則敵手獲得否則敵手獲得M和和MAC后就有可能修改后就有可能修改M中弱的部中弱的部分，從而偽造出一個與原分，從而偽造出一個與原MAC相匹配的新消息。相匹配的新消息。數(shù)據(jù)認證算法是最為廣泛使用的消息認證碼中的一數(shù)據(jù)認證算法是最為廣泛使用的消息認證碼中的一個，已作為個，已作為FIPS Publication（FIPS PUB 113）并被并被ANSI作

17、為作為X9.17標準。標準。算法基于算法基于CBC模式的模式的DES算法，其初始向量取為零算法，其初始向量取為零向量。需被認證的數(shù)據(jù)（消息、記錄、文件或程序）向量。需被認證的數(shù)據(jù)（消息、記錄、文件或程序）被分為被分為64比特長的分組比特長的分組D1，D2，DN，其中最后其中最后一個分組不夠一個分組不夠64比特的話，可在其右邊填充一些比特的話，可在其右邊填充一些0，然后按以下過程計算數(shù)據(jù)認證碼（見圖然后按以下過程計算數(shù)據(jù)認證碼（見圖6.2）：）：6.1.3 數(shù)據(jù)認證算法數(shù)據(jù)認證算法圖圖6.2 數(shù)據(jù)認證算法數(shù)據(jù)認證算法其中其中E為為DES加密算法，加密算法，K為密鑰。為密鑰。數(shù)據(jù)認證碼或者取為數(shù)據(jù)

18、認證碼或者取為ON或者取為或者取為ON的最左的最左M個比特，個比特，其中其中16M64。112213321()()()()KKKNKNNOEDOEDOOEDOOEDO雜湊函數(shù)雜湊函數(shù)H是一公開函數(shù)，用于將任意長的消息是一公開函數(shù)，用于將任意長的消息M映映射為較短的、固定長度的一個值射為較短的、固定長度的一個值H(M)，作為認證符，作為認證符，稱函數(shù)值稱函數(shù)值H(M)為雜湊值、雜湊碼或消息摘要。雜湊為雜湊值、雜湊碼或消息摘要。雜湊碼是消息中所有比特的函數(shù)，因此提供了一種碼是消息中所有比特的函數(shù)，因此提供了一種錯誤錯誤檢測檢測能力，即改變消息中任何一個比特或幾個比特能力，即改變消息中任何一個比特或

19、幾個比特都會使雜湊碼發(fā)生改變。都會使雜湊碼發(fā)生改變。6.2 雜湊函數(shù)雜湊函數(shù) 6.2.1 雜湊函數(shù)的定義及使用方式雜湊函數(shù)的定義及使用方式圖圖6.3 表示雜湊函數(shù)用來提供消息認證的基本使用方表示雜湊函數(shù)用來提供消息認證的基本使用方式，共有以下式，共有以下6種種（見（見142頁圖頁圖6.3）：）： 消息與雜湊碼鏈接后用單鑰加密算法加密。由于消息與雜湊碼鏈接后用單鑰加密算法加密。由于所用密鑰僅為收發(fā)雙方所用密鑰僅為收發(fā)雙方A、B共享，因此可保證消息共享，因此可保證消息的確來自的確來自A并且未被篡改。同時還由于消息和雜湊碼并且未被篡改。同時還由于消息和雜湊碼都被加密，這種方式還提供了保密性，見圖都被

20、加密，這種方式還提供了保密性，見圖6.3(a)。 用單鑰加密算法僅對雜湊碼加密。這種方式用于用單鑰加密算法僅對雜湊碼加密。這種方式用于不要求保密性的情況下，可減少處理負擔(dān)。注意這不要求保密性的情況下，可減少處理負擔(dān)。注意這種方式和圖種方式和圖6.1(a)的的MAC結(jié)果完全一樣，即將結(jié)果完全一樣，即將EKH(M)看作一個函數(shù)，函數(shù)的輸入為消息看作一個函數(shù)，函數(shù)的輸入為消息M和密和密鑰鑰K，輸出為固定長度，見圖輸出為固定長度，見圖6.3(b)。 用公鑰加密算法和發(fā)送方的秘密鑰僅加密雜湊碼。用公鑰加密算法和發(fā)送方的秘密鑰僅加密雜湊碼。和一樣，這種方式提供認證性，又由于只有發(fā)送和一樣，這種方式提供認證

21、性，又由于只有發(fā)送方能產(chǎn)生加密的雜湊碼，因此這種方式還對發(fā)送方方能產(chǎn)生加密的雜湊碼，因此這種方式還對發(fā)送方發(fā)送的消息提供了數(shù)字簽字，事實上這種方式就是發(fā)送的消息提供了數(shù)字簽字，事實上這種方式就是數(shù)字簽字，見圖數(shù)字簽字，見圖6.3(c)。 消息的雜湊值用公鑰加密算法和發(fā)送方的秘密鑰消息的雜湊值用公鑰加密算法和發(fā)送方的秘密鑰加密后與消息鏈接，再對鏈接后的結(jié)果用單鑰加密加密后與消息鏈接，再對鏈接后的結(jié)果用單鑰加密算法加密，這種方式提供了保密性和數(shù)字簽字，見算法加密，這種方式提供了保密性和數(shù)字簽字，見圖圖6.3(d)。 使用這種方式時要求通信雙方共享一個秘密值使用這種方式時要求通信雙方共享一個秘密值S

22、，A計算消息計算消息M和秘密值和秘密值S鏈接在一起的雜湊值，并將鏈接在一起的雜湊值，并將此雜湊值附加到此雜湊值附加到M后發(fā)往后發(fā)往B。因因B也有也有S，所以可重新所以可重新計算雜湊值以對消息進行認證。由于秘密值計算雜湊值以對消息進行認證。由于秘密值S本身未本身未被發(fā)送，敵手無法對截獲的消息加以篡改，也無法被發(fā)送，敵手無法對截獲的消息加以篡改，也無法產(chǎn)生假消息。這種方式僅提供認證，見圖產(chǎn)生假消息。這種方式僅提供認證，見圖6.3(e)。 這種方式是在中消息與雜湊值鏈接以后再增加這種方式是在中消息與雜湊值鏈接以后再增加單鑰加密運算，從而又可提供保密性，見圖單鑰加密運算，從而又可提供保密性，見圖6.3

23、(f)。由于加密運算的速度較慢，代價較高，而且很多加由于加密運算的速度較慢，代價較高，而且很多加密算法還受到專利保護，因此在不要求保密性的情密算法還受到專利保護，因此在不要求保密性的情況下，方式和將比其他方式更具優(yōu)勢。況下，方式和將比其他方式更具優(yōu)勢。圖圖6-3 雜湊函數(shù)的基本使用方式雜湊函數(shù)的基本使用方式雜湊函數(shù)的目的是為需認證的數(shù)據(jù)產(chǎn)生一個雜湊函數(shù)的目的是為需認證的數(shù)據(jù)產(chǎn)生一個“指指紋紋”。為了能夠?qū)崿F(xiàn)對數(shù)據(jù)的認證，雜湊函數(shù)應(yīng)滿。為了能夠?qū)崿F(xiàn)對數(shù)據(jù)的認證，雜湊函數(shù)應(yīng)滿足以下條件：足以下條件： 函數(shù)的輸入可以是任意長。函數(shù)的輸入可以是任意長。 函數(shù)的輸出是固定長。函數(shù)的輸出是固定長。 已知已

24、知x，求求H(x)較為容易，可用硬件或軟件實現(xiàn)。較為容易，可用硬件或軟件實現(xiàn)。 已知已知h，求使得求使得H(x)=h的的x在計算上是不可行的，在計算上是不可行的，這一性質(zhì)稱為函數(shù)的單向性，稱這一性質(zhì)稱為函數(shù)的單向性，稱H(x)為單向雜湊函數(shù)。為單向雜湊函數(shù)。6.2.2 雜湊函數(shù)應(yīng)滿足的條件雜湊函數(shù)應(yīng)滿足的條件 已知已知x，找出找出y(yx)使得使得H(y)=H(x)在計算上是不可在計算上是不可行的。行的。如果單向雜湊函數(shù)滿足這一性質(zhì)，則稱其為如果單向雜湊函數(shù)滿足這一性質(zhì)，則稱其為弱單向弱單向雜湊函數(shù)。雜湊函數(shù)。 找出任意兩個不同的輸入找出任意兩個不同的輸入x、y，使得使得H(y)=H(x)在在

25、計算上是不可行的。計算上是不可行的。如果單向雜湊函數(shù)滿足這一性質(zhì)，則稱其為如果單向雜湊函數(shù)滿足這一性質(zhì)，則稱其為強單向強單向雜湊函數(shù)雜湊函數(shù)。第和第個條件給出了雜湊函數(shù)無碰撞性的概念，第和第個條件給出了雜湊函數(shù)無碰撞性的概念，如果雜湊函數(shù)對不同的輸入可產(chǎn)生相同的輸出，則如果雜湊函數(shù)對不同的輸入可產(chǎn)生相同的輸出，則稱該函數(shù)具有碰撞性。稱該函數(shù)具有碰撞性。以上以上6個條件中，前個條件中，前3個是雜湊函數(shù)能用于消息認證個是雜湊函數(shù)能用于消息認證的基本要求。第的基本要求。第4個條件（即單向性）則對使用秘密個條件（即單向性）則對使用秘密值的認證技術(shù)值的認證技術(shù)(見圖見圖6.3(e)極為重要。假如雜湊函數(shù)

26、極為重要。假如雜湊函數(shù)不具有單向性，則攻擊者截獲不具有單向性，則攻擊者截獲M和和C=H(SM)后，求后，求C的逆的逆SM，就可求出秘密值就可求出秘密值S。第第5個條件使得敵手個條件使得敵手無法在已知某個消息時，找到與該消息具有相同雜無法在已知某個消息時，找到與該消息具有相同雜湊值的另一消息。這一性質(zhì)用于雜湊值被加密情況湊值的另一消息。這一性質(zhì)用于雜湊值被加密情況時時(見圖見圖6.3(b)和圖和圖6.3(c)防止敵手的偽造，由于在這防止敵手的偽造，由于在這種情況下，敵手可讀取傳送的明文消息種情況下，敵手可讀取傳送的明文消息M，因此能因此能產(chǎn)生該消息的雜湊值產(chǎn)生該消息的雜湊值H(M)。但由于敵手不

27、知道用于加密雜湊值的密鑰，他就不但由于敵手不知道用于加密雜湊值的密鑰，他就不可能既偽造一個消息可能既偽造一個消息M，又偽造這個消息的雜湊值又偽造這個消息的雜湊值加密后的密文加密后的密文EKH(M)。然而，如果第然而，如果第5個條件不成個條件不成立，敵手在截獲明文消息及其加密的雜湊值后，就立，敵手在截獲明文消息及其加密的雜湊值后，就可按以下方式偽造消息：首先求出截獲的消息的雜可按以下方式偽造消息：首先求出截獲的消息的雜湊值，然后產(chǎn)生一個具有相同雜湊值的偽造消息，湊值，然后產(chǎn)生一個具有相同雜湊值的偽造消息，最后再將偽造的消息和截獲的加密的雜湊值發(fā)往通最后再將偽造的消息和截獲的加密的雜湊值發(fā)往通信的

28、接收方。第信的接收方。第6個條件用于抵抗生日攻擊。個條件用于抵抗生日攻擊。1. 相關(guān)問題相關(guān)問題已知一雜湊函數(shù)已知一雜湊函數(shù)H有有n個可能的輸出，個可能的輸出，H(x)是一個特定的輸出，如果對是一個特定的輸出，如果對H隨機取隨機取k個輸入，個輸入，則至少有一個輸入則至少有一個輸入y使得使得H(y)=H(x)的概率為的概率為0.5時，時，k有多大？有多大？以后為敘述方便，稱對雜湊函數(shù)以后為敘述方便，稱對雜湊函數(shù)H尋找上尋找上述述y的攻擊為第的攻擊為第類生日攻擊。類生日攻擊。6.2.3 生日攻擊生日攻擊因為因為H有有n個可能的輸出，所以輸入個可能的輸出，所以輸入y產(chǎn)生的輸出產(chǎn)生的輸出H(y)等于特

29、定輸出等于特定輸出H(x)的概率是的概率是1/n，反過來說反過來說H(y)H(x)的概率是的概率是1-1/n。y取取k個隨機值而函數(shù)的個隨機值而函數(shù)的k個輸出中沒個輸出中沒有一個等于有一個等于H(x)，其概率等于每個輸出都不等于其概率等于每個輸出都不等于H(x)的概率之積，為的概率之積，為1-1/nk，所以所以y取取k個隨機值得到函個隨機值得到函數(shù)的數(shù)的k個輸出中至少有一個等于個輸出中至少有一個等于H(x)的概率為的概率為1-1-1/nk。由由(1+x)k1+kx，其中其中|x|365，則不可能使得任意兩個數(shù)據(jù)則不可能使得任意兩個數(shù)據(jù)都不相同，因此假定都不相同，因此假定k365。k個數(shù)據(jù)項中任

30、意兩個個數(shù)據(jù)項中任意兩個都不相同的所有取值方式數(shù)為都不相同的所有取值方式數(shù)為365!365 364(3651)(365)!kk即第即第1個數(shù)據(jù)項可從個數(shù)據(jù)項可從365個中任取一個，第個中任取一個，第2個數(shù)據(jù)項個數(shù)據(jù)項可在剩余的可在剩余的364個中任取一個，依次類推，最后一個個中任取一個，依次類推，最后一個數(shù)據(jù)項可從數(shù)據(jù)項可從365-k+1個值中任取一個。如果去掉任意個值中任取一個。如果去掉任意兩個都不相同這一限制條件，可得兩個都不相同這一限制條件，可得k個數(shù)據(jù)項中所有個數(shù)據(jù)項中所有取值方式數(shù)為取值方式數(shù)為365k。所以可得所以可得365!(365, )(365)! 365365!(365, )

31、1(365, )1(365)! 365kkQkkPkQkk 當(dāng)當(dāng)k=23時，時，P(365,23)=0.5073，即上述問即上述問題只需題只需23人，人數(shù)如此之少。人，人數(shù)如此之少。若若k取取100，則，則P(365,100)=0.9999997，即即獲得如此大的概率。獲得如此大的概率。之所以稱這一問題是悖論是因為當(dāng)人數(shù)之所以稱這一問題是悖論是因為當(dāng)人數(shù)k給定時，得到的至少有兩個人的生日相同的概率比給定時，得到的至少有兩個人的生日相同的概率比想象的要大得多。這是因為在想象的要大得多。這是因為在k個人中考慮的是任意個人中考慮的是任意兩個人的生日是否相同，在兩個人的生日是否相同，在23個人中可能的

32、情況數(shù)個人中可能的情況數(shù)為為C223=253。將生日悖論推廣為下述問題：已知一個在將生日悖論推廣為下述問題：已知一個在1到到n之間之間均勻分布的整數(shù)型隨機變量，若該變量的均勻分布的整數(shù)型隨機變量，若該變量的k個取值中個取值中至少有兩個取值相同的概率大于至少有兩個取值相同的概率大于0.5，則，則k至少多大？至少多大？與上類似，與上類似， ，令令P(n, k)0.5，可可得得 。若取若取n=365，則則 。!( , )1()!knP n knkn 1.18knn1.18 36522.54k 3. 生日攻擊生日攻擊生日攻擊是基于下述結(jié)論：設(shè)雜湊函數(shù)生日攻擊是基于下述結(jié)論：設(shè)雜湊函數(shù)H有有2m個可能的

33、輸出（即輸出長個可能的輸出（即輸出長m比特），如果比特），如果H的的k個隨機輸入中至少有兩個產(chǎn)生相同輸出的概率大于個隨機輸入中至少有兩個產(chǎn)生相同輸出的概率大于0.5，則，則 。稱尋找函數(shù)稱尋找函數(shù)H的具有相同輸出的兩個任意的具有相同輸出的兩個任意輸入的攻擊方式為第輸入的攻擊方式為第類生日攻擊。類生日攻擊。222mmk 第第類生日攻擊可按以下方式進行：類生日攻擊可按以下方式進行： 設(shè)用戶將用圖設(shè)用戶將用圖6.3(c)所示的方式發(fā)送消息，即所示的方式發(fā)送消息，即A用用自己的秘密鑰對消息的雜湊值加密，加密結(jié)果作為自己的秘密鑰對消息的雜湊值加密，加密結(jié)果作為對消息的簽字，連同明文消息一起發(fā)往接收者。對

34、消息的簽字，連同明文消息一起發(fā)往接收者。 敵手對敵手對A發(fā)送的消息發(fā)送的消息M產(chǎn)生出產(chǎn)生出2m/2個變形的消息，個變形的消息，每個變形的消息本質(zhì)上的含義與原消息相同，同時每個變形的消息本質(zhì)上的含義與原消息相同，同時敵手還準備一個假冒的消息敵手還準備一個假冒的消息M，并對假冒的消息產(chǎn)并對假冒的消息產(chǎn)生出生出2m/2個變形的消息。個變形的消息。 敵手在產(chǎn)生的兩個消息集合中，找出雜湊值相同敵手在產(chǎn)生的兩個消息集合中，找出雜湊值相同的一對消息的一對消息, ，由上述討論可知敵手成功的概由上述討論可知敵手成功的概率大于率大于0.5。如果不成功，則重新產(chǎn)生一個假冒的消。如果不成功，則重新產(chǎn)生一個假冒的消息，

35、并產(chǎn)生息，并產(chǎn)生2m/2個變形，直到找到雜湊值相同的一對個變形，直到找到雜湊值相同的一對消息為止。消息為止。 敵手將敵手將 提交給提交給A請求簽字，由于請求簽字，由于 與與 的雜的雜湊值相同，所以可將湊值相同，所以可將A對對 的簽字當(dāng)作對的簽字當(dāng)作對 的簽字，的簽字，將此簽字連同將此簽字連同 一起發(fā)給意欲的接收者。一起發(fā)給意欲的接收者。,M MMMMMMM上述攻擊中如果雜湊值的長為上述攻擊中如果雜湊值的長為64比特，則敵手攻擊比特，則敵手攻擊成功所需的時間復(fù)雜度為成功所需的時間復(fù)雜度為O(232)。將一個消息變形為具有相同含義的另一消息的方法將一個消息變形為具有相同含義的另一消息的方法有很多，

36、例如對文件，敵手可在文件的單詞之間插有很多，例如對文件，敵手可在文件的單詞之間插入很多入很多“space-space-backspace”字符對，然后將其字符對，然后將其中的某些字符對替換為中的某些字符對替換為“space-backspace-space ”就就得到一個變形的消息。得到一個變形的消息。目前使用的大多數(shù)雜湊函數(shù)如目前使用的大多數(shù)雜湊函數(shù)如MD5、SHA，其結(jié)構(gòu)其結(jié)構(gòu)都是迭代型的，如圖都是迭代型的，如圖6.4所示。其中函數(shù)的輸入所示。其中函數(shù)的輸入M被被分為分為L個分組個分組Y0,Y1,YL-1，每一個分組的長度為每一個分組的長度為b比比特，最后一個分組的長度不夠的話，需對其做填充

37、。特，最后一個分組的長度不夠的話，需對其做填充。最后一個分組中還包括整個函數(shù)輸入的長度值，這最后一個分組中還包括整個函數(shù)輸入的長度值，這樣一來，將使得敵手的攻擊更為困難，即敵手若想樣一來，將使得敵手的攻擊更為困難，即敵手若想成功地產(chǎn)生假冒的消息，就必須保證假冒消息的雜成功地產(chǎn)生假冒的消息，就必須保證假冒消息的雜湊值與原消息的雜湊值相同，而且假冒消息的長度湊值與原消息的雜湊值相同，而且假冒消息的長度也要與原消息的長度相等。也要與原消息的長度相等。6.2.4 迭代型雜湊函數(shù)的一般結(jié)構(gòu)迭代型雜湊函數(shù)的一般結(jié)構(gòu)圖圖6.4 迭代型雜湊函數(shù)的一般結(jié)構(gòu)迭代型雜湊函數(shù)的一般結(jié)構(gòu)算法中重復(fù)使用一壓縮函數(shù)算法中重

38、復(fù)使用一壓縮函數(shù)f（注意，有些書將雜湊注意，有些書將雜湊函數(shù)也稱為壓縮函數(shù)，在此用壓縮函數(shù)表示雜湊函函數(shù)也稱為壓縮函數(shù)，在此用壓縮函數(shù)表示雜湊函數(shù)中的一個特定部分），數(shù)中的一個特定部分），f 的輸入有兩項，一項是上的輸入有兩項，一項是上一輪（第一輪（第i-1輪）輸出的輪）輸出的n比特值比特值CVi-1，稱為鏈接變量，稱為鏈接變量，另一項是算法在本輪（第另一項是算法在本輪（第i輪）的輪）的b比特輸入分組比特輸入分組Yi。f 的輸出為的輸出為n比特值比特值CVi，CVi又作為下一輪的輸入。又作為下一輪的輸入。算法開始時還需對鏈接變量指定一個初值算法開始時還需對鏈接變量指定一個初值IV，最后最后一輪

39、輸出的鏈接變量一輪輸出的鏈接變量CVL即為最終產(chǎn)生的雜湊值。即為最終產(chǎn)生的雜湊值。通常有通常有bn，因此稱函數(shù)因此稱函數(shù)f為壓縮函數(shù)。算法可表達為壓縮函數(shù)。算法可表達如下：如下：CV0=IV=n比特長的初值；比特長的初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVL算法的核心技術(shù)是設(shè)計無碰撞的壓縮函數(shù)算法的核心技術(shù)是設(shè)計無碰撞的壓縮函數(shù)f，而敵手而敵手對算法的攻擊重點是對算法的攻擊重點是f 的內(nèi)部結(jié)構(gòu)，由于的內(nèi)部結(jié)構(gòu)，由于f 和分組密和分組密碼一樣是由若干輪處理過程組成，所以對碼一樣是由若干輪處理過程組成，所以對f 的攻擊需的攻擊需通過對各輪之間的位模式的分析來進行，分析過程通

40、過對各輪之間的位模式的分析來進行，分析過程常常需要先找出常常需要先找出f 的碰撞。由于的碰撞。由于f 是壓縮函數(shù)，其碰是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計撞是不可避免的，因此在設(shè)計f 時就應(yīng)保證找出其碰時就應(yīng)保證找出其碰撞在計算上是不可行的。撞在計算上是不可行的。下面介紹幾個重要的迭代型雜湊函數(shù)。下面介紹幾個重要的迭代型雜湊函數(shù)。MD4是是MD5雜湊算法的前身，由雜湊算法的前身，由Ron Rivest于于1990年年10月作為月作為RFC提出，提出，1992年年4月公布的月公布的MD4的改進的改進（RFC 1320，1321）稱為稱為MD5。6.3 MD5雜湊算法雜湊算法MD5算法采用圖

41、算法采用圖6.4描述的迭代型雜湊函數(shù)的一般結(jié)描述的迭代型雜湊函數(shù)的一般結(jié)構(gòu)，算法的框圖如圖構(gòu)，算法的框圖如圖6.5所示。算法的輸入為任意長所示。算法的輸入為任意長的消息（圖中為的消息（圖中為K比特），分為比特），分為512比特長的分組，比特長的分組，輸出為輸出為128比特的消息摘要。比特的消息摘要。6.3.1 算法描述算法描述圖圖6.5 MD5的算法框圖的算法框圖處理過程有以下幾步：處理過程有以下幾步： 對消息填充對消息填充，使得其比特長在模對消息填充對消息填充，使得其比特長在模512下下為為448，即填充后消息的長度為，即填充后消息的長度為512的某一倍數(shù)減的某一倍數(shù)減64，留出的留出的64

42、比特備第比特備第2步使用。步驟是必需的，即使步使用。步驟是必需的，即使消息長度已滿足要求，仍需填充。例如，消息長為消息長度已滿足要求，仍需填充。例如，消息長為448比特，則需填充比特，則需填充512比特，使其長度變?yōu)楸忍?，使其長度變?yōu)?60，因，因此填充的比特數(shù)大于等于此填充的比特數(shù)大于等于1而小于等于而小于等于512。填充方式是固定的，即第填充方式是固定的，即第1位為位為1，其后各位皆為，其后各位皆為0。 附加消息的長度用步驟留出的附加消息的長度用步驟留出的64比特以比特以little-endian方式來表示消息被填充前的長度。如果消息長方式來表示消息被填充前的長度。如果消息長度大于度大于2

43、64，則以，則以264為模數(shù)取模。為模數(shù)取模。Little-endian方式是指按數(shù)據(jù)的最低有效字節(jié)（方式是指按數(shù)據(jù)的最低有效字節(jié)（byte）（或最低有效位）優(yōu)先的順序存儲數(shù)據(jù)，即將最低或最低有效位）優(yōu)先的順序存儲數(shù)據(jù)，即將最低有效字節(jié)（或最低有效位）存于低地址字節(jié)（或有效字節(jié)（或最低有效位）存于低地址字節(jié)（或位）。相反的存儲方式稱為位）。相反的存儲方式稱為big-endian方式。方式。前兩步執(zhí)行完后，消息的長度為前兩步執(zhí)行完后，消息的長度為512的倍數(shù)（設(shè)為的倍數(shù)（設(shè)為L倍），則可將消息表示為分組長為倍），則可將消息表示為分組長為512的一系列分組的一系列分組Y0，Y1，YL-1，而每一分

44、組又可表示為而每一分組又可表示為16個個32比比特長的字，這樣消息中的總字數(shù)為特長的字，這樣消息中的總字數(shù)為N=L16，因此因此消息又可按字表示為消息又可按字表示為M0,N-1。 對對MD緩沖區(qū)初始化算法使用緩沖區(qū)初始化算法使用128比特長的緩沖區(qū)比特長的緩沖區(qū)以存儲中間結(jié)果和最終雜湊值，緩沖區(qū)可表示為以存儲中間結(jié)果和最終雜湊值，緩沖區(qū)可表示為4個個32比特長的寄存器（比特長的寄存器（A，B，C，D），），每個寄存器都每個寄存器都以以littleendian方式存儲數(shù)據(jù)，其初值取為（以存儲方式存儲數(shù)據(jù)，其初值取為（以存儲方式）方式）A=01234567，B=89ABCDEF， C=FEDCBA

45、98，D=76543210，實際上為實際上為67452301，EFCDAB89，98BADCFE，10325476。 以分組為單位對消息進行處理每一分組以分組為單位對消息進行處理每一分組Yq(q=0,L-1)都經(jīng)一壓縮函數(shù)都經(jīng)一壓縮函數(shù)HMD5處理。處理。HMD5是算是算法的核心，其中又有法的核心，其中又有4輪處理過程，如圖輪處理過程，如圖6.6所示。所示。 輸出消息的輸出消息的L個分組都被處理完后，最后一個個分組都被處理完后，最后一個HMD5的輸出即為產(chǎn)生的消息摘要。的輸出即為產(chǎn)生的消息摘要。圖圖6.6 MD5的分組處理框圖的分組處理框圖圖圖6.6 MD5的分組處理框圖的分組處理框圖HMD5

46、的的4輪處理過程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不輪處理過程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不同，分別表示為同，分別表示為F、G、H、I。每輪的輸入為當(dāng)前處每輪的輸入為當(dāng)前處理的消息分組理的消息分組Yq和緩沖區(qū)的當(dāng)前值和緩沖區(qū)的當(dāng)前值A(chǔ)、B、C、D，輸輸出仍放在緩沖區(qū)中以產(chǎn)生新的出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。每輪處每輪處理過程還需加上常數(shù)表理過程還需加上常數(shù)表T中四分之一個元素，分別為中四分之一個元素，分別為T116, T1732, T3348, T4964。表表T有有64個元素，見表個元素，見表6.1，第，第i個元素個元素Ti為為232abs(sin(i)的的整數(shù)部分，其中整數(shù)部分，其中si

47、n為正弦函數(shù)，為正弦函數(shù)，i以弧度為單位。由以弧度為單位。由于于abs(sin(i)大于大于0小于小于1，所以，所以Ti可由可由32比特的字比特的字表示。第表示。第4輪的輸出再與第輪的輸出再與第1輪的輸入輪的輸入CVq相加，相加相加，相加時將時將CVq看作看作4個個32比特的字，每個字與第比特的字，每個字與第4輪輸出的輪輸出的對應(yīng)的字按模對應(yīng)的字按模232相加，相加的結(jié)果即為壓縮函數(shù)相加，相加的結(jié)果即為壓縮函數(shù)HMD5的輸出。（見的輸出。（見151頁表頁表6.1）步驟到步驟的處理過程可總結(jié)如下：步驟到步驟的處理過程可總結(jié)如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq

48、,RFFYq,CVqMD=CVL其中其中IV是步驟所取的緩沖區(qū)是步驟所取的緩沖區(qū)ABCD的初值，的初值，Yq是是消息的第消息的第q個個512比特長的分組，比特長的分組，L是消息經(jīng)過步驟是消息經(jīng)過步驟和步驟處理后的分組數(shù)，和步驟處理后的分組數(shù)，CVq為處理消息的第為處理消息的第q個個分組時輸入的鏈接變量（即前一個壓縮函數(shù)的輸分組時輸入的鏈接變量（即前一個壓縮函數(shù)的輸出），出），RFx為使用基本邏輯函數(shù)為使用基本邏輯函數(shù)x的輪函數(shù)，的輪函數(shù)，+為對應(yīng)為對應(yīng)字的模字的模232加法，加法，MD為最終的雜湊值。為最終的雜湊值。壓縮函數(shù)壓縮函數(shù)HMD5中有中有4輪處理過程，每輪又對緩沖區(qū)輪處理過程，每輪又

49、對緩沖區(qū)ABCD進行進行16步迭代運算，每一步的運算形式為（見步迭代運算，每一步的運算形式為（見圖圖6.7）ab+CLSs(a+g(b,c,d)+Xk+TI)其中其中a、b、c、d為緩沖區(qū)的為緩沖區(qū)的4個字，運算完成后再右個字，運算完成后再右循環(huán)一個字，即得這一步迭代的輸出。循環(huán)一個字，即得這一步迭代的輸出。g是基本邏輯是基本邏輯函數(shù)函數(shù)F、G 、H、I之一。之一。CLSs是左循環(huán)移是左循環(huán)移s位，位，s的取的取值由表值由表6.2給出。（見給出。（見152頁表頁表6.2）6.3.2 MD5的壓縮函數(shù)的壓縮函數(shù)圖圖6.7 壓縮函數(shù)中的一步迭代示意圖壓縮函數(shù)中的一步迭代示意圖Ti為表為表T中的第中

50、的第i個字，個字，+為模為模232加法。加法。Xk=Mq16+k，即消息第即消息第q個分組中的第個分組中的第k個字個字（k=1,16）。）。4輪處理過程中，每輪以不同的次序輪處理過程中，每輪以不同的次序使用使用16個字，其中在第個字，其中在第1輪以字的初始次序使用。第輪以字的初始次序使用。第2輪到第輪到第4輪分別對字的次序輪分別對字的次序i做置換后得到一個新次做置換后得到一個新次序，然后以新次序使用序，然后以新次序使用16個字。個字。3個置換分別為個置換分別為2(i)=(1+5i) mod 163(i)=(5+3i) mod 164(i)=7i mod 164輪處理過程分別使用不同的基本邏輯函

51、數(shù)輪處理過程分別使用不同的基本邏輯函數(shù)F、G、H、I，每個邏輯函數(shù)的輸入為每個邏輯函數(shù)的輸入為3個個32比特的字，輸出是一比特的字，輸出是一個個32比特的字，其中的運算為逐比特的邏輯運算，比特的字，其中的運算為逐比特的邏輯運算，即輸出的第即輸出的第n個比特是個比特是3個輸入的第個輸入的第n個比特的函數(shù)，個比特的函數(shù)，函數(shù)的定義由表函數(shù)的定義由表6.3給出，其中給出，其中，-，分別是分別是邏輯與、邏輯或、邏輯非和異或運算，表邏輯與、邏輯或、邏輯非和異或運算，表6.4是四個是四個函數(shù)的真值表。（見函數(shù)的真值表。（見153頁表頁表6.3和和6.4）6.3.3 MD5的安全性的安全性安全雜湊算法安全雜

52、湊算法SHA(Secure Hash Algorithm)由美國由美國NIST設(shè)計，于設(shè)計，于1993年作為聯(lián)邦信年作為聯(lián)邦信息處理標準（息處理標準（FIPS PUB 180）公布。）公布。SHA-0是是SHA的早期版本，的早期版本，SHA-0被公布后，被公布后，NIST很快就發(fā)現(xiàn)了很快就發(fā)現(xiàn)了它的缺陷，修改后的版本稱為它的缺陷，修改后的版本稱為SHA-1，簡稱為，簡稱為SHA。SHA是基于是基于MD4算法，其結(jié)構(gòu)與算法，其結(jié)構(gòu)與MD4非常類似。非常類似。 6.4 安全雜湊算法安全雜湊算法算法的輸入為小于算法的輸入為小于264比特長的任意消息，分為比特長的任意消息，分為512比比特長的分組，輸

53、出為特長的分組，輸出為160比特長的消息摘要。算法的比特長的消息摘要。算法的框圖與圖框圖與圖6.5一樣，但雜湊值的長度和鏈接變量的長一樣，但雜湊值的長度和鏈接變量的長度為度為160比特。比特。6.4.1 算法描述算法描述算法的處理過程有以下幾步：算法的處理過程有以下幾步： 對消息填充與對消息填充與MD5的步驟完全相同。的步驟完全相同。 附加消息的長度與附加消息的長度與MD5的步驟類似，不同之處的步驟類似，不同之處在于以在于以big-endian方式表示填充前消息的長度。即步方式表示填充前消息的長度。即步驟留出的驟留出的64比特當(dāng)作比特當(dāng)作64比特長的無符號整數(shù)。比特長的無符號整數(shù)。 對對MD緩

54、沖區(qū)初始化算法使用緩沖區(qū)初始化算法使用160比特長的緩沖區(qū)比特長的緩沖區(qū)存儲中間結(jié)果和最終雜湊值，緩沖區(qū)可表示為存儲中間結(jié)果和最終雜湊值，緩沖區(qū)可表示為5個個32比特長的寄存器比特長的寄存器(A, B, C, D, E)，每個寄存器都以每個寄存器都以big-endian方式存儲數(shù)據(jù)，其初始值分別為方式存儲數(shù)據(jù)，其初始值分別為A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。 以分組為單位對消息進行處理每一分組以分組為單位對消息進行處理每一分組Yq都經(jīng)一都經(jīng)一壓縮函數(shù)處理，壓縮函數(shù)處理，壓縮函數(shù)由壓縮函數(shù)由4輪處理過程輪處理過程（如圖（

55、如圖6.8所所示）構(gòu)成，示）構(gòu)成，每一輪又由每一輪又由20步迭代組成步迭代組成。4輪處理過程輪處理過程結(jié)構(gòu)一樣，但所用的基本邏輯函數(shù)不同，分別表示結(jié)構(gòu)一樣，但所用的基本邏輯函數(shù)不同，分別表示為為f1,f2,f3,f4。每輪的輸入為當(dāng)前處理的消息分組每輪的輸入為當(dāng)前處理的消息分組Yq和和緩沖區(qū)的當(dāng)前值緩沖區(qū)的當(dāng)前值A(chǔ),B,C,D,E，輸出仍放在緩沖區(qū)以替輸出仍放在緩沖區(qū)以替代代A,B,C,D,E的舊值，每輪處理過程還需加上一個加的舊值，每輪處理過程還需加上一個加法常量法常量Kt，其中其中0t79表示迭代的步數(shù)。表示迭代的步數(shù)。80個常量個常量中實際上只有中實際上只有4個不同取值，如表個不同取值，

56、如表6.5所示，其中所示，其中 為為x的整數(shù)部分。（見的整數(shù)部分。（見155頁表頁表6.5）x 第第4輪的輸出（即第輪的輸出（即第80步迭代的輸出）再與第步迭代的輸出）再與第1輪的輪的輸入輸入CVq相加，以產(chǎn)生相加，以產(chǎn)生CVq+1，其中加法是緩沖區(qū)其中加法是緩沖區(qū)5個個字中的每一個字與字中的每一個字與CVq中相應(yīng)的字模中相應(yīng)的字模232相加。相加。 輸出消息的輸出消息的L個分組都被處理完后，最后一個分組個分組都被處理完后，最后一個分組的輸出即為的輸出即為160比特的消息摘要。比特的消息摘要。步驟到步驟的處理過程可總結(jié)如下：步驟到步驟的處理過程可總結(jié)如下：CV0=IV;CVq+1=SUM32(

57、CVq,ABCDEq);MD=CVL其中其中IV是步驟定義的緩沖區(qū)是步驟定義的緩沖區(qū)ABCDE的初值，的初值，ABCDEq是第是第q個消息分組經(jīng)最后一輪處理過程處理個消息分組經(jīng)最后一輪處理過程處理后的輸出，后的輸出，L是消息（包括填充位和長度字段）的分是消息（包括填充位和長度字段）的分組數(shù)，組數(shù)，SUM32是對應(yīng)字的模是對應(yīng)字的模232加法，加法，MD為最終的摘為最終的摘要值。要值。如上所述，如上所述，SHA的壓縮函數(shù)由的壓縮函數(shù)由4輪處理過程組成，每輪處理過程組成，每輪處理過程又由對緩沖區(qū)輪處理過程又由對緩沖區(qū)ABCDE的的20步迭代運算組步迭代運算組成，每一步迭代運算的形式為（見圖成，每一

58、步迭代運算的形式為（見圖6.9）其中其中A，B，C，D，E為緩沖區(qū)的為緩沖區(qū)的5個字，個字，t是迭代的是迭代的步數(shù)（步數(shù)（0t79），），ft(B,C,D)是第是第t步迭代使用的基本步迭代使用的基本邏輯函數(shù)，邏輯函數(shù)，CLSs為左循環(huán)移為左循環(huán)移s位，位，Wt是由當(dāng)前是由當(dāng)前512比比特長的分組導(dǎo)出的一個特長的分組導(dǎo)出的一個32比特長的字（導(dǎo)出方式見比特長的字（導(dǎo)出方式見下面），下面），Kt是加法常量，是加法常量，+是模是模232加法。加法。6.4.2 SHA的壓縮函數(shù)的壓縮函數(shù)530, , ,( , ,)( ),( ),tttA B C D EEf B C DCLSAWKA CLSBC D圖

59、圖6.9 SHA的壓縮函數(shù)中一步迭代示意圖的壓縮函數(shù)中一步迭代示意圖基本邏輯函數(shù)的輸入為基本邏輯函數(shù)的輸入為3個個32比特的字，輸出是一個比特的字，輸出是一個32比特的字，其中的運算為逐比特邏輯運算，即輸比特的字，其中的運算為逐比特邏輯運算，即輸出的第出的第n個比特是個比特是3個輸入的相應(yīng)比特的函數(shù)。函數(shù)個輸入的相應(yīng)比特的函數(shù)。函數(shù)的定義如表的定義如表6.6。表中。表中, ,分別是與、或、非、分別是與、或、非、異或異或4個邏輯運算，函數(shù)的真值表如表個邏輯運算，函數(shù)的真值表如表6.7所示。（見所示。（見156頁表頁表6.6，157頁表頁表6.7）單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式

60、單擊此處編輯母版副標題樣式單擊此處編輯母版副標題樣式單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版副標題樣式單擊此處編輯母版副標題樣式下面說明如何由當(dāng)前的輸入分組（下面說明如何由當(dāng)前的輸入分組（512比特長）導(dǎo)出比特長）導(dǎo)出Wt（32比特長）。前比特長）。前16個值（即個值（即W0,W1,W15）直直接取為輸入分組的接取為輸入分組的16個相應(yīng)的字，其余值（即個相應(yīng)的字，其余值（即W16,W17,W79）取為取為見圖見圖6.10。與。與MD5比較，比較，MD5直接用一個消息分組直接用一個消息分組的的16個字作為每步迭代的輸入，而個字作為每步迭代的輸入，而SHA則將輸入分則將輸