認(rèn)證與雜湊函數(shù)課件

第六講：認(rèn)證與雜湊函數(shù)一、認(rèn)證與認(rèn)證系統(tǒng)二、認(rèn)證碼三、雜湊函數(shù)四、雜湊函數(shù)的設(shè)計(jì)理論五、MD-5六、SHA七、GOST八、其他雜湊算法2022/11/231第六講：認(rèn)證與雜湊函數(shù)一、認(rèn)證與認(rèn)證系統(tǒng)2022/10/2

第六講：認(rèn)證與雜湊函數(shù)

保密的目的是防止對手破譯系統(tǒng)中的機(jī)密信息。認(rèn)證(Authentication)

是防止主動攻擊，如偽裝、竄擾等，的重要技術(shù)，包括對消息的內(nèi)容、順序、和時(shí)間的竄改以及重發(fā)等。

認(rèn)證目的：（1）驗(yàn)證信息的發(fā)送者是真的、而不是冒充的，此為實(shí)體認(rèn)證，包括信源、信宿等的認(rèn)證和識別；（2）驗(yàn)證信息的完整性，此為消息認(rèn)證，驗(yàn)證數(shù)據(jù)在傳送或存儲過程中未被竄改、重放或延遲等。認(rèn)證的理論與技術(shù)：認(rèn)證和認(rèn)證系統(tǒng)、雜湊(Hash)函數(shù)、數(shù)字簽名、身份證明、認(rèn)證協(xié)議。

2022/11/232第六講：認(rèn)證與雜湊函數(shù)保密的目的是防

第六講：認(rèn)證與雜湊函數(shù)

一、認(rèn)證與認(rèn)證系統(tǒng)類似于保密系統(tǒng)的信息理論，可將信息論用于研究認(rèn)證系統(tǒng)的理論安全性和實(shí)際安全性問題，指出認(rèn)證系統(tǒng)的性能極限以及設(shè)計(jì)認(rèn)證碼必須遵循的原則。保密和認(rèn)證同是信息系統(tǒng)安全的兩個(gè)重要方面，但它們是兩個(gè)不同屬性的問題。認(rèn)證不能自動地提供保密性，而保密也不能自然地提供認(rèn)證功能。一個(gè)純認(rèn)證系統(tǒng)的模型如圖6-1-1所示。在這個(gè)系統(tǒng)中的發(fā)送者通過一個(gè)公開信道將消息送給接收者，接收者不僅想收到消息本身，而且還要驗(yàn)證消息是否來自合法的發(fā)送者及消息是否經(jīng)過竄改。系統(tǒng)中的密碼分析者不僅要截收和分析信道中傳送的密報(bào)，而且可偽造密文送給接收者進(jìn)行欺詐，稱其為系統(tǒng)的竄擾者(Tamper)更加貼切。實(shí)際認(rèn)證系統(tǒng)可能還要防止收、發(fā)之間的相互欺詐。2022/11/233第六講：認(rèn)證與雜湊函數(shù)

一、認(rèn)證與認(rèn)證系統(tǒng)一、認(rèn)證與認(rèn)證系統(tǒng)

圖6-1-1純認(rèn)證系統(tǒng)模型

安全信道信道竄擾者認(rèn)證編碼器認(rèn)證譯碼器信源信宿密鑰源認(rèn)證信道2022/11/234一、認(rèn)證與認(rèn)證系統(tǒng)安全信道信道竄擾者認(rèn)一、認(rèn)證與認(rèn)證系統(tǒng)

認(rèn)證編碼：在要發(fā)送的消息中引入多余度，使通過信道傳送的可能序列集Y大于消息集X。對于任何選定的編碼規(guī)則(相應(yīng)于某一特定密鑰)：發(fā)方可從Y中選出用來代表消息的許用序列，即碼字；收方可根據(jù)編碼規(guī)則唯一地確定出發(fā)方按此規(guī)則向他傳來的消息。竄擾者由于不知道密鑰，因而所偽造的假碼字多是Y中的禁用序列，收方將以很高的概率將其檢測出來而被拒絕。認(rèn)證系統(tǒng)設(shè)計(jì)者的任務(wù)是構(gòu)造好的認(rèn)證碼(AuthenticationCode)，使接收者受騙概率極小化。令xX為要發(fā)送的消息，kK是發(fā)方選定的密鑰，y=A(x,k)Y是表示消息x的認(rèn)證碼字，Ak={y=A(x,k),xX}為認(rèn)證碼。Ak是Y中的許用(合法)序列集，而其補(bǔ)集Ak則為禁用序列集，且Ak∪Ak=Y。2022/11/235一、認(rèn)證與認(rèn)證系統(tǒng)認(rèn)證編碼：在要發(fā)送的消息中引入多余一、認(rèn)證與認(rèn)證系統(tǒng)接收者知道認(rèn)證編碼A(，)和密鑰k，故從收到的y可惟一地確定出消息x。竄擾者雖然知道X、Y、y、A(，)，但不知道具體密鑰k，他的目標(biāo)是想偽造出一個(gè)假碼字y*，使y*Ak，使接收者收到y(tǒng)*后可以密鑰k解密得到一個(gè)合法的、可能由發(fā)端送出的消息x*，使接收者上當(dāng)受騙。如果發(fā)生這一事件，則認(rèn)為竄擾者欺詐成功。

竄擾者攻擊的基本方式：

模仿偽造(ImpersonativeFraudulent)，竄擾者在未觀測到認(rèn)證信道中傳送的合法消息(或認(rèn)證碼字)條件下偽造假碼字y*，稱其為無密文偽造更合適些。若接收者接受y*作為認(rèn)證碼字，則說竄擾者攻擊成功。

