【正文】 ,超過 M和一個 M?,它們的 hash值相同 ?秘書提交 M,經(jīng)理審閱后產(chǎn)生 64位 hash值并對該值簽名 ,返回給秘書 ?秘書用 M?替換 M,再與經(jīng)理數(shù)字簽名一起發(fā)出 ?Hash必須足夠長 (64 ? 128 ? 160) ? Institute of Computer Science amp。 Technology, Peking University 21 hash函數(shù)通用模型 ?由 Merkle于 1989年提出 ?Ron Rivest于 1990年提出 MD4 ?幾乎被所有 hash函數(shù)使用 ?具體做法 : ?把原始消息 M分成一些固定長度的塊 Yi ?最后一塊 padding并使其包含消息 M長度 ?設(shè)定初始值 CV0 ?壓縮函數(shù) f, CVi=f(CVi1,Yi1) ?最后一個 CVi為 hash值 ? Institute of Computer Science amp。 Technology, Peking University 22 hash函數(shù)模型圖 ? Institute of Computer Science amp。 Technology, Peking University 23 MD5簡介 ? ?Merkle于 1989年提出 hash function模型 ?Ron Rivest于 1990年提出 MD4 ?1992年 ,MD5出現(xiàn) ?MD5把數(shù)據(jù)分成 512bit塊 ?MD5的 hash值是 128bit ?在最近數(shù)年之前 ,MD5是最主要的 hash算法 ?現(xiàn)行美國標(biāo)準 SHA1以 MD5的前生 MD4為基礎(chǔ) Institute of Computer Science amp。 Technology, Peking University 24 MD5: padding ?Step 1: Padding M ? M1 ?|M1| ? 448 mod 512 ?|M1| |M| ? 如果 |M| ? 448 mod 512,則 |M1| = |M|+512 ?Padding內(nèi)容 : 100…0 ?Step 2: Append 64bit length M1 ? M2 ?若 |M| 264,則僅取低 64位 ?低字節(jié)在前 (littleendian) ?|M2|為 512的倍數(shù) : Y0,Y1,…,Y L1 Institute of Computer Science amp。 Technology, Peking University 25 MD5: 示意圖 Institute of Computer Science amp。 Technology, Peking University 26 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 Institute of Computer Science amp。 Technology, Peking University 27 MD5 Step 4: 示意圖 Institute of Computer Science amp。 Technology, Peking University 28 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 Institute of Computer Science amp。 Technology, Peking University 29 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] Institute of Computer Science amp。 Technology, Peking University 30 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] Institute of Computer Science amp。 Technology, Peking University 31 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] Institute of Computer Science amp。 Technology, Peking University 32 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] Institute of Computer Science amp。 Technology, Peking University 33 MD5: 總結(jié) ?MD5使用 littleendian ?生日攻擊 +64位可計算 ? 128位 hash值太短 ?Dobbertin在 1996年找到了兩個不同的 512bit塊 ,它們在 MD5計算下產(chǎn)生相同的 hash ?至今還沒有真正找到兩個不同的消息 ,它們的MD5的 hash相等 ?MD5不是足夠安全的 ? ? Institute of Computer Science amp。 Technology, Peking University 34 Secure Hash Algorithm簡介 ?1992年 NIST制定了 SHA(128位 ) ?1993年 SHA成為標(biāo)準 ?1994年修改產(chǎn)生 SHA1(160位 ) ?1995年 SHA1成為新的標(biāo)準 ?SHA1要求輸入消息長度 264 ?SHA1的摘要長度為 160位 ?基礎(chǔ)是 MD4 ? Institute of Computer Science amp。 Technology, Peking University 35 SHA1: padding ?與 MD5相同 ?Step 1: Padding M ? M1 ?|M1| ? 448 mod 512 ?|M1| |M| ? 如果 |M| ? 448 mod 512,則 |M1| = |M|+512 ?Padding內(nèi)容 : 100…0 ?Step 2: Append 64bit length M1 ? M2 ?|M| 264 ?高字節(jié)在前 (bigendian) ?|M2|為 512的倍數(shù) : Y0,Y1,…,Y L1 Institute of Computer Science amp。 Technology, Peking University 36 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 Institute of Computer Science amp。 Technology, Peking University 37 SHA1 step 4: 示意圖 Institute of Computer Science amp。 Technology, Peking University 38 SHA1 step 4: overview ?Step 4: CV0=IV, CVi=HSHA1(CVi1,Yi) (A0,B0,C0,D0,E0)?(A,B,C,D,E), t ? 0 Round(A,B,C,D,E,K[t],W[t]) 0 ? t 80 (A,B,C,D,E)?(A+A0,B+B0,C+C0,D+D0,E+E0) ?整個 Round包含 80次循環(huán) ,每次處理一個 32bit ?W[t] = Yi[t] 0 ? t 16 W[t] =(W[t16]?W[t14]?W[t8]?W[t3])1 16 ? t 80 ?每組 (16個 )W[t]可由前一組 W[t]直接計算 Institute of Computer Science amp。 Technology, Peking University 39 SHA1: pression function ?Four rounds: 0 ? t 80 E ? E+f(t,B,C,D)+(A5)+W[t]+K[t] B ? B30 (A,B,C,D,E)?(A,B,C,D,E)32 ?f(t,B,C,D) = (Bamp。C)|(Bamp。D) 0 ? t 20 K[t] = 230 ? sqrt(2) ?f(t,B,C,D) = B ? C ? D 20 ? t 40 K[t] = 230 ? sqrt(3) ?f(t,B,C,D) = (Bamp。C)|(Bamp。D)|(Camp。D) 30 ? t 60 K[t] = 230 ? sqrt(5) ?f(t,B,C,D) = B ? C ? D 60 ? t 80 K[t] = 230 ? sqrt(10) Institute of Computer Science amp。 Technology, Peking University 40 SHA1總結(jié) ?SHA1使用 bigendian ?抵抗生日攻擊 : 160位 hash值 ?沒有發(fā)現(xiàn)兩個不同的 512bit塊 ,它們在 SHA1計算下產(chǎn)生相同的“ hash” ?速度慢于 MD5 ?安全性優(yōu)于 MD5 ? ? Institute of Computer Science