4.1Hash函數(shù)與隨機(jī)預(yù)言模型4.2迭代Hash函數(shù)4.3MD4.4SHA-14.5MD5與SHA-1的比較*4.6消息認(rèn)證碼(MAC)習(xí)題4.1.1Hash函數(shù)

數(shù)據(jù)的完整性是指數(shù)據(jù)從發(fā)送方產(chǎn)生，經(jīng)過傳輸或存儲以后，未被以未授權(quán)的方式修改的性質(zhì)。密碼學(xué)中的Hash函數(shù)在現(xiàn)代密碼學(xué)中扮演著重要的角色，該函數(shù)不同于計(jì)算機(jī)應(yīng)用領(lǐng)域中的Hash函數(shù)，本書中所講的都是密碼學(xué)中的Hash函數(shù)。

Hash函數(shù)是一個(gè)將任意長度的消息序列映射為較短的、固定長度的一個(gè)值的函數(shù)。密碼學(xué)上的Hash函數(shù)能夠保障數(shù)據(jù)的完整性，它通常被用來構(gòu)造數(shù)據(jù)的“指紋”(即函數(shù)值)，當(dāng)被檢驗(yàn)的數(shù)據(jù)發(fā)生改變的時(shí)候，對應(yīng)的“指紋”信息也將發(fā)生變化。這樣，即使數(shù)據(jù)存儲在不安全的地方，也可以通過數(shù)據(jù)的“指紋”信息來檢測數(shù)據(jù)的完整性。4.1Hash函數(shù)與隨機(jī)預(yù)言模型設(shè)H是一個(gè)Hash函數(shù)，x是消息，不妨假設(shè)x是任意長度的二元序列，相應(yīng)的“指紋”定義為y=H(x)，Hash函數(shù)值通常也稱為消息摘要(MessageDigest)。一般要求消息摘要是相當(dāng)短的二元序列，常用的消息摘要是160位。

如果消息x被修改為x′，則可以通過計(jì)算消息摘要y′=H(x′)并且驗(yàn)證y′=y是否成立來確認(rèn)數(shù)據(jù)x是否被修改的事實(shí)。如果y′≠y，則說明消息x被修改，從而達(dá)到了檢驗(yàn)消息完整性的目的。對于Hash函數(shù)的安全要求，通常采用下面的三個(gè)問題來進(jìn)行判斷。如果一個(gè)Hash函數(shù)對這三個(gè)問題都是難解的，則認(rèn)為該Hash函數(shù)是安全的。

用X表示所有消息的集合(有限集或無限集)，Y表示所有消息摘要構(gòu)成的有限集合。

定義4.1.1

原像問題(PreimageProblem)設(shè)H：X

→Y是一個(gè)Hash函數(shù)，y∈Y。是否能夠找到x∈X，使得H(x)=y。

如果對于給定的消息摘要y，原像問題能夠解決，則(x，y)是有效的。不能有效解決原像問題的Hash函數(shù)稱為單向的或原像穩(wěn)固的。

定義4.1.2

第二原像問題(SecondPreimageProblem)設(shè)H:X→Y是一個(gè)Hash函數(shù)，x∈X。是否能夠找到x′∈X，使得x′≠x，并且H(x′)=H(x)。

如果第二原像問題能夠解決，則(x′，H(x))是有效的二元組。不能有效解決第二原像問題的Hash函數(shù)稱為第二原像穩(wěn)固的。

定義4.1.3

碰撞問題(CollisionProblem)設(shè)H:X→Y是一個(gè)

Hash函數(shù)。是否能夠找到x，x′∈X，使得x′≠x，并且H(x′)=H(x)。

對于碰撞問題的有效解決并不能直接產(chǎn)生有效的二元組，但是，如果(x，y)是有效的二元組，并且x′，x是碰撞問題的解，則(x′，y)也是一個(gè)有效的二元組。不能有效解決碰撞問題的Hash函數(shù)稱為碰撞穩(wěn)固的。實(shí)際應(yīng)用中的Hash函數(shù)可分為簡單的Hash函數(shù)和帶密鑰的Hash函數(shù)。帶密鑰的Hash函數(shù)通常用來作為消息認(rèn)證碼(MessageAuthenticationCode)。假定Alice和Bob有一個(gè)共享的密鑰k，通過該密鑰可以產(chǎn)生一個(gè)Hash函數(shù)Hk。對于消息x，Alice和Bob都能夠計(jì)算出相應(yīng)的消息摘要y=Hk(x)。Alice通過公共通信信道將二元組(x，y)發(fā)送給Bob。當(dāng)Bob接收到(x，y)后，它可以通過檢驗(yàn)y=Hk(x)是否成立來確定消息x的完整性。如果y=Hk(x)成立，說明消息x和消息摘要y都沒有被篡改。下面給出帶密鑰的Hash函數(shù)族的定義。

