現(xiàn)代密碼學(xué)第5章Hash函數(shù)與消息認(rèn)證1110

1、1 21世紀(jì)高等學(xué)校計算機規(guī)劃教材 cryptography 彭代淵彭代淵 信息科學(xué)與技術(shù)學(xué)院信息科學(xué)與技術(shù)學(xué)院 2009.9-2010.1 作 者：何大可 彭代淵 唐小虎 何明星 梅其祥 出版社：人民郵電出版社 2 cryptography 彭代淵彭代淵 信息科學(xué)與技術(shù)學(xué)院信息科學(xué)與技術(shù)學(xué)院 2009年年11月月 3 第第5章章 hash函數(shù)與消息認(rèn)證函數(shù)與消息認(rèn)證 l 5.2 hash5.2 hash函數(shù)函數(shù)md5md5 l 5.3 5.3 安全安全hashhash算法算法shasha 1 1 l 5.4 5.4 基于分組密碼與離散對數(shù)的基于分組密碼與離散對數(shù)的hashhash函數(shù)函數(shù) l

2、 5.5 5.5 消息認(rèn)證消息認(rèn)證 4 5.1 hash函數(shù)概述函數(shù)概述 5 5.1.1 hash函數(shù)定義函數(shù)定義 l 數(shù)據(jù)安全數(shù)據(jù)安全 u機密性機密性 u完整性完整性 u認(rèn)證性認(rèn)證性 l 密碼技術(shù)主要保證數(shù)據(jù)的機密性密碼技術(shù)主要保證數(shù)據(jù)的機密性 l hash函數(shù)能保證數(shù)據(jù)的完整性和認(rèn)證性函數(shù)能保證數(shù)據(jù)的完整性和認(rèn)證性 6 5.1.1 hash函數(shù)定義函數(shù)定義 l hash函數(shù)定義：函數(shù)定義：hash函數(shù)是一個將任意長度的消息函數(shù)是一個將任意長度的消息 （message）映射成固定長度消息的函數(shù)。）映射成固定長度消息的函數(shù)。 n* n* i i* n xhyx h n a aa a a aa

