決定論的署名（Deterministic signature）

はじめに

署名についてのセキュリティを調べていたところ、決定論的署名を行うことが重要であるものの
サンプル実装などで案外解説されていないので、解説していこうと思います。

決定論的署名

ECDSAなどの署名や検証において、必要なのは、秘密鍵、公開鍵、メッセージ、ナンスの４つが必要です。
このナンスを適切に設定しないと秘密鍵が漏れてしまいます。
ある秘密鍵において同じナンスを使用すると署名値から秘密鍵が判明してしまいます。
そこで、ナンスをランダムにする必要があります。

しかし、各プログラミング言語で実装されているランダム関数などは大丈夫なのでしょうか？
簡単なものですと、シード（seed）を設定するのに、時間を使ったりします。
なんらかの手段で時間をリセットしたりすると同じ乱数を発生するかもしれません。
実際にPS3ではナンスを同じにしていた為（実装上の不具合）、秘密鍵が漏れてしまいました。

そこで、ECDSAでは、RFC 6979というものが定義されています。
楕円曲線DSA - Wikipediaのセキュリティにも重要性が記載されています。

簡単に言うと、秘密鍵とメッセージから、ランダムに見えるナンスを生成し署名する仕組みです。

悪い例

本当に秘密鍵が漏れてしまうのかを、検証してみたいと思います。
まずは、ECDSAの仕様をおさらいします。

署名側と検証側が知っている情報についてです。
大文字は楕円曲線上の点、小文字は数値、ただし$m$はメッセージとします。

署名側が知っている情報

\begin{align*}
x &\text{ : 秘密鍵} \\
P &\text{ : 公開鍵} (P=xG) \\
k &\text{ : ナンス} \\
R &\text{ : ナンスポイント} (R=kG) \\
m &\text{ : メッセージ} \\
H(\cdot)&\text{ : ハッシュ関数} \\
\end{align*}

検証側が知っている情報

\begin{align*}
P &\text{ : 署名-公開鍵} \\
m &\text{ : メッセージ} \\
H(\cdot)&\text{ : ハッシュ関数} \\
\end{align*}

ECDSA

ECDSAを見てみます。

署名

最終的に、$(r,s)$を検証側に知らせます。

\begin{align*}
&e = \text{H}(m) \\
&R = kG \\
&R : (x_R,y_R) \\
&r = x_R \\
&s = \frac{e+xr}{k} \\
&(r,s)\text{ : 署名値} \\
\end{align*}

検証

$(r,s)$を受け取ったら以下の手順で検証します。

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

秘密鍵の算出（ナンスが同じ場合）

ナンスを同じにした場合にどのようにして署名側の秘密鍵を算出するのかを見てみます。
Pythonのecdsaを使ってコードでも検証してみます。

サンプルを作ったので、興味のある方は使ってみてください。

署名

署名者は、異なるメッセージ$m_1,m_2$を同じナンス$k$で署名します。

\begin{align*}
&R = kG \\
&R : (x_R,y_R) \\
&r = x_R \\
&e_1 = \text{H}(m_1) \\
&s_1 = \frac{e_1+xr}{k} \\
&(r,s_1)\text{ : 署名値} \\
&e_2 = \text{H}(m_2) \\
&s_2 = \frac{e_2+xr}{k} \\
&(r,s_2)\text{ : 署名値} \\
\end{align*}

from hashlib import sha256
from ecdsa import ecdsa
import random

g = ecdsa.generator_secp256k1
n = g.order()

x = random.randint(1, n-1)
pub = ecdsa.Public_key(g, x*g)
pri = ecdsa.Private_key(pub, x)
k = random.randint(1, n-1)
nonce = ecdsa.Public_key(g, k*g)
m1 = 'hello'  # @param {type:"string"}
m2 = 'こんにちは'  # @param {type:"string"}

print('\033[34m'+'秘密鍵(x)：0x{:x}'.format(x)+'\033[0m')
print('公開鍵(P)：(0x{:x},0x{:x})'.format(pub.point.x(), pub.point.y()))
print('\033[35m'+'ナンス(k)：0x{:x}'.format(k)+'\033[0m')
print('ナンスポイント(R)：(0x{:x},0x{:x})'.format(nonce.point.x(), nonce.point.y()))
print('メッセージ１：{}'.format(m1))
print('メッセージ２：{}'.format(m2))

e1 = int.from_bytes(sha256(m1.encode('utf-8')).digest(), 'big')
sig1 = pri.sign(e1, k)

e2 = int.from_bytes(sha256(m2.encode('utf-8')).digest(), 'big')
sig2 = pri.sign(e2, k)

r1 = sig1.r
r2 = sig2.r
s1 = sig1.s
s2 = sig2.s
print('署名値１(r,s1)=(0x{:x},0x{:x})'.format(r1, s1))
print('署名値２(r,s2)=(0x{:x},0x{:x})'.format(r2, s2))

検証

検証側は、$(r,s_1),(r,s_2)$を受け取って以下の手順で署名者の秘密鍵$x$と求めます。
最初にナンス$k$を求め、署名値から秘密鍵$x$を算出します。

\begin{align*}
&e_1 = \text{H}(m_1) \\
&e_2 = \text{H}(m_2) \\
&k = \frac{e_1-e_2}{s_1-s_2} \\
&x = \frac{s_1 \cdot k - e_1}{r} \\
\end{align*}

e1 = int.from_bytes(sha256(m1.encode('utf-8')).digest(), 'big')
e2 = int.from_bytes(sha256(m2.encode('utf-8')).digest(), 'big')
print('署名値1の検証結果：{}'.format(pub.verifies(e1, sig1)))
print('署名値2の検証結果：{}'.format(pub.verifies(e2, sig2)))

if (r1 == r2):
    print('ナンスポイントが一致したので、ナンス(k)と秘密鍵(x)を算出します。')
    k = (((e1 - e2) % n) * pow(((s1 - s2) % n), n-2, n)) % n
    print('\033[35m'+'ナンス(k)：0x{:x}'.format(k)+'\033[0m')
    r = r1
    x = (((((s1 * k) % n) - e1) % n)*pow(r, n-2, n)) % n
    print('\033[34m'+'秘密鍵(x)：0x{:x}'.format(x)+'\033[0m')
else:
    print('ナンスポイントが一致しません')

RFC6979

もちろん、PythonのコードにもRFC6979は実装されていますので、サンプルコードの乱数を使わないでこちらを利用した方が望ましいです。

from ecdsa import rfc6979

msg = sha256(m1.encode('utf-8')).digest()
rfc6979_k = rfc6979.generate_k(n, pri.secret_multiplier, sha256, msg)
print('メッセージ「{}」のナンス(k)：0x{:x}'.format(m1, rfc6979_k))

さいごに

ナンスを使う署名全般に言えますが、ナンスは大事です。
しかし、ナンスを単なる乱数として考えない場合はナンスの生成方法を考える必要があります。

暗号論的擬似乱数生成器とか調べないといけないなぁ・・・どんどん、脱線していく・・・