定義4.1.4

一個(gè)帶密鑰的Hash函數(shù)族包括以下構(gòu)成要素：

(1)X：所有消息的集合(有限集或無限集)；

(2)Y：所有消息摘要構(gòu)成的有限集合；

(3)K：密鑰空間，是所有密鑰的有限集合；

(4)對任意的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必須具備以下性質(zhì)：

(1)H能夠用于任何大小的數(shù)據(jù)分組；

(2)H產(chǎn)生定長的輸出；

(3)對任意給定的x，H(x)要易于計(jì)算，便于軟件和硬件實(shí)現(xiàn);

(4)對任意給定的消息摘要y，尋找x使得y=H(x)在計(jì)算上是不可行的；

(5)對任意給定的消息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è)條件用于防止生日攻擊。生日攻擊的思想來源于概率論中一個(gè)著名的問題——生日問題。該問題是問一個(gè)班級中至少要有多少個(gè)學(xué)生才能夠使得有兩個(gè)學(xué)生生日相同的概率大于1/2。該問題的答案是23。即只要班級中學(xué)生的人數(shù)大于23人，則班上有兩個(gè)人生日相同的概率就將大于1/2?；谏諉栴}的生日攻擊意味著要保證消息摘要對碰撞問題是安全的，則安全消息摘要的長度就有一個(gè)下界。例如，長度為40比特的消息摘要是非常不安全的，因?yàn)閮H僅在220(大約為一百萬)個(gè)隨機(jī)Hash函數(shù)值中就有50%的概率發(fā)現(xiàn)一個(gè)碰撞。所以對于安全的消息摘要，現(xiàn)在通常建議可接受的最小長度為128比特(此時(shí)生日攻擊需要超過264個(gè)Hash函數(shù)值)。而實(shí)際使用的消息摘要一般為160比特甚至更長。4.1.2隨機(jī)預(yù)言模型

本小節(jié)介紹一種Hash函數(shù)的某種理想化模型，該模型對于每一個(gè)消息，都試圖得到一個(gè)理想的Hash函數(shù)值。由Bellare和Rogaway提出的隨機(jī)預(yù)言模型(RandomOracleModel)是一種“理想化”的Hash函數(shù)數(shù)學(xué)模型。在這個(gè)模型中，隨機(jī)從FX，Y中選出一個(gè)Hash函數(shù)H:X→Y，僅僅允許預(yù)言器訪問函數(shù)H，這表示對于任一個(gè)消息x，隨機(jī)預(yù)言模型都不會給出一個(gè)公式或者算法來計(jì)算消息摘要H(x)的值。因此，計(jì)算H(x)值的惟一方法是詢問預(yù)言器，這種Hash函數(shù)模型相當(dāng)于根據(jù)給出的消息x，在一本關(guān)于隨機(jī)數(shù)的書中查詢H(x)的值，對于每一個(gè)x，都有一個(gè)完全隨機(jī)的H(x)與之對應(yīng)。

定義4.1.5

令FX，Y是所有從X到Y(jié)的函數(shù)集合。假定|X|=N，|Y|=M，則|FX，Y|=MN。任何Hash函數(shù)族F

FX，Y被稱為一個(gè)(N，M)—Hash族。

對于隨機(jī)預(yù)言模型，以下結(jié)論是成立的。

定理4.1

隨機(jī)選擇H∈FX，Y并取子集合X0

X。假設(shè)當(dāng)

且僅當(dāng)x∈X0時(shí)，H(x)的值由查詢預(yù)言器確定，那么對于所有的x∈X＼X0和y∈Y，P(H(x)=y)=。