3、a a aa a a a a a )( : 0 任任意意長長度度消消息息集集合合 消消息息集集合合長長度度為為 字字母母表表 將將h稱為一個稱為一個hash函數(shù)（函數(shù)（hash function），或稱為哈希函），或稱為哈希函 數(shù)、散列函數(shù)。對于任何消息數(shù)、散列函數(shù)。對于任何消息x ，將，將h(x)稱為稱為x的的hash值、值、 散列值、消息摘要（散列值、消息摘要（message digest）。）。 7 5.1.1 hash函數(shù)定義函數(shù)定義 l hash函數(shù)的碰撞（函數(shù)的碰撞（collision） 設(shè)x、x是兩個不同的消息，如果 h(x)=h(x) 則稱x和x是hash函數(shù)h的一個（對）碰撞

4、. 8 5.1.1 hash函數(shù)定義函數(shù)定義 l hash函數(shù)的分類函數(shù)的分類 u單向單向hash函數(shù)（函數(shù)（one way） 給定一個給定一個hash值值y，如果尋找一個消息，如果尋找一個消息x，使得，使得y=h (x) 是計算上不可行的，則稱是計算上不可行的，則稱h是單向是單向hash函數(shù)函數(shù). u弱抗碰撞弱抗碰撞hash函數(shù)（函數(shù)（weakly collision free） 任給一個消息任給一個消息x，如果尋找另一個不同的消息，如果尋找另一個不同的消息x，使，使 得得h(x) =h(x)是計算上不可行的，則稱是計算上不可行的，則稱h是弱抗碰撞是弱抗碰撞 hash函數(shù)函數(shù). u強抗碰撞強

5、抗碰撞hash函數(shù)函數(shù) （strongly collision free） 如果尋找兩個不同的消息如果尋找兩個不同的消息x和和x，使得，使得h(x)=h(x)是計是計 算上不可行的，則稱算上不可行的，則稱h是強抗碰撞是強抗碰撞hash函數(shù)函數(shù). 9 5.1.1 hash函數(shù)定義函數(shù)定義 l 安全安全hash函數(shù)函數(shù)h應(yīng)具有以下性質(zhì)：應(yīng)具有以下性質(zhì)： u 對任意的消息對任意的消息x，計算，計算h(x)是容易的；是容易的； u h是單向的；是單向的； u h是弱抗碰撞的，或是強抗碰撞的。是弱抗碰撞的，或是強抗碰撞的。 10 5.1 hash函數(shù)概述函數(shù)概述 11 5.1.2 hash函數(shù)的安全性

6、l 對對hash函數(shù)的攻擊是指尋找一對碰撞消息的過程函數(shù)的攻擊是指尋找一對碰撞消息的過程 l 生日悖論（生日悖論（birthday paradox） 生日問題：假設(shè)每個人的生日是等概率的，每年有生日問題：假設(shè)每個人的生日是等概率的，每年有365天，天， 在在k個人中至少有兩個人的生日相同的概率大于個人中至少有兩個人的生日相同的概率大于1/2，問，問k最小最小 應(yīng)是多少？應(yīng)是多少？ k人生日都不同的概率是：人生日都不同的概率是： . 365 1 1. 365 2 1 365 1 1 k . 365 1 1. 365 2 1 365 1 11),365( k kp 2k人人生生日日相相同同的的概概

7、率率為為：人人中中至至少少有有 有有p(365,23)=0.5073。即在。即在23個人中，至少有兩個人生日相個人中，至少有兩個人生日相 同的概率大于同的概率大于0.5，這個數(shù)字比人們直觀猜測的結(jié)果小得多，這個數(shù)字比人們直觀猜測的結(jié)果小得多， 因而稱為生日悖論。因而稱為生日悖論。 12 l 生日攻擊法生日攻擊法 生日悖論原理可以用于構(gòu)造對生日悖論原理可以用于構(gòu)造對hash函數(shù)的攻擊函數(shù)的攻擊 u設(shè)設(shè)hash函數(shù)值有函數(shù)值有n個比特，個比特，m是真消息，是真消息，m是偽造的假消息，是偽造的假消息， 分別把消息分別把消息m和和m表示成表示成r和和r個個變形的消息變形的消息。消息與其變形。消息與其變

8、形 消息具有不同的形式，但有相同的含義。將消息表示成變消息具有不同的形式，但有相同的含義。將消息表示成變 形消息的方法很多，例如增加空格、使用縮寫、使用意義形消息的方法很多，例如增加空格、使用縮寫、使用意義 相同的單詞、去掉不必要的單詞等。相同的單詞、去掉不必要的單詞等。 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 13 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 l 生日攻擊法生日攻擊法 u分別把消息分別把消息m和和m表示成表示成r和和r個個變形的消息變形的消息 14 l 生日攻擊法生日攻擊法 u計算真消息計算真消息m的變形與假消息的變形與假消息m的變形發(fā)生碰撞的概率的變形發(fā)生碰撞的概率

9、 由于由于n比特長的散列值共有比特長的散列值共有2n個，所以對于給定個，所以對于給定m的變形的變形mi 和和m的變形的變形mj，mi與與mj不碰撞的概率是不碰撞的概率是1-1/2n。由于。由于m共有共有 r個變形，所以個變形，所以m的全部變形都不與的全部變形都不與mi碰撞的概率是：碰撞的概率是： 1 1/2. r n 因為消息因為消息m共有共有r個變形，因此個變形，因此m的變形與的變形與m的變形都不碰撞的概的變形都不碰撞的概 率是：率是： .2/1 rr n 1 m的變形與的變形與m的變形發(fā)生碰撞的概率是：的變形發(fā)生碰撞的概率是： .1 2 1 11)( 2n rrrr n enp 5.1.2

10、 hash函數(shù)的安全性函數(shù)的安全性 15 l 生日攻擊法生日攻擊法 當(dāng)當(dāng)r=r=2n/2時，時，p(n)=1 e 1 0.63。對于。對于hash值長度為值長度為64比比 特的特的hash函數(shù)，生日攻擊的時間復(fù)雜度約為函數(shù)，生日攻擊的時間復(fù)雜度約為232，所以是，所以是 不安全的。不安全的。 為了抵抗生日攻擊，建議為了抵抗生日攻擊，建議hash值長度至少為值長度至少為128 比特比特. 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 16 l 中間相遇攻擊（中間相遇攻擊（in-the-middle attack） u用于攻擊一類具有特殊結(jié)構(gòu)的用于攻擊一類具有特殊結(jié)構(gòu)的hash函數(shù)函數(shù) u分析分析

11、hash函數(shù)運算的中間值相等的概率函數(shù)運算的中間值相等的概率 u討論一類利用加密變換構(gòu)造的討論一類利用加密變換構(gòu)造的hash函數(shù)函數(shù) 設(shè)加密體制為：設(shè)加密體制為： n k n e mmk kmmk k:, 對于消息對于消息m=(m1, m2)，其散列值的計算分以下兩步：，其散列值的計算分以下兩步： （1） h1= ek(m1, iv)； （2） d=h(m)=ek (m2, h1)， 其中其中iv是加密變換的初始值。是加密變換的初始值。 這類這類hash函數(shù)將遭受中間相遇攻擊。函數(shù)將遭受中間相遇攻擊。 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 17 l 中間相遇攻擊（中間相遇攻擊（in-t

12、he-middle attack） u用于攻擊一類具有特殊結(jié)構(gòu)的用于攻擊一類具有特殊結(jié)構(gòu)的hash函數(shù)函數(shù) u分析分析hash函數(shù)運算的中間值相等的概率函數(shù)運算的中間值相等的概率 u討論一類利用加密變換構(gòu)造的討論一類利用加密變換構(gòu)造的hash函數(shù)函數(shù) u攻擊方式攻擊方式: 假設(shè)攻擊者要找出一個假消息假設(shè)攻擊者要找出一個假消息m=(m1, m2)， 使得使得m與與m是一個碰撞。設(shè)是一個碰撞。設(shè)m的散列值都為的散列值都為d。攻擊者首。攻擊者首 先產(chǎn)生消息先產(chǎn)生消息m1的的r個變形，消息個變形，消息m2的的r個變形個變形. 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 18 中間值集合 假消息的 第

13、1部分 m1 變形 m1,1 ek m1,2 ek m1,r ek iv m2,2 dk m2,r dk 假消息的 第2部分 m2 m2,1 dk d 目標(biāo)摘要 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 h1= ek(m1, iv) d=h(m)=ek(m 2, h1) 19 5.1.2 hash函數(shù)的安全性函數(shù)的安全性 .,.,2 , 1| ),( ,.,2 , 1| ),(: .,.,2 , 1|,.,2 , 1|: , 2, 22 , 1, 11 , 2, 1 rjdmdhh riivmehh rjm rim jkj iki ji 計計算算 令令 這里這里dk是解密變換。假設(shè)加密變換

14、是解密變換。假設(shè)加密變換ek是隨機的，那么是隨機的，那么 可以使用生日攻擊法來分析集合可以使用生日攻擊法來分析集合h1和和h2中出現(xiàn)相同元中出現(xiàn)相同元 素的概率。素的概率。 如果集合如果集合h1與與h2有相同元素，例如有相同元素，例如h1, i= h2, j=dk(m2, j, d)， 則有則有d=ek (m2, j, h1,i )，即，即m與與m有相同的散列值有相同的散列值d。 h1= ek(m1, iv) d=h(m)=ek(m2, h1) 20 5.1 hash函數(shù)概述函數(shù)概述 21 5.1.3 hash5.1.3 hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法 l 壓縮函數(shù)（壓縮函數(shù)（com

15、pression function） l 迭代技術(shù)迭代技術(shù) 設(shè)設(shè)x是一個長度為是一個長度為l 的比特串。重復(fù)應(yīng)的比特串。重復(fù)應(yīng) 用壓縮函數(shù)用壓縮函數(shù)f，對消，對消 息息x進行多次壓縮，進行多次壓縮， 最后得到最后得到x的散列值的散列值 ) 1(1 , 01 , 0: tf mtm 22 5.1.3 hash5.1.3 hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法 l 計算消息計算消息x的散列值的散列值h(x)的步驟的步驟 u 預(yù)處理預(yù)處理: 用一個公開算法在消息用一個公開算法在消息x右方添加若干比特，右方添加若干比特， 得到比特串得到比特串y，使，使 得得y的長度為的長度為t的倍數(shù)。即有的倍數(shù)。即

16、有 y= x | pad(x) = y1 | y 2 | | yr , 其中其中| yi|=t (i =1, 2, r)，pad(x)稱為稱為填充函數(shù)填充函數(shù)。典型的。典型的 填充函數(shù)是先添加填充函數(shù)是先添加x長度長度| x|的值，再添加若干比特（例的值，再添加若干比特（例 如如0）。）。 u迭代過程迭代過程: 設(shè)設(shè)h0=iv是一個長度為是一個長度為m的初始比特串，的初始比特串， 重復(fù)使用壓縮函數(shù)重復(fù)使用壓縮函數(shù)f，依次計算，依次計算 hi= f (hi 1| yi) (i =1, 2, r). u輸出變換輸出變換: 設(shè)設(shè)g: 0,1m0,1t是一個公開函數(shù)，令是一個公開函數(shù)，令 h(x)=g

17、(hr). 23 5.1.3 hash5.1.3 hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法 l 用上述方法構(gòu)造的用上述方法構(gòu)造的hash函數(shù)稱為迭代函數(shù)稱為迭代hash函數(shù)。大多數(shù)函數(shù)。大多數(shù) 實用實用hash函數(shù)都是迭代函數(shù)都是迭代hash函數(shù)函數(shù) l 在預(yù)處理階段，必須保證變換在預(yù)處理階段，必須保證變換xy是單射。因為如果預(yù)是單射。因為如果預(yù) 處理變換處理變換xy不是單射，則存在不是單射，則存在x x使得使得y=y，從而，從而 h(x)=h(x)，即能夠找到，即能夠找到h的碰撞。的碰撞。 l 對于任意無碰撞的壓縮函數(shù)，都可以使用迭代技術(shù)構(gòu)造對于任意無碰撞的壓縮函數(shù)，都可以使用迭代技術(shù)構(gòu)造

18、一個無碰撞的一個無碰撞的hash函數(shù)。函數(shù)。 24 第第5章章 hash函數(shù)與消息認(rèn)證函數(shù)與消息認(rèn)證 l 5.3 5.3 安全安全hashhash算法算法shasha 1 1 l 5.4 5.4 基于分組密碼與離散對數(shù)的基于分組密碼與離散對數(shù)的hashhash函數(shù)函數(shù) l 5.5 5.5 消息認(rèn)證消息認(rèn)證 25 5.2 hash5.2 hash函數(shù)函數(shù)md5md5 l md5(md:message digest,消息摘要消息摘要) 1990年年10月月, 著名密碼學(xué)家著名密碼學(xué)家r. l. rivest在在 mit(massachusetts institute of technology)提

19、出了一種提出了一種 hash函數(shù)函數(shù),作為作為rfc 1320 (rfc:互聯(lián)網(wǎng)研究和開發(fā)機構(gòu)互聯(lián)網(wǎng)研究和開發(fā)機構(gòu) 工作記錄工作記錄)公開發(fā)表公開發(fā)表,稱為稱為md4. md5是是md4的改進版本的改進版本, 于于1992年年4月作為月作為rfc 1321公開發(fā)表公開發(fā)表. l md5特性特性 u直接構(gòu)造法: 不依賴任何密碼系統(tǒng)和假設(shè)條件 u算法簡潔 u計算速度快 u特別適合32位計算機軟件實現(xiàn) u傾向于使用低端結(jié)構(gòu). 26 5.2.1 5.2.1 md5算法算法 l md5算法的輸入可以是任意長度的消息算法的輸入可以是任意長度的消息x，對輸入消息，對輸入消息 按按512位的分組為單位進行處理

20、，輸出位的分組為單位進行處理，輸出128位的散列值位的散列值 md(x)。整個算法分為五個步驟。整個算法分為五個步驟。 l 步驟步驟1: 增加填充位增加填充位 u在消息x右邊增加若干比特，使其長度與448模512同 余。也就是說，填充后的消息長度比512的某個倍數(shù) 少64位。 u即使消息本身已經(jīng)滿足上述長度要求，仍然需要進 行填充。 u例如，若消息長為448，則仍需要填充512位使其長 度為960位。填充位數(shù)在1到512之間。填充比特的第 一位是1，其它均為0。 27 5.2.1 5.2.1 md5算法算法 l 步驟步驟2: 附加消息長度值附加消息長度值 用64位表示原始消息x的長度，并將其附

21、加在步驟1所得 結(jié)果之。若填充前消息長度大于264，則只使用其低64位。 填充方法是把64比特的長度分成兩個32比特的字，低32 比特字先填充，高32比特字后填充。 l 步驟步驟1與步驟與步驟2一起稱為消息的預(yù)處理一起稱為消息的預(yù)處理 u 經(jīng)預(yù)處理后，原消息長度變?yōu)?12的倍數(shù) u設(shè)原消息x經(jīng)預(yù)處理后變?yōu)橄?y=y0 y1 yl1， 其中yi（i =0,1,l1）是512比特 u在后面的步驟中，將對512比特的分組yi進行處理 28 5.2.1 5.2.1 md5算法算法 u例例5.1 假設(shè)消息為假設(shè)消息為: x=“abcde”=01100001 01100010 01100011 0110

