楕円曲線DSA

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

DSAとの比較[編集]

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

署名生成[編集]

Parameter
CURVE 使用する楕円曲線
G ベースポイント(位数 n の巨大素数とともに楕円曲線を定義する)
n G の位数(n * G = O を満たす)

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

アリスは [1, n-1] の範囲からランダムに選択された秘密鍵 d_A と、公開鍵 Q_A = d_A * G から成る鍵ペアを生成する。ここで *楕円曲線上での掛け算 (scalar multiplication) を意味する。

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

  1. e = \textrm{HASH}(m) を計算する。ここで HASH は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\,\bmod\,n を計算する。r = 0 となる場合には k の選択に戻る。
  6. s = k^{-1}(z + r d_A)\,\bmod\,n を計算する。s = 0 となる場合には k の選択に戻る。
  7. (r, s)m に対する署名となる。

s を計算する際に、\textrm{HASH}(m) から得られる z は整数に変換される。zn より「大きい」ことは許されるが、「長い」ことは許されない[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 + r d_A) であるから、攻撃者は秘密鍵 d_A = \frac{s k - z}{r} を得ることができる。このように単一の k を用いることは不適切な実装であり、PlayStation 3のソフトウェア署名鍵が漏洩したのはこれが原因であった[2]

署名検証[編集]

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

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

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

  1. r および s がいずれも [1, n-1] の範囲にある整数であることを確認する。これを満たさない場合には署名は不正なものである。
  2. e = \textrm{HASH}(m) を計算する。ここで HASH は署名生成に用いられたハッシュ関数と同一のものである。
  3. z を、e の最上位側の L_n ビットとする。
  4. w = s^{-1}\,\bmod\,n を計算する。
  5. u_1 = zw\,\bmod\,n および u_2 = rw\,\bmod\,n を計算する。
  6. 曲線状の点 (x_1, y_1) = u_1 * G + u_2 * Q_A を計算する。
  7. 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 = (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 を計算可能とし、アルゴリズムを破綻させるものである[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 を導くことで回避できる。

脚注[編集]

参考文献[編集]

関連項目[編集]

外部リンク[編集]