山大信息安全課件第6章 哈希函數(shù)

1、第6章 哈希函數(shù)6.1.哈希函數(shù) 當我們對長的文件使用DSS簽名時，需要把文件切成160 位的塊并逐塊分別簽名，最后拼接起來構成整個文件的簽名。這樣做存在問題是：文件的簽名太長.使用安全性好的簽名算法，計算簽名的時間花費太多.將所有簽名段的重新排序或刪除其中一些段，最后仍然能夠通過驗證。需要保證的是整個消息的完整性 . 密碼學哈希函數(shù)(Cryptography Hash Function)的基本思想是把哈希函數(shù)值 看成 的壓縮代表（稱為Imprint, Message Digest），即 中任意一位發(fā)生變化都將引起函數(shù)值的變化。這樣我們可以用對 的簽名代替對 的簽名。哈希函數(shù) ， ， 把任意有

2、限長的輸入行映射到固定長的行。哈希函數(shù)的值域與定義域相比規(guī)模要小得多，它是“多對一”的映射。所謂碰撞(Collision)是指定義域的兩個不同元素 映射到同一個象 上。哈希函數(shù)存在碰撞是必然的。我們把 和 從計算意義上唯一地聯(lián)系在一起，而找到碰撞在計算上是困難的。6.1.1哈希函數(shù)的性質哈希函數(shù)應滿足的要求是：1) 壓縮 任意長， 固定長；2) 容易從 計算出 。 單向性(one-way)基本上對所有事先指定的 ，找到 使 在計算上是困難的； 弱抗碰撞(Weak Collision Resistance) 已知 ，找 使 在計算上是困難的；5) 強抗碰撞(Strong Collision Re

3、sistance)找任 兩個不同的輸入 ，使 在計算上 是困難的.其中1）2）是對哈希函數(shù)的基本要求。例如： ， 滿足基本要求但不 滿足單向性3）。 ， 是大素數(shù)， ，不滿足1）和4）5）。為什么要提出性質3）4）和5）呢？如果哈希函數(shù)不滿足3），則對手有可能用特定簽名方案偽造隨機消息摘要z 上的簽名。例如對手掌握隨機消息摘要z 上的簽名y，他可以找到消息x 使 ，則 ( x, y ) 就是合格的偽造品。為此我們希望哈希函數(shù)滿足單向性質。如果我們不是對消息本身簽名而是對消息摘要簽名，那么就希望哈希函數(shù)滿足性質4）。否則對手看到A在上的簽名 后去找 使 ，而且聲稱A是對 簽名。如果讓對手能自己選

4、送消息請A簽名，則要求哈希函數(shù)滿足性質5）。否則對手找一對 使得 ，對手先讓A對 簽名，而后聲稱A是對 簽名。不難看出由性質5）可以推出性質4）。但是由性質5）不能推出性質3）。例如：g是滿足性質5）的哈希函數(shù)，定義 。那么取以1打頭長度為n+1的y，它的原象就是y的后面n位。6.1.2 哈希函數(shù)的用法 哈希函數(shù)是一種消息認證碼(Message Authentication Code)，它對消息產(chǎn)生一個短小的值。哈希函數(shù)是整個消息x的函數(shù)，消息中任意一位改變都將引起哈希函數(shù)值的改變。所謂認證是指一個證實收到的消息源可信且未被篡改的過程。有多種使用哈希函數(shù)方式來提供消息認證。已知A和B共享密鑰K

5、，如果A發(fā)送給B 1) 提供保密（僅雙方共享K）和認證（加密保護哈希值）. 2) 提供認證（加密保護哈希值）. 提供認證和數(shù)字簽名（加密保護 哈希值，僅發(fā)送方能生成簽名）. 提供保密（僅雙方共享K）、認證 和數(shù)字簽名. 5) 提供保密、認證和數(shù)字簽名（僅雙方共享S） . 提供保密、認證和數(shù)字簽名（僅雙方共享K,S） .對于不需要消息保密的應用中使用2）3）可以降低計算量。由于加密軟件慢、硬件費用高、加密算法專利保護、出口限制等等因素，人們傾向不使用帶有加密的方法，而采用5）。6.1.3 哈希函數(shù)的構造方法 大多數(shù)重要的哈希函數(shù)設計成迭代過程。 為初值， 是第 階段與 +1階段間的鏈接變量。 是

