RSA 演算法正確性證明
RSA 相關內容網上很多，但是大多數都更強調怎麼實際使用，相關的數學證明和理解比較少，或者看著總不是很明白，所以就基於我自己的理解來寫一寫
RSA
RSA 是基於「大整數分解這一數學困難問題」的公鑰密碼體制
須知定理
- 歐拉函數：設 m 是一個正整數，則 m 個整數 1，… ，m - 1 中與 m 互素的整數的個數記為 φ(n)，通常叫做歐拉函數
- 若 p 是素數，則 φ(p) = p - 1
- 設 m，n 是互素的兩個正整數，則 φ(mn) = φ(m)φ(n) = (m - 1)(n - 1)
- 歐拉定理：設 m 是大於 1 的整數，如果 a 滿足 gcd(a, m) = 1 的整數，則：a^φ(m) = 1(mod m)
祕鑰的產生
- 選擇兩個大素數 p 和 q，計算 n = p * q，φ(n) = (p - 1)(q - 1)
- 選一個整數 e，滿足 gcd(φ(n), e) = 1 (1 < e < φ(n))
- 計算出滿足等式 d * e = 1 (mod φ(n)) 的值 d
- 以 {e, n} 為公鑰，{d, n} 為私鑰
加密解密
密文為 c，明文為 m c = m^e (mod n)，m = c^d (mod n)
演算法解密的正確性證明
已知 c = m^e (mod n)， 則 m = c^d (mod n) = m^ed (mod n) = m^1(modφ(n)) = m^kφ(n)+1 (mod n)， 因此只需證明 m = m^kφ(n)+1 (mod n) 分為兩種情況：
① m 與 n 互素
由歐拉定理得 m^φ(n) = 1(mod n)，則 m^kφ(n) = 1(mod n)，則 m^kφ(n)+1 = m(mod n)
② m 與 n 不互素
因為 m < n (原因見下面)，p 和 q 又都是素數，意味著 m 要麼是 p 的倍數，要麼是 q 的倍數，不能同時是 p 和 q 的倍數（如果同時是 p 和 q 的倍數，那 m > n），不妨設 m 是 p 的倍數，則 m = cp，其中 c 為正整數， 那麼 gcd(m, q) = 1，由歐拉定理得：
m^φ(q) = 1(mod q)
那麼
m^kφ(q) = 1(mod q)
(m^kφ(q))^φ(p) = 1^φ(p)(mod q)
(m^kφ(q))^φ(p) = 1(mod q)
m^kφ(n) = 1(mod q)
所以，會存在一個整數 r，使得 m^kφ(n) = 1 + rq，兩邊同時乘以 m = cp 得：
m^kφ(n)+1 = m + rcpq = m + rcn
即 m^kφ(n)+1 = m(mod n)
綜上所述，無論 m 和 n 是否互素，RSA 都能對消息正確得進行解密
注意點
- 加密的時候要求明文 m 要小於 n。如果 m > n，而在計算過程中用到了 mod 運算，則不能通過解密演算法正確求得明文 m，只能得到比 n 小且與 m(mod n) 同餘的整數
- 祕鑰生成過程中的 p，q，φ(n)，一般都要安全地銷毀，p，q 的存在是可以提高 RSA 演算法的解密速度的。為什麼 n 不用銷毀？因為目前來說分解兩個大素數仍然一個數學困難問題，也就是說已知 n 來求得 q 和 p 是很困難的。那為什麼要把 φ(n) 銷毀？因為 φ(n) = (p - 1)(q - 1)，而 n = p * q，根據這兩個式子就可以算出 p，q 了
推薦閱讀：
