楕円曲線DSA

楕円曲線DSA（だえんきょくせんDSA、Elliptic Curve Digital Signature Algorithm、Elliptic Curve DSA、楕円DSA、ECDSA）は、Digital Signature Algorithm (DSA) について楕円曲線暗号を用いるようにした変種である。

DSAとの比較

楕円曲線暗号で一般的に言われるように、ECDSAにおいて必要とされる公開鍵のサイズはセキュリティビット数のおよそ2倍であると考えられている。例えば、80ビットのセキュリティビット数（攻撃者が秘密鍵を取得するために $2^{80}$ 回の計算を必要とする）を得るために、DSAでは最低でも1024ビットの公開鍵が必要であるが、ECDSAでは160ビットの公開鍵で十分である。一方、署名のサイズはDSAでもECDSAでも同じであり、必要とするビット安全性の4倍のビット長を要する（80ビットのビット安全性を保つためには320ビットの長さの署名が必要）。

署名生成

パラメーター	説明
E	${ℝ}^2$ 上で定義される楕円曲線 $y^2=x^3+ax+b$ (ワイエルシュトラスの標準形)
p	E 上の有理点を還元する素数。E は${𝐅}_p\times {𝐅}_p$ 上の楕円曲線に写される
G	${𝐅}_p\times {𝐅}_p$ 上のベースポイント
n	G の位数（$n*G=O$ を満たす）
$d_A$	秘密鍵：$[1,n-1]$の範囲からランダムに選択され保持される整数
$Q_A$	公開鍵：$d_A*G$ (${𝐅}_p\times {𝐅}_p$ 上の点)
m	送信されるメッセージ

(注)「$*$」は楕円曲線上での掛け算 (scalar multiplication) を意味する。

アリスが署名したメッセージをボブに送る場合を考える。最初に、使用する楕円曲線のパラメータ $(E,p,G,n)$ を決めておく必要がある。

アリスは $[1,n-1]$ の範囲からランダムに選択された秘密鍵 $d_A$ と、公開鍵 $Q_A=d_A*G$ から成る鍵ペアを生成する。$d_A$ と $Q_A$ の対応は1対1であり、$d_A$ から $Q_A$ を計算することは比較的容易だが、 $Q_A$ から $d_A$ を計算することは実質的に不可能(離散対数問題)である。つまり $d_A$ と $Q_A$ の対応は一方向性関数になっている。

アリスがメッセージ $m$ に署名する場合、以下の計算を行う。

1. $e=H(m)$ を計算する。ここで H はSHA-1のような暗号学的ハッシュ関数を指す。
2. $z$ を、$e$ の最上位側の $L_n$ ビットとする。ここで $L_n$ は位数 $n$ のビット長とする。
3. $[1,n-1]$ の範囲から整数 $k$ を任意に選択する。
4. 曲線上の点 $(x_1,y_1)=k*G$ を計算する。
5. $r=x_{1}modn$ を計算する。$r=0$ となる場合には $k$ の選択に戻る。
6. $s=k^{-1}(z+r{d}_A)modn$ を計算する($k^{-1}$は有限体${𝐅}_n$における$k$の逆元である)。$s=0$ となる場合には $k$ の選択に戻る。
7. $(r,s)$ が $m$ に対する署名となる。

$s$ を計算する際に、$H(m)$ から得られる $z$ は整数に変換される。$z$ は $n$ より「大きい」ことは許されるが、「長い」ことは許されない。

DSAと同様に、署名ごとに異なる $k$ を選択することは極めて重要である。さもないと、ステップ6の式から秘密鍵 $d_A$ を得ることが可能となってしまう。メッセージ $m$ および $m^{\prime }$ に対して、未知だが同じ $k$ から得られた2つの署名 $(r,s)$ および $(r,s^{\prime })$ がある場合、攻撃者は $z$ および $z^{\prime }$ を計算することが可能であり、$s-s^{\prime }=k^{-1}(z-z^{\prime })$ であることから、$k=\frac{z-z^{\prime }}{s-s^{\prime }}$ が得られる。$s=k^{-1}(z+r{d}_A)$ であるから、攻撃者は秘密鍵 $d_A=\frac{sk-z}{r}$ を得ることができる。このように単一の $k$ を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった。

署名検証

ボブがアリスの署名を検証するためには、アリスの公開鍵 $Q_A$ が必要である。公開鍵 $Q_A$ が正当なものであるかの検証は以下のとおりである。

1. $Q_A$ が $O$ でないことを確認する。
2. $Q_A$ が曲線上にあることを確認する。
3. $n*Q_A=O$ であることを確認する。

メッセージ $m$ と署名 $(r,s)$ の検証は以下のように行われる。

