第8章Hash函數Hash函數定義數據安全機密性完整性認證性密碼技術主要保證數據的機密性Hash函數能保證數據的完整性和認證性Hash函數定義Hash函數常用來構造數據的短“指紋”：消息的發送者使用所有的消息產生一個附件也就是短“指紋”，并將該短“指紋”與消息一起傳輸給接收者。即使數據存儲在不安全的地方，接收者重新計算數據的指紋，并驗證指紋是否改變，就能夠檢測數據的完整性。這是因為一旦數據在中途被破壞，或改變，短指紋就不再正確。

Hash函數定義Hash函數定義：Hash函數是一個將任意長度的消息（message）映射成固定長度消息的函數。Hash函數是一個函數，它以一個變長的報文作為輸入，并產生一個定長的散列碼，有時也稱為報文摘要，作為函數的輸出。Hash函數（hashfunction），或稱為哈希函數、散列函數。對于任何消息x，將h(x)稱為x的Hash值、散列值、消息摘要（messagedigest）。Hash函數作用Hash函數最主要的作用于是用于鑒別，鑒別在網絡安全中起到舉足輕重的地位。鑒別的目的有以下兩個：第一，驗證信息的發送者是真正的，而不是冒充的，同時發信息者也不能抵賴，此為信源識別；第二，驗證信息完整性，在傳遞或存儲過程中未被篡改，重放或延遲等。

8.1Hash函數的性質Hash函數的碰撞（collision）

設x、x’是兩個不同的消息，如果

h(x)=h(x’)

則稱x和x’是Hash函數h的一個（對）碰撞.8.1Hash函數的性質Hash函數的分類單向Hash函數（one

way）給定一個Hash值y，如果尋找一個消息x，使得y=h(x)是計算上不可行的，則稱h是單向Hash函數.弱抗碰撞Hash函數（weaklycollision

free）任給一個消息x，如果尋找另一個不同的消息x’，使得h(x)=h(x’)是計算上不可行的，則稱h是弱抗碰撞Hash函數.強抗碰撞Hash函數（stronglycollision

free）如果尋找兩個不同的消息x和x’，使得h(x)=h(x’)是計算上不可行的，則稱h是強抗碰撞Hash函數.8.1Hash函數的性質hash函數在現代密碼學中起著重要的作用，主要用于對數據完整性和消息認證壓縮性：任意長度的數據，算出的摘要長度都固定。容易計算：從原數據容易算出摘要。抗修改性：對原數據進行任何改動，哪怕只修改1個字節，所得到的摘要都有很大區別。弱抗碰撞：已知原數據和其摘要，想找到一個具有相同摘要的數據（即偽造數據），在計算上是困難的。強抗碰撞：想找到兩個不同的數據，使它們具有相同的摘要，在計算上是困難的。Hash函數的安全性對Hash函數的攻擊是指尋找一對碰撞消息的過程與傳統密碼體制的攻擊方式相比，對散列函數的攻擊方法主要有兩種：窮舉攻擊：它可以用于任何類型的散列函數的攻擊，最典型的方式就是所謂的“生日攻擊”。采用生日攻擊的攻擊者將產生許多明文消息，然后計算這些明文消息的指紋（摘要），進行比較。利用散列函數的代數結構：攻擊其函數的弱性質。通常的有中間相遇攻擊、修正分組攻擊和差分分析攻擊等。生日悖論（birthdayparadox）生日問題：假設每個人的生日是等概率的，每年有365天，在k個人中至少有兩個人的生日相同的概率大于1/2，問k最小應是多少？

k人生日都不同的概率是：

有P(365,23)=0.5073。即在23個人中，至少有兩個人生日相同的概率大于0.5，這個數字比人們直觀猜測的結果小得多，因而稱為生日悖論。生日攻擊法生日悖論原理可以用于構造對Hash函數的攻擊設Hash函數值有n個比特，m是真消息，M是偽造的假消息，分別把消息m和M表示成r和R個變形的消息。消息與其變形消息具有不同的形式，但有相同的含義。將消息表示成變形消息的方法很多，例如增加空格、使用縮寫、使用意義相同的單詞、去掉不必要的單詞等。Hash函數的安全性Hash函數的安全性生日攻擊法分別把消息m和M表示成r和R個變形的消息生日攻擊法計算真消息m的變形與假消息M的變形發生碰撞的概率由于n比特長的散列值共有2n個，所以對于給定m的變形mi和M的變形Mj，mi與Mj不碰撞的概率是1-1/2n。由于M共有R個變形，所以M的全部變形都不與mi碰撞的概率是：

Hash函數的安全性因為消息m共有r個變形，因此m的變形與M的變形都不碰撞的概率是：m的變形與M的變形發生碰撞的概率是：生日攻擊法當r=R=2n/2時，P(n)=1

e

1

