《數(shù)據(jù)加密與PKI應(yīng)用（微課版）》 課件 Chapter05-散列算法

數(shù)據(jù)加密與PKI應(yīng)用第5章散列算法散列算法（也被稱為散列函數(shù)、雜湊函數(shù)、哈希函數(shù)、Hash()）能夠?qū)Σ煌L度的輸入消息，產(chǎn)生固定長度的輸出。這個固定長度的輸出散列值被稱為原輸入消息的消息摘要（MessageDigest），也被稱為原消息的數(shù)字指紋。對于一個安全的散列算法，這個消息摘要通?？梢灾苯幼鳛橄⒌恼J(rèn)證標(biāo)簽。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析

MD，即加強式迭代模式（Merkle-Damgard），1979年RalphMerkle基于數(shù)據(jù)壓縮函數(shù)f()建立的散列函數(shù)的通用模式。MD結(jié)構(gòu)消息M的散列值計算:Hash(M)=CVLCVq=f(CVq-1,mq-1),1≤q≤LCV0=IV目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析消息分組填充填充之后的消息比特長度Lm與448同模512，即填充后的消息比特長度比512的整數(shù)倍少64比特。即使原始消息長度已經(jīng)達到要求（原始消息比特長度與448同模512），也要進行填充。填充的比特位數(shù)大于等于1比特，小于等于512比特。填充模式是第一位為1，后面跟足夠多的0。

MD5算法的輸入為任意長度的消息，對消息以512比特長度為單位進行分組，對所有分組進行迭代式處理，最終輸出128比特的散列值。消息分組填充【例5-1】不同長度原始消息的填充結(jié)果。

(1)原始消息恰好是448比特，則填充512比特，使消息長度為960比特，也就是512比特加上448比特。

(2)原始消息500比特，則填充460比特，使消息長度為960比特，即512比特加上448比特。

(3)原始消息512比特，則填充448比特，使消息長度為960比特，即512比特加上448比特。

最后，將原始消息的長度用64比特數(shù)據(jù)表示，并添加到最后一個分組（448比特的分組）的末尾，使該分組的長度達到512比特。如果原始消息704比特，其二進制值為1011000000，將這個數(shù)字寫為64比特（前面添加54個0），并把它添加到最后一個分組的末尾，使得該分組的大小也是512比特。如果原始消息的長度大于264比特，則以264為模數(shù)取模。初始化MD緩沖區(qū)

MD5的中間結(jié)果和最終結(jié)果保存在128比特的緩沖區(qū)中，緩沖區(qū)使用4個32比特的寄存器（A、B、C、D）表示，這些寄存器的初始值為：A=67452301H01B=efcdab89H02C=98badcfeH03D=10325476H04MD5的壓縮函數(shù)MD5散列算法壓縮函數(shù)處理512比特數(shù)據(jù)分組，每個數(shù)據(jù)分組被分為16個子分組，每個子分組4字節(jié)。MD5壓縮函數(shù)由4輪運算組成，每輪16步，每步處理1個子分組。每輪的輸入為當(dāng)前要處理的消息分組mq-1和緩沖區(qū)的當(dāng)前值A(chǔ)、B、C、D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。MD5(M)=CVLCVq=SUM32(CVq-1,I(mq-1,H(mq-1,G(mq-1,F(mq-1,CVq-1))))),1≤q≤LCV0=IV基本邏輯函數(shù)常量數(shù)據(jù)子分組的使用

當(dāng)前要處理的512比特分組被分為16個子分組，保存于X[i]中，不同輪中使用順序不同。MD5算法的迭代運算temp←B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])A←DD←CC←BB←temp

符號“←”表示賦值運算；

“+”為模232加法。例題分析∵B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])

=

B+CLS9(A+G(B,C,D)+X[6]+T[18])

=A2EF9F08H∴temp=A2EF9F08H(1)A←D

∴A=99669966H(2)D←C

∴D=CCFFCCFFH(3)C←B

∴C=AA55AA55H(4)B←temp

