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

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

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

Bernard Fabrot

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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