你有沒有想過，在設置密碼時，你輸入「2333！@#￥」之後，到底網站是怎麼生成密碼的呢？
目前廣泛使用的加密算法是怎樣的產生的？它何以能保護世界範圍內的在線金融活動？黑客又是怎樣破譯密碼的？其實，這些都源於一個數學問題。
（圖片來源：veer圖庫）
網絡加密的誕生
人類自從能夠交流以來，就需要媒介來傳遞秘密的消息。為了防止重要的信息落入不該知道的人手中，我們的祖先發明了相當多的有趣的加密方式。其中一種最早的加密消息的手段是2500多年前由斯巴達軍隊發明的。消息的發送方和接收方分別持有一個尺寸相同的圓柱體，稱為斯巴達密碼棒（scytale）。為了編碼信息，發送方首先將一條狹窄的羊皮紙沿水平方向包在密碼棒上，這樣它就一圈圈地纏繞起來。然後順著密碼棒的垂直方向豎著寫下信息。展開羊皮紙之後，上面的文字看起來毫無意義。只有將它重新纏繞在尺寸相同的密碼棒上時，信息才會重現。
密碼棒（圖片來源：維基百科）
從那以後，一代代人不斷創造出更多的複雜加密方法。其中最複雜的一種機器編碼裝置是德國人發明的恩尼格瑪，在二戰中被德軍所利用。
恩尼格瑪密碼機（圖片來源：維基百科）
在1977年之前，所有想要發送加密消息的人都面臨著一個固有的問題。發送方和接收方必須提前見面來決定使用哪種密碼。例如，斯巴達的將軍們需要對密碼棒的尺寸達成一致。即使是批量生產的恩尼格瑪，柏林方面依然需要派出特工，給潛水艇艦長和坦克指揮官傳送密碼本，詳細說明每天加密所需的機器設置。當然，如果敵人得到了密碼本，那他們就玩兒完了。
想像一下網際網路電子商務使用這種密碼系統的後勤狀況。在安全發送銀行帳戶信息之前，我們必須接收來自購物網站的安全信件，信中會告訴我們如何加密信息。考慮到龐大的網絡信息流量，很可能會有大量的安全信件被攔截。一種適用於快速的全球通信時代的密碼系統亟需開發。就像布萊切利園的數學家在二戰時破解了恩尼格瑪一樣，現在也是數學家發明了一代又一代的密碼，並將其從諜戰小說帶到了地球村。這些數學密碼為我們所知的公鑰密碼系統的誕生奠定了基礎。
（圖片來源：veer圖庫）
其實加密和解密就像鎖門和開門一樣。對於傳統的門，鎖門和開門用的是同一把鑰匙。對於恩尼格瑪，用於加密的設置也可以用於解密。這個設置——稱為密鑰——一定要保密。接收者和發送者距離越遠，後勤運送加密和解密的密鑰就越困難。設想一個間諜頭目想要安全地接收不同的特工發過來的加密消息，但是不希望這些特工看到彼此的消息。因此，不同的密鑰需要分別發給不同的特工。現在把特工換成幾百萬名饑渴的購物網站用戶。這種規模的操作雖說並非完全不可能，但對後勤來說簡直是噩夢。首先，訪問網站的用戶無法立即下單，因為它們必須等待安全密鑰傳過來。全球資訊網（WorldWideWeb）真的變成了「萬未網」（WorldWideWait）。
公鑰密碼系統則像有兩把不同鑰匙的門：鑰匙A用來鎖門，鑰匙B用來開門。你會忽然發現，對於鑰匙A來說，沒有必要再添加什麼安全措施。其他人擁有這把鑰匙並不會危及安全。現在把這個門想像成公司網站的安全部門的入口。公司可以自由地向任何訪問者分發密鑰A，使得訪問者可以給網站發送加密消息，比如信用卡號碼。儘管每個人都可以用這個密鑰來加密數據，也就是把秘密鎖在門後，但沒人可以讀取其他人加密後的消息。實際上，一旦數據被加密，用戶就無法讀取，即使是自己發送的消息也不行。只有幕後運營這個網站的公司擁有密鑰B，而只有擁有密鑰B才能解密並讀取那些信用卡號碼。
公開密鑰加密（圖片來源：維基百科）
公鑰密碼系統的首次公開提出是在1976年的一篇影響深遠的論文中，作者是史丹福大學的兩位數學家，惠特菲爾德·迪菲和馬丁·赫爾曼。兩人在密碼世界中掀起了一種反主流文化的潮流，欲挑戰政府機構對密碼系統的壟斷。尤其是迪菲，一個典型的反建制派，屬於20世紀60年代的那種叛逆長發青年。兩人都熱衷於讓密碼學面向公眾，並認為它不該僅僅是由政府關起門來討論的話題，而是應該用於造福個人。但後來人們才知道，一些政府安全機構早就聯合推進了這一密碼系統，只是沒有公開發表在期刊上，而是被列為最高機密，並被束之高閣。
左：惠特菲爾德·迪菲 右：馬丁·愛德華·赫爾曼（圖片來源：維基百科）
史丹福大學的一篇題為《密碼學新方向》的論文，預示著加密技術和電子安全技術的新時代的到來。配有兩個密鑰的公鑰密碼系統，理論上聽起來十分強大，但是能否將理論用於實踐並創造有效的密碼呢？經過幾年的嘗試，一些密碼學家開始懷疑這種加密技術的可行性。他們擔心這種學術化的密碼系統無法應對真實世界的間諜活動。
RSA：MIT三劍客
迪菲和赫爾曼的論文激發了眾多人的靈感，其中就有麻省理工學院的羅納德·L.李維斯特。和叛逆的迪菲和赫爾曼不同，李維斯特是個傳統的人。他沉默寡言，講話溫和，行為舉止也很慎重。當他讀到《密碼學新方向》這篇論文的時候，他的職業目標還是成為學術機構的一員。他的夢想是教授職位和定理，而不是密碼和間諜。那時他還不知道，他所讀的這篇論文將帶他走上另一條路：創造出史上最強大、商業上也最為成功的密碼系統之一。
羅納德·李維斯特（圖片來源：維基百科）
在史丹福大學和巴黎工作了一陣子之後，李維斯特於1974年加入MIT的計算機科學系。和圖靈一樣，他對抽象理論和具體機器的相互作用十分感興趣。在史丹福大學他花了一陣子時間來製作智慧機器人，但是他的思想卻轉向了計算機科學更加理論化的層面。
在圖靈的時代，受到希爾伯特的第二和第十問題的啟發，計算機所面對的主要問題是，理論上是否存在這樣的一種程序，它能夠解決特定類型的問題。正如圖靈所展示的那樣，沒有程序可以決定某個數學事實能否被證明。到了20世紀70年代，另一個理論問題在計算機科學界掀起了一陣風潮。假設的確存在解決特定數學問題的程序，那麼是否有可能分析該程序解決問題的速度？如果要實現該程序的話，那麼這個問題顯然很重要。這個問題需要很強的理論分析能力，卻又植根於現實世界。
這種理論與實際的結合對李維斯特而言簡直是完美的挑戰。他離開了史丹福大學的機器人項目，加入了MIT，轉而研究計算複雜度這一新興學科。
李維斯特回憶道：「一天，有個研究生帶著這篇論文來找我，對我說：『您或許會對這個感興趣。』」那正是迪菲和赫爾曼的論文，他立刻被吸引了。「他還說：『這篇論文在宏觀上討論了密碼學的定義和發展。要是您也可以給出出主意就好了。』」文中的挑戰囊括了李維斯特所有的興趣：計算、邏輯學和數學。其中有個問題顯然是出於對現實世界的考慮，但也直接關聯到和李維斯特所關心的一個理論問題。「在密碼學中，你所關心的是如何區分容易的問題和困難的問題，」他解釋道，「而這正是計算機科學所研究的東西。」如果一個密碼很難破解，那麼它一定是基於某個很難計算求解的數學問題。
李維斯特開始嘗試構建公鑰密碼系統，他從數學寶庫中挑選所需的難題，這些問題都是計算機需要花很長時間才能破解的。他也需要有人來給他的工作提供反饋意見。那時的MIT已經開始打破傳統大學的桎梏，加強各院系之間的互動和溝通，為的是鼓勵跨學科研究。李維斯特雖然在計算機科學系工作，但他和數學系的同事在同一樓層。在他附近的辦公室就坐著兩位數學家，倫納德·阿德曼和阿迪·薩莫爾。
阿德曼比李維斯特更善於交際，但仍然符合學者的經典形象，對那些看似不切實際的事物有著瘋狂而奇妙的想法。阿德曼回想起有一天早晨，當他來到李維斯特的辦公室時的情景：「羅就坐在那兒，手裡拿著一份稿子。他對我說：『你看過這篇斯坦福的論文嗎，是關於加密、密碼、加擾之類的……』我回答：『好吧，這挺好的，羅，但我還有重要的事情要談，我真的不關心這些。』但是羅對此很興趣。」阿德曼關心的是高斯和歐拉的抽象世界。證明費馬大定理對他來說才是重要的事情，而不是投身於密碼學這種流行學科的研究。
倫納德·阿德曼（圖片來源：維基百科）
李維斯特在附近的辦公室裡發現了更好的聆聽者——阿迪·薩莫爾，來MIT訪學的以色列數學家。薩莫爾就和李維斯特一起尋找可用來實現迪菲和赫爾曼的設想的方法。儘管阿德曼並不怎麼感興趣，他還是難以無視李維斯特和薩莫爾的研究熱情：「每次我走進辦公室裡，他們都在討論這個。他們嘗試的多數系統都失敗了。既然我也在那裡，我就索性加入了討論，看看他們的提議靠不靠譜。」
阿迪·薩莫爾（圖片來源：維基百科）
隨著他們對「困難」的數學問題的研究範圍不斷拓展，他們的密碼系統已初具雛形，並開始用到了越來越多的數論知識。這正是阿德曼的本行：「因為那是我的專業領域，所以分析他們的系統時，我可以施展拳腳，而且大部分時間也用不著他們。」當李維斯特和薩莫爾提出一個看起來非常安全的系統時，他以為自己輸定了。但是藉助自己的數論知識，只需工作一宿就足以破解他們最新的密碼：「這種情況周而復始。在去滑雪的路上，我們討論的是這個……甚至我們坐著纜車，快要到達山頂的時候，我們還在討論這個……」
轉折點發生在一天晚上，三人受邀去往研究生院，參加逾越節第一夜的晚餐。阿德曼沒喝酒，但他記得李維斯特喝了一瓶逾越節家宴的酒。阿德曼半夜才回家。他到家不久後，電話鈴就響了。打來電話的是李維斯特：「我想到了另一個點子……」阿德曼仔細地聽著，說：「羅，這次你成功了！我覺得你這個想法是對的。」關於因數分解的難題，他們已經思考了一段時間。對尋找構造出某個數的素因數而言，目前尚未出現任何巧妙的編程方法。這個問題太合適了。在逾越節晚宴酒的影響下，李維斯特已經看到了如何將這個問題通過編程融入到他的新密碼中。李維斯特回憶道：「當時的第一感覺真是太棒了。但我們知道，起初感覺良好並不意味著後面的路就會好走。所以我們把問題擱到了第二天早晨。」
次日上午，阿德曼來MIT上班的時候，李維斯特拿著一份手稿跟他打招呼，稿子的頂部寫著阿德曼、李維斯特和薩莫爾的名字。阿德曼翻閱著手稿，回想起李維斯特昨天晚上打電話告訴他的事情。「於是我對羅說，『把我的名字去掉，這是你完成的』，之後我們為了要不要留下我的名字差點打起來。」最後，阿德曼同意再考慮考慮。當時阿德曼覺得署名與否並不重要，因為這篇文章有可能是他發表的文章中閱讀量最低的。不過他又想到，為了這個早期的密碼系統，他沒日沒夜地研究，終於讓它有了較為成熟的方案，也讓這篇論文避免了因生成不安全的密碼而在發表後遭人唾棄的危險。「於是我回去找羅，對他說：『讓我來當第三作者吧。』這就是RSA加密算法的名稱的由來。」
李維斯特覺得他們最好研究一下因數分解問題到底有多難：「研究因數分解在那時屬於一種高深的藝術，相關文獻也很少。我們所提出的算法究竟要花多少時間才能完成，我們也不好說。」不過恰好馬丁·加德納對這個問題有所了解，他是世界上最受歡迎的數學科普作家之一。加德納被李維斯特的想法迷住了，正好他在《科學美國人》雜誌上有一個專欄，他便問李維斯特是否願意由他來寫一篇專欄文章，介紹這一思想。
加德納的文章發表後，讀者的反響讓阿德曼最終確信，他們真的搞了件大事情：
那年夏天，我在伯克利的某間書店裡面。有一位顧客在和櫃檯後面的人談論著什麼，然後我聽到他說：「你有沒有看過《科學美國人》裡的那篇關於密碼的文章？」我就走了過去，對他說：「嗨，我就是文中提到的研究者之一。」他就回過頭來，對我說：「我可以得到你的親筆籤名嗎？」我們可曾被人要過親筆籤名？從未有過。喔，當時感覺……也許我們的出頭之日就要來了！
加德納在文中還提到，只要提供貼好郵票並寫上收信地址的信封，這三位數學家就會寄出論文的預印本。「等我回到MIT的時候，我們已經收到了數以千計的——毫不誇張，真是數以千計的——來自世界各地的信封，其中還有來自保加利亞國家安全局的……」
人們開始告訴他們三個，他們要發財了。即使是在20世紀70年代，電子商務還很難想像的時候，人們也能看出他們的想法擁有巨大的潛能。阿德曼覺得用不了幾個月就會財源滾滾，於是直接出門買了輛紅色跑車慶祝一下。看來邦別裡並不是唯一一位用跑車來獎勵自己在數學上的成就的人。
阿德曼的跑車最後還是用他在MIT的工資分期付清的。安全機構和商業機構著實花了一段時間，才真正領會了RSA加密算法在密碼安全方面的威力。當阿德曼一邊開著跑車，一邊還想著費馬大定理時，李維斯特已經開始著手推動他們的想法落地：
我們認為我們的方案或許還有一些商業價值。我們去MIT的專利辦公室碰了碰運氣，看看有沒有公司願意將其投入市場。但那時是20世紀80年代早期，我們幾乎沒有市場。那個時代對此感興趣的人太少了。網際網路尚未興起，個人計算機也尚未普及。
對此最感興趣的當然是安全機構。「安全機構開始密切關注這一技術的進展，」李維斯特說，「但他們仔細研究後，認為我們的研究計劃不會進展太快。」在情報機構緊閉的大門背後，似乎有人做著同樣的事情。不過安全機構也不是很確定，能否將特工人員的生命安全託付給幾位研究密碼的數學家。根據來自德國聯邦信息安全局的安斯加爾·霍伊澤爾的回憶，在20世紀80年代，他們曾考慮在該領域使用RSA加密算法。他們問了這幾位數學家一個問題：西方國家的數學家在數論上是否強於俄羅斯數學家。當得到否定的回答時，這個想法就被擱置了。但是在接下來的十年中，RSA加密算法證明了自己的價值：它不僅能保護特工人員的生命安全，還能在商業領域大顯身手。
一個密碼學的紙牌戲法
如今網絡上進行的大部分交易都是由RSA加密算法保護的。值得注意的是這種公鑰密碼系統背後的數學計算，令人想起高斯的時鐘計算器，以及費馬（阿德曼的偶像）所證明的定理，即費馬小定理。
皮埃爾·德·費馬（圖片來源：維基百科）
高斯計算器上的加法運算和我們所熟悉的12小時錶盤的工作原理一致。我們知道，如果現在是9點，那麼再過4小時就是1點。這就是時鐘計算器上的加法運算：對數字進行求和，然後除以12。以下就是高斯200多年前所寫的式子：
4+9=1（以12為模）
在高斯的時鐘計算器上，乘法和冪運算的原理也一樣：先用傳統計算器來計算，再將結果除以12，最後取餘數。
高斯還意識到，這種計算器不必拘泥於傳統的12小時錶盤。甚至在高斯明確提出時鐘計算器的概念之前，費馬就已經發現了一個基本規律，即所謂的費馬小定理。假設有一個錶盤時間為素數的時鐘計算器，該素數用p表示。如果在該計算器上計算某個數字的p次冪的話，那麼結果總是會出現最初的數字。例如，使用5小時錶盤的時鐘計算器來計算2的5次冪。傳統計算器的計算結果是32，而在5小時的錶盤上，時針會指向2點。費馬發現，每次將計算結果乘以2時，時針指向的鐘點是有規律地變化的。5次操作之後，時針就指向最初的鐘點，並開始重複前5次的規律，如下表所示。
如果使用13小時錶盤的時鐘計算器來進行3的13次冪運算，即31，32，…，313，就會得到：
3，9，1，3，9，1，3，9，1，3，9，1，3
這時候指針並沒有遍及錶盤上所有的數字，但其指向的鐘點還是有規律地重複的。也就是說，如果對3進行13次冪運算，那麼第一次和最後一次運算的結果都是3。無論費馬選擇了什麼樣的p值，這種神奇的現象都一樣會發生。採用高斯的時鐘運算或模運算的記法，可以將費馬的這一發現描述為，在p小時錶盤上，對任意素數p及錶盤的任意鐘點x，都有：
xp=x（以p為模）
費馬的發現在某種程度上令數學家們熱血沸騰。素數居然如此神奇，但背後的原因是什麼呢？費馬並不滿足於實驗觀察，他希望從理論上證明，無論錶盤時間選擇什麼素數，這一結論都能站得住腳。
費馬在1640年寫給他的朋友伯納德·弗萊尼科·德貝西的一封信中描述了這一發現。他好歹沒有像對待費馬大定理那樣，只在某本書的空白處寫了幾句話，聲稱「我確信已發現了一種美妙的證法，可惜這裡空白的地方太小，寫不下」。雖然他承諾將證明寄給弗萊尼科，但這一證明的文本至今下落不明。又過了一個世紀，相關的討論才重新進入人們的視野。1736年，歐拉發現了費馬的素數錶盤指針在進行素數冪次運算之後還能指向起始鐘點的原因。歐拉還設法將費馬的發現推廣到N小時錶盤上，其中N=p×q，p和q都是素數。歐拉發現，在這種錶盤上，時針指向的鐘點在(p-1)×(q-1)+1步操作之後開始有規律地重複。
由費馬發現並由歐拉推廣的神奇的素數時鐘運算，在逾越節晚宴結束後的深夜闖入李維斯特的腦海。李維斯特想到，可以將費馬小定理作為設計新密碼的關鍵機制，用於信用卡號碼的加密和解密。
加密信用卡號碼就像開始演示某種紙牌戲法，但這不是普通的紙牌：如果要記錄這摞紙牌共有多少張，那麼這個數字可以達上百位。用戶的信用卡號碼就是這些紙牌中的一張。用戶將信用卡號碼的紙牌放在這摞紙牌的頂部，然後由網站來洗牌，這樣用戶的紙牌似乎就「消失」了。想要從這摞打亂的紙牌中找回這張牌，無異於大海撈針，這對任何黑客而言都是不可能的任務。然而網站知道這個戲法背後的竅門。多虧有了費馬小定理，網站只需要再洗一次牌，就能讓信用卡號碼那張牌在紙牌的頂端重現。第二次洗牌就是只有網站的所有者——也就是公司——才能掌握的密鑰。
（圖片來源：veer圖庫）
李維斯特設計這一加密技巧所用到的數學計算相當簡單。洗牌也是通過數學計算來完成的。用戶在網站上下單之後，計算機就會獲取用戶的信用卡號碼並進行計算。計算很容易執行，但是如果不知道密鑰的話，那就幾乎不可能破解。這是因為計算使用的並不是傳統的計算器，而是高斯的時鐘計算器。
網際網路公司會告訴客戶，在他們下單之後，應該用多少個鐘點的錶盤進行時鐘計算。這取決於素數p和q的大小，它們分別有約60位數。之後公司將兩個數字相乘，得到第三個數字，即N=p×q。這樣一來，錶盤上的鐘點數會特別大，可達120位。每個客戶始終用相同的時鐘計算器來加密信用卡號碼。密碼的安全性意味著公司可以一連幾個月使用相同的錶盤而無須更換。
為網站的時鐘計算器選擇錶盤上的鐘點數，這就是公鑰選擇的第一步。儘管數字N是公開的，兩個素數p和q卻依然保密。p和q就是破解已經加密的信用卡號碼的兩個要素。
下一步，每個客戶都會收到數字E，它被稱為加密數字。每個人的E都一樣，而且它和N一樣是公開的。如果要加密信用卡號碼C的話，那麼就在網站的時鐘計算器上將其進行E次冪的運算。（把E看成魔術師洗牌的次數，洗牌之後就可以隱藏你選擇的那張牌了。）借用高斯的表述，可以寫作CE（以N為模）。
為什麼這個加密算法如此安全呢？畢竟任何黑客都可以在網絡空間裡看到加密後的信用卡號碼，而且他們還可以查詢加密使用的公鑰，公鑰包含了N小時錶盤的時鐘計算器以及信用卡號碼的E次冪運算。要破解這個密碼的話，黑客要做的就是找到一個數字，該數字在N小時錶盤的時鐘計算器上經過E次冪運算，就能得到加密的信用卡號碼。但是找到這個數字相當困難。因為冪運算是在時鐘計算器而非傳統計算器上進行的，所以破解起來格外困難。使用傳統計算器的話，計算結果會和信用卡號碼相乘的次數等比例增長，但使用時鐘計算器就不會這樣。這樣一來，黑客就很難知道紙牌的初始位置，因為計算結果的數值大小和你從哪裡開始沒什麼關係。於是，經過E次洗牌之後，黑客對於牌面幾乎一無所知。
（圖片來源：veer圖庫）
如果黑客對時鐘計算器發起暴力枚舉攻擊呢？這也不可能成功。密碼學家現在所利用的時鐘計算器的N，也就是錶盤上的鐘點數，已經有100多位了。也就是說，錶盤上的鐘點數比宇宙中的原子數還多。（相比之下，加密數字E通常就小得多了。）但是，如果這個問題不可能解決的話，那麼網際網路公司究竟是如何找回客戶的信用卡號碼的呢？
李維斯特知道，費馬小定理能保證一個神奇的解碼數字D的存在。網際網路公司對加密的信用卡號碼進行D次冪運算之後，最初的信用卡號碼就會出現。魔術師在紙牌戲法中也使用了相同的技巧。一定次數的洗牌之後，紙牌順序看似完全被打亂，但是魔術師知道，再洗幾次牌就可以恢復原來的順序。例如完美洗牌，一摞牌對半均分，然後讓兩側的每張牌交錯重疊，這樣洗8次牌後，就可恢復原來的紙牌順序。當然，魔術師的藝術是可以完成連續8次的完美洗牌。費馬也發現了類似的時鐘算法，即讓52張紙牌恢復原來順序的完美洗牌次數。而費馬的戲法正是李維斯特用來破解RSA加密算法的武器。
儘管經過網站多次洗牌之後，客戶信用卡號碼的那張牌已經難尋蹤跡，但網際網路公司知道，就像數學魔術師一樣，再經過D次洗牌，它就會出現在紙牌的頂部。但是只有知道秘密素數p和q才能知道D。李維斯特利用了歐拉所推廣的費馬小定理，其時鐘計算器使用兩個素數而不是一個。歐拉已經證明，在這樣的時鐘計算器上，經過(p-1)×(q-1)+1次洗牌後，這摞紙牌就會恢復原先的順序。因此，想要知道錶盤鐘點數為N=p×q的時鐘計算器的重複周期到底有多長，唯一的辦法就是知道p和q。因此，掌握這兩個素數就成了破解RSA加密算法的關鍵。令「消失」的信用卡號碼重現的洗牌次數只有網際網路公司知道，因此p和q也都是保密的。
儘管p和q是保密的，但它們的乘積N是公開的。因此，李維斯特的RSA加密算法的安全性是建立在對N進行因數分解的超高難度上的。黑客所面臨的挑戰和科爾教授在20世紀初所面對的問題是一樣的：找到N的兩個素因數。
來源：科學大院
編輯：GUOmazing