基礎密碼學 非對稱式金鑰加密法 樹德科技大學 資訊工程系 林峻立 助理教授

非對稱式金鑰密碼系統的概念 解決兩大金鑰的議題： 金鑰分送 數位簽章 非對稱式金鑰密碼學使用兩把不同的金鑰：一把為私密金鑰（private key）、一把為公開金鑰（public key） 公開金鑰： 公開並用於加密訊息、驗證簽章(即是解密) 私密金鑰： 私密保存，用來解密訊息、簽署（建立）簽章(即是加密)

公開金鑰密碼學 – 加解密

公開金鑰密碼學 – 數位簽章

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

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 運算的複雜度

RSA範例 這是一個較為實際的例子。我們選擇 512 位元的 p 與 q，然後計算 n 及 φ(n)，接著選擇 e 並檢查其是否與 φ(n) 互質，然後計算 d。最後，我們顯示加密與解密的結果。整數 p 是 159 位數。

RSA範例 整數 q 是 160 位數。 模數 n = p × q，其為 309 位數。

RSA範例 φ(n) = (p − 1)(q − 1) 為 309 位數。

RSA範例 Bob 選擇 e = 35535（理想值是 65537），並測試確認其與 φ(n) 互質。然後，他找到 e 在模 φ(n) 下 的乘法反元素 d。

RSA範例 Alice 想要傳送訊息「THIS IS A TEST」，這個訊息可經由 00 到 26 的編碼系統改成數值（26 是「空白」字元）。 Alice 計算密文為 C = Pe，即

RSA範例 Bob 能夠使用 P = Cd 而將密文回復成明文，即 在解碼後，回復的明文為「THIS IS A TEST」。

ElGamal 密碼系統 除了 RSA，另外一個公開金鑰密碼系統是 ElGamal 密碼系統(ElGamal cryptosystem)，根據發明者 Taher ElGamal 命名。ElGamal 是基於離散對數問題。

ElGamal 系統的金鑰產生、加密及解密程序

橢圓曲線密碼系統 雖然 RSA 與 ElGamal 是安全的非對稱式金鑰密碼系統，但它們的安全是有代價的，也就是需要大的金鑰長度。研究學者已經在尋找替代方案，以提供相同的安全等級，但金鑰長度較小。其中一個有希望的替代方案便是橢圓曲線密碼系統（elliptic curve cryptosystem, ECC）。 ECC 的安全是基於解橢圓曲線對數問題的困難度上。

使用橢圓曲線的 ElGamal 密碼系統

訊息完整性 至目前為止，我們已經研讀的密碼系統可以提供保密性或機密性，但是並未提供完整性。然而，我們有時可能不需要機密性，卻必須有完整性。

文件與指紋 保護文件完整性的方法之一是使用指紋（fingerprint）。如果 Alice 需要確保她的文件內容不會被改變，她可以在文件的底部按印指紋。

訊息與訊息摘要 相對於文件與指紋的電子版本是訊息與摘要。

檢查完整性

密碼雜湊函數的準則 一個密碼雜湊函數必須滿足三個準則︰ 抗前像（preimage resistance） 抗第二前像（second preimage resistance） 抗碰撞（collision resistance）

抗碰撞

SHA-512 的訊息摘要

Whirlpool 雜湊函數 Whirlpool 是一個迭代式密碼雜湊函數，植基於 Miyaguchi-Preneel 機制，使用對 稱式金鑰區塊加密法來代替壓縮函數，即是適用於此目標的改良 AES 加密法。

Whirlpool 雜湊函數

安全雜湊演算法的特性

篡改偵測碼 篡改偵測碼（modification detection code, MDC）是一個訊息摘要，可以證明訊息的完 整性︰訊息沒有被更改過。如果 Alice 需要傳送訊息給 Bob，並且確保訊息在傳輸過程不會 被更改，Alice 可以建立一個訊息摘要 MDC，並且把訊息和 MDC 傳送給 Bob。Bob 可以從訊息建立新的 MDC，並且比較收到的 MDC 和此新建立的 MDC，如果它們相同，則訊息沒有被更改過。

篡改偵測碼

訊息確認性 訊息摘要並不會確認訊息的傳送者，為了提供訊息的確認性，Alice 需要提供證據以證明這是 Alice 所傳送的訊息，而非冒充者所傳。密碼雜湊函數所產生的摘要通常稱為篡改偵測碼，其能偵測訊息的任何更改，而對於訊息確認（資料來源的確認），我們需要的是訊息確認碼。

訊息確認碼

數位信封 Digital Envelop

數位簽章 Digital Signature

X.509 Public-Key Certificate

Key Terms Symmetric Cryptosystem Asymmetric Cryptosystem Secret key Master key Session key Asymmetric Cryptosystem Private key Public key