密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法 Computer-based Asymmetric Key Cryptographic Algorithms (Part 2)

訊息摘要演算法 原始訊息摘要演算法 (MD) 安全雜湊演算法 (SHA) 訊息鑑別碼 (MAC) 雜湊訊息鑑別碼 (HMAC)

MD5 原始訊息摘要演算法 (MD) 由 Ron River 所發展 MD -> MD2 -> MD3 -> MD4 -> MD5 MD5十分快速 產生128位元訊息摘要 (4個32位元區塊組成)

MD5 如何工作？ 填入 附加長度 將輸入分割成 512 位元區塊 初始化鏈結變數 處理區塊 複製鏈結變數到四個符合的變數中 將目前的 512 位元分割成 16 個子區塊 現在有四個回合。在每一個回合中，處理屬於每一個區塊的所有 16 個子區塊

MD5 如何工作 (1/7) 步驟 1：填入

MD5 如何工作 (2/7) 步驟 2：附加長度

MD5 如何工作 (3/7) 步驟 3：將輸入分割成 512 位元區塊

MD5 如何工作 (4/7) 步驟 4：初始化鏈結變數 A Hex 01 23 45 67 B Hex 89 AB CD EF C Hex FE DC BA 98 D Hex 76 54 32 10 鏈結變數 4個變數，各32位元，共128位元

MD5 如何工作 (5/7) 步驟 5.1：複製鏈結變數 A – D 到 a – d 變數中 A B C D a b c d abcd

MD5 如何工作 (6/7) 步驟 5.2：將目前的 512 位元分割成 16 個子區塊

MD5 如何工作 (7/7) 步驟 5.3：現在有四個回合。在每一個回合中， 處理屬於每一個區塊的所有 16 個子區塊

