非對稱式密碼（asymmetric cipher） 使用兩把金鑰：公鑰（public key） 公開，私鑰（private key） 保密。
解決金鑰分發問題#
用公鑰加密的任何訊息只能用私鑰解密。這消除了金鑰分發的問題——公鑰是公開的，用公鑰即可為對應私鑰加密訊息，不需要頻外通道傳輸祕密金鑰。代價是：非對稱式密碼往往比對稱式慢得多。
RSA#
RSA 是較流行的非對稱演算法之一，其安全性建立在大數分解的困難上。
金鑰生成流程：
- 選兩個質數 P、Q，計算乘積
N = P · Q。 - 計算 Euler 函數 φ(N)（1 到 N−1 之間與 N 互質的數的個數）。若 N 是兩質數 P、Q 的乘積，則
φ(P·Q) = (P−1)·(Q−1)。 - 隨機選一個與 φ(N) 互質的加密金鑰 E。
- 找一個滿足
E · D = S · φ(N) + 1的解密金鑰 D（S 為任意整數）。
第 4 步用擴展歐幾里得演算法求解。歐幾里得演算法是計算兩數最大公因數（GCD）的極快方法：大數除以小數只看餘數，再用小數除以餘數，重複到餘數為 0，最後非零的餘數就是 GCD。它執行時間
O(log₁₀N)——步數約等於較大數的位數。
加解密函式：
加密：C = M^E (mod N)
解密：M = C^D (mod N)例如 P=11、Q=13 → N=143、φ(N)=120；取 E=7253、算出 D=77。訊息 M=98：
98^7253 = 76 (mod 143) ← 密文 76
76^77 = 98 (mod 143) ← 只有知道 D 的人能還原公鑰為 (N, E)、私鑰為 D，而 P、Q 被丟棄。
RSA 的數學核心：Euler 定理
RSA 由 Euler 全等定理成立：若 M 與 N 互質且 M < N，則 M 自乘 φ(N) 次再對 N 取餘數，餘數永遠是 1：
若 gcd(M, N) = 1 且 M < N，則 M^φ(N) = 1 (mod N)重複 S 次並兩邊乘 M：
M^(S·φ(N)+1) = M (mod N)這本質上是「輸入自己」的函式。但若能拆成兩部分，一部分加密、一部分解密，就能還原訊息——找 E、D 使 E·D = S·φ(N) + 1，代入即得 RSA。
RSA 安全性繫於保密 D。但 N、E 都公開，若 N 能分解回 P、Q，就能算出 φ(N)、進而用擴展歐幾里得算出 D。因此 RSA 金鑰大小必須考量最佳已知分解演算法。目前最佳是數域篩法（NFS），執行時間次指數——仍不足以在合理時間內破解 2048 位元 RSA 金鑰。
Shor 量子分解演算法#
Shor 演算法：量子平行如何有效分解大數
Peter Shor 利用量子平行性，配合一個古老的數論技巧有效分解數字：
- 取要分解的 N，選一個小於 N、與 N 互質的 A（若不互質，A 就是 N 的因數之一）。
- 把 1 起的連續數字載入疊加態，同時對每個值算
f(x) = A^x (mod N)。 - 結果會出現重複模式，用傅立葉轉換在量子電腦上快速求出重複的週期 R。
- 計算
gcd(A^(R/2) + 1, N)與gcd(A^(R/2) − 1, N)，至少一個是 N 的因數。
以破解前例（N=143）為例，取 A=21、f(x)=21^x (mod 143)：
x=1 → 21 x=2 → 12 x=3 → 109 x=4 → 1
x=5 → 21 x=6 → 12 x=7 → 109 x=8 → 1週期 R=4。gcd(21²−1, 143)=11、gcd(21²+1, 143)=13——兩個因數都出現了，可用來重算私鑰。