第3章單向散列函數(shù)

1、第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security第第3章章 單向散列函數(shù)單向散列函數(shù) 3.1 3.1 單向散列函數(shù)概述單向散列函數(shù)概述3.2 MD53.2 MD5算法算法3.3 SHA3.3 SHA家族家族3.4 3.4 消息認證碼消息認證碼(MAC)(MAC)3.5 3.5 對單向散列函數(shù)的攻擊對單向散列函數(shù)的攻擊第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 世界上很難找到兩個相同指紋的人，我們可用世界上很難找到兩個相同指紋的人，我們可用指紋指紋代代表一個人。如果把一條消息看成

2、一個人，消息的表一個人。如果把一條消息看成一個人，消息的散列散列值值就是指紋，由此我們可用散列值代表一條消息。就是指紋，由此我們可用散列值代表一條消息。 單向散列函數(shù)是數(shù)字簽名單向散列函數(shù)是數(shù)字簽名中的一個關(guān)鍵環(huán)節(jié)中的一個關(guān)鍵環(huán)節(jié), ,可以大大可以大大縮短簽名時間縮短簽名時間并提高安全性并提高安全性, ,另外在另外在消息完整性檢測消息完整性檢測, ,內(nèi)存的散布分配內(nèi)存的散布分配, ,軟件系統(tǒng)中軟件系統(tǒng)中帳號口令帳號口令的安全存儲，單的安全存儲，單向散列函數(shù)也有重要應(yīng)用。向散列函數(shù)也有重要應(yīng)用。 第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Securi

3、ty 單向散列函數(shù)是將單向散列函數(shù)是將一個消息一個消息以以不可逆的方式不可逆的方式將它轉(zhuǎn)換將它轉(zhuǎn)換成一段（通常更?。┏梢欢危ㄍǔ８。┟芪拿芪? 也可以簡單的理解為取一串也可以簡單的理解為取一串輸入碼（稱為消息），并把它們轉(zhuǎn)化為長度較短、位輸入碼（稱為消息），并把它們轉(zhuǎn)化為長度較短、位數(shù)固定的輸出序列即散列值（也稱為消息摘要）的過數(shù)固定的輸出序列即散列值（也稱為消息摘要）的過程。程。 散列函數(shù)值可以說是對明文的一種散列函數(shù)值可以說是對明文的一種“指紋指紋”或是或是“摘摘要要”，是明文的，是明文的壓縮版壓縮版，是明文的，是明文的映射映射，可看成是明，可看成是明文的文的代表代表，就是用，就是用小的

4、散列值小的散列值代表代表大的明文大的明文。 一小代大也有例外！像一小代大也有例外！像口令口令的散列存儲。的散列存儲。3.1 3.1 單向散列函數(shù)概述單向散列函數(shù)概述第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 所謂的所謂的單向散列函數(shù)單向散列函數(shù)(Hash Function(Hash Function，又稱哈希函數(shù)、雜，又稱哈希函數(shù)、雜湊函數(shù)湊函數(shù)) )，是將，是將任意長度的消息任意長度的消息M M映射成一個映射成一個固定長度散列固定長度散列值值h h( (設(shè)長度為設(shè)長度為m)m)的函數(shù)的函數(shù)H H： h=H(M)h=H(M) 散列函

5、數(shù)要具有單向性，則必須滿足如下特性：散列函數(shù)要具有單向性，則必須滿足如下特性： 給定給定M M，很容易計算，很容易計算h h。 給定給定h h，根據(jù)，根據(jù)H(M)=hH(M)=h反推反推M M很難。很難。 給定給定M M，要找到另一消息，要找到另一消息MM并滿足并滿足H(M)=H(M)H(M)=H(M)很難。很難。 在某些應(yīng)用中，單向散列函數(shù)還需要滿足抗碰撞在某些應(yīng)用中，單向散列函數(shù)還需要滿足抗碰撞(Collision)(Collision)的條件：要找到的條件：要找到兩個隨機的消息兩個隨機的消息M M和和MM，使，使H(M)=H(M)H(M)=H(M)很難。很難。 第第3 3章章 單向散列函

6、數(shù)單向散列函數(shù)Network and Information Security散列函數(shù)工作模式散列函數(shù)工作模式 消息分組1 消息分組2壓縮函數(shù)壓縮函數(shù)IV 消息分組n 填充位壓縮函數(shù)函數(shù)值圖3-1 單向散列函數(shù)工作模式第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 3.2.1 算法算法 MD表示消息摘要表示消息摘要(Message Digest)。MD5是是MD4的改進版，該算法對輸入的的改進版，該算法對輸入的任意長度消息產(chǎn)生任意長度消息產(chǎn)生128位散列值位散列值(或消息或消息摘要摘要) 。MD5算法可用圖算法可用圖3-2表示。表示。3

