---
lang: zh-tw
tags: NTHU, Notes, Cryptocurrency
date: 20210513
robots: noindex, nofollow
license: GPL-3.0
---

ECDSA Signature Generation & Verification
===
Introduction
---
- Elliptic Curve Digital Signature Algorithm (ECDSA)
- EC 版本的 DSA
- 基於 ElGamal 簽章系統做修改得來的
- EdDSA 是變形版的 ECDSA，加速計算的效率且不犧牲安全性，例如：Ed25519
- 一般來說，公認 ECDSA 所需的 bit length 是兩倍於 security level
- 例如：希望達到 80-bit security level 需要至少使用 160-bit ECDSA
- n-bit security level 意旨攻擊者機率上需要嘗試 $2^n$ 次才能猜出 private key

Notation
---
- 情境
- Alice 要傳送訊息給 Bob，Bob 要驗證訊息的正確性
- 符號定義
- $E(\mathbb{F}_p)$：The *set of points* belong to the elliptic curve $E$ over $\mathbb{F}_p$
- $G$：The base point of an EC.
- $n$：The (additive) **order** of the base point $G$
- $d$：Alice's private key
- $Q$：Alice's public key
- *msg*：The message to send
- *HASH*( )：A cryptographic hash function (e.g., SHA-256, SHA-3)

Private Key and Public Key
---
- $d$
- Private key
- A **pseudorandom** integer scalar ${\in}\ [1,\ n-1]$
- $Q$
- Public key
- $Q=G+G+{\dots}+G=[d]G\ {\in}\ E(\mathbb{F}_p)$

Signature Generation
---
Alice 利用 $d$ 和 $Q$ 針對 *msg* 製作 ECDSA signature

1. 利用「魔法」得到 pseudorandom number $k\ {\in}\ [1,\ n-1]$ 當作 ephemeral key
2. 計算 $[k]G=(x_1,\ y_1)\ {\in}\ E(\mathbb{F}_p)$
- 有的文件在這邊多一步「convert $x_1$ to an integer $\overline{x_1}$」
- 用意是把 $x_1$ 從 field element over $\mathbb{F}_p$ 轉換成一般的「數字」
- 例如：over $\mathbb{F}_{2^m}$ 的時候就需要把 bit string $x_1$ 轉成 decimal $\overline{x_1}$
3. 得到簽章的前半部分 $r={x_1}\mod{n}$
- 若 $r=0$，則重回第 1 步從頭來過
- 在敘述其它功能的時候，可能會多一個記號 $R=(x_1,\ y_1)=[k]G$
4. 計算 $k^{-1}\mod{n}$
- 乘法反元素可以用 Euclidean algorithm 求得
6. 計算 *HASH*( *msg* ) 並把結果從 bit string 轉換為整數記做 $e$
7. 得到簽章的後半部分 $s=k^{-1}(e+dr)\mod{n}$
- 若 $s=0$，則重回第 1 步從頭來過
8. 最終的簽章就是合併兩半部分 $(r,\ s)$

- 注意事項
- 因為 $r$ 和 $s$ 都 ${\in}\ \mathbb{Z}_n$（$n$ 是 $G$ 的 order），所以簽章結果會是 private key $d$ 的兩倍長
- 第 1 步的「魔法」很重要，每次簽章都必須使用不同的 $k$，否則可以反推出 private key $d$
- $(r,\ -s)$ 也是合法有效的簽章，同樣可透過 verification 步驟驗證正確性
- 因為 $r={x_1}\mod{n}$ 是同餘關係，也就是 $r=x_1+tn$ where $t\ {\in}\ \mathbb{Z}$，所以有機會出現選到某個不同的 $k'$ 使得 $[k']G=(x_1+{\square}n,\ \dots)\ {\in}\ E(\mathbb{F}_p)$，此時同樣具有 $r=x_1\mod{n}$；雖然看起來其扯無比，不過這與 public key recovery 步驟有關

Signature Verification
---
Bob 收到四樣東西：$Q$、*msg*、$r$、$s$；若 Bob 執行以下步驟出現失敗，則直接認為收到不合法簽章

