第03章_2單向散列函數(shù)

1、12第第5章章 Hash函數(shù)與數(shù)字簽名函數(shù)與數(shù)字簽名l 5.2 Hash5.2 Hash函數(shù)函數(shù)MD5MD5l 5.3 5.3 安全安全HashHash算法算法SHASHA 1 1 l 5.4 5.4 基于分組密碼與離散對(duì)數(shù)的基于分組密碼與離散對(duì)數(shù)的HashHash函數(shù)函數(shù)l 5.5 5.5 消息認(rèn)證消息認(rèn)證35.1 Hash函數(shù)概述函數(shù)概述45.1.1 Hash函數(shù)定義函數(shù)定義l 數(shù)據(jù)安全數(shù)據(jù)安全u機(jī)密性機(jī)密性u(píng)完整性完整性u(píng)認(rèn)證性認(rèn)證性l 密碼技術(shù)主要保證數(shù)據(jù)的機(jī)密性密碼技術(shù)主要保證數(shù)據(jù)的機(jī)密性l Hash函數(shù)能保證數(shù)據(jù)的完整性和認(rèn)證性函數(shù)能保證數(shù)據(jù)的完整性和認(rèn)證性55.1.1 Hash函

2、數(shù)定義函數(shù)定義l Hash函數(shù)定義：函數(shù)定義：Hash函數(shù)是一個(gè)將任意長(zhǎng)度的消息函數(shù)是一個(gè)將任意長(zhǎng)度的消息（message）映射成固定長(zhǎng)度消息的函數(shù)。）映射成固定長(zhǎng)度消息的函數(shù)。n*n*ii*nxhyx h nA AA AA AA AA AA AA AA A)(:0任任意意長(zhǎng)長(zhǎng)度度消消息息集集合合消消息息集集合合長(zhǎng)長(zhǎng)度度為為字字母母表表 將將h稱為一個(gè)稱為一個(gè)Hash函數(shù)（函數(shù)（hash function），或稱為哈希函），或稱為哈希函數(shù)、散列函數(shù)。對(duì)于任何消息數(shù)、散列函數(shù)。對(duì)于任何消息x ，將，將h(x)稱為稱為x的的Hash值、值、散列值、消息摘要（散列值、消息摘要（message dig

3、est）。）。65.1.1 Hash函數(shù)定義函數(shù)定義l Hash函數(shù)的碰撞（函數(shù)的碰撞（collision） 設(shè)x、x是兩個(gè)不同的消息，如果 h(x)=h(x) 則稱x和x是Hash函數(shù)h的一個(gè)（對(duì)）碰撞.75.1.1 Hash函數(shù)定義函數(shù)定義l Hash函數(shù)的分類函數(shù)的分類u單向單向Hash函數(shù)（函數(shù)（one way） 給定一個(gè)給定一個(gè)Hash值值y，如果尋找一個(gè)消息，如果尋找一個(gè)消息x，使得，使得y=h (x)是計(jì)算上不可行的，則稱是計(jì)算上不可行的，則稱h是單向是單向Hash函數(shù)函數(shù). u弱抗碰撞弱抗碰撞Hash函數(shù)（函數(shù)（weakly collision free） 任給一個(gè)消息任給一個(gè)

4、消息x，如果尋找另一個(gè)不同的消息，如果尋找另一個(gè)不同的消息x，使，使得得h(x) =h(x)是計(jì)算上不可行的，則稱是計(jì)算上不可行的，則稱h是弱抗碰撞是弱抗碰撞Hash函數(shù)函數(shù). u強(qiáng)抗碰撞強(qiáng)抗碰撞Hash函數(shù)函數(shù) （strongly collision free） 如果尋找兩個(gè)不同的消息如果尋找兩個(gè)不同的消息x和和x，使得，使得h(x)=h(x)是計(jì)是計(jì)算上不可行的，則稱算上不可行的，則稱h是強(qiáng)抗碰撞是強(qiáng)抗碰撞Hash函數(shù)函數(shù). 85.1.1 Hash函數(shù)定義函數(shù)定義l 安全安全Hash函數(shù)函數(shù)h應(yīng)具有以下性質(zhì)：應(yīng)具有以下性質(zhì)：u 對(duì)任意的消息對(duì)任意的消息x，計(jì)算，計(jì)算h(x)是容易的；是容易

5、的；u h是單向的；是單向的；u h是弱抗碰撞的，或是強(qiáng)抗碰撞的。是弱抗碰撞的，或是強(qiáng)抗碰撞的。95.1 Hash函數(shù)概述函數(shù)概述105.1.2 Hash函數(shù)的安全性l 對(duì)對(duì)Hash函數(shù)的攻擊是指尋找一對(duì)碰撞消息的過程函數(shù)的攻擊是指尋找一對(duì)碰撞消息的過程l 生日悖論（生日悖論（birthday paradox） 生日問題：假設(shè)每個(gè)人的生日是等概率的，每年有生日問題：假設(shè)每個(gè)人的生日是等概率的，每年有365天，天，在在k個(gè)人中至少有兩個(gè)人的生日相同的概率大于個(gè)人中至少有兩個(gè)人的生日相同的概率大于1/2，問，問k最小最小應(yīng)是多少？應(yīng)是多少？ k人生日都不同的概率是：人生日都不同的概率是： .365

6、11.3652136511k.36511.36521365111),365(kkP 2k人人生生日日相相同同的的概概率率為為：人人中中至至少少有有 有有P(365,23)=0.5073。即在。即在23個(gè)人中，至少有兩個(gè)人生日相個(gè)人中，至少有兩個(gè)人生日相同的概率大于同的概率大于0.5，這個(gè)數(shù)字比人們直觀猜測(cè)的結(jié)果小得多，這個(gè)數(shù)字比人們直觀猜測(cè)的結(jié)果小得多，因而稱為生日悖論。因而稱為生日悖論。11l 生日攻擊法生日攻擊法 生日悖論原理可以用于構(gòu)造對(duì)生日悖論原理可以用于構(gòu)造對(duì)Hash函數(shù)的攻擊函數(shù)的攻擊u設(shè)設(shè)Hash函數(shù)值有函數(shù)值有n個(gè)比特，個(gè)比特，m是真消息，是真消息，M是偽造的假是偽造的假消息，

7、分別把消息消息，分別把消息m和和M表示成表示成r和和R個(gè)個(gè)變形的消息變形的消息。消。消息與其變形消息具有不同的形式，但有相同的含義。息與其變形消息具有不同的形式，但有相同的含義。將消息表示成變形消息的方法很多，例如增加空格、將消息表示成變形消息的方法很多，例如增加空格、使用縮寫、使用意義相同的單詞、去掉不必要的單詞使用縮寫、使用意義相同的單詞、去掉不必要的單詞等。等。5.1.2 Hash函數(shù)的安全性函數(shù)的安全性125.1.2 Hash函數(shù)的安全性函數(shù)的安全性l 生日攻擊法生日攻擊法u分別把消息分別把消息m和和M表示成表示成r和和R個(gè)個(gè)變形的消息變形的消息13l 生日攻擊法生日攻擊法u計(jì)算真消息

8、計(jì)算真消息m的變形與假消息的變形與假消息M的變形發(fā)生碰撞的概率的變形發(fā)生碰撞的概率 由于由于n比特長(zhǎng)的散列值共有比特長(zhǎng)的散列值共有2n個(gè)，所以對(duì)于給定個(gè)，所以對(duì)于給定m的變形的變形mi和和M的變形的變形Mj，mi與與Mj不碰撞的概率是不碰撞的概率是1-1/2n。由于。由于M共有共有R個(gè)變形，所以個(gè)變形，所以M的全部變形都不與的全部變形都不與mi碰撞的概率是：碰撞的概率是： 1 1/2.Rn因?yàn)橄⒁驗(yàn)橄共有共有r個(gè)變形，因此個(gè)變形，因此m的變形與的變形與M的變形都不碰撞的概的變形都不碰撞的概率是：率是：.2/1rRn1m的變形與的變形與M的變形發(fā)生碰撞的概率是：的變形發(fā)生碰撞的概率是：.1

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