7、.2 MD5 算算 法法第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security圖3-2 MD5算法 2) 附加填充位附加填充位 3) 消息長度消息長度64 4) 初始化初始化MD緩沖區(qū)緩沖區(qū) 5) 輸出輸出 1) 按按512位的分組處位的分組處理輸入消息理輸入消息1000消息Kbit32bitN512bitL512bit512512bit512bit512128512128128IVCVL-1CV1128位消息摘要HMD5HMD5HMD5Y0Y1YL-1消息長度（K mod 264）填充位圖3-2 MD5算法第第3 3章章 單向散列函數(shù)單向散列

8、函數(shù)Network and Information Security 由上圖可知，由上圖可知，MD5MD5算法包括以下五個步驟。算法包括以下五個步驟。1) 1) 附加填充位附加填充位 首先填充消息，使其長度為一個比首先填充消息，使其長度為一個比512512的倍數(shù)小的倍數(shù)小6464位的數(shù)位的數(shù)。填充方法：在消。填充方法：在消息后面填充一位息后面填充一位1 1，然后填充所需數(shù)量的，然后填充所需數(shù)量的0 0。填充位的位數(shù)是。填充位的位數(shù)是1 1511511。 填充消息長度填充消息長度=512-(k+64) mod 512=512-(k+64) mod 5122)2)消息消息長度長度 將原消息長度的將

9、原消息長度的6464位表示附加在填充后的消息后面。位表示附加在填充后的消息后面。當原當原消息長度消息長度大于大于2 26464時，用消息長度時，用消息長度mod 2mod 26464填充。這時，填充。這時，總長度總長度恰好是恰好是512512的整數(shù)倍。令的整數(shù)倍。令M0 M0 1 1N N11為填充后消息的各個字為填充后消息的各個字( (每字為每字為3232位位) )，N N是是1616的倍數(shù)。的倍數(shù)。1 0 0 0消息K b i t3 2 b i tN5 1 2 b i tL5 1 2 b i t5 1 25 1 2 b i t5 1 2 b i t5 1 21 2 85 1 21 2 81

10、 2 8I VC VL - 1C V11 2 8 位消息摘要HMD 5HMD 5HMD 5Y0Y1YL - 1消息長度（K mo d 26 4）填充位圖3 - 2 MD 5 算法第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3) 初始化初始化MD緩沖區(qū)緩沖區(qū) 初始化用于計算消息摘要的初始化用于計算消息摘要的128位緩沖區(qū)。這個緩沖區(qū)由位緩沖區(qū)。這個緩沖區(qū)由四個四個32位寄存器位寄存器A A、B B、C C、D D表示。寄存器的初始化值為表示。寄存器的初始化值為(按低位字節(jié)在前的順序存放按低位字節(jié)在前的順序存放)： A: 01234567

11、 B: 89abcdef C: fedcba98 D: 76543210 4) 按按512位的分組處理輸入消息位的分組處理輸入消息 這一步為這一步為MD5的主循環(huán)，包括四輪，如圖的主循環(huán)，包括四輪，如圖3-3所示。每個循環(huán)都以當前的所示。每個循環(huán)都以當前的正在處理的正在處理的512比特分組比特分組Yq和和128比特緩沖值比特緩沖值A(chǔ)BCDABCD為輸入，然后更新緩沖內(nèi)容。為輸入，然后更新緩沖內(nèi)容。 1 0 0 0消息K b i t3 2 b itN5 1 2 b itL5 1 2 b i t5 1 25 1 2 b i t5 1 2 b i t5 1 21 2 85 1 21 2 81 2 8

12、I VC VL - 1C V11 2 8 位消息摘要HMD 5HMD 5HMD 5Y0Y1YL - 1消息長度（K m o d 26 4）填充位圖3 - 2 MD 5 算法第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security第四輪第三輪第二輪第一輪ABCDCVqYqABCDCVq1圖3-3 單個512比特分組的MD5主循環(huán)處理 第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 圖3-3中，四輪的操作類似，每一輪進行16次操作。各輪的操作過程如圖3-4所示。 圖3-4 MD5某一輪的1次執(zhí)