0. 驗證 $Q\ {\in}\ E(\mathbb{F}_p)$ 且 $Q\ {\neq}\ \mathcal{O}$
1. 驗證 $r$ 和 $s$ 都 ${\in}\ [1,\ n-1]$
2. 計算 *HASH*( *msg* ) 並把結果從 bit string 轉換為整數記做 $e$
3. 計算 $w=s^{-1}\mod{n}$
4. 計算 $u_1=ew\mod{n}$ 和 $u_2=rw\mod{n}$
5. 計算 $X=[u_1]G+[u_2]Q\ {\in}\ E(\mathbb{F}_p)$，然後我們記做 $X=(x_1,\ y_1)$
6. 檢查 $X\ {\neq}\ \mathcal{O}$，然後取 $v=\overline{x_1}\mod{n}$
- 和 [Signature Generation](#Signature-Generation) 第二步的邏輯相同
- 把 $x_1$ 從 field element over $\mathbb{F}_p$ 轉換成一般「數字」$\overline{x_1}$
7. 檢查 $v=r$

- 注意事項
- 因為計算反元素很耗時，所以最高效的實作應該只計算一次 $s^{-1}\ \mod{n}$
- 利用 Shamir's trick 可以讓 $[u_1]G+[u_2]Q$ 的求解快一點
- 其實 Alice 不必傳送 $Q$，利用[方法](http://www.secg.org/sec1-v2.pdf#subsubsection.4.1.6)可以透過 *msg*、$r$、$s$ 還原出 public key
- Correctness of the algorithm
- $[u_1]G+[u_2]Q$
- $=[ew]G+[rw]\Big([d]G\Big)$
- $=[we+wdr]G$
- $=[s^{-1}e+s^{-1}dr]G$
- $=[\Big(k^{-1}(e+dr)\Big)^{-1}(e+dr)]G$
- $=[k(e+dr)^{-1}(e+dr)]G=[k]G$
- $\Longrightarrow$ Both of $r$ and $v$ are the x-coordinate of the $[k]G$.

Public Key Recovery
---
在傳輸頻寬非常珍貴的情況下（e.g., blockchain txn payload），其實 Alice 不需要每次都把自己的 public key $Q$ 附在 signature 當中，Bob 可以透過 *msg*、$r$、$s$ 反推得到，接著 Bob 再用其他方法查詢並比對反推結果是否吻合 Alice 事前公告的 public key

1. 利用 $r$、$(r+n)$、$(r+2n)$、、、 over $\mathbb{F}_p$ 推算出一堆可能的 $R$ 點們
- 若 $[n]R\ {\neq}\ \mathcal{O}$，則把「這種點」排除掉、不要放進下一步
- 原因請見 [Signature Generation](#Signature-Generation) 的注意事項
2. 計算 *HASH*( *msg* ) 並把結果從 bit string 轉換為整數記做 $e$
3. 計算 $Q=[r^{-1}]\Big([s]R-[e]G\Big)$ 和 $Q=[r^{-1}]\Big([s](-R)-[e]G\Big)$
- 因為 EC 是對稱於 X 軸，所以會有兩個可能的 public key $Q$ 是透過 $R$ 和 $-R$ 所生出來
- 雖然有可能得到 0、1 或 2 把 public key $Q$，但是如果有額外資訊唯一規定到底誰是正確的那把（e.g., EIP-155 `v` payload），那這一步就不必算正負 $R$
- 通常優良的的 EC 會取 $n=\#E(\mathbb{F}_p)$（i.e., cofactor 等於一），因此第一步只會有唯一的 $R$

- Correctness of the algorithm
- $[r^{-1}]\Big([s]R-[e]G\Big)$
- $=[r^{-1}s]R-[r^{-1}e]G$
- $=[r^{-1}k^{-1}(e+dr)]\Big([k]G\Big)-[r^{-1}e]G$
- $=[r^{-1}e+d]G-[r^{-1}e]G$
- $=[r^{-1}e+d-r^{-1}e]G$
- $=[d]G=Q\ {\in}\ E(\mathbb{F}_p)$

Reference
---
- https://link.springer.com/content/pdf/10.1007/s102070100002.pdf
- ANSI X9.62-1998
- https://www.secg.org/sec1-v2.pdf
- https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages
- https://medium.com/cryptoadvance/how-schnorr-signatures-may-improve-bitcoin-91655bcb4744

Further Reading
---
- Elliptic Curve 與 secp256k1 筆記
- https://hackmd.io/oFmZZHamQUOKG9DHhEV7lw
- Schnorr Signature Generation & Verification
- https://hackmd.io/S4VkJObyRB6sdMauNLusYQ