這道題本要 35 年才能解開，但他們提前 15 年就「交卷」了

1999 年，密碼學專家羅納德·李維斯特設計了一道難題，並估計最快要到 2033 年才能算出答案，也就是說需要 35 年。但是最近，一位自學成才的程序員和一個專家小組先後「交卷」，比預估的時間足足提前了 15 年，而且他們實際上用來運算的時間還要更短。

時間膠囊開啟現場。圖片來源：CASIL

撰文 戚譯引

麻省理工學院的校園中沉睡著一些時間膠囊，有的被秘密隱藏，有的已經公開相關信息，等待人們將它打開。其中一枚位於計算機科學與人工智慧實驗室（Computer Science and Artificial Intelligence Lab，CSAIL），它的歷史比 CASIL 還要久遠，原本計劃在 2033 年被打開，除非有人能提前解開一道難題，找到打開它的密碼。

這道難題名為「時間之鎖」（time lock puzzle），由著名密碼學專家、RSA 加密演算法中的「R」羅納德·李維斯特（Ronald Rivest）設計。李維斯特認為，計算機需要連續運行 35 年才能解開這道難題。

但是就在最近，一位自學成才的程序員解開了這道難題，而且他只花了三年半，用的是自己的台式機。而且幾乎就在同一時期，另一個專家小組也算出了答案。

1

「時間之鎖」的思想來自 1996 年的一篇論文，它的目標是設計一道難題，確保只有在未來的某個時間點之後才能被解開。論文作者一共三人：李維斯特、RSA 加密演算法共同發明者阿迪·薩米爾（Adi Shamir），以及當時只有 22 歲、如今是加州大學伯克利分校教授的大衛·瓦格納（David Wagnerd）。

關於「時間之鎖「難題的論文。全文參見：https://people.csail.mit.edu/rivest/pubs/RSW96.pdf

具體而言，解開難題的時間受限於兩個因素：硬體的性能，以及難題本身是否能夠通過並行計算解決。並行計算指將運算過程拆分成多個部分，這些部分能夠同時進行，最後再將計算結果匯總處理。如果一道難題能夠通過並行計算解決，那麼即使運算量很大，也可以通過增加設備的方式加快運算速度。

為了確保計算機只有連續運行一段特定時間後才能解出答案，「時間之鎖」難題需要藉助於連續的運算過程，每一步運算都依賴上一步的結果。論文作者們寫道：「解題的過程應該像懷孕一樣，兩個女人也沒法用 4.5 個月生下一個孩子。」

具體到打開這個時間膠囊的密碼，李維斯特要求解題者求出 80 萬億次平方運算的結果。例如，2 的平方等於 4，4 再平方得 16，重複這個過程 80 萬億次，就能得出一個數字。接著，將這個數字和難題提及的另一個數字帶入運算，得出一個新數字，可以翻譯成簡短的賀語。

所以，「時間之鎖」難題並不複雜，算起來卻十分繁瑣。根據當時計算機的算力和摩爾定律（即當價格不變時，集成電路上可容納的元器件的數目約每隔 18～24 個月便會增加一倍，性能也隨之提升），李維斯特認為解題至少需要計算機連續運行 35 年。

2

伯納德·法布羅特（Bernard Fabrot）是比利時的一名獨立開發者，他在 2015 年偶然發現了這道難題，對它產生了興趣。

伯納德·法布羅特（Bernard Fabrot），圖片來自 Wired

儘管李維斯特是用 Java 編寫這道難題的，但法布羅特意識到，用 GMP 解題或許更快。GMP 全稱「GNU 多重精度算術庫」（GNU Multiple Precision Arithmetic Library）這是一個用 C 語言編寫的開源數學運算庫，更加適合精確計算。

法布羅特開始在自己的台式機上運行計算。他告訴 Wired：「那幾年裡，我沒有告訴任何人我在嘗試攻破這個難題，除了關係很密切的朋友。我知道我有機會，但如果我告訴了其他人，他們就能用 CPU 更強勁的電腦超過我。」

法布洛特的擔憂或許是對的。他當時並不知道，一個計算機科學家和密碼學專家組成的小組也想要解開這道難題。

這個項目名為Cryptophage，由前任英特爾工程師西蒙·佩弗斯（Simon Peffers）領頭，正在研究可驗證延遲函數（verifiable delay functions，VDF），它或許能作為區塊鏈的保護機制。可驗證延遲函數於 2018 年被提出，它繼承了李維斯特早期的延遲密碼學研究，其解決方案同樣只能通過連續運算得到。在研究過程中，他們遇到了一個測試他們成果的好辦法——MIT 的時間膠囊。

今年 3 月中旬，小組開始運行一種優化平方運算之間延遲的演算法，由薩班吉大學（Sabanci University）研究員埃爾丁克·奧茲特克（Erdinc Ozturk）設計。這個演算法被植入現場可編程門陣列（field programmable gata array，FPGA），這是一種多功能晶元，只能運行一種演算法，因此它比通用 CPU 效率更高。在 FPGA 上，奧茲特克演算法的運算速度是普通 CPU 的十倍。

根據晶元的計算效率，Cryptophage 推算他們將用兩個月完成計算，最終在 5 月 10 日晚得到答案。然而，當他們聯繫 MIT 告知進展的時候，李維斯特告訴他們，法布羅特已經搶先一步了——他的程序跑了三年半，終於算出了答案。

「以前從來沒人找過我們，直到這兩位在同一天出現，宣稱找到了答案，真是驚人的巧合，」李維斯特說。

3

既然難題已被破解，時間膠囊被提前打開。活動在當地時間 5 月 15 日進行，法布羅特和 Cryptophage 都受邀參加。

這個時間膠囊來自 1999 年。那時候 CASIL 還叫 MIT 計算機科學實驗室（Laboratory for Computer Science），在慶祝實驗室成立 35 周年的活動中，當時的實驗室主任邁克爾?德圖佐斯（Michael Dertouzos）將它交給著名建築師弗蘭克·格里（Frank Gehry），它將被保存在格里設計的新大樓中，計劃在下一個 35 年後打開。

CASIL 位於史塔特科技中心（Ray and Maria Stata Center），由弗朗克·格里設計。圖片來源：Wikipedia

時間膠囊里裝著 50 件體現了計算機科學早期歷史的物品，包括微軟第一款產品 Altair BASIC、來自 1979 年的第一個電子表格軟體 VisiCalc 的用戶操作手冊，還有最早的萬維網和乙太網的相關記錄。在活動之前，法布羅特還說他非常期待看到最早的文字冒險遊戲之一《魔域》（Zork）的原始副本，不知道他有沒有如願。

僅僅過了十五年，計算機領域已經今非昔比。儘管「時間之鎖」的解題過程無法被簡化，軟體和硬體的進步已經大大加快了運算速度。李維斯特承認他高估了題目的難度。要在那麼長的時間跨度內預測技術的進步是很困難的，並且李維斯特說他沒有預料到會出現 FPGA 晶元這樣的技術突破，因為當時這項技術並沒有這麼複雜，也沒有如此普及。

事實上，今天的可驗證延遲函數已經開始為未來的技術發展預留更多的空間。「例如我們可以假設，攻擊者的硬體運行速度無法超過普通硬體的 100 倍，」Cryptophage 的網站上這樣寫道。

參考來源

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！