22、0100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. p步驟1在x的右邊填充1個“1”和407個“0”，將x變成448 比特的x1: x1= x | 1 | 0 (407個) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00000000 00000000 00000000 00000000 00000000 0000

23、0000 00000000 00000000 00000000 00000000 00000000 00000000. 29 5.2.1 5.2.1 md5算法算法 u例例5.1 假設(shè)消息為假設(shè)消息為: x=“abcde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. p經(jīng)步驟2處理后的比特串為（16進制表示）： x2=x1|28(64位) =61626364 65800000 00000000 00000000 00000000 00000000 00000000 0000000

24、0 00000000 00000000 00000000 00000000 00000000 00000000 28000000 00000000. 30 5.2.1 5.2.1 md5算法算法 l 步驟步驟3: 初始化初始化md緩沖區(qū)緩沖區(qū) umd5算法的中間結(jié)果和最終結(jié)果都保存在128位的緩 沖區(qū)里，緩沖區(qū)用4個32位的寄存器表示。 u4個緩沖區(qū)記為a、b、c、d，其初始值為下列32位整 數(shù)（16進制表示）： a=67 45 23 01, b=ef cd ab 89, c=98 ba dc fe, d=10 32 54 76. u上述初始值以小端格式存儲(字的最低有效字節(jié)存儲在 低地址位置

25、 )為： 字a=01 23 45 67, 字b=89 ab cd ef, 字c=fe dc ba 98, 字d=76 54 32 10. 31 5.2.1 5.2.1 md5算法算法 l 步驟步驟4: 以以512位的分組位的分組(16個字個字)為單位處理消息為單位處理消息 umd5是迭代hash函數(shù), 其壓縮函數(shù)為: . 128512128 5md 1 , 01 , 0: h u步驟4是md5算法的主循環(huán)，它以512比特作為分 組，重復(fù)應(yīng)用壓縮函數(shù)hmd5，從消息y的第一個分 組y1開始，依次對每個分組yi進行壓縮，直至最后 分組yl1，然后輸出消息x的hash值?？梢?，md5 的循環(huán)次數(shù)等于

