Hash函數(shù)分解課件

1、 第七章 雜 湊 函 數(shù)第1頁，共38頁。雜湊函數(shù)(Hash函數(shù)）雜湊函數(shù)是密碼學(xué)的一個基本工具，在數(shù)字簽名、身份認證和消息的完整性檢測等方面有著重要的應(yīng)用雜湊函數(shù)H是一公開函數(shù)，用于將任意長的消息M映射為較短的、固定長度的一個值H(M)，作為認證符，稱函數(shù)值H(M)為雜湊值、雜湊碼或消息摘要。雜湊碼是消息中所有比特的函數(shù)，因此提供了一種錯誤檢測能力，即改變消息中任何一個比特或幾個比特都會使雜湊碼發(fā)生改變。特點：H 打上了輸入數(shù)字串的烙印，為數(shù)字指紋(Digital Finger Print)第2頁，共38頁。散列函數(shù)的性質(zhì) （1）一般雜湊函數(shù)h(m)算法公開，不需要密鑰 （2）具有數(shù)據(jù)壓縮功

2、能，可將任意長度的輸入數(shù)據(jù)轉(zhuǎn)換成一個固定長度的輸出。 （3）對任何給定的m，h(m)易于計算。第3頁，共38頁。Hash函數(shù)的應(yīng)用 在密碼學(xué)和數(shù)據(jù)安全技術(shù)中，它是實現(xiàn)有效、安全可靠數(shù)字簽字和認證的重要工具，是安全認證協(xié)議中的重要模塊。第4頁，共38頁。Hash函數(shù)的應(yīng)用注：實際應(yīng)用中，未必一定是如h(mk)的計算方式，明文與密鑰k的組合方式因不同的實現(xiàn)可以不同。 第5頁，共38頁。單向雜湊函數(shù)要求密碼學(xué)中所用的雜湊函數(shù)必須滿足一定安全性的要求，要能防偽造，抗擊各種類型的攻擊，如生日攻擊、中途相遇攻擊等等。安全要求：（1）具有單向性。給定消息的散列值h(m)，要得到消息m在計算上不可行；（2）具

3、有弱抗碰撞性（Weak collision resistance）。對任何給定的消息m，尋找與m不同的消息m，使得它們的散列值相同，即h(m)h (m)，在計算上不可行。 （3）具有強抗碰撞性（Strong collision resistance) 。尋找任意兩個不同的消息m和m， 使得h(m)h (m) 在計算上不可行。第6頁，共38頁。H是多對一映射雜湊函數(shù)是多對一映射，所以必然存在碰撞outputhHMMH第7頁，共38頁。Hash函數(shù)的無碰撞性弱單向雜湊，是在給定M下，考察與特定M的無碰撞性；而強單向雜湊函數(shù)是考察輸入集中任意兩個元素的無碰撞性。顯然，對于給定的輸入數(shù)字串的集合，后一

4、種碰撞要容易實現(xiàn)。因為從下面要介紹的生日悖論知，在N個元素的集中，給定M找與M相匹配的M的概率要比從N中任取一對元素M，M相匹配的概率小得多。第8頁，共38頁。單向雜湊函數(shù)安全性要求 雜湊函數(shù)的安全性取決于其抗擊各種攻擊的能力，對手的目標是找到兩個不同消息映射為同一雜湊值。一般假定對手知道雜湊算法，采用選擇明文攻擊法 對雜湊函數(shù)的基本攻擊方法：（1）窮舉攻擊（或暴力攻擊）：不涉及雜湊算法的結(jié)構(gòu)，能對任何類型的散列函數(shù)進行攻擊。其中最典型方法是“生日攻擊”：給定初值H0，尋找MM，使h(H0, M)=h(H0, M)。（2）密碼分析法，這類攻擊方法依賴于對散列函數(shù)的結(jié)構(gòu)和代數(shù)性質(zhì)分析，采用針對散