在以上結(jié)論中，概率P(H(x)=y)實(shí)際上是對任意的x∈X，計(jì)算相應(yīng)的函數(shù)H(x)的值，從而得到指定值的條件概率。通過該結(jié)論可知，M的值越大，相應(yīng)地產(chǎn)生碰撞的概率就越小。4.2迭代Hash函數(shù)本節(jié)討論一種可以將有限定義域上的Hash函數(shù)延拓到具有無限定義域上的Hash函數(shù)的方法——迭代Hash函數(shù)。目前使用的Hash函數(shù)大多數(shù)都是迭代Hash函數(shù)，例如被廣泛使用的MD5、安全Hash算法(SHA-1)等。在本節(jié)中，假設(shè)Hash函數(shù)的輸入和輸出都是位串。把位串的長度記為|x|，把位串x和y的串聯(lián)記為x‖y。下面給出一種構(gòu)造無限定義域上Hash函數(shù)H的方式，該方式通過將一個(gè)已知的壓縮函數(shù)compress:{0，1}m+t→{0，1}m(m≥1，t≥1)擴(kuò)展為可以具有無限長度輸入的Hash函數(shù)H來達(dá)到目的。通過這種方法構(gòu)造的Hash函數(shù)稱為迭代Hash函數(shù)?；趬嚎s函數(shù)compress構(gòu)造迭代Hash函數(shù)包括以下三步：

(1)預(yù)處理。輸入一個(gè)消息x，其中|x|≥m+t+1，基于x構(gòu)造相應(yīng)的位串y(|y|≡0modt)的過程如下：

y=y1‖y2‖…‖yr

其中，|yi|=t，1≤i≤r，r為消息分組的個(gè)數(shù)。

(2)迭代壓縮。設(shè)z0是一個(gè)公開的初始位串，|z0|=m。具體的迭代過程如下：

z1←compress(z0‖y1)

z2←compress(z1‖y2)

zr←compress(zr-1‖yr)

最終得到長度是m的位串zr。

(3)后處理。設(shè)g:{0，1}m→{0，1}t是一個(gè)公開函數(shù)，定義H(x)=g(zr)。則有

在上述預(yù)處理過程中常采用以下方式實(shí)現(xiàn)：

y=x‖pad(x)

