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