10、sh函數(shù)函數(shù)u分析分析Hash函數(shù)運(yùn)算的中間值相等的概率函數(shù)運(yùn)算的中間值相等的概率u討論一類利用加密變換構(gòu)造的討論一類利用加密變換構(gòu)造的Hash函數(shù)函數(shù) 設(shè)加密體制為：設(shè)加密體制為： nKnE MMK KMMK K:, 對(duì)于消息對(duì)于消息m=(m1, m2)，其散列值的計(jì)算分以下兩步：，其散列值的計(jì)算分以下兩步： （1） h1= EK(m1, IV)； （2） d=h(m)=EK (m2, h1)， 其中其中IV是加密變換的初始值。是加密變換的初始值。 這類這類Hash函數(shù)將遭受中間相遇攻擊。函數(shù)將遭受中間相遇攻擊。5.1.2 Hash函數(shù)的安全性函數(shù)的安全性16l 中間相遇攻擊（中間相遇攻擊（

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

12、變形M1,1 EKM1,2 EKM1,r EKIVM2,2 DKM2,R DK假消息的第2部分 M2M2,1 DKd目標(biāo)摘要5.1.2 Hash函數(shù)的安全性函數(shù)的安全性h1= EK(m1, IV)d=h(m)=EK(m2, h1) 185.1.2 Hash函數(shù)的安全性函數(shù)的安全性.,.,2 , 1| ),(,.,2 , 1| ),(:.,.,2 , 1|,.,2 , 1|:, 2, 22, 1, 11, 2, 1RjdMDhH riIVMEhH RjM riM jKjiKiji計(jì)計(jì)算算令令 這里這里DK是解密變換。假設(shè)加密變換是解密變換。假設(shè)加密變換EK是隨機(jī)的，那么是隨機(jī)的，那么可以使用生日

13、攻擊法來分析集合可以使用生日攻擊法來分析集合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) 195.1 Hash函數(shù)概述函數(shù)概述205.1.3 Hash5.1.3 Hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法l 壓縮函數(shù)（壓縮函數(shù)（compression function）l 迭代技術(shù)迭代技術(shù) 設(shè)設(shè)x是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度

14、為L(zhǎng)的比特串。重復(fù)應(yīng)的比特串。重復(fù)應(yīng)用壓縮函數(shù)用壓縮函數(shù)f，對(duì)消，對(duì)消息息x進(jìn)行多次壓縮，進(jìn)行多次壓縮，最后得到最后得到x的散列值的散列值) 1(1 , 01 , 0:tfmtm 215.1.3 Hash5.1.3 Hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法 l 計(jì)算消息計(jì)算消息x的散列值的散列值h(x)的步驟的步驟u 預(yù)處理預(yù)處理: 用一個(gè)公開算法在消息用一個(gè)公開算法在消息x右方添加若干比特，右方添加若干比特，得到比特串得到比特串y，使得，使得y的長(zhǎng)度為的長(zhǎng)度為t的倍數(shù)。即有的倍數(shù)。即有 y= x | pad(x) = y1 | y 2 | | yr , 其中其中| yi|=t (i =1,

15、2, r)，pad(x)稱為稱為填充函數(shù)填充函數(shù)。典型的。典型的填充函數(shù)是先添加填充函數(shù)是先添加x長(zhǎng)度長(zhǎng)度| x|的值，再添加若干比特（例的值，再添加若干比特（例如如0）。）。 u迭代過程迭代過程: 設(shè)設(shè)H0=IV是一個(gè)長(zhǎng)度為是一個(gè)長(zhǎng)度為m的初始比特串，的初始比特串，重復(fù)使用壓縮函數(shù)重復(fù)使用壓縮函數(shù)f，依次計(jì)算，依次計(jì)算 Hi= f (Hi 1| yi) (i =1, 2, r).u輸出變換輸出變換: 設(shè)設(shè)g: 0,1m0,1t是一個(gè)公開函數(shù)，令是一個(gè)公開函數(shù)，令 h(x)=g(Hr). 225.1.3 Hash5.1.3 Hash函數(shù)的迭代構(gòu)造法函數(shù)的迭代構(gòu)造法 l 用上述方法構(gòu)造的用上述方

16、法構(gòu)造的Hash函數(shù)稱為迭代函數(shù)稱為迭代Hash函數(shù)。大多數(shù)函數(shù)。大多數(shù)實(shí)用實(shí)用Hash函數(shù)都是迭代函數(shù)都是迭代Hash函數(shù)函數(shù)l 在預(yù)處理階段，必須保證變換在預(yù)處理階段，必須保證變換xy是單射。因?yàn)槿绻A(yù)是單射。因?yàn)槿绻A(yù)處理變換處理變換xy不是單射，則存在不是單射，則存在x x使得使得y=y，從而，從而h(x)=h(x)，即能夠找到，即能夠找到h的碰撞。的碰撞。l 對(duì)于任意無碰撞的壓縮函數(shù)，都可以使用迭代技術(shù)構(gòu)造對(duì)于任意無碰撞的壓縮函數(shù)，都可以使用迭代技術(shù)構(gòu)造一個(gè)無碰撞的一個(gè)無碰撞的Hash函數(shù)。函數(shù)。 23第第5章章 Hash函數(shù)與數(shù)字簽名函數(shù)與數(shù)字簽名l 5.3 5.3 安全安全Has