13、行過程 cs非線性函數(shù)bdaMjTicbdaj:015, i:164(共四輪， 每一次用的都不同)第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 四輪操作的不同之處在于每輪使用的非線性函數(shù)不同，在第一輪操作之前，首先把A、B、C、D復制到另外的變量a、b、c、d中。這四個非線性函數(shù)分別為(其輸入/輸出均為32位字)：F(X,Y,Z) = (X ? Y)? (X) ? Z)G(X,Y,Z) = (X ? Z) ?(Y ? (Z)H(X,Y,Z) = X Y ZI(X,Y,Z) = Y (X ?(Z) 其中， ?表示按位與； ?表示按位或；

14、表示按位反； 表示按位異或。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 此外，由圖3-4可知，這一步中還用到了一個有64個元素的表T1.64，Ti=232abs(sin(i)，i的單位為弧度。根據(jù)以上描述，將這一步驟的處理過程歸納如下：for i = 0 to N/161 do /* 每次循環(huán)處理16個字，即512字節(jié)的消息分組*/*把A存為AA，B存為BB，C存為CC，D存為DD*/AA = A BB = B CC = C DD = D第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Secu

15、rity /* 第一輪第一輪*/* 令令abcd k s i表示操作表示操作b = b + (a + F(b,c,d) + Mk + Ti) s)其中，其中，Ys表示表示Y循環(huán)左移循環(huán)左移s位位*/* 完成下列完成下列16個操作個操作*/ABCD 0 7 1 DABC 1 12 2 CDAB 2 17 3 BCDA 3 22 4ABCD 4 7 5 DABC 5 12 6 CDAB 6 17 7 BCDA 7 22 8ABCD 8 7 9 DABC 9 12 10 CDAB 10 17 11 BCDA 11 22 12ABCD 12 7 13 DABC 13 12 14 CDAB 14 17

16、15 BCDA 15 22 16第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security/* 第二輪第二輪*/*令令abcd k s i表示操作表示操作b = b + (a + G(b,c,d) + Mk + Ti) s)*/*完成下列完成下列16個操作個操作*/ABCD 1 5 17 DABC 6 9 18 CDAB 11 14 19 BCDA 0 20 20ABCD 5 5 21 DABC 10 9 22 CDAB 15 14 23 BCDA 4 20 24ABCD 9 5 25 DABC 14 9 26 CDAB 3 14 27 BCDA

17、8 20 28ABCD 13 5 29 DABC 2 9 30 CDAB 7 14 31 BCDA 12 20 32第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security/*第三輪第三輪*/*令令abcd k s t表示操作表示操作b= b + (a + H(b,c,d) + Mk + Ti) s)*/*完成以下完成以下16個操作個操作*/ABCD 5 4 33 DABC 8 11 34 CDAB 11 16 35 BCDA 14 23 36ABCD 1 4 37 DABC 4 11 38 CDAB 7 16 39 BCDA 10 23 40A

18、BCD 13 4 41 DABC 0 11 42 CDAB 3 16 43 BCDA 6 23 44ABCD 9 4 45 DABC 12 11 46 CDAB 15 16 47 BCDA 2 23 48 第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security/*第四輪第四輪*/*令令abcd k s t表示操作表示操作b = b + (a + I(b,c,d) +Mk + Ti) s) */*完成以下完成以下16個操作個操作*/ABCD 0 6 49 DABC 7 10 50 CDAB 14 15 51 BCDA 5 21 52ABCD 12

19、 6 53 DABC 3 10 54 CDAB 10 15 55 BCDA 1 21 56ABCD 8 6 57 DABC 15 10 58 CDAB 6 15 59 BCDA 13 21 60ABCD 4 6 61 DABC 11 10 62 CDAB 2 15 63 BCDA 9 21 64 A = A + AA B = B + BB C = C + CC D = D + DD end /*i循環(huán)*/第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 5) 輸出輸出 由由A、B、C、D四個寄存器四個寄存器的輸出按低位字的輸出按低位字節(jié)在

20、前的順序節(jié)在前的順序(即以即以A的低字節(jié)開始、的低字節(jié)開始、D的高字的高字節(jié)結(jié)束節(jié)結(jié)束)得到得到128位的消息摘要。位的消息摘要。 以上就是對以上就是對MD5算法的描述。算法的描述。MD5算法的算法的運算均為基本運算，比較容易實現(xiàn)且速度很快。運算均為基本運算，比較容易實現(xiàn)且速度很快。 第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.2.2 舉例舉例我們以求字符串我們以求字符串“abc”的的MD5散列值為例來說明上面描述的過程。散列值為例來說明上面描述的過程?！癮bc”的二進制表示為的二進制表示為01100001 01100010 01

21、100011。1填充消息填充消息消息長消息長24，先填充，先填充1位位1，然后填充，然后填充423位位0，再用消息長，再用消息長24，即，即0 x00000000 00000018填充，則：填充，則：M0=61626380 M1=00000000 M2=00000000 M3=00000000M4=00000000 M5=00000000 M6=00000000 M7=00000000M8=00000000 M9=00000000 M10=00000000 M11=00000000M12=00000000 M13=00000000 M14=00000000 M15=000000182初始化初始

22、化A: 0123 45 67B: 89ab cd efC: fedc ba 98D: 7654 32 103主循環(huán)主循環(huán)利用利用3.2.1節(jié)中描述的過程對字塊節(jié)中描述的過程對字塊1（本例只有一個字塊）進行處理。變量（本例只有一個字塊）進行處理。變量a、b、c、d每一次計每一次計算后的中間值不再詳細列出。算后的中間值不再詳細列出。4輸出輸出消息摘要消息摘要=90015098 3cd24fb0 d6963f7d 28e17f72第第3 3章章 單向散列函數(shù)單向散列函數(shù)問題問題 計算計算Hash的自變量由的自變量由3部分組成：部分組成： 消息本身消息本身+填充填充+消息本身長度消息本身長度 為什么不

