# 從餘數運算到 RSA 加密演算

## 背景

RSA 是現代網際網路應用中最重要的加密演算法之一，運用非對稱加密的方式解決密鑰交換問題。在通訊過程中，比如 A 生成一對密鑰組合，包含公鑰和密鑰，而用公鑰加密的密文，只能由密鑰解開，所以要跟 A 秘密通話，就用 A 給的公鑰來加密，這個消息也只有 A 才能知道。至於怎麼確定公鑰是來自 A 呢？則是數位憑證的範疇。

這對公鑰密鑰看似很神奇，其實加解密手法很簡潔，簡潔到讓人感嘆數學之美:
> 用公鑰(n, e)加密：明文^e^ ≡ 密文 (mod n)
> 用私鑰(n, d)解密：密文^d^ ≡ 明文 (mod n)

上述表達式是同餘式，也就是 `≡` 兩邊 mod n 是相等的。mod 運算就是取被除數 / 除數得到的餘數，運算符是 `%`。比如 `5 % 3 = 2`。所以上式也可表達成:
> 用公鑰(n, e)加密：密文 = 明文^e^ % n
> 用私鑰(n, d)解密：明文 = 密文^d^ % n

推導 RSA 之前，我們需有相關背景知識，分別是中國餘數定理、模運算規則，和費馬小定理。

## 中國剩餘定理