1. $r$ および $s$ がいずれも $[1,n-1]$ の範囲にある整数であることを確認する。これを満たさない場合には署名は不正なものである。
2. $e=H(m)$ を計算する。ここで H は署名生成に用いられたハッシュ関数と同一のものである。
3. $z$ を、$e$ の最上位側の $L_n$ ビットとする。
4. $w=s^{-1}modn$ を計算する。
5. $u_1=zwmodn$ および $u_2=rwmodn$ を計算する。
6. 曲線上の点 $(x_1,y_1)=u_1*G+u_2*Q_A$ を計算する。
7. $r\equiv x_1(\mathrm{mod}n)$ であれば署名は正当なものである。

Straus's algorithm（Shamir's trickとも）を用いることで、2つの楕円曲線上での掛け算の和 $u_1*G+u_2*Q_A$ を、2つの楕円曲線上での掛け算よりも速く計算することができる。

アルゴリズムの正当性

ここで $C$ は署名検証のステップ6で得られた点とする。

$C=u_1*G+u_2*Q_A$

公開鍵が $Q_A=d_A*G$ と定義されることより

$C=u_1*G+u_2{d}_A*G$

楕円曲線上での掛け算より

$C=(u_1+u_2{d}_A)*G$

署名検証のステップ4より $u_1$ および $u_2$ の定義を拡張すると

$C=(z{s}^{-1}+r{d}_A{s}^{-1})*G$

$s^{-1}$ を外に出して

$C=(z+r{d}_A)s^{-1}*G$

署名のステップ6より $s$ の定義を拡張すると

$C=(z+r{d}_A)(z+r{d}_A{)}^{-1}(k^{-1}{)}^{-1}*G$

逆数の逆数は元と同じであることと、逆数と元の積は $O$ であることから

$C=k*G$

$r$ の定義より、これは署名検証のステップ6と等しい。

これは正しく署名されたメッセージは正しく検証されることのみを示しており、セキュアな署名アルゴリズムであるための他の要素については考慮していない。

セキュリティ

2010年12月、fail0verflowと名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていたECDSA秘密鍵の回復に成功したと発表した。しかし、これは $k$ をランダムではなく固定値としていたソニーの不適切な実装によるものであり、アルゴリズム自体の脆弱性ではない。署名生成のセクションで述べたように、$k$ を固定値で用いることは秘密鍵 $d_A$ を計算可能とし、アルゴリズムを破綻させるものである。

2011年3月29日、2人の研究者による論文がテンプレート:仮リンクに発表された。この論文では、サイドチャネル攻撃の一つであるタイミング攻撃によって、ECDSAを認証に利用し、OpenSSLを用いたサーバのTLS秘密鍵を入手可能であることが示された。この脆弱性はOpenSSL 1.0.0eで修正された。

2013年8月、Java class SecureRandomのいくつかの実装において、$k$ のコリジョンが発生することがあるバグが明らかとなった。前述のように、これにより秘密鍵を得ることが可能であり、Javaを利用しECDSAを認証に用いていたAndroidアプリからBitcoinが盗まれる危険性があった。この問題は独立提出のテンプレート:IETF RFCにあるように、秘密鍵とメッセージハッシュから決定論的に $k$ を導くことで回避できる。

2015年1月、Bitcoinのウォレットが完全にオフラインであっても、ECDSAを利用したトランザクションのデジタル署名を通して秘密鍵が漏洩される可能性があることを示す研究論文がarXivにて発表された。この論文では、利用ユーザー側がECDSAおよびビットコインの実装を完全に検証できない限り信頼できないことから、ソースコードの検証からコンパイルといったユーザー側の敷居が高くなるため、プライベートキー漏洩の攻撃を防ぐための実質的な解決策が現段階でないと結論付けている。

このアルゴリズムは楕円曲線をパラメータとして必要とするが、多くの場合NISTによって定められた楕円曲線（P-256、P-384、P-521など）が用いられる。これらの曲線は特定のシード値からSHA-1を基盤としたアルゴリズムを用いて算出されているが、シード値の根拠が不明であること、また同じく固定の楕円曲線を用いたアルゴリズムであるテンプレート:仮リンクにNSAがバックドアを仕込んだ上でRSAセキュリティ社のセキュリティ製品に採用させたと報道されたことから、疑いの目で見られることがある。

実装ライブラリ

ECDSAをサポートしているライブラリは以下の通りである。

• Botan
• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク
• OpenSSL
• GnuTLS
• wolfCrypt

参考文献

• Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
• Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography, Version 2.0, May 21, 2009.
• López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
• Daniel J. Bernstein, Pippenger's exponentiation algorithm, 2002.
• Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119–152, 2005. ePrint version
• Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• テンプレート:Cite journal

関連項目

• 楕円曲線暗号
• Digital Signature Algorithm

外部リンク

• Digital Signature Standard; includes info on ECDSA