23、是：為什么不是： 消息本身消息本身+消息本身長度消息本身長度+填充填充 Network and Information Security第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3 安全散列函數(shù)安全散列函數(shù)(SHA-1) 3.3.1 SHA家族家族 SHA (Secure Hash Algorithm，安全散列算法，安全散列算法) 家族是美國國家族是美國國家安全局家安全局 (NSA) 設(shè)計，美國國家標準與技術(shù)研究院設(shè)計，美國國家標準與技術(shù)研究院 (NIST) 發(fā)發(fā)布的一系列密碼散列函數(shù)。布的一系列密碼散列函數(shù)。 1993年發(fā)布年

24、發(fā)布SHA 家族的第一個成員（家族的第一個成員（SHA-0），），1995年發(fā)布年發(fā)布了了SHA-1。 SHA-1在許多安全協(xié)定中廣為使用，包括在許多安全協(xié)定中廣為使用，包括TLS和和SSL、PGP、SSH、S/MIME和和IPsec，曾被視為是，曾被視為是MD5的后繼者。的后繼者。 第第3 3章章 單向散列函數(shù)單向散列函數(shù)SHA-0和和SHA-1相繼被攻破和攻擊，相繼被攻破和攻擊，NIST 發(fā)布了另外四種變體發(fā)布了另外四種變體算法名稱算法名稱 輸 出輸 出 長長度度(bits) 分塊長度分塊長度 （bits） 最大消息最大消息長度長度(bits) 字長字長 (bits) 步數(shù)步數(shù)SHA-0

25、160 512 264-1 32 80 SHA-1 SHA-2 S H A -256/224 256/224 512 264-1 32 64 S H A -512/384 512/384 1024 2128-1 64 80 Network and Information Security SHA算法參數(shù)比較第第3 3章章 單向散列函數(shù)單向散列函數(shù)3.3.2 SHA-1算法算法Network and Information Security第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security SHA1SHA1的的輸入為長度輸入為長度小于小于26

26、4位的消息（若大于，位的消息（若大于， 用用mod mod 即可）即可），輸出為，輸出為160位的消息摘要。具體過位的消息摘要。具體過程如下。程如下。 1) 填充消息填充消息 首先將消息填充為首先將消息填充為512位的整數(shù)倍位的整數(shù)倍，填充方法和，填充方法和MD5完全相同：完全相同：先填充一個先填充一個1，然后填充一定數(shù)量，然后填充一定數(shù)量的的0，使其長度比，使其長度比512的倍數(shù)少的倍數(shù)少64位位；接下來用原；接下來用原消息長度的消息長度的64位表示填充。這樣，消息長度就成位表示填充。這樣，消息長度就成為為512的整數(shù)倍。以的整數(shù)倍。以M0、M1、Mn-1表示填充后表示填充后消息的各個字塊消

27、息的各個字塊(每字塊為每字塊為16個個32位字位字)。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 2) 初始化緩沖區(qū)初始化緩沖區(qū) 在運算過程中，在運算過程中，SHA要用到兩個緩沖區(qū)，要用到兩個緩沖區(qū)，兩個緩兩個緩沖區(qū)均有五個沖區(qū)均有五個32位的寄存器位的寄存器。第一個緩沖區(qū)標記為第一個緩沖區(qū)標記為A A、B B、C C、D D、E E；第二個緩沖區(qū)標記為；第二個緩沖區(qū)標記為H0、H1、H2、H3、H4。此外，運算過程中還用到一個標記為。此外，運算過程中還用到一個標記為W0、W1、W79的的80個個32位字序列和一個單字的緩沖區(qū)位字序

28、列和一個單字的緩沖區(qū)TEMP。在運算之前，初始化。在運算之前，初始化Hj： H0 = 0 x67452301 H1 = 0 xEFCDAB89 H2 = 0 x98BADCFE H3 = 0 x10325476 H4 = 0 xC3D2E1F0第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 3) 按按512位的分組處理輸入消息位的分組處理輸入消息 SHA運算主循環(huán)包括四輪，每輪運算主循環(huán)包括四輪，每輪20次操作。次操作。SHA用用到一個邏輯函數(shù)序列到一個邏輯函數(shù)序列f0、f1、f79。每個邏輯函數(shù)的。每個邏輯函數(shù)的輸入為輸入為三個三個3

29、2位字位字，輸出為一個，輸出為一個32位字。位字。定義如下(B、C、D均為32位字)：ft (B,C,D) = (B ? C) ?(B ? D) (0t19)ft (B,C,D) = B C D (20t39)ft (B,C,D) = (B ? C) ?(B ? D) ?(C ? D) (40t59)ft (B,C,D) = B C D (60t79) 其中，運算符的定義與其中，運算符的定義與3.1節(jié)中節(jié)中MD5運算中的相同。運算中的相同。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security SHA運算中還用到了運算中還用到了常數(shù)常數(shù)字序列字

30、序列K0、K1、K79，其值為，其值為 Kt = 0 x5A827999 (0t19) Kt = 0 x6ED9EBA1 (20t39) Kt = 0 x8F1BBCDC (40t59) Kt = 0 xCA62C1D6 (60t79)第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security SHA算法按如下步驟處理每個字塊算法按如下步驟處理每個字塊Mi： (1) 把把Mi分為分為16個字個字W0、W1、W15。 (2) for t =16 to 79 do let Wt =(Wt3 Wt8 Wt14 Wt16)1 (3) Let A =H0，B