Chinese Remainder Theorem，簡稱 "CRT"。
YouTube: [孫子定理是什麽？韓信點兵又是怎麽回事？](https://www.youtube.com/watch?v=Ope18waS1GU)

[b431. 中國餘數](http://morris821028.github.io/2015/07/10/zj-b431/)

中國剩餘定理有個很實際的應用，叫做 [Mignotte's scheme](http://cryptowiki.net/index.php?title=Mignotte%27s_scheme)，就是分別給 5 個特工一組密文，要解開此密文，必須有 3 名特工聚一起才行，能防止一個特工擁有密文的全部，或者某個特工被抓而解不開密文。

## 模運算規則

從 RSA 的加解密公式就看到使用模運算，我們需要一併理解模運算的特性。

闡述之前，先看我們以前玩過的數學小魔術：「你心想三位數，乘以 13，告訴我乘積的後三位數，我就能知道你想的是哪個數！」
* 假如你想的是`233`，接著你把 `233` 乘上 13 得到 `3029`，所以你告訴我 `029`
* 我只要把 `29 * 77 = 2233`，積的後三位數 `233` 就是你心想的數

這裡就有點非對稱的影子: `(1000, 13)` 是公鑰; `(1000, 77)` 是私鑰。原理是運用模運算的規律：
1. 若 `a ≡ b (mod p)`，則對於任意的 `c`，都符合 `(a * c) ≡ (b * c) (mod p)`
2. `(a * b * c) % p ＝ ((a * b) % p * c) % p`

我們來分解:
> 13 * 77 = 1001 => 1001 % 1000 = 1
> => 1001 ≡ 1 (mod 1000)
> => a * 1001 ≡ a (mod 1000)

就是說任何數乘以 1001 除以 1000 得到餘數是本身。因此：
> (a * 1001) % 1000 = (a * 13 * 77) % 1000 = ((a * 13) % 1000) * 77) % 1000

不難發現，我們不用知道 `a * 13` 的積，而是知道它除以 1000 的餘數即可，因為反正最後都是要模 1000，那事先拿一部分來模 1000 並不影響結果。跟除法類似，兩個數乘積除以另一個數，那事先用一個乘數除以除數，得到的值再乘以另一個乘數再除，並不影響結果。這個思想，也是 RSA 用來當被模數過大時，改善程式碼效率的演算法。

還有個規律需要推導：
a^ed^ % p ＝ (a^e^ % p)^d^ % p

把 a^e^ 看成一個整體，也就是求 d 個 a^e^ 相乘再模 p，從上可知，事先用乘數模 p 並不影響結果，也就是每個 a^e^ 先模 p，一共有 d 個，相乘，再模 p 跟原來是一樣的。

## 費馬小定理

如果 n 是個質數，對於任意的 a 有 a^n^ - a = n 的倍數。關於費馬小定理的證明，有一種很具象的證明，即「循環移位」的方法。

費馬小定理還有一種說法：對任意 a，隨著 i 的增加，a^i^ % n 呈現出長度為 n-1 的週期性，n 為質數。
> a^n^ - a ＝ n的倍數 => a^n^ - a ≡ 0 (mod n)
> => a^n^ % n = a % n

也就是說 a^1^ % n, a^2^ % n, ... 到 a^n^ % n，餘數又回到原點。而從上節說到的模運算可知道:
> (a * a) % n ＝ ((a % n) * a) % n

也就是說 a^i^ % n 是由 a^i-1^ % n 決定，這樣環環相扣還能回到原點，就是說明要循環啦，以 n-1 為週期在循環。這個規律正是 RSA 的基礎。

上面說到 n 為質數，如果 n 不是質數呢？假設 n ＝ p * q, p, q都是質數，對任意 a，隨著 i 的增加，a^i^ % n會呈現怎樣的週期性？根據費馬小定理，a^i^ % p 的循環週期為 p - 1, a^i^ % q 的循環週期為 q - 1。再回顧下上面的中國剩餘定理，pq 互質，在一個循環週期內，a^i^ 可由數對 (a^i^ % p, a^i^ % q) 判定，也就是數對 (a^i^ % p, a^i^ % q) 存在週期為 (p-1)(q-1) 的循環，可得出 a^i^ 也存在週期為 (p-1)(q-1) 的循環，必然 a^i^ % n 的循環週期也是 (p-1)(q-1)。

總結一下，若 n 為質數，則 a^i^ % n 的循環週期是 n-1; 若 n 是兩質數 p, q 的乘積，則 a^i^ % n 的循環週期是 (p-1)(q-1)。

## 推導RSA

把加密公式代入解密公式：明文 ＝ (明文^e^ % n)^d^ % n，即明文 ＝ 明文^ed^ % n，這很有可能是明文的 i 次方模 n 的餘數在以 ed - 1 為週期循環，或者有比 ed - 1 更小的週期，順著這個想法，我們看看怎麼構造 e, d, n 使其成立。

用費馬小定理和中國剩餘定理給過證明的：給出兩質數 p, q，其乘積為 n，那麼隨著 i 的增加，明文 i % n 呈現週期為 (p-1)(q-1) 的循環。

我們最終是要得到明文，所以取明文的 1 次方，那麼有：
> 明文 % n ＝ 明文^h(p-1)(q-1)+1 % n^

我們不能暴露 pq，不然密鑰就沒有意義，所以這裡嘗試構造出
> ed ＝ h(p-1)(q-1) + 1，也就是 ed ≡ 1 (mod m), m = (p-1)(q-1)

至此，RSA 的實際作用已表明，就是模運算規則有非對稱性，以及餘數有週期性。

至於怎麼找到這對 ed 呢？直接上定理簡單說，這裡的術語是稱作 d 是 e 的模反元素，由 Euler 定理:
> a^φ(n)^ ≡ 1 (mod n)
> 正整數 a, n 互質

可證明。其中 Euler 函數 φ(n) 是求 1 到 n 的範圍內，有多少個數與 n 互質，這個值也是 a^i^ % n 的餘數序列有多長的週期的解。從小於 m 的數裡頭找到一個與 m 互質的，作為 e，e 是肯定能找到的。那麼:
> e * e^φ(n)-1^ ≡ 1 (mod n)

也就是 d 必然存在。

我們回過頭來看看密鑰對的生成步驟做個對比。
1. 隨機選擇兩個不相等的質數 p 和 q;
2. 計算 p 和 q 的乘積 n;
3. 計算 p - 1 和 q - 1 的乘積 m
4. 隨機選個整數 e，e 與 m 要互質，且 0 < e < m;
5. 計算 e 的模反元素 d;
6. n，e 組成公鑰，n, d 組成私鑰;

數學裡很多高深莫測的東西往往異常簡潔。

延伸閱讀:
* [RSA 非對稱加密演算法: 利用中國剩餘定理加速](http://jianiau.blogspot.com/2014/05/rsa-decrypt-with-crt.html)
* [餘數運算](http://www.csie.ntnu.edu.tw/~u91029/Residue.html)
* [同餘與其應用](http://ir.nptu.edu.tw/bitstream/987654321/18754/1/005.pdf)
* [RSA 加解密原理](https://ithelp.ithome.com.tw/articles/10198936)