我開始了一系列易讀的每日帖子，主題是後量子安全。但我不知道這會持續多少天 :)。所以，讓我們拭目以待。 第1天：肖爾算法與量子末日(?) 我們的安全堆棧大部分依賴於一個假設：整數因式分解和離散對數是「困難的」。在經典矽上，它們確實是。要破解RSA-2048，你需要的時間簡直比宇宙的年齡還要長。 但這並不是一條物理法則。這是經典計算的限制。 1994年，彼得·肖爾展示了它們可以在量子計算機上高效解決。肖爾算法不僅僅是暴力破解密鑰；它使用量子傅里葉變換（QFT [不是量子場論，哈哈]）來找到函數f(x) = a^x mod N的周期。一旦你有了周期，你就有了因子。 一旦你有了因子，私鑰就死了。因為私鑰可以從公鑰重建。複雜度的轉變才是真正的「末日」。我們從亞指數時間轉變為多項式時間O((log N)^3)。我們不是在談論10倍的加速；我們是在談論從數萬億年縮短到幾小時在CRQC上。 與RSA類似，ECC（橢圓曲線密碼學）也不是安全的。由於其高效的代數群結構，破解256位ECC密鑰實際上需要的邏輯量子位數比RSA-2048還要少。 --- 感謝你的閱讀！明天，我們將討論為什麼HNDL（現在收割，稍後解密）威脅意味著後量子過渡必須立即發生。 （視覺：彼得·肖爾）