楕円曲線DSA

楕円曲線DSA（だえんきょくせんDSA、"Elliptic Curve Digital Signature Algorithm"、"Elliptic Curve DSA"、楕円DSA、ECDSA）は、Digital Signature Algorithm (DSA) について楕円曲線暗号を用いるようにした変種である。
DSAとの比較.
楕円曲線暗号で一般的に言われるように、ECDSAにおいて必要とされる公開鍵のサイズはセキュリティビット数のおよそ2倍であると考えられている。例えば、80ビットのセキュリティビット数（攻撃者が秘密鍵を取得するために formula_1 回の計算を必要とする）を得るために、DSAでは最低でも1024ビットの公開鍵が必要であるが、ECDSAでは160ビットの公開鍵で十分である。一方、署名のサイズはDSAでもECDSAでも同じであり、必要とするビット安全性の4倍のビット長を要する（80ビットのビット安全性を保つためには320ビットの長さの署名が必要）。
署名生成.
アリスが署名したメッセージをボブに送る場合を考える。最初に、使用する楕円曲線のパラメータ formula_2 を決めておく必要がある。
アリスは formula_3 の範囲からランダムに選択された秘密鍵 formula_4 と、公開鍵 formula_5 から成る鍵ペアを生成する。ここで formula_6 は楕円曲線上での掛け算 (scalar multiplication) を意味する。
アリスがメッセージ formula_7 に署名する場合、以下の計算を行う。
formula_25 を計算する際に、formula_26 から得られる formula_9 は整数に変換される。formula_9 は formula_13 より「大きい」ことは許されるが、「長い」ことは許されない。
DSAと同様に、署名ごとに異なる formula_15 を選択することは極めて重要である。さもないと、ステップ6の式から秘密鍵 formula_4 を得ることが可能となってしまう。メッセージ formula_7 および formula_33 に対して、未知だが同じ formula_15 から得られた2つの署名 formula_23 および formula_36 がある場合、攻撃者は formula_9 および formula_38 を計算することが可能であり、formula_39 であることから、formula_40 が得られる。formula_41 であるから、攻撃者は秘密鍵 formula_42 を得ることができる。このように単一の formula_15 を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった。
署名検証.
ボブがアリスの署名を検証するためには、アリスの公開鍵 formula_44 が必要である。公開鍵 formula_44 が正当なものであるかの検証は以下のとおりである。
メッセージ formula_7 と署名 formula_23 の検証は以下のように行われる。
Straus's algorithm（Shamir's trickとも）を用いることで、2つの楕円曲線上での掛け算の和 formula_64 を、2つの楕円曲線上での掛け算よりも速く計算することができる。
アルゴリズムの正当性.
ここで formula_65 は署名検証のステップ6で得られた点とする。
formula_66
公開鍵が formula_5 と定義されることより
formula_68
楕円曲線上での掛け算より
formula_69
署名検証のステップ4より formula_70 および formula_71 の定義を拡張すると
formula_72
formula_73 を外に出して
formula_74
署名のステップ6より formula_25 の定義を拡張すると
formula_76
逆数の逆数は元と同じであることと、逆数と元の積は formula_47 であることから
formula_78
formula_52 の定義より、これは署名検証のステップ6と等しい。
これは正しく署名されたメッセージは正しく検証されることのみを示しており、セキュアな署名アルゴリズムであるための他の要素については考慮していない。
セキュリティ.
2010年12月、fail0verflowと名乗るグループが、ソニーがPlayStation 3のソフトウェア署名に用いていたECDSA秘密鍵の回復に成功したと発表した。しかし、これは formula_15 をランダムではなく固定値としていたソニーの不適切な実装によるものであり、アルゴリズム自体の脆弱性ではない。署名生成のセクションで述べたように、formula_15 を固定値で用いることは秘密鍵 formula_4 を計算可能とし、アルゴリズムを破綻させるものである。
2011年3月29日、2人の研究者による論文がに発表された。この論文では、サイドチャネル攻撃の一つであるタイミング攻撃によって、ECDSAを認証に利用し、OpenSSLを用いたサーバのTLS秘密鍵を入手可能であることが示された。この脆弱性はOpenSSL 1.0.0eで修正された。
2013年8月、Java class SecureRandomのいくつかの実装において、formula_15 のコリジョンが発生することがあるバグが明らかとなった。前述のように、これにより秘密鍵を得ることが可能であり、Javaを利用しECDSAを認証に用いていたAndroidアプリからBitcoinが盗まれる危険性があった。この問題は、RFC 6979にあるように、秘密鍵とメッセージハッシュから決定論的に formula_15 を導くことで回避できる。
このアルゴリズムは楕円曲線をパラメータとして必要とするが、多くの場合NISTによって定められた楕円曲線（P-256、P-384、P-521など）が用いられる。これらの曲線は特定のシード値からSHA-1を基盤としたアルゴリズムを用いて算出されているが、シード値の根拠が不明であること、また同じく固定の楕円曲線を用いたアルゴリズムであるにNSAがバックドアを仕込んだ上でRSAセキュリティ社のセキュリティ製品に採用させたと報道されたことから、疑いの目で見られることがある。
実装ライブラリ.
ECDSAをサポートしているライブラリは以下の通りである。