Chameleon Signature 變色龍簽名入門

傳統電子簽名 (Conventional Digital Signature Algorithms)
傳統的電子簽名方法，例如 DSA / ECDSA 等，
主要可分為公鑰 (Public Key) 、私鑰 (Private Key) 以及簽署 (Signature / Digest) 三個部分。

例如，Alice 可以運用自己的私鑰，透過 DSA，得出一份加上了簽署的文件。
然後，Bob 就可以利用 Alice 的公鑰，透過驗證該簽署，去確認文件是由 Alice 所發出的。

過程中，當 Alice 簽署了這份文件，就代表她認同，電子簽署具有以下所有特性：

• 不可偽造性 (Unforgeability): 因為只有 Alice 擁有私鑰，任何人都不可能輕易偽造一份合法的電子簽名，冒認 Alice 已經認可另一份文件。
• 不可爭議性 (Non-Repudiation): 因為簽名難以偽造，一旦 Alice 簽署過這一份文件，她就不可能否認自己已經簽過。情況就有如銀行過數一樣，一旦成功操作，就不可逆轉。
• 可傳播性 (Transferability): 同一個簽名，不但只 Bob 會相信。只要任何一個人擁有 Alice 的公鑰，只要私鑰沒有外泄，他們都一樣會相信 Alice 已經認可這份文件。

然後，有人就提出了一個問題：有沒有一種電子簽名，可以只保留部分特點？
於是，變色龍簽署 (Chameleon Signature) 應運而生。

---

變色龍電子簽名 (Chameleon Signature Algorithms)
在 1997 年左右，Krawczyk 與 Rabin 發表了一種算法 [1]，
透過在 Hash Function 中加多一個後門 (trapdoor)，達至「簽名不變，內容可篡改」的特性。

聽起上來，「可以篡改內容」的電子簽名，就像「沒有用」的簽名，
但實際上，情況卻正好相反，因為：

• 假設 Alice 擁有 K 的公鑰、私鑰和後門，而 Bob 則只有 K 的公私鑰。當一份文件中包含了 K 簽名，這份文件就有可能是由 Alice 或 Bob 所簽署。所以，如果該文件是由 Bob 利用 K 簽發的話，除了 Alice 以外，沒有其他會相信 Bob：因為其他人會質疑 Bob 發出的文件，即使簽名不變、驗證也成功，但因為 Alice 有後門，所以她有可能偷偷改過內容。換句話說，文件中的簽名的可傳播性 (transferability)，就降低到只有 Alice 與 Bob 之間：只有他們兩個，才知道真相如何。
• 同一個例子，如果 Alice 真的偷偷改過文件內容，到「審判」的一天，Bob 就可以拿出原文件，證明自己清白：因為 Bob 沒有後門，要在短時間內，要找出可以產生同一個簽名的文件，幾乎不可能發生。所以，Bob 就可以用自己原文件，向「審判官」證明是 Alice 動了手腳，與己無尤。可見，這種簽名，仍然有一定程度的不可爭議性 (non-repudiatory)。
• 其實整個系統，論安全性而言，基本上與傳統的 DSA 無異：如果黑客沒有私鑰或者後門，簽名同樣難以偽造 (unforgeable)，所以仍然算得上安全。

---

變色龍簽名系統架構
由於涉及數論 (Number Theory) 及 Discrete Log Arithmetic，為避免鑽得太過深入，
以下只提及一些重要元件，數學推算內容則輕輕帶過。

變色龍散列 / 哈希函數 (Chameleon Hash)

• 假設訊息為 m，修改過的訊息為 m'，目標為：ChameleonHash(m) = ChameleonHash(m')
• 只要達到以上目標，產生的簽名 σ = (CH(m), SK) 就自然不變。

初始化

• 隨機產生後門 x ∈ Zp，並計算出變色龍函數公鑰 K = (g, y) = (g, g^x mod p)
• 排除後門的話，它有點像 HMAC 的概念。

ChameleonHash 計算過程（使用公鑰 K 產生）

• 隨機產生臨時變數 r
• 計算出 CH = (g^my^r mod p) = (g^mg^xr mod p) = (g^m+xr mod p)
• 最後得出 (m, r, CH)

ChameleonHash 驗證過程（使用公鑰 K）

• 由於 r 已經提供，計算方法同上，得出 CH2，對比 CH 即可得出結果。

ChameleonHash 的後門 x 使用過程