17、hHash算法算法SHASHA 1 1 l 5.4 5.4 基于分組密碼與離散對(duì)數(shù)的基于分組密碼與離散對(duì)數(shù)的HashHash函數(shù)函數(shù)l 5.5 5.5 消息認(rèn)證消息認(rèn)證245.2 Hash5.2 Hash函數(shù)函數(shù)MD5MD5l MD5(MD:message digest,消息摘要消息摘要) 1990年年10月月, 著名密碼學(xué)家著名密碼學(xué)家R. L. Rivest在在MIT(Massachusetts Institute of Technology)提出了一種提出了一種Hash函數(shù)函數(shù),作為作為RFC 1320 (RFC:互聯(lián)網(wǎng)研究和開發(fā)機(jī)構(gòu)互聯(lián)網(wǎng)研究和開發(fā)機(jī)構(gòu)工作記錄工作記錄)公開發(fā)表公開發(fā)表

18、,稱為稱為MD4. MD5是是MD4的改進(jìn)版本的改進(jìn)版本, 于于1992年年4月作為月作為RFC 1321公開發(fā)表公開發(fā)表.l MD5特性特性u(píng)直接構(gòu)造法: 不依賴任何密碼系統(tǒng)和假設(shè)條件 u算法簡(jiǎn)潔u計(jì)算速度快u特別適合32位計(jì)算機(jī)軟件實(shí)現(xiàn)u傾向于使用低端結(jié)構(gòu).255.2.1 5.2.1 MD5算法算法 l MD5算法的輸入可以是任意長(zhǎng)度的消息算法的輸入可以是任意長(zhǎng)度的消息x，對(duì)輸入消息，對(duì)輸入消息按按512位的分組為單位進(jìn)行處理，輸出位的分組為單位進(jìn)行處理，輸出128位的散列值位的散列值MD(x)。整個(gè)算法分為五個(gè)步驟。整個(gè)算法分為五個(gè)步驟。 l 步驟步驟1: 增加填充位增加填充位u在消息x

19、右邊增加若干比特，使其長(zhǎng)度與448模512同余。也就是說，填充后的消息長(zhǎng)度比512的某個(gè)倍數(shù)少64位。u即使消息本身已經(jīng)滿足上述長(zhǎng)度要求，仍然需要進(jìn)行填充。u例如，若消息長(zhǎng)為448，則仍需要填充512位使其長(zhǎng)度為960位。填充位數(shù)在1到512之間。填充比特的第一位是1，其它均為0。265.2.1 5.2.1 MD5算法算法 l 步驟步驟2: 附加消息長(zhǎng)度值附加消息長(zhǎng)度值 用64位表示原始消息x的長(zhǎng)度，并將其附加在步驟1所得結(jié)果之。若填充前消息長(zhǎng)度大于264，則只使用其低64位。填充方法是把64比特的長(zhǎng)度分成兩個(gè)32比特的字，低32比特字先填充，高32比特字后填充。l 步驟步驟1與步驟與步驟2一

20、起稱為消息的預(yù)處理一起稱為消息的預(yù)處理u 經(jīng)預(yù)處理后，原消息長(zhǎng)度變?yōu)?12的倍數(shù)u設(shè)原消息x經(jīng)預(yù)處理后變?yōu)橄?Y=Y0 Y1 YL1， 其中Yi（i =0,1,L1）是512比特u在后面的步驟中，將對(duì)512比特的分組Yi進(jìn)行處理 275.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步驟1在x的右邊填充1個(gè)“1”和407個(gè)“0”，將x變成448比特的x1: x1= x | 1 | 0 (4

21、07個(gè)) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. 285.2.1 5.2.1 MD5算法算法u例例5.1 假設(shè)消息為假設(shè)消息為: x=“ab

22、cde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16.p經(jīng)步驟2處理后的比特串為（16進(jìn)制表示）：x2=x1|28(64位) =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 28000000 00000000. 295.2.1 5.2.1 MD5算法算法l 步驟步驟3: 初始化初

23、始化MD緩沖區(qū)緩沖區(qū) uMD5算法的中間結(jié)果和最終結(jié)果都保存在128位的緩沖區(qū)里，緩沖區(qū)用4個(gè)32位的寄存器表示。u4個(gè)緩沖區(qū)記為A、B、C、D，其初始值為下列32位整數(shù)（16進(jìn)制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE, D=10 32 54 76.u上述初始值以小端格式存儲(chǔ)(字的最低有效字節(jié)存儲(chǔ)在低地址位置 )為： 字A=01 23 45 67, 字B=89 AB CD EF, 字C=FE DC BA 98, 字D=76 54 32 10.305.2.1 5.2.1 MD5算法算法l 步驟步驟4: 以以512位的分組位的分組(16個(gè)字

24、個(gè)字)為單位處理消息為單位處理消息 uMD5是迭代Hash函數(shù), 其壓縮函數(shù)為:. 1285121285MD1 , 01 , 0:Hu步驟4是MD5算法的主循環(huán)，它以512比特作為分組，重復(fù)應(yīng)用壓縮函數(shù)HMD5，從消息Y的第一個(gè)分組Y1開始，依次對(duì)每個(gè)分組Yi進(jìn)行壓縮，直至最后分組YL1，然后輸出消息x的Hash值?？梢?，MD5的循環(huán)次數(shù)等于消息Y中512比特分組的數(shù)目L。31MD5壓縮函數(shù)HMD5 uHMD5由四輪處理組成由四輪處理組成u加法是指緩沖區(qū)中的加法是指緩沖區(qū)中的4個(gè)字與個(gè)字與CVi中對(duì)應(yīng)的中對(duì)應(yīng)的4個(gè)字分別模個(gè)字分別模232相加相加 . 1285121285MD1 , 01 ,