其中，pad(x)是填充函數(shù)，一個(gè)典型的填充函數(shù)是在消息x后填入|x|的值，并填充一些額外的比特，使得所得到的比特串y是t的整數(shù)倍。在預(yù)處理階段，必須保證映射x→y是單射(如果映射x|→y不是一一對應(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ì)一種無碰撞的壓縮函數(shù)compress，而攻擊者對算法的攻擊重點(diǎn)也是compress的內(nèi)部結(jié)構(gòu)。由于迭代Hash函數(shù)和分組密碼一樣是由compress壓縮函數(shù)對消息x進(jìn)行若干輪壓縮處理組成的，因此對compress的攻擊需通過對各輪之間的位模式的分析來進(jìn)行，分析過程常常需要先找到compress的碰撞。由于compress是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計(jì)compress時(shí)就應(yīng)保證找出其碰撞在計(jì)算上是不可行的。

下面介紹幾個(gè)重要的迭代Hash函數(shù)。4.3MD

MD(MessageDigest，消息摘要)算法由RonRivest在1990年10月提出，人們通常稱之為MD4。

MD4對于輸入的消息產(chǎn)生128位的消息摘要。由于它的安全性不是基于任何其他的密碼體制和已知的單向函數(shù)，因此它的安全性只能由時(shí)間來證明。MD4算法首次公布后，Bertden

Boer和AntoonBosselaers對三輪算法中的后兩輪成功地進(jìn)行了密碼分析。在一個(gè)不相關(guān)的分析結(jié)果中，RalphMerkle成功地攻擊了三輪算法中的前兩輪。EliBiham也討論了對MD4的前兩輪進(jìn)行差分攻擊的可能性。盡管這些攻擊算法還沒有擴(kuò)展到整個(gè)MD4算法，但是為了增強(qiáng)算法的安全性，RonRivest于1992年4月給出了MD4的改進(jìn)算法——MD5。為了介紹MD5，下面先介紹MD4。4.3.1MD4

MD4算法中涉及到如下一些基本運(yùn)算：

(1)X∧Y：X和Y進(jìn)行邏輯與運(yùn)算；

(2)X∨Y：X和Y進(jìn)行邏輯或運(yùn)算；

(3)X⊕Y：X和Y進(jìn)行邏輯異或運(yùn)算；

(4)：X的邏輯補(bǔ)運(yùn)算；

(5)X+Y：整數(shù)模232加法運(yùn)算；

(6)X<<s：將X循環(huán)左移s位(0≤s≤31)。

MD4算法的具體過程如下。

首先輸入任意長度的消息x，由x構(gòu)造一個(gè)數(shù)組序列

M=M［0］M［1］…M［n-1］

其中，|M［i］|=32，0≤i≤n-1，n≡0mod16。在得到M的基礎(chǔ)上，MD4構(gòu)造Hash函數(shù)H(x)的方法如下：

(1)給定4個(gè)寄存器A、B、C、D(也稱為鏈接變量)，對其賦初值：

A=67452301

B=efcdab89

C=98badcfe

D=10325476

其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一個(gè)十六進(jìn)制的數(shù)字或一個(gè)長度為4的二進(jìn)制序列。

(2)計(jì)算

X［j］=M［16i+j］

其中，0≤i≤(n/16)-1，0≤j≤15。

(3)將已有的4個(gè)寄存器A、B、C、D中的數(shù)組分別存放到另外4個(gè)寄存器AA、BB、CC、DD中。

(4)執(zhí)行第一輪操作。具體內(nèi)容包括：

A=(A+F(B，C，D)+X［4k］)<<3

D=(D+F(A，B，C)+X［4k+1］)<<7

C=(C+F(D，A，B)+X［4k+2］)<<11

B=(B+F(C，D，A)+X［4k+3］)<<19

其中，0≤k≤3，F(xiàn)(X，Y，Z)=(X∧Y)∨(∧Z)。

(5)執(zhí)行第二輪操作。具體內(nèi)容包括：

A=(A+G(B，C，D)+X［k］+5a827999)<<3

D=(D+G(A，B，C)+X［4+k］+5a827999)<<5

C=(C+G(D，A，B)+X［8+k］+5a827999)<<9

B=(B+G(C，D，A)+X［12+k］+5a827999)<<13

其中，0≤k≤3，G(X，Y，Z)=(X∧Y)∨(X∧Z)∨(Y∧Z)。

(6)執(zhí)行第三輪操作。具體內(nèi)容包括：

A=(A+H(B，C，D)+X［0］+6ed9eba1)<<3

D=(D+H(A，B，C)+X［8］+6ed9eba1)<<9

C=(C+H(D，A，B)+X［4］+6ed9eba1)<<11

B=(B+H(C，D，A)+X［12］+6ed9eba1)<<15

A=(A+H(B，C，D)+X［2］+6ed9eba1)<<3

D=(D+H(A，B，C)+X［10］+6ed9eba1)<<9

C=(C+H(D，A，B)+X［6］+6ed9eba1)<<11

B=(B+H(C，D，A)+X［14］+6ed9eba1)<<15

A=(A+H(B，C，D)+X［1］+6ed9eba1)<<3

D=(D+H(A，B，C)+X［9］+6ed9eba1)<<9

C=(C+H(D，A，B)+X［5］+6ed9eba1)<<11

B=(B+H(C，D，A)+X［13］+6ed9eba1)<<15

A=(A+H(B，C，D)+X［3］+6ed9eba1)<<3

D=(D+H(A，B，C)+X［11］+6ed9eba1)<<9

C=(C+H(D，A，B)+X［7］+6ed9eba1)<<11

B=(B+H(C，D，A)+X［15］+6ed9eba1)<<15

其中，H(X，Y，Z)=X⊕Y⊕

Z。

(7)A=A+AA，B=B+BB，C=C+CC，D=D+DD。

(8)輸出H(x)=A‖B‖C‖D，得到128位的消息摘要。4.3.2MD5

MD5算法以512位的分組長度來處理消息，每一個(gè)分組又被劃分為16個(gè)32位的子分組。算法的輸出由4個(gè)32位的分組組成，它們串聯(lián)成一個(gè)128位的消息摘要。

MD5算法的具體過程如下。

首先對消息x進(jìn)行預(yù)處理，使其長度恰好比512的整數(shù)倍小64。然后在其后面附上用64位表示的消息長度信息。得到的結(jié)果序列長度恰好是512的整數(shù)倍。在此基礎(chǔ)上，MD5構(gòu)造Hash函數(shù)H(x)的方法如下：

(1)對給定的4個(gè)寄存器A、B、C、D賦初值：

A=01234567

B=89abcdef

C=fedcba98

D=76543210

其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一個(gè)十六進(jìn)制的數(shù)字或一個(gè)長度為4的二進(jìn)制序列。

(2)將以上得到的寄存器的值賦給相應(yīng)的變量AA、BB、CC、DD。然后對512位的消息分組序列應(yīng)用主循環(huán)進(jìn)行處理，循環(huán)的次數(shù)是消息中512位的分組數(shù)。每一次的主循環(huán)都有四輪(注：MD4只有三輪)操作，而且這四輪操作都很相似。每一輪進(jìn)行16次操作，每次操作對AA、BB、CC、DD中的三個(gè)作一次非線性的函數(shù)運(yùn)算，然后將得到的結(jié)果加上第四個(gè)變量，再加上消息的一個(gè)子分組和一個(gè)常數(shù)。再將所得結(jié)果循環(huán)右移一個(gè)不定的數(shù)(在MD5算法中給出了具體的數(shù)值)，并加上AA、BB、CC、DD其中的一個(gè)。最后用得到的結(jié)果取代AA、BB、CC、DD其中的一個(gè)。以上過程中用到的四個(gè)非線性函數(shù)分別定義為在此基礎(chǔ)上，設(shè)Mj表示消息的第j個(gè)子分組，0≤j≤15。則以上過程中四種基本操作分別定義為

AA=FF(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+F(BB,CC,DD)+Mj+tj)<<s)

