RSA 算法是如何誕生的

        最近為了研究某個極其無聊的問題，讀了一些公鑰加密的歷史，意外地發現這段歷史竟然非常有趣。尤其是 RSA 算法的誕生過程，被很多書寫得非常勵志，看得人熱血澎湃。果然比起算法本身，這些背后的故事更能吸引我的興趣。

        RSA 算法具體是怎么回事，我就不在這瞎說了。簡介可以看 Wikipedia，如果想形象一點理解算法本身，這兒有個不錯的視頻，可以通過它了解 RSA 的基本思想。我就直接從 RSA 這三個人說起了。參考的書籍資料列在文末。

        RSA 背后的三個小伙

        RSA 是由三個提出者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的姓氏首字母組成的。這三個人風格迥異，組成了一個技能互補的完美團隊。

        Ron Rivest，RSA 中的 R。他在耶魯讀數學系，隨后跑到斯坦福讀計算機科學系研究人工智能。他所研究的課題——讓機器人在沒有人干預的情況下在停車場散步，在那個計算機科學系僅 成立四年的年代明顯太過樂觀，但他依然樂此不疲。畢業后他接受 MIT 任教的工作機會。也許是因為多年積累的科研氛圍，他對新技術非常興奮，大量閱讀前沿文獻。與此同時，他認為迷人的理論應該與現實世界相結合，才能散發魅 力，對世界有所改變，這也是他的理想。

        Adi Shamir，RSA 中的 S。他是以色列人，和 Rivest 一樣，學數學后轉計算機科學進一步深造，畢業后以訪問學者的身份來到 MIT。他很聰明，學習能力超強。雖然他在數學上的造詣頗深，但起初他在算法方面的知識十分匱乏，當他接到 Rivest 關于算法高級課程講授的邀請信時連連叫苦，教算法已經夠嗆了，還什么高級課程？給博士生講的么？雖然如此，他還是硬著頭皮前往 MIT，之后很快投入到學習中，整天泡在圖書館，讀了一書架關于算法的書籍，最終僅用兩周便掌握了所需的知識。

        Leonard Adleman，RSA 中的 A。自幼胸無大志，從未想過做什么數學家。讀大學時受各方面影響，甚至包括電視節目的 影響，在專業選擇上猶豫不決，最終因為學數學會有大量時間做別的而選擇就讀數學系。畢業后在美國銀行做程序員，之后想去學醫，被錄取了卻又改變主意想研究 物理，上了幾堂課又覺得沒意思。最后他怕掛科對找工作有影響，跑去圖書館借了本計算機科學的書，一直沒還，學校就會因此扣留成績單。輾轉幾次后，他最終選 擇讀計算機科學 PhD。畢業后同樣在 MIT 任教。

        這三人當時都非常年輕，二十多、三十出頭的樣子。他們的辦公室距離很近，可以經常串門。于是故事就從一次 Adleman 的串門開始了。

自左至右：Adi Shamir, Ron Rivest, Leonard Adleman (via)

        42 次的失敗

        1976 年底的某天，Adleman 無意推開 Rivest 的房門。熱愛新技術的 Rivest 果不其然正拿著份樓上的  Whitfield Diffie 與 Martin Hellman 合 作發表的新論文研究。自認為對前沿理念無所不曉的 Rivest，沒料到這篇文章提出了一個前所未有的思路，這讓他興奮不已。正琢磨著，Adleman 推門進來了，Rivest 便忘我地向 Adleman 講解了這篇論文中所述的思想，在 Adleman 聽起來大約是這樣的：

