最近為(wei)了研究某個極(ji)其無聊的(de)問(wen)題，讀了一些(xie)公鑰加密的(de)歷史，意(yi)外(wai)地發現這段歷史竟然非(fei)常有趣(qu)。尤其是 RSA 算(suan)法的(de)誕生過程(cheng)，被很多(duo)書(shu)寫得非(fei)常勵志，看得人熱(re)血澎湃(pai)。果然比起算(suan)法本(ben)身，這些(xie)背(bei)后的(de)故事更能吸(xi)引(yin)我的(de)興趣(qu)。

RSA 算(suan)(suan)法具體是怎(zen)么回事，我(wo)就(jiu)不在這瞎說(shuo)了。簡介可以看 ，如果想(xiang)形(xing)象一(yi)點理解(jie)算(suan)(suan)法本身，有個(ge)不錯的(de)視頻，可以通(tong)過它了解(jie) RSA 的(de)基(ji)本思想(xiang)。我(wo)就(jiu)直(zhi)接從 RSA 這三個(ge)人(ren)說(shuo)起了。參(can)考的(de)書籍資料列在文(wen)末。

RSA 背后的三個小伙

RSA 是由(you)三(san)個(ge)提(ti)出者 、 和 的姓氏首(shou)字母組成(cheng)的。這三(san)個(ge)人風格迥異，組成(cheng)了一個(ge)技能(neng)互補的完美團隊(dui)。

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

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

Leonard Adleman，RSA 中的 A。自(zi)幼胸無(wu)大志(zhi)，從未想過做(zuo)什么(me)數學(xue)(xue)家。讀(du)大學(xue)(xue)時受各(ge)方(fang)面影響(xiang)，甚至包括的影響(xiang)，在專業(ye)(ye)選(xuan)擇(ze)上猶(you)豫不決(jue)，最(zui)終因(yin)(yin)為學(xue)(xue)數學(xue)(xue)會(hui)有(you)大量時間做(zuo)別(bie)的而選(xuan)擇(ze)就讀(du)數學(xue)(xue)系(xi)。畢(bi)(bi)業(ye)(ye)后在美國銀行做(zuo)程(cheng)序員，之(zhi)后想去學(xue)(xue)醫，被錄取了(le)卻又改變主意(yi)想研究物理，上了(le)幾堂課又覺得沒意(yi)思(si)。最(zui)后他怕掛科(ke)對找工(gong)作(zuo)有(you)影響(xiang)，跑(pao)去圖書館借(jie)了(le)本計(ji)(ji)算機(ji)科(ke)學(xue)(xue)的書，一直沒還(huan)，學(xue)(xue)校就會(hui)因(yin)(yin)此扣留成績(ji)單(dan)。輾轉幾次后，他最(zui)終選(xuan)擇(ze)讀(du)計(ji)(ji)算機(ji)科(ke)學(xue)(xue) PhD。畢(bi)(bi)業(ye)(ye)后同樣在 MIT 任教(jiao)。

這三人當時都非常年(nian)輕(qing)，二十多、三十出(chu)頭的樣子(zi)。他們的辦公(gong)室距(ju)離很近(jin)，可以(yi)經常串門。于是故(gu)事就(jiu)從一次 Adleman 的串門開始了。

42次的失敗

1976 年(nian)底(di)的(de)(de)(de)某天，Adleman 無(wu)意推開 Rivest 的(de)(de)(de)房(fang)門(men)。熱愛新(xin)技(ji)術(shu)的(de)(de)(de) Rivest 果不其然正(zheng)拿著份(fen)樓上的(de)(de)(de)   與(yu) 合作發表的(de)(de)(de)新(xin)論(lun)文(wen)研究。自(zi)認(ren)為對前沿理念無(wu)所(suo)(suo)不曉的(de)(de)(de) Rivest，沒(mei)料到這(zhe)篇(pian)文(wen)章(zhang)提出了一個前所(suo)(suo)未有的(de)(de)(de)思路，這(zhe)讓他興奮不已。正(zheng)琢磨(mo)著，Adleman 推門(men)進(jin)來了，Rivest 便忘我地向 Adleman 講解了這(zhe)篇(pian)論(lun)文(wen)中所(suo)(suo)述的(de)(de)(de)思想，在(zai) Adleman 聽起來大約是這(zhe)樣(yang)的(de)(de)(de)：

