簡介
現實生活中,由於 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 = Me mod N 加密,並確保 M < N
4. 以 M = Cd mod N 解密,當中可使用 CRT 加速。
破解:若果 e 並非隨機數字呢?
如果有數條 Public Key 使用了相同的 e,然後明文內容 (M) 又是一樣的話,情況就危險了。
首先,因為 e 是公開的,攻擊者如果得到 Me,可以推算回 M 的值。
假設有三條不同的 Public Keys,它們使用不同的 N,可得:
C1 = Me mod N1
C2 = Me mod N2
C3 = Me mod N3
故此,它又變成了 CRT 的問題:「某數 Me 除 N1 得 C1, 除 N2 得 C2, 除 N3 得 C3」。
例子:假設 Me 為 x,e = 3,N1 = 6,N2 = 35,N3 = 143,C1 = 5,C2 = 20,C3 = 125 :
x ≡ 5 (mod 6)
x ≡ 20 (mod 35)
x ≡ 125 (mod 143)
得出:
N = 6*35*143 = 30030,Ncrt1 = 35*143 = 5005, Ncrt2 = 6*143 = 858, Ncrt3 = 6*35 = 210
xcrt1 ≡ 5005-1 (mod 6),xcrt2 ≡ 858-1 (mod 35),xcrt3 ≡ 210-1 (mod 143)
利用 Extended Euclidean Algorithm:
5005 = 6*834 + 1
1 = 5005*(1) + 6(-834),所以 xcrt1 = 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),所以 xcrt2 = 2
210 = 143*1 + 67
143 = 67*2 + 9
67 = 9*7 + 4
9 = 4*2 + 1
將移項的算式結合,得出 1 = 210*(-32) + 143*(47),所以 xcrt3 = -32 = 143 - 32 = 111
最後得出:
x = [ ( b1* Ncrt1 * xcrt1 ) + ( b2* Ncrt2 * xcrt2 ) + ( b3* Ncrt3 * xcrt3 ) ] mod N
x = [ (5*5005*1) + (20*858*2) + (125*210*111) ] mod 30030 = 2973095 mod 30030 = 125
因為 Me = 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
No comments:
Post a Comment