回合運算 程序 P 的步驟首先在 b、c、d 上執行 將變數 a 加入程序 P 的輸出 將訊息子區塊 M[i] 加入步驟2的輸出 將常數 t[k] 加入步驟3的輸出 將步驟4的輸出左循環位移 s 位元 將變數 b 加入步驟5的輸出 步驟6的輸出變成新的變數 a a = b + ((a + P(b, c, d) + M[i] + T[k] <<< s) 所有的變數向右移動一個位置

MD5 的運作 步驟8 d a b c

程序P

回合對應表 (回合1)

回合對應表 (回合2)

回合對應表 (回合3)

回合對應表 (回合4)

表格t的值

MD4與MD5差異

弱點 MD5 較老，訊息摘要長度為128位，隨著電腦運算能力提高，找到「碰撞」是可能的

弱點 2004年，中國數學家王小雲證明 MD5 數位簽名演算法可以產生碰撞。 2007年，Marc Stevens、Arjen K. Lenstra 和 Benne de Weger 進一步指出透過偽造軟體簽名，可重複性攻擊MD5演算法。研究者使用前綴碰撞法 (字首碰撞法)，使程式前端包含惡意程式，利用後面的空間添上垃圾代碼湊出同樣的 MD5 Hash 值。

弱點 2008年，荷蘭埃因霍芬技術大學科學家成功把2個可執行檔案進行了 MD5 碰撞，使得這兩個運行結果不同的程式被計算出同一個 MD5 ，顯然這樣會為病毒大開方便之門。 2008年12月一組科研人員透過MD5碰撞成功生成了偽造的SSL證書，這使得在https協議中伺服器可以偽造一些根CA的簽名。

安全雜湊演算法 (SHA) Secure Hash Algorithm, SHA 美國國家標準技術局(NIST)沿著 NSA 發展 1993年成為一個聯邦資料處理標準 (Federa Information Processing Standards, FIPS PUB 180) 1995年修訂成FIPS PUB 180-1，並更名為SHA-1 SHA是一個MD4的修正版，其設計與MD4非常相似

SHA 如何工作？ 填入 附加長度 將輸入分割成 512 位元區塊 初始化鏈結變數 處理區塊 複製鏈結變數 A-E 到變數 a-e 中 目前的 512 位元區塊分割成 16 個子區塊，每一個包含 32 位元 SHA 包含四個回合，每一個回合包含 20 個疊代

SHA 如何工作 (1/7) 步驟 1：填入

SHA 如何工作 (2/7) 步驟 2：附加長度

SHA 如何工作 (3/7) 步驟 3：將輸入分割成 512 位元區塊

SHA 如何工作 (4/7) 步驟 4：初始化鏈結變數 A Hex 01 23 45 67 B Hex 89 AB CD EF C Hex FE DC BA 98 D Hex 76 54 32 10 E Hex C3 D2 E1 F0 鏈結變數 5個變數，各32位元，共160位元

SHA 如何工作 (5/7) 步驟 5.1：複製鏈結變數 A – E 到 a – e 變數中 A B C D E a b c d e

SHA 如何工作 (6/7) 步驟 5.2：將目前的 512 位元分割成 16 個子區塊

SHA 如何工作 (7/7) 步驟 5.3：SHA 包含四個回合，每一個回合包含 20 個疊代 abcde = (e + P(b, c,d) + s5(a) + W[i] + K[i]), a, s30(b), c,d

單一 SHA-1 疊代

W[t]的值 t = 0 到 15 W[t] = M[t] t = 16 到 79 W[t] = s1(W[t – 16] XOR W[t – 14] XOR W[t – 8] XOR W[t – 3]

程序P

K[t]的值

MD5 與 SHA-1 的比較

SHA-1 的破解 2005年，Rijmen和Oswald發表了對SHA-1較弱版本(53次的加密迴圈而非80次)的攻擊：在2^80的計算複雜度之內找到碰撞。 2005年二月，王小雲、殷益群及於紅波發表了對完整版SHA-1的攻擊，只需少於2^69的計算複雜度，就能找到一組碰撞。

SHA-1 的破解 2005年8月17日的CRYPTO會議尾聲中王小雲、姚期智、姚儲楓再度發表更有效率的SHA-1攻擊法，能在2^63個計算複雜度內找到碰撞。 2006年的CRYPTO會議上，Christian Rechberger和Christophe De Cannière宣布他們能在容許攻擊者決定部分原訊息的條件之下，找到SHA-1的一個碰撞。

SHA-1 的安全 對 SHA-1 的實用攻擊目前能未成功 使用80次疊代並產生160位元訊息摘要 SHA 是 MD4 再加上改良的位元雜湊 多一個額外的回合和更多隨機性

訊息鑑別碼 (MAC) Message Authentication Code, MAC 概念類似訊息摘要 發送方和接收方需要共用一把共享的對稱性(秘密)金鑰 特徵 確保接收方的訊息沒有改變 接收方可以確認訊息是來自正確的發送方 與對稱性金鑰密碼學的差異 加密程序不需要是可逆的，單向函數可用

MAC 程序

MAC 程序 A 和 B 分享一個對稱性(秘密)金鑰 K，且此金鑰不被其他人知道。A 使用金鑰 K 在訊息 M 上計算 MAC H1。 A 寄出原始訊息 M 和 MAC H1 給 B 。 B 接收到訊息，B 也使用 K 在 M 上計算其 MAC H2。 B 比較 H1 和 H2。假如兩個相符合，B 可得知在傳送中訊息 M 沒有改變。假如 H1 與 H2 不相等，B 將拒絕此訊息，因為訊息在傳送之間被改變。

雜湊訊息鑑別碼 (HMAC) Hash-based Message Authentication Code, HMAC 在網際網路上的使用相當廣泛 網際網路協定 (Internet Protocol, IP) 安全插座層協定 (Secure Socket Layer, SSL)

HMAC 概念

HMAC變數定義 MD：訊息摘要/雜湊函數被使用(MD5, SHA-1等) M：原始訊息 L：訊息M中的區塊數目 b：每一區塊位元數目 K：對稱性金鑰 ipad：字串00110110重複b/8次 opad：字串01011010重複b/8次

HMAC 如何工作？ 取金鑰 K 的長度等於 b (區塊的位元數) 以 ipad XOR K 以產生 S1 加入 M 到 S1 中 必要時須調整輸入金鑰的長度 以 ipad XOR K 以產生 S1 加入 M 到 S1 中 訊息摘要演算法 以 opad XOR K 以產生 S2 加入 H 到 S2 中

HMAC 的步驟 (1/7) 步驟 1：取 K 的長度等於 b

HMAC 的步驟 (2/7) 步驟 2：以 ipad XOR K 以產生 S1

HMAC 的步驟 (3/7) 步驟 3：加入 M 到 S1 中

HMAC 的步驟 (4/7) 步驟 4：訊息摘要演算法

HMAC 的步驟 (5/7) 步驟 5：以 opad XOR K 以產生 S2

HMAC 的步驟 (6/7) 步驟 6：加入 H 到 S2 中

HMAC 的步驟 (7/7) 步驟 7：訊息摘要演算法

HMAC 的操作

HMAC 的缺點 HMAC演算法所產生的MAC能夠符合數位簽章的需求 但是HMAC使用對稱性金鑰進行加密，因此會有對稱性金鑰的問題 金鑰散佈 金鑰分配 無法驗證簽章由誰產生

數位簽章技術 (DSS) Digital Signature Standard, DSS 美國國家標準技術局(NIST)於1991年發表DSS表準為聯邦資訊處理表準(FIPS) PUB 186 使用SHA-1產生訊息摘要 使用數位簽章演算法(Digital Signature Algorithm, DSA) 非對稱性金鑰密碼學 僅使用於數位簽章

RSA 與 DSA RSA DSA DSA 與 RSA 有智慧財產權上的爭議 RSA資料安全公司(RS Data Security Inc, RSADSI) 非免費 可用於加密與簽章 DSA 美國國家技術標準局(NIST) 免費 只能用於簽章 DSA 與 RSA 有智慧財產權上的爭議

數位簽章 (1/6) 訊息摘要計算

數位簽章 (2/6) 建立數位簽章

數位簽章 (3/6) 原始訊息與數位簽章一起傳送

數位簽章 (4/6) 接受方計算其自有的訊息摘要

數位簽章 (5/6) 接受方解密取得發送方的訊息摘要

數位簽章 (6/6) 數位簽章憑證

其他演算法 背包式演算法 橢圓曲線密碼學 ElGamal Ralph Merkle 和 Martin Hellman 發展的第一個以公開金鑰加密的演算法 基於背包問題 橢圓曲線密碼學 Elliptic Curve Cryptography, ECC 基於橢圓曲線離散演算法問題 ElGamal 基於有限範圍內計算離散演算法的困難度

章節總結 非對稱性金鑰密碼學的目標在解決對稱性金鑰密碼學中金鑰交換的問題 RSA 是一個非常受歡迎的非對稱性金鑰密碼學協定 在非對稱性金鑰密碼學中，每一個通訊方都需要一組金鑰對 公開金鑰會共享給每一個人，而私密金鑰必須由一個人保持祕密 質數在非對稱性金鑰密碼學中非常重要

章節總結 數位信封結合了對稱性和非對稱性金鑰密碼學的優點 訊息摘要（也稱為雜湊）可以辨識訊息 MD5 和 SHA-1 是訊息摘要演算法 HMAC 是一個包含加密的訊息摘要演算法 HMAC 受實際爭論之苦 DSA 和 RSA 演算法可以用在數位簽章

The End