《信息安全引論》課件Chapter4

1、 身份的認證與完整性認證是現(xiàn)代密碼學的關鍵問題。認證性解決方案與單向散列函數(shù)、數(shù)字簽名密切相關。前面已經(jīng)學習過數(shù)字簽名，在本章我們先學習單向散列函數(shù)并集中力量研究認證問題。第4章 單向散列函數(shù)本章內(nèi)容第1節(jié) 單向散列函數(shù)綜述第2節(jié) MD4算法第3節(jié) SHA-1算法第4節(jié) 單向散列函數(shù)特點第5節(jié) 單向散列函數(shù)應用小結 單向散列函數(shù)是密碼學的一個重要概念，在密碼學中有重要的應用。本章講述了對于單向散列函數(shù)的要求，兩個重要的單向散列函數(shù)算法MD4和SHA-1。介紹了單向散列函數(shù)的特點以及單向散列函數(shù)的主要應用。作業(yè)題 1. 請你認真思考，還有什么密碼學的問題，可以用單向散列函數(shù)解決？或者為單向散列函

2、數(shù)找兩個新的應用？ 2. 為什么單向散列函數(shù)要設計的那么復雜?有簡單的算法嗎? 如有,請?zhí)岢龈倪M意見。The End1. 單向散列函數(shù)綜述 字符串的長度：一個字符串的長度是指字符串中所包含的字符的個數(shù)。字符串1001010101的長度是9，123546的長度是6單向散列函數(shù)應當滿足以下要求單向散列函數(shù)的形式定義單向散列函數(shù) 設計一個以任意長度的消息為自變量的函數(shù)不是件容易的事；再要求單向就更難了。實際上設計單向散列函數(shù)時，往往采用與對稱加密算法DES相同的方法，對任意長度的消息，先進行分組，然后對每個分組進行若干輪運算，而每一輪的輸入是一個消息分組與前一輪計算的輸出，最后一個分組的最后一輪輸出

3、作為最后的單向散列函數(shù)值。單向散列函數(shù)單向散列函數(shù) 單向散列函數(shù)的算法有很多，例如Snefru算法(函數(shù)值為128或256比特)，N-Hash算法(日本電報電話公司設計的算法，函數(shù)值為128比特)，MD4算法，MD5算法，SHA安全散列算法，HAVAL算法，GOST散列函數(shù)(俄羅斯的散列函數(shù)標準，產(chǎn)生256比特的函數(shù)值)。應用最多的是MD5和SHA。限門單向函數(shù) 限門單向函數(shù)是有一個秘密限門的特殊的單向函數(shù)。它在一個方向上計算很容易而反方向卻很難計算，但是如果你知道那個秘密限門，反方向計算也就變得很容易。即很容易計算F(x), 但是給定F(x)要求x卻很難。然而有一個秘密消息y,如果知道F(x

4、)和y，就很容易計算x.BACK2. 單向散列函數(shù)MD4 MD4進行計算的消息長度L必須是512比特的整數(shù)倍，如果消息長度不是512比特的整數(shù)倍，需要填充到長度512的整數(shù)倍，至少為512比特。如果L是512的整數(shù)倍，需要額外填充512比特。填充方法如圖所示。MD4算法概述MD4概述(1) MD4產(chǎn)生的消息摘要是128比特的數(shù)據(jù)。每次處理的是512比特的分組。將這個512比特的分組分成16個32比特的字，分別記作m0, m1, m2, ., m15。首先給消息摘要一個固定的值。用這16個32比特的字依次去修改消息摘要的值。然后每次運算都取出當前的消息摘要與消息的下一個分組進行運算，以得到MD4

5、概述(2)新的消息摘要。每次計算都對消息分組進行三輪運算，每輪運算就重復運用這16個32比特的字。每次計算都將計算的結果與上一次計算的結果中對應的字相加，然后與一個32比特的消息相加，并進行一定數(shù)量的循環(huán)移位。最后的結果就是消息摘要。MD4算法概述(3)MD4算法概述(5)MD4中所用的操作MD4算法概述(4)首先我們看消息摘要的初值：消息摘要用4個字來表示，每個字為8個16進制數(shù)或者說一個32比特的數(shù)。MD4的第一輪函數(shù) MD4的每一輪運算就是要根據(jù)消息對d3, d2, d1, d0 進行修改，得到新的d3,d2, d1, d0 ，現(xiàn)在我們看是如何用消息對d3, d2, d1, d0 進行修

6、改的。對d3, d2, d1, d0的修改要用到一個函數(shù)F(x,y,z)。對i的解釋 上述公式中的i 就是指16個32比特的字的編號，取值范圍為0,1,15。通過計算可知，當處理第1個字(即i=1)時，修改的是d0, 當處理第2個字(即i=2)時，修改的是d3, 依此類推，處理每個字時，修改的是那一個d都可以計算出來。每一個i修改一個d，因為i的值有16個，只有4個d, 所以處理完一個512比特的分組，每個d都被重復修改了4次。MD4的第一輪函數(shù) 對MD4函數(shù)的解釋MD4的每一輪運算就是要根據(jù)消息對d3, d2, d1, d0進行修改，得到新的d3, d2, d1, d0 ，現(xiàn)在我們看是如何用

