1999年，MIT發(fā)布了一個加密挑戰(zhàn)叫LCS35。考慮到摩爾定理和假設(shè)2012年會有10Ghz的電腦，這項(xiàng)挑戰(zhàn)預(yù)計2034年之前沒人能破解。這在密碼學(xué)屆非常有名，當(dāng)年比爾蓋茨、Tim Berners Lee（萬維網(wǎng)之父）、日本軟銀老板孫正義等都見證和贊助了這項(xiàng)挑戰(zhàn)的發(fā)布。

但是日前，一個比利時小伙剛剛破解了這個加密挑戰(zhàn)，整整提前了15年！他破解的方法用到了VDF-Verifiable Delay FuncTIons， 現(xiàn)在也是加密貨幣界關(guān)注的新技術(shù)。

這消息在密碼學(xué)屆已經(jīng)炸開了鍋，這周五MIT會舉行發(fā)布會對外宣布，還會在紐約時報和Wired雜志上報道。而螞蟻礦池在2019年4月25日周四打包高度為573138的BTC區(qū)塊時將此事記錄到了區(qū)塊鏈上“Congrats Bernard Fabrot for solving LCS35！”，意味著這件加密算法被破解的故事將被永久記錄。

LCS35加密挑戰(zhàn)是什么？

LCS35挑戰(zhàn)是由著名的RSA密碼系統(tǒng)的發(fā)明者之一Ron Rivest在1999年提出的一個很小但此前仍然未解決的挑戰(zhàn)。它包含一個任務(wù)：根據(jù)以下等式，給定2048位整數(shù)n和指數(shù)t，計算以下值：

其中t是14位（或47位）整數(shù)，比如79685186856218；n是616位（或2048位）整數(shù)，它是兩個大質(zhì)數(shù)（未給出）的乘積。然后，w的值可用于解密密文z，這是另一個616位整數(shù)。明文提供關(guān)于n的因式分解的隱藏信息，允許解題者容易地驗(yàn)證解決方案。

LCS35為什么能引起密碼學(xué)界軒然大波？難度在哪里？

這項(xiàng)挑戰(zhàn)的難度在于：在已知的范圍內(nèi)，w的值只能按順序計算，這意味著不可能并行化該過程。在不知道n的因式分解的情況下找到w值的唯一已知方法是將t連續(xù)平方。以1999年的芯片速度作為起點(diǎn)并考慮到摩爾定律的話，即便是每年用最快的增長模型替換計算機(jī)，這種簡單粗暴的計算方法要花大概35年的時間才能得到正確的t值。

LCS35挑戰(zhàn)使用了時間鎖定謎題（TIme-lock puzzles）和定時釋放（TImed-release crypto）。而且加密專家還注意到LCS35挑戰(zhàn)與RSA算法之間存在關(guān)聯(lián)（由Rivest，Shamir和Leonard Adleman共同發(fā)明），兩者都可以通過分解大量素數(shù)來打破。在這種情況下，該數(shù)值長度有2048位，而公開分解的最長素數(shù)為768位。因此，攻擊2048位素數(shù)是不可能的，這意味著具有2048位公鑰的RSA算法是安全的，并且LCS35挑戰(zhàn)只能通過上述平方方法來解決。

該項(xiàng)挑戰(zhàn)作為密碼學(xué)競賽中的一個分類，該競賽下還有eStream、后量子密碼學(xué)標(biāo)準(zhǔn)化（Post-Quantum Cryptography StandardizaTIon）、DESCHALL項(xiàng)目、RSAFactoring Challenge等國際密碼學(xué)難題

螞蟻礦池此次有幸將這一歷史性時刻記錄在區(qū)塊上，今后將攜手共同見證區(qū)塊鏈更為光明的未來！