公鑰(yao)密碼 blah blah blah…不對稱密碼 blah blah blah…單向(xiang)函(han)數 blah blah blah…但(dan)是符合(he)條件的單向(xiang)函(han)數目前沒找到(dao)。我(wo)有(you)信心找到(dao)這樣(yang)的單向(xiang)函(han)數，你(ni)看(kan)你(ni)要不要和我(wo)一起試試？

這些顯然(ran)不(bu)足(zu)以讓(rang)早已下(xia)決心(xin)走(zou)純理論路(lu)線的(de)(de) Adleman 動(dong)心(xin)，對(dui)此他(ta)(ta)只是(shi)報以一個“禮貌的(de)(de)哈欠”。想(xiang)當(dang)初(chu)選擇讀計算機科學，除(chu)了方(fang)便找工作，Adleman 還深(shen)受(shou)馬丁(ding)加德納(na)專欄(lan)的(de)(de)影響。專欄(lan)中寫到的(de)(de)哥德爾定理讓(rang)他(ta)(ta)感到驚艷，深(shen)深(shen)體(ti)會到數學之美，如(ru)今只有(you)高斯之流方(fang)能入(ru)他(ta)(ta)的(de)(de)眼，眼下(xia) Rivest 滔滔不(bu)絕的(de)(de)什么加密(mi)解(jie)密(mi)，在(zai)他(ta)(ta)看(kan)來既不(bu)高級也(ye)不(bu)好玩。

好在 Rivest 拉到(dao)了(le)另一(yi)個同盟，也(ye)就是(shi)隔壁(bi)的(de) Shamir。Shamir 一(yi)聽說這(zhe)篇(pian)文章(zhang)就立刻意(yi)識到(dao)它的(de)價值(zhi)，二人一(yi)拍即合，開始了(le)他們晝(zhou)夜不(bu)休的(de)單向函(han)數尋找(zhao)之旅。因為(wei)兩人都頭腦靈(ling)活，很(hen)快(kuai)就想到(dao)了(le)一(yi)些(xie)方案。盡管(guan) Adleman 不(bu)情愿參與其中，他們還是(shi)會把結果(guo)拿給(gei) Adleman，Adleman 的(de)角色就是(shi)逐個擊破這(zhe)些(xie)方案，找(zhao)出各種漏洞(dong)，給(gei)那兩個頭腦發熱的(de)人潑點(dian)冷水，免(mian)得(de)他們走彎路。

三(san)人走火(huo)入(ru)魔一(yi)(yi)般，吃(chi)飯聊、喝酒聊，甚(shen)至去滑雪度假也不忘討(tao)論這(zhe)(zhe)(zhe)件事。Shamir 就在滑雪的(de)時(shi)候想(xiang)(xiang)到了一(yi)(yi)個(ge)絕妙的(de)點(dian)子，以(yi)至于把(ba)滑雪板都落在了身后。當(dang)他(ta)意識(shi)到這(zhe)(zhe)(zhe)一(yi)(yi)點(dian)回頭(tou)去取時(shi)，卻(que)又(you)不幸忘記了那(nei)個(ge)一(yi)(yi)閃而過的(de)點(dian)子。相對(dui)來說給他(ta)們(men)啟(qi)發的(de) Diffie 要幸運一(yi)(yi)些，他(ta)在下樓買可樂(le)的(de)時(shi)候同樣讓(rang)靈感(gan)溜(liu)(liu)走，好在上樓的(de)過程中他(ta)又(you)想(xiang)(xiang)起(qi)來了，這(zhe)(zhe)(zhe)個(ge)差點(dian)溜(liu)(liu)走的(de)靈感(gan)正是(shi) Rivest 那(nei)天(tian)手(shou)中所(suo)拿(na)論文(wen)的(de)核心(xin)思想(xiang)(xiang)，為 RSA 算法奠定(ding)了基礎。

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

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

算法的誕生與命名

1977 年 4 月，Rivest 和其余兩人(ren)參加(jia)了(le)(le)(le)猶太逾越(yue)節的(de)(de) Party，喝了(le)(le)(le)些酒(jiu)。到(dao)家后 Rivest 睡不著(zhu)，隨手翻(fan)了(le)(le)(le)翻(fan)數學(xue)書，隨后一(yi)個靈(ling)感逐漸(jian)清晰起(qi)來。他大氣不敢出一(yi)口(kou)，冷靜(jing)下來連夜整理(li)自(zi)己(ji)的(de)(de)思路，一(yi)氣呵成(cheng)寫就了(le)(le)(le)一(yi)篇論文。次(ci)日，Rivest 把論文拿給(gei) Adleman，做好再一(yi)次(ci)徒勞的(de)(de)心理(li)準備，但這(zhe)一(yi)次(ci) Adleman 認輸了(le)(le)(le)，認為這(zhe)個方案應該是可(ke)行的(de)(de)。

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