AA=GG(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+G(BB,CC,DD)+Mj+tj)<<s)

AA=HH(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+H(BB,CC,DD)+Mj+tj)<<s)

AA=II(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+I(BB,CC,DD)+Mj+tj)<<s)接下來詳細(xì)介紹主循環(huán)中的四輪操作的具體內(nèi)容。

第一輪操作(共包含16次操作)：

FF(AA，BB，CC，DD，M0，7，d76aa478)

FF(DD，AA，BB，CC，M1，12，e8c7b756)

FF(CC，DD，AA，BB，M2，17，242070db)

FF(BB，CC，DD，AA，M3，22，c1bdceee)

FF(AA，BB，CC，DD，M4，7，f57c0faf)

FF(DD，AA，BB，CC，M5，12，4787c62a)

FF(CC，DD，AA，BB，M6，17，a8304613)

FF(BB，CC，DD，AA，M7，22，fd469501)

FF(AA，BB，CC，DD，M8，7，698098d8)

FF(DD，AA，BB，CC，M9，12，8b44f7af)

FF(CC，DD，AA，BB，M10，17，ffff5bb1)

FF(BB，CC，DD，AA，M11，22，895cd7be)

FF(AA，BB，CC，DD，M12，7，6b901122)

FF(DD，AA，BB，CC，M13，12，fd987193)

FF(CC，DD，AA，BB，M14，17，a679438e)

FF(BB，CC，DD，AA，M15，22，49b40821)第二輪操作(共包含16次操作)：

GG(AA，BB，CC，DD，M1，5，f61e2562)

GG(DD，AA，BB，CC，M6，9，c040b340)

GG(CC，DD，AA，BB，M11，14，265e5a51)

GG(BB，CC，DD，AA，M0，20，e9b6c7aa)

GG(AA，BB，CC，DD，M5，5，d62f105d)

GG(DD，AA，BB，CC，M10，9，02441453)

GG(CC，DD，AA，BB，M15，14，d8a1e681)

GG(BB，CC，DD，AA，M4，20，e7d3fbc8)

GG(AA，BB，CC，DD，M9，5，21e1cde6)

GG(DD，AA，BB，CC，M14，9，c33707d6)

GG(CC，DD，AA，BB，M3，14，f4d50d87)

GG(BB，CC，DD，AA，M8，20，455a14ed)

GG(AA，BB，CC，DD，M13，5，a9e3e905)

GG(DD，AA，BB，CC，M2，9，fcefa3f8)

GG(CC，DD，AA，BB，M7，14，676f02d9)

GG(BB，CC，DD，AA，M12，20，8d2a4c8a)第三輪操作(共包含16次操作)：

