20年未解的MIT加密難題，被自學(xué)成才的程序員破解，比預(yù)計早15年
你也可以，自學(xué)成才
栗子 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI
誕生在1999年的MIT密碼難題，被一個自學(xué)成才的程序員破解了。
當(dāng)年，出題人按照摩爾定律估計，完成計算要35年。
結(jié)局的到來，足足提前了15年。
而交卷的人類只用了i7電腦的一個CPU核。
這個密碼，還將解鎖一個20年前的秘密。
怎樣的一個謎？
回到1999年4月，MIT計算機科學(xué)實驗室 (LCS) 就要滿35歲了。
它收到了一份富有儀式感的生日禮物，是個時間囊?(Time Capsule) ：有人把重要的東西藏在里面，設(shè)定一個時間，留給未來的人類打開。
與眾不同的是，這個時間囊有一個“密碼鎖”，是由密碼學(xué)家Ron Rivest設(shè)計的。著名的RSA加密算法便是以他的名字命名。
Rivest設(shè)了一個平方密碼，初始值是2。2^2=4，4^2=16，16^2=256……
平方之后還要取模 (mod) ，就是余數(shù)。如16 ≡ 1 mod 3， 16除以3余1。
當(dāng)然，這里不是模三，是模一個很大的數(shù)：
△ 這是兩個大質(zhì)數(shù)的乘積，RSA算法的根基
那么，平方運算要做多少次？
80萬億次。
就像開頭提到的那樣，用摩爾定律推算，破解這個密碼大概需要35年。這正是實驗室當(dāng)時的年紀(jì)。
那如果一直沒有人解出答案，或者大家干脆已經(jīng)忘記了這一道謎題呢？
設(shè)計者就把35年定為最終期限。即便人類沒有交出答卷，時間囊依然會在2033年、實驗室70周年的慶典上開啟。
當(dāng)然，1999年的科學(xué)家們不會想到，四年之后LCS實驗室就和AI實驗室合體進化，成為了后來大名鼎鼎的CSAIL。
他們大概也不會想到，20年后會有人提前交卷。
并且，第一個交卷的程序員，只用了三年半來解題而已。
三年半破解謎題
2015年，謎題發(fā)射的16年后，自學(xué)成才的比利時程序員Bernard Fabrot?(簡稱“博納”) 和它偶遇了。
謎題代碼是用Java寫的，但博納認(rèn)為用GNP多精度運算庫 (GMP) 的話，解起來會更快。
這個開源庫是用C語言寫成的，也為Python、R、C++、PHP等各種語言做了包裝。
博納把家里臺式機的其中一個CPU核，變成了解題專用，7天24小時不停地跑。除非家里停電，或者要出遠(yuǎn)門。
除了最親密的朋友之外，博納不敢把自己的秘密行動告訴任何人。
“我知道我是有機會贏的，可如果告訴了別人，他們用上更強的設(shè)備就可能超過我了?！?/p>
三年有余，博納完成了那80萬億次平方運算。
最后一步，是用平方運算得到的結(jié)果、和題中給出的一個數(shù)，按題目要求做運算；算出的一串?dāng)?shù)字，可以翻譯成一句祝賀。
博納收到了溫暖的賀詞，便雞凍地向MIT宣布自己解開了謎題。
像前文說起的那樣，20年了，計算機科學(xué)實驗室不復(fù)存在，與AI實驗室合體而成的CSAIL實驗室也已赫赫有名。
而CSAIL負(fù)責(zé)人Daniela Rus聽到這個消息的時候，甚至不知道題目的存在。不過，稍微回溯一下歷史，雙方便對上了暗號。
博納現(xiàn)在還不能透露這句話是什么。一切等到5月15日，答案會和時間囊一同昭告天下。
他會帶著榮光參加這場儀式。
事實也證明，不讓太多人知道自己的想法，是非常機智的：
對手也快完成了
雖然，CSAIL負(fù)責(zé)人并不記得當(dāng)年的故事，但企圖解開這個謎團的，并不止博納一人。
還有一個根正苗紅的項目組，名叫Cryptophage，由前英特爾工程師Simon Peffers帶領(lǐng)，只為破解MIT密碼而生。
他們用的方法和博納不一樣。那是一個新的平方算法，跑在可編程的加速器FPGA上，大約比CPU快10倍。
團隊說只需要兩個月，預(yù)計5月11日就能跑出答案了。
結(jié)局總是出人意料。團隊滿懷欣喜地聯(lián)系MIT，預(yù)告即將誕生的成果，卻被告知已有人捷足先登。
雖敗猶榮，他們依然受到了邀請，參加5月15日時間囊開啟的盛會。
One More Thing
在打開之前，除了設(shè)計師沒有人知道，時間囊里究竟藏了多少秘密。
但現(xiàn)在已經(jīng)有些劇透了。有的禮物來自比爾·蓋茨，有的禮物來自萬維網(wǎng)的發(fā)明者Tim Berners-Lee。
而大贏家博納最期待的，還是世界上最早的PC游戲：Zork (魔域) 的原始版本。
謎題本題：
http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
- 馬云正式卸任后，阿里巴巴開盤跌0.87%2019-09-10
- 亞馬遜在華拓展云計算團隊，挑戰(zhàn)阿里巴巴和騰訊2019-10-16
- AI獨角獸云知聲，已完成一期科創(chuàng)板IPO輔導(dǎo)2019-10-17
- IDC：今年上半年中國公有云服務(wù)市場規(guī)模達(dá)54.2億美元2019-11-07
相關(guān)閱讀
克10-EM-P-150x150.jpg)