• 目標：假設已有 CH 及 m'，利用 x 幫助找出 r' 的值。
• 公式：移項後可得出 r' = [ ( m + xr - m' ) / x ] mod q
• 結果得出 (m', r', CH)，當中即使 m 已經改變，但 r 同時更新，故 CH 可以不變。
• 如果黑客沒有 x，找出新的 r 將會變成 DLP 問題 (Discrete Log Problem)。

將 ChameleonHash 與簽名系統結合

• 初始化：
• 產生 Alice 的 DSA 公私鑰 PK_A 及 SK_A（或稱為私鑰 S）
• 產生 ID，CH 的公鑰 K（或稱為公鑰 R）及後門 x
• 簽名：
• 簽署者擁有 K, PK_A, SK_A
• 使用 K 將訊息 m 進行 Chameleon Hash，得出結果 Digest = (m, r, CH)
• 將結果加上 ID，並以 Alice 的私鑰進行 DSA 簽署，得出 σ = Sign_SKA(CH || ID)
• 最後，整個訊息為 (m, r, σ)
• 驗證：
• 任何人均擁有 K, PK_A
• 收到 (m, r, σ) 後，使用 K 及 r 將訊息 m 進行 Chameleon Hash，得出結果 CH
• 將結果加上 ID，再以 DSA 驗證，得出 Result = Verify_PKA((CH || ID), σ)
• 修改內容：
• 修改者需擁有 K 及 x
• 擁有 x 的人可以選擇修改內容（由 m 變成 m'），並得出新的 r 值（r'）
• 由於 Chameleon Hash 值一致，所以不用重新進行 DSA 簽名
• 結果得出 (m', r', σ)

如是者，系統將有公鑰 (Public Key) 、私鑰 (Private Key) 、變色龍公鑰 (K)、變色龍後門 (Trapdoor x)，以及簽署 (Signature / Digest) 五個部分。

---

變色龍簽名（或散列）的應用

現實生活中，這種簽名的應用仍未普及，以下為一些可行例子：

• 公開記帳系統 (Open Ledger) [2]：
  假設 Alice 想給 Bob 10% 的家財，Alice 可以立下單據，並用 Bob 的給予的變色龍公鑰 K 及自己的電子簽名私鑰 SK 進行變色龍簽名，然後將簽名公開。這樣，每一個外人都可以見證這一個簽名，但卻不會完全相信 Alice 與 Bob 之間的約定（因為 Bob 有後門可以修改內容）。這種方法，可以以保障 Alice 和 Bob 之間的約定，有多人見證，但同時也不會因外人妒忌，而影響自己的人身安全。假若有一天，Bob 真的偷偷改掉內容，Alice 只需向大家公開原單據，就可以證明自己清白。
• 可修改式區塊鏈 (Redactable Blockchain)：
  在一些私人區塊鏈中，給予某方（例如管理層）最大權力，保留可改性，可以防止因為錯誤決定，或者資料問題，而導致整個系統不可用的情況。例如當 GPDR 私隱條例實施後，管理層就可以決定先暫停一下區塊鏈網絡，然後將所有敏感資料，從區塊鏈中擦去，最後重新啟動系統。系統根據 Longest Chain Rule，就會在日後自動抹去舊的區塊鏈，如是者，管理員就不必重新建立整個系統。
• RUSH 5G Handover 系統：
  這篇由 Y. Zhang 發布的論文 [3]，也提到 Chameleon Hash 的應用。
  內容主要是用作 mutual authentication。

---

參考：

[1]: Krawczyk, Hugo, and Tal Rabin. "Chameleon hashing and signatures." Internet-https://pdfs.semanticscholar.org/1c29/4428c76ba7d1d0bb5e1d1bc931138c092453.pdf (1997).

[2]: 哈希（Chameleon Hash）、零知识证明（Zero—Knowledge Proof）和广播加密相关知识, MUZIBing's BLOG, https://muzibing.github.io/2019/10/12/2019.10.12%EF%BC%8885%EF%BC%89/#%E4%B8%80%E3%80%81%E5%8F%98%E8%89%B2%E9%BE%99%E5%93%88%E5%B8%8C%EF%BC%88Chameleon-Hash%EF%BC%89

[3]: Y. Zhang, R. Deng, E. Bertino, and D. Zheng, “Robust and Universal Seamless Handover Authentication in 5G HetNets,” IEEE Trans. Dependable Secur. Comput., vol. 47907, no. c, pp. 1–1, 2019, doi: 10.1109/tdsc.2019.2927664.

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

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。