HH(AA，BB，CC，DD，M5，4，fffa3942)

HH(DD，AA，BB，CC，M8，11，8771f681)

HH(CC，DD，AA，BB，M11，16，6d9d6122)

HH(BB，CC，DD，AA，M14，23，fde5380c)

HH(AA，BB，CC，DD，M1，4，a4beea44)

HH(DD，AA，BB，CC，M4，11，4bdecfa9)

HH(CC，DD，AA，BB，M7，16，f6bb4b60)

HH(BB，CC，DD，AA，M10，23，bebfbc70) HH(AA，BB，CC，DD，M13，4，289b7ec6)

HH(DD，AA，BB，CC，M0，11，eaa127fa)

HH(CC，DD，AA，BB，M3，16，d4ef3085)

HH(BB，CC，DD，AA，M6，23，04881d05)

HH(AA，BB，CC，DD，M9，4，d9d4d039)

HH(DD，AA，BB，CC，M12，11，e6db99e5)

HH(CC，DD，AA，BB，M15，16，1fa27cf8)

HH(BB，CC，DD，AA，M2，23，c4ac5665)第四輪操作(共包含16次操作)：

II(AA，BB，CC，DD，M0，6，f4292244)

II(DD，AA，BB，CC，M7，10，432aff97)

II(CC，DD，AA，BB，M14，15，ab9423a7)

II(BB，CC，DD，AA，M5，21，fc93a039)

II(AA，BB，CC，DD，M12，6，655b59c3)

II(DD，AA，BB，CC，M3，10，8f0ccc92)

II(CC，DD，AA，BB，M10，15，ffeff47d)

II(BB，CC，DD，AA，M1，21，85845dd1)

II(AA，BB，CC，DD，M8，6，6fa87e4f)

II(DD，AA，BB，CC，M15，10，fe2ce6e0)

II(CC，DD，AA，BB，M6，15，a3014314)

II(BB，CC，DD，AA，M13，21，4e0811a1)

II(AA，BB，CC，DD，M4，6，f7537e82)

II(DD，AA，BB，CC，M11，10，bd3af235)

II(CC，DD，AA，BB，M2，15，2ad7d2dd)

II(BB，CC，DD，AA，M9，21，eb86d391)

(3)A=A+AA，B=B+BB，C=C+CC，D=D+DD。

(4)輸出H(x)=A‖B‖C‖D，得到128位的消息摘要。

通過與MD4的過程進(jìn)行比較可知，MD5相對MD4進(jìn)行了以下一些改進(jìn)：

(1)增加了主循環(huán)中的操作次數(shù)，由三輪操作改進(jìn)為四輪操作；

(2)操作的每一步均有惟一的加法常數(shù)；

(3)為了減弱函數(shù)G的對稱性，函數(shù)定義由(X∧Y)∨(X∧Z)∨(Y∧Z)改進(jìn)為(X∧Z)∨(Y∧(

Z))；

(4)改變了第二輪和第三輪中訪問消息子分組的次序，使得其形式更加不相似；

(5)近似優(yōu)化了每一輪中循環(huán)移位的位移量，各輪的位移量各不相同。

MD5算法有以下性質(zhì)：Hash函數(shù)的每一位均是輸入消息序列中每一位的函數(shù)。該性質(zhì)保證了在Hash函數(shù)計(jì)算過程中產(chǎn)生基于消息x的混合重復(fù)，從而使得生成的Hash函數(shù)結(jié)果混合得非常理想，也就是說，隨機(jī)選取兩個(gè)有著相似規(guī)律性的兩組消息序列，也很難產(chǎn)生相同的Hash函數(shù)值。

目前，MD5算法被廣泛應(yīng)用于各種領(lǐng)域。從密碼分析的角度上看，MD5仍然被認(rèn)為是一種易受到攻擊的算法，而且，近年來對MD5攻擊的相關(guān)研究已取得了很大的進(jìn)展。2004年，我國學(xué)者王小云給出了一種解決MD5碰撞問題的算法。因此，有必要用一個(gè)具有更長消息摘要和更能抵御已知密碼分析攻擊的Hash函數(shù)來代替目前被廣泛使用的MD5算法。下面介紹的安全Hash算法——SHA-1就是這樣一個(gè)算法。4.4SHA-1