25、0:H32MD5壓縮函數(shù)壓縮函數(shù)HMD5 uHMD5的四輪處理過程的算法結(jié)構(gòu)相同，每一輪要對(duì)緩的四輪處理過程的算法結(jié)構(gòu)相同，每一輪要對(duì)緩沖區(qū)沖區(qū)ABCD進(jìn)行進(jìn)行16次迭代，每次迭代的運(yùn)算形式為次迭代，每次迭代的運(yùn)算形式為:( , , ) )sabL ag b c dX kT i 其中其中a、b、c、d分別為緩沖分別為緩沖區(qū)區(qū)A、B、C、D中的字，運(yùn)中的字，運(yùn)算結(jié)束后再將（算結(jié)束后再將（a、b、c、d）循環(huán)右移一個(gè)字。循環(huán)右移一個(gè)字。 33MD5壓縮函數(shù)壓縮函數(shù)HMD5 uHMD5的基本邏輯函數(shù)的基本邏輯函數(shù)gp每一輪使用一個(gè)基本邏輯函數(shù)每一輪使用一個(gè)基本邏輯函數(shù)g，每個(gè)基本邏輯函數(shù)的，每個(gè)基本

26、邏輯函數(shù)的輸入是三個(gè)輸入是三個(gè)32位的字，輸出是一個(gè)位的字，輸出是一個(gè)32位的字，它執(zhí)行位位的字，它執(zhí)行位邏輯運(yùn)算，即輸出的第邏輯運(yùn)算，即輸出的第n位是其三個(gè)輸入的第位是其三個(gè)輸入的第n位的函數(shù)位的函數(shù)p基本邏輯函數(shù)基本邏輯函數(shù)g的定義的定義 符號(hào)符號(hào) 、 、 和和 分別表示邏輯操作分別表示邏輯操作AND、OR、NOT和和XOR 34MD5壓縮函數(shù)壓縮函數(shù)HMD5 uHMD5的基本邏輯函數(shù)的基本邏輯函數(shù)gp基本邏輯函數(shù)基本邏輯函數(shù)g的真值表的真值表 b c dF G H I0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 11 0 1 00 1 1 0

27、1 0 0 10 0 1 10 1 0 11 1 0 01 1 1 035MD5壓縮函數(shù)壓縮函數(shù)HMD5 u字組字組X 把當(dāng)前處理的把當(dāng)前處理的512比特的分組比特的分組Yi依次分成依次分成16個(gè)個(gè)32比特的字比特的字, 分別記為分別記為X0,1,15.u在每一輪的在每一輪的16步迭代中步迭代中, 每一步迭代使用一個(gè)字每一步迭代使用一個(gè)字,迭代步數(shù)不同使用的字也不相同迭代步數(shù)不同使用的字也不相同. 因此因此, 16步迭代步迭代恰好用完恰好用完16個(gè)字個(gè)字.36MD5壓縮函數(shù)壓縮函數(shù)HMD5 u對(duì)于不同輪處理過程對(duì)于不同輪處理過程, 使用使用16個(gè)字的順序不一樣個(gè)字的順序不一樣.p第一輪中，使用

28、順序?yàn)閄0,1,15。p第二輪中使用順序由下列置換確定: 2(i)= (1+5i) mod 16p第三輪中使用順序由下列置換確定: 3(i)= (5+3i) mod 16p第四輪中使用順序由下列置換確定: 4(i)= 7i mod 16.u例如例如: 第三輪處理過程的第第三輪處理過程的第i步迭代使用字步迭代使用字 X 3(i)= X(5+3i) mod 16; 第第8步迭代使用字步迭代使用字 X 3(8)=X(5+3 8)=X29=X13. 37MD5壓縮函數(shù)壓縮函數(shù)HMD5 T1=D76AA478T2=E8C7B756T3=242070DBT4=C1BDCEEET5=F57C0FAFT6=4

29、787C62AT7=A8304613T8=FD469501T9=698098D8T10=8B44F7AFT11=FFFF5BB1T12=895CD7BET13=6B901122T14=FD987193T15=A679438ET16=49B40821T17=F61E2562T18=C040B340T19=265E5A51T20=E9B6C7AAT21=D62F105DT22=02441453T23=D8A1E681T24=E7D3FBC8T25=21E1CDE6T26=C33707D6T27=F4D50D87T28=455A14EDT29=A9E3E905T30=FCEFA3F8T31=676F

30、02D9T32=8D2A4C8AT33=FFFA3942T34=8771F681T35=699D6122T36=FDE5380CT37=A4BEEA44T38=4BDECFA9T39=F6BB4B60T40=BEBFBC70T41=289B7EC6T42=EAA127FAT43=D4EF3085T44=04881D05T45=D9D4D039T46=E6DB99E5T47=1FA27CF8T48=C4AC5665T49=F4292244T50=432AFF97T51=AB9423A7T52=FC93A039T53=655B59C3T54=8F0CCC92T55=FFEFF47DT56=8584

