電子簽名 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

Compile CPABE Toolkit in Mac OS X 10.15.1 (Catalina)

CPABE Toolkit 是一套由 John Bethencourt 開發的 CLI 加密小工具，
主要可以用作演示和了解 CP-ABE 的運作模式。

1. 下載以下兩個 Package:
網站： http://acsc.cs.utexas.edu/cpabe/index.html
主程式： cpabe-0.11.tar.gz
函數庫： libbswabe-0.9.tar.gz

2. 確保已經安裝 OpenSSL, NTL Library, GLib:
OpenSSL 可以通過 brew install openssl 安裝。
GLib 則可以通過 brew install glib 安裝。
NTL 可以由 https://www.shoup.net/ntl/download.html 下載。
NTL 安裝教學： https://www.shoup.net/ntl/doc/tour-unix.html （很簡單的）

3. 編譯及安裝 PBC:
到 https://crypto.stanford.edu/pbc/files/pbc-0.5.14.tar.gz 下載 PBC
執行 tar zxf pbc-0.5.14.tar.gz 解開封包，然後 cd pbc-0.5.14
然後執行  ./configure ，make 和 sudo make install

3. 編譯及安裝 libbswabe:
執行 tar zxf libbswabe-0.9.tar.gz 解開封包，然後 cd libbswabe-0.9 
執行 ./configure CFLAGS="-I/usr/local/opt/openssl@1.1/include" LIBS="-L/usr/local/opt/openssl@1.1/lib"
執行 make CFLAGS="-I/usr/local/opt/glib/include/glib-2.0 -I/usr/local/opt/glib/lib/glib-2.0/include -I/usr/local/include/pbc"
最後 sudo make install

4. 編譯及安裝 cpabe:
執行 tar zxf cpabe-0.11.tar.gz，然後 cd pbc-0.5.14
執行 ./configure CFLAGS="-I/usr/local/opt/openssl@1.1/include -I/usr/local/include" LIBS="-L/usr/local/opt/openssl@1.1/lib -L/usr/local/lib"
最後執行 make 及 sudo make install

如果一切順利，可以 Cmd+N 開一個新的 Terminal，然後查看 which cpabe-setup。
成功的話，會看到它返回 /usr/local/bin/cpabe-setup

5. 小記
在 Catalina 中，這個 Project 需要更改以下兩行：

diff --git a/policy_lang.c b/policy_lang.c
index 7b7672a..2351ea9 100644
--- a/policy_lang.c
+++ b/policy_lang.c
@@ -1942,14 +1942,14 @@ cmp_policy( sized_integer_t* n, int gt, char* attr )

     /* some error checking */

-    if( gt && n->value >= ((uint64_t)1<<(n->bits ? n->bits : 64)) - 1 )
+    if( gt && n->value >= (n->bits ? (((uint64_t)1<<(n->bits))-1) : UINT64_MAX) )
         die("error parsing policy: unsatisfiable integer comparison %s > %llu\n"
                 "(%d-bits are insufficient to satisfy)\n", attr, n->value,
                 n->bits ? n->bits : 64);
     else if( !gt && n->value == 0 )
         die("error parsing policy: unsatisfiable integer comparison %s < 0\n"
                 "(all numerical attributes are unsigned)\n", attr);
-    else if( !gt && n->value > ((uint64_t)1<<(n->bits ? n->bits : 64)) - 1 )
+    else if( !gt && n->value > (n->bits ? (((uint64_t)1<<(n->bits))-1) : UINT64_MAX) )
         die("error parsing policy: trivially satisfied integer comparison %s < %llu\n"
                 "(any %d-bit number will satisfy)\n", attr, n->value,
                 n->bits ? n->bits : 64);

初探 bilinear mapping

Bilinear Map 是不少新型 Pairing-based Cryptography 的基礎概念。
當中雖然有不少難明的數學，但我們仍然可以在用最少數學的情況下理解它。

---

