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

はじめに

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

楕円曲線DSA（ECDSA）

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

基本的なパラメータ

署名する為の秘密鍵、公開鍵、メッセージ、ハッシュ関数を定義します。

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

署名（Sign）

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

\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$が使用可能です。

\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$だけが残ります。

\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$が署名値候補になります。

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

問題点

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

\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があります。

プログラミング

署名(Sign)

RFC6979の署名生成（2.4. Signature Generation）で署名値を求めます。
若干、部品が多いですがハッシュ関数とbiginteger（任意精度整数）で求めています。

// 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の「3.4.2 ECDSA Signature Verification」を利用します。

// 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にサンプルコードがありますので、詳しく見たい方はこちらをご覧ください。
今回は、Test Vectorsが見つからなかった為、golangの別の実装で双方向（Sign⇔Verify）を検証してみました。
ほとんどの言語で可能ですので一度試してみてください。