∴B=A2EF9F08H【例5-4】請計算壓縮函數(shù)第2輪第2步的計算結(jié)果。假設(shè)輸入鏈接變量A=CC33CC33H，B=AA55AA55H，C=CCFFCCFFH，D=99669966H。使用的子分組為00AA00AAH。(1)temp←B+CLSs(A+f(B,C,D)+X[ρ(i)]+T[k])第2輪第2步使用的常量是T[18]=C040B340H。已經(jīng)計算得到第2輪16個子分組的使用順序，第2步使用子分組X[6]=00AA00AAH。已經(jīng)計算得到第2輪使用的邏輯函數(shù)G(B,C,D)=CCDDCCDDH。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析SHA-1算法描述

SHA-1算法對消息以512比特長度的分組為單位進行處理，輸出160比特的散列值。SHA-1算法的分組填充方式與MD5算法相同，但是散列值和鏈接變量的長度是160比特。

SHA-1的中間結(jié)果和最終結(jié)果保存于160比特的緩沖區(qū)中。緩沖區(qū)使用5個32比特的寄存器（A、B、C、D、E）表示A=67452301H01B=efcdab89H02C=98badcfeH03D=10325476H04E=c3d2e1f0H05SHA-1的整體結(jié)構(gòu)SHA-1(M)=CVLCVq=SUM32(CVq-1,f4(mq-1,f3(mq-1,f2(mq-1,f1(mq-1,CVq-1))))),1≤q≤LCV1=IV

這4輪運算的結(jié)構(gòu)相同，但是各輪使用的邏輯函數(shù)不同，分別是f1()、f2()、f3()、f4()。SHA-1的壓縮函數(shù)

每輪使用一個加法常量Kt，其中0≤t≤79，表示迭代步數(shù)。80個常量中實際上只有4個不同的取值。temp←E+ft(B,C,D)+CLS5(A)+Wt+Kt

E←D

D←C

C←CLS30(B)

B←A

A←tempSHA-1的壓縮函數(shù)

SHA-1算法每一步迭代都要使用一個32比特的字Wt，所以一共需要80個字。Wt是由消息分組mq擴充得到的。

如果mq=M0||M1||...||M15Wt=Mt,0≤t≤15Wt=CLS1(Mt-3

⊕Mt-8

⊕Mt-14

⊕Mt-16),16≤t≤79temp←E+ft(B,C,D)+CLS5(A)+Wt+Kt

E←D

D←C

C←CLS30(B)

B←A

A←temp【例5-5】如果M0=11221122H，M2=11AA11AA，M8=EE00EE00H，M13=FF66FF66H，M15=66996699H，請計算W15和W16的值。(1)W15==66996699H。(2)W16=CLS1(M13

⊕M8

⊕M2

⊕M0)=23DC23DCH目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用05045.4散列算法分析生日攻擊

分生日攻擊是對散列函數(shù)進行分析和計算碰撞消息的一般方法。它只依賴于消息摘要的長度。這種攻擊方法給出了散列函數(shù)具備安全性的一個必要條件。

生日問題是指在k個人中至少有兩個人的生日相同的概率大于0.5時，k至少多大？(1)因為h()有n個可能的輸出，所以任意取兩個不同的輸入x、y，使得h(x)≠h(y)的概率為

；(2)任意取三個不同的輸入，使得輸出不產(chǎn)生碰撞的概率為

；(3)任意取k個不同的輸入，使得輸出不產(chǎn)生碰撞的概率為

；(4)依據(jù)Taylor級數(shù)，在n>>1的情況下進行約算，可以得到結(jié)論。所以，如果取n=365，則k≈23，即只需要23人，就能以大于0.5的概率找到兩個生日相同的人。

生日攻擊意味著安全消息摘要的長度有一個下限。通常，建議消息摘要的長度至少為128比特。安全散列算法SHA-1的輸出長度選擇160比特正是出于這種考慮。差分分析

差分分析的基本思想是通過分析特定明文差對密文差的影響來獲得可能性最大的密鑰。

2004年，我國山東大學(xué)的王小云教授做的破譯MD5、HAVAL-128、MD4、和RIPEMD算法的報告震驚了整個密碼學(xué)屆。2005年又宣布了破譯SHA-1的消息，再一次震撼了世界密碼學(xué)屆。王小云教授的攻擊方法采用模差分思想，根據(jù)每次循環(huán)中模減差分或異或差分，得到差分特征，通過兩種差分的結(jié)合，提出了新的一系列散列函數(shù)攻擊的有效方法。目錄015.1散列函數(shù)的結(jié)構(gòu)025.2MD5散列算法035.3SHA-1散列算法5.5散列算法的應(yīng)用