SHA-1(SecurityHashAlgorithm，安全Hash算法)是一個(gè)產(chǎn)生160位消息摘要的迭代Hash函數(shù)。該算法由美國國家標(biāo)準(zhǔn)和技術(shù)協(xié)會(NIST)提出，并作為聯(lián)邦信息處理標(biāo)準(zhǔn)在1993年公布。SHA-1算法輸入消息的最大長度不超過264位，輸入的消息按照512位的分組進(jìn)行處理。

SHA-1算法的具體操作包括以下幾步：

(1)填充過程。設(shè)輸入的消息序列為x，|x|表示消息序列的長度。因?yàn)镾HA-1算法要求輸入消息的最大長度不超過264位，所以|x|≤264-1。填充過程對輸入的消息序列進(jìn)行填充使得消息長度與448模512同余(即|x|mod512=448)，填充的位數(shù)范圍是1~512，填充位串的最高位為1，其余各位均為0。

(2)在填充的結(jié)果序列后附加序列。將一個(gè)64位的序列附加到填充的結(jié)果序列后面，填充列的值等于初始序列位串的長度值。從而得到長度是512位的分組序列。

(3)對給定的5個(gè)寄存器A、B、C、D、E賦初值：

A=67452301

B=efcdab89

C=98badcfe

D=10325476

E=c3d2e1f0

其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一個(gè)十六進(jìn)制的數(shù)字或一個(gè)長度為4的二進(jìn)制序列。

(4)將以上得到的寄存器的值賦給相應(yīng)的變量AA、BB、CC、DD、EE。然后對512位的消息分組序列y應(yīng)用主循環(huán)進(jìn)行處理，每一次的主循環(huán)都有四輪操作。每一輪進(jìn)行20次操作，每次操作對AA、BB、CC、DD、EE中的三個(gè)作一次非線性的函數(shù)運(yùn)算，然后進(jìn)行與MD5算法類似的移位運(yùn)算和加運(yùn)算。SHA-1算法中的非線性函數(shù)定義為同時(shí)定義相應(yīng)的常數(shù)為

設(shè)y=M0‖M1‖…‖M15，其中每一個(gè)消息分組Mi都是長度為32位的序列。用以下方法將消息分組從16個(gè)32位的序列變成80個(gè)32位的序列。主循環(huán)如下：

當(dāng)0≤t≤79時(shí)，

TEMP=(AA<<5)+Ft(BB，CC，DD)+EE+Wt+Kt

EE=DD

DD=CC

CC=BB<<30

BB=AA

AA=TEMP

(5)A=A+AA，B=B+BB，C=C+CC，D=D+DD，E=E+EE。

(6)輸出H(x)=A‖B‖C‖D，得到160位的消息摘要。4.5MD5與SHA-1的比較由于SHA-1與MD5都由MD4演化而來，所以極為相似。下面給出MD5和SHA-1之間的比較分析。

(1)抗窮舉式搜索攻擊的強(qiáng)度。由于MD5和SHA-1的消息摘要長度分別為128和160，因此用窮舉式搜索攻擊尋找具有給定消息摘要的消息分別需要做O(2128)和O(2160)次運(yùn)算，而窮舉式搜索攻擊找到具有相同消息摘要的兩個(gè)不同消息分別需要做O(264)和O(280)次運(yùn)算。所以SHA-1抗擊窮舉式搜索攻擊的強(qiáng)度高于MD5抗擊窮舉式搜索攻擊的強(qiáng)度。

(2)速度。由于兩個(gè)算法的主要運(yùn)算都是模232加法，因此都易于在32位結(jié)構(gòu)上實(shí)現(xiàn)。但比較起來，SHA-1的迭代步數(shù)(80步)多于MD5的迭代步數(shù)(64步)，所用的緩沖區(qū)(160位)大于MD5使用的緩沖區(qū)(128位)，因此在相同硬件上實(shí)現(xiàn)時(shí)，SHA-1的速度要比MD5的速度慢。

