いまさらECDSARECOVER

# はじめに（Introduction）

Ethereum系のスマートコントラクトに若干関わる事になったのだが、
署名値の検証方法がBitcoinと異なる為、非常に混乱しました。

楕円曲線暗号の定義から、ECDSARECOVERの解説まで行います。
また、サンプルコード（JavaScript）も作成していきます。

# 楕円曲線暗号（Elliptic Curve Cryptography）

### 楕円曲線パラメータ（secp256k1）

楕円曲線は、有限体 $\mathbb{F}_p$ 上の曲線 $ y^2 = x^3 + ax +b $ を利用します。
secp256k1では以下のパラメータを使用します。

```math
\begin{align*}
p =&\ \small{\texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F}} \\
=&\ 2^{256} − 2^{32} − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 \\
a =&\ 0 \\
b =&\ 7 \\
\end{align*}
```

したがって、secp256k1は $y^2 = x^3 + 7 \pmod{p}$ の楕円曲線を使用します。
生成元 $G$ とその位数 $n$ は以下となります。
生成元は楕円曲線上の点（Point）で位数で循環します。

```math
\begin{align*}
G =&\ \small{\texttt{04}} \\
&\ \small{\texttt{79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9
59F2815B 16F81798 }}\\
&\ \small{\texttt{483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8}} \\
n =&\ \small{\texttt{FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141}}\\
\end{align*} 
```

点の加算、スカラー倍算の定義の元で、$G=nG+G$ が成り立ちます。
$p$ も $n$ も素数（Prime Number）となります。

<details>
<summary>サンプルコード（JavaScript）</summary><div>

```javascript
// 楕円曲線演算（secp256k1）    

// 楕円曲線係数（ secp256k1 : y^2 = x^3 + 7　）
const b = 7n;
// 楕円曲線の位数
const p = BigInt('0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F');
// 生成元
const G = {
    x: BigInt('0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798'),
    y: BigInt('0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8'),
}
// 生成元の位数
const n = BigInt('0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141');
```

</div></details>

### 剰余演算（Modulo operation）

