近日，麻省理工學院（MIT）正式宣布一名自學成才的比利時程序員 Bernard Fabrot 成功破解了 RSA 算法發明者Ron Rivest20 年前提出的難題。據稱，這一行動對于當前流行的加密算法將產生深遠影響。

這個名為 LCS35 的難題是由加密算法界元老、RSA 暗碼系統發現者之一、MIT 教授 Ron Rivest 在 1999 年 4 月提出的。發起者們曾預測：以 1999 年的芯片計算速度作為起點并考慮到摩爾定律的話，即使用最快的增長模型，破解這一難題所需的算力也要在 35 年之后（也就是今天看來，最快 15 年之后）才能出現。

然而，Bernard Fabrot 這次只使用了一臺 CPU 為英特爾 Core i7 的家用臺式機就把問題解決了。

Bernard Fabrot

據 MIT 介紹，Fabrot 花費了三年半的時間解決這一難題，這一題目涉及到長度為 80 萬億次平方運算的起始數字，而且專門被設計為阻止破解者使用并行算法進行加速破解。

1999 年 4 月初，一個時間膠囊（time capsule）被送到著名建筑師 Frank Gehry 手中，并指示他將這個時間膠囊融入到建筑設計中，而這最終建成了麻省理工學院（MIT）的計算機科學暨人工智能實驗室（CSAIL）。這個時間膠囊本質上是一個早期計算機歷史博物館，其中收藏有微軟創始人比爾·蓋茨和萬維網之父蒂姆·伯納·李爵士捐贈的 50 件物品。

這個時間膠囊在 35 年內不會被公開—直到有人可以破解設計中的暗碼加密。該暗碼加密由 Ron Rivest 設計，其名字中的「R」代表了 RAS 暗碼系統中的「R」，該系統是有史以來最重要的加密協議之一。Ron Rivest 稱加密的設計并不復雜，但幾乎要花費 35 年的時間才能計算出答案。

4 月 15 日，在 Rivest 提出該難題的 20 年之后，一位自學成才的比利時程序員 Bernard Fabrot 解決了這一難題。該難題的原始指令是將解決方案送到計算機科學實驗室主任手中，但 Fabrot 意外地發現該實驗室不存在了（該實驗室在 2003 年與 MIT 的人工智能實驗室合并為 CSAIL）。更令 Fabrot 感到驚訝的是，當他告知 CSAIL 主任 Daniela Rus 自己的解決方案時，這位主任竟然不知道該難題的存在。

Rivest 的難題主要是為了得出運行平方運算近 80 萬億次所得到的最終數字。舉例而言，當你計算 2 的平方會得到 4，計算 4 的平方會得到 16，以此類推，運行平方運算 80 萬億次。之后，利用最終得到的數字運行一個數學運算，而該運算又將使用最終的平方運算數字以及難題提示給出的一個數字。這樣會分解出一個可以被編譯成簡短祝賀短語的新數字（Rivest 和 Fabrot 均拒絕透露精確短語，該短語會在 5 月 15 日的時間膠囊開啟儀式上公布）。

該難題的關鍵在于其要求序列運算，這意味著你無法通過并行計算而更快地得到答案。你需要在前一個平方運算結果的基礎上一步步地運行平方運算，所以使用更多計算機或采用超級計算機對結果無益。根據摩爾定律以及 1999 年運行平方運算需要花費的時間，Rivest 預測計算出該難題的答案應該需要 35 年左右。

Fabrot 是一位獨立開發者，他在 2015 年偶然發現了這個難題。盡管 Rivest 最初以 Java 語言發布了該難題的代碼，但 Fabrot 意識到如果自己使用 GNU Multiple Precision Arithmetic Library（一款用于「精確計算」的免費軟件），則能更快地解決這一難題。因此，Fabrot 專門在其家用臺式電腦中安裝一個 CPU 內核來全天候、無眠無休地運行平方運算。

Fabrot 說：「這些年，除了很親密的朋友，沒有人知道我在嘗試解決這個難題。我覺得自己有可能解決這個難題，如果我告訴別人，那他們可能用更強大的 CPU 來打敗我。」

三年半之后，Fabrot 最終完成了大約 80 萬億平方運算，并獲得了難題的解決方案。時間剛剛好！雖然 Fabrot 不知道，一組計算機科學家和密碼學專家正在研究一個名為 Cryptophage 的項目，該項目使用專門的硬件來解決 MIT 的難題。

前英特爾工程師 Simon Peffers 領導的 Cryptophage 小組在研究可驗證延遲函數作為區塊鏈（如以太坊）安全機制的可能性。可驗證延遲函數是 Rivest 早期關于時間延遲密碼學的現代成果，它們的解決方案只能通過序列運算獲取。Peffers 表示，研究期間 Cryptophage 小組遇到了 Rivest 的難題，他們認為該難題是驗證其研究的不錯方式。

3 月中旬，該團隊開始運行薩班吉大學研究人員 Erdinc Ozturk 設計的一個算法，該算法被優化用來減少平方運算之間的延遲。它是在 FPGA 芯片上實現的，這款芯片是多用途的，只運行特定算法，因此比通用 CPU 更高效。使用 Ozturk 的算法，FPGA 比運行非優化軟件的高端商用 CPU 快了約 10 倍。

基于芯片的計算效率，Cryptophage 小組估計其將在 5 月 10 日晚上得出 MIT 難題的正確解決方案，這離他們開始計算僅兩個月而已。當他們聯系 MIT 并聲稱即將有一個解決方案出爐時，Rivest 告訴他們 Fabrot 已經捷足先登，給出答案了。

「在這兩撥人幾乎同時來找我們并告訴我們說解決了這個問題之前，幾乎從沒有人來找過我們，這真是一個驚人的巧合。」Rivest 表示。

Rivest 很快承認，自己高估了難題的難度。Rivest 表示，在如此長的時間內對技術的進步進行預測有些困難，他沒想到像 FPGA 芯片這樣的突破，以前的芯片沒這么復雜，用途也沒這么廣泛。

Ron Rivest，著名密碼學家，MIT 教授。

盡管 Cryptophage 小組不是第一個揭開難題的，但 Peffers 表示他們仍將出席 5 月 15 號的時間膠囊開啟儀式。只有膠囊的設計者知道里面的全部內容，不過它的確包含蒂姆·伯納斯-李（萬維網的發明者）、羅伯特·梅特卡夫（以太網的發明者）和比爾·蓋茨等人的貢獻。Fabrot 說，他最興奮的是看到膠囊里有 Zork（最早的電腦游戲之一）的原件。