Chinese Remainder Theorem 孫子定理及應用

簡介

「有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？」
《孫子算經》

古代中國並非只有文學。早在南北朝間，孫子就問過這一條問題：「有一個數字，除三會餘二，除五會餘三，除七會除二。這個數字是什麼？」當然，如果數字不大，你可以選擇以沒有系統的方法推敲答案，或者畫成圖畫。但到底有沒有一個有系統的解法呢？

事實上是有的，而且步驟並不複雜。不過，證明的步驟不算直觀。

---

孫子定理解法

以下用 23 作為例子，解釋計算流程，最後會用公式表達。

步驟一：假設 x 為答案 (23)，如果以 x ≡ b_i (mod n_i) 表示，可以寫成以下公式：

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

步驟二：假設 N = n₁ * n₂ * n₃，而 Ni 則等於不包括自己的相乘結果，也就是：
N = 3*5*7 =105
N₁ = n₂ * n₃ = 5*7 = 35

N₂ = n₁ * n₃ = 3*7 = 21

N₃ = n₁ * n₂ = 3*5 = 15

步驟三：找出 N_i 在 n_i 下的模反元素（multiplicative inverse* ，也就是 N_i^-1），設為 x_i：
35 * x₁ ≡ 1 (mod 3) 或寫作 x₁ ≡ 35^-1 (mod 3) （按：35 跟 x₁ 相乘後再 mod 3 得出 1）
21 * x₂ ≡ 1 (mod 5) 或寫作 x₂ ≡ 21^-1 (mod 5)
15 * x₃ ≡ 1 (mod 7) 或寫作 x₃ ≡ 15^-1 (mod 7)

* 註：multiplicative inverse 的作用是指 multiply a number to undo the multiplication，例如 35 * 1/35 = 1。
在 modular arithmetic 中，我們不考慮小數，同時，mod 的數值會影響其結果：
例如在 mod 3 的情況下，35 的 multiplicative inverse 是 2 (35*2 mod 3 = 70 mod 3 = 1)
但在 mod 34 的情況下，35 的 multiplicative inverse 是 1 (35*1 mod 34 = 35 mod 34 = 1)

對於小數字，我們可以透過窮盡 (exhaustive search) 找出 multiplicative inverse，例如：
35*1 mod 3 = 2 ✗
35*2 mod 3 = 1 ✔ (i.e. the multiplicative inverse of 35 in mod 3 is 2)
21*1 mod 5 = 1 ✔ (i.e. the multiplicative inverse of 21 in mod 5 is 1)
15*1 mod 7 = 1 ✔ (i.e. the multiplicative inverse of 15 in mod 7 is 1)

但對於較大的數字，我們需要用有系統的方法，例如 Extended Euclidean Algorithm：
> 根據 Bezout's Identity，任何數字都可以寫成 a*x + b*y。
> 所以，我們可以故意將 p 與 b 的最大公因數，寫成 gcd(p, b) = p*x + b*y
> 然後，將等式兩邊都 mod P ：
> gcd(p, b) mod p = (p*x + b*y) mod p
> gcd(p, b) mod p = (b*y) mod p
> 如果 gcd(p, b) != 1 的情況下，代表你不可能找到一個相乘後 mod p 可以餘 1 的 y。
> 所以 p 和 b 一定要是 co-prime，而公式則變成 b^-1 mod p = y
> 也就是說，當你肯定 p 和 b 是 co-prime，
> 而你又找到 1 = p*x + b*y，這個 y 就是 multiplicative inverse
> 舉個例子： 1 = 3*(-23) + 35*(2)   （詳細運算方法容後討論）
> 所以 2 就是 35 在 mod 3 下的 multiplicative inverse

步驟四：代入以下公式，找出 x = 23：
x = [ ( b₁* N₁ * x₁ ) + ( b₂* N₂ * x₂ ) + ( b₃* N₃ * x₃ ) ] mod N
x = [ (2*35*2) + (3*21*1) + (2*15*1) ] mod 105
x = 233 mod 105 = 23

對於 x 值較小的情況，使用 CRT 固然沒有靠盲猜快。
但當 x 的數值非常大，而且你有步驟一的資料，CRT 就是唯一的作法了。

---

應用

1. RSA 解碼（可參考此段片）
一般而言，RSA 會公布 Public Key = (e, N)，收藏 Private Key = (d, N)。
當中，Private Key 收藏者知道 N = p*q。
在加密過程中，訊息 M 會經過 M^e mod N = C 變成 C (Ciphertext)，
而解密過程中，C 則會經過 d 次方運算，得出  C^d mod N = M^ed mod N = M。
（當中由於 d 屬於 e 在 λ(N) = gcd(p − 1, q − 1) 中的 multiplicative inverse，故兩者可以互相抵消）

雖然理論上，解密方可以用以上公式算出 M，
可是實際操作上，由於 N 的數值實在太大，計算 mod 的時間將會非常長，
所以，我們可以利用倒轉的 CRT，加速運算過程：

以 e = 37, d = 11613, N = 21829, N = p*q = 83*263 為例子：
假設收到 C = 17639，解密方程將為 M = 17639¹¹⁶¹³ mod 21829
然後根據 CRT 可以拆成兩條公式：

• M ≡ 17639¹¹⁶¹³ (mod 83)
• M ≡ 17639¹¹⁶¹³ (mod 263)

然後對於每一條公式，因為 Ni 值已經變小，所以可以再進行簡化：

• M ≡ 17639¹¹⁶¹³ mod 83 = (17639 mod 83)¹¹⁶¹³ mod 83 = 43¹¹⁶¹³ mod 83
• M ≡ 17639¹¹⁶¹³ mod 263 = (17639 mod 263)¹¹⁶¹³ mod 263 =18¹¹⁶¹³ mod 263

這個時候，可以再利用 Euler Theorem (φ(83) = 82, φ(263) = 262) 再簡化（非必要）：

• M ≡ 43¹¹⁶¹³ mod 83，11613 mod φ(83) = 51，所以 M = 43⁵¹ mod 83 = 58 mod 83
• M ≡ 18¹¹⁶¹³ mod 263，11613 mod φ(263) = 85，所以 M = 18⁸⁵ mod 263 = 44 mod 263

故此可得出以下公式：

• M ≡ 58 mod 83，也就是說，M 在 mod 83 的情況下，會得出 58
• M ≡ 44 mod 263， 也就是說，M 在 mod 263 的情況下，會得出 44

所以，這個問題又變成了 CRT 的問題：

• M ≡ 58 (mod 83)
• M ≡ 44 (mod 263)

運用上一部分提供的答法，可以得出：

• N = 83*263 = 21829, N1 = 263, N2 = 83
• x₁ ≡ 263^-1 (mod 83) = 6
• x₁ ≡ 83^-1 (mod 263) = 244
• x = [ (58*263*6) + (44*83*244) ] mod 21829 =  307

故此，M 為 307。

2. 對於固定 n 值的 RSA 進行破解

3. EAP-DDBA 的密碼驗證

---

小結
CRT 在 RSA 和其他加密學有很多不同的應用，所以認識 CRT 對了解加密概念十分有幫助。
之後會再詳細討論其他驗證用的應用，以及 CRT 如何幫助破解 RSA。