biginteger（任意精度整数）でECDSA（楕円曲線DSA）

# はじめに

[前回](https://qiita.com/tnakagawa/items/c0396c294eaf67f55fdc)、楕円曲線（EC）の加法を求めました、これにより秘密鍵と公開鍵が作成出来るようになりました。
今回は、ECDSA（楕円曲線DSA）の署名（Sign）と検証（Verify）をbiginteger（任意精度整数）を使って実装しみようという試みです。

# 楕円曲線DSA（ECDSA）

仕様は、[NSA](https://apps.nsa.gov/iaarchive/search.cfm)のSearchに「ECDSA」と入れて検索します。
「Suite B Implementer’s Guide to FIPS 186-3 (ECDSA)」という文章がこれにあたります。
（※：Wikipediaにあるリンクはリンク切れでした、名称は変えています。）

### 基本的なパラメータ
署名する為の秘密鍵、公開鍵、メッセージ、ハッシュ関数を定義します。

```math
\begin{align*}
&P = xG \\
&\text{Message : } m \\
&\text{Hash}() \text{ : hash function} \\
\end{align*}
```

### 署名（Sign）

基本的なパラメータを使って署名を行います。
署名する側なので、秘密鍵$x$は使用可能です。
また、乱数$k$を求めます。
（後述しますが、乱数を使いまわすと危険なので注意が必要です。）

```math
\begin{align*}
&e = \text{Hash}(m) \\
&R = kG \\
&R : (x_R,y_R) \\
&r = x_R \\
&s = \frac{e+xr}{k} \\
&\text{Signature : } (r,s) \\
\end{align*}
```

署名値は、$(r,s)$となります。

### 検証（Verify）

署名値$(r,s)$と基本的なパラメータを使って検証を行います。
検証する側なので、公開鍵$P$が使用可能です。

```math
\begin{align*}
&e = \text{Hash}(m) \\
&w = s^{-1} \\
&u_1 = ew \\
&u_2 = rw \\
&Q = u_1G + u_2P \\
&Q : (x_Q,y_Q) \\
&v = x_Q \\
&v \overset{?}{=} r \\
\end{align*}
```

計算した、楕円曲線上の点$Q$から、$x$座標$x_Q$が合致しているか判定する。

### 証明（Proof）

$e+xr$が消えて、最後に$k$だけが残ります。

```math
\begin{align*}
e &= \text{Hash}(m) \\
w &= s^{-1} \\
u_1 &= ew \\
u_2 &= rw \\
Q &= u_1G + u_2P \\
 &= \frac{ek}{e+xr}G + \frac{rk}{e+xr}xG \\
 &= \frac{ek+xrk}{e+xr}G \\
 &= \frac{(e+xr)k}{e+xr}G \\
 &= kG \\
Q &: (x_Q,y_Q) \\
\end{align*}
```

### 個人的な疑問

$-k$でも成り立たね？ということは、$s$と$-s$が署名値候補になります。

```math
\begin{align*}
Q &= -kG \\
Q &: (x_Q,-y_Q) \\
\end{align*}
```

### 問題点

乱数$k$が同じであれば秘密鍵$x$を求める事が出来ます。

```math
\begin{align*}
e &= \text{Hash}(m) \\
e' &= \text{Hash}(m') \\
R &= kG \\
R &: (x_R,y_R) \\
r &= x_R \\
s &= \frac{e+xr}{k} \\
s' &= \frac{e'+xr}{k} \\
\text{Signature}&: (r,s) \text{ or } (r,s') \\
s-s' &= \frac{e+xr}{k} - \frac{e'+xr}{k}= \frac{e-e'}{k} \\
k &= \frac{e-e'}{s-s'} \\
\end{align*}
```

$s$と$-s$が署名値候補なので、異なる場合があります。

乱数$k$を安全に設定する為、[RFC6979](https://tools.ietf.org/html/rfc6979)があります。

# プログラミング

## 署名(Sign)

[RFC6979](https://tools.ietf.org/html/rfc6979)の署名生成（2.4.  Signature Generation）で署名値を求めます。
若干、部品が多いですがハッシュ関数とbiginteger（任意精度整数）で求めています。

```golang
// H returns the double hash of message.
func H(m []byte) []byte {
	hash := sha256.Sum256(m)
	hash = sha256.Sum256(hash[:])
	return hash[:]
}

// 2.3.2.  Bit String to Integer
// https://tools.ietf.org/html/rfc6979#section-2.3.2
func bits2int(m []byte) *big.Int {
	qlen := n.BitLen()
	b := new(big.Int).SetBytes(m)
	blen := b.BitLen()
	if qlen < blen {
		b.Rsh(b, uint(blen-qlen))
	}
	return b
}

// 2.3.3.  Integer to Octet String
// https://tools.ietf.org/html/rfc6979#section-2.3.3
func int2octets(x *big.Int) []byte {
	l := len(n.Bytes())
	bs := x.Bytes()
	if len(bs) < l {
		bs2 := make([]byte, l)
		copy(bs2[l-len(bs):], bs)
		return bs2
	}
	if len(bs) > l {
		bs2 := make([]byte, l)
		copy(bs2, bs[len(bs)-l:])
		return bs2
	}
	return bs
}

// HMAC returns a sequence of bits of length hlen with the key and the data.
// 3.1.1.  HMAC
// https://tools.ietf.org/html/rfc6979#section-3.1.1
func HMAC(key []byte, values ...[]byte) []byte {
	h := hmac.New(sha256.New, key)
	data := []byte{}
	for _, value := range values {
		data = append(data, value...)
	}
	h.Write(data)
	return h.Sum(nil)
}

// 3.2.  Generation of k
// https://tools.ietf.org/html/rfc6979#section-3.2
func nonceRFC6979(m []byte, x *big.Int) *big.Int {
	h1 := H(m)
	V := bytes.Repeat([]byte{0x01}, len(h1))
	K := make([]byte, len(h1))
	K = HMAC(K, V, []byte{0x00}, int2octets(x), h1)
	V = HMAC(K, V)
	K = HMAC(K, V, []byte{0x01}, int2octets(x), h1)
	V = HMAC(K, V)
	for {
		T := []byte{}
		tlen := new(big.Int).SetBytes(T).BitLen()
		qlen := n.BitLen()
		if tlen < qlen {
			V = HMAC(K, V)
			T = append(T, V...)
		}
		k := bits2int(T)
		if k.Cmp(big.NewInt(0)) > 0 && k.Cmp(n) < 0 {
			return k
		}
		K = HMAC(K, V, []byte{0x00})
		V = HMAC(K, V)
	}
}

// Sign returns the signature.
// 2.4.  Signature Generation
// https://tools.ietf.org/html/rfc6979#section-2.4
func Sign(m []byte, x *big.Int) (*big.Int, *big.Int) {
	h := new(big.Int).Mod(bits2int(H(m)), n)
	k := nonceRFC6979(m, x)
	R := Mul(k, G)
	r := R.X
	// s = (h + x*r) * k^(q-2)
	s := new(big.Int).Mod(
		new(big.Int).Mul(
			new(big.Int).Add(h, new(big.Int).Mul(x, r)),
			new(big.Int).Exp(k, new(big.Int).Sub(n, big.NewInt(2)), n)),
		n)
	half := new(big.Int).Rsh(n, 1)
	if s.Cmp(half) > 0 {
		s.Sub(n, s)
	}
	return r, s
}
```

## 検証(Verify)

検証は、[NSA](https://apps.nsa.gov/iaarchive/library/index.cfm)の「3.4.2 ECDSA Signature Verification」を利用します。

```golang
// Verify verifies the signature in r, s of message using the public key, P.
// https://apps.nsa.gov/iaarchive/library/index.cfm
// "Suite B Implementer’s Guide to FIPS 186-3 (ECDSA)"
func Verify(P *Point, m []byte, r, s *big.Int) bool {
	if r.Cmp(big.NewInt(1)) < 0 && r.Cmp(n) >= 0 {
		return false
	}
	if s.Cmp(big.NewInt(1)) < 0 && s.Cmp(n) >= 0 {
		return false
	}
	e := bits2int(H(m))
	w := new(big.Int).Exp(s, new(big.Int).Sub(n, big.NewInt(2)), n)
	u1 := new(big.Int).Mod(new(big.Int).Mul(e, w), n)
	u2 := new(big.Int).Mod(new(big.Int).Mul(r, w), n)
	V := Add(Mul(u1, G), Mul(u2, P))
	if V.Infinite() || r.Cmp(V.X) != 0 {
		return false
	}
	return true
}
```

実装完了です。

# さいごに

[github](https://github.com/tnakagawa/refec)にサンプルコードがありますので、詳しく見たい方はこちらをご覧ください。
今回は、Test Vectorsが見つからなかった為、golangの別の実装で双方向（Sign⇔Verify）を検証してみました。
ほとんどの言語で可能ですので一度試してみてください。