RSA 加密與解密
RSA 為非對稱式加密，也就是說用來加密的鑰匙 跟 用來解密的鑰匙 是不相同的。
用來加密的鑰匙稱為公鑰，公鑰是可以公開的，任何人有了公鑰後，可以對明文訊息以公鑰加密後變成密文，傳送給接收方。
用來解密的鑰匙稱為私鑰，接收方收到密文後，可以利用私鑰來解密，得到明文訊息。
其它人就算得到密文，也因為沒有私鑰，所以無法將密文解密。
本文分成以下數個部分：
RSA 的加密與解密方式
RSA 的公鑰及私鑰
RSA 的解密原理
RSA 的加密與解密範例
RSA 的加密與解密方式
RSA 加密與解密方式為：公鑰加密，私鑰解密
公鑰： e, n
私鑰： d, n
訊息： m
密文： c
將 m 加密，得到密文 c，加密方式為：
me ≡ c (mod n)
對 m 的 e 次方 取 n 的餘數，所得值為 c。
將 c 解密，得到明文 m，解密方式為：
cd ≡ m (mod n)
對 c 的 d 次方 取 n 的餘數，所得值為 m。
從上述加、解密方式可以知道，公鑰及私鑰不能是隨便產生的，必須遵循它的規則，否則上述算式將不會成立。
RSA 的公鑰及私鑰
要計算 RSA 的公鑰及私鑰，得先從決定 n 的值開始。
選擇兩個質數 p 及 q，令
n = p x q。
令 f(n) 為與 n 互值且小於 n 的整數個數，根據 歐拉定理
f(n) = (p-1) x (q-1)。
決定公鑰 e 的值，條件為： e 與 f(n) 互質，且 1 < e < f(n)。
決定私鑰 d 的值，條件為： 使得
d x e ≡ 1 (mod f(n)) 成立。
如此公鑰及私鑰都已經決定完成。
RSA 的解密原理
解密的方式為：
cd ≡ m (mod n)
所以要証明上述加、解密可以運作順利，就要証明上式成立。
因為加密方式為：
me ≡ c (mod n)
所以：
c = me - kn
代入解密方式：
(me - kn)d ≡ m (mod n)
又因為 kn 一定是 n 的倍數，mod n 的值為 0，所以上式可以簡化為：
(me)d ≡ m (mod n)
=>
med ≡ m (mod n)
又因為：
d x e ≡ 1 (mod f(n))
所以：
d x e = h f(n) + 1
代入原式，可以得到：
med = mh f(n) + 1 ≡ m (mod n)
接下來分成兩種情況：
第一種： m 與 n 互質，則根據歐拉定理：
mf(n) ≡ 1 (mod n)
所以原式成為：
mh f(n) + 1 = [(mf(n))h] x m = 1 x m = m ≡ m (mod n)
=> 則原式成立。
第二種： m 與 n 不互質
因為 n = p x q，且 p, q 為質數，所以 m 一定為 k x p 或 k x q。
以 m = kp 為例，又因為 q 是質數，且 m < n = p x q，所以 k 與 q 一定是互質，則根據歐拉定理：
(kp)q-1 ≡ 1 (mod q)
所以下式也會成立：
[(kp)q-1]h(p-1) x kp ≡ kp (mod q)
=>
(kp)(q-1) x (h(p-1)) x kp ≡ kp (mod q)
又因為：
d x e = h f(n) + 1
所以：
(kp)(q-1) x (h(p-1)) x kp = (kp)h(q-1)(p-1)+1 = (kp)ed ≡ kp (mod q)
把 kp (mod q) 展開，可以寫成：
(kp)ed = tq + kp
又因為 (kp)
ed 一定是 p 的位數，所以 (tq + kp) 也一定是 p 的倍數，所以 tq 一定也是 p 的倍數，又 p 與 q 互值，所以 t 一定是 p 的位數，所以：
(kp)ed = tq + kp = t'pq + kp
又因為 m = kp 且 n = pq，代入上式後，得到：
med = t'n + m ≡ m (mod n)
=> 原式成立。
RSA 的加密與解密範例
公鑰： e, n
私鑰： d, n
訊息： m
密文： c
取 p = 3、q = 11，所以 n = 33。
f(n) = (3-1)(11-1) = 20。
又條件為：
ed ≡ 1 (mod 20)
ed = 20k + 1，取 k = 1，令 e = 3、d = 7。
所以公鑰為： (3, 33)，私鑰為： (7, 33)。
假設訊息為 m = 17
加密： (17)
3 (mod 33) = 29
密文 c = 29
解密： (29)
7 (mod 33) = 17
Reference
輕鬆學習RSA加密演算法原理
RSA算法原理（二）
