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。

Merkle Tree 和 Bitcoin 的關係

Merkle Tree 入門

要確保整串非常長的資料（例如區塊鏈）的完整性，理論上，我們可以有幾種方法：

• 直接將整條資料 Hash 成一個 hash value
  
• 將資料斬成一個一個區塊 (block)，然後下一個 block 記低上一個 block 的 hash value
• 將資料斬成一個一個區塊 (block)，然後算出每個 block 的 hash value，最後以 binary tree 形色不斷向上計算，直至得到最後一個 hashed value，又稱為 Merkle Root

Merkle Tree 指就是第三種方法。當 block 數量為雙數時，Merkle Root 可以這樣得出 [1]：

簡單而言，就是計算 L1 - L4 的 Hash，得出 H(L1) - H(L4)，

然後計算 H0 = H(H(L1) || H(L2)) 和 H0 = H(H(L3) || H(L4))，

最後計算 Merkle Root = H(H0 || H1)。

當 Block 數為單數時，以上圖為例，假設只有 L1-L3，我們就可以：

假設有一個 block L4 = L3，

然後故技重施，最後得出 Merkle Root。

當 Block 數為單數，並導致上一層也是單數，我們也同樣故技重施，直至單數消失。

這種架構，對於本身資料結構已經是 linked list 的區塊鏈 (Blockchain) 來講特別方便。

因為不需要花額外的工作處理資料切割，就能直接用這個方法，確保資料完整性。

而且當區塊鏈不斷變長，我們也不需要重新計算舊的區塊，變相可以刪掉舊區塊節省空間。

（例如當加入 L5， 我們並不需重新計過 H(L1) ~ H(L4)，也可以找到 Merkle Root）

Merkle Tree 在 Bitcoin 的應用

作為第一個引人注目的 Blockchain 應用，Bitcoin 中同樣引入了 Merkle Tree，

而它的出發點同樣是想保護整條 Block 的完整性。

我們可先看一下 Bitcoin 的 header 架構 [2]：

Bytes	Name	Data Type	Description
4	version	int32_t	The block version number
32	previous block header hash	char[32]	A SHA256(SHA256()) hash in internal byte order of the previous block’s header. This ensures no previous block can be changed without also changing this block’s header.
32	merkle root hash	char[32]	A SHA256(SHA256()) hash in internal byte order. The merkle root is derived from the hashes of all transactions included in this block, ensuring that none of those transactions can be modified without modifying the header.
4	time	uint32_t	The block time is a Unix epoch time when the miner started hashing the header (according to the miner).
4	nBits	uint32_t	An encoded version of the target threshold
4	nonce	uint32_t	An arbitrary number miners change to modify the header hash in order to produce a hash less than or equal to the target threshold.

當中可見，Previous Block Header Hash 是用來確保上一個 block 的合法性。理論上，我們如果要確定任何一個 block 是否合法，最簡單的方法，就是用這個欄目，一直追溯直至第一個 block（又稱作 Coinbase）即可。但這種做法，將會耗費大量時間，所以理論上可行，實際上卻十分困難。

Bitcoin 的發明者 Satoshi Nakamoto 似乎一早就發現這個情況，所以他增加了 Merkle Root Hash 這個項目。自此，如果你要確認某一個 block，你只需要重新找出該 block 的 H(block)，然後向上推演，計出 Merkle Root，再比對 chain head 中的 Merkle Root Hash 是否相等即可。根據 [3] 所指，要推算任何一個 block，理論上只需要 2*log2(N) 次計算，變相快速有效得多。

Merkle Tree 其他應用

Merkle Tree 提供一種便捷的驗證方法，所以一直有不少地方均用到。

例如 Tor，Git，SEMUD [4] 等等。

---

參考：

[1] - https://en.wikipedia.org/wiki/Merkle_tree#/media/File:Hash_Tree.svg

[2] - https://bitcoin.org/en/developer-reference#block-headers

[3] - Mastering Bitcoin by Andreas M. Antonopoulos - https://www.oreilly.com/library/view/mastering-bitcoin/9781491902639/ch07.html

[4] - http://ieeexplore.ieee.org/document/8264846/

Schnorr Signature 簡介

Schnorr Signature 的動機

提到電子簽名，最常見的包括以 RSA 為基礎的 RSA，或者以橢圓曲線為基礎的 ECDSA。

這些算法雖然普遍，但普遍來講因為算法複雜，耗時也比較高。

Schnorr Signature 就是基於這個背景下產生的：由於它算法簡單易明，速度也比較快。

Schnorr Signature 的算法簡介

1. 初始化：

• 首先產生一個 Schnorr Group Parameters，得出 generator (g) 和 prime order (q)。
• 選取一個 cryptographic hash function H。
  

2. 產生 Key：

• 隨機產生一個 x，這個 x 必需與 q 是 relatively prime，這個將成為 Private Key。
  
• 運用 y = g^x 產生 y，這個成為 Public Key。

3. 簽名：

• 隨機產生一個 k，這個 k 必需與 q 是 relatively prime
• 計算 r = g^k
• 計算 e = H( r || M ) 或可寫作 H ( g^k || M )，當中 M 是訊息，|| 指組連 (concatenate)
• 計算 s = k - xe，或可寫作 s = k - x*H( g^k || M )
• 公布 (s, e) 出去，也可以寫成 ( k-xe, e )，這個就是 Schnorr Signature 簽名 (digest)。 
  

PS：如果 prime order 是小於 2^160 (160 bit) 的話，基本上 s 和 e 各佔不多於 40 bytes (320 bits)。

PS2：過程當中，簽署方必須小心，k 的數值必須每次不同，否則如果有兩條不同 M，其他人就可以透過得出的 s 和 s'，透過相減約走 k，繼而找出 x：

• s - s' = (k-xe) - (k'-xe') = (k-k') - x(e-e') = 0 - x(e-e')
• 因為 e' 和 e' 均是由相同的 g^k 疊加已知的 M 或 M' 再 hash 而成，
  所以只要不斷撞，很大機會能找回 concat 的 g^k 值到底是什麼，最後找回 x。
  

4. 驗證簽名：

• 手持 Public Key y = g^x
• 計算 r_verify = g^s * y^e = g^(k - xe) * g^(xe) = g^( k - xe + xe ) = g^k
• 計算 e_verify = H ( r_verify || M ) = H ( g^k || M )
• 如果 e_verify 與 e 相等，簽名則為有效。

Schnorr Signature 的缺點

由於它計算快捷，普遍來講，相對其他複雜的算法，它更易撞到，也就是更容易破解。

所以，一般而言，密碼學家認為它需要比其他算法長 4 倍，才能達到相近的強度。例如 NIST 256-bit 來講，Schnorr Signature 最少需要 1024 bit 簽名長度，才能達到 ECDSA 的 ECDSAwithSHA256 (256 bit) 簽名相等的安全性。

（也有其他新的論文提到了 Short Schnorr Signature，它的長度能減少至 3t 右右。）

基於橢圓曲線 (Elliptic Curve) 的 Schnorr Signature

有一種算法 EdDSA，正正使用相類似的原理運作。

它採用特殊的曲線，達至相類似的效果。而且廢除了隨機產生的 k，減低密碼外流的風險。

---

參考：

[1] - https://en.wikipedia.org/wiki/Schnorr_signature