5、列函數(shù)弱性質(zhì)的方法進行攻擊。這類攻擊方法有中間相遇攻擊、修正分組攻擊和差分分析等等。第9頁，共38頁。生日攻擊1生日悖論：在一個會場參加會議的人中，找一個與某人生日相同的概率超過0.5時，所需參會人員為183人。但要問使參會人員中至少有兩個同日生的概率超過0.5的參會人數(shù)僅為23人。這是因為，對于與某個已知生日的人同日生的概率為1/365，若房中有t人，則至少找到一人與此人同日生的概率為多少。易于解出，當(dāng)t183時可使p0.5。第一個人在特定日生的概率為1/365，而第二人不在該日生的概率為(1-1/365)，類似地第三人與前兩位不同日生的概率為(1-2/365)，以此類推，t個人都不同時生日

6、概率為Pt=(1-1/365)(1-2/365)(1-(t-1)/365)，因此，至少有兩人于同日生的概率為1-Pt. 解之，當(dāng)t23時，p0.5。第10頁，共38頁。對散列函數(shù)的生日攻擊 與散列函數(shù)相關(guān)的類似問題可表述如下：給定一個散列函數(shù)h的輸出長度為n位，共有2n個可能的散列值輸出，找x和y滿足H(x)=H(y)，則嘗試多少個報文可以找到一對（假設(shè)散列值n比特）顯然，最多嘗試2n1個報文，必有一對沖突其實，遠在到達2n1之前，很可能早就找到了(期望2n-1)如果只要達到一定的概率(如1/2)，約需嘗試多少個不同報文？答案：2n/2第11頁，共38頁。雜湊函數(shù)的構(gòu)造(Merkle-Damg

7、ard)迭代型散列函數(shù)的一般結(jié)構(gòu)：算法中重復(fù)使用某個函數(shù)f 。函數(shù)f的輸入有兩項，一項是上一輪（第i-1輪）的輸出CVi-1，稱為鏈接變量，另一項是算法在本輪（第i輪）b位的輸入分組mi。整個散列函數(shù)的邏輯關(guān)系可表示為： CV0 =IV； CVi = f（CVi-1，mi）；1it； h（M）= CVt第12頁，共38頁。直接設(shè)計散列函數(shù)MD5、SHA1是當(dāng)前國際通行的兩大密碼標準。MD5由國際著名密碼學(xué)家圖靈獎獲得者兼公鑰加密算法RSA的創(chuàng)始人Rivest設(shè)計，SHA1是由美國專門制定密碼算法的標準機構(gòu)美國國家標準技術(shù)研究院（NIST）與美國國家安全局（NSA）設(shè)計。兩大算法是目前國際電子簽

8、名及許多其它密碼應(yīng)用領(lǐng)域的關(guān)鍵技術(shù)，廣泛應(yīng)用于金融、證券等電子商務(wù)領(lǐng)域。其中，SHA1早在1994年便為美國政府采納，目前是美國政府廣泛應(yīng)用的計算機密碼系統(tǒng)。第13頁，共38頁。1990MD419911992MD51993SHA019941995SHA119961997199819992000200120022003SHA-256,384,512200420052006MD4 is brokentheoretical attack on SHA0MD5, SHA0 broken, theoretical attack on SHA1直接設(shè)計散列函數(shù)第14頁，共38頁。MD系列MIT 一系列雜湊

9、算法 (Ronal Rivest 設(shè)計) /rivest/Message Digest (MD)MD2 (RFC 1319) MD4 (RFC 1320) MD5 (RFC 1321) 應(yīng)用曾經(jīng)是最廣泛的摘要算法但是摘要太短(128bits)而SHA有160bits第15頁，共38頁。MD5特性：輸入：任意長度的消息 輸出：128位消息摘要 處理：以512位輸入數(shù)據(jù)塊為單位步驟1(填充消息): 使得消息的長度（bit為單位）模512為448。如果數(shù)據(jù)長度正好是模512為448，增加512個填充bit，也就是說填充的個數(shù)為1-512。 填充方法：第一個bit為1，其余全部為0。步驟2(補足長度)