31、5DD1T57=6FA87E4FT58=FE2CE6E0T59=A3014314T60=4E0811A1T61=F7537E82T62=BD3AF235T63=2AD7D2BBT64=EB86D391u常數(shù)表常數(shù)表T：64個(gè)個(gè)32位常數(shù)位常數(shù)p Ti =232 abs(sin(i)的整數(shù)部分的整數(shù)部分(i=1,2,64).38MD5壓縮函數(shù)壓縮函數(shù)HMD5 u常數(shù)表常數(shù)表T：64個(gè)個(gè)32位常數(shù)位常數(shù)p Ti =232abs(sin(i)的整數(shù)部分(i=1,2,64).p常數(shù)表T的作用是“隨機(jī)化”32位的輸入數(shù)據(jù)，即消除輸入數(shù)據(jù)的規(guī)律性。pHMD5的第k輪處理過程使用常數(shù)表T的元素 T16(k1

32、)+1, 16(k1)+2,16k (k=1,2,3,4)， 第k輪的第i次迭代使用元素 T16( k1)+ i(i=1,2,16).39MD5壓縮函數(shù)HMD5 u循環(huán)左移位數(shù)循環(huán)左移位數(shù)s Ls(v)表示對(duì)表示對(duì)32位的變量位的變量v循環(huán)左移循環(huán)左移s位。位。s的值與輪的值與輪數(shù)和迭代步數(shù)有關(guān)。數(shù)和迭代步數(shù)有關(guān)。 步數(shù)輪數(shù)123456789101112 13 14 15 1612347546129111017141615222023217546129111017141615222023217546129111017141615222023217546129111017141615222023

33、21405.2.1 MD55.2.1 MD5算法算法 l 步驟步驟5: 輸出輸出 依次對(duì)消息的L個(gè)512比特的分組進(jìn)行處理，第L個(gè)分組處理后的輸出值即是消息x的散列值MD(x)。 可將MD5的處理過程歸納如下：uCV0=IVuCVi+1=SUM32CVi, RFI (Yi, RFH (Yi, RFG (Yi, RFF (Yi, CVi) ) (i=0,1, L1)uMD= CVL1.uIV =第三步定義的緩沖區(qū)ABCD的初值uL =消息經(jīng)第一步和第二步處理后分組的個(gè)數(shù)uYi =消息的第i個(gè)512位分組uRFu =使用基本邏輯函數(shù)u的輪函數(shù)uSUM32=對(duì)輸入字的模232相加uMD =散列值.4

34、15.2.2 MD55.2.2 MD5的安全性的安全性 l Rivest猜測(cè)，猜測(cè)，MD5可能是可能是128位位Hash函數(shù)中強(qiáng)度最大的。函數(shù)中強(qiáng)度最大的。l 目前，對(duì)MD5的攻擊已取得以下結(jié)果：uT. Berson（1992）已經(jīng)證明，對(duì)單輪的MD5算法，利用差分密碼分析，可以在合理的時(shí)間內(nèi)找出散列值相同的兩條消息。這一結(jié)果對(duì)MD5四輪運(yùn)算的每一輪都成立。但是，目前尚不能將這種攻擊推廣到具有四輪運(yùn)算的MD5上.uB. Boer和A. Bosselaers（1993）說明了如何找到消息分組和MD5兩個(gè)不同的初始值,使它們產(chǎn)生相同的輸出. 也就是說, 對(duì)一個(gè)512位的分組, MD5壓縮函數(shù)對(duì)緩沖

35、區(qū)ABCD的不同值產(chǎn)生相同的輸出,這種情況稱為偽碰撞（pseudo-collision）.目前尚不能用該方法成功攻擊MD5算法.425.2.2 MD55.2.2 MD5的安全性的安全性 uH. Dobbertin（1996）找到了MD5無初始值的碰撞(pseudo-collision).給定一個(gè)512位的分組,可以找到另一個(gè)512位的分組,對(duì)于選擇的初始值IV0,它們的MD5運(yùn)算結(jié)果相同. 到目前為止, 尚不能用這種方法對(duì)使用MD5初始值IV的整個(gè)消息進(jìn)行攻擊. uR. L. Rivest曾猜想作為128比特長(zhǎng)的Hash函數(shù)，MD5的強(qiáng)度達(dá)到了最大：要找出兩個(gè)具有相同Hash值的消息需執(zhí)行O(

36、264)次運(yùn)算，而要找出具有給定Hash值的一個(gè)消息則要執(zhí)行O(2128)次運(yùn)算。43MD5算法的安全性算法的安全性u(píng) 我國山東大學(xué)王小云教授（我國山東大學(xué)王小云教授（2004）提出的攻擊對(duì)）提出的攻擊對(duì)MD5最具威脅。對(duì)于最具威脅。對(duì)于MD5的初始值的初始值IV，王小云找到了，王小云找到了許多許多512位的分組對(duì)，它們的位的分組對(duì)，它們的MD5值相同值相同. 王小云在美州密碼年會(huì)（王小云在美州密碼年會(huì)（Crypto2004）上做了攻擊）上做了攻擊MD5、HAVAL-128、MD4和和RIPEMD算法的報(bào)告，公算法的報(bào)告，公布了布了MD系列算法的破解結(jié)果。對(duì)于系列算法的破解結(jié)果。對(duì)于MD5的攻

37、擊，報(bào)告的攻擊，報(bào)告中給出了一個(gè)具體的碰撞例子。中給出了一個(gè)具體的碰撞例子。 44設(shè)m1表示消息（十六進(jìn)制表示）：00000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c00000010 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89 00000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a00000030 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b 00000040 96 0b 1d

38、 d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d500000050 35 73 9a c7 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f 00000060 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79 cc 15 5c 00000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a d8 35 cc a7 e3. m2表示消息：00000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c00000010 2f ca b5 07 12 46

39、 7e ab 40 04 58 3e b8 fb 7f 89 00000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a 00000030 08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b00000040 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d500000050 35 73 9a 47 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f 00000060 75 27 7f 79 30 d5 5c eb 22 e8 ad b

40、a 79 4c 15 5c 00000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a 58 35 cc a7 e3. MD5算法的安全性算法的安全性45MD5算法的安全性算法的安全性l 則有 MD5(m1) = MD5(m2) a4c0d35c95a63a805915367dcfe6b751.l 消息m1與m2只有6個(gè)字節(jié)不同，即粗體字符部分。實(shí)際上，它們的Hamming距離也僅為6比特。這清楚地表明MD5不是強(qiáng)無碰撞的, 也否定了R. L. Rivest的猜想。 事實(shí)上, 利用數(shù)據(jù)鏈接的方法，可通過在消息m1與m2的后端鏈接相同的數(shù)據(jù)，得到無窮多個(gè)碰撞的例子。MD5

41、的安全性受到了嚴(yán)重的威脅。在安全強(qiáng)度要求較高的系統(tǒng)中，應(yīng)避免MD5的使用。l 國際密碼學(xué)家國際密碼學(xué)家Lenstra利用王小云等提供的利用王小云等提供的MD5碰撞，偽造碰撞，偽造了符合了符合X.509標(biāo)準(zhǔn)的數(shù)字證書標(biāo)準(zhǔn)的數(shù)字證書. l MD5算法抗密碼分析能力較弱算法抗密碼分析能力較弱,對(duì)對(duì)MD5的生日攻擊所需代價(jià)的生日攻擊所需代價(jià)為為264數(shù)量級(jí)數(shù)量級(jí). 所以所以, 必須設(shè)計(jì)新的必須設(shè)計(jì)新的Hash算法算法, 使其與使其與MD5相比相比具有更長(zhǎng)的散列值和更高的安全性具有更長(zhǎng)的散列值和更高的安全性.46第第5章章 Hash函數(shù)與數(shù)字簽名函數(shù)與數(shù)字簽名 l 5.4 5.4 基于分組密碼與離散對(duì)數(shù)

42、的基于分組密碼與離散對(duì)數(shù)的HashHash函數(shù)函數(shù)l 5.5 5.5 消息認(rèn)證消息認(rèn)證475.3 5.3 安全安全HashHash算法算法SHASHA 1 1l 安全安全Hash算法算法SHA（secure hash algorithm）由美國標(biāo)）由美國標(biāo)準(zhǔn)與技術(shù)研究所（準(zhǔn)與技術(shù)研究所（NIST）設(shè)計(jì)并于）設(shè)計(jì)并于1993年作為聯(lián)邦信息年作為聯(lián)邦信息處理標(biāo)準(zhǔn)（處理標(biāo)準(zhǔn)（FIPS 180）發(fā)布）發(fā)布l 修改版于修改版于1995年發(fā)布（年發(fā)布（FIPS 180 1），通常稱之為），通常稱之為SHA 1。該標(biāo)準(zhǔn)稱為。該標(biāo)準(zhǔn)稱為安全安全Hash函數(shù)函數(shù)。l RFC 3174也給出了也給出了SHA 1，

43、它基本上是復(fù)制，它基本上是復(fù)制FIPS 180 1的內(nèi)容，但增加了的內(nèi)容，但增加了C代碼實(shí)現(xiàn)。代碼實(shí)現(xiàn)。l SHA 1算法的輸入是長(zhǎng)度小于算法的輸入是長(zhǎng)度小于264的任意消息的任意消息x，輸出，輸出160位的散列值。位的散列值。485.3.1 SHA5.3.1 SHA 1 1算法步驟算法步驟l SHA 1處理消息的過程與處理消息的過程與MD5類似，對(duì)輸入消息按類似，對(duì)輸入消息按512位位的分組為單位進(jìn)行處理，整個(gè)算法分為五個(gè)步驟的分組為單位進(jìn)行處理，整個(gè)算法分為五個(gè)步驟l 步驟步驟1: 增加填充位增加填充位 在消息右邊增加若干比特，使其長(zhǎng)度與在消息右邊增加若干比特，使其長(zhǎng)度與448模模512同

44、余。即使消息本身同余。即使消息本身已經(jīng)滿足上述長(zhǎng)度要求，仍然需要進(jìn)行填充。填充位數(shù)在已經(jīng)滿足上述長(zhǎng)度要求，仍然需要進(jìn)行填充。填充位數(shù)在1到到512之之間。填充比特的第一位是間。填充比特的第一位是“1”，其它均為，其它均為“0”。l 步驟步驟2: 附加消息長(zhǎng)度值附加消息長(zhǎng)度值 用用64位表示原始消息位表示原始消息x的長(zhǎng)度，并將其附加在步驟的長(zhǎng)度，并將其附加在步驟1所得結(jié)果之后。所得結(jié)果之后。l 步驟步驟1與步驟與步驟2一起稱為消息的預(yù)處理一起稱為消息的預(yù)處理 經(jīng)預(yù)處理后，原消息長(zhǎng)度變?yōu)榻?jīng)預(yù)處理后，原消息長(zhǎng)度變?yōu)?12的倍數(shù)。設(shè)原消息的倍數(shù)。設(shè)原消息x經(jīng)預(yù)處理后變經(jīng)預(yù)處理后變?yōu)橄橄=Y0

