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.

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

電子簽名 Digital Signature: ECDSA

現實中常遇到的一個問題：
假設有兩個人 Alice 和 Bob，他們不能互相見面，只能透過不同的中間人轉發訊息。
可是，他們想確認接收到的訊息，真的是由對方發出的。

在這個情況下，因為每個人都有 Bob 的 Public Key (PKBob)，
所以即使 Bob 收到 Enc({I am Alice}, PKBob)，也不能代表這句是由 Alice 發出。

面對這種情況，有兩種解決方法。

第一種是 Alice 和 Bob 先互相見面，交換機密，然後 Alice 和 Bob 之間可以透過不斷試探對方（例如問機密中有沒有某個字），來確認對方的身份。這種做法叫 ZKP (Zero Knowledge Proof)，雖然聽起來簡單，但操作起來並不容易。因為要互相見面一次，而且試探過程不能只問一條問題。所以，要透過問多條問題，還要小心選題，才能 99.999...% 確保對方身分。

第二種方法，就是利用電子簽名，就比較常用。由於每個人都會儲起自己的 Private Key，所以如果我可以利用自己的 Private Key 為文章做些記號，然後讓對方用我的 Public Key 驗證這個記號，對方就能 100% 相信，文章是我寫的（因為理論上只有我才有自己的 Private Key）。這種方法既可以善用 Public / Private Key，又可以確保 non-repudiation，所以一直都十分受歡迎。

---

ECDSA (Elliptic Curve Digital Signature Algorithm) 的算法：

公開參數 Public Key Parameters:
α, β (elliptic curve), p (large prime), G (elliptic curve base point), n (order), h (co-factor)
公鑰 Public Key： d_a
私鑰 Private Key：d_a • G
訊息： m

簽名過程：
先選一個 random k (under integer with order n (ℤn))，
計算出 P = k • G = (x_p, y_p)。
再計算 r = x_p mod n 和 s = [ k^(-1) * (m + r * d_a) ] mod n。
最後產生 output signature = (s, r)。

驗證過程：
先計算 u_1 = ( s^(-1) * m ) mod n
再計算 u_2 = ( s^(-1) * r ) mod n
得出 P = u_1 • G + u_2*(PK) = u_1 • G + u_2*d_a • G
= {[( s^(-1) * m ) + ( s^(-1) * r  * d_a )] mod n } • G
= {[ (s^(-1)) * ( m + r  * d_a )] mod n } • G
= {[ k^(-1) * (m + r * d_a) * ( m + r  * d_a ) ] mod n } • G = (x_p, y_p)
如果 r = x_p mod n，則代表驗證成功。

詳細證明的話，需用到 elliptic curve 的 multiplication / addition 公式，
由於比較繁複，所以到有需要就再補充吧。

---

參考：
[1] https://www.maximintegrated.com/en/design/technical-documents/tutorials/5/5767.html
[2] Chapter 13.5 - Elliptic Curve Digital Signature Algorithm - (P.430), CRYPTOGRAPHY AND NETWORK SECURITY PRINCIPLES AND PRACTICE SEVENTH EDITION, William Stallings