從餘數運算到 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: 孫子定理是什麽？韓信點兵又是怎麽回事？

b431. 中國餘數

中國剩餘定理有個很實際的應用，叫做 Mignotte's scheme，就是分別給 5 個特工一組密文，要解開此密文，必須有 3 名特工聚一起才行，能防止一個特工擁有密文的全部，或者某個特工被抓而解不開密文。

模運算規則

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

闡述之前，先看我們以前玩過的數學小魔術：「你心想三位數，乘以 13，告訴我乘積的後三位數，我就能知道你想的是哪個數！」

假如你想的是233，接著你把 233 乘上 13 得到 3029，所以你告訴我 029
我只要把 29 * 77 = 2233，積的後三位數 233 就是你心想的數

這裡就有點非對稱的影子: (1000, 13) 是公鑰; (1000, 77) 是私鑰。原理是運用模運算的規律：

若 a ≡ b (mod p)，則對於任意的 c，都符合 (a * c) ≡ (b * c) (mod p)
(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ⁿ - a = n 的倍數。關於費馬小定理的證明，有一種很具象的證明，即「循環移位」的方法。

費馬小定理還有一種說法：對任意 a，隨著 i 的增加，aⁱ % n 呈現出長度為 n-1 的週期性，n 為質數。

aⁿ - a ＝ n的倍數 => aⁿ - a ≡ 0 (mod n)
=> aⁿ % n = a % n

也就是說 a¹ % n, a² % n, … 到 aⁿ % n，餘數又回到原點。而從上節說到的模運算可知道:

(a * a) % n ＝ ((a % n) * a) % n

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

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

總結一下，若 n 為質數，則 aⁱ % n 的循環週期是 n-1; 若 n 是兩質數 p, q 的乘積，則 aⁱ % 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ⁱ % n 的餘數序列有多長的週期的解。從小於 m 的數裡頭找到一個與 m 互質的，作為 e，e 是肯定能找到的。那麼:

e * e^φ(n)-1 ≡ 1 (mod n)

也就是 d 必然存在。

我們回過頭來看看密鑰對的生成步驟做個對比。

隨機選擇兩個不相等的質數 p 和 q;
計算 p 和 q 的乘積 n;
計算 p - 1 和 q - 1 的乘積 m
隨機選個整數 e，e 與 m 要互質，且 0 < e < m;
計算 e 的模反元素 d;
n，e 組成公鑰，n, d 組成私鑰;

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