在多大的模数大小下，logjam还原阶段变得不切实际了？

Question

攻击Diffie-Hellman交换与日志阻塞涉及一个庞大的预计算努力一次，然后是一个相对简单的减少阶段，这是必要的打破每一个单独的握手。在多大的DH大小，减少步骤，没有预先计算，变得不切实际？

例如，如果1024位DH组的缩减阶段可以实时完成，而预计算阶段需要一年时间，而硬件方面则需要1 000万美元(从原始的逻辑论文中估计)，那么DH组在减少阶段需要多大才能要求硬件和一年的1 000万美元的费用(有效地否定了预计算的优势)？

Answer 1

在这种规模下，很难将具体成本计入这些步骤，而且可以调整参数，使预计算成本更高，从而降低单个日志的成本，但我们可以尝试逐步地这样做，以获得一个概念。预计算步骤的复杂性是L_p[1/3, 1.923] = \exp\left((1.923 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,, ，在1024位素数字段的情况下，假设o(1) = 0-would大致相当于2^{86}操作^1。

另一方面，单个对数的L_p[1/3, 1.232] = \exp\left((1.232 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,. 复杂度又一次降低了，假设o(1) = 0需要一个粗略的2900-bit素数来匹配1024位预计算的成本。2900位的预计算步骤将超出2^{128}操作。

^1这个复杂性图通常忽略内存和存储成本，随着数字的增长，这些开销变得越来越重要，但无论如何，这是一个粗略的近似。