2002 Rivest, Shamir, Adleman —— 三個年輕人與一張彩票式質數#

「1977 年 4 月，三位 MIT 學者用『大數難分解』這個看似 沒用的數論事實，發明了能保護全世界金融的演算法。 當年 RFC 提案被 NSA 勸退——如今它無所不在。」

案件檔案#

前因#

1976 年 Diffie–Hellman（2015 案）提出公鑰構想，但只有 金鑰交換，沒有真正的一般性加密。三人在 1977 年春 讀到 DH 論文後追問：能否造一個「公開的鎖＋私藏的鑰」？ 他們從數論教科書尋找「單向函數」的候選人。

線索與推理#

線索一：候選單向函數的偵查#

線索二：RSA 演算法（1977）#

金鑰生成：
  選大質數 p, q → N = pq；φ(N) = (p−1)(q−1)
  選 e 與 φ(N) 互質；d ≡ e⁻¹ (mod φ(N))   ← 擴展歐幾里得
  公鑰 (N,e)，私鑰 d
加密：c = mᵉ mod N        解密：m = c^d mod N
正確性（歐拉定理）：c^d ≡ m^{ed} ≡ m^{1+kφ} ≡ m (mod N)
安全性支柱：已知 N 求 φ(N) ⟺ 分解 pq → 指數級難

歐拉/費馬小定理的直接工程化——2000 年前數論的 「純數學」首度成為軍事級基礎設施。簽章即反序： σ = h(m)^d，驗證 σ^e = h(m)。

線索三：安全性假設的精緻化#

單純「分解難」不夠。後續理論補強：

• OAEP 填充（Bellare–Rogaway 1994）：在隨機預言模型下 證明選擇明文安全 → 抗結構性攻擊
• 已知攻擊歷史：共模攻擊、小指數廣播（Håstad）、 時序旁路（Kocher 1996）——密碼學是假設與攻擊的 永續軍備賽

線索四：那段歷史插曲#

1977 年〈A Method for Obtaining Digital Signatures and Public-Key Cryptosystems〉投稿前，Rivest 曾受 NSA 來信 勸撤。1983 年 MIT 獲專利。Gardner 在《Scientific American》 刊登後，全球密碼龐克運動點燃（PGP 1991）。

理論評析#

RSA 的偵探學意義：安全性 = 複雜度假設 + 結構設計。 它把 P vs NP 式的「難解性」（1982、1993 案）從學術 概念變成金融合約的擔保。若量子電腦（Shor 演算法， 1994）成熟，N= pq 的單向性崩塌——後量子密碼遷移 （NIST 2024 標準化 ML-KEM 等）正是此案的續集。

後果#

• TLS/HTTPS、SSH、電子簽章法、加密貨幣錢包皆以 RSA 或其表親為基石。
• Adleman 另闢 DNA 計算（1994）；Shamir 另創秘密共享 與差分分析密碼攻擊；Rivest 另創 RC4 與選票密碼學。

關聯案件#

→ 2015-Diffie-Hellman與公鑰密碼學、2000-Andrew-Yao與偽隨機性及複雜度理論、1995-Manuel-Blum與計算不可辨識及密碼學