楕円曲線DSA
楕円曲線DSA(だえんきょくせんDSA、Elliptic Curve Digital Signature Algorithm、Elliptic Curve DSA、楕円DSA、ECDSA)は、Digital Signature Algorithm (DSA) について楕円曲線暗号を用いるようにした変種である。
楕円曲線暗号で一般的に言われるように、ECDSAにおいて必要とされる公開鍵のサイズはセキュリティビット数のおよそ2倍であると考えられている。例えば、80ビットのセキュリティビット数(攻撃者が秘密鍵を取得するために 2^{80} 回の計算を必要とする)を得るために、DSAでは最低でも1024ビットの公開鍵が必要であるが、ECDSAでは160ビットの公開鍵で十分である。一方、署名のサイズはDSAでもECDSAでも同じであり、必要とするビット安全性の4倍のビット長を要する(80ビットのビット安全性を保つためには320ビットの長さの署名が必要)。
アリスが署名したメッセージをボブに送る場合を考える。最初に、使用する楕円曲線のパラメータ (CURVE, G, n) を決めておく必要がある。
アリスは [1, n-1] の範囲からランダムに選択された秘密鍵 d_A と、公開鍵 Q_A = d_A * G から成る鍵ペアを生成する。ここで * は楕円曲線上での掛け算 (scalar multiplication) を意味する。
アリスがメッセージ m に署名する場合、以下の計算を行う。
e = \textrm{HASH}(m) を計算する。ここで HASH は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 + r d_A)\,\bmod\,n を計算する。s = 0 となる場合には k の選択に戻る。
(r, s) が m に対する署名となる。
s を計算する際に、\textrm{HASH}(m) から得られる z は整数に変換される。z は n より「大きい」ことは許されるが、「長い」ことは許されない。
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 + r d_A) であるから、攻撃者は秘密鍵 d_A = \frac{s k - z}{r} を得ることができる。このように単一の k を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった。
ボブがアリスの署名を検証するためには、アリスの公開鍵 Q_A が必要である。公開鍵 Q_A が正当なものであるかの検証は以下のとおりである。
Q_A が O でないことを確認する。
Q_A が曲線上にあることを確認する。
n * Q_A = O であることを確認する。
メッセージ m と署名 (r, s) の検証は以下のように行われる。
r および s がいずれも [1, n-1] の範囲にある整数であることを確認する。これを満たさない場合には署名は不正なものである。
e = \textrm{HASH}(m) を計算する。ここで HASH は署名生成に用いられたハッシュ関数と同一のものである。
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つの楕円曲線上での掛け算よりも速く計算することができる。
ここで 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人の研究者による論文がIACRに発表された。この論文では、サイドチャネル攻撃の一つであるタイミング攻撃によって、ECDSAを認証に利用し、OpenSSLを用いたサーバのTLS秘密鍵を入手可能であることが示された。この脆弱性はOpenSSL 1.0.0eで修正された。
2013年8月、Java class のいくつかの実装において、k のコリジョンが発生することがあるバグが明らかとなった。前述のように、これにより秘密鍵を得ることが可能であり、Javaを利用しECDSAを認証に用いていたAndroidアプリからBitcoinが盗まれる危険性があった。この問題は、RFC 6979にあるように、秘密鍵とメッセージハッシュから決定論的に k を導くことで回避できる。
このアルゴリズムは楕円曲線をパラメータとして必要とするが、多くの場合NISTによって定められた楕円曲線(P-256、P-384、P-521など)が用いられる。これらの曲線は特定のシード値からSHA-1を基盤としたアルゴリズムを用いて算出されているが、シード値の根拠が不明であること、また同じく固定の楕円曲線を用いたアルゴリズムであるDual_EC_DRBGにNSAがバックドアを仕込んだ上でRSAセキュリティ社のセキュリティ製品に採用させたと報道されたことから、疑いの目で見られることがある。
ECDSAをサポートしているライブラリは以下の通りである。