密碼學 - RSA 與 PKCS#1

Posted on

RSA 是由麻省理工學院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 在 1977 年發表的，名稱就是取自他們三人姓氏的首字母。當時，他們受到了
1976 年 Diffie 和 Hellman 提出的公鑰密碼體制概念的啟發，致力於尋找一種實用的非對稱加密演算法。

PKCS#1 是 RSA 密碼學的一個標準，它定義了 RSA 密碼學中的很多重要概念和演算法，包括 RSA 的金鑰格式、加密和解密過程、簽章和驗證過程等。

本文將介紹 RSA 和 PKCS#1 的基本概念和原理，幫助你更好地理解這兩個重要的密碼學標準。

什麼是非對稱加密算法?

在討論 RSA 和 PKCS#1 之前，我們先來了解一下非對稱加密算法的基本概念。image 1

傳統的對稱加密算法，如 DES 和 AES，使用同一個金鑰進行加密和解密。這種方式的優點是速度快，但缺點是金鑰管理不便，尤其是在大規模網路環境中，安全地分發和保管金鑰成為一大挑戰。
非對稱加密算法，也稱為公鑰密碼體制，使用兩個不同的金鑰: 公鑰和私鑰。公鑰可以公開，而私鑰必須保密。

非對稱加密算法有三個主要用途:

加解密 – 公鑰加密， 私鑰解密

當 Alice 要向 Bob 發送加密消息時，先向 Bob 索取他的公鑰，然後用 Bob 的公鑰加密。

這樣，即使第三方攔截了密文，由於沒有對應的私鑰，也無法解密。當 Bob 收到密文後，用自己的私鑰解密，得到原始明文。

這種方式解決了金鑰分發的問題，非常適合在開放的網路環境中使用。

簽驗章 – 私鑰加密， 公鑰解密

如果 Alice 要向 Bob 證明一個消息確實是自己發的，可以先用雜湊函數(如 SHA-256)計算消息的摘要，然後用自己的私鑰加密這個摘要，作為簽章。Bob
收到消息和簽章後，用 A 的公鑰解密簽章，得到摘要，再與收到的消息計算雜湊值比對。

如果兩者一致，就能確認消息未被篡改，且確實來自 Alice。

金鑰協定 – 我方私鑰與對方公鑰能導出協定值

在某些場景下，通訊雙方需要協商出一個共同的金鑰，用於後續的對稱加密通訊。

非對稱加密可以安全地完成這個過程。例如在 Diffie-Hellman 金鑰交換協議中，雙方分別生成自己的私鑰，計算出對應的公鑰，然後交換公鑰。
接下來，雙方分別用自己的私鑰和對方的公鑰進行運算，最終得到一個相同的金鑰。

這個過程不需要直接傳送金鑰，而是通過公鑰和私鑰的數學性質，確保雙方得到相同的結果。

除了本文介紹的 RSA 算法，還有其他常見的非對稱加密算法，如: 離散對數、因式分解、ECC (橢圓曲線)、DSA (數位簽章算法)、晶格密碼學等。

水到渠成的非對稱加密算法

RSA 算法的發明還有一段鮮為人知的故事。

早在 1973 年，英國情報局的密碼學家 Clifford Cocks 就已經發明了一種類似 RSA 的非對稱加密算法。然而，由於當時這個發現被列為機密，因此Cocks 的工作無法公開發表。

直到 1997 年，這個被稱為「非祕密加密」(Non-Secret Encryption)的算法才被解密。雖然 Cocks 的發明比 RSA 早了幾年，但由於保密的緣故，並未對學術界產生影響。

RSA 的現況與挑戰

在眾多的非對稱加密算法中，RSA 因其優異的特性和廣泛的應用而備受矚目。以下我們將討論使用 RSA 的優缺點。

優點

支援每一種用途

RSA 是一種多功能的算法，它能夠同時支援加解密、簽驗章和金鑰協定三種主要用途。

這意味著，無論是需要保密通訊、數位簽章，還是金鑰交換。

RSA 都能提供解決方案。這種多功能性使得 RSA 在各種應用場景中都能發揮重要作用，大大簡化了系統設計和實作。