31、 =H1，C =H2，D =H3，E =H4 (4) for t =0 to 79 do TEMP = (A5)+ft (B, C, D)+E +Wt +Kt ; E =D; D =C; C =(B30); B = A; A = TEMP; (5) Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E 4) 輸出輸出- 在處理完在處理完Mn后，后，160位的消息摘要為位的消息摘要為H0、H1、H2、H3、H4級聯(lián)的結(jié)果。級聯(lián)的結(jié)果。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Securit

32、y 3.3.3 舉例 我們以求字符串我們以求字符串a(chǎn)bc的的SHA1散列值為例來說明上散列值為例來說明上面描述的過程。面描述的過程。abc的二進制表示為的二進制表示為 a b c 01100001 01100010 01100011。(2) 初始化：初始化：H0 = 0 x67452301 H1 = 0 xEFCDAB89H2 = 0 x98BADCFE H3 = 0 x10325476H4 = 0 xC3D2E1F0 (1) 填充消息：消息長填充消息：消息長l=24，先填充，先填充1位位1，然后填充，然后填充423位位0，再用消息長再用消息長24，即，即0 x00000000 0000001

33、8（64位）位）填充。填充。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security (3) 主循環(huán)：處理消息字塊主循環(huán)：處理消息字塊1(本例中只有本例中只有1個字塊個字塊)，分成，分成16個字：個字： （01100001 01100010 01100011 24） W0=61626380 W1=00000000 W2=00000000 W3=00000000 W4=00000000 W5=00000000 W6=00000000 W7=00000000 W8=00000000 W9=00000000 W10=00000000 W11=00000

34、000 W12=00000000 W13=00000000 W14=00000000 W15=00000018 然后根據(jù)然后根據(jù)3.2.1節(jié)中描述的過程計算，其中，循環(huán)節(jié)中描述的過程計算，其中，循環(huán)“for t = 0 to 79”中，各步中，各步A、B、C、D、E的值如下：的值如下：第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security A B C D Et = 0: 0116FC3367452301 7BF36AE2 98BADCFE 10325476t = 1: 8990536D0116FC33 59D148C0 7BF36AE2 98B

35、ADCFEt = 2: A1390F088990536D C045BF0C 59D148C0 7BF36AE2t = 3: CDD8E11BA1390F08 626414DB C045BF0C 59D148C0t = 4: CFD499DECDD8E11B 284E43C2 626414DB C045BF0Ct = 5: 3FC7CA40 CFD499DE F3763846 284E43C2 626414DBt = 6: 993E30C1 3FC7CA40 B3F52677 F3763846 284E43C2t = 7: 9E8C07D4 993E30C1 0FF1F290 B3F52677

36、F3763846t = 8: 4B6AE328 9E8C07D4 664F8C30 0FF1F290 B3F52677t = 9: 8351F929 4B6AE328 27A301F5 664F8C30 0FF1F290t =10: FBDA9E89 8351F929 12DAB8CA 27A301F5 664F8C30第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 字塊1處理完后，Hi的值為： H0 = 67452301 + 42541B35 = A9993E36 H1 = EFCDAB89 + 5738D5E1 = 4706816A

37、 H2 = 98BADCFE + 21834873 = BA3E2571 H3 = 10325476 + 681E6DF6 = 7850C26C H4 = C3D2E1F0 + D8FDF6AD = 9CD0D89D (4) 輸出：消息摘要 = A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D也就是說abc的散列函數(shù)值為：第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3.4 SHA1與MD5的比較SHA1與MD5的比較如表 所示。 SHA-1MD5Hash值長度160 bit128 bit分組

38、處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3.3 SHA1與MD5的比較SHA1與MD5的比較如表3-1所示。表3-1 SHA-1與MD5的比較 SHA-1MD5Hash值長度160 bit128 bit分組處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464第第3 3章章 單向散列函

39、數(shù)單向散列函數(shù)Network and Information Security3.3.3 SHA1與MD5的比較SHA1與MD5的比較如表3-1所示。表3-1 SHA-1與MD5的比較 SHA-1MD5Hash值長度160 bit128 bit分組處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3.3 SHA1與MD5的比較SHA1與MD5的比較如表3-1所示。表3-1 SHA-1與MD

40、5的比較 SHA-1MD5Hash值長度160 bit128 bit分組處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3.3 SHA1與MD5的比較SHA1與MD5的比較如表3-1所示。表3-1 SHA-1與MD5的比較 SHA-1MD5Hash值長度160 bit128 bit分組處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函

41、數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.3.4 SHA1與MD5的比較SHA1與MD5的比較如表3-1所示。表3-1 SHA-1與MD5的比較 SHA-1MD5Hash值長度160 bit128 bit分組處理長度512 bit512 bit步數(shù)80(420)64(416)最大消息長264 bit不限非線性函數(shù)3(第第2、4輪輪相同相同)4常數(shù)個數(shù)464ft (B,C,D) = (B ? C) ?(B ? D) (0t19)ft (B,C,D) = B C D (20t39)ft

