假設一台 1024qb 的量子電腦，暴力破解 1024bit RSA、256bit AES 和 512bit SHA512 需要多長時間

假設將來有一台正常工作的 1024 量子位量子超級電腦，它可以執行Shor 算法或Grover 算法以非常快速地破解加密。我對量子比特的數量如何轉化為正常 2 位電腦的性能改進感興趣。

例如，如果我在 4 量子比特的量子超級電腦上使用 Shor 算法，那麼分解 1024 位 RSA 的時間是否會像普通的 2 比特超級電腦那樣需要一半的時間？那麼，如果我們向上推算到 8 個量子位的超級電腦到 512 個量子位、1024 個量子位甚至 2048 個量子位等。添加更多的量子位會帶來什麼樣的因式分解速度提升？我最初認為量子電腦只能有 4 個量子比特。但現在看來，在技術原因範圍內，您可以繼續將量子比特添加到您想要的數量。這是否意味著如果我有一台 1024 量子位的超級電腦，我可以在一瞬間分解 RSA 1024 位？它可以以什麼速度檢查可能的因式分解？

所以我很感興趣“理論上”需要多長時間：

1. 蠻力使用 Shor 算法找到 1024 位加密 RSA 消息的密鑰。
2. 蠻力使用 Grover 算法找到 256 位 AES 加密消息的密鑰。
3. 查找 SHA2-512 位雜湊的前映像。
4. 為 SHA2-512 位雜湊構造彩虹表。
5. 如果人們現在使用 2048 位 RSA 作為標準，是否需要兩倍以上的時間？

非常感謝您對如何計算它的一些解釋以及以秒、分鐘、小時、天或年為單位的分解時間。

添加更多的量子比特不會提高計算速度。具有 4 個量子位的量子電腦不會比具有 2 個量子位的量子電腦更快。量子位是量子電腦的“記憶體”。更多的量子比特意味著你可以分解更大的數字。如果我沒記錯的話，你需要一個疊加 $ \Theta(N^2) $ 術語，這意味著 $ \Theta(\log(N^2)) $ qubits 到因子 N。Shor 算法的執行時間是 $ O((\log N)^3) $ 分解[數學處理錯誤] $ N $ 。重要的是要記住 Shor 的算法只能分解（通過解決離散對數問題）。請參閱維基百科關於 Shor 算法的條目。

至於 Grover 算法，它在“黑盒”查詢方面提供了優於經典電腦的二次優勢。所以量子電腦可以在[數學處理錯誤] $ O(\sqrt{N}) $ 試驗而經典電腦需要 $ O(N) $ trials. Again, increasing the number of qubits does not lower the running time, but increases the “memory” of the quantum computer. In order to run Grover’s algorithm to brute-force a key, you need a superposition of all keys, which requires $ \log K $ qubits where [Math Processing Error] $ K $ is the number of possible keys.

With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned.

Current estimations for an impelmentation of Grover’s algorithm for AES requires much more qubits. According to this paper by Grassl et al. the required number of qubits required for AES-256 is 6681, see the following extracted table:

I guess it’s not unreasonable to draw similar conclusions for SHA2-512, which has a much bigger internal state, and say that 1024 qubits are not enough.

And regarding RSA, there is a paper from Proos and Zalka with estimations for RSA and ECC. See the image below extracted from the paper:

Which clarifies that you need 2048 qubits to factor a 1024 RSA key. As noted by user1147688 in a comment this paper talks about logical qubits, and specifies that:

Also it seems very probable that for large scale quantum computation error correction or full fault tolerant quantum computation techniques are necessary. Then each of our “logical” qubits has to be encoded into several physical qubits (possibly dozens) and the logical quantum gates will consist of many physical ones.

Making the target number of qubits to break RSA-1024 much higher than the theoretical 2048.

Edit1: to take into account comment by user1147688

引用自：https://crypto.stackexchange.com/questions/9480