中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性

目錄

簡介

中國餘式定理Chinese Remainder Theorem(CRT)在密碼理論當中屬於重要的概念,尤其在RSA密碼系統裡也扮演重要的角色。

中國餘式定理

CRT主要想解決的問題是找到共同的數針對不同的模運算式,這種在像是RSA密碼系統計算合成數\(n\)取決於\(p\)及\(q\)兩個質數很有幫助。

對於\(n_{1}, n_{2}, \cdot\cdot\cdot\cdot,n_{m}\)以及\(r_{1},r_{2},\cdot\cdot\cdot\cdot,r_{m}\),\(n_{i} \perp n_{j}, i \neq j\),能夠組成各自的聯立方程式:

\(x \equiv r_{k} \, (mod \, n_{k})\, , 1 \leq k \leq m\)

透過上述的每一個聯立方程式可以找出\(x\):

\(x = [r_{1}N_{1}(N_{1}^{-1} \, mod \, n_{1})+\cdot\cdot\cdot+r_{m}N_{m}(N_{m}^{-1} \, mod \, n_{m})] \, mod \, N\)

其中\(N = n_{1}n_{2} \cdot\cdot\cdot n_{m}\)以及\(N_{i} = N/n_{i}\)

舉例:

\(n_{1} = 3, n_{2} = 4, n_{3} = 7, r_{1} = 1, r_{2} = 3, r_{3} = 1\)可以組成下列的聯立方程式:

\(\begin{cases}
x \equiv 1 \, (mod \, 3)\\
x \equiv 4 \, (mod \, 4)\\
x \equiv 1 \, (mod \, 7)
\end{cases}\)

並且\(N = n_{1}n_{2}n_{3} = 3*4*7 = 84, N_{1} = N/n_{1} = 84/3 = 28, N_{2} = N/n_{2} = 84/4 = 21, N_{3} = N/n_{3} = 84/7 = 12\)

接著找各個\(N_{i}\)的反元素,

\(N_{1}^{-1} = 28^{-1} \, mod \, 3 \equiv 1 \, mod \, 3\\ N_{2}^{-1} = 21^{-1} \, mod \, 4 \equiv 1 \, mod \, 4\\N_{3}^{-1} = 12^{-1} \, mod \, 7 \equiv 3 \, mod \, 7 \)

這樣就能可以找到\(x\):

\(x = (1 \times 28 \times 1 + 3 \times 21 \times 1 + 1 \times 12 \times 3) \, mod \, 84 \equiv 43 \, (mod \, 84)\)

同構 Isomorphism

符合CRT的聯立方程式具有同構的特性,假設\(Z_{n} = \{0, 1, 2,\cdot\cdot\cdot\cdot,n-1\}\)以及\(n_{1},n_{2},\cdot\cdot\cdot\cdot,n_{m}\),\(n_{i} \perp n_{j}, i \neq j\)

\(Isomorphism: Z_{n} \to Z_{n_{1}} \times Z_{n_{2}} \times \cdot\cdot\cdot \times Z_{n_{m}}: \\ \psi(x) \to (x \, mod \, n_{1}, x \, mod \, n_{2}, \cdot\cdot\cdot, x \, mod \, n_{m}) \)

使用CRT找到\(x\)透過\(\psi^{-1}(x_{1},x_{2},\cdot\cdot\cdot,x_{m})\)

舉例:

\(n = pq = 3 \times 5 = 15\),可以看成\(Z_{15} = Z_{3} \times Z_{5}\)

可以看成\(0 \to (0, 0)\\2 \to (2, 2) \\ 7 \to (1 ,2)\\ 10 \to (1, 0)\)等等

\((7 + 10) \, mod \, 15 = 2\)可以看成\((1, 2) + (1, 0) = (2, 2) \to 2\)

或者\((7 \times 10) \, mod \, 15 = 10\)可以看成\((1, 2) \times (1, 0) = (1, 0) \to 10\)

前面提到主要對RSA有用就是因為有同構的特性:

計算\(x = a^{b} \, mod \, pq\),\(pq\)可以想成\(n\),代表\(n\)的群來自\(Z_{n} \to Z_{p} \times Z_{q}\),以及\(k = len(pq)\)的長度。

\(a^{b} \, mod \, n \\ \to (a^{b} \, mod \, n \, mod \, p, a^{b} \, mod \, n \, mod \, q)\\ = (a^{b} \, mod \, p, a^{b} \, mod \, q) \\ = ((a \, mod \, p)^{b \, mod \, p-1} \, mod \, p, (a \, mod \, q)^{b \, mod \, q-1} \, mod \, q)\\ = (x_{1}, x_{2})\)

所以\(a^{b} \, mod \, n = \psi^{-1} (x_{1}, x_{2})\),計算\(a^{b} \, mod \, n\)需要\(O(k^{3})\)的時間。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *