Trending News: 完美保密如何閱讀文獻PUF 晶片上的物理不可複製功能FrostyGoop/BUSTLEBERM 工控惡意軟體解析讀墨 Readmoo mooInk Pro 2C 13.3吋 彩色電子書閱讀器 閱讀PDF檔案的應許之機對稱加密函式必要的Confusion以及Diffusion特性亂數產生器 硬體篇環論群之可解性威脅情報指標Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測的問題分類異常檢測的方法評估異常檢測簡介 Anomaly Detection高斯消去法線性向量時間複雜度其他種圖靈機圖靈機消息理論中的熵資訊測量符號相互消息Palo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週六. 2 月 22nd, 2025
Trending News: 完美保密如何閱讀文獻PUF 晶片上的物理不可複製功能FrostyGoop/BUSTLEBERM 工控惡意軟體解析讀墨 Readmoo mooInk Pro 2C 13.3吋 彩色電子書閱讀器 閱讀PDF檔案的應許之機對稱加密函式必要的Confusion以及Diffusion特性亂數產生器 硬體篇環論群之可解性威脅情報指標Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測的問題分類異常檢測的方法評估異常檢測簡介 Anomaly Detection高斯消去法線性向量時間複雜度其他種圖靈機圖靈機消息理論中的熵資訊測量符號相互消息Palo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週六. 2 月 22nd, 2025

中國餘式定理 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})的時間。

Scientia

研究興趣包括密碼理論、密碼工程、安全隱私性、計算複雜度、量子消息與量子計算、硬體安全、網路安全及異常檢測。

Related Posts

完美保密
完美保密

在1978年Ralph C. Merkle提出了一篇”Secure communications over insecure channels”想法之後，人們開始意識到在網路上傳輸資料時其實存在著攻擊者(adversary)在監聽我們的溝通，從而開始發展要混淆傳輸的資料使得在不安全的環境中也可以安心傳輸

Continue reading
對稱加密函式必要的Confusion以及Diffusion特性
對稱加密函式必要的Confusion以及Diffusion特性

在密碼理論研究當中有兩個特性對於安全的密碼系統來說是不可或缺的，分別是混淆(confusion)以及擴散(diffusion)這兩種特性，由Claude Shannon提出利用這兩種特性是想要抵抗密碼分析上被統計出明文的情況，confusion應用在對稱式密碼系統當中想要讓明文以及輸出密文之間的局部關聯性隱藏起來，其實就是用密鑰來對要加密的資料做影響，而diffusion則是要防止攻擊者能夠利用密文的統計性質找出對應的明文。

Continue reading

發佈留言

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

You Missed

1
完美保密
密碼理論
完美保密
2
如何閱讀文獻
文藝分享
如何閱讀文獻
3
PUF 晶片上的物理不可複製功能
硬體安全
PUF 晶片上的物理不可複製功能
4
FrostyGoop/BUSTLEBERM 工控惡意軟體解析
網路安全
FrostyGoop/BUSTLEBERM 工控惡意軟體解析
5
讀墨 Readmoo mooInk Pro 2C 13.3吋 彩色電子書閱讀器 閱讀PDF檔案的應許之機
文藝分享
讀墨 Readmoo mooInk Pro 2C 13.3吋 彩色電子書閱讀器 閱讀PDF檔案的應許之機
6
對稱加密函式必要的Confusion以及Diffusion特性
密碼理論
對稱加密函式必要的Confusion以及Diffusion特性