RSA 算法是如何誕生的

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

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

RSA 背后的三個小伙

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

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

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

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

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

42次的失敗

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

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

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

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

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

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

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

算法的誕生與命名

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

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

之后

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

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

參考資料

• Crypto: How the Code Rebels Beat the Government–Saving Privacy in the Digital Age：Steven Levy 所著，大部分內(nèi)容都是從這本書了解到的。書里從 Whitfield Diffie 的八卦（是真的八卦，和他老婆的相遇之類）說起，一直說到非?，F(xiàn)實的 NSA 涉入等情節(jié)，寫得很詳細很有趣。中譯本譯作《隱私的終結(jié)》，但翻譯水平非常有限，比如把愛倫坡譯成艾倫坡和阿蘭坡兩種不同譯法，把 cutting-edge 翻譯成邊緣，或者干脆把算法水平有待提高翻譯成精通算法什么的…

• The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography：中譯本《密碼故事》，除了密碼從古至今的演變，書里還單獨對 Ellis 和 Cocks 等人的工作做了詳細的講述。我還沒看完這本書，但感覺會很有意思。

• 關(guān)于 Adleman 的更多八卦可以看這篇采訪，總覺得他的氣場和其余兩人很不搭，各種變卦和無所謂。啊對了，Adleman 也是將計算機病毒命名為 Computer virus 的人。