45、Y1 YL 1，其中，其中Yi（i =0,1,L 1）是）是512比特。在后面的比特。在后面的步驟中，將對(duì)步驟中，將對(duì)512比特的分組比特的分組Yi進(jìn)行處理。進(jìn)行處理。495.3.1 SHA5.3.1 SHA 1 1算法步驟算法步驟l 步驟步驟3: 初始化緩沖區(qū)初始化緩沖區(qū) SHA 1算法的中間結(jié)果和最終結(jié)果保存在算法的中間結(jié)果和最終結(jié)果保存在160位的緩沖區(qū)里，緩沖區(qū)位的緩沖區(qū)里，緩沖區(qū)用用5個(gè)個(gè)32位的寄存器表示。位的寄存器表示。5個(gè)緩沖區(qū)記為個(gè)緩沖區(qū)記為A、B、C、D、E，其初始，其初始值為下列值為下列32位整數(shù)（位整數(shù)（16進(jìn)制表示）：進(jìn)制表示）： A=67 45 23 01, B=E

46、F CD AB 89, C=98 BA DC FE , D=10 32 54 76, E=C3 D2 E1 F0. 其中，前其中，前4個(gè)初始值與個(gè)初始值與MD5的初始值相同。的初始值相同。SHA 1以大端格式存儲(chǔ)緩以大端格式存儲(chǔ)緩沖區(qū)的值，即字的最高有效字節(jié)存于低地址字節(jié)位置。因此，上述沖區(qū)的值，即字的最高有效字節(jié)存于低地址字節(jié)位置。因此，上述初始值存儲(chǔ)為（十六進(jìn)制）：初始值存儲(chǔ)為（十六進(jìn)制）： 字字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.505.3.1 SHA5.3.1

47、 SHA 1 1算法步驟算法步驟l 步驟步驟4: 以以512位的分組（位的分組（16個(gè)字）為單位處理消息個(gè)字）為單位處理消息uSHA 1是迭代是迭代Hash函數(shù)，其壓縮函數(shù)為：函數(shù)，其壓縮函數(shù)為：. 160512160SHA1 , 01 , 0:Hu步驟步驟4是是SHA 1算法的主循環(huán)，它以算法的主循環(huán)，它以512比特作為分組，比特作為分組，重復(fù)應(yīng)用壓縮函數(shù)重復(fù)應(yīng)用壓縮函數(shù)HSHA，從消息，從消息Y的第一個(gè)分組的第一個(gè)分組Y1開開始，依次對(duì)每個(gè)分組始，依次對(duì)每個(gè)分組Yi進(jìn)行壓縮，直至最后分組進(jìn)行壓縮，直至最后分組YL 1，然后輸出消息然后輸出消息x的的Hash值。值。uSHA 1循環(huán)次數(shù)等于消

