新編密碼學(xué) 課件 第6章 Hash函數(shù)

6.1Hash函數(shù)的基本概念

6.2迭代的Hash函數(shù)

6.3MD5算法與SHA-1算法

6.4SM3算法6.1Hash函數(shù)的基本概念數(shù)據(jù)的完整性是指數(shù)據(jù)從發(fā)送方產(chǎn)生,經(jīng)過(guò)傳輸或存儲(chǔ)以后,沒(méi)有被以未授權(quán)的方式修改的性質(zhì)。密碼學(xué)中的Hash函數(shù)在現(xiàn)代密碼學(xué)中扮演著重要的角色,該函數(shù)雖然與計(jì)算機(jī)應(yīng)用領(lǐng)域中的Hash函數(shù)有關(guān),但兩者之間存在著重要的差別。計(jì)算機(jī)應(yīng)用領(lǐng)域中的Hash函數(shù)(也稱散列函數(shù))是一個(gè)將任意長(zhǎng)度的消息序列映射為較短的、固定長(zhǎng)度的值的函數(shù)。密碼學(xué)上的Hash函數(shù)能夠保障數(shù)據(jù)的完整性,它通常被用來(lái)構(gòu)造數(shù)據(jù)的“指紋”(即函數(shù)值),當(dāng)被檢驗(yàn)的數(shù)據(jù)發(fā)生改變時(shí),對(duì)應(yīng)的“指紋”信息也發(fā)生變化。這樣,即使數(shù)據(jù)被存儲(chǔ)在不安全的地方,我們也可以通過(guò)數(shù)據(jù)的“指紋”信息來(lái)檢測(cè)數(shù)據(jù)的完整性。設(shè)H是一個(gè)Hash函數(shù),x是消息,不妨假設(shè)x是任意長(zhǎng)度的二元序列,相應(yīng)的“指紋”定義為y=H(x),Hash函數(shù)值通常也稱為消息摘要(MessageDigest)。一般要求消息摘要是固定長(zhǎng)度的二元序列。如果消息x被修改為x',則可以通過(guò)計(jì)算消息摘要y'=H(x'),并且驗(yàn)證y'=y是否成立來(lái)確認(rèn)數(shù)據(jù)x是否被修改。如果y'≠y,則說(shuō)明消息x被修改,從而達(dá)到檢驗(yàn)消息完整性的目的。對(duì)于Hash函數(shù)的安全要求,通常用下面3個(gè)問(wèn)題進(jìn)行判斷。如果一個(gè)Hash函數(shù)對(duì)這3個(gè)問(wèn)題都是難解的,則認(rèn)為該Hash函數(shù)是安全的。用X表示所有消息的集合(有限集或無(wú)限集),Y表示所有消息摘要構(gòu)成的有限集合。(1)原像問(wèn)題(PreimageProblem):設(shè)H:X→Y是一個(gè)Hash函數(shù),y∈Y,是否能夠找到x∈X,使得H(x)=y。如果對(duì)于給定的消息摘要y,原像問(wèn)題能夠解決,則(x,y)是有效的。不能有效解決原像問(wèn)題的Hash函數(shù)稱為單向的或原像穩(wěn)固的。(2)第二原像問(wèn)題(SecondPreimageProblem):設(shè)H:X→Y是一個(gè)Hash函數(shù),x∈X,是否能夠找到x'∈X,使得x'≠x,且H(x')=H(x)。如果第二原像問(wèn)題能夠解決,則(x',H(x))是有效的二元組。不能有效解決第二原像問(wèn)題的Hash函數(shù)稱為第二原像穩(wěn)固的。(3)碰撞問(wèn)題(CollisionProblem):設(shè)H:X→Y是一個(gè)Hash函數(shù),是否能夠找到x,x'∈X,使得x'≠x,且H(x')=H(x)。對(duì)于碰撞問(wèn)題的有效解決并不能直接產(chǎn)生有效的二元組,但是,如果(x,y)是有效的二元組,且x',x是碰撞問(wèn)題的解,則(x',y)也是一個(gè)有效的二元組。不能有效解決碰撞問(wèn)題的Hash函數(shù)稱為碰撞穩(wěn)固的。實(shí)際應(yīng)用中的Hash函數(shù)可分為簡(jiǎn)單的Hash函數(shù)和帶密鑰的Hash函數(shù)。一個(gè)帶密鑰的Hash函數(shù)通常作為消息認(rèn)證碼。假定Alice和Bob有一個(gè)共享的密鑰k,通過(guò)該密鑰可以產(chǎn)生一個(gè)Hash函數(shù)Hk。對(duì)于消息x,Alice和Bob都能夠計(jì)算出相應(yīng)的消息摘要y=Hk(x)。Alice通過(guò)公共通信信道將二元組(x,y)發(fā)送給Bob,Bob接收到(x,y)后,通過(guò)檢驗(yàn)y=Hk(x)是否成立來(lái)確定消息x的完整性。如果y=Hk(x)成立,說(shuō)明消息x和消息摘要y都沒(méi)有被篡改。一個(gè)帶密鑰的Hash函數(shù)族包括以下構(gòu)成要素:(1)X:所有消息的集合(有限集或無(wú)限集)。(2)Y:所有消息摘要構(gòu)成的有限集合。(3)K:密鑰空間,是所有密鑰的有限集合。(4)對(duì)任意的k∈K,都存在一個(gè)Hash函數(shù)Hk∈H,Hk:X→Y。如果Hk(x)=y,則稱二元組(x,y)∈X×Y在密鑰k下是有效的。Hash函數(shù)的目的是為文件、報(bào)文或其他分組數(shù)據(jù)提供完整性檢驗(yàn),要實(shí)現(xiàn)這個(gè)目的,設(shè)計(jì)的Hash函數(shù)H必須具備以下條件:(1)H能夠用于任何大小的數(shù)據(jù)分組。(2)H產(chǎn)生定長(zhǎng)的輸出。(3)對(duì)任意給定的消息x,H(x)要易于計(jì)算,便于軟件和硬件實(shí)現(xiàn)。(4)對(duì)任意給定的消息摘要y,尋找x使得y=H(x)在計(jì)算上是不可行的。(5)對(duì)任意給定的消息x,尋找x',x'≠x,使得H(x)=H(x')在計(jì)算上是不可行的。(6)尋找任意的(x,x'),使得H(x)=H(x')在計(jì)算上是不可行的。以上6個(gè)條件中,前3個(gè)條件是Hash函數(shù)能夠用于消息認(rèn)證的基本要求,第4個(gè)條件是指Hash函數(shù)具有單向性,第5個(gè)條件用于消息摘要被加密時(shí)防止攻擊者的偽造(即能夠抵抗弱碰撞),第6個(gè)條件用于防止生日攻擊(即能夠抵抗強(qiáng)碰撞)。條件(4)(5)和(6)意味著Hash函數(shù)具有3個(gè)一般特性:抗原像特性、抗第二原像特性、碰撞特性。Hash函數(shù)的目的是確定消息是否被修改。因此,對(duì)Hash函數(shù)攻擊的目標(biāo)是生成這樣的修改后消息:其Hash函數(shù)值與原始消息的Hash函數(shù)值相等。例如,如果Oscar找到了一對(duì)消息M1

和M2,使得H(M1)=H(M2),而消息M1

是Alice發(fā)送的,那么Oscar就可以用M2

來(lái)替換M1,從而達(dá)到攻擊的目的。Oscar的問(wèn)題是如何找到具有相同Hash函數(shù)值,并使Alice接受其中一條而反對(duì)另外一條的兩條消息。這可以采取窮舉搜索的方式。Oscar可以構(gòu)造一組可接受的消息和一組不可接受的消息,之后計(jì)算每個(gè)消息的Hash函數(shù)值,尋找具有相同Hash函數(shù)值的消息對(duì)。這種類(lèi)型攻擊法的可行性基于生日問(wèn)題的解決。生日攻擊的思想來(lái)源于概率論中一個(gè)著名的問(wèn)題———生日問(wèn)題。該問(wèn)題是:一個(gè)班級(jí)中至少要有多少個(gè)學(xué)生,才使得兩個(gè)學(xué)生生日相同的概率大于1/2,其答案是23,即只要班級(jí)中的學(xué)生人數(shù)大于23,則班上有兩個(gè)人生日相同的概率大于1/2?；谏諉?wèn)題的生日攻擊意味著,要保證消息摘要對(duì)碰撞問(wèn)題是安全的,則安全消息摘要的長(zhǎng)度就有一個(gè)下界。如果消息摘要的長(zhǎng)度為m位,則總的消息數(shù)為2m,因此需要檢查大約

