我们将如何设计一个快速电路来解决LCS35？

Question

LCS35是一个时间锁难题，在罗纳德·L·里弗特的LCS35时间胶囊密码的描述 1中有这样的说法。它实例化了罗纳德·L·里弗特、阿迪·沙米尔和大卫·瓦格纳的时间锁谜题和定时释放密码 2中的一个系统。

解决这个难题可以归结为为2^{(2^t)}\bmod n计算n，一个公共2046位RSA秘密分解模数，以及t\approx1.13\cdot2^{46}。引用方法通过迭代w_i=2^{(2^i)}\bmod n (从w_0=2开始，或者可能从w_{10}=2^{1024}开始)，依次计算i的w_{i+1}\gets w_i^2\bmod n到t。

为此，我们将如何设计快速电路？它能达到什么样的速度(以等效的模块平方每秒)？我感兴趣的是

• 数学技巧:例如蒙哥马利算术有用吗？
• 架构权衡:例如，电路深度和尺寸之间的权衡，两者都会导致速度减慢。
• 技术:当涉及到快速逻辑时，我甚至不知道什么技术是目前最先进的技术，更不知道它能实现什么。

LCS35的设计试图阻止大规模并行化的尝试，据我们所知，大部分都是成功的。不过，问题是如何计算。

t的值在1999年被选择为3000平方秒/秒，指数增长到2012年的×13，然后又是×5 / 2034 (挑战结束于2033年)。

我建议忽略：

• 运营成本:与比特币挖掘相比，这是可以忽略不计的，除非我们找到一种并行化的方法，这将是一个重大突破。
• 投资成本:这取决于太多的因素，而且评估是不可伪造的。
• 计算错误，因为我们知道如何处理：
  • 参考1建议计算w'_i=2^{(2^i)}\bmod(c\,n)，其中c是中等素数(50位)。这允许对w'_i\bmod c\ =\ 2^{(2^i)\bmod (c'-1)}\bmod c进行定期检查，如果出现错误时可以进行回溯，并最终得到w_t\gets w'_t\bmod n。
  • 一个变体是计算两个独立引擎上的w'_i=2^{(2^t)}\bmod(3n)和w''_i=2^{(2^t)}\bmod(5n) (方便地，两个模块都是2048位)，并定期检查w'_i\bmod n=w''_i\bmod n。这需要两个独立的实现，但模数的大小几乎没有增加，因此(我猜)计算速度更快，计算引擎也更小。

• 本质上影响n的攻击，包括使用量子计算机。
• 替代LCS35的定时释放密码，在这个其他问题中被问到.

Answer 1

原来LCS35问题是第一个由伯纳德·法布罗于2019年4月15日破案问题。它花费了3.5年的运行时间在一个标准的现代CPU的核心上，使用了GMP。

独立地，隐噬菌体项目在不到2个月的时间内解决了LCS35问题，从2019年3月中旬开始，使用了一个基于FPGA的系统，该系统以极低的延迟执行模块平方。