7、消息對d3, d2, d1, d0進行修改的。對d3, d2, d1, d0的修改要用到一個函數(shù)F(x,y,z)。函數(shù)F (x, y, z)輸入3個32比特的字，輸出一個32比特字?？梢苑Q為選擇函數(shù)或者抽簽函數(shù)。因為如果第一個輸入 x 的第 i 比特為1，函數(shù)的第i比特就選擇 y 的第i比特，如果第一個輸入 x 的第i比特為0，函數(shù)的第i比特就選擇 z 的第i 比特。If x then y, else z .MD4的第二輪運算 G ( x, y, z) 在課本上稱為擇多函數(shù)，因為只有在輸入的3個字的第i比特有3個，如果這3個比特中有2個以上為1(0)輸出的第i比特就為1(0)。我們可以稱之為投

8、票函數(shù)，因為輸出的第i比特，取決于3個輸入的第i比特中的多數(shù)情況，多數(shù)為1，就輸出1，多數(shù)為0就輸出0第二輪中的計算MD4的第三輪函數(shù)MD4的第三輪運算消息摘要值將三輪運算完成之后，將最后所得的連接起來，則消息摘要值ExampleMD4(The quick brown fox jumps over the lazy dog) = 1bee69a46ba8 11185c194762abaeae90MD4(The quick brown fox jumps over the lazy cog) = b86e130ce702 8da59e672d56ad0113df BACK3. 安全散列算法SHA

9、-1 SHA-1是NIST推薦的與DSA一起使用的散列算法，算法能處理的最長消息為264比特，輸出160比特的單向散列函數(shù)值。這個算法與MD4類似，但是速度要慢一點，也更安全一些，對于每個消息分組，SHA-1進行5輪運算。在進行散列運算前，SHA-1也需要將消息填充成512比特的整數(shù)倍，填充的方法與MD4相同。這里不再贅述。SHA-1算法概述SHA-1的運算概述SHA-1的一次運算SHA-1算法細節(jié)Wt 的生成SHA-的常數(shù)SHA-1的非線性函數(shù)4. 對單向散列函數(shù)的攻擊 對單向散列函數(shù)的攻擊主要是窮舉攻擊，但是根據(jù)攻擊者的目的不同可以有兩種攻擊：第1種是給定某個消息的散列值h=Hash (M

10、)，攻擊者要逐個產(chǎn)生產(chǎn)生一些消息，從中找到一個消息M，使得Hash (M)=Hash (M)。第二種攻擊方法稱為沖突攻擊，攻擊者尋找兩個隨機的消息M，M使得Hash (M)=Hash (M)。對單向散列函數(shù)的攻擊 沖突攻擊與生日悖論有重要的關系，有時也稱為生日攻擊。隨便拉出來多少個人，才能找到至少一個人與你的生日相同？另一個問題是隨便找多少個人在一起，才能使這些人中至少有兩個人的生日相同的概率大于0.5？ 答案是253和23(這個數(shù)字非常出人意料的小)。 對單向散列函數(shù)的攻擊 單向散列函數(shù)的長度：64比特的單向散列函數(shù)對付生日攻擊來說顯然太小。目前大多數(shù)的單向散列函數(shù)產(chǎn)生128比特的散列值，這

11、就迫使試圖進行生日攻擊的人必須進行對264個隨機文件進行散列運算才能夠找到散列值相同的兩個文件，但這也不足以維持散裂函數(shù)的安全性，因此SHA-1生成的是160比特的散列值。生日攻擊的計算公式生日攻擊的計算公式BACK5. 單向散列函數(shù)的特點 單向散列函數(shù)又稱為壓縮函數(shù)、收縮函數(shù)、消息摘要、消息指紋、密碼校驗和、鑒別性、操作檢驗碼等。在數(shù)字簽名、認證等方面有重要的應用。這是由單向散列函數(shù)的特點決定的。主要的特點有兩個： （1）兩個消息只要稍有不同，計算出的單向散列值就是不同的。 （2）找到具有某個散列值的消息，或者找到具有相同散列值的兩個消息在計算上是不可行的。BACK6. 單向散列函數(shù)的應用(

12、FIPS180-1) Applications: The SHA-1 may be used with the DSA in electronic mail, electronic funds transfer, software distribution, data storage, and other applications which require data integrity assurance and data origin authentication. The SHA-1 may also be used whenever it is necessary to generate a condensed version of a message.完整性認證(1) 認證問題是網(wǎng)絡應用中的重要問題，認證問題有兩種： (1) 信息完整性認證：Bob收到Alice發(fā)送的信息，這個信息是不是Alice發(fā)送的原始信息，即信息在發(fā)送過程是否受到過篡改。 (2) 實體身份認證：某個人聲稱她就是Alice，如何保證她確實就是Alice，而不是其他人冒充的。完整性認證(2) Alice向Bob發(fā)送一個消息，為了保證消息的完整性，Alice在發(fā)送消息的同時計算消息的單向散列函數(shù)值。Bob收到消息及單向散列函數(shù)之值后，計算消息的單向散列函數(shù)值，如果計算的結果和收到的