26、消息y中512比特分組的數(shù)目l。 32 md5壓縮函數(shù)hmd5 uhmd5由四輪處理組成由四輪處理組成 u加法是指緩沖區(qū)中的加法是指緩沖區(qū)中的 4個字與個字與cvi中對應(yīng)的中對應(yīng)的 4個字分別模個字分別模232相加相加 . 128512128 5md 1 , 01 , 0: h 33 md5壓縮函數(shù)壓縮函數(shù)hmd5 uhmd5的四輪處理過程的算法結(jié)構(gòu)相同，每一輪要對緩的四輪處理過程的算法結(jié)構(gòu)相同，每一輪要對緩 沖區(qū)沖區(qū)abcd進行進行16次迭代，每次迭代的運算形式為次迭代，每次迭代的運算形式為: ( , , ) ) s abl ag b c dx kt i 其中其中a、b、c、d分別為緩沖分別

27、為緩沖 區(qū)區(qū)a、b、c、d中的字，運中的字，運 算結(jié)束后再將（算結(jié)束后再將（a、b、c、d） 循環(huán)右移一個字。循環(huán)右移一個字。 34 md5壓縮函數(shù)壓縮函數(shù)hmd5 uhmd5的基本邏輯函數(shù)的基本邏輯函數(shù)g p每一輪使用一個基本邏輯函數(shù)每一輪使用一個基本邏輯函數(shù)g，每個基本邏輯函數(shù)的，每個基本邏輯函數(shù)的 輸入是三個輸入是三個32位的字，輸出是一個位的字，輸出是一個32位的字，它執(zhí)行位位的字，它執(zhí)行位 邏輯運算，即輸出的第邏輯運算，即輸出的第n位是其三個輸入的第位是其三個輸入的第n位的函數(shù)位的函數(shù) p基本邏輯函數(shù)基本邏輯函數(shù)g的定義的定義 符號符號 、 、 和和 分別表示邏輯操作分別表示邏輯操作

28、and、or、not和和 xor 35 md5壓縮函數(shù)壓縮函數(shù)hmd5 uhmd5的基本邏輯函數(shù)的基本邏輯函數(shù)g p基本邏輯函數(shù)基本邏輯函數(shù)g的真值表的真值表 b c df g h i 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 36 md5壓縮函數(shù)壓縮函數(shù)hmd5 u字組字組x 把當(dāng)前處理的把當(dāng)前處理的512比特的分組比特的分組yi依次分成依次分成16個個32 比特的字比特的字, 分別記為分別記為x0,1,15.

29、u在每一輪的在每一輪的16步迭代中步迭代中, 每一步迭代使用一個字每一步迭代使用一個字, 迭代步數(shù)不同使用的字也不相同迭代步數(shù)不同使用的字也不相同. 因此因此, 16步迭代步迭代 恰好用完恰好用完16個字個字. 37 md5壓縮函數(shù)壓縮函數(shù)hmd5 u對于不同輪處理過程對于不同輪處理過程, 使用使用16個字的順序不一樣個字的順序不一樣. p第一輪中，使用順序為x0,1,15。 p第二輪中使用順序由下列置換確定: 2(i)= (1+5i) mod 16 p第三輪中使用順序由下列置換確定: 3(i)= (5+3i) mod 16 p第四輪中使用順序由下列置換確定: 4(i)= 7i mod 16.

30、 u例如例如: 第三輪處理過程的第第三輪處理過程的第i步迭代使用字步迭代使用字 x 3(i)= x(5+3i) mod 16; 第第8步迭代使用字步迭代使用字 x 3(8)=x(5+3 8)=x29=x23. 38 md5壓縮函數(shù)壓縮函數(shù)hmd5 t1=d76aa478 t2=e8c7b756 t3=242070db t4=c1bdceee t5=f57c0faf t6=4787c62a t7=a8304613 t8=fd469501 t9=698098d8 t10=8b44f7af t11=ffff5bb1 t12=895cd7be t13=6b901122 t14=fd987193 t15

