楕円曲線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	$\mathbb {R} ^{2}$ 上で定義される楕円曲線 $y^{2}=x^{3}+ax+b$ (ワイエルシュトラスの標準形)
p	E 上の有理点を還元する素数。E は $\mathbf {F} _{p}\times \mathbf {F} _{p}$ 上の楕円曲線に写される
G	$\mathbf {F} _{p}\times \mathbf {F} _{p}$ 上のベースポイント
n	G の位数（ $n*G=O$ を満たす）
$d_{A}$	秘密鍵： $[1,n-1]$ の範囲からランダムに選択され保持される整数
$Q_{A}$	公開鍵： $d_{A}*G$ ( $\mathbf {F} _{p}\times \mathbf {F} _{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$ に署名する場合、以下の計算を行う。

$e=H(m)$ を計算する。ここで H はSHA-1のような暗号学的ハッシュ関数を指す。
$z$ を、 $e$ の最上位側の $L_{n}$ ビットとする。ここで $L_{n}$ は位数 $n$ のビット長とする。
$[1,n-1]$ の範囲から整数 $k$ を任意に選択する。
曲線上の点 $(x_{1},y_{1})=k*G$ を計算する。
$r=x_{1}\,{\bmod {\,}}n$ を計算する。 $r=0$ となる場合には $k$ の選択に戻る。
$s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$ を計算する( $k^{-1}$ は有限体 $\mathbf {F} _{n}$ における $k$ の逆元である)。 $s=0$ となる場合には $k$ の選択に戻る。
$(r,s)$ が $m$ に対する署名となる。

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

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

署名検証

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

$Q_{A}$ が $O$ でないことを確認する。
$Q_{A}$ が曲線上にあることを確認する。
$n*Q_{A}=O$ であることを確認する。

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

$r$ および $s$ がいずれも $[1,n-1]$ の範囲にある整数であることを確認する。これを満たさない場合には署名は不正なものである。
$e=H(m)$ を計算する。ここで H は署名生成に用いられたハッシュ関数と同一のものである。
$z$ を、 $e$ の最上位側の $L_{n}$ ビットとする。
$w=s^{-1}\,{\bmod {\,}}n$ を計算する。
$u_{1}=zw\,{\bmod {\,}}n$ および $u_{2}=rw\,{\bmod {\,}}n$ を計算する。
曲線上の点 $(x_{1},y_{1})=u_{1}*G+u_{2}*Q_{A}$ を計算する。
$r\equiv x_{1}{\pmod {n}}$ であれば署名は正当なものである。

Straus's algorithm（Shamir's trickとも）を用いることで、2つの楕円曲線上での掛け算の和 $u_{1}*G+u_{2}*Q_{A}$ を、2つの楕円曲線上での掛け算よりも速く計算することができる^[3]。

アルゴリズムの正当性

ここで $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=(zs^{-1}+rd_{A}s^{-1})*G$

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

$C=(z+rd_{A})s^{-1}*G$

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

$C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}*G$

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

$C=k*G$

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

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

セキュリティ

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

2011年3月29日、2人の研究者による論文がIACR（英語版）に発表された。この論文では、サイドチャネル攻撃の一つであるタイミング攻撃によって、ECDSAを認証に利用し、OpenSSLを用いたサーバのTLS秘密鍵を入手可能であることが示された^[5]。この脆弱性はOpenSSL 1.0.0eで修正された^[6]。

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

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

実装ライブラリ

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

脚注

^ FIPS 186-3, pp. 19 and 26
^ Console Hacking 2010 - PS3 Epic Fail, page 123–128
^ The Double-Base Number System in Elliptic Curve Cryptography
^ Bendel, Mike (2010年12月29日). “Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access”. Exophase.com 2013年12月26日閲覧。
^ Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack
^ OpenSSL: News, ChangeLog
^ “Android bug batters Bitcoin wallets”. The Register (2013年8月12日). 2013年12月26日閲覧。
^ ^a ^b “RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE” (1999年7月). 2015年7月11日閲覧。
^ “SafeCurves: Rigidity”. 2015年7月11日閲覧。
^ 例えばMD5やSHA-2で撹拌のために用いられる定数テーブルは整数ラジアンの三角関数の値や素数の平方根や立方根の値を特定の形で用いており、意図的な操作の余地が少ない。
^ “Exclusive: Secret contract tied NSA and security industry pioneer”. Reuters (2013年12月20日). 2015年7月11日閲覧。
^ Daniel J. Bernstein, Tanja Lange (2013年5月31日). “Security dangers of the NIST curves”. 2015年7月11日閲覧。
^ Maxwell, Gregory (2013年9月8日). “[tor-talk NIST approved crypto in Tor?]”. 2015年7月11日閲覧。

参考文献

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.
. (2004). doi:10.1007/b97644.

外部リンク

Digital Signature Standard; includes info on ECDSA

[1] FIPS 186-3, pp. 19 and 26

[2] Console Hacking 2010 - PS3 Epic Fail, page 123–128

[3] The Double-Base Number System in Elliptic Curve Cryptography

[4] Bendel, Mike (2010年12月29日). “Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access”. Exophase.com 2013年12月26日閲覧。

[5] Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack

[6] OpenSSL: News, ChangeLog

[7] “Android bug batters Bitcoin wallets”. The Register (2013年8月12日). 2013年12月26日閲覧。

[nist_curve_background-8] “RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE” (1999年7月). 2015年7月11日閲覧。

[9] “SafeCurves: Rigidity”. 2015年7月11日閲覧。

[10] 例えばMD5やSHA-2で撹拌のために用いられる定数テーブルは整数ラジアンの三角関数の値や素数の平方根や立方根の値を特定の形で用いており、意図的な操作の余地が少ない。

[11] “Exclusive: Secret contract tied NSA and security industry pioneer”. Reuters (2013年12月20日). 2015年7月11日閲覧。

[12] Daniel J. Bernstein, Tanja Lange (2013年5月31日). “Security dangers of the NIST curves”. 2015年7月11日閲覧。

[13] Maxwell, Gregory (2013年9月8日). “[tor-talk NIST approved crypto in Tor?]”. 2015年7月11日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]