楕円曲線における点の加算やスカラー倍算、デジタル署名や検証の計算で扱う剰余演算を定義します。
位数を $p$ とします。
加算は、$x + y \equiv z \pmod{p}$ となります。
乗算は、$x \times y \equiv z \pmod{p}$ となります。
減算は、$x - y \equiv z \pmod{p}$ となりますが、JavaScriptの場合 $z$ が負の値となる場合があります。
この場合は正の値にする為、$z = p + z$ とします。（負の値で計算しても問題はありません。）
つぎに、べき乗を作成します。
べき乗の剰余なので、冪剰余を実装するのですが、$z \equiv  x^y \pmod{p}$ のように簡単にはできません。
JavaScriptの場合、`bigint`型であっても上限が存在します。
「[冪剰余 - Wikipedia#2.2 途中で剰余をとる](https://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99#%E9%80%94%E4%B8%AD%E3%81%A7%E5%89%B0%E4%BD%99%E3%82%92%E3%81%A8%E3%82%8B)」のロジックを利用します。
除算ですが、乗法逆元 $z \equiv x^{-1} \pmod{p}\ $ を算出し乗算と組み合わせる事で実現します。
$p$ が素数であれば、乗法逆元は[フェルマーの小定理](https://qiita.com/tnakagawa/items/500db60b3bbe16e7fb30)を応用して $z \equiv x^{p-2} \pmod{p}\ $ で計算できます。


<details>
<summary>サンプルコード（JavaScript）</summary><div>

```javascript
// 剰余演算

/**
 * 加算（剰余演算）
 * @param {bigint} x 
 * @param {bigint} y 
 * @param {bigint} p 
 * @returns x + y mod p 
 */
function add(x, y, p) {
    return (x + y) % p;
}

/**
 * 減算（剰余演算）
 * 負値の場合、正値に変更
 * @param {bigint} x 
 * @param {bigint} y 
 * @param {bigint} p 
 * @returns x - y mod p
 */
function sub(x, y, p) {
    let z = (x - y) % p;
    if (z < 0n) {
        z += p;
    }
    return z;
}

/**
 * 乗算（剰余演算）
 * @param {bigint} x 
 * @param {bigint} y 
 * @param {bigint} p 
 * @returns x * y mod p
 */
function mul(x, y, p) {
    return (x * y) % p;
}


/**
 * 乗法逆元（剰余演算）
 * @param {bigint} x 
 * @param {bigint} p 素数
 * @returns x ^ -1 mod p
 */
function inv(x, p) {
    return pow(x, p - 2n, p);
}

/**
 * べき乗（剰余演算）
 * @param {bigint} x 
 * @param {bigint} y 
 * @param {bigint} p
 * @returns x ^ y mod p
 */
function pow(x, y, p) {
    let z = 1n;
    while (y > 0n) {
        if (y & 1n) {
            z = z * x % p;
        }
        x = (x * x) % p;
        y >>= 1n;
    }
    return z;
}
```

</div></details>

### 点の加算（Point Addition）

楕円曲線上の点の加算を以下のようにあらわす。

#### ２点が異なる場合（P<sub>1</sub> ≠ P<sub>2</sub>）

![point_add_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/12dbf130-0c76-2aa1-4a57-11982c612b4b.png)

上の図で、緑の点を $P_1(x_1,y_2)$ 、青の点を $P_2(x_1,y_2)$、赤の点を $P_3(x_3,y_3)$ とします。
この時、$P_3 = P_1 + P_2$ とすると、$P_3$ は以下の式で求められます。

```math
\begin{align*}
s&=\frac{y_2-y_1}{x_2-x_1}\\
x_3&=s^2-x_1-x_2\\
y_3&=s(x_1-x_3)-y_1\\
\end{align*}
```

#### ２倍算（P<sub>1</sub> = P<sub>2</sub>）

![point_add_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/bec03381-fce7-0b88-d008-29d5a1b0c8a7.png)

同じ点を加算する場合を考えます。
上の図で、緑の点を $P_1(x_1,y_2)$ 、青の点を $P_3(x_3,y_3)$ とします。
この時、$P_3 = P_1 + P_1$ とすると、$P_3$ は以下の式で求められます。

```math
\begin{align*}
s&=\frac{3x_1^2}{2y_1}\\
x_3&=s^2-2x_1\\
y_3&=s(x_1-x_3)-y_1\\
\end{align*}
```

#### 無限遠点（Point at infinity）

![point_infinity_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/9619d9b3-0a95-443d-6e9d-ef7eda917c07.png)

２点を通る直線を考えた時、上の図のように曲線と交わらない場合が考えられます。
この時、無限遠点 $I$ で交わる事とすると、以下のような点の加算ができます。

```math
\begin{align*}
P = I + P =P + I\\
\end{align*}
```

#### 特殊な場合

![point_infinity_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/b0f0227c-8ba9-08d6-6ab8-3f1da2f7455b.png)

上記のような点の場合、２倍算の結果は無限遠点となります。


以上を踏まえ点の加算のコードを作成します。
上記の図は全て実数での表現の為、連続したグラフになっていますが、実際は有限体なので連続なグラフとはなりません。

<details>
<summary>サンプルコード（JavaScript）</summary><div>

```javascript
/**
 * 点の加算
 * @param {point} P1 
 * @param {point} P2 
 * @returns 点
 */
function addPoint(P1, P2) {
    if (P1.x == null && P1.y == null) {
        return P2;
    }
    if (P2.x == null && P2.y == null) {
        return P1;
    }
    let s = null;
    if (P1.x != P2.x) {
        // 異なる点
        // s = (P2.y - P1.y) / (P2.x - P1.x)
        s = sub(P2.y, P1.y, p) * inv(sub(P2.x, P1.x, p), p);
    } else {
        // 同一点
        if (P1.y != P2.y) {
            // P1 = -P2
            return { x: null, y: null };
        } else if (P1.y == 0n) {
            // 接線が垂直
            return { x: null, y: null };
        }
        // s = (3*P1.x^2) / (2 * P1.y)
        s = mul(3n, pow(P1.x, 2n, p), p) * inv(mul(2n, P1.y, p), p);
    }
    // P3.x = s^2 - P1.x - P2.x
    let x3 = sub(sub(pow(s, 2n, p), P1.x, p), P2.x, p);
    // P3.y = s*(P1.x - P3.x) - P1.y
    let y3 = sub(mul(s, sub(P1.x, x3, p), p), P1.y, p);
    return { x: x3, y: y3 };
}
```

</div></details>

### スカラー倍算（Scalar Multiplication）

同じ点 $P$ を加算できるので、$P+P=2P\ $ とあらわします。
これを $k$ 回繰り返したものを、$kP$と表します。
これをスカラー倍算と呼びます。
実装するには、$k$ 回ループすれば良いように思えますが、secp256k1では非常に大きい数を使用します。
そこで、二進展開を用いる事で、$\log_2(k)$ 回で済むように工夫します。


<details>
<summary>サンプルコード（JavaScript）</summary><div>

```javascript
/**
 * 点のスカラー倍算
 * @param {point} P 
 * @param {bigint} k 
 * @returns kP
 */
function mulPoint(P, k) {
    let Q = { x: null, y: null };
    while (k > 0n) {
        if (k & 1n) {
            Q = addPoint(Q, P);
        }
        P = addPoint(P, P);
        k >>= 1n;
    }
    return Q;
}

```

</div></details>

### テスト（TEST）

secp256k1のテストデータ（[secp256k1 Test Vectors](https://chuckbatson.wordpress.com/2014/11/26/secp256k1-test-vectors/)）からテストを行います。


# 署名と検証（Sign and Verify）

[Standards for Efficient Cryptography](https://www.secg.org/sec1-v2.pdf)の署名と検証についてみます。

### 署名（Sign）

**Input**
秘密鍵$\ x\ $、メッセージ$\ M\ $
**Output**
署名値$\ S=(r,s)\ $

**Actions**

1. 一時的な$\ k\ $を選択します。（乱数など）
2. 楕円曲線のスカラー倍算より、$R = kG\ ,\ R(x_R,y_R)\ $を生成します。
3. $\ r = x_R \pmod{n}\ $を計算します。
4. $\ e = \textit{HASH}(M)\ $メッセージをハッシュしそれを数値とします。
5. $s =  k^{-1}(e + rx) \pmod{n}\ $左記の式で署名値を計算します。<br>$s=0\ $だった場合は1へ戻ります。
6. 署名値$\ S=(r,s)\ $を返す。

:::note alert
The signer may replace (r, s) with (r, −s mod n), because this is an equivalent signature.
同等の署名であるため、署名者は (r, s) を (r, −s mod n) に置き換えることができます。

r は楕円曲線上の点における x 座標なので、y 座標の候補が2つになります。
:::


### 検証（Verify）

**Input**
公開鍵$\ P(x_P,y_P)\ $、メッセージ$\ M\ $、署名値$\ S=(r,s)\ $
**Output**
署名値の有効（valid）または、無効（invalid）

**Actions**

1. 署名値の$\ r\ $と$\ s\ $が$\ \[1,n-1\]\ $の範囲にあるか判定します。<br>範囲外の場合は**無効（invalid）**として処理を終えます。
2. $\ e = \textit{HASH}(M)\ $メッセージをハッシュしそれを数値とします。
3. $\ u_1=es^{-1} \pmod{n}\ $と$\ u_2=rs^{-1} \pmod{n}\ $を計算します。
4. $\ R=(x_R,y_R)=u_1G+u_2P\ $左記の計算を行います。<br>$\ R\ $が無限遠点の場合は**無効（invalid）**として処理を終えます。
5. $\ v=x_R \pmod{n}\ $を計算します。
6. $\ v = r\ $の場合は**有効（valid）**として処理を終えます。<br>$\ v \ne r\ $の場合は**無効（invalid）**として処理を終えます。

# ECDSAPUBKEY, ECDSASIGN and ECDSARECOVER

[Ethereum Yellow Paper](https://ethereum.github.io/yellowpaper/paper.pdf)にある、ECDSAPUBKEY、ECDSASIGN、ECDSARECOVERを実装してみます。
Ethereum系のスマートコントラクトでは ECDSASIGN で算出した署名値から、ECDSARECOVER を利用して公開鍵を復元する事で認証としているようです。

### ECDSAPUBKEY

$\text{ECDSAPUBKEY}( p_r \in B_{32} ) \equiv p_u \in B_{64}$

**Input**
秘密鍵 $p_v$
**Output**
公開鍵 $p_u$

**Actions**

単純に生成元 $G$ を秘密鍵 $p_r$ でスカラー倍算して公開鍵 $p_u$ を求めます。

### ECDSASIGN

$\text{ECDSASIGN}( e \in B_{32} , p_r \in B_{32} ) \equiv (v \in B_{1},r \in B_{64},s \in B_{64})$

**Input**
メッセージハッシュ $e$
秘密鍵 $p_v$
**Output**
署名データ $(v,r,s)$
　リカバリ識別子：$v \in \lbrace 27,28 \rbrace$
　$x$座標：$0 < r < n$
　署名値：$0 < s < n \div 2 + 1$

:::note info
The value 27 represents an even y value and 28 represents an odd y value.
yの値が偶数ならば27、奇数であれば28とします。

rは楕円曲線のx座標なので、それを用いてy座標を求められますが、楕円曲線はx軸に対して対称な図形の為、y座標は2つ求められます。
奇素数pの有限体上での楕円曲線なので、y,-yならばどちらかが奇数、どちらかが偶数となります。
したがって、奇数が偶数かがわかれば一意にy座標が求められます。
:::

**Actions**

1. 通常の署名と同じように、一時的な $k$ を求めます。（乱数など）
2. 生成元のスカラー倍算を行い、$R = kG$ とし$R(x_R,y_R)$ から $r = x_R$ とします。<br>$r$ が $0 < r < n$ でない場合、1からやり直します。
3. $x = p_v$ とし $s = k^{-1}(e + rx) \pmod{n}$ を求めます。<br>$s$ が $0 < s < n \div 2 + 1$ でない場合、$s=-s$ とし $R = -R$ とします。
4. $y_R$ が偶数の場合 $v=27$ とし、奇数の場合 $v=28$ とします。
5. 署名データ $(v,r,s)$ を返します。

:::note info
ep-155(https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155.md)では、vに'CHAIN_ID'を含める仕様となっています。
:::

### ECDSARECOVER

$\text{ECDSARECOVER}( e \in B_{32} , v \in B_{1},r \in B_{64},s \in B_{64} ) \equiv p_u \in B_{64}$

**Input**
メッセージハッシュ $e$
リカバリ識別子 $v$
$x$座標 $r$
署名値 $s$
**Output**
公開鍵 $p_u$

**Actions**

1. $R(x_R,y_R)$ とした時、$x_R = r$ として、次のように$y_R$ を求めます。<br>$y_R = (x_R^3 + 7)^{\frac{p+1}{4}}$
2. $v$ が奇数（27）かつ $y_R\ $が奇数または、$v$ が偶数（28）かつ $y_R$ が偶数である場合、$y_R = p - y_R$ とします。
3. $Q = r^{-1}(sR - eG)$ を計算して、$Q$ を返します。



<details>
<summary>サンプルコード（JavaScript）</summary><div>

```javascript
// ECDSA演算

/**
 * 公開鍵生成
 * @param {bigint} x 秘密鍵
 * @returns 公開鍵
 */
function ECDSAPUBKEY(x) {
    return mulPoint(G, x)
}

/**
 * 署名値生成
 * @param {bigint} e メッセージハッシュ
 * @param {bigint} x 秘密鍵
 * @returns 署名データ
 */
function ECDSASIGN(e, x) {
    let k = rnd32() % n;
    let R = mulPoint(G, k);
    let r = R.x;
    if (r >= n) {
        return ECDSASIGN(e, x);
    }
    // s = (e + xr) / k
    let s = mul(add(e, mul(x, r, n), n), inv(k, n), n);
    if (s == 0n) {
        return ECDSASIGN(e, x);
    }
    // 0 < s < n ÷ 2 + 1
    if (s > (n - 1n) / 2n) {
        s = n - s;
        R.y = p - R.y;
    }
    // v ∈ {27, 28} 
    // The value 27 represents an even y value and 28 represents an odd y value.
    let v = 27n + (R.y & 1n);
    return { v: v, r: R.x, s: s };
}

/**
 * 署名値から公開鍵取得
 * @param {bigint} e メッセージハッシュ
 * @param {bigint} v リカバリ識別子
 * @param {bigint} r x座標
 * @param {bigint} s 署名値
 * @returns 公開鍵
 */
function ECDSARECOVER(e, v, r, s) {
    let R = { x: r, y: null };
    // y = √(x^3 + 7)
    R.y = pow(add(pow(r, 3n, p), b, p), (p + 1n) / 4n, p);
    if ((v & 1n) == (R.y & 1n)) {
        R.y = p - R.y;
    }
    // Q = r^{−1}(sR − eG)
    let Q = mulPoint(addPoint(mulPoint(R, s), mulPoint(G, sub(n, e, n))), inv(r, n));
    return Q;
}
```

</div></details>

# まとめ（Conclusion）

ソースコードは**[Github](https://github.com/tnakagawa/education/tree/master/ecdsarecover)**にあります。
デモは**[ここ](https://tnakagawa.github.io/education/ecdsarecover/index.html)**にあります。

$x_R=r$ から $R(x_R,y_R)$ が復元できれば、公開鍵も復元できる事がわかりました。
問題としては、$x_R$ は有限体 $\mathbf{F}_p$ 、その他は有限体 $\mathbf{F}_n$ の為、微小な差があります。
その為、かなりの低確率で候補がもう１つあるみたいです。（詳細は以下を参照ください。）
[Standards for Efficient Cryptography / SEC 1: Elliptic Curve Cryptography](https://www.secg.org/sec1-v2.pdf)の「4.1.6 Public Key Recovery Operation」
 


# 参考（References）

- [Standards for Efficient Cryptography<br>SEC 1: Elliptic Curve Cryptography](https://www.secg.org/sec1-v2.pdf)

- [Standards for Efficient Cryptography<br>SEC 2: Recommended Elliptic Curve Domain Parameters](https://www.secg.org/sec2-v2.pdf)

- [冪剰余 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99)

- [楕円曲線暗号 - Wikipedia](https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7)

- [secp256k1 Test Vectors](https://chuckbatson.wordpress.com/2014/11/26/secp256k1-test-vectors/)

- [ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER<br>Appendix F. Signing Transactions](https://ethereum.github.io/yellowpaper/paper.pdf)

- [ecrecoverでpublic keyが一意に定まる理由](https://y-nakajo.hatenablog.com/entry/2018/01/25/120531)

- [どうしてECDSA署名から公開鍵が復元できるのか？](https://techmedia-think.hatenablog.com/entry/2018/01/21/131037)

- [ECDSAによる署名生成と検証の仕組みを分かりやすく解説](https://zoom-blc.com/what-is-ecdsa)