42、(B,C,D) = (B ? C) ?(B ? D) ?(C ? D) (40t59)ft (B,C,D) = B C D (60t79)F(X,Y,Z) = (X ? Y)? (X) ? Z)G(X,Y,Z) = (X ? Z) ?(Y ? (Z)H(X,Y,Z) = X Y ZI(X,Y,Z) = Y (X ?(Z)第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security根據(jù)各項特征，簡要地說明它們間的不同。根據(jù)各項特征，簡要地說明它們間的不同。（1 1）安全性：）安全性：SHA-1SHA-1所產(chǎn)生的摘要較所產(chǎn)生的摘要較MD5MD5長長323

43、2位。若兩種位。若兩種散列函數(shù)在結(jié)構(gòu)上沒有任何問題的話，散列函數(shù)在結(jié)構(gòu)上沒有任何問題的話，SHA-1SHA-1比比MD5MD5更更安全。安全。（2 2）速度：兩種方法都考慮了以）速度：兩種方法都考慮了以3232位處理器為基礎(chǔ)的系位處理器為基礎(chǔ)的系統(tǒng)結(jié)構(gòu)，但統(tǒng)結(jié)構(gòu)，但SHA-1SHA-1的運算步驟較的運算步驟較MD5MD5多了多了1616步，而且步，而且SHA-1SHA-1記錄單元的長度較記錄單元的長度較MD5MD5多了多了3232位。因此若是以位。因此若是以硬硬件來實現(xiàn)件來實現(xiàn)SHA-1SHA-1，其速度大約較，其速度大約較MD5MD5慢慢25%25%。（3 3）簡易性：兩種方法都相當?shù)暮唵危?/p>

44、在實現(xiàn)上不需要）簡易性：兩種方法都相當?shù)暮唵危趯崿F(xiàn)上不需要很復雜的程序或是大量的存儲空間。然而總體上來講，很復雜的程序或是大量的存儲空間。然而總體上來講，SHA-1SHA-1每一步的操作都較每一步的操作都較MD5MD5簡單簡單。 第第3 3章章 單向散列函數(shù)單向散列函數(shù)3.3.5 SHA-512算法算法 SHA-512輸出消息摘要的長度為輸出消息摘要的長度為512位。位。輸入輸入被處理成被處理成1024位的塊位的塊 ，處理過程由以下步驟組，處理過程由以下步驟組成：成：Network and Information Security第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and

45、 Information Security（2）填加長度。 填充后 消息的長度恰為1024bit的整數(shù)倍。（1）填充。若k是消息長度，則計算填充消息長度的公式是：1024-（k+128）mod 1024 ，128位用來放消息長度。（4）以1024bit的塊(16個字)為單位處理消息，算法的核心是具有80輪運算的模塊（3）初始Hash緩沖區(qū)。一個512bit的塊用于保存Hash函數(shù)的中間值和最終結(jié)果。該緩沖區(qū)用8個64bit的寄存器（5）輸出。所有的N個1024bit分組都處理完以后，從第N階段輸出的是512bit的消息摘要。第第3 3章章 單向散列函數(shù)單向散列函數(shù)（4）以）以1024bit塊塊

46、(16個字個字)為單位處理消息為單位處理消息，算法的核心算法的核心是具有是具有80輪運算的模塊輪運算的模塊 。 第一輪，緩沖區(qū)里的值是中間的散列第一輪，緩沖區(qū)里的值是中間的散列值值Hi-1。每一輪，如每一輪，如t輪，使用一個輪，使用一個64bit的值的值Wt，其中，其中0t79表示輪數(shù)，該值由當表示輪數(shù)，該值由當前被處理的前被處理的1024bit消息分組消息分組Mi導出。導出。每一輪還將使用附加的常數(shù)每一輪還將使用附加的常數(shù)Kt。常數(shù)獲得：前常數(shù)獲得：前80個素數(shù)取三次方根，個素數(shù)取三次方根，取小數(shù)部分的前取小數(shù)部分的前64bit。第第80輪的輸出和第一輪輸入輪的輸出和第一輪輸入Hi-1相加產(chǎn)

47、相加產(chǎn)生生Hi。緩沖區(qū)里的緩沖區(qū)里的8個字和個字和Hi-1里的相應(yīng)字獨里的相應(yīng)字獨立進行模立進行模264的加法運算。的加法運算。Network and Information Security第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information SecurityHashHash函數(shù)在函數(shù)在WebWeb信息系統(tǒng)中的應(yīng)用信息系統(tǒng)中的應(yīng)用身份認證身份認證用戶注冊時第一次設(shè)置密碼（用戶注冊時第一次設(shè)置密碼（passwordpassword）, ,密碼不直接寫數(shù)據(jù)密碼不直接寫數(shù)據(jù)庫。？庫。？系統(tǒng)用系統(tǒng)用HashHash函數(shù)計算函數(shù)計算用戶密碼用戶密碼的的HashHash