(3)簡潔與緊致性。兩個(gè)算法描述起來都較為簡單，實(shí)現(xiàn)起來也較為簡單，均不需要較大的程序和代換表。*4.6消息認(rèn)證碼(MAC)含有密鑰的Hash函數(shù)通常稱為消息認(rèn)證碼(MessageAuthenticationCodes，MAC)。MAC具有與前面討論的單向Hash函數(shù)相同的特性，所不同的是MAC還包含有密鑰。將單向Hash函數(shù)變成MAC的一個(gè)簡單辦法是應(yīng)用對稱加密算法對消息摘要進(jìn)行加密。但這種方法需要在發(fā)送消息和消息摘要的同時(shí)還要將加密算法使用的加密密鑰通過安全的信道發(fā)送，這樣做降低了算法的實(shí)用性。構(gòu)造MAC的常用方法是把密鑰作為Hash函數(shù)輸入消息的一部分，使得產(chǎn)生的消息摘要不僅與消息序列有關(guān)，而且與附加的密鑰有關(guān)，從而在一個(gè)不帶密鑰的Hash函數(shù)中介入一個(gè)密鑰。但這樣做往往是不安全的，下面通過實(shí)例給予說明。

設(shè)H(x)是不帶密鑰的迭代結(jié)構(gòu)的Hash函數(shù)，k是一個(gè)密鑰，其長度為m位?，F(xiàn)在來構(gòu)造一個(gè)新的帶密鑰的Hash函數(shù)Hk(x)。為了描述簡單，假定H(x)沒有預(yù)處理過程和輸出變換過程。輸入的消息序列記為x，則x的長度應(yīng)該是t的倍數(shù)，建立Hash函數(shù)的壓縮函數(shù)，記為compress:{0，1}m+t→{0，1}m?，F(xiàn)在給出在已知一組有效的消息x和相應(yīng)的消息認(rèn)證碼Hk(x)，且無需知道密鑰k的情況下，來構(gòu)造一個(gè)有效的消息認(rèn)證碼的過程。設(shè)x′是一個(gè)長度為t的位串，現(xiàn)在考慮消息序列x‖x′。

產(chǎn)生消息摘要Hk(x‖x′)的過程如下：

Hk(x‖x′)=compress(Hk(x)‖x′)

因?yàn)镠k(x)和x′都是已知的，所以攻擊者在無需知道密鑰k的情況下，也能構(gòu)造出有效的消息認(rèn)證碼(x‖x′，Hk(x‖x′))。應(yīng)用上述方法構(gòu)造的帶密鑰的Hash函數(shù)存在安全問題。

根據(jù)以上分析可知，構(gòu)造消息認(rèn)證碼不能夠簡單地將密鑰參數(shù)和消息x進(jìn)行拼接，然后直接計(jì)算相應(yīng)的Hash函數(shù)值來處理。根據(jù)消息x和密鑰k計(jì)算消息認(rèn)證碼需要更復(fù)雜的處理過程，下面介紹兩種廣泛使用的消息認(rèn)證碼。4.6.1基于分組密碼的MAC

目前被廣泛使用的MAC算法是基于分組密碼的MAC算法。下面以DES分組密碼為例，來說明構(gòu)造MAC算法的過程。消息分組的長度取為64位，MAC算法的密鑰取為DES算法的加密密鑰。

給定消息序列x和56位的密鑰k，構(gòu)造相應(yīng)的MAC的過程如下：

(1)填充和分組。對消息序列x進(jìn)行填充，將消息序列x分成t個(gè)長度為64位的分組，記為

x=x1‖x2‖x3‖…‖xt

(2)分組密碼的計(jì)算。應(yīng)用DES分組加密算法的計(jì)算過程如下：

(3)可選擇輸出。使用第二個(gè)密鑰k′，k′≠k，計(jì)算相應(yīng)的H(x)的過程如下：

通過以上過程最終得到消息x的MAC為H(x)。

在以上計(jì)算MAC的過程中，第(3)步可選擇輸出過程相當(dāng)于對最后一個(gè)消息分組進(jìn)行了三重DES加密，該操作能夠有效減少M(fèi)AC受到窮舉式搜索攻擊的威脅。由于三重DES加密過程只是在可選擇輸出過程進(jìn)行，沒有在整個(gè)分組密碼計(jì)算過程采用，因此不會影響中間過程的效率。4.6.2基于序列密碼的MAC

考慮到基于異或運(yùn)算的流密碼的位運(yùn)算會直接導(dǎo)致作為基礎(chǔ)明文的可預(yù)測變化，對流密