31、=a679438e t16=49b40821 t17=f61e2562 t18=c040b340 t19=265e5a51 t20=e9b6c7aa t21=d62f105d t22=02441453 t23=d8a1e681 t24=e7d3fbc8 t25=21e1cde6 t26=c33707d6 t27=f4d50d87 t28=455a14ed t29=a9e3e905 t30=fcefa3f8 t31=676f02d9 t32=8d2a4c8a t33=fffa3942 t34=8771f681 t35=699d6122 t36=fde5380c t37=a4beea44 t38=

32、4bdecfa9 t39=f6bb4b60 t40=bebfbc70 t41=289b7ec6 t42=eaa127fa t43=d4ef3085 t44=04881d05 t45=d9d4d039 t46=e6db99e5 t47=1fa27cf8 t48=c4ac5665 t49=f4292244 t50=432aff97 t51=ab9423a7 t52=fc93a039 t53=655b59c3 t54=8f0ccc92 t55=ffeff47d t56=85845dd1 t57=6fa87e4f t58=fe2ce6e0 t59=a3014314 t60=4e0811a1 t61=f

33、7537e82 t62=bd3af235 t63=2ad7d2bb t64=eb86d391 u常數(shù)表常數(shù)表t：64個個32位常數(shù)位常數(shù) p ti =232 abs(sin(i)的整數(shù)部分的整數(shù)部分(i=1,2,64). 39 md5壓縮函數(shù)壓縮函數(shù)hmd5 u常數(shù)表常數(shù)表t：64個個32位常數(shù)位常數(shù) p ti =232abs(sin(i)的整數(shù)部分(i=1,2,64). p常數(shù)表t的作用是“隨機化”32位的輸入數(shù)據(jù)， 即消除輸入數(shù)據(jù)的規(guī)律性。 phmd5的第k輪處理過程使用常數(shù)表t的元素 t16(k1)+1, 16(k1)+2,16k (k=1,2,3,4)， 第k輪的第i次迭代使用元素 t

34、16( k1)+ i(i=1,2,16). 40 md5壓縮函數(shù)hmd5 u循環(huán)左移位數(shù)循環(huán)左移位數(shù)s ls(v)表示對表示對32位的變量位的變量v循環(huán)左移循環(huán)左移s位。位。s的值與輪的值與輪 數(shù)和迭代步數(shù)有關(guān)。數(shù)和迭代步數(shù)有關(guān)。 步數(shù) 輪數(shù) 123456789101112 13 14 15 16 1 2 3 4 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9

35、11 10 17 14 16 15 22 20 23 21 41 5.2.1 md55.2.1 md5算法算法 l 步驟步驟5: 輸出輸出 依次對消息的l個512比特的分組進行處理，第l個分組 處理后的輸出值即是消息x的散列值md(x)。 可將md5的處理過程歸納如下： ucv0=iv ucvi+1=sum32cvi, rfi (yi, rfh (yi, rfg (yi, rff (yi, cvi) ) (i=0,1, l1) umd= cvl1. uiv =第三步定義的緩沖區(qū)abcd的初值 ul =消息經(jīng)第一步和第二步處理后分組的個數(shù) uyi =消息的第i個512位分組 urfu =使用基本

36、邏輯函數(shù)u的輪函數(shù) usum32=對輸入字的模232相加 umd =散列值. 42 5.2.2 md55.2.2 md5的安全性的安全性 l rivest猜測，猜測，md5可能是可能是128位位hash函數(shù)中強度最大的。函數(shù)中強度最大的。 l 目前，對md5的攻擊已取得以下結(jié)果： ut. berson（1992）已經(jīng)證明，對單輪的md5算法，利用差分 密碼分析，可以在合理的時間內(nèi)找出散列值相同的兩條消息。 這一結(jié)果對md5四輪運算的每一輪都成立。但是，目前尚不 能將這種攻擊推廣到具有四輪運算的md5上. ub. boer和a. bosselaers（1993）說明了如何找到消息分組和 md5兩

37、個不同的初始值,使它們產(chǎn)生相同的輸出. 也就是說, 對一個512位的分組, md5壓縮函數(shù)對緩沖區(qū)abcd的不同值 產(chǎn)生相同的輸出,這種情況稱為偽碰撞（pseudo-collision）.目 前尚不能用該方法成功攻擊md5算法. 43 5.2.2 md55.2.2 md5的安全性的安全性 uh. dobbertin（1996）找到了md5無初始值的碰撞 (pseudo-collision).給定一個512位的分組,可以找到另 一個512位的分組,對于選擇的初始值iv0,它們的md5 運算結(jié)果相同. 到目前為止, 尚不能用這種方法對使用 md5初始值iv的整個消息進行攻擊. u我國山東大學(xué)王小云

38、教授（我國山東大學(xué)王小云教授（2004）提出的攻擊對）提出的攻擊對 md5最具威脅。對于最具威脅。對于md5的初始值的初始值iv，王小云找到，王小云找到 了許多了許多512位的分組對，它們的位的分組對，它們的md5值相同值相同. u國際密碼學(xué)家國際密碼學(xué)家lenstra利用王小云等提供的利用王小云等提供的md5碰撞，碰撞， 偽造了符合偽造了符合x.509標(biāo)準(zhǔn)的數(shù)字證書標(biāo)準(zhǔn)的數(shù)字證書. l md5算法抗密碼分析能力較弱算法抗密碼分析能力較弱,對對md5的生日攻擊所需的生日攻擊所需 代價為代價為264數(shù)量級數(shù)量級. 所以所以, 必須設(shè)計新的必須設(shè)計新的hash算法算法, 使其與使其與 md5相比具

39、有更長的散列值和更高的安全性相比具有更長的散列值和更高的安全性. 44 第第5章章 hash函數(shù)與消息認(rèn)證函數(shù)與消息認(rèn)證 l 5.4 5.4 基于分組密碼與離散對數(shù)的基于分組密碼與離散對數(shù)的hashhash函數(shù)函數(shù) l 5.5 5.5 消息認(rèn)證消息認(rèn)證 45 5.3 5.3 安全安全hashhash算法算法shasha 1 1 l 安全安全hash算法算法sha（secure hash algorithm）由美國標(biāo)）由美國標(biāo) 準(zhǔn)與技術(shù)研究所（準(zhǔn)與技術(shù)研究所（nist）設(shè)計并于）設(shè)計并于1993年作為聯(lián)邦信息年作為聯(lián)邦信息 處理標(biāo)準(zhǔn)（處理標(biāo)準(zhǔn)（fips 180）發(fā)布）發(fā)布 l 修改版于修改版于1

40、995年發(fā)布（年發(fā)布（fips 180 1），通常稱之為），通常稱之為 sha 1。該標(biāo)準(zhǔn)稱為。該標(biāo)準(zhǔn)稱為安全安全hash函數(shù)函數(shù)。 l rfc 3174也給出了也給出了sha 1，它基本上是復(fù)制，它基本上是復(fù)制fips 180 1 的內(nèi)容，但增加了的內(nèi)容，但增加了c代碼實現(xiàn)。代碼實現(xiàn)。 l sha 1算法的輸入是長度小于算法的輸入是長度小于264的任意消息的任意消息x，輸出，輸出160 位的散列值。位的散列值。 46 5.3.1 sha5.3.1 sha 1 1算法步驟算法步驟 l sha 1處理消息的過程與處理消息的過程與md5類似，對輸入消息按類似，對輸入消息按512位位 的分組為單位進

41、行處理，整個算法分為五個步驟的分組為單位進行處理，整個算法分為五個步驟 l 步驟步驟1: 增加填充位增加填充位 在消息右邊增加若干比特，使其長度與在消息右邊增加若干比特，使其長度與448模模512同余。即使消息本身同余。即使消息本身 已經(jīng)滿足上述長度要求，仍然需要進行填充。填充位數(shù)在已經(jīng)滿足上述長度要求，仍然需要進行填充。填充位數(shù)在1到到512之之 間。填充比特的第一位是間。填充比特的第一位是“1”，其它均為，其它均為“0”。 l 步驟步驟2: 附加消息長度值附加消息長度值 用用64位表示原始消息位表示原始消息x的長度，并將其附加在步驟的長度，并將其附加在步驟1所得結(jié)果之后。所得結(jié)果之后。 l

42、 步驟步驟1與步驟與步驟2一起稱為消息的預(yù)處理一起稱為消息的預(yù)處理 經(jīng)預(yù)處理后，原消息長度變?yōu)榻?jīng)預(yù)處理后，原消息長度變?yōu)?12的倍數(shù)。設(shè)原消息的倍數(shù)。設(shè)原消息x經(jīng)預(yù)處理后變經(jīng)預(yù)處理后變 為消息為消息y=y0 y1 yl 1，其中，其中yi（i =0,1,l 1）是）是512比特。在后面的比特。在后面的 步驟中，將對步驟中，將對512比特的分組比特的分組yi進行處理。進行處理。 47 5.3.1 sha5.3.1 sha 1 1算法步驟算法步驟 l 步驟步驟3: 初始化緩沖區(qū)初始化緩沖區(qū) sha 1算法的中間結(jié)果和最終結(jié)果保存在算法的中間結(jié)果和最終結(jié)果保存在160位的緩沖區(qū)里，緩沖區(qū)位的緩沖區(qū)里

43、，緩沖區(qū) 用用5個個32位的寄存器表示。位的寄存器表示。5個緩沖區(qū)記為個緩沖區(qū)記為a、b、c、d、e，其初始，其初始 值為下列值為下列32位整數(shù)（位整數(shù)（16進制表示）：進制表示）： a=67 45 23 01, b=ef cd ab 89, c=98 ba dc fe , d=10 32 54 76, e=c3 d2 e1 f0. 其中，前其中，前4個初始值與個初始值與md5的初始值相同。的初始值相同。sha 1以大端格式存儲緩以大端格式存儲緩 沖區(qū)的值，即字的最高有效字節(jié)存于低地址字節(jié)位置。因此，上述沖區(qū)的值，即字的最高有效字節(jié)存于低地址字節(jié)位置。因此，上述 初始值存儲為（十六進制）：初始

44、值存儲為（十六進制）： 字字a=67 45 23 01, 字字b=ef cd ab 89, 字字c=98 ba dc fe, 字字d=10 32 54 76, 字字e=c3 d2 e1 f0. 48 5.3.1 sha5.3.1 sha 1 1算法步驟算法步驟 l 步驟步驟4: 以以512位的分組（位的分組（16個字）為單位處理消息個字）為單位處理消息 usha 1是迭代是迭代hash函數(shù)，其壓縮函數(shù)為：函數(shù)，其壓縮函數(shù)為： . 160512160 sha 1 , 01 , 0: h u步驟步驟4是是sha 1算法的主循環(huán)，它以算法的主循環(huán)，它以512比特作為分組，比特作為分組， 重復(fù)應(yīng)用壓縮

45、函數(shù)重復(fù)應(yīng)用壓縮函數(shù)hsha，從消息，從消息y的第一個分組的第一個分組y1開開 始，依次對每個分組始，依次對每個分組yi進行壓縮，直至最后分組進行壓縮，直至最后分組yl 1， 然后輸出消息然后輸出消息x的的hash值。值。 usha 1循環(huán)次數(shù)等于消息循環(huán)次數(shù)等于消息y中中512比特分組的數(shù)目比特分組的數(shù)目l。 49 shasha 1 1的的 壓縮函數(shù)壓縮函數(shù)h hsha sha u由四輪處理組成由四輪處理組成 u加法是模加法是模232相加相加 cvi (160) yi (512) bcdae f4, k, w60,61,79, 20步 bcdae f2, k, w20,21,39, 20步

46、bcdae f3, k, w40,41,59, 20步 bcdae f1, k, w0,1,19, 20步 + + + + + cvi+1 (160) 50 shasha 1 1的壓縮函數(shù)的壓縮函數(shù)h hsha sha u壓縮函數(shù)壓縮函數(shù)hsha的四輪處理過程的算法結(jié)構(gòu)相同，每一輪的四輪處理過程的算法結(jié)構(gòu)相同，每一輪 要對緩沖區(qū)要對緩沖區(qū)abcde進行進行20次迭代，每次迭代的運算形次迭代，每次迭代的運算形 式為式為 dc,(b),a,),(a)d)c,(b,(eed,c,b,a, 305 lkwlf tt a b c d e a b c d e + + f +wt +kt l30 l5 其中

47、其中a、b、c、d、 e分別為五個緩沖分別為五個緩沖 區(qū)中的字，運算結(jié)區(qū)中的字，運算結(jié) 束后再將（束后再將（a、b、 c、d、e）循環(huán)右）循環(huán)右 移一個字。移一個字。 51 dcb d)(cd)(bc)(b dcb d)b(c)(b shasha 1 1的壓縮函數(shù)的壓縮函數(shù)h hsha sha u基本邏輯函數(shù)基本邏輯函數(shù)f p每一輪使用一個基本邏輯函數(shù)每一輪使用一個基本邏輯函數(shù)f，每個基本邏輯函，每個基本邏輯函 數(shù)的輸入是三個數(shù)的輸入是三個32位的字，輸出是一個位的字，輸出是一個32位的字，位的字， 它執(zhí)行位邏輯運算，即輸出的第它執(zhí)行位邏輯運算，即輸出的第n位是其三個輸入位是其三個輸入 第第n

48、位的函數(shù)。位的函數(shù)。 輪數(shù)基本邏輯函數(shù)ff(b, c, d) 1 2 3 4 f1(b, c, d) f2(b, c, d) f3(b, c, d) f4(b, c, d) 52 shasha 1 1的壓縮函數(shù)的壓縮函數(shù)h hsha sha u基本邏輯函數(shù)基本邏輯函數(shù)f p基本邏輯函數(shù)基本邏輯函數(shù)f的真值表的真值表 b c df1 f2 f3 f4 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 53 shasha 1

49、1的壓縮函數(shù)的壓縮函數(shù)h hsha sha u字組字組wt p t（0t79）代表迭代步數(shù)，依次表示第一、二、三、四輪處 理過程進行的迭代次序 pwt(0t79)是32比特的字，它的前面16個字w0,w1,w15依次 取自當(dāng)前輸入分組yi，其余字為 ).79,.,17,16()( 381416 1 twwwwlw ttttt u加法常數(shù)表加法常數(shù)表kt 30 30 30 30 22 23 25 210 迭代步數(shù)迭代步數(shù)十六進制十六進制十進制十進制 0t19 20t39 40t59 60t79 5a827999 6ed9eba1 8f1bbcdc ca62c1d6 54 5.3.1 sha5.3

50、.1 sha 1 1算法步驟算法步驟 l 步驟步驟5: 輸出輸出 u第l個分組處理后的輸出值即是消息x的散列值md(x) usha1的處理過程歸納如下： pcv0=iv p cvi+1=sum32(cvi, abcdei ) (i=0,1, l1) pmd= cvl1 u其中： piv =第三步定義的緩沖區(qū)abcde的初值 pabcdei =處理第i個消息分組時最后一輪的輸出 pl =消息經(jīng)第一步和第二步處理后分組的個數(shù) psum32=對輸入字的模232相加 pmd =散列值. 55 5.3.2 sha5.3.2 sha 1 1和和md5md5的比較的比較 l sha 1與與md5的算法類似，

51、所以它們的性質(zhì)極為相似的算法類似，所以它們的性質(zhì)極為相似 l 抗窮舉攻擊的能力抗窮舉攻擊的能力 usha1抗窮舉攻擊的能力比md5強 u用窮舉攻擊方法產(chǎn)生具有給定散列值的消息 pmd5需要的代價為2128數(shù)量級 psha1需要的代價為2160數(shù)量級 u用窮舉攻擊方法產(chǎn)生兩個具有相同散列值的消息 pmd5需要的代價為264數(shù)量級 psha1需要的代價為280數(shù)量級 l 抗密碼分析的能力抗密碼分析的能力 umd5算法抗密碼分析的能力較弱算法抗密碼分析的能力較弱 usha 1算法抗密碼分析的能力似乎并不弱算法抗密碼分析的能力似乎并不弱 56 5.3.2 sha5.3.2 sha 1 1和和md5md

52、5的比較的比較 l 速度速度 sha 1執(zhí)行的速度比執(zhí)行的速度比md5的速度慢得多的速度慢得多 l 簡潔性簡潔性 sha 1和和md5兩種算法都易于描述和實現(xiàn)，不需要使用兩種算法都易于描述和實現(xiàn)，不需要使用 大的程序和置換表大的程序和置換表 l 數(shù)據(jù)的存儲方式數(shù)據(jù)的存儲方式 md5使用使用little endian方式，方式，sha 1使用使用big endian方式。方式。 這兩種方式?jīng)]有本質(zhì)的差異這兩種方式?jīng)]有本質(zhì)的差異 57 第第5章章 hash函數(shù)與消息認(rèn)證函數(shù)與消息認(rèn)證 l 5.5 5.5 消息認(rèn)證消息認(rèn)證 58 5.4 5.4 基于分組密碼與離散對數(shù)的基于分組密碼與離散對數(shù)的has

