1994 年 4 月，作為麻省理工學院電腦科學實驗室成立 35 週年的慶祝活動，時任實驗室主任 Michael Dertouzos 設計了一個「創新成果時間膠囊」。
他將一系列電腦領軍人物的創新成果收錄其中，準備在35年後再取出來，作為實驗室成立 70 週年的禮物。
不過問題來了，如何能保證剛好在 35 年之後取出來呢？這可難不倒麻省理工學院這些頂級的科學家，他們為時間膠囊設計了一把「密碼鎖」，也就是一道密碼學難題。
同時，他們還非常嚴謹地考慮了未來電腦算力的提升速度，特意加強難度，使得密碼學難題至少需要 35 年時間來破解。
業界一堆密碼學「大牛」也都十分清楚，麻省理工學院給出的密碼學難題肯定不是鬧著玩的，所以就沒在上面浪費時間。於是乎，這道密碼學難題足足塵封了 20 年之久。
今年 4 月，一名工程師成功地破解了麻省理工學院的密碼學難題，更厲害的是，這名工程師並不是用了 20 年，他在2015年才偶然發現了這個密碼學難題，也就是說他破解只用了 3 年的時間。
他是怎麼做到的？他又有著什麼樣的訣竅？讓我們一起走進這名工程師的傳奇。
「簡單」的麻省理工學院密碼學難題
那麼，Rivest設的這個密碼學難題到底是什麼呢？
簡單來說，這個難題就是要找到運行近 80 兆次平方操作的結果。比如說，如果你從 2 開始計算，平方後就得到了 4 ，緊接著 4 再進行平方計算就得到了 16 ，這個過程需要重複 80 兆次。
麻省理工學院密碼學難題的形式十分簡單
當然了，每次平方計算後還需要對一個很大的數字 n 求模值，也就是求除以 n 之後的餘數，最後算得的結果與難題中給定的一個數字進行數學計算，你就會得到一個新的數字，也就是這個密碼學難題的答案。
雖然說當前密碼學難題已經被破解，但出題人 Rivest 和破題人 Fabrot 都拒絕透露確切的答案。他們準備在 5 月 15 日舉行一個開啟時間膠囊的儀式，屆時將會在儀式上公布答案。
你可能覺得這看起來也不難嘛，用更多的電腦加大算力不就可以了麼？事實上沒那麼簡單。這個密碼學難題的關鍵在於它需要順序操作，也就是說你需要在前一步計算結果的基礎上，進行這一步的平方計算，這意味著你只能一步步計算來得到結果，而無法透過當下常用的平行計算來更快地得到答案。
Ron Rivest在當年的說明中，給出的解題思路示例
因此使用更多的電腦或是超級電腦都無濟於事。考慮到「摩爾定律」（Intel創辦人Gordon Moore提出的：微處理器的性能每隔 18 個月提升一倍），以及在 1999 年進行平方操作所需要的時間，Rivest 估計僅靠計算得出密碼學難題的答案至少需要 35 年。
而作為一名獨立開發者，Fabrot是在 2015 年才偶然發現了這個密碼學難題。Rivest 最初使用 Java 語言開發了破解難題的代碼。
後來，他便意識到如果借助 GNU 多精度運算程式庫（GNU Multiple Precision Arithmetic Library）這個用 C 語言編寫的精確運算工具，可以加快破解難題的速度。
所以 Fabrot 立即著手去做，他在家裡的桌上型電腦上專門分出一個 CPU 核心用於運行平方計算，在此期間除了他去度假或是家裡停電，Fabrot 的電腦一直在全天候運行。
「在這些年裡，除了非常親密的幾個朋友之外，我沒有向任何人透露過我正在解決這個密碼學難題，」 Fabrot 說，「我相信自己可以做到，同時我也知道如果我告訴其他人，他們可能會使用更強大的 CPU 來超越我。」
三年半之後， Fabrot 終於完成了大約 80 兆的平方計算，得到了密碼學難題的結果。
本文為巴比特資訊授權刊登，原文標題為「塵封20年的密碼學難題，被無名程序員3年破解」