密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法

Presentation on theme: "密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法"— Presentation transcript:

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

2 前言 對稱性金鑰密碼學是快速且有效率的 對加密的訊息，發送方和接收方在對稱性金鑰密碼學中使用相同金鑰，要同意這一把金鑰並未讓任何其他人知道是一件非常困難的事 非對稱性金鑰密碼學可以解決這個問題

3 非對稱性金鑰密碼學的簡史 在1970年間，史丹佛大學的學生 Whitfield Diffie 遇見他的教授 Martin Hellman，他們開始思考金鑰交換的問題，經過一些研究與複雜的數學分析，他們開始興起非對稱性金鑰密碼學的想法 許多專家認為這在密碼學史上或許是唯一的真正改個概念，因此，Diffie 和 Hellman 被當成非對稱性金鑰密碼學之父

4 非對稱性金鑰密碼學的簡史 非對稱性金鑰密碼學榮耀的爭論
英國通訊電子安全組織 (Communication Electronic Security Group, CSEG) 秘密的單位 1960, Jame Ellis, 提出概念 1973, Jame Ellis與Cliffird Cocks, 設計出演算法 1974, Malcolm, 發展出非對稱性金鑰密碼學 1997,公開的文件發現CSEG早在1970 美國國家安全局 (National Security Agency, NSA) 1970, 也在發展非對稱金鑰密碼系統

5 非對稱性金鑰密碼學的簡史 在1977年，Ron Rivest、Adi Shamir 和Len Adleman 在 MIT 時發展出第一個主要的非對稱性金鑰密碼學系統 基於 Diffie 和 Hellman 理論的框架 並在 1978 年發表他們的結果。這個機制被稱為 RSA演算法

6 非對稱性金鑰密碼學的簡史 RSA 是被廣泛接受的公開金鑰機制 解決了金鑰協議和分配的問題

7 非對稱性金鑰密碼學總覽 非對稱性金鑰密碼學 (Asymmetric Key Cryptography)
公開金鑰密碼學 (Public Key Cryptography) 金鑰對 (key pair) 公開金鑰 (public key) 散佈給任何人都可以取得 用於加密 私密金鑰 (private key) 個人保存 用於解密

8 非對稱性金鑰密碼學的運作 當A想要寄出訊息給B，A使用B的公開金鑰加密訊息。(因為A知道B的公開金鑰)
A寄出這個訊息給B。(已經用B的公開金鑰加密的訊息) B使用B的私密金鑰解密A的訊息。(只有B知道自己的私密金鑰) 只有B才有解開密文訊息的私密金鑰，故傳輸過程中的訊息對任何人是沒有意義的。

9 非對稱性金鑰密碼學的運作

10 非對稱性金鑰密碼學的運作 若B要傳送訊息給A
使用相同的步驟，但是B使用A的公開金鑰加密訊息，A收到B傳送過來的密文訊息，A使用A的私密金鑰解開密文。

11 私密與公開金鑰 私密金鑰：用於解密 公開金鑰：用於加密

12 RSA演算法 RSA演算法為目前最受歡迎的非對稱性金鑰密碼學演算法 RSA基於整數因數分解的問題 RSA使用大質數來產生金鑰

13 質數 所謂質數是指只能被 1 和自己整除的數 例如 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,…

14 RSA演算法原理 基於數學事實，整數因數分解問題 找大質數並相乘是容易，但要從乘積中進行因數分解是非常困難的

15 RSA演算法的使用流程

16 RSA金鑰產生步驟 選擇兩個大質數 P 和 Q 計算 N = P * Q
選擇公開金鑰 E，使它不是一個 (P – 1) 和 (Q – 1) 的因數 選擇私密金鑰 D，使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1

17 RSA加解密步驟 在加密中，從明文 PT 計算密文 CT CT = PTE mod N 將密文 CT 寄給接收方
在解密中，從密文 CT 計算明文 PT PT = CTD nod N

18 範例(步驟1, 2) 選擇兩個大質數 P 和 Q P = 47, Q = 71
計算 N = P * Q N = 47 * 71 = 3337