53、hhash函數(shù)函數(shù) l hash函數(shù)的間接構(gòu)造法函數(shù)的間接構(gòu)造法 u利用已有的密碼算法構(gòu)造利用已有的密碼算法構(gòu)造hash函數(shù)函數(shù) u如果密碼算法是安全的，那么利用它所構(gòu)造的如果密碼算法是安全的，那么利用它所構(gòu)造的hash 函數(shù)也是安全的函數(shù)也是安全的 59 5.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造hashhash函數(shù)函數(shù) l 已知條件已知條件 設(shè)設(shè)ek是一個分組長度為是一個分組長度為n的分組密碼的加密算法，的分組密碼的加密算法， 密鑰為密鑰為k，對于任意的消息，對于任意的消息x，首先對，首先對x進行分組，進行分組， 每組的長度為每組的長度為n。設(shè)消息。設(shè)消息x為為: x

54、=x1 x2xl, 其中其中xi gf(2)n（1 i l）. 60 5.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造hashhash函數(shù)函數(shù) l 基于分組密碼基于分組密碼cbc工作模式構(gòu)造工作模式構(gòu)造hash函數(shù)函數(shù) u首先選取一個初始值首先選取一個初始值: y0 =iv gf(2)n， u然后依次計算然后依次計算: u最后定義最后定義hash值為值為: hcbc(x)=yl. 1 () (1), ikii yexyil iv=y0 x1 ek y1 x2 ek y2 xl ek yl=hcbc(x) 61 l 基于分組密碼基于分組密碼cfb工作模式構(gòu)造工作模式構(gòu)造hash函

