【文章內(nèi)容簡介】 輸出長 m比特），如果 H 的 k個隨機輸入中至少有兩個產(chǎn)生相同輸出的概 率大于 ，則 k ≈ 2m/2. (稱尋找函數(shù) H的具有相同輸出的兩個任意輸 入的攻擊方式為 第 Ⅱ 類生日攻擊 。 ) Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 29 ? 雜湊函數(shù)輸出長度 n應足夠大，以防止生日攻擊。 ? 64bits 認為太小。 ? 通常 128512bits。 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 30 ? 目前使用的大多數(shù)雜湊函數(shù)如 MD SHA，其結(jié)構(gòu)都是迭代型的，如圖 。 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 31 CVL1 CV1 IV = 初始值 CVi = 鏈接變量， Yi = 第 i 個輸入分組 f = 壓縮函數(shù) n = 雜湊值 的長度 b = 輸入分組的長度 迭代型雜湊函數(shù)的一般結(jié)構(gòu) b Y0 n f b Y1 n f b YL1 n f n n CVL CV0=IV= initial nbit value CVi=f(CVi1, Yi1) (1 ? i ? L) H(M) = CVL IV=CV0 圖 迭代型雜湊函數(shù)的一般結(jié)構(gòu) Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 32 其中函數(shù)的輸入 M被分為 L個分組Y0,Y1,…,YL1，每一個分組的長度為 b比特，最后一個分組的長度不夠的話，需對其做填充。 最后一個分組中還包括整個函數(shù)輸入的長度值，這樣一來，將使得敵手的攻擊更為困難，即敵手若想成功地產(chǎn)生假冒的消息，就必須保證假冒消息的雜湊值與原消息的雜湊值相同，而且假冒消息的長度也要與原消息的長度相等。 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 33 ? 算法的核心技術(shù)是 設計無碰撞的壓縮函數(shù) f，而敵手對算法的攻擊重點是 f 的內(nèi)部結(jié)構(gòu)，由于 f 和分組密碼一樣是由若干輪處理過程組成，所以對 f 的攻擊需通過對各輪之間的位模式的分析來進行，分析過程常常需要先找出 f 的碰撞。由于 f 是壓縮函數(shù)，其碰撞是不可避免的，因此在設計 f 時就應保證找出其碰撞在計算上是不可行的。 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 34 MD5雜湊算法 ? MD4是 MD5雜湊算法的前身，由 Ron Rivest于 1990年 10月作為 RFC提出， 1992年 4月，改動很小的修訂版以 RFC 1320發(fā)表。 ? MD5 (RFC 1321) developed by Ron Rivest at MIT in 90’s. 報文 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 512 512 512 128bit 摘要 圖 MD5的算法框圖 填充 (1 to 512 bits) Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 36 MD5算法描述 ? 步驟 1： 添加填充位 (一個 1和若干個 0)。 在消息的最后添加適當?shù)奶畛湮皇沟脭?shù)據(jù)位的長度滿足 length ? 448 mod 512。 即使消息長度已滿足要求 ， 仍需填充 。 例如 ， 消息長為 448比特 ， 則需填充 512比特 ， 使其長度變?yōu)?960。 因此填充的比特數(shù)大于等于 1而小于等于 512。 ? 步驟 2： 添加長度 。 添加原始消息的長度 （ 二進制位的個數(shù) ） ， 用 64位表示 。 以 小數(shù)在前 的格式存儲 (即低位字節(jié)放在低地址字節(jié)上 )。 如果消息長度大于 264， 則以 264為模數(shù)取模 。 這樣報文表示為 L個 512位的數(shù)據(jù)塊： Y0,Y1,…,YL1。 其長度為 L?512bits。 令 N=L?16,則長度為 N個 32位的字 。 (令M[0…N1]表示以字為單位的消息表示 ) Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 37 MD5算法描述 ? 步驟 3：初始化 MD緩沖區(qū)。一個 128位 MD緩沖區(qū)用以保存中間和最終散列函數(shù)的結(jié)果。它可以表示為 4個 32位的寄存器 (A,B,C,D)。 寄存器初始化為以下的 16進制值： A = 67452301 B = EFCDAB89 C = 98BADCFE D = 10325476 以小數(shù)在前的格式存儲： Word A: 01 23 45 67 Word B: 89 AB CD EF Word C: FE DC BA 98 Word D: 76 54 32 10 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 38 MD5算法描述 ? 步驟 4：處理 512位消息塊 （ 16個 32位字 ） 。壓縮函數(shù) HMD5是本算法的核心 。 它包括 4輪 處理 。 4輪處理具有相似的結(jié)構(gòu) ,但每次使用不同的基本邏輯函數(shù) ， 記為 F,G,H,I。 每一輪以當前的 512位數(shù)據(jù)塊 (Yq)和 128位緩沖值 ABCD作為輸入 ， 并修改緩沖值的內(nèi)容 。 每次使用 64元素表 T[1…64]中四分之一的元素 。 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 39 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算法描述 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 40 Copyright Yuan Email: 南京航空航天大學網(wǎng)絡研究室 Hash函數(shù) 41 MD5算法描述 ? 步驟 5：輸出