杂凑与乱数演算法

1、1第五章第五章 雜湊與亂數演算法雜湊與亂數演算法5-1 雜湊函數簡介雜湊函數簡介5-2 簡單的雜湊函數簡單的雜湊函數5-3 破解雜湊函數破解雜湊函數5-4 MD5 訊息摘要訊息摘要5-5 MD5 演算法演算法5-6 MD5 壓縮函數壓縮函數5-7 MD4 訊息摘要訊息摘要5-8 SHA-1 演算法演算法5-9 SHA-1 壓縮函數壓縮函數5-10 各種演算法之比較各種演算法之比較5-11 亂數產生器亂數產生器5-12 加密法的亂數產生加密法的亂數產生25-1 雜湊函數簡介雜湊函數簡介雜湊函數雜湊函數 (Hash Function) 簡介簡介 數位指紋數位指紋 (Digital Fingerpr

2、int) 定義：定義： 明文：明文：M 雜湊函數：雜湊函數：H 雜湊值：雜湊值：h = H(M) 雜湊函數必須具備之功能：雜湊函數必須具備之功能：1. 1.對任意長度的訊息輸入，產生固定長度的雜湊值輸出。對任意長度的訊息輸入，產生固定長度的雜湊值輸出。 2. 2.可可 H(M)，並可經由硬體或軟體來實現。，並可經由硬體或軟體來實現。 3. 3.單向雜湊（單向雜湊（One-way Hash）之特性。）之特性。 4. 4.對於訊息對於訊息 M1，在計算上是無法找出另一個訊息，在計算上是無法找出另一個訊息 M2 M1，使得，使得 H(M1) = H(M2)。 5. 5.若若 H(M1) = H(M2

3、)，則，則 M1 = M2，若，若 H(M1)H(M2)，則，則 M1M2。 弱雜湊函數弱雜湊函數( (Weak Hash Function)Weak Hash Function) 強雜湊函數強雜湊函數( (Strong Hash Function)Strong Hash Function) 35-2 簡單的雜湊函數簡單的雜湊函數CRC (Cylic Redundancy Code) Bitwise-XOR 不符合弱雜湊函數不符合弱雜湊函數 不符合強雜湊函數不符合強雜湊函數 ABMH(M)訊息訊息雜湊演算法 MH(M)T TH(M) = H(M) (正常)H(M) = H(M) (正常)或或H

4、(M) H(M) (錯誤發生)H(M) H(M) (錯誤發生)M訊息訊息H(M)=雜湊演算法 45-3 破解雜湊函數破解雜湊函數破解雜湊函數的基本原理破解雜湊函數的基本原理 偽造訊息，使其與原來訊息的雜湊值相同偽造訊息，使其與原來訊息的雜湊值相同 生日攻擊法生日攻擊法 (Birthday Attack)攻擊者已得到一份經由簽署者簽署過的文件，簽署方式是明文後面加上攻擊者已得到一份經由簽署者簽署過的文件，簽署方式是明文後面加上已加過密的雜湊值。已加過密的雜湊值。 攻擊者依照該文件的明文格式，修改其內容，並製造出其它偽造明文。攻擊者依照該文件的明文格式，修改其內容，並製造出其它偽造明文。 攻擊者針

5、對此明文產生攻擊者針對此明文產生 232 個不同的變形，一定可以找出相同雜湊值的個不同的變形，一定可以找出相同雜湊值的偽造明文。偽造明文。 攻擊者將偽造的明文與原來簽署的雜湊值結合起來，一併送出。攻擊者將偽造的明文與原來簽署的雜湊值結合起來，一併送出。 經由接收者檢視後（利用簽署者的公開鑰匙），認為該明文的確是由簽經由接收者檢視後（利用簽署者的公開鑰匙），認為該明文的確是由簽署者所發沒錯。署者所發沒錯。 中途相遇攻擊法中途相遇攻擊法 (Meet-in-the-Middle Attack) 一個區塊接一個區塊的偽造一個區塊接一個區塊的偽造 55-4 MD5 訊息摘要訊息摘要Message Dig