55、數(shù)函數(shù) u首先選取一個初始值首先選取一個初始值: y0 =iv gf(2)n， u然后依次計算然后依次計算: u最后定義最后定義hash值為值為: hcfb(x)=yl. 5.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造hashhash函數(shù)函數(shù) 1 () (1), iiki yxeyil iv=y0 x1 y1 ek x2 y2 ek yl=hcfb(x) xl ek l 在密鑰公開的情況下，基于分組密碼在密鑰公開的情況下，基于分組密碼cbc工作模工作模 式和式和cfb工作模式構(gòu)造的工作模式構(gòu)造的hash函數(shù)是不安全的，函數(shù)是不安全的， 它們甚至不是弱無碰撞的它們甚至不是弱無碰

56、撞的. 62 l 基于一些困難數(shù)學(xué)問題，諸如離散對數(shù)問題、因子分基于一些困難數(shù)學(xué)問題，諸如離散對數(shù)問題、因子分 解問題、背包問題等可以構(gòu)造出一些解問題、背包問題等可以構(gòu)造出一些hash函數(shù)，這些函數(shù)，這些 hash函數(shù)的安全性依賴于對應(yīng)數(shù)學(xué)問題的困難性函數(shù)的安全性依賴于對應(yīng)數(shù)學(xué)問題的困難性 l chaum、heijst和和pfitzmann（1992年）提出的基于離年）提出的基于離 散對數(shù)問題構(gòu)造的散對數(shù)問題構(gòu)造的hash函數(shù)函數(shù) u運行速度不是很快運行速度不是很快 u可以證明是安全的可以證明是安全的. l chaum heijst pfitzmann hash函數(shù)的構(gòu)造函數(shù)的構(gòu)造 設(shè)設(shè)p是一