48、息循環(huán)次數(shù)等于消息Y中中512比特分組的數(shù)目比特分組的數(shù)目L。51SHASHA 1 1的的壓縮函數(shù)壓縮函數(shù)H HSHASHA u由四輪處理組成由四輪處理組成u加法是模加法是模232相加相加 CVi (160)Yi (512)BCDAEf4, K, W60,61,79, 20步BCDAEf2, K, W20,21,39, 20步BCDAEf3, K, W40,41,59, 20步BCDAEf1, K, W0,1,19, 20步 + + + + +CVi+1 (160)52SHASHA 1 1的壓縮函數(shù)的壓縮函數(shù)H HSHASHA u壓縮函數(shù)壓縮函數(shù)HSHA的四輪處理過程的算法結(jié)構(gòu)相同，每一輪的四

49、輪處理過程的算法結(jié)構(gòu)相同，每一輪要對(duì)緩沖區(qū)要對(duì)緩沖區(qū)ABCDE進(jìn)行進(jìn)行20次迭代，每次迭代的運(yùn)算形次迭代，每次迭代的運(yùn)算形式為式為DC,(B),A,),(A)D)C,(B,(EED,C,B,A,305LKWLftt A B C D E A B C D E + + f +Wt +KtL30L5 其中其中A、B、C、D、E分別為五個(gè)緩沖分別為五個(gè)緩沖區(qū)中的字，運(yùn)算結(jié)區(qū)中的字，運(yùn)算結(jié)束后再將（束后再將（A、B、C、D、E）循環(huán)右）循環(huán)右移一個(gè)字。移一個(gè)字。53DCBD)(CD)(BC)(BDCBD)B(C)(BSHASHA 1 1的壓縮函數(shù)的壓縮函數(shù)H HSHASHA u基本邏輯函數(shù)基本邏輯函數(shù)fp

50、每一輪使用一個(gè)基本邏輯函數(shù)每一輪使用一個(gè)基本邏輯函數(shù)f，每個(gè)基本邏輯函，每個(gè)基本邏輯函數(shù)的輸入是三個(gè)數(shù)的輸入是三個(gè)32位的字，輸出是一個(gè)位的字，輸出是一個(gè)32位的字，位的字，它執(zhí)行位邏輯運(yùn)算，即輸出的第它執(zhí)行位邏輯運(yùn)算，即輸出的第n位是其三個(gè)輸入位是其三個(gè)輸入第第n位的函數(shù)。位的函數(shù)。輪數(shù)基本邏輯函數(shù)ff(B, C, D)1234f1(B, C, D)f2(B, C, D)f3(B, C, D)f4(B, C, D)54SHASHA 1 1的壓縮函數(shù)的壓縮函數(shù)H HSHASHA u基本邏輯函數(shù)基本邏輯函數(shù)fp基本邏輯函數(shù)基本邏輯函數(shù)f的真值表的真值表B C Df1 f2 f3 f40 0 00

51、 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 01 1 0 10 1 0 11 0 1 00 1 0 10 0 1 01 0 1 01 1 1 155SHASHA 1 1的壓縮函數(shù)的壓縮函數(shù)H HSHASHA u字組字組Wtp t（0t79）代表迭代步數(shù)，依次表示第一、二、三、四輪處理過程進(jìn)行的迭代次序pWt(0t79)是32比特的字，它的前面16個(gè)字W0,W1,W15依次取自當(dāng)前輸入分組Yi，其余字為).79,.,17,16()(3814161tWWWWLWttttt u加法常數(shù)表加法常數(shù)表Kt30303030222325210迭代步數(shù)迭代步數(shù)十六進(jìn)制十六進(jìn)

52、制十進(jìn)制十進(jìn)制0t1920t3940t5960t795A8279996ED9EBA18F1BBCDCCA62C1D6565.3.1 SHA5.3.1 SHA 1 1算法步驟算法步驟l 步驟步驟5: 輸出輸出u第L個(gè)分組處理后的輸出值即是消息x的散列值MD(x)uSHA1的處理過程歸納如下：pCV0=IVp CVi+1=SUM32(CVi, ABCDEi ) (i=0,1, L1)pMD= CVL1u其中：pIV =第三步定義的緩沖區(qū)ABCDE的初值pABCDEi =處理第i個(gè)消息分組時(shí)最后一輪的輸出pL =消息經(jīng)第一步和第二步處理后分組的個(gè)數(shù)pSUM32=對(duì)輸入字的模232相加pMD =散列值

53、.575.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比較的比較l SHA 1與與MD5的算法類似，所以它們的性質(zhì)極為相似的算法類似，所以它們的性質(zhì)極為相似l 抗窮舉攻擊的能力抗窮舉攻擊的能力uSHA1抗窮舉攻擊的能力比MD5強(qiáng) u用窮舉攻擊方法產(chǎn)生具有給定散列值的消息pMD5需要的代價(jià)為2128數(shù)量級(jí)pSHA1需要的代價(jià)為2160數(shù)量級(jí) u用窮舉攻擊方法產(chǎn)生兩個(gè)具有相同散列值的消息 pMD5需要的代價(jià)為264數(shù)量級(jí)pSHA1需要的代價(jià)為280數(shù)量級(jí) l 抗密碼分析的能力抗密碼分析的能力 uMD5算法抗密碼分析的能力較弱算法抗密碼分析的能力較弱uSHA 1算法抗密碼分析的能力似乎

54、并不弱算法抗密碼分析的能力似乎并不弱 585.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比較的比較l 速度速度 SHA 1執(zhí)行的速度比執(zhí)行的速度比MD5的速度慢得多的速度慢得多 l 簡(jiǎn)潔性簡(jiǎn)潔性 SHA 1和和MD5兩種算法都易于描述和實(shí)現(xiàn)，不需要使用兩種算法都易于描述和實(shí)現(xiàn)，不需要使用大的程序和置換表大的程序和置換表 l 數(shù)據(jù)的存儲(chǔ)方式數(shù)據(jù)的存儲(chǔ)方式 MD5使用使用little endian方式，方式，SHA 1使用使用big endian方式。方式。這兩種方式?jīng)]有本質(zhì)的差異這兩種方式?jīng)]有本質(zhì)的差異 59l MD5和和SHA-1其實(shí)都屬于其實(shí)都屬于MD4的改進(jìn)版本，它們之間的

