密碼學與網路安全 第9章 公開金鑰密碼學與RSA

Presentation on theme: "密碼學與網路安全 第9章 公開金鑰密碼學與RSA"— Presentation transcript:

1 密碼學與網路安全 第9章 公開金鑰密碼學與RSA

2 私密金鑰密碼學 傳統的私密／秘密／單一金鑰密碼學使用一把金鑰 傳送端和接收端共用同一把金鑰 所以也稱為對稱式加密
若通訊時洩漏金鑰，會危及通訊安全 而且也無法確認傳送端的真實身份

3 公開金鑰密碼學 公開金鑰密碼學是整個密碼學最重大的發展，也是整個密碼學演進史唯一真正的變革 使用兩把金鑰：公開金鑰和私密金鑰
也稱為非對稱加密，兩端使用不一樣的金鑰 公開金鑰演算法是以數學函數為基礎，而非替代和重排

4 為什麼要使用公開金鑰加密？ 解決兩大金鑰的議題： 公開金鑰加密是由菲迪和赫爾曼在1976年於史丹佛大學公開發表 金鑰分送 數位簽章
安全單位更早之前也已提出類似的概念，但未公開

5 公開金鑰密碼學 公開金鑰／雙金鑰／非對稱密碼學使用兩把金鑰： 公開金鑰：公開並用於加密訊息、確認簽章(即是解密)
私密金鑰：只由接收端擁有，用來解密訊息、簽署（建立）簽章(即是加密) 非對稱式因為 加密訊息或確認簽章之金鑰無法解密訊息或建立簽章

6 公開金鑰密碼學

7 公開金鑰密碼學

8 公開金鑰的特徵 非對稱演算法的加密是依賴一把金鑰，並且用另一把不同但相關的金鑰來解密，這些演算法具有以下重要的特性：
若只知道密碼系統的演算法和加密金鑰，無法經由計算得到解密金鑰 對於已加密的密文而言，搭配另一把金鑰可以快快的解密 兩把金鑰的任一把可用來加密，另一把可用來解密（對某些演算法而言）

9 公開金鑰加密系統之認證加保密

10 公開金鑰密碼系統的應用 廣義的三大應用： 有些演算法適合這三種應用，而有些只能用在其中的一或兩種應用
加密／解密：傳送者以接收者的公開金鑰加密訊息 數位簽章：傳送者以自己的私密金鑰「簽署」訊息 交換金鑰：通訊雙方合作交換通訊金鑰 有些演算法適合這三種應用，而有些只能用在其中的一或兩種應用

11 公開金鑰的安全性 公開金鑰加密也會受到暴力法攻擊，雖然反制的對策也相同：使用更長的金鑰。不過，公開金鑰系統依靠某些反向的數學函數，這些函數的計算複雜度可能超過線性成長於金鑰位元數。所以金錀的大小必須 大得足夠抵擋暴力攻擊。 小得足以不會太難解密和加密。 另一種類型的攻擊，是找出某些方法而以公開金鑰計算出私密金鑰 (並未有數學證明此法無可破解！) 最後一種針對公開金鑰系統的特殊攻擊方式，屬於「可能訊息」攻擊法 假設欲傳送的明文是DES的56位元金鑰，則不論公開金鑰的金鑰長度有多長，只要加密256 種明文而得到256種密文即查表解密。這種攻擊法會簡化暴力攻擊而針對56位元金鑰。若要阻止這種攻擊，能在訊息之後加上一些隨機位元

12 RSA RSA是1977年由Ron Rivest、Adi Shamir、和Len Adleman在MIT所發展
是目前最好也最廣為使用的公開金鑰架構 使用指數運算式，將明文加密成二進位值小於整數n的區塊 n的大小通常是1024個位元 (故n 小於等於21024  1)

13 RSA演算法 傳送者與接收者都必須知道n值，傳送者知道e值，而只有接收者知道d值
Rivest、Shamir、Adleman發展的方法使用指數運算式，將明文加密成二進位值小於整數n的區塊 區塊大小必須要小於或等於log2(n) 實際上的區塊大小是i個位元（2i < n ≦ 2i+1） 某些明文區塊M和密文區塊C是以如下形式加密、解密： 傳送者與接收者都必須知道n值，傳送者知道e值，而只有接收者知道d值

14 RSA演算法 RSA演算法若要滿足公開金鑰加密，就必須符合以下要求： e和d之間的關係可以表示為：
若M < n、Med mod n = M，就有可能找出e、d、n的值 若M < n，要計算Me mod n和Cd mod n就相對容易 知道e和n而要找出d是不可行 e和d之間的關係可以表示為：

15 RSA演算法

16 RSA範例 - 產生金鑰 選擇質數：p=17 & q=11 計算 n = pq =17 × 11=187
選擇 e: gcd(e,160)=1; e=7 者出 d: de=1 mod 160 且 d < 160; d=23，使用擴充歐幾里德演算法即可算出。 公布公開金鑰 PU={7,187} 保持私密金鑰 PR={23,187} 的安全

17 RSA範例 － 加/解密

18 模數算數的指數運算 RSA的加密和解密都有整數的指數運算和取n同餘 以取n同餘來減小計算過程的中間值，讓計算變得實際可行

19 模數算數的指數運算 c = 0; f = 1 for i = k downto 0 do c = 2 x c
f = (f x f) mod n if bi == 1 then c = c + 1 f = (f x a) mod n return f

20 以公開金鑰加速運算 要以公開金鑰加速RSA演算法，通常要選擇特定的e值 e值最常見的選擇是65537（216 + 1）、3、17
這些選擇只有兩個1位元，因此能將數值乘法所需執行的指數減到最少 但太小的公開金鑰（例如e = 3）會讓RSA容易受到攻擊

21 產生RSA金鑰 RSA使用必須： 必須從夠大的集合選擇這些質數 p、q 決定質數p和q之後，要選擇e值並且計算d值，或者選擇d值、計算e值
選擇像是gcd(ø(n),e) = 1的e值，並且計算d ≡ e-1(mod ø(n))

22 RSA的安全性 4種可以攻擊RSA演算法的方法： 暴力法：要試過所有可能的私密金鑰 數學攻擊法：共有數種方式，其效果都等同於分解兩質數的乘積
計時攻擊法：這些方法依靠解密演算法的執行時間 選定明文攻擊法：這種類型的攻擊會刺探RSA演算法的特性

23 因數分解的問題 三種以數學運算攻擊RSA的方法： 將n分解成兩個質因數，最後算出 d ≡ e-1 (mod ø(n))
不需要先算出p和q而直接算出ø(n) 不需要先算出 ø(n)而直接算出d 大部分RSA密碼破解的焦點，是將n分解成兩個質因數

24 計時攻擊法 刺探者能經由記錄電腦解密的時間長短，而算出私密金鑰 Paul Kocher在1990年代中期所發展
計時攻擊不只適用於RSA，也適用其他的公開金鑰密碼系統 簡單的反制方法： 固定指數運算時間 隨機延遲 障眼法(在指數運算前將密文乘上某一隨機數字)

25 選定密文攻擊 (略) 基本的RSA演算法容易遭受選定密文攻擊 攻擊者選定了一些密文，然後給予對應的明文，並以目標的私密金鑰解密
然後選擇以目標私密金鑰處理過的資料區塊，就能得到破解密碼所需要的資訊 CCA攻擊RSA的簡單例子會利用如下的RSA特性：

26 總結 公開金鑰密碼學的原則 RSA 演算法 實作 安全性