【文章內容簡介】 hash: Ht ?速度慢 ,且許多這樣的 hash函數(shù)被證明不安全 (與 E的安全性無關 ) ?下面的四種可能是安全的 : ?Hi=EHi1(Mi)?Mi ?Hi=EHi1(Mi)?Mi?Hi1 ?Hi=EHi1(Mi?Hi1)?Mi ?Hi=EHi1(Mi?Hi1)?Mi?Hi1 ?現(xiàn)在很少使用 hash函數(shù)通用結構 ?由 Merkle于 1989年提出 ?Ron Rivest于 1990年提出 MD4 ?幾乎被所有 hash函數(shù)使用 ?具體做法 : –把原始消息 M分成一些固定長度的塊 Yi –最后一塊 padding并使其包含消息 M長度 –設定初始值 CV0 –壓縮函數(shù) f, CVi=f(CVi1,Yi1) –最后一個 CVi為 hash值 b Y0 n IV= CV0 f b Y1 n f b YL1 n CVL1 f CV1 n n IV = initial value 初始值 CV = chaining value 鏈接值 Yi = ith input block (第 i 個輸入數(shù)據(jù)塊 ) f = pression algorithm (壓縮算法） n = length of hash code (散列碼的長度 ) b = length of input block(輸入塊的長度 ) General Structure of Secure Hash Code CVL CV0=IV= initial nbit value CVi=f(CVi1, Yi1) (1 ? i ? L) H(M) = CVL 討論幾種常用的 HASH算法 ? MD5 ? SHA1 ? RIPEMD160 ? HMAC MD5簡介 ?Merkle于 1989年提出 hash function模型 ?Ron Rivest于 1990年提出 MD4 ?1992年 , MD5 (RFC 1321) developed by Ron Rivest at MIT ?MD5把數(shù)據(jù)分成 512bit塊 ?MD5的 hash值是 128bit ?在最近數(shù)年之前 ,MD5是最主要的 hash算法 ?現(xiàn)行美國標準 SHA1以 MD5的前身 MD4為基礎 MD5: padding ?Step 1: Padding M ? M1 –|M1| ? 448 mod 512 –|M1| |M| ? – 如果 |M| ? 448 mod 512,則 |M1| = |M|+512 –Padding內容 : 100…0 ?Step 2: Append 64bit length M1 ? M2 –若 |M| 264,則僅取低 64位 –低字節(jié)在前 (littleendian) –|M2|為 512的倍數(shù) : Y0,Y1,…,Y L1 MD5: 示意圖 MD5: pression ?Step 3: Initialize MD buffer (littleendian) A = 01 23 45 67 (0x67452301) B = 89 AB CD EF (0xEFCDAB89) C = FE DC BA 98 (0x98BADCFE) D = 76 54 32 10 (0x10325476) ?Step 4: Compression CV0=IV CVi=HMD5(CVi1,Yi) ?Step 5: Output MD = CVL MD5 Step 4: 示意圖 MD5 Step 4: overview ?Step 4: CV0=IV, CVi=HMD5(CVi1,Yi) –(A0,B0,C0,D0)?(A,B,C,D) –RoundOne(A,B,C,D,T[1…16],X[0…15]) –RoundTwo(A,B,C,D,T[17…32],X[0…15]) –RoundThree(A,B,C,D,T[33…48],X[0…15]) –RoundFour(A,B,C,D,T[49…64],X[0…15]) –(A,B,C,D)?(A+A0,B+B0,C+C0,D+D0) ?512bit塊 (X[…] 為 32bit表示 )在四個 Round使用 ?每個 Round包含 16次循環(huán) ,每次處理一個 32bit ?T[j]= [sin(j)*232]的整數(shù)部分 , 1 ? j ? 64 MD5 Compression Function 每一輪包含對緩沖區(qū) ABCD的 16步操作所組成的一個序列。 a?b + (( a + g(b,c,d) + X[k] +T[i])s) 其中， a,b,c,d = 緩沖區(qū)的四個字，以一個給定的次序排列； g = 基本邏輯函數(shù) F,G,H,I之一； s = 對 32位字循環(huán)左移 s位 X[k] = M[q?16 + k] = 在第 q個 512位數(shù)據(jù)塊中的第 k個 32位字 T[i] = 表 T中的第 i個 32位字； + = 模 232的加； A B C D A B C D + + + CLSs + g X[k] T[i] Function g g(b,c,d) 1 F(b,c,d) (b?c)?(b?d) 2 G(b,c,d) (b?d)?(c?d) 3 H(b,c,d) b?c?d 4 I(b,c,d) c?(b?d) ?2i = (1+5i) mod 16 ?3i = (5+3i) mod 16 ?2i = 7i mod 16 MD5 Step 4: RoundOne ?For(k = 0。 k 16。 ++k) { A?B + ((A+g1(B,C,D)+X[?1(k)]+T[16?0+k+1]) s1[k mod 4]) (A,B,C,D) ? (A,B,C,D) 32 } ?g1(B,C,D) = (B amp。 C) | (B amp。 D) ??1(k) = k, 0 ? k 16 ?s1[0…3] = [7,12,17,22] MD5 Step 4: RoundTwo ?For(k = 0。 k 16。 ++k) { A?B + ((A+g2(B,C,D)+X[?2(k)]+T[16?1+k+1]) s2[k mod 4]) (A,B,C,D) ?(A,B,C,D) 32 } ?g2(B,C,D) = (B amp。 D) | (C amp。 D) ??2(k) = (1+5k) mod 16, 0 ? k 16 ?s2[0…3] = [5,9,14,20] MD5 Step 4: RoundThree ?For(k = 0。 k 16。 ++k) { A?B + ((A+g3(B,C,D)+X[?3(k)]+T[16?2+k+1]) s3[k mod 4]) (A,B,C,D) ? (A,B,C,D) 32 } ?g3(B,C,D) = B ? C ? D ??3(k) = (5+3k) mod 16, 0 ? k 16 ?s3[0…3] = [4,11,16,23] MD5 Step 4: RoundFour ?For(k = 0。 k 16。 ++k) { A?B + ((A+g4(B,C,D)+X[?4(k)]+T[16?3+k+1]) s4[k mod 4]) (A,B,C,D) ? (A,B,C,D) 32 } ?g4(B,C,D) = C ? (B | D) ??4(k) = 7k mod 16, 0 ? k 16 ?s4[0…3] = [6,10,15,21] CV0 = IV CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]) MD = CVL 其中： IV = ABCD的初始值（見步驟 3） Yq = 消息的第 q個 512位數(shù)據(jù)塊 L = 消息中數(shù)據(jù)塊數(shù)； CVq = 鏈接變量，用于第 q個數(shù)據(jù)塊的處理 RFx = 使用基本邏輯函數(shù) x的一輪功能函數(shù)。 MD = 最終消息摘要結果 SUM32=分別按 32位字計算的模 232加法結果。 MD5: 總結 ?MD5使用小數(shù)在前 ?生日攻擊 +64位可計算 ? 128位 hash值太短 ?Dobbertin在 1996年找到了兩個不同的 512bit塊 ,它們在 MD5計算下產生相同的 hash ?至今還沒有真正找到兩個不同的消息 ,它們的 MD5的 hash相等 ?MD5不是足夠安全的 Secure Hash Algorithm簡介 ?1992年 NIST制定了 SHA(128位 ) ?1993年 SHA成為標準 （ FIPS PUB 180） ?1994年修改產生 SHA1(160位 ) ?1995年 SHA1成為新的標準 ,作為 SHA1(FIPS PUB 1801) ?SHA1要求輸入消息長度 264 ?輸入按 512位的分組進行處理的 ?SHA1的摘要長度為 160位 ?基礎是 MD4 SHA1: padding ?與 MD5相同 ?Step 1: Padding M ? M1 –|M1| ? 448 mod 512 –|M1| |M| ? – 如果 |M| ? 448 mod 512,則 |M1| = |M|+512 –Padding內容 : 100…0 ?Step 2: Append 64bit length M1 ? M2 –|M| 264 –高字節(jié)在前 (bigendian) –|M2|為 512的倍數(shù) : Y0,Y1,…,Y L1 SHA1: press ?Step 3: Initialize MD buffer (bigendian) A = 67 45 23 01 (0x67452301) B = EF CD AB 89 (0xEFCDAB89) C = 98 BA DC FE (0x98BADCFE) D = 10 32 54 76 (0x10325476) E = C3 D2 E1 F0 (0xC3D2E1F0) ?Step 4: Compression CV0=IV CVi=HSHA1(CVi1,Yi) ?Step 5: Output MD = CVL SHA1 step 4: 示意圖 SHA1 step 4: overview ?St