0.63。對于Hash值長度為64比特的Hash函數，生日攻擊的時間復雜度約為232，所以是不安全的。為了抵抗生日攻擊，建議Hash值長度至少為128比特.Hash函數的安全性8.2基于分組密碼的Hash函數基于分組密碼的CBC工作模式的Hash函數H首先選取一個初始向量令然后計算基于分組密碼的CFB工作模式的Hash函數H令然后計算首先選取一個初始向量8.3hash函數MD4MD4是麻省理工學院教授RonaldRivest于1990年設計的一種信息摘要算法。它是一種用來測試信息完整性的密碼散列函數的實行。其摘要長度為128位。這個算法影響了后來的算法如MD5、SHA家族和RIPEMD等。

MD5算法是1991年發布的一項數字簽名加密算法，它當時解決了MD4算法的安全性缺陷，成為應用非常廣泛的一種算法。8.3hash函數MD4MD4算法的輸入可以是任意長度的消息x，對輸入消息按512位的分組為單位進行處理，輸出128位的散列值MD(x)。整個算法分為五個步驟。步驟1:增加填充位步驟2:附加消息長度值步驟3:初始化MD緩沖區步驟4:以512位的分組(16個字)為單位處理消息步驟5:輸出消息的預處理步驟：設x是一個消息,用二進制表示。首先由x生成一個數組是長度為32比特(bit)的(0,1)序列,M由x生成：①d=(447-|x|)mod512②令l為的二進制表示。l的長度為64比特(bit)。如果l的長度不足64比特(bit),則在l的左端添0補足③M=這里|x|表示x的長度,||表示序列的聯接,譬如x||y

表示將序列y排在序列x的右端。步驟1:增加填充位在消息x右邊增加若干比特，使其長度與448模512同余。也就是說，填充后的消息長度比512的某個倍數少64位。即使消息本身已經滿足上述長度要求，仍然需要進行填充。例如，若消息長為448，則仍需要填充512位使其長度為960位。填充位數在1到512之間。填充比特的第一位是1，其它均為0。步驟2:附加消息長度值

用64位表示原始消息x的長度，并將其附加在步驟1所得結果之后。若填充前消息長度大于等于264，則使用其64位。填充方法是把64比特的長度分成兩個32比特的字，低32比特字先填充，高32比特字后填充。步驟1與步驟2一起稱為消息的預處理

經預處理后，原消息長度變為512的倍數設原消息x經預處理后變為消息

Y=Y0Y1…YN

1，其中Yi（i=0,1,…,N

1）是32比特在后面的步驟中，將對512比特的分組Yi進行處理例8.1

假設消息為:

x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.步驟1在x的右邊填充1個“1”和407個“0”，將x變成448比特的x1:x1=x||1||0(407個)=x||8000000000000000000000

00000000

00000000

00000000000000000000000000000000

00000000

0000000000000000

00000000.=61626364658000000000000000000000

00000000

00000000

0000000000000000

00000000

00000000

00000000

00000000

0000000000000000.例8.1

假設消息為:

x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.經步驟2處理后的比特串為（16進制表示）：x2=x1||28(64位)=61626364658000000000000000000000

00000000

00000000

00000000

00000000

000000000000000000000000

00000000

00000000

000000002800000000000000.步驟3:初始化MD緩沖區

MD4算法的中間結果和最終結果都保存在128位的緩沖區里，緩沖區用4個32位的寄存器表示。4個緩沖區記為A、B、C、D，其初始值為下列32位整數（16進制表示）：

A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476.上述初始值以小端格式存儲(字的最低有效字節存儲在低地址位置)為：字A=01234567,字B=89ABCDEF,

字C=FEDCBA98,字D=76543210.步驟4:以512位的分組(16個字)為單位處理消息

MD4是迭代Hash函數,其壓縮函數為:步驟4是MD4算法的主循環，它以512比特作為分組，重復應用壓縮函數HMD4，從消息Y的第一個分組Y0開始，依次對每16個分組Yi進行壓縮，直至最后分組N/16-1，然后輸出消息x的Hash值?？梢?，MD4的循環次數等于消息Y中512比特分組的數目L。步驟5:輸出依次對消息的L個512比特的分組進行處理，第L個分組處理后的輸出值即是消息x的散列值MD(x)。8.3Hash函數MD4MD4算法如下①設A、B、C、D是四個32位的寄存器,其初值(用十六進制表示)分別為A=67452301、B=efcdab89、C=98badcfe、D=10325476:②對i=0至N/16-1執行第3步至第8步③對j=0至15執行X[j]=M[16i+j]④將寄存器A、B、C、D中的值存儲到另外四個寄存器AA、BB、CC、DD中,AA=A，BB=B，CC=C，DD=D⑤執行Round1⑥執行Round2⑦執行Round3⑧A=A+AA，B=B+BB，C=C+CC，D=D+DD點此查看Round1點此查看Round2點此查看Round38.4安全Hash算法SHA安全Hash算法SHA（securehashalgorithm）由美國標準與技術研究所（NIST）設計并于1993年作為聯邦信息處理標準（FIPS180）發布修改版于1995年發布（FIPS180