6、哈希函數(shù)的壓縮函數(shù)， 是 位， 是 位， 是輸出變換. 哈希函數(shù) 的輸入是 。首先對 進行預處理使之長度是 的整倍數(shù)， ， 是 位， 。再令 ，對 做 。最后令函數(shù)值 。以下兩點提供了簡單有效的構造方法。 1)任何強抗碰撞的壓縮函數(shù)都可以擴展成一個強抗碰撞的哈希函數(shù)。 2)若 或 是強抗碰撞哈希函數(shù)，則 強抗碰撞的哈希函數(shù)。 由此可知，設計安全的哈希函數(shù)的難題變成設計一固定長輸入的抗碰撞壓縮函數(shù)。6.2 生日攻擊與強抗碰撞強度6.2.1 生日悖論問題：假定每個人的生日是等概率的，每年有365天（不考慮閏年）。在k個人中至少有兩個人的生日相同的概率大于1/2。問k的最小值。 我們把每個人的生日看

7、成在1，365中的隨機變量。有基本組合數(shù)學知識知個人的生日不重復的概率為 當k=23時， 。從而23個人的生日至少有一個重復的概率為 = 0.5073。這個結果似乎和人們的直覺不太一致，這就是所謂的生日悖論。6.2.2 兩個相交的集合 給定一個取整數(shù)的隨機變量，它服從1，n的均勻分布。兩個有個隨機變量的集合 ， 。取定 ， （稱與匹配）的概率為1 / n， 的概率為1-1/n。Y中所有k個隨機變量都不等于 的概率為 。假設X中k個隨機變量兩兩互不相同，則Y中所有k個隨機變量與X中k個隨機變量都不相等的概率為 。從而Y與X至少有一個匹配的概率為 。我們希望知道多大的k能使這個概率大于1 / 2。

8、為此，利用不等式 有 。令不等式右邊等于1/2，求出 。 6.2.3 強抗碰撞強度 “兩個集合相交”問題可以轉述為：假設哈希函數(shù)h輸出長度為m，全部可能的輸出有 個?，F(xiàn)哈希函數(shù)h接收k個隨機輸入產(chǎn)生X，接受另外k個隨機輸入產(chǎn)生Y。根據(jù)前面的討論知，當取 時才使X與Y至少存在一對匹配的概率大于1/2。 由此看出 將決定輸出長度m為哈希函數(shù)h強抗碰撞的強度。 如果我們采用傳輸加密的消息摘要和不加密的消息，那么對手需要尋找另一個消息使得這兩個消息的摘要相同，以便代替原消息來欺騙接收者。一種基于生日悖論的攻擊有可能做到這一點。G.Yuval在1979年提出如下策略：發(fā)送者準備通過在消息x后面附加 來對

9、消息x進行簽名，其中 是m位；對手對消息x產(chǎn)生 個變形的消息（表達同樣的意思），再擬定表示另一個意思的 個假消息（準備去替換消息x）。計算所有消息的哈希值；根據(jù)生日悖論，“兩個相交集合”問題成功的概率大于1/2。比較兩個哈希值集合，以便發(fā)現(xiàn)具有相同哈希值（匹配）的消息。如果沒發(fā)現(xiàn)，則再產(chǎn)生其他一批有效消息和假消息。直到出現(xiàn)一個匹配為止。用找到匹配的假消息代替消息x后面仍然附加 送給接受方。 6.4有代表性的哈希函數(shù)6.4.1 基于私鑰密碼系統(tǒng)的哈希函數(shù)6.4.2 基于離散對數(shù)問題的哈希函數(shù)6.4.3 MD系列哈希函數(shù)6.4.4 安全散列標準 6.4.1 基于私鑰密碼系統(tǒng)的哈希函數(shù) 其中 長度為

10、n。令 是初始向量，f由私鑰加密算法確定， ， 哈希函數(shù) 。 如果f的設置方案是下列四種，則是安全的6.4.2 基于離散對數(shù)問題的哈希函數(shù) Chaum-van Heijst-Pfitzmann哈希函數(shù)p, q=(p-1)/2均是素數(shù)， ， 是 的本原元素且在計算上是不可行的。 : 0,1,q-10,1,q-1 可以證明h是強抗碰撞哈希函數(shù)。6.4.3 MD系列哈希函數(shù) 1990年R.L.Rivest提出MD4哈希函數(shù)，它不基于某種密碼系統(tǒng)和假設，是一種直接構造法。計算速度高，對長的信息簽名很實用。 1991年對MD4作了六點修改形成強化版本MD5。 對要進行哈希運算的0-1串x轉變成M, 形式