驗章速度快

與其他一些非對稱加密算法相比，RSA 在驗證簽章時具有速度優勢。

這是因為 RSA 驗章只需要進行一次公鑰運算，而產生簽章需要一次私鑰運算。由於公鑰運算通常比私鑰運算快，因此在需要大量驗證簽章的場合，如電子商務和電子政務中，RSA 能夠提供更高的效率。

這對於需要即時處理大量請求的系統來說，是一個重要優勢。

缺點與安全隱憂

量子電腦的威脅

RSA 的安全性是建立在大質數分解問題的困難性上。

目前，還沒有找到在經典電腦上高效率解決該問題的演算法。然而，隨著量子計算技術的發展，這種情況可能會發生變化。

理論上，量子電腦能夠使用 Shor 算法在多項式時間內分解大整數，這將徹底破解 RSA 的安全性。雖然目前的量子電腦還無法處理足夠大的數，但從長遠來看，這仍是 RSA 面臨的一個重大挑戰。

為此，密碼學界正在積極研究後量子密碼學，以應對未來可能出現的威脅。

RSA768 挑戰於 2009 年 12 月被破解

2009 年 12 月，一個國際研究小組成功分解了一個 768 位的 RSA 質數，完成了 RSA768 挑戰。這表明，隨著計算能力的提升，原本被認為是安全的金鑰長度可能不再足夠。

這促使人們使用更長的金鑰，如：2048 位甚至 4096 位，以獲得更高的安全性。然而，金鑰長度的增加，也會帶來更高的計算成本和通訊開銷。

https://www.infosecurity-magazine.com/news/768-bit-rsa-encryption-cracked/

NSA 植入後門的疑慮

2013 年，美國國家安全局(NSA)被指控在某些加密算法的標準中植入後門。

雖然這些指控主要涉及對稱加密算法和隨機數生成器，但也引發了人們對 RSA 等廣泛使用的算法的信任危機。這提醒我們，在選擇和實現加密算法時，需要謹慎評估其安全性和可信度。

https://www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220/

旁道攻擊的風險

除了理論上的安全性，RSA 的實作還面臨旁道攻擊的風險。

例如，時間攻擊可以通過分析加密操作的執行時間來推斷出私鑰的某些訊息。
聲學分析攻擊則可以通過記錄加密設備的聲音，萃取出 4096 位的 RSA 金鑰。

這些攻擊利用了現實中的物理特性，而非算法本身的數學基礎。為了抵禦此類攻擊，需要在實現中引入額外的防護措施，如時間攻擊防禦和物理隔離等。

選擇明文攻擊對 PKCS#1 v1.5 填充方案的影響

1998 年，Bleichenbacher 發現了一種針對 PKCS#1 v1.5 填充方案的選擇明文攻擊。該攻擊利用了 v1.5 方案對錯誤情況處理的差異，允許攻擊者在一定條件下恢復明文。
為了應對這一漏洞，RSA 實驗室在 PKCS#1 v2.0 中引入了更安全的 OAEP 填充方案。這提醒我們，在使用 RSA 時，需要同時關注演算法本身和配套的編碼、填充方案的安全性。

儘管存在這些安全隱憂，RSA 仍然是當前最為可靠和實用的非對稱加密算法之一。通過增加金鑰長度、採用安全的填充方案、引入旁道攻擊防護等措施，可以大大提高 RSA 的安全性。同時，密碼學界也在積極研究後量子密碼學，以應對未來可能出現的量子計算威脅。

RSA 的基本原理

RSA 三人組獨立發現了這種演算法，並率先將其公開發表。

他們注意到，如果找到一個數學函數，其正向計算很容易，但反過來計算卻非常困難，就可以用來構建公鑰密碼系統。

經過研究，他們發現大質數分解正好符合這個要求:

給定兩個大質數 p 和 q
計算 n = pq 很容易，反過來，給定 n，要分解出 p 和 q 卻非常困難。

基於這個思路，他們設計了 RSA 算法，使用質數 p 和 q 構造公鑰和私鑰，並利用模運算的性質實現加密和解密。這個算法不僅實現了非對稱加密，還可以用於數位簽章。