55、比的改進(jìn)版本，它們之間的比較可簡(jiǎn)單地表示如下較可簡(jiǎn)單地表示如下(更好的雪崩是指將前一步的輸出加到更好的雪崩是指將前一步的輸出加到下一輪，以加速雪崩效應(yīng)下一輪，以加速雪崩效應(yīng))， MD4、 MD5與與SHA-1比較如下比較如下表所示。表所示。60l 1、（、（1）利用）利用MD5算法對(duì)一個(gè)文件進(jìn)行處理，計(jì)算它的算法對(duì)一個(gè)文件進(jìn)行處理，計(jì)算它的Hash值，提交程序代碼和運(yùn)算結(jié)果。值，提交程序代碼和運(yùn)算結(jié)果。l （2）微軟的系統(tǒng)軟件都有）微軟的系統(tǒng)軟件都有MD5驗(yàn)證，嘗試查找軟件的驗(yàn)證，嘗試查找軟件的MD5值。同時(shí)，在值。同時(shí)，在Windows操作系統(tǒng)中，通過開始操作系統(tǒng)中，通過開始運(yùn)運(yùn)行行sigv

56、erif命令，利用數(shù)字簽名查找非命令，利用數(shù)字簽名查找非Windows的系統(tǒng)軟的系統(tǒng)軟件。件。練習(xí)題ex61第第5章章 Hash函數(shù)與數(shù)字簽名函數(shù)與數(shù)字簽名l 5.5 5.5 消息認(rèn)證消息認(rèn)證625.4 5.4 基于分組密碼與離散對(duì)數(shù)的基于分組密碼與離散對(duì)數(shù)的HashHash函數(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ù)也是安全的635.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造HashHash函數(shù)函數(shù)

57、l 已知條件已知條件 設(shè)設(shè)Ek是一個(gè)分組長(zhǎng)度為是一個(gè)分組長(zhǎng)度為n的分組密碼的加密算法，的分組密碼的加密算法，密鑰為密鑰為k，對(duì)于任意的消息，對(duì)于任意的消息x，首先對(duì)，首先對(duì)x進(jìn)行分組，進(jìn)行分組，每組的長(zhǎng)度為每組的長(zhǎng)度為n。設(shè)消息。設(shè)消息x為為: x=x1 x2xL, 其中其中xi GF(2)n（1 i L）.645.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造HashHash函數(shù)函數(shù)l 基于分組密碼基于分組密碼CBC(密文分組鏈接密文分組鏈接)工作模式構(gòu)造工作模式構(gòu)造Hash函數(shù)函數(shù)u首先選取一個(gè)初始值首先選取一個(gè)初始值: y0 =IV GF(2)n，u然后依次計(jì)算然后依次計(jì)算

58、: u最后定義最后定義Hash值為值為: hCBC(x)=yL. 1() (1),ikiiyExyiL IV=y0 x1 Ek y1 x2 Ek y2 xL EkyL=hCBC(x)65l 基于分組密碼基于分組密碼CFB(密文反饋密文反饋)工作模式構(gòu)造工作模式構(gòu)造Hash函數(shù)函數(shù)u首先選取一個(gè)初始值首先選取一個(gè)初始值: y0 =IV GF(2)n，u然后依次計(jì)算然后依次計(jì)算: u最后定義最后定義Hash值為值為: hCFB(x)=yL. 5.4.1 5.4.1 利用分組密碼算法構(gòu)造利用分組密碼算法構(gòu)造HashHash函數(shù)函數(shù)1() (1),iikiyxEyiL IV=y0 x1 y1 Ek x

59、2 y2 EkyL=hCFB(x) xL Ekl 在密鑰公開的情況下，基于分組密碼在密鑰公開的情況下，基于分組密碼CBC工作模工作模式和式和CFB工作模式構(gòu)造的工作模式構(gòu)造的Hash函數(shù)是不安全的，函數(shù)是不安全的，它們甚至不是弱無碰撞的它們甚至不是弱無碰撞的.66l 基于一些困難數(shù)學(xué)問題，諸如離散對(duì)數(shù)問題、因子分基于一些困難數(shù)學(xué)問題，諸如離散對(duì)數(shù)問題、因子分解問題、背包問題等可以構(gòu)造出一些解問題、背包問題等可以構(gòu)造出一些Hash函數(shù)，這些函數(shù)，這些Hash函數(shù)的安全性依賴于對(duì)應(yīng)數(shù)學(xué)問題的困難性函數(shù)的安全性依賴于對(duì)應(yīng)數(shù)學(xué)問題的困難性l Chaum、Heijst和和Pfitzmann（1992年）

60、提出的基于離年）提出的基于離散對(duì)數(shù)問題構(gòu)造的散對(duì)數(shù)問題構(gòu)造的Hash函數(shù)函數(shù)u運(yùn)行速度不是很快運(yùn)行速度不是很快u可以證明是安全的可以證明是安全的.l Chaum Heijst Pfitzmann Hash函數(shù)的構(gòu)造函數(shù)的構(gòu)造 設(shè)設(shè)p是一個(gè)大素?cái)?shù)，是一個(gè)大素?cái)?shù)，q=(p 1)/2是一個(gè)素?cái)?shù)，是一個(gè)素?cái)?shù)， 和和 是是Zp的兩的兩個(gè)本原元。假設(shè)離散對(duì)數(shù)個(gè)本原元。假設(shè)離散對(duì)數(shù)log 是計(jì)算上不可行的。定義是計(jì)算上不可行的。定義Hash函數(shù)函數(shù)h為：為：5.4.2 5.4.2 基于離散對(duì)數(shù)問題的基于離散對(duì)數(shù)問題的Hash函數(shù)函數(shù) .mod),(,:2121*pxxhZZZhxxppp 67l Chaum