螞蟻礦池將可以破解一個(gè)叫LCS35的加密挑戰(zhàn)

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

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

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

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

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

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

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

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

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

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

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