RSA 算法發表後，迅速獲得了廣泛的關注和應用。它的安全性建立在大質數分解問題的困難性上，至今仍未被證明可以在多項式時間內解決。隨著電腦性能的提升，RSA 所需的金鑰長度也不斷增加，目前一般推薦最少使用 2048 位或更長的金鑰。

RSA 的金鑰生成

在 RSA 加密系統中，每個使用者都需要產生一對金鑰 :公鑰和私鑰。這對金鑰必須符合一定的數學性質，才能保證加密和解密的正確性。

以下是 RSA 金鑰生成的詳細過程:

隨機選擇兩個不同的大質數 p 和 q。

這兩個質數必須足夠大，一般要求至少是 512 位(即十進制位數大約 155 位)，現在常用 2048 位甚至 3072 位。
選擇質數的方法可以用擴充歐幾里得算法和 Miller-Rabin 質數判定法。
為了確保安全，p 和 q 最好差不多大，且 (p-1) 和 (q-1) 中至少有一個大的質因數。

計算 n = p × q。

這個 n 就是 RSA 加密和解密時用到的模數，也是構成公鑰和私鑰的一部分。
n 的位數就是 RSA 金鑰的長度。
注意:一定要對 p 和 q 保密，不能讓任何人知道，因為只要知道 p 和 q，就可以算出私鑰。

計算 n 的歐拉函數 φ(n) = (p-1) × (q-1)。

根據歐拉定理，對任意正整數 a 和 n，如果 a 與 n 互質，那麼 a^φ(n) ≡ 1 (mod n)。
RSA 加密和解密的核心就是利用了這個定理。
要注意: φ(n) 也必須保密，因為知道了 φ(n) 就可以算出私鑰。

隨機選擇一個整數 e，作為加密指數，要求 1 < e < φ(n)，且 e 與 φ(n) 互質。

常見的 e 有 3、17、65537 等，一般建議使用 65537。
e 可以公開，和 n 一起作為公鑰 (n, e)。

計算 e 關於 φ(n) 的模反元素 d，使得 e × d ≡ 1 (mod φ(n))。

這個 d 就是解密指數，也就是 RSA 的私鑰。
計算 d 可以用擴充歐幾里得算法，因為 e 和 φ(n) 互質，所以一定存在模反元素 d。
d 必須絕對保密，如果洩露會導致私鑰被攻破。

所以，最終生成的 RSA 金鑰對就是:

公鑰: (n, e)
私鑰: (n, d)

RSA 的加密和解密

有了公鑰 (n，e) 和私鑰 (n，d)，我們就可以進行 RSA 的加密和解密操作了。
設要加密的明文為 M，密文為 C。

加密過程

首先，將明文 M 轉換為一個小於 n 的整數 m。如果 M 較長，可以分塊加密。
然後，使用公鑰 (n，e) 對 m 進行加密，得到密文 c:

c ≡ m^e (mod n)

將密文 c 傳送給接收方。

註記：^ 表示次方運算，mod 表示取模運算。

解密過程

接收方收到密文 c 後，使用私鑰 (n，d) 對 c 進行解密，得到明文 m:

m ≡ c^d (mod n)

最後，將 m 轉換回明文 M。如果 M 分塊加密，需要將各塊密文解密後拼接起來。

註記：^ 表示次方運算，mod 表示取模運算。

加密和解密原理

在這裡我們稍微整理一下。

當我們選擇了兩個質數 p 和 q，計算 n = pq 和 φ(n) = (p-1)(q-1)。

q， p is prime number
count n = p * q
count φ(n) = (p-1)(q-1)

然後選擇一個與 φ(n) 互質的整數 e 作為加密指數，再計算出 e 關於 φ(n) 的模反元素 d
作為解密指數，滿足 ed ≡ 1 (mod φ(n))。
公鑰為 (n，e)，私鑰為 (n，d)。

select e， 1 < e < φ(n)， e and φ(n) are coprime
count d = e^-1 mod φ(n)
public key is (n，e)， private key is (n，d)

對於明文 m (小於 n)，加密過程為:

c ≡ m^e (mod n)

解密過程為:

m ≡ c^d (mod n)

我們來展示解密能夠還原出正確的明文，即證明:

(m^e)^d ≡ m (mod n)

因為 ed ≡ 1 (mod φ(n))，所以存在整數 k 使得:

ed = 1 + kφ(n)

將其代入等式:

c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(1+kφ(n)) ≡ m × (m^φ(n))^k (mod n)

根據歐拉定理，當 m 與 n 互質時:

m^φ(n) ≡ 1 (mod n)

當 m 與 n 不互質時，m 只能是 p 或 q 之一，此時:

m^φ(n) ≡ m (mod n)

對於與 n 不互質的 m (即 m = p 或 m = q)，我們可以使用費馬小定理和中國剩餘定理來證明 m^φ(n) ≡ m (mod n)。
費馬小定理指出，如果 p 是質數，且 m 不是 p 的倍數，則:

m^(p-1) ≡ 1 (mod p)

假設 m = p，則:

p^(q-1) ≡ 1 (mod q)

因為 φ(n) = (p-1)(q-1)，所以:

m^φ(n) = p^((p-1)(q-1)) = (p^(p-1))^(q-1) ≡ 1^(q-1) ≡ 1 (mod q)

另一方面，因為 m = p，所以:

m^φ(n) ≡ 0 (mod p)

根據中國剩餘定理，如果兩個同餘方程:

x ≡ a (mod p)
x ≡ b (mod q)

其中 p 和 q 互質，則存在唯一解:

x ≡ a (mod p) 且 x ≡ b (mod q)

結合上述兩個同餘式，我們得到:

m^φ(n) ≡ m (mod n)

所以，(m^φ(n))^k ≡ 1 或 m (mod n)，因此:

(m^e)^d ≡ m (mod n)

這就證明了 RSA 的解密過程能夠正確還原出明文，而 RSA 的安全性就建立在，如果不知道 p 和 q，就難以計算出 d。

RSA 的簽章和驗證

RSA 除了可以用於加密和解密外，還可以用於數位簽章和驗證。

簽章過程

假設 Alice 要對一個消息 M 進行簽章，首先她需要計算消息的雜湊值 H(M)。然後，她使用自己的私鑰 (n，d) 對雜湊值 H(M) 進行加密，得到簽章 S:

S ≡ H(M)^d (mod n)

最後，她將消息 M 和簽章 S 一起發送給 Bob。

驗證過程

Bob 收到消息 M 和簽章 S 後，首先計算消息的雜湊值 H(M)。然後，他使用 Alice 的公鑰 (n，e) 對簽章 S 進行解密，得到解密值 D:

D ≡ S^e (mod n)

如果 D 等於雜湊值 H(M)，則認為簽章有效，否則認為簽章無效。

PKCS#1

接下來，我們來介紹 PKCS#1，這是 RSA 密碼學的一個標準，定義了 RSA 加密和簽章的基本格式。

PKCS#1 自 1991 年首次發布以來，經歷了多次修訂和更新:

  • PKCS#1 v1.1 ~ v1.3 (1991): 定義了 RSA 加密和簽章的基本格式。
  • PKCS#1 v1.5 (1993): 定義了 RSA 加密和簽章的基本格式。這些內容
  • PKCS#1 v2.0 (1998): 引入了 OAEP 填充方案，增強了安全性，發布在 RFC 2437 中。
  • PKCS#1 v2.1 (2002): 對 v2.0 進行了一些編輯上的修改和澄清，RFC 3447 就是基於這個版本。
  • PKCS#1 v2.2 (2012): 進一步完善了標準，並與 RFC 3447 保持一致。

填充方案

在 RSA 加密中，填充方案的選擇對於安全性至關重要。填充方案可以防止攻擊者利用某些數學特性來破解密文。以下是兩種主要的填充方案：

PKCS#1 v1.5 填充

PKCS#1 v1.5 填充方案是一種較早的填充方式，主要用於加密和簽章。它的填充過程如下：

  1. 在加密前，先將明文資料填充到特定長度。
  2. 填充過程中加入隨機資料，以防止相同的明文產生相同的密文。
  3. 將填充好的資料進行加密。

