來源 | WIRED
編譯 | Guoxi
責編 | Aholiab
出品 | 區塊鏈大本營（blockchain_camp）
1994 年 4 月，作為麻省理工學院電腦科學實驗室成立 35 週年的慶祝活動，時任實驗室主任 Michael Dertouzos 設計了一個“創新成果時間膠囊“。
他將一系列計算機領軍人物的創新成果收錄其中，準備在35年後再取出來，作為實驗室成立 70 週年的獻禮工程。
不過問題來了，如何能保證剛好在 35 年之後取出來呢？這可難不倒麻省理工學院這些頂級的科學家，他們為時間膠囊設計了一把“密碼鎖“，也就是一道密碼學難題。
同時，他們還非常嚴謹地考慮了未來計算機算力的提升速度，特意加大難度，使得密碼學難題至少需要 35 年時間來破解。
業界一眾密碼學大牛也都十分清楚，麻省理工學院給出的密碼學難題肯定不是鬧著玩的，所以就沒在上面浪費時間。於是乎，這道密碼學難題足足塵封了 20 年之久。
今年 4 月，一名程式設計師成功地破解了麻省理工學院的密碼學難題，更厲害的是，這名程式設計師並不是用了 20 年，他在2015年才偶然發現了這個密碼學難題，也就是說他破解只用了 3 年的時間。
他是怎麼做到的？他又有著什麼樣的訣竅？讓我們一起走進這名程式設計師的傳奇。