公鑰密碼 blah blah blah…不對稱密碼 blah blah blah…單向函數 blah blah blah…但是符合條件的單向函數目前沒找到。我有信心找到這樣的單向函數，你看你要不要和我一起試試？

        這些顯然不足以讓早已下決心走純理論路線的 Adleman 動心，對此他只是報以一個“禮貌的哈欠”。想當初選擇讀計算機科學，除了方便找工作，Adleman 還深受馬丁加德納專欄的影響。專欄中寫到的哥德爾定理讓他感到驚艷，深深體會到數學之美，如今只有高斯之流方能入他的眼，眼下 Rivest 滔滔不絕的什么加密解密，在他看來既不高級也不好玩。

        好在 Rivest 拉到了另一個同盟，也就是隔壁的 Shamir。Shamir 一聽說這篇文章就立刻意識到它的價值，二人一拍即合，開始了他們晝夜不休的單向函數尋找之旅。因為兩人都頭腦靈活，很快就想到了一些方案。盡管 Adleman 不情愿參與其中，他們還是會把結果拿給 Adleman，Adleman 的角色就是逐個擊破這些方案，找出各種漏洞，給那兩個頭腦發熱的人潑點冷水，免得他們走彎路。

        三人走火入魔一般，吃飯聊、喝酒聊，甚至去滑雪度假也不忘討論這件事。Shamir 就在滑雪的時候想到了一個絕妙的點子，以至于把滑雪板都落在了身后。當他意識到這一點回頭去取時，卻又不幸忘記了那個一閃而過的點子。相對來說給他們啟發 的 Diffie 要幸運一些，他在下樓買可樂的時候同樣讓靈感溜走，好在上樓的過程中他又想起來了，這個差點溜走的靈感正是 Rivest 那天手中所拿論文的核心思想，為 RSA 算法奠定了基礎。

        起初 Rivest 和 Shamir 構造出來的算法很快就能被 Adleman 破解，二人受到強烈的打擊，以至于有一階段他們走向了另一個極端，試圖證明 Diffie 他們的想法根本就是不靠譜的。但慢慢的，破解變得沒那么容易，特別是他們的第 32 號方案，Adleman 用了一晚上才找出漏洞，這讓他們感覺勝利就在眼前。

        就這樣，Rivest 和 Shamir 先后拋出了 42 個方案，雖然這 42 個全部被 Adleman 擊破，不過他們的努力并不算白費，至少指出了 42 條錯誤的路線。

        算法的誕生與命名

        1977 年四月，Rivest 和其余兩人參加了猶太逾越節的 Party，喝了些酒。到家后 Rivest 睡不著，隨手翻了翻數學書，隨后一個靈感逐漸清晰起來。他大氣不敢出一口，冷靜下來連夜整理自己的思路，一氣呵成寫就了一篇論文。次日，Rivest 把論文拿給 Adleman，做好再一次徒勞的心理準備，但這一次 Adleman 認輸了，認為這個方案應該是可行的。

        按照慣例，Rivest 按姓氏字母序將三人的名字署在論文上，也就是 Adleman、Rivest、Shamir，但 Adleman 總覺得自己貢獻微乎其微，不過是潑潑冷水，不至于還要署個名，便要求 Rivest 拿掉自己的名字。在 Rivest 的堅持下，他最終要求至少把自己的名字放到最后。也正因為如此，RSA 叫做 RSA 沒有被叫做 ARS。雖然 Adleman 一開始認為這注定是他諸多論文中最不起眼的一篇，RSA 走紅后他還是調侃說，越來越覺得 ARS 更順口了。

        之后

        之后的歷史我們就非常熟悉了，他們的論文受到各方贊賞。Rivest 還把論文發給馬丁加德納一份，加德納非常感興趣，把 Rivest 請到家里面談，進一步了解 RSA 算法。當然此前，加德納還不忘先表演一個撲克魔術。這次會面也促成后來馬丁加德納在他著名的專欄刊登 RSA 算法及破解獎金的故事。至于 R、S、A 這三人，依然保持著友誼，還成立了 RSA 公司，賺了一大筆錢。

        最后，既然 RSA 是根據提出者命名的，必然也逃不出 Stigler’s law 的魔爪。的確從時間上來說，RSA 這三人并非最早提出這個算法的人。事實上早于這三人四年時間，RSA 算法的思想就被英國學者構造出來了。早在 1969 年，英國密碼學家 James Ellis 就想到了公鑰密碼的概念，但同樣卡在尋找單向函數這個問題上。1973 年 9 月，年僅 26 歲的數學家 Clifford Cocks 聽 說這個思想后，在完全不了解狀況的心理狀態下花不到半小時就找到了 Rivest 他們苦思冥想的方案。但是，他們效力于政府，這個絕妙的想法立刻被相關機構封鎖，變為機密，誰也不能對外公開自己的發現，于是他們眼睜睜地看著 Diffie 及 RSA 等人重現了他們當時的研究并享有盛譽。直到 1997 年底，時隔二十余年，這件事情才被公之于眾。遺憾的是那時候 Ellis 已經過世一個月，直至逝世都是一個無名英雄。

        參考資料

• Crypto: How the Code Rebels Beat the Government–Saving Privacy in the Digital Age：Steven Levy 所著，大部分內容都是從這本書了解到的。書里從 Whitfield Diffie 的八卦（是真的八卦，和他老婆的相遇之類）說起，一直說到非常現實的 NSA 涉入等情節，寫得很詳細很有趣。中譯本譯作《隱私的終結》，但翻譯水平非常有限，比如把愛倫坡譯成艾倫坡和阿蘭坡兩種不同譯法，把 cutting-edge 翻譯成邊緣，或者干脆把算法水平有待提高翻譯成精通算法什么的…
• The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography：中譯本《密碼故事》，除了密碼從古至今的演變，書里還單獨對 Ellis 和 Cocks 等人的工作做了詳細的講述。我還沒看完這本書，但感覺會很有意思。
• 關于 Adleman 的更多八卦可以看這篇采訪，總覺得他的氣場和其余兩人很不搭，各種變卦和無所謂。啊對了，Adleman 也是將計算機病毒命名為 Computer virus 的人。