認識 RSA 加密演算法

簡介

1976 年以前，所有的加密方法都是同一種模式，即對稱加密演算法：

• 甲方選擇某一種加密規則，對訊息進行加密。
• 乙方使用同一種規則，對訊息進行解密。

1976 年，兩位美國密碼學家 Whitfield Diffie 和 Martin Hellman 提出了新的構思，可以在不直接傳遞密鑰的情況下，完成解密。這種新的加密模式即非對稱加密演算法：

• 乙方生成一把公鑰和一把私鑰。公鑰是公開的，任何人都可以獲得，而私鑰則是保密的。
• 甲方獲取乙方的公鑰，然後用它對訊息進行加密。
• 乙方得到加密後的訊息，用私鑰進行解密。

1977 年，三位數學家 Rivest、Shamir 和 Adleman 設計了一種算法，可以實現非對稱加密演算法。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

這種算法非常可靠，密鑰越長，它就越難破解。對極大整數做因數分解的難度決定了 RSA 演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 演算法愈可靠。

數學概念

互質關係

如果兩個正整數，除了 1 以外，沒有其他公因子，就稱這兩個數是互質關係。比如，15 和 32 沒有公因子，所以它們是互質關係。

歐拉函數

對正整數 n，歐拉函數是小於等於 n 的正整數中與 n 互質的數的數目，以 φ(n) 表示。

比如，在 1 到 8 之中，有多少個數與 8 構成互質關係？在 1 到 8 之中，與 8 形成互質關係的是 1、3、5、7，所以 φ(8) 等於 4。

其中有一種情況，如果 n 可以被分解成兩個互質的整數之積，則積的歐拉函數等於各個因子的歐拉函數之積。

比如，φ(56) = φ(8×7) = φ(8)×φ(7) = 4×6 = 24。

實作

假設 Alice 要與 Bob 進行加密通訊，Alice 該如何生成公鑰和私鑰？

第一步，隨機選擇兩個不相等的質數 p 和 q。Alice 選擇 61 和 53。這兩個質數越大，就越難破解。

const p = 61n;
const q = 53n;

第二步，計算 p 和 q 的乘積 n。n 的長度就是密鑰長度。3233 寫成二進制是 110010100001，一共有 12 位，所以這個密鑰就是 12 位。實際應用中，RSA 密鑰一般是 1024 位，重要場合則為 2048 位。

const n = p * q; // 3233n

第三步，計算 n 的歐拉函數 φ(n)。Alice 算出 φ(3233) 等於 60 乘以 52，即 3120。

const r = (p - 1n) * (q - 1n); // 3120n

第四步，隨機選擇一個整數 e，條件是 1 < e < φ(n)，且 e 與 φ(n) 互質。

const gcd = (a, b) => b ? gcd(b, a % b) : a; // 取最大公因數

let e = 1n;
for (let i = 2n; i < r; i++) {
  if (gcd(i, r) === 1n) {
    e = i; // 7n
    break;
  }
}

第五步，計算 e 對於 φ(n) 的模反元素 d。所謂「模反元素」就是指有一個整數 d，可以使得 e×d 被 φ(n) 除的餘數為 1。

let d;
for (let i = e + 1n; i < r; i++) {
  if ((i * e) % r === 1n) {
    d = i; // 1783n
    break;
  }
}

第六步，將 n 和 e 封裝成公鑰，然後將 n 和 d 封裝成私鑰。

const pubKeyN = n;
const pubKeyE = e;
const priKeyN = n;
const priKeyD = d;

加密與解密

假設 Bob 要向 Alice 發送加密訊息 m，他要用 Alice 的公鑰 (n, e) 對其進行加密。

const m = 100n;
const encrypted = m ** pubKeyE % pubKeyN; // 2872n

Alice 拿到 Bob 發來的 2872n 以後，就用自己的私鑰 (n, d) 對其進行解密。

const decrypted = encrypted ** priKeyD % n; // 100n

因此，Alice 知道了 Bob 加密前的原文就是 100n。

可靠性

大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。

舉例來說，我們可以對 3233 進行因數分解（61×53），但是沒辦法對以下整數進行因數分解：

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

它等於以下兩個質數的乘積：

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

這大概是人類已經分解的最大整數。比它更大的因數分解，還沒有被報導過，因此目前被破解的最長 RSA 密鑰就是 768 位。

程式碼

• rsa.go

參考資料

• RSA 算法原理（一）
• RSA 算法原理（二）