48、值，并保存到數(shù)據(jù)庫中。值，并保存到數(shù)據(jù)庫中。以后用戶登錄系統(tǒng)時，用戶輸入密碼后，以后用戶登錄系統(tǒng)時，用戶輸入密碼后， 系統(tǒng)首先計算它的系統(tǒng)首先計算它的HashHash值，值，然后從然后從數(shù)據(jù)庫中取出對應(yīng)的數(shù)據(jù)庫中取出對應(yīng)的HashHash值與其比較，值與其比較， 若若相同相同視為合法用戶，視為合法用戶， 否則不合法否則不合法。合法用戶允許訪問系統(tǒng)，合法用戶允許訪問系統(tǒng)， 不合法不能訪問系統(tǒng)。不合法不能訪問系統(tǒng)。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security用戶用戶+密碼密碼 這種身份認證方式這種身份認證方式簡單、簡單、 高效，但安全性不

49、高效，但安全性不是很高。是很高。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.4 消息認證碼消息認證碼(MAC) 目前的認證技術(shù)有對用戶的認證和對消息的認證兩種方式。 1 用戶認證用于鑒別用戶的身份是否是合法用戶； 2 消息認證就是驗證所收到的消息確實是來自真正的發(fā)送方且未被修改的消息，也可以驗證消息的順序和及時性。 消息認證實際上是對消息本身產(chǎn)生一個冗余的信息MAC（Message Authentication Code，消息認證碼）附加在消息后面。 其組成是：消息+消息認證碼，以認證消息的完整性 第第3 3章章 單向散列函數(shù)單向

50、散列函數(shù)Network and Information Security3.4.1 消息認證碼基本概念消息認證碼基本概念 與與密鑰相關(guān)密鑰相關(guān)的的單向散列函數(shù)單向散列函數(shù)通常稱為通常稱為MAC，即消息，即消息認證碼：認證碼：MAC=CK(M) 其中，其中，M為可變長的消息；為可變長的消息；K為通信雙方共享的密為通信雙方共享的密鑰鑰；C為單向函數(shù)。為單向函數(shù)。 MAC可為擁有可為擁有共享密鑰的雙方共享密鑰的雙方在通信中在通信中驗證消息的驗證消息的完整性完整性；也可被；也可被單個用戶單個用戶用來驗證他的用來驗證他的文件是否被改動文件是否被改動 。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Networ

51、k and Information Security圖3-6 MAC應(yīng)用于消息認證 M H K M H K 比較 C K (M) 發(fā)送端 接收端 M C K (M) 若若沒有沒有K， 能否驗證消息的完整性？能否驗證消息的完整性？不能不能如攻擊者將消息如攻擊者將消息M 和摘要和摘要都替換了都替換了，將不能驗證，將不能驗證原消息原消息的完整性的完整性3.4.2 消息的完整性驗證消息的完整性驗證第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security RFC 2104RFC 2104定義的定義的全稱為全稱為Keyed-Hash Message Auth

52、entication Code，它用一個秘密密鑰來產(chǎn)，它用一個秘密密鑰來產(chǎn)生和驗證生和驗證MAC小知識：小知識：Request For Comments（RFC）文件是由）文件是由Internet Society（ISOC）贊助發(fā)行?；镜模┵澲l(fā)行?；镜幕ヂ?lián)網(wǎng)通信協(xié)議互聯(lián)網(wǎng)通信協(xié)議在在RFC文件內(nèi)都有詳文件內(nèi)都有詳細說明。幾乎所有的細說明。幾乎所有的互聯(lián)網(wǎng)標準互聯(lián)網(wǎng)標準都收錄在都收錄在RFC文件之中。文件之中。3.4.3 HMAC3.4.3 HMAC算法算法第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security圖3-7 HMAC結(jié)構(gòu)將數(shù)值將

53、數(shù)值0 x36重復重復B次。次。 B:計算消息摘要時輸入塊的字節(jié)長度計算消息摘要時輸入塊的字節(jié)長度 將數(shù)值0 x5c重復B次 在在密密鑰鑰K的的左左邊邊項項加加0 ipad K0 Si text opad S0 HASH HASH t bit MAC(text)t L 字節(jié) B 字節(jié) 最左邊最左邊t字節(jié)作為字節(jié)作為MAC第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security由圖可知，由圖可知，HMAC執(zhí)行的是如下操作：執(zhí)行的是如下操作：MAC(text)t = HMAC(K, text)t = H(K0 opad )| H(K0 ipad) |

54、 text)t具體操作步驟如下：具體操作步驟如下：(1) 如果如果K的長度的長度等于等于B，設(shè)置，設(shè)置K0 = K并跳轉(zhuǎn)到第并跳轉(zhuǎn)到第(4)步。步。(2) 如果如果K的長度的長度大于大于B，對，對K求散列值：求散列值：K0 = H(K)。(3) 如果如果K的長度的長度小于小于B，在，在K的左邊附加的左邊附加0得到得到B字節(jié)的字節(jié)的K0。(4) 執(zhí)行執(zhí)行K0 ipad。ipadK0SitextopadS0HASHHASHt bitMAC(text)tL字節(jié)B字節(jié)第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security(5) 將數(shù)據(jù)將數(shù)據(jù)text附加

