先分清楚兩把不同的鎖
RSA 與 ECC 藏的不是同一種祕密。RSA 把祕密放在大數的質因數裡；ECC 把祕密放在公開點 P 到公開點 Q 之間的群運算次數 k 裡。
Shor 也不是把所有答案同時讀出來。它利用保持相位的疊加、干涉與量子傅立葉轉換，讓隱藏結構的線索更容易被量測。
八張圖先走直覺主線；想看 N=15 的算式時，再打開第五張下面的工程師延伸，不必一開始就卡在模運算。
1. 量子電腦到底在威脅哪一把鎖？
瀏覽器的小鎖頭、銀行連線與韌體簽章，常會用到公開金鑰密碼。它的工作通常是確認對方身分、建立共享祕密，或驗證一份資料確實由指定私鑰簽署。真正大量傳輸的內容，多半再交給 AES 這類對稱式加密處理。
RSA 與 ECC 的安全性依賴特定數學難題。Shor 演算法能在足夠大型、可容錯的量子電腦上，高效率求解整數分解與離散對數；這兩種問題都出現在他最初的工作中。攻擊者因此可能重建 RSA 私鑰，或恢復 ECC 的祕密標量。這項威脅有明確的硬體前提，不能只從「存在量子電腦」就推得攻擊已能實行。[1]
2. RSA 與 ECC 藏的是兩種不同祕密
RSA 的直覺是：選兩個很大的質數，乘成一個更大的數。乘法容易；只拿到乘積時，要把兩個質數找回來，對已知的傳統演算法非常困難。RSA 的私鑰不是單純等於那兩個質數，但知道它們後，就能算出建立私鑰所需的關鍵資料。
ECC 走另一條路。先選曲線上的公開起點 P，按照固定規則重複做點運算 k 次，得到公開點 Q。從 P 和祕密數字 k 算出 Q 很快；反過來只看 P、Q，要找出 k，就是橢圓曲線離散對數問題。
齒輪與跳格子的畫面只是在表達「正向容易、反向困難」。RSA 不是把實體齒輪拆開，ECC 的點也不是沿著平滑曲線一步一步跑；真正運算發生在有限群的規則裡。
3. Shor 不直接猜私鑰，而是改找隱藏結構
傳統電腦並非只會笨笨地逐把鑰匙嘗試。數論研究已發展出很聰明的分解與離散對數演算法；問題是當金鑰尺寸夠大時，最佳已知傳統方法仍然慢得不實用。
Shor 的突破是換題目。以 RSA 為例，它把分解問題轉成「某個模指數運算多久會重複一次」的階或週期問題。找到合適週期後，再用普通的整數運算抽出因數。ECC 版本則利用橢圓曲線群裡的隱藏關係求離散對數。兩者共享量子找結構的框架，但後段數學不同。
回聲比喻只用來記住週期這條線索。量測後還要推算候選週期、檢查條件，再做傳統計算；一次量測未必有用，也不會直接交出私鑰。文末用 N=15 展示週期與因數之間的關係，並讓你試到需要重來的底數。模型逐項搜尋週期，沒有執行量子電路。
4. 量子干涉怎麼留下週期線索？
量子暫存器可以把許多輸入放進同一個疊加狀態，接著以保持相位關係的方式計算函數。這並不等於可以把所有計算結果一次讀出；一量測，能取得的資訊仍然有限。
演算法真正的設計重點是干涉。某些振幅互相抵消，另一些振幅互相加強。量子傅立葉轉換（QFT）把重複結構轉成較容易量測的頻率線索；多跑幾次、收集量測值，再由傳統電腦推回可能的週期。
因此，圖中的水波不是「錯答案消失、正確私鑰發光」的字面過程。亮起來的是和週期相容的機率峰值，後面還要做分數逼近、驗證與可能的重試。
5. RSA：週期如何幫忙拆出因數？
拿到週期 r 之後，演算法會利用 a^r − 1 可以分成兩部分的性質，計算它們和 RSA 大數 N 的最大公因數。運氣好時，非平凡因數就會出現；運氣不好，例如週期不合用或只得到 1 與 N，就換一個 a 再試。
這也是為什麼「找到週期」與「找到私鑰」不能畫上等號。週期只是把原本困難的分解問題接到一條可行的數論路徑；取得因數後，才繼續重建 RSA 私鑰。
工程師延伸：15 的小例子到底在做什麼？
若 `N=15`、選 `a=2`，餘數序列在 `2^4` 時回到 1，所以可用週期 `r=4`。這代表 15 整除 `2^4−1`。平方差把它寫成 `(2^2−1)(2^2+1)=3×5`，於是因數剛好直接出現。
真正的大數不一定這麼漂亮。先確認週期 `r` 是偶數，再計算 `gcd(a^(r/2)−1, N)` 與 `gcd(a^(r/2)+1, N)`，檢查是否得到大於 1、小於 `N` 的非平凡因數。若 `r` 是奇數，或只得到 1 與 `N`，就換一個 `a` 重試。例如 `a=14`、`N=15`、`r=2` 時，兩個最大公因數是 `gcd(13,15)=1` 與 `gcd(15,15)=15`，還沒有取得因數。這一小例子是在展示「週期如何製造可分解的式子」，不是說所有 RSA 都只要做一次加減。
6. ECC：Shor 找的是祕密步數 k
在 ECC 中，公開資訊通常包含曲線、基點 P 與公開點 Q=kP，私鑰是 k。傳統電腦從 P、k 算 Q 很快，但從 P、Q 倒推 k 很難，這正是 ECDH 金鑰交換與 ECDSA 簽章所依賴的安全基礎。
Shor 的離散對數演算法建立兩個量子索引的疊加，計算它們在群裡組合後的位置，再用量子傅立葉分析隱藏的線性關係。量測與傳統後處理最後可以恢復 k。原始與後續工作都把離散對數列為量子電腦可在多項式時間求解的問題。[1]
主線只需要記住：RSA 是「因數被找回」，ECC 是「祕密標量被找回」。Shor 同時威脅兩者，不代表兩者用同一條分解算式。
7. 今天能破解嗎？真正急的是哪些資料？
Shor 的數學結果不等於今天已有能破解 RSA-2048 或常用 ECC 的機器。實際攻擊需要大型、可容錯、能執行長量子電路的密碼分析相關量子電腦（CRQC）。NIST 也把 CRQC 描述成未來威脅，並明確表示何時出現仍難以預測。[2]
需要現在準備的原因是資料壽命。攻擊者可以先蒐集今天攔到的密文，等未來硬體足夠時再解密，這常被稱為「現在收集、未來解密」。CISA、NSA 與 NIST 的量子就緒指南特別提醒，病歷、政府資料、研發祕密與其他需要長期保密的內容，不能等 CRQC 出現才開始換演算法。[3]
數位簽章的風險略有不同：舊密文關心未來是否被解密；簽章則關心未來是否能偽造身分、軟體更新或憑證。系統盤點時，金鑰交換與簽章都要列入。
8. 哪些要換？哪些不是 Shor 的直接目標？
Shor 的直接目標是整數分解與離散對數，因此 RSA、有限體 Diffie–Hellman／DSA，以及橢圓曲線 ECDH／ECDSA 都在遷移範圍。AES 與密碼雜湊不是 Shor 的直接目標；它們仍可能受到 Grover 等不同量子演算法影響，所以「NOT SHOR」不等於「永遠不受量子影響」。
NIST 已在 2024 年發布第一批正式後量子標準：FIPS 203 的 ML-KEM 用於金鑰封裝，FIPS 204 的 ML-DSA 與 FIPS 205 的 SLH-DSA 用於數位簽章。NIST 現在建議組織開始採用並遷移，而不是等待量子電腦成熟。[4][5]
實務順序是：找出系統裡的公開金鑰演算法與憑證、標記資料需要保密多久、確認供應商與協定支援、測試新舊系統互通，再分批遷移。PQC 不是「換一個函式名稱」；金鑰、簽章與封包大小、效能、硬體資源、憑證鏈和升級路徑都可能改變。
五點帶走
- RSA 靠整數分解困難，ECC 靠橢圓曲線離散對數困難。
- Shor 不會直接讀出所有答案；它用疊加、干涉與 QFT 找結構線索。
- RSA 利用週期抽出因數；ECC 利用群關係恢復祕密標量
k。 - 今天還沒有可實際破解常用 RSA／ECC 的 CRQC，但長期機密已有「現在收集、未來解密」風險。
- 遷移的重點是盤點公開金鑰用途，逐步導入標準化 PQC，而不是恐慌式全面停用密碼系統。
下一篇會回答一個更實際的問題：ML-KEM 如何在不使用 RSA 或 ECC 的情況下，讓兩端建立同一把共享金鑰？
References
- Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer：整數分解與離散對數量子演算法的原始論文。
- NIST NCCoE, Migration to Post-Quantum Cryptography FAQ：CRQC 威脅、公開金鑰演算法風險與遷移準備的持續更新說明。
- CISA / NSA / NIST, Quantum-Readiness: Migration to Post-Quantum Cryptography：量子就緒路線圖與「現在收集、未來解密」風險。
- NIST, Approval of FIPS 203, 204 and 205：第一批正式後量子密碼標準公告。
- NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard：ML-KEM 的正式規格與用途。
- NIST IR 8547 IPD, Transition to Post-Quantum Cryptography Standards：量子脆弱標準與 PQC 遷移方向的初始公開草案。
從週期線索抽出 15 的因數
先用 a=2，跟著餘數走到 1，找出最小正週期 r。看 r/2 那一步的值，算兩個最大公因數。再改用 a=14：仍找到週期，卻只得到平凡因數，必須重試。
這裡以傳統逐項搜尋找週期。沒有量子暫存器、QFT 或量子加速；只示範 Shor 分解流程的傳統後處理。
學習指南
安全基礎
查看課程大綱 → · 進度只計入已發布課程
先備知識
- 公開金鑰與對稱式加密的基本角色
我學會了什麼
- 區分 RSA 質因數分解與 ECC 離散對數
- 說明干涉為何留下週期線索，而非讀出所有答案
- 辨識量子脆弱的公開金鑰用途並規劃 PQC 遷移