第 6 章　里維斯特、薩莫爾與阿德曼：RSA 密碼學的數學魔術#

6.2 1977 年 RSA 演算法的誕生：大質數相乘容易、因數分解極難的單向函數威力#

6.2.1 MIT 的三個人與一次派對#

1977 年春，MIT 的 Ronald Rivest、Adi Shamir、Leonard Adleman（Adleman 為新聘助理教授）讀到 Diffie–Hellman 論文，決心構造第一個公鑰加密方案。流傳的經過：經過多次失敗（Adleman 自述參與約 40 種失敗方案，他的角色主要是「殺方案」），1977 年 4 月的一次猶太逾越節派對後（Adleman 家），Rivest 在深夜靈感中寫出「A–D–H」函數雛形，次日三人完成系統，命名按 Rivest–Shamir–Adleman（Adleman 自述本以為自己只是「被放進作者名單的殺手」）。

6.2.2 數學骨架#

選兩大質數 \(p,q\)，令 \(n=pq,\ \varphi(n)=(p-1)(q-1)\)；取 \(e\) 與 \(\varphi\) 互質、求 \(d\equiv e^{-1}\pmod{\varphi(n)}\)。加密／解密：

正確性由歐拉定理保證；安全性寄託於：由 \(n\) 反求 \(\varphi(n)\) 等價於分解 \(n\)——大數分解被視為計算難題（因數分解至今無多項式時間古典算法）。私鑰 \((d)\) 不必傳送，公鑰 \((n,e)\) 可公開——鑰匙配送問題消失。

6.2.3 首秀與保密之爭#

• 1977 年 8 月 Scientific American「數學遊戲」專欄（Martin Gardner）刊出 RSA 描述與一個 129 位挑戰數（RSA-129），獎金 100 美元——RSA 一夜成名；
• NSA 曾試圖阻礙學術密碼論文（Shamir 赴以演講受「請求」的插曲、1977 IEEE 會議撤稿事件）；
• 1994 年，全球 600 餘台電腦以二次篩法分解 RSA-129——「挑戰數的壽命」成為算力增長的公眾教材。

6.2.4 前因後果#

• 前因：6.1 公鑰思想＋數論（歐拉、費馬小定理）＋MIT 開放學術文化。
• 事件：1977 RSA 發明、1983 獲美國專利（US 4,405,829）。
• 後果：非對稱密碼成為標準；數位簽章（以私鑰簽、公鑰驗）使「身份與完整性」上線——6.3 的商業化大戲登場。

下一節：6.3 RSA 公司