57、個大素數(shù)，是一個大素數(shù)，q=(p 1)/2是一個素數(shù)，是一個素數(shù)， 和和 是是zp的兩的兩 個本原元。假設(shè)離散對數(shù)個本原元。假設(shè)離散對數(shù)log 是計算上不可行的。定義是計算上不可行的。定義 hash函數(shù)函數(shù)h為：為： 5.4.2 5.4.2 基于離散對數(shù)問題的基于離散對數(shù)問題的hash函數(shù)函數(shù) .mod),( ,: 21 21 * pxxh zzzh xx ppp 63 l chaum heijst pfitzmann hash函數(shù)是強抗碰撞的函數(shù)是強抗碰撞的 用反證法，如果用反證法，如果hash函數(shù)函數(shù)h有一對碰撞，那么可以有一對碰撞，那么可以 證明離散對數(shù)證明離散對數(shù)log 能被有效計算能

58、被有效計算. 設(shè)設(shè)(x1, x2)，(x3, x4)是是h的一對碰撞消息，即的一對碰撞消息，即(x1, x2) (x3, x4)，h(x1, x2)=h(x3, x4)，那么，那么 5.4.2 5.4.2 基于離散對數(shù)問題的基于離散對數(shù)問題的hash函數(shù)函數(shù) .modmod 24314321 p p xxxxxxxx 記記d=gcd(x4 x2, p 1)。因為。因為p 1=2q，且，且q是一個素是一個素 數(shù)，所以數(shù)，所以d 1,2, q, p 1。下面對。下面對d的四個取值分別的四個取值分別 進行討論。進行討論。 64 l chaum heijst pitzmann hash函數(shù)是強抗碰撞的

59、函數(shù)是強抗碰撞的 5.4.2 5.4.2 基于離散對數(shù)問題的基于離散對數(shù)問題的hash函數(shù)函數(shù) u情況情況1：d =1 此時此時x4 x2關(guān)于模關(guān)于模p 1有逆，設(shè)有逆，設(shè)y=(x4 x2) 1 mod (p 1)， 則存在整數(shù)則存在整數(shù)k，使得，使得(x4 x2) y=1+ (p 1) k，則有，則有 .mod )()1()()1()( 313124 p yxxkpyxxkpyxx 因此，可計算離散對數(shù)因此，可計算離散對數(shù) ).1(mod)()(log 1 243131 pxxxxyxx 65 5.4.2 5.4.2 基于離散對數(shù)問題的基于離散對數(shù)問題的hash函數(shù)函數(shù) u情況情況2：d =2 因為因為p 1=2q,且且q是奇數(shù)是奇數(shù),所以所以gcd(x4 x2, q)=1. 設(shè)設(shè)y=(x4 x2) 1 mod q，則存在整數(shù)，則存在整數(shù)k，使得，使得 (x4 x2) y=1+qk, 有有 .mod ,mod) 1( ,mod1mod1 )()( 1)( 21 2431 24 p p p p yxxyxx kqkyxx qqp ).1(mod) 1(log)( ),1(mod)()( log 1 2431 1 243131 p xxxx p xxxxyxx 或或 由于由于 q= 1 mod p，所以，所以 ).1(mod)( ),1(mod)()( log 1 2431 1 2