19 範例(步驟3) 選擇公開金鑰 E，使它不是一個 (P – 1) 和 (Q – 1) 的因數 (47 – 1) * (71 – 1) = 46 * 70 = 的因數為 2, 2, 5, 7, = 2 * 2 * 5 * 7 * 23 選擇 E 不包含上述因數 Ex: 4 (含2), 15 (含5), 14 (含2, 7), 69 (含23)不可選 E = 79

20 範例(步驟4) 選擇私密金鑰 D，使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1 在恆等式替換 E = 79, P = 47, Q = 71 (D * 79) mod (47 – 1) * (71 – 1) = 1 (D * 79) mod (46 * 70) = 1 (D * 79) mod 3220 = 1 經過計算 D = 1019 (1019 * 79) mod 3220 = mod 3220 = 1

21 範例(步驟5) 在加密中，從明文 PT 計算密文 CT CT = PTE mod N 假設明文 PT = 688 E = 79, N = 3337 CT = mod 3337 = 1570 得到密文 1570

22 範例(步驟6) 將密文 CT 寄給接收方 傳送 1570 給對方

23 範例(步驟7) 在解密中，從密文 CT 計算明文 PT PT = CTD nod N 取得密文 CT = 1570 D = 1019, N = 3337 PT = mod 3337 = 688 解回明文 688

24 實例 E = 5 D = 77 N = 119 字母編碼 A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, ……, Z = 26

25 RSA的關鍵 RSA的演算法很簡單，因此關鍵在金鑰 金鑰的產生由 P, Q (兩個質數) 得來
N = P * Q 且產生公開金鑰(E)與私密金鑰(D) N, E 是公開的 攻擊者可由 N, E 來推得 D？

26 RSA的關鍵 RSA的關鍵在於當 P, Q 選擇數字很大時 要將 N 分解成 P, Q 是很困難的 因此要找到 D 必須依賴 P, Q, E

27 RSA金鑰長度 1997年以後設計的系統採 政府機關公開金鑰基礎建設憑證政策 一般使用者：1024位元 憑證認證機構：2048位元
100年1月1日起簽發使用2048位元憑證 原先1024位元憑證使用至到期為止

28 RSA已知的攻擊 針對RSA的攻擊是基於大數因數分解 1999年，RSA-155(512 bits)被成功分解
花了五個月時間(約8000 MIPS 年)和224 CPU hours 在一台有3.2G中央內存的Cray C916計算機上完成 2002年，RSA-158也被成功因數分解 2009年12月12日， RSA-768 (768 bits, 232 digits)也被成功分解 已經威脅到1024位元的安全性

29 RSA-158 = ×

30 RSA-768 = ×

31 對稱性與非對稱性金鑰密碼學之間的比較

32 運算速度的比較 使用硬體設計 DES 比 RSA 快 1000 倍 使用軟體設計 DES 比 RSA 快 100 倍

33 兩個世界中的最佳 結合兩個密碼學機制，以得到兩者中的優點，但不犧牲兩者中的任何特色，我們需要確認符合下列的目標 解決方案應該完全安全
加密和解密的過程不需要花很長時間。 產生的密文不應太大 解決方案應該控制在能讓大多數人簡單地使用，無須多餘的複雜度 解決方案必須能解決金鑰分配問題

34 結合方法 使用對稱性金鑰演算法加解密訊息 使用非對稱性金鑰演算法來傳遞金鑰 同時傳遞訊息密文與金鑰包裝
金鑰包裝 (key wrapping) 同時傳遞訊息密文與金鑰包裝 數位信封 (digital envelope)

35 結合方法 (1/7)

36 結合方法 (2/7)

37 結合方法 (3/7)

38 結合方法 (4/7)

39 結合方法 (5/7)

40 結合方法 (6/7)

41 結合方法 (7/7)

42 數位簽章 使用RSA加解密演算法 公開私密金鑰 訊息傳遞者使用「公開金鑰」對訊息進行「加密(簽章) 」
訊息接收者使用「私密金鑰」對密文進行「解密(驗證) 」

