我开始了一系列易读的每日帖子，主题是后量子安全。但我不知道这将持续多少天 :). 第1天：肖尔算法与量子末日(?) 我们大部分的安全堆栈——RSA、ECC、Diffie-Hellman——依赖于一个单一的假设：整数因式分解和离散对数是“困难的”。在经典硅基计算中，它们确实是。要破解RSA-2048，你需要的时间简单来说超过宇宙的年龄。 但这并不是物理法则。这是经典计算的限制。 1994年，彼得·肖尔展示了它们可以在量子计算机上高效解决。肖尔算法不仅仅是暴力破解密钥；它使用量子傅里叶变换（QFT [不是量子场论，哈哈]）来找到函数f(x) = a^x mod N的周期。一旦你有了周期，你就有了因子。 一旦你有了因子，私钥就完蛋了。因为私钥可以从公钥重构。复杂度的转变才是真正的“末日”。我们从亚指数时间转变为多项式时间O((log N)^3)。我们不是在谈论10倍的加速；我们是在谈论从数万亿年缩短到几小时在CRQC上。 与RSA类似，ECC（椭圆曲线密码学）也并不安全。由于其高效的代数群结构，破解256位ECC密钥实际上需要的逻辑量子比RSA-2048更少。 --- 感谢阅读！明天，我们将讨论为什么HNDL（现在收割，稍后解密）威胁意味着后量子过渡必须现在发生。 （视觉：彼得·肖尔）