牛油貓的筆記

Sunday, May 24, 2020

CRT 孫子定理應用 2：破解 RSA 內容

簡介
現實生活中，由於 RSA 的公鑰中每一個 Parameters 都會由 OpenSSL 隨機產生，所以 RSA 理論上仍然安全。不過，若果公鑰中有些 Parameters 並不是隨機產生的話，RSA 將會十分危險。以下文章會以 constant e 的情況作為示範。

RSA 算法重温（可查看此互動網頁）
1. 先找出兩個質數的數字 p 和 q，得出 N = p*q 和 r = (p-1)(q-1)
2. 找出 e*d mod r = 1 的任何一個組合，並確保 e 和 r ，以及 d 和 r 均互質 (relatively prime)。
3. 以 C = M^e mod N 加密，並確保 M < N
4. 以 M = C^d mod N 解密，當中可使用 CRT 加速。

破解：若果 e 並非隨機數字呢？
如果有數條 Public Key 使用了相同的 e，然後明文內容 (M) 又是一樣的話，情況就危險了。
首先，因為 e 是公開的，攻擊者如果得到 M^e，可以推算回 M 的值。
假設有三條不同的 Public Keys，它們使用不同的 N，可得：
C₁ = M^e mod N₁
C₂ = M^e mod N₂
C₃ = M^e mod N₃

故此，它又變成了 CRT 的問題：「某數 M^e除 N₁得 C₁，除 N₂得 C₂，除 N₃得 C₃」。
例子：假設 M^e 為 x，e = 3，N₁ = 6，N₂ = 35，N₃ = 143，C₁ = 5，C₂ = 20，C₃ = 125 ：
x ≡ 5 (mod 6)
x ≡ 20 (mod 35)
x ≡ 125 (mod 143)

得出：
N = 6*35*143 = 30030，N_crt1 = 35*143 = 5005， N_crt2 = 6*143 = 858， N_crt3 = 6*35 = 210
x_crt1 ≡ 5005^-1 (mod 6)，x_crt2 ≡ 858^-1 (mod 35)，x_crt3 ≡ 210^-1 (mod 143)

利用 Extended Euclidean Algorithm：
5005 = 6*834 + 1
1 = 5005*(1) + 6(-834)，所以 x_crt1 = 1

858 = 35*24 + 18，移項可得 18 = 858 - 35*24
35 = 18*1 +17，移項可得 17 = 35 - 18*1
18 = 17*1 + 1，移項可得 1 = 18 - 17*1
將移項的算式結合，得出 1 = (858 - 35*24)*2 - 35 = 858*2 + 35(-49)，所以 x_crt2 = 2

210 = 143*1 + 67
143 = 67*2 + 9
67 = 9*7 + 4
9 = 4*2 + 1
將移項的算式結合，得出 1 = 210*(-32) + 143*(47)，所以 x_crt3 = -32 = 143 - 32 = 111

最後得出：
x = [ ( b₁* N_crt1 * x_crt1 ) + ( b₂* N_crt2 * x_crt2 ) + ( b₃* N_crt3 * x_crt3 ) ] mod N
x = [ (5*5005*1) + (20*858*2) + (125*210*111) ] mod 30030 = 2973095 mod 30030 = 125

因為 M^e = 125，已知 e = 3，所以可計算 root(125, 3) = 5 ，從而得知 M = 5。

備註
對於 e 值稍有不同，但 N 相同的 RSA 公鑰，同樣可以使用另一種破解方法，參見此頁。
由於這個方法並非使用 CRT，所以不在本章討論。

小結
這篇文章示範了使用非隨機 Parameter 對 RSA 的危險性。其實，只要 RSA 中的每一個 Parameters 都是隨機產生，加上長度足夠，RSA 暫時來講仍然安全。不過，隨著 Shor's Algorithm 以及量子電腦的出現，RSA 被成功破解的可能性，將會越來越高。所以，我們可以預料，Lattice-based 的 Post-Quantum Cryptography 的發展，將會越來越快。

---

參考：

[1] - https://www.youtube.com/watch?v=15xcBE7MFBg

Friday, May 22, 2020

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。

Monday, May 18, 2020

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*log₂(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/