個(gè)消息,使得兩條消息具有相同Hash函數(shù)值的概率大于50%。例如,長(zhǎng)度為40位的消息摘要是非常不安全的,因?yàn)閮H僅在220(大約為一百萬(wàn))個(gè)隨機(jī)Hash函數(shù)值中就有50%的概率發(fā)現(xiàn)一個(gè)碰撞。舉例來(lái)說(shuō),如果Alice使用了一個(gè)生成16位Hash函數(shù)值的Hash函數(shù),那么Oscar所需要做的工作是構(gòu)造Alice可以接受的28=256條消息和構(gòu)造Alice不能接受的另外256條消息。存在50∶50的機(jī)會(huì),使得這些消息中有兩條消息生成相同的Hash函數(shù)值。這可以通過(guò)生成8個(gè)字不同的類(lèi)似消息來(lái)達(dá)到目的。6.2迭代的Hash函數(shù)本節(jié)討論一種可以將有限定義域上的Hash函數(shù)延拓到具有無(wú)限定義域上的Hash函數(shù)的方法———迭代Hash函數(shù)。1979年,Merkle基于數(shù)據(jù)壓縮函數(shù)compress建議了一個(gè)Hash函數(shù)的通用模式。壓縮函數(shù)compress接受兩個(gè)輸入:m位長(zhǎng)度的壓縮值和t位的數(shù)據(jù)值y,并生成一個(gè)m位的輸出。Merkle建議的內(nèi)容是:數(shù)據(jù)值由消息分組組成,對(duì)所有數(shù)據(jù)分組進(jìn)行迭代處理。在本節(jié)中,我們假設(shè)Hash函數(shù)的輸入和輸出都是位串。我們把位串的長(zhǎng)度記為|x|,把位串x和y的串聯(lián)記為x‖y。下面給出一種構(gòu)造無(wú)限定義域上Hash函數(shù)H的方式,該方式將一個(gè)已知的壓縮函數(shù)compress:{0,1}m+1→{0,1}m(m≥1,t≥1)擴(kuò)展為具有無(wú)限長(zhǎng)度輸入的Hash函數(shù)H。通過(guò)這種方法構(gòu)造的Hash函數(shù)稱為迭代Hash函數(shù)。其系統(tǒng)結(jié)構(gòu)如圖6-1所示。基于壓縮函數(shù)compress構(gòu)造迭代Hash函數(shù)包括以下3個(gè)步驟:(1)預(yù)處理:輸入一個(gè)消息x,其中|x|≥m+t+1,基于x構(gòu)造相應(yīng)的位串y(|y|≡0modt)的過(guò)程如下:y=y1‖y2‖…‖yr

