蚂蚁矿池将可以破解一个叫LCS35的加密挑战_技术

1999年，MIT发布了一个加密挑战叫LCS35。考虑到摩尔定理和假设2012年会有10Ghz的电脑，这项挑战预计2034年之前没人能破解。这在密码学届非常有名，当年比尔盖茨、TIm Berners Lee（万维网之父）、日本软银老板孙正义等都见证和赞助了这项挑战的发布。

但是日前，一个比利时小伙刚刚破解了这个加密挑战，整整提前了15年！他破解的方法用到了VDF-Verifiable Delay FuncTIons，现在也是加密货币界关注的新技术。

这消息在密码学届已经炸开了锅，这周五MIT会举行发布会对外宣布，还会在纽约时报和Wired杂志上报道。而蚂蚁矿池在2019年4月25日周四打包高度为573138的BTC区块时将此事记录到了区块链上“Congrats Bernard Fabrot for solving LCS35！”，意味着这件加密算法被破解的故事将被永久记录。

LCS35加密挑战是什么？

LCS35挑战是由著名的RSA密码系统的发明者之一Ron Rivest在1999年提出的一个很小但此前仍然未解决的挑战。它包含一个任务：根据以下等式，给定2048位整数n和指数t，计算以下值：

其中t是14位（或47位）整数，比如79685186856218；n是616位（或2048位）整数，它是两个大质数（未给出）的乘积。然后，w的值可用于解密密文z，这是另一个616位整数。明文提供关于n的因式分解的隐藏信息，允许解题者容易地验证解决方案。

LCS35为什么能引起密码学界轩然大波？难度在哪里？

这项挑战的难度在于：在已知的范围内，w的值只能按顺序计算，这意味着不可能并行化该过程。在不知道n的因式分解的情况下找到w值的唯一已知方法是将t连续平方。以1999年的芯片速度作为起点并考虑到摩尔定律的话，即便是每年用最快的增长模型替换计算机，这种简单粗暴的计算方法要花大概35年的时间才能得到正确的t值。

LCS35挑战使用了时间锁定谜题（TIme-lock puzzles）和定时释放（TImed-release crypto）。而且加密专家还注意到LCS35挑战与RSA算法之间存在关联（由Rivest，Shamir和Leonard Adleman共同发明），两者都可以通过分解大量素数来打破。在这种情况下，该数值长度有2048位，而公开分解的最长素数为768位。因此，攻击2048位素数是不可能的，这意味着具有2048位公钥的RSA算法是安全的，并且LCS35挑战只能通过上述平方方法来解决。