這種填充方案較為簡單，但在 1998 年被發現存在選擇明文攻擊的風險。為了提升安全性，後來引入了更為安全的填充方案。

範例：PKCS#1 v1.5 加密

現在，我們來看一個使用 PKCS#1 v1.5 填充方案的 RSA 加密的例子。假設我們要用 RSA 公鑰加密一段訊息 “HELLO”。

  1. 選擇 RSA 金鑰，公鑰 (n, e)，私鑰 (n, d)：
    • n = 3233
    • e = 17
    • d = 2753
  2. 轉換訊息為數字表示：
    • “HELLO” 對應的 ASCII 編碼為 [72, 69, 76, 76, 79]
    • 轉換為數字 M = 7269767679
  3. 應用 PKCS#1 v1.5 填充方案：
    • 假設金鑰長度為 128 位元 (16 位數字)，訊息長度為 8 位數字
    • 填充格式為：0x00 || 0x02 || PS || 0x00 || M
    • PS 為隨機生成的非零填充字節，使總長度達到 128 位元
      例如，填充後的資料可能為：00 02 AA BB CC DD 00 7269767679 (AA, BB, CC, DD 是隨機數)
  4. 進行 RSA 加密：
    • 使用公鑰 (n, e) 對填充後的資料進行加密
    • 計算：C ≡ M^e (mod n)
      例如，假設填充後的資料為 1234567890123456（僅作為範例）：
    • C ≡ 1234567890123456^17 (mod 3233)
  5. 傳送密文 C 給接收者。

數位簽章

PKCS#1 也定義了 RSA 數位簽章的標準格式。數位簽章用於驗證消息的完整性和來源，確保消息未被篡改且確實來自聲稱的發送者。簽章過程如下：

  1. 發送者對消息進行雜湊運算，生成消息摘要。
  2. 使用私鑰對消息摘要進行加密，生成簽章。
  3. 將簽章附加到消息後一同發送給接收者。

範例：PKCS#1 v1.5 數位簽章

假設我們要用 RSA 私鑰對訊息 “HELLO” 進行簽章。

  1. 選擇 RSA 金鑰，公鑰 (n, e)，私鑰 (n, d)：

    • n = 3233
    • e = 17
    • d = 2753

  2. 計算訊息的雜湊值：

    • 假設使用 SHA-256，訊息 “HELLO” 的雜湊值為 H(M)
      假設 H(M) = 123456（僅作為範例）

  3. 應用 PKCS#1 v1.5 填充：

    • 填充格式為：0x00 || 0x01 || FF...FF || 0x00 || H(M)
    • FF…FF 是一系列的填充字節
      例如，填充後的資料可能為：00 01 FF FF FF FF 00 123456（FF…FF 為填充字節）

  4. 進行 RSA 簽章：

    • 使用私鑰 (n, d) 對填充後的雜湊值進行加密
    • 計算：S ≡ H(M)^d (mod n)
      例如，假設填充後的資料為 7890123456（僅作為範例）：
    • S ≡ 7890123456^2753 (mod 3233)

  5. 傳送簽章 S 和原始訊息 M 給接收者。

驗證過程：

  1. 接收者接收到訊息 M 和簽章 S：

    • M = “HELLO”
    • S = 接收到的簽章

  2. 計算訊息的雜湊值 H(M)：

    • 使用相同的雜湊算法計算 H(M)

  3. 使用公鑰解密簽章 S：

    • 計算：D ≡ S^e (mod n)

  4. 比較解密結果 D 和計算的雜湊值 H(M)：

    • 如果 D == H(M)，則簽章有效
    • 否則，簽章無效

結論

RSA 和 PKCS#1 是現代密碼學中的重要組成部分，廣泛應用於加解密、數位簽章和金鑰交換等領域。
儘管 RSA 面臨量子計算的挑戰，但其數學基礎和實踐應用使其仍然是一種可靠的加密方式。

隨著密碼學的不斷發展，新技術和新算法的出現將進一步提升資料保護的安全性。

也許你也會想看看