1），通常稱之為SHA

1。該標準稱為安全Hash函數。RFC3174也給出了SHA

1，它基本上是復制FIPS180

1的內容，但增加了C代碼實現。SHA

1算法的輸入是長度小于264的任意消息x，輸出160位的散列值。8.4安全Hash算法SHASHA

1處理消息的過程與MD4類似，對輸入消息按512位的分組為單位進行處理，整個算法分為五個步驟步驟1:增加填充位

在消息右邊增加若干比特，使其長度與448模512同余。即使消息本身已經滿足上述長度要求，仍然需要進行填充。填充位數在1到512之間。填充比特的第一位是“1”，其它均為“0”。8.4安全Hash算法SHA步驟2:附加消息長度值

用64位表示原始消息x的長度，并將其附加在步驟1所得結果之后。步驟1與步驟2一起稱為消息的預處理

經預處理后，原消息長度變為512的倍數。設原消息x經預處理后變為消息M=M0M1…MN

1，其中Mi（i=0,1,…,N

1）是32比特。在后面的步驟中，將對512比特的分組進行處理。8.4安全Hash算法SHA步驟3:初始化緩沖區

SHA

1算法的中間結果和最終結果保存在160位的緩沖區里，緩沖區用5個32位的寄存器表示。5個緩沖區記為A、B、C、D、E，其初始值為下列32位整數（16進制表示）：

A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476,E=C3D2E1F0.

其中，前4個初始值與MD5的初始值相同。SHA

1以大端格式存儲緩沖區的值，即字的最高有效字節存于低地址字節位置。因此，上述初始值存儲為（十六進制）：字A=67452301,字B=EFCDAB89,字C=98BADCFE,

字D=10325476,字E=C3D2E1F0.8.4安全Hash算法SHA步驟4:以512位的分組（16個字）為單位處理消息SHA

1是迭代Hash函數，其壓縮函數為：步驟4是SHA

1算法的主循環，它以512比特作為分組，重復應用壓縮函數HSHA，從消息的第一個分組開始，依次對每個分組進行壓縮，直至最后分組，然后輸出消息x的Hash值。SHA

1循環次數等于消息中512比特分組的數目L。SHA

1的

壓縮函數HSHA

由四輪處理組成加法是模232相加CVi

(160)Yi(512)BCDAEf4,K4,W[60,61,…,79],20步BCDAEf2,K2,W[20,21,…,39],20步BCDAEf3,K3,W[40,41,…,59],20步BCDAEf1,K1,W[0,1,…,19],20步

+

+

+

+

+CVi+1

(160)SHA

1的壓縮函數HSHA

壓縮函數HSHA的四輪處理過程的算法結構相同，每一輪要對緩沖區ABCDE進行20次迭代，每次迭代的運算形式為

TEMP=(A<<5)+ft(B,C,D)+E+X[k]+Kt

E=DD=CC=B<<30B=AA=TEMPSHA

1的壓縮函數HSHA

基本邏輯函數f每一輪使用一個基本邏輯函數f，每個基本邏輯函數的輸入是三個32位的字，輸出是一個32位的字，它執行位邏輯運算，即輸出的第n位是其三個輸入第n位的函數。輪數基本邏輯函數ff(B,C,D)1234f1(B,C,D)f2(B,C,D)f3(B,C,D)f4(B,C,D)SHA

1的壓縮函數HSHA

字組Xt

t（0≤t≤79）代表迭代步數，依次表示第一、二、三、四輪處理過程進行的迭代次序Xt(0≤t≤79)是32比特的字，它的前面16個字X0,X1,…,X15依次取自當前輸入分組Mi，其余字為加法常數表Kt迭代步數十六進制十進制0

t

1920t

3940t

5960t

795A8279996ED9EBA18F1BBCDCCA62C1D68.4安全Hash算法SHA步驟5:輸出第N/16個分組處理后的輸出值即是消息x的散列值MD(x)8.4安全Hash算法SHASHA-1算法如下①設A、B、C、D、E是5個32位的寄存器,其初值(用十六進制表示)分別為A=67452301、B=efcdab89、C=98badcfe、D=10325476、E=c3d2e1f0②對i=0至N/16-1執行第3步至第10步③對j=0至15執行X[j]=M[16i+j]⑤將寄存器A、B、C、D、E中的值存儲到另外四個寄存器AA、BB、CC、DD中,AA=A，BB=B，CC=C，DD=D，EE=E⑥執行Round1⑦執行Round2⑧執行Round3⑩A=A+AA，B=B+BB，C=C+C