其中,|yi|=t(1≤i≤r),r為消息分組的個(gè)數(shù)。(2)迭代壓縮:設(shè)z0是一個(gè)公開(kāi)的初始位串,|z0|=m。具體的迭代過(guò)程如下:最終得到長(zhǎng)度是m的位串zr。(3)后處理:設(shè)g:{0,1}m

→{0,1}t

是一個(gè)公開(kāi)函數(shù),定義H(x)=g(zr)。則有在上述預(yù)處理過(guò)程中常采用以下方式實(shí)現(xiàn):其中,pad(x)是填充函數(shù),一個(gè)典型的填充函數(shù)是在消息x后填入|x|的值,并填充一些額外的位,使得所得到的位串y是t的整數(shù)倍。在預(yù)處理階段,必須保證映射xy是單射(如果映射xy是一一對(duì)應(yīng)的,就可能找到x≠x'使得y=y',則有H(x)=H(x'),從而設(shè)計(jì)的H將不是碰撞穩(wěn)固的),同時(shí)保證|x‖pad(x)|是t的整數(shù)倍?；趬嚎s函數(shù)compress構(gòu)造迭代Hash函數(shù)的核心技術(shù)是設(shè)計(jì)一種無(wú)碰撞的壓縮函數(shù)compress,而攻擊者對(duì)算法的攻擊重點(diǎn)也是compress的內(nèi)部結(jié)構(gòu)。由于迭代Hash函數(shù)和分組密碼一樣,是由壓縮函數(shù)compress對(duì)消息x進(jìn)行若干輪壓縮處理過(guò)程組成的,所以對(duì)compress的攻擊須分析各輪之間的位模式,分析過(guò)程常常需要先找到compress的碰撞。由于compress是壓縮函數(shù),其碰撞是不可避免的,因此在設(shè)計(jì)compress時(shí)就應(yīng)保證找出其碰撞在計(jì)算上是不可行的。6.3MD5算法與SHA-1算法6.3.1MD5算法的描述MD(MessageDigest,消息摘要)算法由RonRivest在1990年10月提出,1992年4月,RonRivest公布了相應(yīng)的改進(jìn)算法。人們通常把RonRivest在1990年提出的算法稱為MD4,把相應(yīng)的改進(jìn)算法稱為MD5。MD5接收任意長(zhǎng)度的消息作為輸入,并生成128位的消息摘要作為輸出。MD5以512位的分組長(zhǎng)度來(lái)處理消息,每一個(gè)分組又被劃分為16個(gè)32位的子分組。算法的輸出由4個(gè)32位的分組組成,它們串聯(lián)成一個(gè)128位的消息摘要。MD5的算法框圖如圖6-2所示。對(duì)于給定長(zhǎng)度的消息x,MD5算法的具體過(guò)程需要如下3個(gè)步驟:(1)在消息x末尾添加一些額外位來(lái)填充消息,使其長(zhǎng)度恰好比512的整數(shù)倍小64。(2)在其后附上用64位表示的消息長(zhǎng)度信息,得到的結(jié)果序列長(zhǎng)度恰好是512的整數(shù)倍。(3)將初始輸入A=01234567,B=89abcdef,C=fedcba98,D=76543210放在4個(gè)32位寄存器A,B,C,D里(其中0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f表示一個(gè)十六進(jìn)制的數(shù)字或一個(gè)長(zhǎng)度為4的二進(jìn)制序列),MD5對(duì)每個(gè)512位的分組進(jìn)行4輪處理。在完成所有4輪處理后,A,B,C,D的初值加到A,B,C,D的新值上,生成相應(yīng)的消息分組的輸出。這個(gè)輸出用作處理下一個(gè)消息分組的輸入,待最后一個(gè)消息分組處理完后,寄存器A,B,C,D中保存的128位內(nèi)容就是所處理消息的Hash函數(shù)值。下面分別敘述每個(gè)步驟的細(xì)節(jié)。(1)填充是絕大多數(shù)Hash函數(shù)的通用特性,正確的填充能夠增加算法的安全性。對(duì)MD5中的消息進(jìn)行填充,使其長(zhǎng)度等于448mod512,填充是由一個(gè)1后跟足夠個(gè)數(shù)的0組成的,以達(dá)到所要求的長(zhǎng)度。這里應(yīng)強(qiáng)調(diào)的是,即使原消息的長(zhǎng)度達(dá)到了所要求的長(zhǎng)度,也要進(jìn)行填充因此,填充的位數(shù)大于等于1而小于等于512。(2)附加消息的長(zhǎng)度,用上一步留出的64位來(lái)表示消息被填充前的長(zhǎng)度。例如,原始消息的長(zhǎng)度為704位,其二進(jìn)制值為1011000000,將這個(gè)二進(jìn)制值寫(xiě)為64位(在開(kāi)始位置添加54個(gè)0),并把它添加到消息的末尾,其結(jié)果是一個(gè)具有960+64=1024位的消息。(3)MD5的初始輸出放在4個(gè)32位寄存器A,B,C,D中,這些寄存器隨后將用于保存Hash函數(shù)的中間結(jié)果和最終結(jié)果。將4個(gè)寄存器的值賦給相應(yīng)的變量AA,BB,CC,DD。然后對(duì)512位的消息分組序列應(yīng)用主循環(huán),循環(huán)的次數(shù)是消息中按512位分組的分組數(shù)。每一次的主循環(huán)都有4輪操作,而且這4輪操作都很相似。每一輪進(jìn)行16次操作,每次操作對(duì)AA,BB,CC,DD中的3個(gè)作一次非線性的函數(shù)g運(yùn)算,g是基本邏輯函數(shù)FF,GG,HH,II之一。然后將得到的結(jié)果加上第4個(gè)變量,再加上消息的一個(gè)子分組Mj和一個(gè)常數(shù)tj(0≤j≤15),再將所得結(jié)果循環(huán)左移一個(gè)不定的數(shù)s,并加上AA,BB,CC,DD中的一個(gè)。最后用得到的結(jié)果取代AA,BB,CC,DD中的一個(gè)。MD5的分組處理框圖如圖6-3所示,壓縮函數(shù)中的單步迭代示意圖如圖6-4所示。單步基本操作定義為:AA=BB+((AA+g(BB,CC,DD)+Mj+tj)<<s)上述過(guò)程涉及4個(gè)非線性函數(shù)FF,GG,HH,II,子分組Mj,常數(shù)tj,循環(huán)左移數(shù)s,這里分別對(duì)它們進(jìn)行解釋:(1)4個(gè)非線性函數(shù)FF,GG,HH,II接受3個(gè)32位字作為輸入,并按照位邏輯運(yùn)算產(chǎn)生32位輸出。FF,GG,HH,II分別定義為FF,GG,HH,II的函數(shù)真值表如表6-1所示。(2)子分組Mj:將512位的消息分成16個(gè)子分組,每個(gè)子分組32位,共有16個(gè)組,Mj表示第j個(gè)組。Mj的使用過(guò)程為:在第1輪16個(gè)組中Mj正好被用上一次;從第2輪到第4輪則依次通過(guò)下面的置換實(shí)現(xiàn):例如,第3輪ρ3(j)≡(5+3j)mod16的結(jié)果依次為5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2。(3)常

數(shù)tj:每

輪

處

理

過(guò)

程

中

需

要

加

上

常

數(shù)T(見(jiàn)

圖65)中

的16個(gè)

元

素tj,tj為232×abs(sinj)的整數(shù)部分,這里j以弧度為單位。圖中tj由32位的字表示。(4)循環(huán)左移數(shù)s:每輪中每步左循環(huán)移位的位數(shù)按表6-2執(zhí)行。接下來(lái)我們?cè)敿?xì)介紹主循環(huán)中4輪操作的具體內(nèi)容。第1輪操作(共包含16次操作):第2輪操作(共包含16次操作):第3輪操作(共包含16次操作):第4輪操作(共包含16次操作):在此基礎(chǔ)上,令A(yù)=A+AA,B=B+BB,C=C+CC,D=D+DD,輸

