# RSA 筆記：非對稱加密的基礎
## 先建立畫面：乘起來容易，拆回去難
拿兩個質數出來，比如 `61` 跟 `53`，把它們乘起來一點都不費力：`61 × 53 = 3233`，心算都做得到。但反過來，如果我現在只給你 `3233` 這個數字，要你回答「這是哪兩個質數相乘出來的」，你得一個一個質數去試除（2, 3, 5, 7, 11...）才找得到 `61` 跟 `53`——位數一多，這個「試除」的成本會爆炸式增加。
RSA 的整個安全性，就建立在這個「正向乘法很快、反向分解很慢」的不對稱性上，只是把 `61`、`53` 換成長度動輒 1024 bit（超過 300 位數）的質數。這個「反過來很難」的問題，正式名稱叫**整數分解問題**。
## 金鑰是怎麼從這個難題長出來的
拿兩個大質數 `p`、`q`，相乘得到 `n = p × q`，這個 `n` 就是公鑰跟私鑰共用的「模數」。接著算出 `n` 的歐拉函數 `φ(n) = (p-1)(q-1)`，挑一個跟 `φ(n)` 互質的數當公開指數 `e`（業界慣例用 `65537`），再用擴充歐幾里得演算法算出 `e` 對 `φ(n)` 的模反元素 `d`，也就是私鑰指數。
- 公鑰是 `(n, e)`
- 私鑰是 `(n, d)`，但**要算出 `d`，非得知道 `p`、`q` 不可**（`φ(n)` 依賴 `p-1` 跟 `q-1`）
所以只知道公鑰 `(n, e)` 的人，如果想反推出私鑰 `d`，唯一的路就是先把 `n` 分解回 `p × q`——這就是為什麼整數分解問題一旦被攻破，RSA 就跟著垮。目前對 2048 bit 以上的 `n`，沒有任何已知算法能在合理時間內分解。
用 Web Crypto API（瀏覽器跟 Node.js 是同一份規格）把一組真的 RSA 金鑰匯出成 JWK 格式攤開來看，可以直接驗證私鑰確實是公鑰的「超集合」：
```
公鑰欄位: alg, e, ext, key_ops, kty, n
私鑰欄位: alg, d, dp, dq, e, ext, key_ops, kty, n, p, q, qi
n 是否相同: true
e 是否相同: true
```
私鑰裡的 `n`、`e` 跟公鑰完全一樣，多出來的 `d`（私鑰指數）、`p`、`q`（那兩個質數本身！）、`dp`/`dq`/`qi`（CRT 加速用的中間值）才是真正的秘密。這也直接回答了一個常見的誤會：如果把「私鑰」對外公開、只留著「公鑰」保密，並不會多一層保護——公開出去的私鑰裡已經包含了 `p`、`q` 這兩個因數，攻擊者根本不用做任何分解就直接拿到答案；反過來把公鑰藏起來也沒用，因為私鑰檔案裡本來就有一份 `n`、`e`。真正決定安全性的，永遠是「誰拿得到 `p`、`q`（或等價的 `d`）」，跟你怎麼稱呼哪把鑰匙無關。
## 直接拿 RSA 加密資料：為什麼行不通
如果只是把 RSA 的數學（`密文 = 明文^e mod n`）原封不動拿來加密，會踩到兩個坑：一是這個運算本身是確定性的（同樣明文、同樣公鑰，永遠算出同樣密文），攻擊者可以把猜測的明文加密後拿去比對密文；二是明文能塞進去的長度被 `n` 的位元組數卡死。實務上都會加一層叫 **OAEP** 的隨機化填充機制來解決第一個問題，但第二個「長度上限」的限制依然存在，而且比想像中更緊。
拿 2048 bit 金鑰、OAEP 搭配 SHA-256 實測：
```
190 bytes: OK
191 bytes: FAIL: The operation failed for an operation-specific reason
```
換成 SHA-1 上限會變寬（因為雜湊輸出比較短，佔用的填充空間比較少）：
```
214 bytes: OK
215 bytes: FAIL: The operation failed for an operation-specific reason
```
這個界線不是巧合，RFC 8017 給的公式是 `明文長度上限 = k - 2×hLen - 2`（`k` 是金鑰位元組數，`hLen` 是雜湊輸出位元組數）。2048 bit 金鑰 `k = 256` bytes，SHA-256 輸出 `hLen = 32` bytes：`256 - 64 - 2 = 190`，跟實測完全對上。
還有一個容易忽略的細節：OAEP 用的雜湊演算法是**綁在金鑰匯入當下**的，不是加解密呼叫時才傳。同一把私鑰、同一份 PEM 內容，加密端用 SHA-256、解密端匯入時卻選了 SHA-1，解密一樣會失敗：
```
解密失敗（符合預期）：OperationError: The operation failed for an operation-specific reason
```
## 混合加密：讓 RSA 只做它擅長的事
190 bytes 的上限意味著 RSA 幾乎不可能直接拿來加密一份文件或一張圖片。業界標準的解法（TLS、PGP 都是這樣做）是**混合加密**：每次加密都隨機產生一把 AES-256 金鑰，拿它去加密真正的內容（AES-GCM 對長度沒有這種硬性上限），再把這把固定只有 32 bytes 的 AES 金鑰本身用 RSA-OAEP 包起來。32 bytes 遠低於任何常見金鑰長度的 190 bytes 上限，所以不管原始內容多大，RSA 只需要負責包住這一小段對稱金鑰，真正的加解密工作全部交給 AES。組合起來的密文結構是：
```
[RSA-OAEP 包住的 AES 金鑰][12 bytes AES-GCM IV][AES-GCM 密文 + 16 bytes 認證標籤]
```
解密時反過來：先用 RSA 私鑰解出 AES 金鑰，再用這把金鑰去解真正的內容。
## 真實世界裡 RSA 出過的問題，都不是數學本身被攻破
整數分解問題到現在都沒有被攻破，但 RSA 的**實作**史上出過幾次真實漏洞，分清楚這些跟「數學本身」的差別很重要。
**Bleichenbacher's Attack（1998）**——早期版本的 RSA 填充方案（PKCS#1 v1.5，不是這裡用的 OAEP）在解密失敗時，伺服器回傳的錯誤訊息會洩漏「填充格式對不對」這個資訊。攻擊者拿一份密文反覆送、根據伺服器回應是否報「填充格式錯誤」，就能一位元一位元把明文清出來，完全不需要破解任何數學難題，純粹是實作細節洩漏了一個可利用的旁路（side channel）。這正是為什麼現在都改用 OAEP——OAEP 的設計目的之一就是讓填充驗證失敗時不會洩漏這種可利用的資訊。
**ROCA（2017）、2008 年 Debian OpenSSL 事件**——這兩起都是「金鑰產生階段」出問題：前者是某廠牌安全晶片產生的質數帶有可預測的結構，後者是 Debian 某個版本的亂數產生器被意外改壞、可能產生的私鑰空間小到能被窮舉。兩起事件的共通點是「產生 `p`、`q` 這兩個質數的過程不夠隨機」，不是「已知 `n` 之後可以分解回 `p×q`」——難題本身還是難的，是產生金鑰的那一步先天有瑕疵。
至於「量子電腦會不會讓 RSA 過時」——會，但這跟上面說的實作漏洞是完全不同層次的威脅：Shor's Algorithm 在理論上能讓量子電腦有效率地分解大整數，一旦真的有夠大規模的量子電腦出現，RSA 的數學基礎會直接被繞過。但這個威脅同樣適用於橢圓曲線的離散對數問題，並不是「RSA 特別脆弱、換成 EC 就安全」——真正對量子電腦免疫的是另一整套稱為後量子密碼學（如 NIST 的 ML-KEM/Kyber）的獨立技術，跟 EC 沒有關係。
## 小結
| 項目 | 內容 |
|---|---|
| 依賴的難題 | 整數分解問題（給定 `n = p×q`，反推 `p`、`q`） |
| 公鑰 | `(n, e)` |
| 私鑰 | `(n, d)`，本質上等同持有 `p`、`q` |
| 2048-bit 公鑰大小（SPKI DER） | 294 bytes |
| 2048-bit 簽章大小 | 256 bytes |
| OAEP+SHA-256 明文上限 | 190 bytes（2048-bit 金鑰） |
| 直接加密大量資料的解法 | 混合加密：RSA-OAEP 只包一把 AES-256 金鑰 |
| 已知的實作漏洞 | Bleichenbacher（填充 oracle）、ROCA/Debian（弱亂數金鑰產生） |
| 數學難題本身被攻破過嗎 | 沒有（量子電腦是理論上的未來威脅，不分 RSA/EC） |