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

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

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

Bernard Fabrot

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ron Rivest，著名密碼學(xué)家，MIT 教授。

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