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

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

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

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

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

定義4.1.1

原像問題(PreimageProblem)設H：X

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

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

定義4.1.2

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

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

定義4.1.3

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

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

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

定義4.1.4

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

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

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

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

(4)對任意的k∈K，都存在一個Hash函數(shù)Hk∈H，Hk:X→Y。

如果Hk(x)=y，則二元組(x，y)∈X×Y稱為在密鑰k下是有效的。

Hash函數(shù)的目的是為文件、報文或者其他的分組數(shù)據(jù)提供完整性檢驗。要實現(xiàn)這個目的，設計的Hash函數(shù)H必須具備以下性質：

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

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

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

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

(5)對任意給定的消息x，尋找x′，x′≠x，使得H(x)=H(x′)在計算上是不可行的；

(6)尋找任意的(x，x′)，使得H(x)=H(x′)在計算上是不可行的。以上6個條件中，前3個條件是Hash函數(shù)能夠用于消息認證的基本要求；第4個條件是指Hash函數(shù)具有單向性；第5個條件用于消息摘要被加密時防止攻擊者的偽造；第6個條件用于防止生日攻擊。生日攻擊的思想來源于概率論中一個著名的問題——生日問題。該問題是問一個班級中至少要有多少個學生才能夠使得有兩個學生生日相同的概率大于1/2。該問題的答案是23。即只要班級中學生的人數(shù)大于23人，則班上有兩個人生日相同的概率就將大于1/2?；谏諉栴}的生日攻擊意味著要保證消息摘要對碰撞問題是安全的，則安全消息摘要的長度就有一個下界。例如，長度為40比特的消息摘要是非常不安全的，因為僅僅在220(大約為一百萬)個隨機Hash函數(shù)值中就有50%的概率發(fā)現(xiàn)一個碰撞。所以對于安全的消息摘要，現(xiàn)在通常建議可接受的最小長度為128比特(此時生日攻擊需要超過264個Hash函數(shù)值)。而實際使用的消息摘要一般為160比特甚至更長。4.1.2隨機預言模型

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

定義4.1.5

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

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

對于隨機預言模型，以下結論是成立的。

定理4.1

隨機選擇H∈FX，Y并取子集合X0

X。假設當

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

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

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

y=y1‖y2‖…‖yr

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

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

z1←compress(z0‖y1)

z2←compress(z1‖y2)

zr←compress(zr-1‖yr)

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

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

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

y=x‖pad(x)

其中，pad(x)是填充函數(shù)，一個典型的填充函數(shù)是在消息x后填入|x|的值，并填充一些額外的比特，使得所得到的比特串y是t的整數(shù)倍。在預處理階段，必須保證映射x→y是單射(如果映射x|→y不是一一對應的，就可能找到x≠x′使得y=y′，則有H(x)=H(x′)，從而設計的H將不是碰撞穩(wěn)固的)，同時保證|x‖pad(x)|是t的整數(shù)倍?；趬嚎s函數(shù)compress構造迭代Hash函數(shù)的核心技術是設計一種無碰撞的壓縮函數(shù)compress，而攻擊者對算法的攻擊重點也是compress的內部結構。由于迭代Hash函數(shù)和分組密碼一樣是由compress壓縮函數(shù)對消息x進行若干輪壓縮處理組成的，因此對compress的攻擊需通過對各輪之間的位模式的分析來進行，分析過程常常需要先找到compress的碰撞。由于compress是壓縮函數(shù)，其碰撞是不可避免的，因此在設計compress時就應保證找出其碰撞在計算上是不可行的。

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

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

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

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

MD4算法中涉及到如下一些基本運算：

(1)X∧Y：X和Y進行邏輯與運算；

(2)X∨Y：X和Y進行邏輯或運算；

(3)X⊕Y：X和Y進行邏輯異或運算；

(4)：X的邏輯補運算；

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

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

MD4算法的具體過程如下。

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

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

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

(1)給定4個寄存器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表示一個十六進制的數(shù)字或一個長度為4的二進制序列。

(2)計算

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

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

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

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

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í)行第二輪操作。具體內容包括：

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í)行第三輪操作。具體內容包括：

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位的分組長度來處理消息，每一個分組又被劃分為16個32位的子分組。算法的輸出由4個32位的分組組成，它們串聯(lián)成一個128位的消息摘要。

MD5算法的具體過程如下。

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

(1)對給定的4個寄存器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表示一個十六進制的數(shù)字或一個長度為4的二進制序列。

(2)將以上得到的寄存器的值賦給相應的變量AA、BB、CC、DD。然后對512位的消息分組序列應用主循環(huán)進行處理，循環(huán)的次數(shù)是消息中512位的分組數(shù)。每一次的主循環(huán)都有四輪(注：MD4只有三輪)操作，而且這四輪操作都很相似。每一輪進行16次操作，每次操作對AA、BB、CC、DD中的三個作一次非線性的函數(shù)運算，然后將得到的結果加上第四個變量，再加上消息的一個子分組和一個常數(shù)。再將所得結果循環(huán)右移一個不定的數(shù)(在MD5算法中給出了具體的數(shù)值)，并加上AA、BB、CC、DD其中的一個。最后用得到的結果取代AA、BB、CC、DD其中的一個。以上過程中用到的四個非線性函數(shù)分別定義為在此基礎上，設Mj表示消息的第j個子分組，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)接下來詳細介紹主循環(huán)中的四輪操作的具體內容。

第一輪操作(共包含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的過程進行比較可知，MD5相對MD4進行了以下一些改進：

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

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

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

Z))；

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

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

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

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

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

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

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

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

(3)對給定的5個寄存器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表示一個十六進制的數(shù)字或一個長度為4的二進制序列。

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

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

當0≤t≤79時，

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

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

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

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

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

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

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

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

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

給定消息序列x和56位的密鑰k，構造相應的MAC的過程如下：

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

x=x1‖x2‖x3‖…‖xt

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

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

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

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

考慮到基于異或運算的流密碼的位運算會直接導致作為基礎明文的可預測變化，對流密