6、est (MD)MIT 一系列雜湊演算法一系列雜湊演算法 (Ron Rivest 設計設計) MD2 (RFC 1319) MD4 (RFC 1320) MD5 (RFC 1321) MD5 運作原理運作原理 區段演算：區段演算：512 bits 雜湊值長度：雜湊值長度：128 bits 初始向量：初始向量：128 bits 原文訊息附加位元訊息長度P0P1P2PL-1HMD5128不定長度不定長度1 512 bits64 bitsL * 512 bits L * 512 bits HMD5128HMD5128HMD5128IVCV1CV2CVL-1128 bits128 bits訊息摘要訊息

7、摘要512 bits 65-5 MD5 演算法演算法 (一一)MD5 演算法演算法 兩組輸入：512 bits 明文區塊與 128 bits 上一區塊的輸出(或 IV) 。 輸入資料區分為四個暫存器：A, B, C, D。 區分為四個步驟，每步驟計算 16 次，合計 64 次。 加入 sin(x) 非線性函數參數值。 處理步驟處理步驟： 步驟 1：將輸入明文（512 bits）以每 32 bits 為單位，分別存入Xk中，其中 k =0, 1, 2, ., 15。 步驟 2：初始化 A、B、C 與 D 暫存器，如下： A：01 23 45 67 B：89 ab cd ef C：fe dc ba

8、 98 D：76 54 32 10 步驟 3：進入第一回合運算，執行 16 次： a = b+(a+F(b, c, d)+Xk+Ti) s) 步驟 4：進入第二回合運算，執行 16 次： a = b+(a+G(b, c, d)+Xk+Ti) s) 步驟 5：進入第三回合運算，同樣執行 16 次： a = b+ (a+ H(b, c, d)+ Xk+Ti) s) 步驟 6：進入第四回合運算，同樣執行 16 次： a = b+ (a+ H(b, c, d)+ Xk+Ti) s) 步驟 7：輸出訊息摘要，執行 SUM32 計算。 75-5 MD5 演算法演算法 (二二)處理程序處理程序非線性函數：非

9、線性函數：sun(x) 的鹽的鹽 Ti = 232 (abs(sin(i)，i 為弧度。 abcd k s ia = b+(a + F(b, c, d) + Xk+Ti) s)A AB BC CD D1281283232512512P Pq qCVCVq q第一回合第一回合16 steps16 stepsabcd k s ia = b+(a + G(b, c, d) + Xk+Ti) s)ABCD第二回合第二回合16 steps16 stepsabcd k s ia = b+(a + H(b, c, d) + Xk+Ti) s)ABCD第三回合第三回合16 steps16 stepsabcd

10、k s ia = b+(a + I(b, c, d) + Xk+Ti) s)ABCD第四回合第四回合16 steps16 stepsXkXkXkXkXkXkXkXk128 bits128 bitsCVCVq+1q+1SUMSUM323285-6 MD5 壓縮函數壓縮函數MD5 運算處理運算處理 a = b + (a + g(b, c, d) + Xk + Ti) 0；最好是夠大的質數。；最好是夠大的質數。 a 乘數（乘數（Multiplier）：）：0 a m。 c 增量（增量（Increment）：）：0 c m。 X0 起始值，或稱種子（起始值，或稱種子（Seed）：）：0 X0 m。 全

11、週期全週期 (Full Period) (Full Period) 函數函數： Xn+1 = (a Xn + c) mod 232-1 155-12 加密法的亂數產生加密法的亂數產生 (一一)DES 加密法的亂數產生加密法的亂數產生 初始亂數：全週期虛擬亂數產生。初始亂數：全週期虛擬亂數產生。 採用採用 DES 演算法演算法 加密鑰匙的保護加密鑰匙的保護 CnCn+1C Cn+1n+1 = (a C = (a Cn n + k) mod m + k) mod m全週期虛擬亂數DES加密演算法主鑰匙主鑰匙K Km mX Xn+1n+1 = E = EKmKm(C(Cn+1n+1) )165-12 加密法的亂數產生加密法的亂數產生 (二二)ANSI 亂數產生亂數產生ANSI X9.17 標準標準 採用採用 3DES 演算法演算法 輸入參數輸入參數：日期：日期/時間與上一次運算結果。時間與上一次運算結果。加密鑰匙加密鑰匙：112 bits 。 亂數輸出亂數輸出：64 bits。 演算法輸出演算法輸出： Ri = 3DESK1|K2 Vi 3DESK1|K2 DTi Vi+