假設有兩個 Cyclic Groups (G1 和 G2)。
它們中間有一個 mapping function，可以找出相對應另一個新的 Cyclic Group (Gt)。
只要輸入 G1 和 G2 的成員值，它就會為你找出對應的 Gt 成員值。
我們先稱這個 mapping function 做 e 。

這個 mapping function e 有一些好用的特性：
假設 u 是 G1 的成員，v 是 G2 的成員，w 是 Gt 的成員，它就可以：
e( u^a, v^b ) = e( u,v )^(ab) = w^(ab)

其實這種 mapping function 有點難找，計算上也未必容易，
所以，我們只考慮那些 efficient 的 bilinear map，並稱它們做 admissible bilinear map。

而在加密學中最好用的 mapping，就是當 G1 = G2 的那一種。
所以在不同的文章，普遍都會假定 G = G1 = G2 。

---

目前有兩大方法可以找出 bilinear mapping function，其中一種是 Weil Pairing，另一種是 Tate Pairing。由於牽涉太多數學和計算機科學，而且不好理解，所以不在此詳述。

---

以下一個例子，證明 bilinear map 其實很好用：

1. Decisional Diffie-Hellman
給定 g, g^a, g^b, g^z, 判斷 a*b = z 。
沒有 bilinear map，你必須先試出 a 和 b 的值，然後才知道。
（按：(g^a)*(g^b) = g^(a+b)，所以真的只有不斷試，沒有捷徑）

但當有 bilinear map，事情就十分好辦：
只要先試一下 e(g^a, g^b) = w^(ab)，再試一下 e(g, g^z) = w^(z)，
只要 w^(ab) 和 w^(z) 的數值相同，就等於 w^(ab) = w^(z)，也就是 ab=z。
（註：w^(ab) 的數值是 Gt group space 的值。數字是什麼也不重要啊，反正相同就可以）

2. Computational Diffie-Hellman
給定 g, g^a, g^b，找出 g^(ab) 。
這種情況，即使有 bilinear mapp 也沒有用。
因為 bilinear map 只會給你另一個 group space 的值，根本沒有什麼用。

這種 CDH 困難，DDH 容易的特性，
正好幫助我們用 bilinear map 來加密資料，同時又不易破解。

---

例如 Joux 的 3 Party Diffie Hellman，正正使用了 bilinear mapping。
首先 Alice, Bob 和 Carol 持有 a, b 和 c，而且他們是三角關係：
（就是 A <---> B, B <---> C, C <---> A 的關係）

1. Alice 和 Bob 交換 g^a 和 g^b ，
2. Bob 和 Carol 交換 g^b 和 g^c ，
3. Carol 和 Alice 交換 g^c 和 g^a ,

此刻，Alice 擁有 a, g^b 和 g^c，Bob 擁有 b, g^a 和 g^c，Carol 擁有 c, g^b 和 g^a 。
所以：
Alice 可以計算出 e(g^b, g^c)^a = (w^(bc))^a = w^(abc)
Bob 可以計算出 e(g^a, g^c)^b = (w^(ac))^b = w^(abc)
Carol 可以計算出 e(g^b, g^a)^c = (w^(ba))^c = w^(abc)

他們三人就可以用 w^(abc) 作為共同金鑰。

後來 Boneh Franklin 的 Identity Based Cryptography 都使用了接近的概念，
於加密時放置了 g^r 和 g^s，並使用 bilinear mapping 找出 w^(rs) 進行加密/解密。

---

小記：因為 bilinear mapping 太難理解， 所以當 1993 年被發現的時候，它主要是用作嘗試破解 ECC (MOV reduction) 的。雖然理論上破解的難度由 infinite 變成 finite，但仍然十分困難。直至 2000 年左右，Joux，Boneh 和 Franklin 等人發現到「正當」的新用途，也就是 3-Way DHKE 和 IBE 。

---

引用參考：

https://people.csail.mit.edu/alinush/6.857-spring-2015/papers/bilinear-maps.pdf
https://www.math.uwaterloo.ca/~ajmeneze/publications/pairings.pdf