出H(x)=A‖B‖C‖D,得到128位的消息摘要。MD5算法具有的性質(zhì)是:Hash函數(shù)的每一位均是輸入消息序列中每一位的函數(shù)。該性質(zhì)保證了在Hash函數(shù)計(jì)算過(guò)程中產(chǎn)生基于消息x的混合重復(fù),從而使得生成的Hash函數(shù)結(jié)果混合得非常理想,也就是說(shuō),隨機(jī)選取兩組有著相似規(guī)律性的消息序列,也很難產(chǎn)生相同的Hash函數(shù)值。目前,MD5算法被廣泛應(yīng)用于各種領(lǐng)域,從密碼分析的角度看,MD5仍然被認(rèn)為是一種易受到攻擊的算法,而且近年來(lái)對(duì)MD5攻擊的相關(guān)研究已取得了很大的進(jìn)展。2004年,我國(guó)學(xué)者王小云給出了一種解決MD5碰撞問(wèn)題的算法。因此,有必要用一個(gè)具有更長(zhǎng)消息摘要和更能抵御已知密碼分析攻擊的Hash函數(shù)來(lái)代替目前被廣泛使用的MD5算法。下面介紹的安全Hash算法,即SHA-1算法。6.《漢語(yǔ)大字典》《漢語(yǔ)大字典》(徐中舒主編，四川辭書(shū)出版社、湖北辭書(shū)出版社1986～1990年聯(lián)合出版)共收錄單字約56000個(gè)，是目前為止收錄漢字最多、單字釋義最全的字典。所有古今文獻(xiàn)中出現(xiàn)過(guò)的漢字，幾乎都可以在該書(shū)中查到。該書(shū)對(duì)每個(gè)漢字的音、形、義都作了歷史的、全面的反映。書(shū)中系統(tǒng)整理了古今楷書(shū)漢字，并收列能反映形體演變關(guān)系的甲骨文、金文、篆書(shū)和隸書(shū)形體。除用漢語(yǔ)拼音字母注明字的現(xiàn)代讀音外，書(shū)中還收列了中古的反切，標(biāo)注了上古的韻部。該書(shū)義項(xiàng)完備，書(shū)證豐富，詳釋字的本義、派生義、通假義，釋義比較準(zhǔn)確。全書(shū)共8卷，按部首編排，共200個(gè)部首，同部首的按漢字筆畫(huà)從少到多排列。每分卷都附有檢字表，第8卷為“附錄和索引”，列有“筆畫(huà)檢字表”，從該表能快速查到字典所收的任何一個(gè)漢字所在的卷、頁(yè)。6.3.2SHA-1算法的描述SHA-1(SecurityHashAlgorithm,安全Hash算法)是一個(gè)產(chǎn)生160位消息摘要的迭代Hash函數(shù),該算法由美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)提出,于1993年公布并作為聯(lián)邦信息處理標(biāo)準(zhǔn)。SHA-1的設(shè)計(jì)基于MD4算法,并且它在設(shè)計(jì)方面也很大程度上模仿MD4算法。2002年,NIST在SHA-1的基礎(chǔ)上,進(jìn)一步推出了SHA-256、SHA-394、SHA-512三個(gè)版本的安全Hash算法,它們的消息摘要長(zhǎng)度分別為256位、394位和512位。這些改進(jìn)算法不僅增強(qiáng)了Hash算法的安全性能,而且便于與AES算法相結(jié)合。這些改進(jìn)算法的基本運(yùn)算結(jié)構(gòu)與SHA-1算法很相似,下面主要介紹SHA-1算法的基本原理和運(yùn)算流程。SHA-1的算法框圖如圖6-6所示。SHA-1算法輸入消息的最大長(zhǎng)度不超過(guò)264,輸入的消息按照512位的分組進(jìn)行處理。算法的具體操作如下:(1)填充過(guò)程。設(shè)輸入的消息序列為x,|x|表示消息序列的長(zhǎng)度。由于SHA-1算法要求輸入消息的最大長(zhǎng)度不超過(guò)264位,所以|x|≤264-1。用和MD5類(lèi)似的方式填充消息,填充過(guò)程對(duì)輸入的消息序列進(jìn)行填充使得消息長(zhǎng)度與448模512同余(即|x|mod512=448),填充的位數(shù)范圍是1~512,填充位串的最高位為1,其余各位均為0。(2)在填充的結(jié)果序列后附加序列。用和MD5類(lèi)似的方式附加消息的長(zhǎng)度,將一個(gè)64位的序列附加到填充的結(jié)果序列后面,填充序列的值等于初始序列位串的長(zhǎng)度值,從而得到長(zhǎng)度是512位的分組序列。(3)對(duì)給定的5個(gè)32位的寄存器A,B,C,D,E賦初值,即其中,0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f表示一個(gè)十六進(jìn)制的數(shù)字或一個(gè)長(zhǎng)度為4的二進(jìn)制序列。這5個(gè)寄存器隨后將用于保存Hash函數(shù)的中間結(jié)果和最終結(jié)果。(4)將寄存器的值賦給相應(yīng)的變量AA,BB,CC,DD,EE。然后對(duì)512位的消息分組序列應(yīng)用主循環(huán),循環(huán)的次數(shù)是消息中按512位進(jìn)行分組的分組數(shù)。每一次的主循環(huán)都有4輪操作,并且這4輪操作都很相似。每一輪進(jìn)行20次操作,每次操作對(duì)AA,BB,CC,DD,EE中的3個(gè)作一次非線性的函數(shù)Ft運(yùn)算,Ft是基本邏輯函數(shù)F1,F2,F3,F4之一。然后進(jìn)行與MD5算法類(lèi)似的移位運(yùn)算(一個(gè)5位的循環(huán)移位和一個(gè)30位的循環(huán)移位)和加運(yùn)算。最后用得到的結(jié)果取代AA,BB,CC,DD中的一個(gè)。SHA-1的分組處理框圖如圖6-7所示,壓縮函數(shù)中的單步迭代示意圖如圖6-8所示。主循環(huán)包括:當(dāng)0≤t≤79時(shí),(1)A=A+AA,B=B+BB,C=C+CC,D=D+DD,E=E+EE。(2)輸出H(x)=A‖B‖C‖D‖E,得到160位的消息摘要。SHA-1算法中的非線性函數(shù)定義為函數(shù)F1,F2,F3,F4的真值表如表63所示。與MD5使用64個(gè)常量不同,SHA-1在各個(gè)階段只加了4個(gè)常量值,分別為設(shè)y=M0‖M1‖…‖M15,其中每一個(gè)消息分組Mi都是長(zhǎng)度為32位的字。用以下方法將消息分組從16個(gè)32位的字變成80個(gè)32位的字:SHA-1分組處理所需的80個(gè)字的產(chǎn)生過(guò)程如圖6-9所示。6.3.3MD5與SHA-1的比較由于MD5與SHA-1都是由MD4演化來(lái)的,所以兩個(gè)算法極為相似。下面給出MD5和SHA-1之間的比較分析。(1)抗窮舉搜索攻擊的強(qiáng)度:MD5與SHA-1的消息摘要長(zhǎng)度分別為128位和160位,由于SHA-1生成的消息摘要長(zhǎng)度比MD5算法生成的消息摘要長(zhǎng)度要長(zhǎng)32位,所以用窮舉搜索攻擊尋找具有給定消息摘要的消息分別需要做O(2128)和O(2160)次運(yùn)算,而窮舉搜索攻擊找到具有相同消息摘要的兩個(gè)不同消息分別需要做O(264)和O(280)次運(yùn)算,因此SHA-1抗擊窮舉搜索攻擊的強(qiáng)度高于MD5抗擊窮舉搜索攻擊的強(qiáng)度。一般認(rèn)為,SHA-1是抗密碼分析的,而MD5算法可能是易于受到攻擊的。(2)速度:由于MD5與SHA-1的主要運(yùn)算都是模232加法,因此都易在32位結(jié)構(gòu)上實(shí)現(xiàn)。但比較起來(lái),SHA-1的迭代步數(shù)(80步)多于MD5的迭代步數(shù)(64步),所用的緩沖區(qū)(160位)大于MD5使用的緩沖區(qū)(128位),因此在相同硬件上實(shí)現(xiàn)時(shí),SHA-1的速度要比MD5的速度慢。(3)簡(jiǎn)潔與緊致性:MD5與SHA-1描述起來(lái)都較為簡(jiǎn)單,實(shí)現(xiàn)起來(lái)也較為簡(jiǎn)單,均不需要較大的程序和代換表。6.4SM3算法6.4.1SM3算法的描述2012年,國(guó)家商用密碼管理辦公室發(fā)布了SM3密碼雜湊算法,并將其作為密碼行業(yè)標(biāo)準(zhǔn)(GM/T0004—2012)。2016年,國(guó)家標(biāo)準(zhǔn)化委員會(huì)公布了SM3密碼雜湊算法為國(guó)家標(biāo)準(zhǔn)(GB/T32905—2016)。目前,SM3密碼雜湊算法已經(jīng)提交ISO國(guó)際標(biāo)準(zhǔn)化組織。SM3密碼雜湊算法的消息分組長(zhǎng)度為512位,輸出摘要長(zhǎng)度為256位。壓縮函數(shù)的狀態(tài)有256位,共64步操作。1.SM3密碼雜湊算法的初始化(1)SM3密碼雜湊算法中用到的初始向量IV共256位,由8個(gè)32位的字串聯(lián)組成,具體值為(2)SM3雜湊算法需要用到的常量定義如下:(3)SM3雜湊算法使用的布爾函數(shù)定義為(4)SM3雜湊算法使用的置換函數(shù)定義為(5)對(duì)于長(zhǎng)度為l位的消息m,SM3密碼雜湊算法首先將位“1”添加到消息的末尾,然后再添加k個(gè)“0”位,其中k是滿足l+k+1≡448mod512的最小非負(fù)整數(shù),最后添加一個(gè)64位的位串,該位串是消息長(zhǎng)度l的二進(jìn)制表示。填充后的消息m'的位長(zhǎng)為512的倍數(shù)。2.SM3密碼雜湊算法的迭代過(guò)程將填充后的消息m'按照512位為一組進(jìn)行消息分組其中,n=(l+k+1)/512。對(duì)消息分組進(jìn)行多輪迭代其中,CF是SM3的壓縮函數(shù),初始值V(0)為256位的初始向量IV,B(i)為填充后的消息分組。迭代過(guò)程輸出的結(jié)果為V(n)。3.SM3密碼雜湊算法的壓縮函數(shù)SM3密碼雜湊算法的核心是壓縮函數(shù)CF。壓縮函數(shù)由消息擴(kuò)展過(guò)程和狀態(tài)更新過(guò)程組成。具體描述如下:1)消息擴(kuò)展過(guò)程將消息分組B(i)按照以下方式擴(kuò)展生成132個(gè)字,并用于壓縮函數(shù)CF。(1)將消息分組B(i)劃分成16個(gè)字W0,W1,…,W15。(2)循環(huán)52次生成52個(gè)字,即(3)循環(huán)64次生成最后64個(gè)字,即SM3密碼雜湊算法的消息擴(kuò)展過(guò)程如圖6-10所示。2)狀態(tài)更新過(guò)程設(shè)A,B,C,D,E,F,G,H為寄存器,