證明RSA演算法在明文和公私鑰中N不互質情況下仍然成立
下文中的 k 代表自然數常數，不同句子，公式中不一定代表同一個數
之前接觸RSA，沒有過多的思考證明過程，今天有感而發，推到了一遍
假設公鑰 (e, N) , 私鑰 (d, N) ，那麼 ed = k * g (N) + 1 ， g是歐拉函數，假設 N = p * q ，p 和 q 都是 大素數， 那麼 g (N) = ( p – 1 ) * ( q – 1 ) , k 是自然數
假設明文是 M , 那麼 密文 C = M ^ e (mod N)
密文再次運算的結果是明文，即使明文 R = C ^ d ( mod N ) = ( M ^ e ) ^ d ( mod N ) = M ^ (ed) (mod N)
最後 明文 R = M ^ (ed) (mod N) = M ^ ( k * g(N) + 1 ) ( mod N )
要從 R 推出明文，就要證明 R 和 明文 M 模N 同餘，也就是 R = k * N + M (k 為自然數)
很簡單的一種情況是 明文 M 和 N 是互質的，因為根據歐拉定理 ：
如果 下圖的 a 和 n 互質，則有
如果 M 和 N 互質，則兩邊乘 M
M ^ ( k * g(N)) 
1 (mod N ) =》 [ M ^ ( k * g(N)) ] * [ M ] = M ^ ( k * g(N) + 1 ) = R M ( mod N )
如果 M 和 N 不是互質，就比較難證明了
M 和 N 不互質，那麼 M 和 N 必然有一個非1的公因子 ， 假設為 g , 則 N = k1 * g , M = k2 * g (k1, k2 均是常數)
兩個素數相乘的積，只有四個因子，分別是 兩個乘起來的素數，1，還有積本身。
那麼 g 就應該是 這四個因子中的一個，前提已經假設 g 非1，那麼 g 可能是剩下三個中的一個。
但是根據 RSA 規範：
5.1.1RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1
M 應該小於 N，那麼 g 就不能取 N，否則 M = k * g = k * N > N
在當前上下文，N = p * q , p 和 q 就是 那兩個大素數， N 就是乘積，那麼 g 就應該是 p 或 q ，可以推出 M = k0 * g = k * q 或者 M = k * p （k0，k 是自然數）
（g是M和N的非1公因子，所以可以寫成 M = k0 * g 的形式）
因為 M < N , 假如 M = k * p , 那麼 k = M / p < N / p = q ，也即 k < q ，那麼 k 必然和 q 互質，因為 q 是素數 （原因見下圖）。M = k * q 時同理
（k 和 q） 與 p 都互質，則有 k * q 與 p 互質。（因為 q 是素數，那麼 k * q 分解的話只能分解出 k 和 q，必然沒有 p 的因子，下同理）
或者 （k 和 p） 與 q 都互質，則有 k * p 與 q 互質。
再用一次歐拉定理，下面假設 M = k * p
(k * p) ^ (g(q)) 1 (mod q)
因為 q 是素數，比 q 小的數都和 q 互質，所以有 q – 1 個數 和 q 互質，也就是 q 的歐拉函數運算結果 g (q) = q – 1
也就是：
(k * p) ^ (q – 1) 1 (mod q)
下面還要用到一個推到：
假如 A 1 (mod q) （公式1），那麼 ( A ) ^ h 1 (mod q) （公式2）
推到： 由公式1得到 A = k * q + 1 , 將 A 代入公式2， ( k * q + 1 ) ^ h 在展開後，只有最後一項是1，不帶 k * q，其他都帶 k * q , 所以 A^h = ( k * q + 1 ) ^ h 在 mod q 之後還是等於1
所以公式2成立
把 A 換成 (k * p) ^ (q – 1) , h 換成 k0 * (p – 1)
(k * p) ^ (q – 1) 1 (mod q)
可以轉化成
[ ( k * p ) ^ ( q – 1) ] ^ ( k0 * ( p – 1 )) 1 (mod q)
[ ( k * p ) ] ^ [ k0 * ( q – 1) * ( p – 1 )] 1 (mod q)
根據 ed = i * g(N) + 1 = i * (p – 1) * (q – 1) + 1
[ ( k * p ) ] ^ (ed – 1) 1 (mod q)
兩邊同乘 k * p
[ ( k * p ) ] ^ (ed) (k * p) (mod q)
可以寫成:
[ ( k * p ) ] ^ (ed) = (k * p) + k1 * q (k1 是自然數常數)
那麼
[ ( k ) ^ (ed) ] * [ p ^ (ed ) ] = (k * p) + k1 * q
[ ( k ) ^ (ed) ] * [ p ^ (ed ) ] – k * p = k1 * q
[ [ (k) ^ (ed) ] * [ p ^ (ed – 1) ] – k ] * p = k1 * q
左邊是 p 的倍數，右邊應該也是 p 的倍數，又 p 和 q 互質，那麼只能 k1 是 p 的倍數
回到之前的公式，把 k1 = k2 * p 代入
[ ( k * p ) ] ^ (ed) = (k * p) + k1 * q =》 [ ( k * p ) ] ^ (ed) = (k * p) + k2 * p * q
因為 N = p * q，繼續代入
[ ( k * p ) ] ^ (ed) = (k * p) + k2 * N
[ ( k * p ) ] ^ (ed) ( mod N ) = [(k * p) + k2 * N ] (mod N) = (k * p) (mod N)
M = k * p 也就是
M ^ (ed) (Mod N) = M (mod N)
也就是 M ^ (ed) 和 M 模 N 同餘
也即，R = M ^ (ed) 和 M 同餘
證畢
