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

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

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

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

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

公開金鑰密碼學

公開金鑰密碼學

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

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

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

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

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

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

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之間的關係可以表示為：

RSA演算法

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} 的安全

RSA範例 － 加/解密

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

模數算數的指數運算 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

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

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

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

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

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

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

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