11、如下 其中*是x長度的右邊64位 其長度是512的倍數(shù)， 從左到右每32位成為一個“字”，M = M0M1MN-1，N是16的倍數(shù)。由M構造一個128 bit 的消息摘要的過程如下:(1) 建立四個32位寄存器A, B, C, D，用十六進制表示它們分別是 A = 67452301 B =EFCDAB89 C = 98BADCFE D = 10325476(2) for to do (3) for to 15 do(4) AA=A, BB=B, CC=C, DD=D(5) 執(zhí)行第一輪，執(zhí)行第二輪，執(zhí)行第三輪 (6) A = A+AA, B = B+BB, C = C+CC, D= D+DD 最

12、后 =A | B | C | D 長度為128 位。在每輪中用到如下運算: 按位“與”“補” 按位”或” 模 加 按位”異或” 循環(huán)左移s位 第一輪: for to 3 do 其中的函數(shù) 第二輪: for to 3 do（其中5A827999 ） 5A827999 5A827999 5A827999 52827999 其中的函數(shù) 第三輪 for to 3 do (其中6ED9EBA1 ) 6ED9EBA1 6ED9EBA1 6ED9EBA1 6ED9EBA1 其中的函數(shù) MD5 MD5是MD4的強化版本，在實際中廣泛受到歡迎。MD5對MD4主要作了六點改進，速度比MD4慢了30%。從三輪改成四

13、輪，第四輪的16步使用函數(shù) ，訪問次序為0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 .第三輪函數(shù)從改為 ，以削弱對稱性.進入第二論和第三輪的輸入字順序改變, 分別為1, 6, 11,0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12和5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2.每輪移位數(shù)改變 第一輪為7，12，17，22 第二輪為5，9，14，10 第三輪為4，11，16，23 第四輪為6，10，15，21第j步（不是每輪）有唯一的加法常

14、數(shù) 的整數(shù)部分.每步加上了上一步的結果，易產(chǎn)生“雪崩效應”.6.4.4 安全散列標準 美國國家標準技術研究所與國家安全局共同設計一個與美國數(shù)字簽名算法(DSS)一起使用的安全哈希算法( Secure Hash Algorithm, 簡稱SHA)。1992年1月31日公布，1993年5月11日采納為標準。1994年7月修改，1995年4月17日公布修改版本稱為SHA-1。SHA與MD4設計原則極為相似，下面列出MD4, MD5, SHA三種哈希函數(shù)基本參數(shù) 位長 遍數(shù)*每遍步數(shù) 相對速度 MD4 128 3*16 1.00 MD5 128 4*16 0.68 SHA 160 4*20 0.28

15、SHA_1所用的運算與MD4相同，每輪算法相同，只是所用的函數(shù)和常數(shù)不同 ： 5A827999 6ED9EBA1 8F1BBCDC CA62C1D6 SHA_1的輸入是消息x，求它的消息摘要 。開始階段的處理與MD4相同，生成M。 1）設置五個寄存器A, B, C, D, E A = 67452301 B = EFCDAB89 C = 98BADCFE D =10325476 E = C3D2E1F02）for to do 3） for to 15 do 4）將 擴展成 for to 79 do 5) AA = A, BB = B, CC = C, DD = D, EE = E 6) 執(zhí)行第一

16、輪 for to 19 do 7) 執(zhí)行第二輪 for to 39 do 8) 執(zhí)行第三輪 for to 59 do 9) 執(zhí)行第四輪 for to 79 do 10) A = A+AA, B = B+BB, C = C+CC, D = D+DD, E = E+EE最后 = A | B | C | D | E。 6.5. 蓋時間戳 加蓋時間戳( timestamping )是哈希函數(shù)的一個應用。為什么需要時間戳呢？假設 敵手攻破某人的簽名之后可以堂而皇之地對任何消息簽名。由此產(chǎn)生兩種問題 : 1 某人發(fā)現(xiàn)自己密鑰流失，發(fā)表用此密鑰所作的簽 名作廢（也包括流失前的簽名）. 2 某人對前面簽名反悔，謊稱自己的密鑰流失 . 為了區(qū)分這兩種情況需要確定“何時簽署的消息”。時間戳就是要提供“在特定時間簽名”的證明。加蓋時間戳的方法有： 1）自己產(chǎn)生可信的時間戳 某人自己得到某些公開的可用信息（在發(fā)生之前不能預測），稱為pub， 是哈希函數(shù)。在消息x的簽名上加蓋時間戳時，某人先計算 ， 再對其簽名 ，第二天在報紙上公布 ，其中z沒有揭示x，并且說明此人在pub出現(xiàn)后及報紙公布前作了簽名y。必要時此人揭示x，以證明z是加蓋了時間戳的x簽名。 有可信的加蓋時間戳服務中心（Time Stamping Service簡稱TSS）. TSS作用是電子公證人(Elect