55、在第附加在第(4)步結(jié)果的后面：步結(jié)果的后面：(K0 ipad) | text(6) 將將H應(yīng)用于第應(yīng)用于第(5)步的結(jié)果：步的結(jié)果：H(K0 ipad) | text)(7) 執(zhí)行執(zhí)行K0 opad。(8) 把第把第(6)步的結(jié)果附加在第步的結(jié)果附加在第(7)步的結(jié)果步的結(jié)果后面：后面：(K0 opad) | H(K0 ipad) | text)第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security (9) 將將H應(yīng)用于第應(yīng)用于第(8)步的結(jié)果：步的結(jié)果：H(K0 opad )| H(K0 ipad) | text) (10) 選擇第選擇第(

56、9)步結(jié)果的最左邊步結(jié)果的最左邊t字節(jié)作字節(jié)作為為MAC。 HMAC算法可以和任何密碼散列函算法可以和任何密碼散列函數(shù)結(jié)合使用，而且對數(shù)結(jié)合使用，而且對HMAC實現(xiàn)作很小實現(xiàn)作很小的修改就可用一個散列函數(shù)的修改就可用一個散列函數(shù)H代替原來代替原來的散列函數(shù)的散列函數(shù)H。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.5 對單向散列函數(shù)的攻擊 對單向散列函數(shù)攻擊的目的對單向散列函數(shù)攻擊的目的在于破壞單在于破壞單向散列函數(shù)的某些特性向散列函數(shù)的某些特性. 比如可以根據(jù)比如可以根據(jù)輸出輸出求得求得輸入輸入，找到一條，找到一條新消息使它的輸出

57、新消息使它的輸出與與原消息的輸出原消息的輸出相同，相同，或者或者找到不同的兩個消息找到不同的兩個消息，使它們的，使它們的輸輸出相同出相同。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security3.5.1 3.5.1 字典攻擊字典攻擊 字典攻擊字典攻擊，對用，對用單向散列函數(shù)加密的口令文件特別有效。單向散列函數(shù)加密的口令文件特別有效。 攻擊者攻擊者編制含有多達幾十萬個常用口令的表編制含有多達幾十萬個常用口令的表，然后用，然后用單向單向散列函數(shù)散列函數(shù)對對所有口令所有口令進行運算，并將結(jié)果存儲到文件中。進行運算，并將結(jié)果存儲到文件中。 攻擊者攻擊者

58、非法非法獲得加密的獲得加密的口令文件口令文件后，將比較這兩個文件，后，將比較這兩個文件，觀察是否有觀察是否有匹配匹配的口令密文。的口令密文。 字典式攻擊，成功率非常高。這是因為大多數(shù)人缺乏安全字典式攻擊，成功率非常高。這是因為大多數(shù)人缺乏安全意識和想象力，選擇的口令過于簡單。編制巨大的口令表意識和想象力，選擇的口令過于簡單。編制巨大的口令表是個問題嗎？是個問題嗎？ 從網(wǎng)上就能找到，熱心的從網(wǎng)上就能找到，熱心的黑客們黑客們已經(jīng)把它完善得很好了。已經(jīng)把它完善得很好了。第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and Information Security 1 1、Salt(Salt

59、(添加符添加符) )是使這種攻擊更困難的一種方法。是使這種攻擊更困難的一種方法。 SaltSalt是一隨機字符串，它與口令連接在一起，再用單向散列函數(shù)對其是一隨機字符串，它與口令連接在一起，再用單向散列函數(shù)對其運算運算。然后將。然后將SaltSalt值和單向散列函數(shù)運算的結(jié)果存入主機數(shù)據(jù)庫中。值和單向散列函數(shù)運算的結(jié)果存入主機數(shù)據(jù)庫中。攻擊者必須對攻擊者必須對所有可能的所有可能的SaltSalt值值進行計算。進行計算。如果如果SaltSalt的長度為的長度為6464比比特，那么攻擊者的預計算量就增大了特，那么攻擊者的預計算量就增大了2 26464倍，同時存儲量也增大了倍，同時存儲量也增大了2

60、26464倍，使得字典攻擊幾乎不可能。倍，使得字典攻擊幾乎不可能。如果攻擊者得知如果攻擊者得知SaltSalt值后進行攻擊，那就不得不重新計算所有可能值后進行攻擊，那就不得不重新計算所有可能的口令，仍然是比較困難的。的口令，仍然是比較困難的。 2 2、另一個對策是、另一個對策是增加增加單向散列函數(shù)處理次數(shù)單向散列函數(shù)處理次數(shù)。比如可以對口令用單向。比如可以對口令用單向散列函數(shù)處理散列函數(shù)處理1010次，這就大大增加了攻擊者的預計算次，這就大大增加了攻擊者的預計算時間，但對正常時間，但對正常用戶沒有用戶沒有明顯影響明顯影響。對策第第3 3章章 單向散列函數(shù)單向散列函數(shù)Network and In