2022/11/236一、認(rèn)證與認(rèn)證系統(tǒng)接收者知道認(rèn)證編碼A(，一、認(rèn)證與認(rèn)證系統(tǒng)代換偽造(SubstitutionFraudulent)，竄擾者截收到認(rèn)證系統(tǒng)中的認(rèn)證碼字y后，進(jìn)行分析并偽造假認(rèn)證碼字y*，故可稱為已知密文偽造。若接收者接受y*為認(rèn)證碼字，則稱竄擾者攻擊成功。竄擾者可以自由地選擇最有利的攻擊方式。

竄擾者成功概率(接收者受騙概率)：

pd=max{pI，pS}(6—1—1)

pI：竄擾者采用模仿攻擊時(shí)最大可能的成功概率

ps：在代換攻擊時(shí)最大可能的成功概率。

完善認(rèn)證性(PerfectAuthentication)：令#{Y}、#{X}、#{K}分別表示密文空間、消息空間、密鑰空間中概率為非零的元素的個(gè)數(shù)。一般認(rèn)證編碼中#{Y}>#{X}，且認(rèn)證碼中元素個(gè)數(shù)#{Ak}#{X2022/11/237一、認(rèn)證與認(rèn)證系統(tǒng)代換偽造(Substitu一、認(rèn)證與認(rèn)證系統(tǒng)對每個(gè)kK，至少有#{X}個(gè)不同的密文使p(Y=y|K=k)≠0。若對手采用模仿偽造策略，完全隨機(jī)地以非零概率從Y中選出一個(gè)作為偽造密文(認(rèn)證碼字)送給接收者，則其成功的概率有(6—1—2)要安全性高，即要pI小，需有#{Y}>>#{X}。由于#{X}>0，要求完全保護(hù)，即要pI=0是不可能實(shí)現(xiàn)的。而且可以證明，要求式(6-1-2)等號成立的充要條件是：對任一kK，都恰有#{Ak}>#{X}。這表明采用隨機(jī)密碼不能使上式等號成立。由于認(rèn)證系統(tǒng)不能實(shí)現(xiàn)完全保護(hù)，故將完善認(rèn)證定義為對給定認(rèn)證碼空間，能使受騙率pd最小的認(rèn)證系統(tǒng)(在此意義下，即使對#{Y}=#{X}時(shí)的平凡情況，此時(shí)pd=1，也有完善認(rèn)證可言)。2022/11/238一、認(rèn)證與認(rèn)證系統(tǒng)對每個(gè)kK，至少有#{X一、認(rèn)證與認(rèn)證系統(tǒng)若在最佳模仿策略下竄擾者只能隨機(jī)地選取一個(gè)yY，則有H(Y)=log#{Y}(6—1—3)而若在任一給定密鑰下，任一認(rèn)證碼字在認(rèn)證碼A中等概出現(xiàn)，則有H(Y|K)=log#{X}(6—1—4)對式(6-1-2)兩邊取對數(shù)可得

logpIlog#{X}－log#{Y}=－{H(Y)－H(Y|K)}=－I(Y；K)定理6-1-1認(rèn)證信道有l(wèi)ogpI－I(Y；K)(6—1—5)等號成立的充要條件為式(6-1-3)和(6-1-4)成立，且

logpd－I(Y；K)(6—1—6)等號成立的必要條件為式(6-1-3)和(6-1-4)成立。2022/11/239一、認(rèn)證與認(rèn)證系統(tǒng)若在最佳模仿策略下竄擾者只能隨一、認(rèn)證與認(rèn)證系統(tǒng)

Simmons稱式(6-1-6)為認(rèn)證信道的容量。利用信息量和熵的關(guān)系式易于得到下述幾個(gè)等價(jià)關(guān)系式。

定理6-2-2－I(Y；K)等價(jià)于下述關(guān)系式：

H(K|Y)－H(K)(6—1—7)

H(Y|K)－H(Y)(6—1—8)

H(XYK)－H(K)－H(Y)(6—1—9)

H(K|XY)－H(K)＋H(XY)－H(Y)(6—1—10)

H(K|XY)－H(K)＋H(X|Y)(6—1—11)

H(YK|X)－H(X)－H(K)－H(Y)(6—1—12)

H(YX|K)－H(Y)(6—1—13)

H(XK|Y)－H(K)(6—1—14)

H(Y|KX)＋H(X)－H(Y)(6—1—15)

2022/11/2310一、認(rèn)證與認(rèn)證系統(tǒng)Simmons稱式(6-1-6)一、認(rèn)證與認(rèn)證系統(tǒng)

定義6-1-2完善認(rèn)證是使式(6-1-6)等號成立的認(rèn)證系統(tǒng)。由式(6-1-6)可知，即使系統(tǒng)是完善的，要使pd小就必須使I(Y；K)大，也就是說使竄擾者從密文Y中可提取更多的密鑰信息！而由式(6-1-7)知，在極端情況下，當(dāng)H(K|Y)=0即竄擾者可從Y獲取有關(guān)密鑰的全部信息時(shí)有

logpd－H(K)(6—1—16)即有pd#{K}(6—1—17)這是一個(gè)平凡的下限。Gilbert等曾給出一個(gè)更強(qiáng)的下限。

定理6-1-3對具有保密的認(rèn)證(竄擾者不知信源狀態(tài))有

logpd－1/2H(K)(6—1—18)而對無保密的認(rèn)證(竄擾者知道信源狀態(tài))有2022/11/2311一、認(rèn)證與認(rèn)證系統(tǒng)定義6-1-2完善認(rèn)證是一、認(rèn)證與認(rèn)證系統(tǒng)

logpd－1/2{H(K)－H(XY)＋H(Y)}=－1/2{H(K)－H(X|Y)(6—1—19)

證明對具有保密性的認(rèn)證有

logpdmax{logpI，－H(K|Y)}(6—1—20)而對于無保密的認(rèn)證有

logpdmax{logpI，－H(K|XY)}(6—1—21)顯然max{logpI，－H(K|Y)1/2{logpI－H(K|Y)}(6—1—22)max{logpI，－H(K|XY)1/2{logpI－H(K|XY)(6—1—23)將式(6-1-7)代入式(6-1-22)中的pI，并將式(6-1-10)代入式(6-1-23)中的pI可分別得到：2022/11/2312一、認(rèn)證與認(rèn)證系統(tǒng)lo一、認(rèn)證與認(rèn)證系統(tǒng)logpd1/2{H(K|Y)－H(K)－H(K|Y)=－1/2H(K)和logpd1/2{H(K|XY)－H(K)＋H(XY)－H(Y)－H(K|XY)=1/2{H(K)－H(XY)+H(Y)或logpd1/2{H(K|XY)－H(K)＋H(X|Y)－H(K|XY)=1/2{H(K)－H(X|Y)}因?yàn)镠(K)log#{X}，且等號成立的充要條件是各密鑰等概，故有系：(6—1—24)

表達(dá)式(6—1—24)給出的條件簡稱為GMS限。由系理可知，對于任何無條件安全的認(rèn)證碼，為了實(shí)現(xiàn)pd安全性所需的碼(注意不是碼字)的數(shù)量或密鑰量至少為1/p2d量級。2022/11/2313一、認(rèn)證與認(rèn)證系統(tǒng)logpd1/2{H(K|Y)－H(一、認(rèn)證與認(rèn)證系統(tǒng)類似于保密系統(tǒng)的安全性，認(rèn)證系統(tǒng)的安全性也劃分為兩大類，即理論安全性和實(shí)際安全性。理論安全性又稱作無條件安全性，就是我們上面所討論的。它與竄擾者的計(jì)算能力或時(shí)間無關(guān)，也就是說竄擾者破譯體制所做的任何努力都不會優(yōu)于隨機(jī)試湊方式。際安全性是根據(jù)破譯認(rèn)證體制所需的計(jì)算量來評價(jià)其安全性的。如果破譯一個(gè)系統(tǒng)在原理上是可能的，但以所有已知的算法和現(xiàn)有的計(jì)算工具不可能完成所要求的計(jì)算量，就稱其為計(jì)算上安全的。如果能夠證明破譯某體制的困難性等價(jià)于解決某個(gè)數(shù)學(xué)難題，就稱其為可證明安全的，如RSA體制。這兩種安全性雖都是從計(jì)算量來考慮，但不盡相同，計(jì)算安全要算出或估計(jì)出破譯它的計(jì)算量下限，而可證明安全則要從理論上證明破譯它的計(jì)算量不低于解已知難題的計(jì)算量。2022/11/2314一、認(rèn)證與認(rèn)證系統(tǒng)類似于保密系統(tǒng)的安全性，認(rèn)證系統(tǒng)二、認(rèn)證碼構(gòu)造認(rèn)證碼使其接近或達(dá)到其性能下限。

對偶性：無條件安全認(rèn)證碼和糾錯(cuò)碼理論互為對偶。這兩者都需要引入多余數(shù)字，在信道中可傳送的序列集中只有一小部分用于傳信。這是認(rèn)證和糾錯(cuò)賴以實(shí)現(xiàn)的基本條件。糾錯(cuò)碼的目的是抗噪聲等干擾，要求將碼中各碼字配置得盡可能地散開(如最小漢明距離極大化)，以保證在干擾作用下所得到的接收序列與原來的碼字最接近。在最大似然譯碼時(shí)可以使平均譯碼錯(cuò)誤概率極小化。認(rèn)證碼的目的是防止偽造和受騙。對于發(fā)送的任何消息序列(或碼字)，竄擾者采用最佳策略所引入的代換或模擬偽造序列應(yīng)盡可能地散布于信道可傳送的序列集中。在認(rèn)證系統(tǒng)中，密鑰的作用類似于信道的干擾，在它們的控制下變換編碼規(guī)則，使造出的代表消息的碼字盡可能交義地配置，即將消息空間X最佳地散布于輸出空間(信道傳送序列集)Y之中，以使竄擾者在不知道密鑰情況下，偽造成功的概率極小化。2022/11/2315二、認(rèn)證碼構(gòu)造認(rèn)證碼使其接近或達(dá)到二、認(rèn)證碼例6-2-1令X={0,1}，Y={00,01,10,11}，K={0,1}。認(rèn)證碼如下表：

這種認(rèn)證編碼就是在消息xi后鏈接上密鑰ki，

yj=(xi||ki)(6—2—1)可將ki看作是對消息xi的簽字，或稱其為xi的認(rèn)證符(authenticator)。類似于系統(tǒng)糾錯(cuò)碼，這種認(rèn)證碼字的前面部分就是消息數(shù)字本身，因此它對消息本身是不保密的。yjxi01kt00100111012022/11/2316二、認(rèn)證碼例6-2-1令X={0,1}，Y={00二、認(rèn)證碼但其H(KY)=0，因而有I(Y;K)=1bit，由此可知有pI1/2。但對j，p(yj為認(rèn)證碼字)=1/2，故有pI=1/2，此為最小可能的取值。但當(dāng)竄擾者截獲到y(tǒng)j后，就會知道當(dāng)前所用密鑰下認(rèn)證碼的另一個(gè)碼字，因而總可用代換攻擊取得成功。所以，有。這一認(rèn)證方案無安全性可言。本例說明，代換攻擊較模仿攻擊更難于防范。

例6-2-2條件同例6-2-1，但K={00,01,11}。認(rèn)證碼如下表：xi

yj01001001110011011000011011kt2022/11/2317二、認(rèn)證碼但其H(KY)=0，因而有I(Y;K)二、認(rèn)證碼這種認(rèn)證碼仍是鏈接形式，即

yj=(xi||f(xi,kt))(6—2—2)式中，f(xi,kt)為給定kt下對于消息xi的認(rèn)證符。例6-2-1中的認(rèn)證符是其特例，即f(xi,kt)=kt。由于消息數(shù)字xi直接在信道中傳送，此編碼對消息本身不保密。對任一給定的yj，可能的密鑰有兩個(gè)，因而H(KY)=1bit，I(Y;K)=H(K)－H(KY)=2－1=1bit。由此可知有。一旦觀察到y(tǒng)j，例如yj=(0,0)，竄擾者將有兩種可能的碼字(10)或(11)可作為代換偽造的備選者。而對于合法的接收者，由于他知道密鑰而可惟一地確定其中之一。因此pS=1/2，故此例下有pd=max(pI

,pd)=pI=pS=1/2。不管X的統(tǒng)計(jì)特性如何，此碼都是完善的。2022/11/2318二、認(rèn)證碼這種認(rèn)證碼仍是鏈接形式，即2022/10/二、認(rèn)證碼

例6-2-3條件同例6-2-2。認(rèn)證碼如下表：

此碼不再是系統(tǒng)形式碼字,yj=f(xi,kt)（6—2—3）的前一部分，不再是消息數(shù)字，而是經(jīng)密鑰作用后的密文。對所有i,j,p(yj||xj)=1/4，因此，系統(tǒng)提供了完善保密性。又H(KY)=1bit，H(K)=2bit，I(Y;K)=1bit，故有pI=1/2。但是H(KY)=0，竄擾者一旦觀察到y(tǒng)j就可成功地選擇其補(bǔ)作為代換偽造碼字，因此，ps=1=pd。這種認(rèn)證碼在代換攻擊下無安全性可言。yjxi01kt0011011010011100000110112022/11/2319二、認(rèn)證碼例6-2-3條件同例6-2-2。認(rèn)證二、認(rèn)證碼例6-2-4

條件同例6-2-2，認(rèn)證碼如下表：

此認(rèn)證碼為非系統(tǒng)形式，且對消息數(shù)字可提供完善保密性。又H(K)=2bit，H(K|Y)=1bit，故I(Y;Z)=1bit。而且對所有j，p(yj為認(rèn)證碼字)=1/2，故pI=1/2。若已知yj，例如yj=(00)，竄擾者有兩種可能的選擇：(10)或(01)，分別與kt=(00)和(01)對應(yīng)，即其成功概率或?yàn)閜(x=1)(kt=(00)時(shí))，或?yàn)閜(x=0)(kt=(01)時(shí)。因此，pS1/2，當(dāng)且僅當(dāng)p(x=1)=p(x=0)=1/2時(shí)，有pS=1/2，此時(shí)pd=pI=pS=1/2，達(dá)到完善認(rèn)證?？梢姡⒌雀攀菍?shí)現(xiàn)完善認(rèn)證的條件之一。yjxi01kt0010010011011011000110112022/11/2320二、認(rèn)證碼例6-2-4條件同例6-2-2，認(rèn)二、認(rèn)證碼由上述幾個(gè)簡單的例子可以看出，在同樣的編碼參數(shù)下，不同的編碼方案的保密和認(rèn)證性能相差很大，研究認(rèn)證編碼理論可為認(rèn)證系統(tǒng)設(shè)計(jì)提供有效工具。上一節(jié)給出了構(gòu)造完善認(rèn)證體制的理論。從式(6-1-2)知，要pI小，需選#{Ak}小，#{Y}要大。而#{Ak}的最小可能值為#{X}。而且我們已知，實(shí)現(xiàn)完善認(rèn)證的必要條件是對所有k，#{Ak}相等。

Gilbert等利用區(qū)組設(shè)計(jì)構(gòu)造了一批較有效的可使pd達(dá)到或接近式(6-1-3)下限的無條件認(rèn)證碼。Simmons對各種認(rèn)證碼進(jìn)行了分類，并將例6-2-2的完善認(rèn)證碼進(jìn)行了推廣，利用正交陣列構(gòu)造認(rèn)證碼。Stinson、萬哲先等利用此法得到了一些新的認(rèn)證碼，認(rèn)證碼的研究還剛剛開始，遠(yuǎn)沒有糾錯(cuò)碼那么成熟，本節(jié)也只介紹了一些基本概念。。2022/11/2321二、認(rèn)證碼由上述幾個(gè)簡單的例子可以看出，三、雜湊函數(shù)

雜湊(Hash)函數(shù)：將任意長的數(shù)字串M映射成一個(gè)較短的定長輸出數(shù)字串H的函數(shù)，以h表示，h(M)易于計(jì)算，稱H=h(M)為M的雜湊值，也稱雜湊碼、雜湊結(jié)果等或簡稱雜湊。

特點(diǎn)：H打上了輸入數(shù)字串的烙印，為數(shù)字指紋(DigitalFingerPrint)。h是多對一映射，因此我們不能從H求出原來的M，但可以驗(yàn)證任一給定序列M’是否與M有相同的雜湊值。

分類：

密碼雜湊函數(shù)，有密鑰控制，以h(k,M)表示。其雜湊值不僅與輸入有關(guān)，而且與密鑰有關(guān)，只有持此密鑰的人才能計(jì)算出相應(yīng)的雜湊值，因而具有身份驗(yàn)證功能，如消息認(rèn)證碼MAC[ANSIX9.9]。雜湊值也稱作認(rèn)證符(Authenticator)或認(rèn)證碼。它要滿足各種安全性要求，密碼雜湊函數(shù)在現(xiàn)在密碼學(xué)中有重要作用。2022/11/2322三、雜湊函數(shù)雜湊(Hash)函數(shù)：將任意長的數(shù)字串M映三、雜湊函數(shù)

一般雜湊函數(shù)，無密鑰控制。無密鑰控制的單向雜湊函數(shù)，其雜湊值只是輸入字串的函數(shù)，任何人都可以計(jì)算，因而不具有身份認(rèn)證功能，只用于檢測接收數(shù)據(jù)的完整性，如竄改檢測碼MDC，用于非密碼計(jì)算機(jī)應(yīng)用中。

應(yīng)用：在密碼學(xué)和數(shù)據(jù)安全技術(shù)中，它是實(shí)現(xiàn)有效、安全可靠數(shù)字簽字和認(rèn)證的重要工具，是安全認(rèn)證協(xié)議中的重要模塊。

別名：壓縮(Compression)函數(shù)、緊縮(Contraction)函數(shù)、數(shù)據(jù)認(rèn)證碼(DataAuthenticationCode)、消息摘要(MessageDigest)、數(shù)字指紋、數(shù)據(jù)完整性校驗(yàn)(DataIntegityCheck)、密碼檢驗(yàn)和(CryptographicCheckSum)、消息認(rèn)證碼MAC(MessageAuthenticationCode)、竄改檢測碼MDC(ManipulationDetectionCode)等。2022/11/2323三、雜湊函數(shù)一般雜湊函數(shù)，無密鑰控制。無密鑰三、雜湊函數(shù)

1.單向雜湊函數(shù)密碼學(xué)中所用的雜湊函數(shù)必須滿足安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。為此，必須深入研究雜湊函數(shù)的性質(zhì)，從中找出能滿足密碼學(xué)需要的雜湊函數(shù)。首先我們引入一些基本概念。

1.單向雜湊函數(shù)

定義6-2-1若雜湊函數(shù)h為單向函數(shù)，則稱其為單向雜湊函數(shù)。顯然，對一個(gè)單向雜湊函數(shù)h，由M計(jì)算H=h(M)是容易的，但要產(chǎn)生一個(gè)M＇使h(M＇)等于給定的雜湊值H是件難事。

定義6-2-2弱單向雜湊函數(shù)：若單向雜湊函數(shù)h，對任意給定M的雜湊值H=h(M)下，找一M‘使h(M’)=H在計(jì)算上不可行。2022/11/2324三、雜湊函數(shù)

1.單向雜湊函數(shù)密碼學(xué)中所三、雜湊函數(shù)

2.雜湊函數(shù)的安全性定義6-2-3強(qiáng)單向雜湊函數(shù)：對單向雜湊函數(shù)h，若要找任意一對輸入M1,M2，M1

M2，使h(M1)=h(M2)在計(jì)算上不可行。無碰撞(Collision-free)性：弱單向雜湊，是在給定M下，考察與特定M的無碰撞性；而強(qiáng)單向雜湊函數(shù)是考察輸入集中任意兩個(gè)元素的無碰撞性。顯然，對于給定的輸入數(shù)字串的集合，后一種碰撞要容易實(shí)現(xiàn)。因?yàn)閺南旅嬉榻B的生日悖論知，在N個(gè)元素的集中，給定M找與M相匹配的M＇的概率要比從N中任取一對元素M，Ｍ＇相匹配的概率小得多。

2.雜湊函數(shù)的安全性：雜湊函數(shù)的安全性取決于其抗擊各種攻擊的能力，對手的目標(biāo)是找到兩個(gè)不同消息映射為同一雜湊值。一般假定對手知道雜湊算法，采用選擇明文攻擊法。2022/11/2325三、雜湊函數(shù)

2.雜湊函數(shù)的安全性定義6-2-三、雜湊函數(shù)

2.雜湊函數(shù)的安全性對雜湊函數(shù)的基本攻擊方法：窮舉攻擊法：給定h=h(H0,M)，其中H0為初值，攻擊者在所有可能的M中尋求有利于攻擊者的M’’，使h(H0,M’)=h(H0,M)，由于限定了目標(biāo)h(H0,M)來尋找h(H0,M’)，這種攻擊法稱為目標(biāo)攻擊。若對算法的初值H0不限定，使其h(H0＇,M)等于h(H0,M’)，則稱這種攻擊法為自由起始目標(biāo)攻擊。

生日攻擊：這種攻擊法不涉及雜湊算法的結(jié)構(gòu)，可用于攻擊任何雜湊算法。強(qiáng)雜湊函數(shù)正是基于生日悖論一類的攻擊法定義的。窮舉和生日攻擊都屬選擇明文攻擊。生日攻擊給定初值H0，尋找MM，使h(H0,M’)=h(H0,M)，也可對初始值H0不加限制，即尋找H0’,M’使h(H0’,M’)=h(H0,M)。2022/11/2326三、雜湊函數(shù)

2.雜湊函數(shù)的安全性對雜湊函數(shù)三、雜湊函數(shù)

2.雜湊函數(shù)的安全性生日悖論：在一個(gè)會場參加會議的人中，找一個(gè)與某人生日相同的概率超過0.5時(shí)，所需參會人員為183人。但要問使參會人員中至少有兩個(gè)同日生的概率超過0.5的參會人數(shù)僅為23人。這是因?yàn)?，對于與某個(gè)已知生日的人同日生的概率為1/365，若房中有t人，則至少找到一人與此人同日生的概率為。易于解出，當(dāng)t183時(shí)可使p>0.5。

第一個(gè)人在特定日生的概率為1/365，而第二人不在該日生的概率為，類似地第三人與前兩位不同日生的概率為，以此類推，t個(gè)人都不同時(shí)生日概率為，因此，至少有兩人于同日生的概率為

解之，當(dāng)t23時(shí)，p>0.5。對于n比特雜湊值的生日攻擊，由上式可計(jì)算出，當(dāng)進(jìn)行2n/2次的選擇明文攻擊下成功的概率將超過0.63。

2022/11/2327三、雜湊函數(shù)

2.雜湊函數(shù)的安全性生日悖論：在三、雜湊函數(shù)

2.雜湊函數(shù)的安全性例6-2-1

令h是一個(gè)雜湊值為80bit的單向雜湊函數(shù)。給定消息M和H(M)下，假定280個(gè)雜湊值等概，則對M有Pr{h(M)}=2-80。今進(jìn)行k次試驗(yàn)，找到一個(gè)M’能使h(M＇)=h(M)的概率為1-(1-2-80)k。因此，當(dāng)進(jìn)行k=274試驗(yàn)時(shí)，找到滿足要求的M’的概率近于1。若在不限定雜湊值的情況下，在消息集中找出一對消息M和M使h(M)=h(M)，根據(jù)生日悖論所需的試驗(yàn)次數(shù)，至少為1.17×240<2×1012。利用大型計(jì)算機(jī)，至多用幾天時(shí)間就能實(shí)現(xiàn)?？梢姡s湊值僅為80bit的雜湊函數(shù)不是強(qiáng)雜湊函數(shù)。因此，能抗擊生日攻擊的雜湊函數(shù)值至少為128bit。

中途相遇攻擊法，這是一種選擇明文/密文的攻擊。用于迭代和級連分組密碼體制，其概率計(jì)算同生日攻擊。由于雜湊算法也可用迭代和級連結(jié)構(gòu)，因而設(shè)計(jì)算法時(shí)必須能抗擊這類攻擊。對于多級級連方案所需攻擊次數(shù)為O(10p2n/2)，其中p是級連級數(shù)。2022/11/2328三、雜湊函數(shù)

2.雜湊函數(shù)的安全性例6-2-1三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系

雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼都是利用冗余度。

線性分組檢錯(cuò)碼是在長為L的消息數(shù)字上增加n比特校驗(yàn)位，構(gòu)成一個(gè)長為L＋n(bit)線性碼。GF(2)上L＋n維線性空間中的L維子空間就是這類線性分組檢錯(cuò)碼的碼空間。當(dāng)碼字在傳輸過程中被竄擾，若結(jié)果不屬于碼空間，收端通過對n個(gè)一致檢驗(yàn)關(guān)系的檢驗(yàn)可以實(shí)現(xiàn)檢錯(cuò)。一個(gè)好的檢錯(cuò)線性碼在于使不可檢錯(cuò)概率極小化，其最佳碼的不可檢錯(cuò)上限為

pd2-n[1－(1－p)n](6—3—1)式中p是信道誤碼率。在抗主動攻擊下，可認(rèn)為p=1/2。而有

pd2-n(6—3—2)線性分組檢錯(cuò)碼是一種MDC雜湊，可作為數(shù)據(jù)完整性檢驗(yàn)，但不能作為身份認(rèn)證。2022/11/2329三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系

二元認(rèn)證碼是將長為L的消息bit序列映射為L＋nbit序列的編碼。在不同密鑰下，同一消息序列被映射為不同的碼序列。為了實(shí)現(xiàn)無條件安全認(rèn)證，希望在密鑰控制下能將消息所對應(yīng)的碼字在盡可能交叉地配置，使不知密鑰的竄擾者成功的概率極小化。模仿偽造成功概率(6—3—3)此與最佳線性檢錯(cuò)碼的不可檢錯(cuò)概率的上限一致。竄擾成功的概率限由(6-1-3)有(6—3—4)

雜湊函數(shù)可以看作是一種非線性認(rèn)證碼，將Lbit輸入消息M變成碼字M||H，其中H是M的雜湊值，一般為nbit。故碼長為L＋n(bit)。2022/11/2330三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系這種非線性碼可能數(shù)極大，即相應(yīng)的密鑰空間K可以很大，但從式(6-3-3)和式(6-3-4)式可以看出#{K}>22n是無作用的。由此可以得出一個(gè)重要結(jié)論，即對于nbit雜湊值下，選擇密鑰比特?cái)?shù)大于2nbit是無意義的。這對于設(shè)計(jì)雜湊算法有重要意義。這是將雜湊函數(shù)看作是一種認(rèn)證編碼給我們的啟示。對于線性分組檢測碼來說，其編碼規(guī)則是固定的。因而#{K}=1。雖然其不可檢錯(cuò)誤的概率上界為2-n，但Pd的下界為1?？梢娝荒芸箵舾Z擾者的攻擊。

2022/11/2331三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系雜湊函數(shù)壓縮輸入數(shù)字串與認(rèn)證編碼之間的差別在于，后者是對固定長Lbits進(jìn)行編碼成L＋nbits碼字，而前者對輸入字串長度未加限制。一般Lnbit，且當(dāng)L不是n的整數(shù)倍時(shí)，采用填充辦法湊成L/n倍(·表示取不小于括號內(nèi)數(shù)的最小整數(shù))。雖然式(6-3-3)給出的對任意L取值模仿攻擊成功概率下限都是2-n。但對雜湊函數(shù)來說，輸入空間的選擇遠(yuǎn)大于認(rèn)證碼的情況。為了減小碰撞，通常都將輸入消息數(shù)字串長度作為參數(shù)納入最后一個(gè)分段中，這樣攻擊者在試圖找到偽消息M’與發(fā)送消息M的雜湊值一樣時(shí)，必須使M’的長度和M的長度一致才合法，從而大大增加了攻擊的難度。這種技術(shù)由Merkle和Damg?rd等提出，稱作MD強(qiáng)化技術(shù)。Damg?rd等證明經(jīng)過MD強(qiáng)化后，雜湊算法抗自由起始攻擊的強(qiáng)度等價(jià)于迭代函數(shù)的強(qiáng)度。

2022/11/2332三、雜湊函數(shù)

3.雜湊函數(shù)、認(rèn)證碼與檢錯(cuò)碼的關(guān)系三、雜湊函數(shù)

4.分組迭代單向雜湊算法的層次結(jié)構(gòu)

4.分組迭代單向雜湊算法的層次結(jié)構(gòu)要想將不限定長度的輸入數(shù)據(jù)壓縮成定長輸出的雜湊值，不可能設(shè)計(jì)一種邏輯電路使其一次到位。實(shí)際中，總是先將輸入數(shù)字串劃分成固定長的段，如m比特段，而后將此mbit映射成nbit，稱完成此映射的函數(shù)為迭代函數(shù)。采用類似于分組密文反饋的模式進(jìn)行對一段mbit輸入做類似映射，以此類推，直到全部輸入數(shù)字串完全做完，以最后的輸出值作為整個(gè)輸入的雜湊值。類似于分組密碼，當(dāng)輸入數(shù)字串不是m的整數(shù)倍時(shí)，可采用填充等方法處理。

2022/11/2333三、雜湊函數(shù)

4.分組迭代單向雜湊算法的層次結(jié)構(gòu)三、雜湊函數(shù)

4.分組迭代單向雜湊算法的層次結(jié)構(gòu)

mbit到nbit的分組映射或迭代函數(shù)的三種選擇：

m>n。有數(shù)據(jù)壓縮，例如，MD4，MD5，SHA等算法。是不可逆映射。

m=n。無數(shù)據(jù)壓縮，亦無數(shù)據(jù)擴(kuò)展，通常分組密碼采用這類。此時(shí)輸入到輸出是一種隨機(jī)映射，在已知密鑰下是可逆的。利用分組密碼構(gòu)造的雜湊算法多屬此類。在不知道密鑰下，分組密碼實(shí)質(zhì)上是一個(gè)單向函數(shù)(或更確切地說是陷門單向函數(shù))。

m<n。有數(shù)據(jù)擴(kuò)展的映射。認(rèn)證碼屬于此類。當(dāng)然迭代函數(shù)設(shè)計(jì)中，也可采用上述組合來實(shí)現(xiàn)，如采用將mbit先進(jìn)行擴(kuò)展，而后再逐步經(jīng)過幾次壓縮實(shí)現(xiàn)理想的密碼特性，如Universal2函數(shù)的構(gòu)造法。2022/11/2334三、雜湊函數(shù)

4.分組迭代單向雜湊算法的層次結(jié)構(gòu)三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法一個(gè)mbit到nbit的迭代函數(shù)以E表示，一般E又都是通過基本輪函數(shù)的多輪迭代實(shí)現(xiàn)的，如分組密碼。因此，像分組密碼一樣輪函數(shù)的設(shè)計(jì)是雜湊算法設(shè)計(jì)的核心。在迭代計(jì)算雜湊值時(shí)，為了隨機(jī)化輸入消息，多采用一個(gè)隨機(jī)化初始向量IV(initialVector)。它可以是已知的、或隨密鑰改變、或作為前綴(prefix)加在消息數(shù)字之前，以H0表示。

5.迭代雜湊函數(shù)的構(gòu)造方法安全迭代函數(shù)E消息M劃分成組M1,M2,…,Mi,…,Mt。選定密鑰為K，

H0為初始向量IV，2022/11/2335三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法

Rabin法：H0=IV；

Hi=E(Mi,Hi-1)i=1,…,t；H(M)=Ht。

密碼分組鏈接(CBC)法：H0=IV；

Hi=E(K,MiHi-1)i=1,2,…,t；H(M)=Ht。ANSIX9.9[1986]、ANSIX9.19、ISO8731-1、ISO9797以及澳大利亞標(biāo)準(zhǔn)都采用了這類CBC-MAC方案。Ohta等對此法進(jìn)行了差分分析。密碼反饋(CFB)法：Hi=E(K,Hi-1Mi)，i=1,2,…,t；H(M)=Ht

4.組合明/密文鏈接法：Mt+1=IV；

Hi=E(K,MiMi-1Hi-1)i=1,2,…,t；H(M)=Ht+1。

5．修正Daveis-Meyer法：

H0=IV；

Hi=E(Hi-1,Mi,Hi-1)(Hi和Mi共同作為密鑰)2022/11/2336三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法若數(shù)據(jù)分組長和密鑰長度相等則可用B.Preneel總結(jié)的下述12種基本方式構(gòu)造的分組迭代雜湊函數(shù)。令E是迭代函數(shù)，它可以是一種分組加密算法，E(K,X)，K是密鑰，X是輸入數(shù)據(jù)組或某種壓縮算法。令消息分組為M1,…,Mi,…,H0=I為初始值。(1)Hi=E(Mi,Hi-1)Hi-1

(2)Hi=E(Hi-1,Mi)MiHi-1

(3)Hi=E(Hi-1,MiHi-1)Mi

(4)Hi=E(Hi-1,MiHi-1)MiHi-1

(5)Hi=E(Hi-1,Mi)Mi(6)Hi=E(Mi,MiHi-1)MiHi-1

2022/11/2337三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法

(7)Hi=E(Mi,Hi-1)MiHi-1(N-hash算法，采用128bitFEAL用此式實(shí)現(xiàn)，但安全性可疑(8)Hi=E(Mi,MiHi-1)Hi-1

(9)Hi=E(MiHi-1,Mi)Mi

(10)Hi=E(MiHi-1,Hi-1,)Hi-1[Brown等1990](11)Hi=E(MiHi-1,Mi)Hi-1

(12)Hi=E(MiHi-1,Hi-1)Mi

如果原來的加密算法是安全的，則上述12種方案給出的雜湊函數(shù)，對于目標(biāo)攻擊的計(jì)算復(fù)雜度為O(2n)，對于中途相遇攻擊的計(jì)算復(fù)雜度為O(2n/2)，因而當(dāng)大于128bit時(shí)也是安全的。2022/11/2338三、雜湊函數(shù)

5.迭代雜湊函數(shù)的構(gòu)造方法(7)三、雜湊函數(shù)

6.由n長bit雜湊算法擴(kuò)展為2nbit雜湊的算法

6.由n長bit雜湊算法擴(kuò)展為2nbit雜湊的算法現(xiàn)有大多數(shù)分組密碼算法，輸入、輸出數(shù)據(jù)多為64bit。作為雜湊算法，都經(jīng)受不了生日攻擊。為此要求雜湊值至少為128bit才能保證安全性。如何從64bit雜湊算法，擴(kuò)展為128bit或更大的雜湊算法，已有不少方案提出。Knudsen[1984]曾對其中一些重要方案，如MDC-2、平行DM、PBGV/LOKI擴(kuò)散等進(jìn)行了分析，表明以分組密碼為基礎(chǔ)構(gòu)造快速而安全的雜湊函數(shù)是很困難的。講義中列舉了8種方案。2022/11/2339三、雜湊函數(shù)

6.由n長bit雜湊算法擴(kuò)展為2nbi三、雜湊函數(shù)

7.基本迭代函數(shù)的選擇

7.基本迭代函數(shù)的選擇：迭代函數(shù)是雜湊函數(shù)的核心，有了安全而有效的迭代函數(shù)，就可用前述的迭代結(jié)構(gòu)構(gòu)造安全雜湊函數(shù)。講義中列出10種構(gòu)造的迭代函數(shù)方法(1)將分組密碼算法作為迭代函數(shù)(2)用RSA來構(gòu)造迭代函數(shù)(3)背包法(4)基于胞元自動機(jī)(Cellularautomata)的算法

(5)專門設(shè)計(jì)的具有數(shù)據(jù)壓縮的單向迭代函數(shù)(6)矩陣單向迭代函數(shù)

2022/11/2340三、雜湊函數(shù)

7.基本迭代函數(shù)的選擇7.基本迭代三、雜湊函數(shù)

7.基本迭代函數(shù)的選擇

(7)以FFT構(gòu)造單向迭代函數(shù)(8)以有限域中元素的指數(shù)運(yùn)算構(gòu)造迭代函數(shù)

(9)

IBC-HASH算法(10)用流密碼構(gòu)造雜湊函數(shù)

2022/11/2341三、雜湊函數(shù)

7.基本迭代函數(shù)的選擇(7)以FF三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式雜湊算法可與加密及數(shù)字簽字結(jié)合使用，實(shí)現(xiàn)系統(tǒng)的有效、安全、保密與認(rèn)證。其基本方式如圖6-3-1中所示。

(a)發(fā)端A

收端B

M

Ek[M||h(M)]M’

h(M’)MUXED

h

h

k

k比較

h(M)判決

h(M)輸出圖中的(a)部分，發(fā)端A將消息M與其雜湊值h(M)鏈接，以單鑰體制加密，后送至收端B。收端用與發(fā)端共享密鑰解密后得M’和h(M)，而后將M送入雜湊變換器計(jì)算出h(M’)，并通過比較完成對消息M的認(rèn)證，從而提供了保密和認(rèn)證。

2022/11/2342三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式雜三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式圖中(b)部分，消息M不保密，只對消息的雜湊值進(jìn)行加解密變換，它只提供認(rèn)證。M

M||Ek[h(M)]M’

h(M’)(b)k

MUXDMXh

判決

h

E

k

比較輸出

h(M)Ek[h(M)]Ek[h(M)]D

h(M)

圖中(c)部分，發(fā)端A采用雙鑰體制，用A的秘密鑰ksa對雜湊值進(jìn)行簽字得Eksa[h(M)]，而后與M鏈接發(fā)出。收端則用A的公鑰對Eksa[h(M)]解密得到h(M)。再與收端自己由接收消息M’計(jì)算得到的h(M’)進(jìn)行比較實(shí)現(xiàn)認(rèn)證。本方案提供了認(rèn)證和數(shù)字簽字。稱作簽字一雜湊方案(Signature-hashingScheme)。這一方案用對消息M的雜湊值簽字來代替對任意長消息M本身的簽字。大大提高了簽字的速度和有效性。2022/11/2343三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式圖中(b三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式圖中(d)部分是在(c)的基礎(chǔ)上加了單鑰加密保護(hù)，可提供認(rèn)證、數(shù)字簽字和保密。M

M||Eksa[k(M)]M’

h(M’)(c)ksa

MUX

DMX

h

判決輸出

h

Ekpa

比較

h(M)Eksa[h(M)]Eksa[h(M)]D

h(M)

M

Ek[M||Eksa[h(M)]]M’

h(M’)(d)ks

MUX

E

D

DMX

h

判決

h

E

k

k

kpa

比較輸出

h(M)Eksa[h(M)]Eksa[h(M)]D

h(M)2022/11/2344三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式圖中(e)部分是在h的運(yùn)算中增加了通信雙方共享的秘密值S，加大了對手攻擊的困難性。它僅提供認(rèn)證。圖中(f)部分是在(e)的基礎(chǔ)上加了單鑰加密的保護(hù)，可提供保密和認(rèn)證。在上述方案中雜湊值都是由明文，而不是由密文計(jì)算的，這對于實(shí)用較方便。

M

M||h(M||s)M’

h(M’||s)(e)MUX

DMXsh

判決輸出

sMUX

h

比較

h(M)h(M||s)M

Ek[M||h(M||s)]M’

h(M’||s)(f)MUX

E

D

DMX

s

h

判決

s

MUX

h

k

k

比較輸出

h(M)h(M||s)h(M||s)

圖6-3-1應(yīng)用迭代雜湊函數(shù)的基本方式2022/11/2345三、雜湊函數(shù)

8.應(yīng)用雜湊函數(shù)的基本方式四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論安全的單向迭代函數(shù)是構(gòu)造安全消息雜湊值的核心和基礎(chǔ)。有了好的單向迭代函數(shù)，就可以利用6-3節(jié)中給出的迭代方式形成雜湊值了。為了抗擊生日和中途相遇攻擊，雜湊值至少應(yīng)為128bit。從實(shí)際應(yīng)用出發(fā)，要求雜湊算法快速、易于實(shí)現(xiàn)。滿足安全性要求，從理論上看最重要的有兩點(diǎn)：一是函數(shù)的單向性，二是函數(shù)映射的隨機(jī)性。

1.單向性。單向性保證了求逆的困難性，這不僅對密碼體制有決定意義，而且對雜湊函數(shù)設(shè)計(jì)也是一個(gè)基本條件。不具有單向性的函數(shù)是不能作認(rèn)證用的。一個(gè)函數(shù)的單向性，如果求逆的困難性超過O(264)，則可認(rèn)為此函數(shù)為計(jì)算復(fù)雜度意義下的單向函數(shù)。2022/11/2346四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論安全的單向迭代函數(shù)是構(gòu)四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論雜湊函數(shù)如果生日攻擊下的難度為O(264)，則可認(rèn)為是無碰撞的。函數(shù)的單向性和無碰撞性的關(guān)系如何？Rompel[1990]證明了一個(gè)重要結(jié)果，即無碰撞函數(shù)存在的充要條件是單向函數(shù)的存在。但這是否就等價(jià)于函數(shù)的單向性函數(shù)的碰撞性，還不清楚。

2.偽隨機(jī)性。迭代函數(shù)是一種映射，如果能通過某種可判定的檢驗(yàn)邏輯驗(yàn)證隨機(jī)性，則稱其為偽隨機(jī)映射。已經(jīng)證明若要迭代函數(shù)能抗擊生日攻擊，則它必須是偽隨機(jī)映射函數(shù)。如果偽隨機(jī)性迭代函數(shù)的逆也是偽隨機(jī)的，就稱其為超偽隨機(jī)函數(shù)。2022/11/2347四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論雜湊函數(shù)如果生四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論已經(jīng)證明要迭代函數(shù)能抗擊中途相遇攻擊，它必須是超偽隨機(jī)的。這個(gè)結(jié)果告訴我們超偽隨機(jī)性函數(shù)作為迭代函數(shù)才能抗擊中途相遇攻擊。已經(jīng)證明了一些特定結(jié)構(gòu)的迭代函數(shù)的偽隨機(jī)性和超偽隨機(jī)性。從而可用來構(gòu)造安全迭代函數(shù)。

3.抗差分攻擊能力?？梢杂貌罘址治鰜砉舻瘮?shù)。因此，要求在構(gòu)造雜湊算法的迭代函數(shù)時(shí)，必須使其能經(jīng)受此類攻擊。

4.非線性性。類似于分組密碼，還有許多性質(zhì)影響安全性。如雪崩特性、高階相關(guān)免疫性等等。

2022/11/2348四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論已經(jīng)證明要迭代四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論對雜湊函數(shù)來說。主要要求是能夠提供認(rèn)證和抗擊生日及中途相遇碰撞能力。因此，函數(shù)的單向性和偽隨機(jī)及超偽隨機(jī)性是最根本的要求。如何構(gòu)造具有偽隨機(jī)性和超偽隨機(jī)性的函數(shù)，它們的結(jié)構(gòu)特點(diǎn)等是雜湊函數(shù)理論的核心。雖然單向雜湊函數(shù)和分組密碼設(shè)計(jì)上有很多相似的要求，但一個(gè)好的單向雜湊函數(shù)未必就是一個(gè)安全的分組加密算法，反之亦然，因?yàn)閮烧咭蟛灰粯?。例如，線性攻擊對單向雜湊函數(shù)沒有太大意義，有些單向雜湊函數(shù)如SHA可有線性特性，但并不影響其安全性，但用于消息加密則不能保證安全性。如前所述，對雜湊迭代函數(shù)而言，能抵抗生日和中途相遇碰撞攻擊是本質(zhì)的要求，但一個(gè)安全的分組密碼算法未必能承受這類攻擊。2022/11/2349四、單向迭代雜湊函數(shù)的設(shè)計(jì)理論對雜湊函數(shù)來說五、

MD-5雜湊算法

RonRivest于1990年提出MD-4雜湊算法,特別適于軟、硬件快速實(shí)現(xiàn)。輸入消息可任意長，壓縮后輸出為128bits。MD-5是MD-4的改進(jìn)形式。下面介紹MD-5算法。1.算法步驟（參看圖6-5-1）(1)

對明文輸入按512bit分組，最后要填充使其成為512bit的整數(shù)倍，且最后一組的后64bit用來表示消息長在mod264下的值K，故填充位數(shù)為1～512

bit，填充數(shù)字圖樣為(100…0)，得Y0,Y1,…，YL-1。其中，Yl為512

bit，即16個(gè)長為32bit的字，按字計(jì)消息長為N=L×16。(2)每輪輸出為128bit，可用下述4個(gè)32

bits字表示：A，B，C，D。其初始存數(shù)以十六進(jìn)制表示為：A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210。2022/11/2350五、MD-5雜湊算法RonRivest于1990五、MD-5雜湊算法

(3)HMD5的運(yùn)算，對512bit(16-字)組進(jìn)行運(yùn)算，Yq表示輸入的第q組512

bit數(shù)據(jù)，在各輪中參加運(yùn)算。T[1,…,64]為64個(gè)元素表，分四組參與不同輪的計(jì)算。T[i]為232×abs(Sine(i))的整數(shù)部分，i是弧度。T[i]可用32bit二元數(shù)表示，T是32bit隨機(jī)數(shù)源。

MD-5是四輪運(yùn)算，各輪邏輯函數(shù)不同。每輪又要進(jìn)行16步迭代運(yùn)算，4輪共需64步完成。每步完成（參看圖6-5-2）。a

b＋CLSS(a＋g(B,C,D)＋X[k]＋T[i])其中

a,b,c,d=緩存器中的四個(gè)字，按特定次序變化。

g=基本邏輯函數(shù)F,G,H,I中之一，算法的每一輪用其中之一。

2022/11/2351五、MD-5雜湊算法(3)HMD5的運(yùn)算，對51

MDq，128

Yq512A

B

C

D32

ABCD＂fF(ABCD,Yq,T[1…16])

A

B

C

D

ABCD＂fG(ABCD,Yq,T[17…32])

A

B

C

D

ABCD＂fH(ABCD,Yq,T[33…48])

A

B

C

D

ABCD＂fI(ABCD,Yq,T[49…64])+++++：mod232圖6-5-1MD-5的一個(gè)

MDq+1128512-bit組的處理2022/11/2352

a

b

c

d