43 數位簽章的基礎 公開金鑰 (簽章) 私密金鑰 (驗證)

44 訊息的隱藏與驗證 訊息的隱藏 訊息的驗證 假如 A 是一個訊息的發送方，B 是接收方，A 使用 B 的公開金鑰加密訊息，並寄出加密訊息給 B
若密文訊息被 C 竊取則 C 無法解密 訊息的驗證 假如 A 是一個訊息的發送方，B 是接收方，A 使用 A 的公開金鑰加密訊息，並寄出加密訊息給 B B 可用 A 的私密金鑰將訊息解密 若密文訊息 C 被竄改則 B 解密失敗

45 訊息摘要 若將訊息使用公開金鑰加密作為簽章的驗證，則當明文很大時，速度非常緩慢 使用數位信封的方式進行簽章
使用對稱性金鑰(K1)加密訊息(PT)為密文(CT) 使用私密金鑰(K2)加密K1 建立數位信封傳送CT與加密後的K1 使用公開金鑰(K3)解開得到K1 使用K1解密密文(CT)得到訊息(PT)

46 訊息摘要 真實情況使用更有效率的作法 訊息摘要是一個訊息的指印(fingerprint)或是總結 類似
訊息摘要(message digest) 雜湊(hash) 訊息摘要是一個訊息的指印(fingerprint)或是總結 類似 縱向冗餘核對 (Longitudinal Redundancy Check, LRC) 回合冗餘核對 (Cyclic Redundancy Check, CRC) 用來確認資料的完整性

47 縱向冗餘核對(LRC) Longitudinal Redundancy Check, LRC
於一組字元相對應的位元串後附加一個同位元 計算行(垂直)中 1 的個數 個數為奇數稱為「奇同位元」(odd parity)，標示為 1 個數為偶數稱為「偶同位元」(even parity)，標示為 0

48 縱向冗餘核對(LRC) 同位元位元

49 縱向冗餘核對(LRC) 訊息傳遞先透過縱向冗餘核對(LRC)產生區塊的同位元位元 LRC(指同位元位元)則為原始訊息的指印
若相同則合理相信資料沒有被修改

50 訊息摘要的概念 訊息摘要基於LRC(或其他檢查碼技術)相同概念但作法更多元 概念 例如 透過設計的運算規則產生指印
指印無法透漏原始訊息的相關訊息 例如 原始訊息：4000 運算：除以1000 指印：4 訊息被改變無法得到正確的指印 只知道指印無法推得與原始訊息的關係 ＝ 4 4000 / 1000 ＝ 4 ……

51 訊息摘要簡單的例子 運算規則：取一個數與上次結果相乘並只留下各位數

52 訊息摘要的概念

53 訊息摘要的概念 資料區塊進行一個訊息摘要演算法(雜湊運算)，會產生訊息摘要(或雜湊)，其大小會小於原始訊息 訊息摘要不會很小且無法直接計算
訊息摘要通常包含128位元或更多 兩個訊息摘要要相同的機會是0到2128的任何數 訊息摘要長度要很長是有目的的 縮小兩個訊息摘要相同的範圍

54 訊息摘要的要求 給予一個訊息，應該要很容易找出對應的訊息摘要 對於同一個訊息，每次運算出的訊息摘要必須相同
給予一個訊息摘要，找出其原始訊息是很困難的 給予任兩個訊息，兩個的訊息摘要一定是不相同的 給予一個訊息與訊息摘要，不可能找到另一個訊息會產生相同的訊息摘要

55 訊息摘要的要求

56 訊息摘要的要求

57 訊息摘要的要求

58 訊息摘要的要求

59 碰撞 當給予兩個訊息，兩個的訊息摘是相同的時，稱為碰撞 訊息摘要演算法通常會產生訊息摘要的長度 任兩個訊息發生訊息摘要碰撞的機率
128位元 160位元 任兩個訊息發生訊息摘要碰撞的機率 1 / 2128 1 / 2160 實際發生碰撞非常罕見

60 訊息摘要的例子

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

62 The End