Post-Quantum-Cryptography
知道密鑰的因素如何幫助我解密？
我最近開始學習密碼學及其量子方面，我遇到了 Shor 算法（它解決了以下問題：“給定一個整數 N，找到它的質因數”）。
我還看到了這個名為“量子電腦如何破解加密 | Shor 算法解釋”的影片
我仍然對知道關鍵因素如何幫助我解決問題感到困惑。
我遇到了 Shor 的算法（它解決了以下問題：“給定一個整數 N，找到它的素數”）。
實際上，Shor 算法解決了“給定週期函式”的問題 $ f $ ，也就是說，如果 $ \underbrace{f(f(… f(a))…)}_{k\text{ times}} = a $ ， 什麼是 $ k $ ？”
通過指定 $ f $ 巧妙地，我們可以用它來解決分解問題。我注意到這一點是因為它也可以用來解決其他有趣的問題。
無論如何，您真正要問的是“如果我們可以分解密鑰，那將如何幫助我們破解 RSA”？請注意，依賴於 RSA 所依賴的因式分解的難度；其他方法（例如 Diffie-Hellman）同樣容易受到 Shor 算法的攻擊，但它們使用不同的 $ f $ 功能。
好吧，使用 RSA，公共指數 $ e $ 和私人指數 $ d $ 與 $ e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)} $ . 事實證明，如果我們知道質因數 $ p, q $ 我們知道公共指數 $ e $ （在公鑰中給出），很容易計算私有指數 $ d $ ; 這立即為我們提供了一種解密方式 $ P = C^d \bmod n $ .