Public-Key
質因數分解如何破壞 ECDSA？
我聽說 ECDSA 將在不遠的將來（大約 15 到 25 年）被執行 Shor 算法的量子電腦打破。然而，據我了解，Shor 算法的唯一目的是快速找到非常大數的質因數。雖然耗時，但這種分解在現代電腦上絕不是不可能的。使用適當的算法，可以在幾小時內找到 Secp256k1 曲線上公鑰的主要因子。如果公開密鑰的主要因素，是否有能夠從公共密鑰中導出私有 ECDSA 密鑰的公式，還是分解的其他方面會帶來如此大的安全風險？儘管對此非常關注，但我一直無法找到有關這些量子攻擊能夠破壞公鑰加密的手段的任何資訊。任何解釋，尤其是數學範例，將不勝感激。
然而，據我了解，Shor 算法的唯一目的是快速找到非常大數的質因數。
你的理解是不正確的。Shor 算法可用於分解整數和求離散對數。
Shor 的算法分為兩部分。首先，它將問題（分解或離散對數）轉化為尋找函式週期的問題。這第一步是非量子的。然後它使用量子傅里葉變換 (QFT) 找到週期。一旦你有了函式的周期，第一步就可以反過來找到原始問題的解決方案。
Shor 的算法可以在沒有 Quantum 部分的情況下使用並模擬 QFT，儘管這樣它會比最著名的經典算法慢得多。這個 python 實現模擬了 QFT，可能有助於理解。