之后

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

最后(hou)，既然 RSA 是根據提出(chu)(chu)者命名的(de)(de)(de)(de)(de)，必然也(ye)(ye)逃不出(chu)(chu) 的(de)(de)(de)(de)(de)魔(mo)爪。的(de)(de)(de)(de)(de)確從時間上來說，RSA 這(zhe)三人并(bing)非最早提出(chu)(chu)這(zhe)個(ge)(ge)(ge)算(suan)法(fa)(fa)的(de)(de)(de)(de)(de)人。事實上早于(yu)這(zhe)三人四年(nian)(nian)時間，RSA 算(suan)法(fa)(fa)的(de)(de)(de)(de)(de)思想(xiang)(xiang)就被(bei)(bei)英(ying)國(guo)(guo)學者構造出(chu)(chu)來了。早在 1969 年(nian)(nian)，英(ying)國(guo)(guo)密碼(ma)學家 就想(xiang)(xiang)到了公(gong)鑰密碼(ma)的(de)(de)(de)(de)(de)概念(nian)，但同樣卡在尋找(zhao)單向函(han)數這(zhe)個(ge)(ge)(ge)問題上。1973 年(nian)(nian) 9 月，年(nian)(nian)僅 26 歲的(de)(de)(de)(de)(de)數學家 聽說這(zhe)個(ge)(ge)(ge)思想(xiang)(xiang)后(hou)，在完全不了解狀況的(de)(de)(de)(de)(de)心理狀態下花不到半小(xiao)時就找(zhao)到了 Rivest 他們苦思冥(ming)想(xiang)(xiang)的(de)(de)(de)(de)(de)方案。但是，他們效(xiao)力(li)于(yu)政(zheng)府，這(zhe)個(ge)(ge)(ge)絕妙的(de)(de)(de)(de)(de)想(xiang)(xiang)法(fa)(fa)立(li)刻被(bei)(bei)相(xiang)關(guan)機(ji)(ji)構封鎖，變(bian)為機(ji)(ji)密，誰也(ye)(ye)不能對外公(gong)開自己的(de)(de)(de)(de)(de)發現(xian)，于(yu)是他們眼(yan)睜(zheng)睜(zheng)地看(kan)著 Diffie 及 RSA 等人重現(xian)了他們當時的(de)(de)(de)(de)(de)研(yan)究并(bing)享有(you)盛譽。直(zhi)到 1997 年(nian)(nian)底，時隔(ge)二十(shi)余(yu)年(nian)(nian)，這(zhe)件事情才被(bei)(bei)公(gong)之于(yu)眾。遺憾的(de)(de)(de)(de)(de)是那時候 Ellis 已經過世一(yi)個(ge)(ge)(ge)月，直(zhi)至逝世都是一(yi)個(ge)(ge)(ge)無名英(ying)雄(xiong)。

參考資料

• ：Steven Levy 所著，大(da)部分(fen)內容(rong)都是從這本(ben)書了解到的(de)。書里(li)從 Whitfield Diffie 的(de)八卦（是真的(de)八卦，和(he)他老婆的(de)相遇(yu)之類）說起(qi)，一直說到非常(chang)現實的(de) NSA 涉入等情(qing)節，寫得很詳細很有(you)(you)趣。中譯本(ben)譯作《》，但(dan)翻(fan)譯水平非常(chang)有(you)(you)限(xian)，比如把(ba)愛倫(lun)坡譯成艾倫(lun)坡和(he)阿(a)蘭坡兩(liang)種不同譯法(fa)，把(ba) cutting-edge 翻(fan)譯成邊緣，或者干脆把(ba)算(suan)法(fa)水平有(you)(you)待提高翻(fan)譯成精(jing)通算(suan)法(fa)什么(me)的(de)…

• ：中譯本《》，除了密碼從(cong)古至今的演(yan)變(bian)，書里(li)還單獨對 Ellis 和(he) Cocks 等人的工(gong)作做(zuo)了詳細的講述。我還沒看完這本書，但感覺會很(hen)有意思。

• 關(guan)于 Adleman 的(de)更(geng)多(duo)八卦可以看，總覺(jue)得他的(de)氣場(chang)和其余兩人很(hen)不搭，各種變卦和無所謂(wei)。啊對了(le)，Adleman 也(ye)是將計算機(ji)病毒命名為 Computer virus 的(de)人。