10、: 將數(shù)據(jù)長度轉(zhuǎn)換為64bit的數(shù)值，如果長度超過64bit所能表示的數(shù)據(jù)長度的范圍，值保留最后64bit，增加到前面填充的數(shù)據(jù)后面，使得最后的數(shù)據(jù)為512bit的整數(shù)倍。然后對每個512bit按每組32bit進行分組,可分為16組。 512=32*16第16頁，共38頁。報文K bitsL512 bits=N 32bits報文長度(K mod 264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512128-bit 摘要MD5產(chǎn)生報文摘要的過程填

11、充(1 to 512 bits)第17頁，共38頁。MD5算法實例例7-1 對字符串”abc”，運用MD5求散列值解: 首先”abc”二進制表示為：01100001 01100010 01100011，共24位長度MD5算法：第一步：按照MD5要求，填充數(shù)據(jù): 5126424424（填充1位“1”，423位“0”，及 1000000)512位的輸入數(shù)據(jù)為(十六進制表示 ）：61626380 00000000 , 00000018而 W0= 61626380, W1=W2=W14=00000000, W15=00000018第18頁，共38頁。MD5算法步驟三：初始化變量 用到4個變量，分別為A

12、、B、C、D，均為32bit長。初始化為： A= 01 23 45 67 B=89 ab cd ef C=fe dc ba 98 D=76 54 32 10 第19頁，共38頁。MD5算法第四步：數(shù)據(jù)處理，共進行四輪。設(shè)對512bit按每組32bit進行分組為M0,M1, M15。第一輪的輔助函數(shù)： F(X,Y,Z) = (X Y) (X Z )X Y表示按位與，X Y表示按位或， X表示按位取反。第一輪的操作：FF(a,b,c,d, Mj,s, ti)表示為： a=b+(a+(F(b,c,d)+Mj+ti)s) 其中： Mj表示第j個分組， s表示循環(huán)左移s位 ti 是給定的常數(shù)， ti=0

13、 x(int(232*sin(i).第20頁，共38頁。a = b + (a + g(b, c, d) + Mk + Ti) s) b = b c = c d = d 然后交換：A=dB=aC=bD=cMD5 壓縮函數(shù)第21頁，共38頁。MD5算法-計算t1計算t1x=sin(1)=0.8414709848078965066525023216303y=232=4294967296z=x*y=232*sin(1)=3614090360.2828283386251439079649int(z)=3614090360=oxD76AA478第22頁，共38頁。MD5算法第一輪循環(huán) FF (a, b,

14、c, d, M 0, 7, 0 xd76aa478); /* 1 */ FF (d, a, b, c, M 1, 12, 0 xe8c7b756); /* 2 */ FF (c, d, a, b, M 2, 17, 0 x242070db); /* 3 */ FF (b, c, d, a, M 3, 22, 0 xc1bdceee); /* 4 */ FF (a, b, c, d, M 4, 7, 0 xf57c0faf); /* 5 */ FF (d, a, b, c, M 5, 12, 0 x4787c62a); /* 6 */ FF (c, d, a, b, M 6, 17, 0 xa8

15、304613); /* 7 */ FF (b, c, d, a, M 7, 22, 0 xfd469501); /* 8 */ FF (a, b, c, d, M 8, 7, 0 x698098d8); /* 9 */ FF (d, a, b, c, M 9, 12, 0 x8b44f7af); /* 10 */ FF (c, d, a, b, M10, 17, 0 xffff5bb1); /* 11 */ FF (b, c, d, a, M11, 22, 0 x895cd7be); /* 12 */ FF (a, b, c, d, M12, 7, 0 x6b901122); /* 13 */

16、 FF (d, a, b, c, M13, 12, 0 xfd987193); /* 14 */ FF (c, d, a, b, M14, 17, 0 xa679438e); /* 15 */ FF (b, c, d, a, M15, 22, 0 x49b40821); /* 16 */ 第23頁，共38頁。MD5算法第二、三、四輪第二、三、四輪與第一輪非常相似。第二輪的輔助函數(shù)： G(X,Y,Z) = (X Z) (Y Z) 第三輪的輔助函數(shù)： H(X,Y,Z) = X Y Z 第四輪的輔助函數(shù)： I(X,Y,Z) = Y (X Z) 第二輪的操作：GG(a,b,c,d, Mj,s, ti)

17、表示： a=b+(a+(G(b,c,d)+Mj+ti)s) 第三輪的操作HH(a,b,c,d, Mj,s, ti)表示： a=b+(a+(H(b,c,d)+Mj+ti)s) 第四輪的操作II(a,b,c,d, Mj,s, ti)表示： a=b+(a+(I(b,c,d)+Mj+ti)s) 第24頁，共38頁。 GG (a, b, c, d, M 1, 5, 0 xf61e2562); /* 17 */ GG (d, a, b, c, M 6, 9, 0 xc040b340); /* 18 */ GG (c, d, a, b, M11, 14, 0 x265e5a51); /* 19 */ GG

18、(b, c, d, a, M 0, 20, 0 xe9b6c7aa); /* 20 */ GG (a, b, c, d, M 5, 5, 0 xd62f105d); /* 21 */ GG (d, a, b, c, M10, 9, 0 x2441453); /* 22 */ GG (c, d, a, b, M15, 14, 0 xd8a1e681); /* 23 */ GG (b, c, d, a, M 4, 20, 0 xe7d3fbc8); /* 24 */ GG (a, b, c, d, M 9, 5, 0 x21e1cde6); /* 25 */ GG (d, a, b, c, M14

19、, 9, 0 xc33707d6); /* 26 */ GG (c, d, a, b, M 3, 14, 0 xf4d50d87); /* 27 */ GG (b, c, d, a, M 8, 20, 0 x455a14ed); /* 28 */ GG (a, b, c, d, M13, 5, 0 xa9e3e905); /* 29 */ GG (d, a, b, c, M 2, 9, 0 xfcefa3f8); /* 30 */ GG (c, d, a, b, M 7, 14, 0 x676f02d9); /* 31 */ GG (b, c, d, a, M12, 20, 0 x8d2a4c

20、8a); /* 32 */ /* 第二輪循環(huán) */ 第25頁，共38頁。 HH (a, b, c, d, M 5, 4, 0 xfffa3942); /* 33 */ HH (d, a, b, c, M 8, 11, 0 x8771f681); /* 34 */ HH (c, d, a, b, M11, 16, 0 x6d9d6122); /* 35 */ HH (b, c, d, a, M14, 23, 0 xfde5380c); /* 36 */ HH (a, b, c, d, M 1, 4, 0 xa4beea44); /* 37 */ HH (d, a, b, c, M 4, 11,

21、0 x4bdecfa9); /* 38 */ HH (c, d, a, b, M 7, 16, 0 xf6bb4b60); /* 39 */ HH (b, c, d, a, M10, 23, 0 xbebfbc70); /* 40 */ HH (a, b, c, d, M13, 4, 0 x289b7ec6); /* 41 */ HH (d, a, b, c, M 0, 11, 0 xeaa127fa); /* 42 */ HH (c, d, a, b, M 3, 16, 0 xd4ef3085); /* 43 */ HH (b, c, d, a, M 6, 23, 0 x4881d05);

22、/* 44 */ HH (a, b, c, d, M 9, 4, 0 xd9d4d039); /* 45 */ HH (d, a, b, c, M12, 11, 0 xe6db99e5); /* 46 */ HH (c, d, a, b, M15, 16, 0 x1fa27cf8); /* 47 */ HH (b, c, d, a, M 2, 23, 0 xc4ac5665); /* 48 */ /* 第三輪循環(huán) */ 第26頁，共38頁。 II (a, b, c, d, M 0, 6, 0 xf4292244); /* 49 */ II (d, a, b, c, M 7, 10, 0 x43

23、2aff97); /* 50 */ II (c, d, a, b, M14, 15, 0 xab9423a7); /* 51 */ II (b, c, d, a, M 5, 21, 0 xfc93a039); /* 52 */ II (a, b, c, d, M12, 6, 0 x655b59c3); /* 53 */ II (d, a, b, c, M 3, 10, 0 x8f0ccc92); /* 54 */ II (c, d, a, b, M10, 15, 0 xffeff47d); /* 55 */ II (b, c, d, a, M 1, 21, 0 x85845dd1); /* 5

24、6 */ II (a, b, c, d, M 8, 6, 0 x6fa87e4f); /* 57 */ II (d, a, b, c, M15, 10, 0 xfe2ce6e0); /* 58 */ II (c, d, a, b, M 6, 15, 0 xa3014314); /* 59 */ II (b, c, d, a, M13, 21, 0 x4e0811a1); /* 60 */ II (a, b, c, d, M 4, 6, 0 xf7537e82); /* 61 */ II (d, a, b, c, M11, 10, 0 xbd3af235); /* 62 */ II (c, d,

25、 a, b, M 2, 15, 0 x2ad7d2bb); /* 63 */ II (b, c, d, a, M 9, 21, 0 xeb86d391); /* 64 */ /* 第四輪循環(huán) */ 第27頁，共38頁。MD5算法做完四輪操作后，執(zhí)行：a = A ab = B bc = C cd = D d如果還有下一個512分組，則對其進行從第一輪開始的操作。如果所有512分組操作完畢，輸出：a b cd, 此即為所給消息的md5值,即所謂的消息摘要。第28頁，共38頁。處理程序非線性函數(shù)：sun(x) 的整數(shù)部分Ti = 232 *(abs(sin(i)，i 為弧度。MD5算法第29頁，共3

26、8頁。SHA1: Secure Hash Algorithm-1SHA-1是數(shù)字簽名標準DSS（Digtial Signature Standard）中使用的散列算法?；贛D4 所以類似MD5輸入 任意報文(264)輸出 160bitsSHA-1，SHA-256，SHA-384，SHA-512 SHA-1，SHA-256的分組大小是512 SHA-384，SHA-512的分組大小是1024 SHA-1輸出的摘要是160bit SHA-256輸出的摘要是256 SHA-384輸出的摘要是384 SHA-512輸出的摘要是512第30頁，共38頁。SHA5算法第一、二步第一步：填充消息 使得消息

27、的長度（bit為單位）模512為448。如果數(shù)據(jù)長度正好是模512為448，增加512個填充bit，也就是說填充的個數(shù)為1-512。填充方法：第一個bit為1，其余全部為0。 計算公式 補零的個數(shù)d=(447|x|) mod 512(l=|x|表示消息長度）X|1|0d|l第二步：補足長度 將數(shù)據(jù)長度轉(zhuǎn)換為64bit的數(shù)值 然后對每個512bit按每組32bit進行分組,可分為16組。512=32*16第31頁，共38頁。SHA1 算法原理 分段運算：512 bits 雜湊值長度：160 bits 初始向量：160 bitsSHA1消息摘要第32頁，共38頁。處理程序：4 回合，共計 80 次

28、；5 個緩存器 A = E + f1-4(t,B, C, D) + S5(A) + Wt + K1-4 B = A C = S30(B) D = C E = D其中 f1-4(t,B, C, D)=步t的基本邏輯函數(shù)Sk =循環(huán)左移k位Wt=一個從當(dāng)前512位輸入 數(shù)據(jù)塊導(dǎo)出的32位字K1-4一個用于加法的常量， 四個不同值+=模 232加SHA-1 壓縮函數(shù)第33頁，共38頁。SHA1 的IV初值用到5個變量，分別為A、B、C、D，E均為32bit長。初始化為： 暫存器初始值 A：67 45 23 01 B：EF CD AB 89 C：98 BA DC FE D：10 32 54 76 E ：C3 D2 E1 F0 第34頁，共38頁?；睾?步驟序號輸入常數(shù)取值方式 (整數(shù)) 第一回合 0 t 19 K1 = 5A82799 230 sqrt(2) 第二回合 20 t 39 K2 = 6ED9EBA1 230 sqrt(3) 第三回合 40 t 59 K3 = 8F1BBCDC 230 sqrt(5) 第四回合 60 t 79 K4 =