RSA演算法發明人設計了一個塵封35年的密碼學難題
故事的主人公是 Bernard Fabrot，一名自學成才的比利時程式設計師。在講他如何解迷之前，我們先來從頭看看故事的起因。
1999 年的 4 月初，著名建築師 Frank Gehry 收到了一個時間膠囊（time capsule ），時間膠囊就是即將現代發明的有代表性意義的物品裝入容器內，密封后深埋地下，在未來的某一時刻開啟。按照指示，這個時間膠囊要放入他主持修建的麻省理工學院「電腦科學和人工智慧實驗室」（簡稱：CSAIL ）的大樓中。
這個時間膠囊可以說是一個早期計算機歷史的博物館，它裡面包含由微軟創始人比爾·蓋茨和圖靈獎得主、全球資訊網之父Tim Berners-Lee爵士等計算機領軍人物捐獻的 50 件計算機歷史上偉大的藏品。
這其中，很可能包括1975年，微軟為麻省理工學院開發的Altair BASIC編輯器，也是微軟有史以來第一個產品（比爾·蓋茨和保羅·艾倫當時編寫的BASIC直譯器就是後來的Microsoft Basic，也是MS-DOS的基礎，後來演變成了現今的Visual Basic）。
顧名思義，時間膠囊需要有了時間的沉澱才會變得更有意義。於是這個與電腦科學密切相關的時間膠囊採取了電腦科學的方法，設計了一個密碼學難題，只有破解了這個難題才能開啟時間膠囊，這個密碼學難題只能透過一次次按順序的計算解開。
考慮到計算機算力的發展速度，解開這個難題至少需要計算 35 年。
這個別出心裁的設計出自 Ron Rivest 之手，對於 Rivest 這個人你可能不太熟悉，但說到大名鼎鼎的非對稱加密的 RSA 演算法你可能會覺得有點熟悉。沒錯，Rivest 就是 RSA 演算法三個發明人中的“ R ”（RSA 演算法由三個發明人姓氏的開頭字母命名）。
Ronald Linn Rivest，美國密碼學家；RSA加密演算法發明者之一
同時，Rivest 還寫了一本書，就是被稱為程式設計師必修課的《演算法導論》。RSA 演算法可以說是有史以來最重要的密碼學演算法之一，今天加密貨幣的輝煌也離不開其底層 RSA 加密演算法的支援。
雖然 Rivest 說這個密碼學難題並不複雜，但實際上，計算這個難題的答案至少需要花費 35 年的時間。甚至在今天故事的主人公Fabrot把難題的答案發給麻省理工學院的時候，相關負責人都已經忘了這個問題的存在。
在今年 4 月 15 日，也就是 Rivest 提出這一密碼學難題後的 20 年，自學成才的比利時程式設計師 Bernard Fabrot 解決了這個難題。
按照這個密碼學難題官方說明的指示，Fabrot 準備將解決方案傳送給麻省理工學院電腦科學實驗室主任，但他驚訝地發現這個實驗室已經不復存在，早在 2003 年，這個實驗室就與麻省理工學院人工智慧實驗室合併，成立了現在的麻省理工學院電腦科學和人工智慧實驗室。
更令人震驚的是，這個新成立的實驗室也早已忘了這個密碼學難題的存在，Fabrot 說，現任麻省理工學院電腦科學和人工智慧實驗室主任 Daniela Rus 在收到解決方案時一頭霧水，因為她根本不知道這個密碼學難題是怎麼回事。
「簡單」的麻省理工學院密碼學難題
那麼，Rivest設 的這個密碼學難題到底是什麼呢？
簡單來說，這個難題就是要找到執行近 80 萬億次平方操作的結果。比如說，如果你從 2 開始計算，平方後就得到了 4 ，緊接著 4 再進行平方計算就得到了 16 ，這個過程需要重複 80 萬億次。
麻省理工學院密碼學難題的形式十分簡單
當然了，每次平方計算後還需要對一個很大的數字 n 求模值，也就是求除以 n 之後的餘數，最後算得的結果與難題中給定的一個數字進行數學計算，你就會得到一個新的數字，也就是這個密碼學難題的答案。
雖然說當前密碼學難題已經被破解，但出題人 Rivest 和破題人 Fabrot 都拒絕透露確切的答案。他們準備在 5 月 15 日舉行一個開啟時間膠囊的儀式，屆時將會在儀式上公佈答案。
你可能覺得這看起來也不難嘛，用更多的計算機加大算力不就可以了麼？事實上沒那麼簡單。這個密碼學難題的關鍵在於它需要順序操作，也就是說你需要在前一步計算結果的基礎上進行這一步的平方計算，這意味著你只能一步步計算來得到結果，而無法透過當下常用的並行化計算來更快地得到答案。
Ron Rivest在當年的說明中，給出的解題思路示例
因此使用更多的計算機或是超級計算機都無濟於事。考慮到「摩爾定律」（英特爾創始人戈登·摩爾提出的：微處理器的效能每隔 18 個月提升一倍），以及在 1999 年進行平方操作所需要的時間，Rivest 估計僅靠計算得出密碼學難題的答案至少需要 35 年。
而作為一名獨立開發者，Fabrot是在 2015 年才偶然發現了這個密碼學難題。Rivest 最初使用 Java 語言開發了破解難題的程式碼。
後來，他便意識到如果藉助 GNU 多精度運算程式庫（GNU Multiple Precision Arithmetic Library）這個用 C 語言編寫的精確運算工具可以加快破解難題的速度。
所以 Fabrot 立即著手去做，他在家裡的臺式計算機上專門分出一個 CPU 核心用於執行平方計算，在此期間除了他去度假或是家裡停電，Fabrot 的電腦一直在全天候執行。
“在這些年裡，除了非常親密的幾個朋友之外，我沒有向任何人透露過我正在解決這個密碼學難題，” Fabrot 說，“我相信自己可以做到，同時我也知道如果我告訴其他人，他們可能會使用更強大的 CPU 來超越我。”
三年半之後， Fabrot 終於完成了大約 80 萬億的平方計算，得到了密碼學難題的結果。
解題者不止Fabrot一個
Fabrot 很幸運，雖然他不知道，但此時一群電腦科學家和密碼學專家也正在開展一個名為 Cryptophage （直譯為：加密噬菌體）的專案，該專案主攻的目標是硬體，目標是使用專門的硬體來解決麻省理工學院提出的密碼學難題，而且在 Fabrot 得到結果時， Cryptophage 團隊的解決方案也在出爐的邊緣。
在前英特爾工程師 Simon Peffers 的帶領下，Cryptophage 團隊當時正在研究將可驗證的延遲函式作為以太坊等區塊鏈安全機制的可能性。
可驗證的延遲函式是對 Rivest 早期延時加密工作的進一步拓展，它們的解決方案都只能透過順序操作得出。 Peffers 說，在研究的過程中， Cryptophage 團隊遇到了 Rivest 提出的密碼學難題，這個難題似乎是為他們的研究量身定製的“考試”。
3 月中旬， Cryptophage 團隊開始研究由土耳其薩班哲大學研究員 Erdinc Ozturk 設計的演算法。這個演算法為減少平方操作之間的延遲作了專門的最佳化，並且該演算法可以在現場可程式設計門陣列（FPGA，Field－Programmable Gate Array）上執行。
現場可程式設計門陣列這種多用途晶片可以為執行特定演算法做出最佳化，因而它比通用的 CPU 更加高效。透過使用 Ozturk 的演算法最佳化，這個密碼學難題在現場可程式設計門陣列上的破解速度比在沒有軟體層面最佳化的高階商用 CPU 上快了約 10 倍。
根據現場可程式設計門陣列的計算能力，Cryptophage 團隊推算出他們將在 5 月 10 日晚上（即他們開始計算的兩個月後）得出麻省理工學院密碼學難題的正確答案。
然而，當他們聯絡麻省理工學院準備分享這份難題即將被攻克的喜悅時，迎接他們的是一盆冷水，出題人 Rivest 告訴他們 Fabrot 已經捷足先登了。
“在這二十年裡沒有任何人來找過我們，直到這兩個人幾乎在同一天告訴我們：“我們已經解決了你的密碼學難題，”出題人 Rivest 說，“這是一個令人驚訝的巧合。”
同時，Rivest 也很快承認自己高估了密碼學難題的難度。Rivest 表示預測很長一段時間內的技術進步是一件很困難的事，在當時他並沒有預料到現場可程式設計門陣列取得的計算能力突破，而且在那時晶片並不像現在這麼複雜，用途也沒有這麼廣泛。
雖然 Cryptophage 團隊並不是第一個解決密碼學難題的人，但 Peffers 表示他們仍將參加 5 月 15 日開啟時間膠囊的儀式。
時間膠囊中都有些什麼只有它的設計師 Michael Dertouzos 知道，不過目前可以確定其中包括圖靈獎得主、全球資訊網之父 Tim Berners-Lee 爵士，乙太網之父 Bob Metcalfe，微軟創始人兼微軟首款產品 Altair BASIC 的開發者比爾·蓋茨等幾位計算機先驅人物捐贈的創新成果。
不過 Fabrot 表示，他對時間膠囊最大的期待，就是裡面包含的原始版本的世界上最早的電腦遊戲 Zork 。
圖片來源：維基百科
麻省理工學院密碼學難題的官方說明：
https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
