【文章內(nèi)容簡介】 代型散列函數(shù)的一般結(jié)構(gòu) 52 IV = 初始值 CV = 鏈接值 Yi = 第 i 個輸入數(shù)據(jù)塊 f = 壓縮算法 n = 散列碼的長度 b = 輸入塊的長度 安全雜湊算法的一般結(jié)構(gòu) b Y0 n f b Y1 n f b YL1 n CVL1 f CV1 n n CVL CV0=IV = initial nbit value CVi=f(CVi1, Yi1) (1 ? i ? L) H(M) = CVL 53 算法中重復使用一壓縮函數(shù) f（注意，有些書將散列函數(shù)也稱為壓縮函數(shù)，在此用壓縮函數(shù)表示散列函數(shù)中的一個特定部分）， f 的輸入有兩項，一項是上一輪（第 i1輪）輸出的 n比特值 CVi1，稱為鏈接變量，另一項是算法在本輪（第 i輪）的 b比特輸入分組 Yi。f 的輸出為 n比特值 CVi， CVi又作為下一輪的輸入。 迭代型散列函數(shù)的一般結(jié)構(gòu) 54 ? 算法開始時還需對鏈接變量指定一個初值 IV，最后一輪輸出的鏈接變量 CVL即為最終產(chǎn)生的雜湊值。 ? 通常有 bn，因此稱函數(shù) f為 壓縮函數(shù) 。算法可表達如下： CV0=IV=n比特長的初值； CVi=f(CVi1,Yi1)； 1≤i≤L； H(M)=CVL 迭代型散列函數(shù)的一般結(jié)構(gòu) 55 算法的核心技術(shù)是設計無碰撞的壓縮函數(shù) f，而敵手對算法的攻擊重點是 f 的內(nèi)部結(jié)構(gòu)，由于 f 和分組密碼一樣是由若干輪處理過程組成，所以對 f 的攻擊需通過對各輪之間的位模式的分析來進行，分析過程常常需要先找出 f 的碰撞。由于 f 是壓縮函數(shù)，其碰撞是不可避免的，因此在設計 f 時就應保證找出其碰撞在計算上是不可行的。 下面介紹幾個重要的迭代型散列函數(shù)。 迭代型散列函數(shù)的一般結(jié)構(gòu) 56 Hash Functions ? 把任意長的消息 “ 壓縮 ” 成固定長的消息的算法 ? 數(shù)字簽名時，常被使用 ? 通常， HASH 函數(shù)是公開的 ? 輸出長度應足夠大，防止生日攻擊 ? 64bits 認為太小 ? 通常 128512bits 57 Hash 函數(shù)設計原理 ? H能用于任何大小的數(shù)據(jù)分組 。 ? H產(chǎn)生定長輸出 。 ? 對任意給定的 x, H(x)要相對易于計算 ,使得軟硬件實現(xiàn)都實際可行 。 ? 對任意給定的碼 h, 尋求 x使得 H(x)=h在計算上是不可行的 (單向性 )。 ? 任意給定分組 x, 尋求不等于 x的 y, 使得 H(y)= H(x)在計算上不可行 (弱抗攻擊性 )。 ? 尋求對任何的 (x,y)對使得 H(x)=H(y)在計算上不可行 (強抗攻擊性 )。 58 ? 生日攻擊 (基于生日悖論 ) 在 k個人中 ,找一個與某人生日相同的人的 概率超過 ,只需 k 而在此人群中 , 至少有兩個人生日相同的概率超過 ,只需 k23. Hash 函數(shù)設計原理 59 MD4是 MD5雜湊算法的前身，由 Ron Rivest于 1990年 10月作為 RFC提出， 1992年 4月公布的 MD4的改進（ RFC 1320， 1321）稱為 MD5。 3. MD5雜湊算法 60 MD5算法采用圖 4描述的迭代型散列函數(shù)的一般結(jié)構(gòu)，算法的框圖如圖 5所示。算法的輸入為任意長的消息（圖中為 K比特），分為 512比特長的分組，輸出為 128比特的消息摘要。 算法描述 61 MD5的算法框圖 62 報文 K bits L?512 bits=N ?32bits 報文長度 (K mod 264) 100…0 Y0 512 bits Y1 512 bits Yq 512 bits YL1 512 bits HMD5 IV 128 HMD5 CV1 128 HMD5 CVq 128 HMD5 CVL1 128 512 填充 (1 to 512 bits) 512 512 512 128bit 摘要 MD5產(chǎn)生報文摘要的過程 63 處理過程有以下幾步： ① 對消息填充對消息填充，使得其比特長在模 512下為 448，即填充后消息的長度為 512的某一倍數(shù)減 64，留出的 64比特備第 2步使用。 步驟①是必需的，即使消息長度已滿足要求，仍需填充。例如，消息長為 448比特，則需填充512比特，使其長度變?yōu)?960，因此填充的比特數(shù)大于等于 1而小于等于 512。 填充方式是固定的，即第 1位為 1，其后各位皆為 0。 MD5算法描述 64 ② 附加消息的長度用步驟①留出的 64比特以littleendian方式來表示消息被填充前的長度。如果消息長度大于 264，則以 264為模數(shù)取模。 Littleendian方式是指按數(shù)據(jù)的最低有效字節(jié)（ byte）（或最低有效位）優(yōu)先的順序存儲數(shù)據(jù)，即將最低有效字節(jié)（或最低有效位）存于低地址字節(jié)（或位）。 相反的存儲方式稱為 bigendian方式 。 MD5算法描述 65 前兩步執(zhí)行完后，消息的長度為 512的倍數(shù)（設為 L倍），則可將消息表示為分組長為 512的一系列分組 Y0， Y1， … ， YL1，而每一分組又可表示為 16個 32比特長的字，這樣消息中的總字數(shù)為 N=L 16，因此消息又可按字表示為 M[0,… ,N1]。 MD5算法描述 66 ③ 對 MD緩沖區(qū)初始化算法使用 128比特長的緩沖區(qū)以存儲中間結(jié)果和最終雜湊值，緩沖區(qū)可表示為 4個 32比特長的寄存器（ A， B， C，D），每個寄存器都以 little endian方式存儲數(shù)據(jù)，其初值取為（以存儲方式）A=01234567， B=89ABCDEF， C=FEDCBA98， D=76543210， 實際上為 67452301， EFCDAB89， 98BADCFE， 10325476。 MD5算法描述 67 ? ④ ：處理消息塊（ 512位 = 16個 32位字）。一個壓縮函數(shù)是本算法的核心 (HMD5)。它包括 4輪處理。四輪處理具有相似的結(jié)構(gòu) ,但每次使用不同的基本邏輯函數(shù)，記為 F,G,H,I。每一輪以當前的 512位數(shù)據(jù)塊 (Yq)和 128位緩沖值 ABCD作為輸入，并修改緩沖值的內(nèi)容。每次使用 64元素表 T[1… 64]中的四分之一 MD5算法描述 68 ? T表，由 sin 函數(shù)構(gòu)造而成。 T的第 i個元素表示為 T[i]，其值等于 232?abs(sin(i)),其中 i是弧度。由于 abs(sin(i))是一個 0到 1之間的數(shù)， T的每一個元素是一個可以表示成 32位的整數(shù)。T表提供了隨機化的 32位模板， 消除了在輸入數(shù)據(jù)中的任何規(guī)律性的特征 MD5算法描述 69 T 表 T[49] = F4292244 T[50] = 432AFF97 T[51] = AB9423A7 T[52] = FC93A039 ．．． T[64] = EB86D391 T[1] = D76AA478 T[2] = E8C7B756 T[3] = 242070DB T[4] = C1BDCEEE ．．． T[16] = 49b40821 70 ? ⑤ 輸出消息的 L個分組都被處理完后，最后一個 HMD5的輸出即為產(chǎn)生的消息摘要。 MD5算法描述 71 ? 步驟 5：輸出結(jié)果。所有 L個 512位數(shù)據(jù)塊處理完畢后，最后的結(jié)果就是 128位消息摘要。 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 = 最終消息摘要結(jié)果 SUM32=分別按 32位字計算的模 232加法結(jié)果。 MD5算法描述 72 MD5的分組處理框圖 73 F,T[1…16],X[i] 16 steps G,T[17…32],X[ ?2i] 16 steps H,T[33…48],X[ ?3i] 16 steps I,T[49…64],X[ ?4i] 16 steps + + + + A B C D A B C D A B C D A B C D CVq 128 32 Yq 512 CVq+1 128 + is mod 232 單個 512bit 分組的 MD5 處理過程 74 HMD5的 4輪處理過程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不同，分別表示為 F、 G、 H、 I。每輪的輸入為當前處理的消息分組 Yq和緩沖區(qū)的當前值 A、 B、 C、 D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的 A、 B、 C、 D。每輪處理過程還需加上常數(shù)表 T中四分之一個元素，分別為 T[1… 16], T[17… 32], T[33… 48], T[49… 64]。表 T有 64個元素，見表 ，第 i個元素 T[i]為 232 abs(sin(i))的整數(shù)部分，其中 sin為正弦函數(shù)， i以弧度為單位。 MD5算法描述 75 ? 由于 abs(sin(i))大于 0小于 1，所以 T\[i\]可由 32比特的字表示。第 4輪的輸出再與第1輪的輸入 CVq相加，相加時將 CVq看作 4個32比特的字，每個字與第 4輪輸出的對應的字按模 232相加，相加的結(jié)果即為壓縮函數(shù)HMD5的輸出。（見 151頁表 ） MD5算法描述 76 步驟③到步驟⑤的處理過程可總結(jié)如下： CV0=IV。 CVq+1=CVq+RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]] MD=CVL 其中 IV是步驟③所取