CRT 孫子定理應用 2：破解 RSA 內容

簡介
現實生活中，由於 RSA 的公鑰中每一個 Parameters 都會由 OpenSSL 隨機產生，所以 RSA 理論上仍然安全。不過，若果公鑰中有些 Parameters 並不是隨機產生的話，RSA 將會十分危險。以下文章會以 constant e 的情況作為示範。

RSA 算法重温（可查看此互動網頁）
1. 先找出兩個質數的數字 p 和 q，得出 N = p*q 和 r = (p-1)(q-1)
2. 找出 e*d mod r = 1 的任何一個組合，並確保 e 和 r ，以及 d 和 r 均互質 (relatively prime)。
3. 以 C = M^e mod N 加密，並確保 M < N
4. 以 M = C^d mod N 解密，當中可使用 CRT 加速。

破解：若果 e 並非隨機數字呢？
如果有數條 Public Key 使用了相同的 e，然後明文內容 (M) 又是一樣的話，情況就危險了。
首先，因為 e 是公開的，攻擊者如果得到 M^e，可以推算回 M 的值。
假設有三條不同的 Public Keys，它們使用不同的 N，可得：
C₁ = M^e mod N₁
C₂ = M^e mod N₂
C₃ = M^e mod N₃

故此，它又變成了 CRT 的問題：「某數 M^e 除 N₁ 得 C₁， 除 N₂ 得 C₂， 除 N₃ 得 C₃」。
例子：假設 M^e 為 x，e = 3，N₁ = 6，N₂ = 35，N₃ = 143，C₁ = 5，C₂ = 20，C₃ = 125 ：
x ≡ 5 (mod 6)
x ≡ 20 (mod 35)
x ≡ 125 (mod 143)

得出：
N = 6*35*143 = 30030，N_crt1 = 35*143 = 5005， N_crt2 = 6*143 = 858， N_crt3 = 6*35 = 210
x_crt1 ≡ 5005^-1 (mod 6)，x_crt2 ≡ 858^-1 (mod 35)，x_crt3 ≡ 210^-1 (mod 143)

利用 Extended Euclidean Algorithm：
5005 = 6*834 + 1
1 = 5005*(1) + 6(-834)，所以 x_crt1 = 1

858 = 35*24 + 18，移項可得 18 = 858 - 35*24
35 = 18*1 +17，移項可得 17 = 35 - 18*1
18 = 17*1 + 1，移項可得 1 = 18 - 17*1
將移項的算式結合，得出 1 = (858 - 35*24)*2 - 35 = 858*2 + 35(-49)，所以 x_crt2 = 2

 210 = 143*1 + 67
143 = 67*2 + 9
67 = 9*7 + 4
9 = 4*2 + 1
將移項的算式結合，得出 1 = 210*(-32) + 143*(47)，所以 x_crt3 = -32 = 143 - 32 = 111

最後得出：
x = [ ( b₁* N_crt1 * x_crt1 ) + ( b₂* N_crt2 * x_crt2 ) + ( b₃* N_crt3 * x_crt3 ) ] mod N
x = [ (5*5005*1) + (20*858*2) + (125*210*111) ] mod 30030 = 2973095 mod 30030 = 125

因為 M^e = 125，已知 e = 3，所以可計算 root(125, 3) = 5 ，從而得知 M = 5。

備註
對於 e 值稍有不同，但 N 相同的 RSA 公鑰，同樣可以使用另一種破解方法，參見此頁。
由於這個方法並非使用 CRT，所以不在本章討論。

小結
這篇文章示範了使用非隨機 Parameter 對 RSA 的危險性。其實，只要 RSA 中的每一個 Parameters 都是隨機產生，加上長度足夠，RSA 暫時來講仍然安全。不過，隨著 Shor's Algorithm 以及量子電腦的出現，RSA 被成功破解的可能性，將會越來越高。所以，我們可以預料，Lattice-based 的 Post-Quantum Cryptography 的發展，將會越來越快。

---

參考：

[1] - https://www.youtube.com/watch?v=15xcBE7MFBg