楕円曲線DSAのソースを表示

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

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

== 署名生成 ==
{| class="wikitable"
|-
! パラメーター
! 説明
|-
| align="center" | ''E'' || <math>\mathbb{R}^2</math> 上で定義される[[楕円曲線]] <math>y^2 = x^3 + ax + b</math> (ワイエルシュトラスの標準形)
|-
| align="center" | ''p'' || ''E'' 上の有理点を[[楕円曲線暗号#素数 p による還元|還元]]する素数。''E'' は<math>\mathbf{F}_p \times \mathbf{F}_p </math> 上の楕円曲線に写される
|-
| align="center" | ''G'' || <math>\mathbf{F}_p \times \mathbf{F}_p </math> 上の[[楕円曲線暗号#離散対数と離散対数問題|ベースポイント]]
|-
| align="center" | ''n'' || ''G'' の位数（<math>n * G = O</math> を満たす）
|-
| align="center" |<math>d_A</math>
|秘密鍵：<math>[1, n-1]</math>の範囲からランダムに選択され保持される整数
|-
| align="center" |<math>Q_A</math>
|公開鍵：<math>d_A * G</math> (<math>\mathbf{F}_p \times \mathbf{F}_p </math> 上の点)
|-
| align="center" |''m''
|送信されるメッセージ
|}
(注)「<math>*</math>」は[[楕円曲線暗号#スカラー倍算|楕円曲線上での掛け算]] (scalar multiplication) を意味する。

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

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

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

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

<math>s</math> を計算する際に、<math>H(m)</math> から得られる <math>z</math> は整数に変換される。<math>z</math> は <math>n</math> より「大きい」ことは許されるが、「長い」ことは許されない<ref>
[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf FIPS 186-3, pp. 19 and 26]</ref>。

DSAと同様に、署名ごとに異なる <math>k</math> を選択することは極めて重要である。さもないと、ステップ6の式から秘密鍵 <math>d_A</math> を得ることが可能となってしまう。メッセージ <math>m</math> および <math>m'</math> に対して、未知だが同じ <math>k</math> から得られた2つの署名 <math>(r, s)</math> および <math>(r, s')</math> がある場合、攻撃者は <math>z</math> および <math>z'</math> を計算することが可能であり、<math>s - s' = k^{-1}(z - z')</math> であることから、<math>k = \frac{z - z'}{s - s'}</math> が得られる。<math>s = k^{-1}(z + r d_A)</math> であるから、攻撃者は秘密鍵 <math>d_A = \frac{s k - z}{r}</math> を得ることができる。このように単一の <math>k</math> を用いることは不適切な実装であり、[[PlayStation 3]]のソフトウェア署名鍵が漏洩したのはこれが原因であった<ref>
[http://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf Console Hacking 2010 - PS3 Epic Fail], page 123–128</ref>。

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

# <math>Q_A</math> が <math>O</math> でないことを確認する。
# <math>Q_A</math> が曲線上にあることを確認する。
# <math>n * Q_A = O</math> であることを確認する。

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

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

[[Straus's algorithm]]（Shamir's trickとも）を用いることで、2つの楕円曲線上での掛け算の和 <math>u_1 * G + u_2 * Q_A</math> を、2つの楕円曲線上での掛け算よりも速く計算することができる<ref>[http://www.lirmm.fr/~imbert/talks/laurent_Asilomar_08.pdf The Double-Base Number System in Elliptic Curve Cryptography]</ref>。

== アルゴリズムの正当性 ==
ここで <math>C</math> は署名検証のステップ6で得られた点とする。

<math>C = u_1 * G + u_2 * Q_A</math>

公開鍵が <math>Q_A = d_A * G</math> と定義されることより

<math>C = u_1 * G + u_2 d_A * G</math>

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

<math>C = (u_1 + u_2 d_A) * G</math>

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

<math>C = (z s^{-1} + r d_A s^{-1}) * G</math>

<math>s^{-1}</math> を外に出して

<math>C = (z + r d_A) s^{-1} * G</math>

署名のステップ6より <math>s</math> の定義を拡張すると

<math>C = (z + r d_A) (z + r d_A)^{-1} (k^{-1})^{-1} * G</math>

逆数の逆数は元と同じであることと、逆数と元の積は <math>O</math> であることから

<math>C = k * G</math>

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

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

== セキュリティ ==
2010年12月、fail0verflowと名乗るグループが、[[ソニー]]が[[PlayStation 3]]のソフトウェア署名に用いていたECDSA秘密鍵の回復に成功したと発表した。しかし、これは <math>k</math> をランダムではなく固定値としていたソニーの不適切な実装によるものであり、アルゴリズム自体の脆弱性ではない。[[#署名生成|署名生成]]のセクションで述べたように、<math>k</math> を固定値で用いることは秘密鍵 <math>d_A</math> を計算可能とし、アルゴリズムを破綻させるものである<ref>{{Cite news|last=Bendel|first=Mike|title=Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access|publisher=Exophase.com|date=2010-12-29|url=http://exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/|accessdate=2013-12-26}}</ref>。

2011年3月29日、2人の研究者による論文が{{仮リンク|IACR|en|International Association for Cryptologic Research}}に発表された。この論文では、[[サイドチャネル攻撃]]の一つである[[タイミング攻撃]]によって、ECDSAを認証に利用し、[[OpenSSL]]を用いたサーバの[[Transport Layer Security|TLS]]秘密鍵を入手可能であることが示された<ref>[https://www.kb.cert.org/vuls/id/536044 Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack]</ref>。この脆弱性はOpenSSL 1.0.0eで修正された<ref>[http://www.openssl.org/news/changelog.html OpenSSL: News, ChangeLog]</ref>。

2013年8月、[[Java]] class [http://docs.oracle.com/javase/7/docs/api/java/security/SecureRandom.html SecureRandom]のいくつかの実装において、<math>k</math> のコリジョンが発生することがあるバグが明らかとなった。前述のように、これにより秘密鍵を得ることが可能であり、Javaを利用しECDSAを認証に用いていた[[Android (オペレーティングシステム)|Android]]アプリから[[Bitcoin]]が盗まれる危険性があった<ref>{{cite web |title=Android bug batters Bitcoin wallets 
| url= http://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/ |publisher=The Register |date=2013-08-12 |accessdate=2013-12-26}}</ref>。この問題は独立提出の{{IETF RFC|6979}}にあるように、秘密鍵とメッセージハッシュから決定論的に <math>k</math> を導くことで回避できる。

2015年1月、Bitcoinの[[ビットコイン#ウォレット|ウォレット]]が完全にオフラインであっても、ECDSAを利用した[[ビットコイン#トランザクション|トランザクション]]のデジタル署名を通して秘密鍵が漏洩される可能性があることを示す研究論文が[[ArXiv|arXiv]]にて発表された<ref>{{cite web |title=How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys |url=https://arxiv.org/pdf/1501.00447 |publisher=arXiv |date=2015-01-02 |accessdate=2025-02-1}}</ref>。この論文では、利用ユーザー側がECDSAおよびビットコインの実装を完全に検証できない限り信頼できないことから、ソースコードの検証からコンパイルといったユーザー側の敷居が高くなるため、プライベートキー漏洩の攻撃を防ぐための実質的な解決策が現段階でないと結論付けている。

このアルゴリズムは楕円曲線をパラメータとして必要とするが、多くの場合[[アメリカ国立標準技術研究所|NIST]]によって定められた楕円曲線（P-256、P-384、P-521など）<ref name="nist_curve_background">{{cite web |url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |title=RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE |date=1999-07 |accessdate=2015-07-11}}</ref>が用いられる。これらの曲線は特定のシード値から[[SHA-1]]を基盤としたアルゴリズムを用いて算出されている<ref name="nist_curve_background" />が、シード値の根拠が不明であること<ref>{{cite web |url=http://safecurves.cr.yp.to/rigid.html |title=SafeCurves: Rigidity |accessdate=2015-07-11}}</ref><ref>例えば[[MD5]]や[[SHA-2]]で撹拌のために用いられる定数テーブルは整数ラジアンの[[三角関数]]の値や[[素数]]の[[平方根]]や立方根の値を特定の形で用いており、意図的な操作の余地が少ない。</ref>、また同じく固定の楕円曲線を用いたアルゴリズムである{{仮リンク|Dual_EC_DRBG|en|Dual_EC_DRBG}}に[[アメリカ国家安全保障局|NSA]]がバックドアを仕込んだ上で[[RSAセキュリティ]]社のセキュリティ製品に採用させたと報道されたこと<ref>{{cite web |url=http://www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220 |publisher=Reuters |title=Exclusive: Secret contract tied NSA and security industry pioneer |date=2013-12-20 |accessdate=2015-07-11}}</ref>から、疑いの目で見られることがある<ref>{{cite web |url=https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf |title=Security dangers of the NIST curves |author=Daniel J. Bernstein, Tanja Lange |date=2013-05-31 |accessdate=2015-07-11}}</ref><ref>{{cite web |url=https://lists.torproject.org/pipermail/tor-talk/2013-September/029956.html |title = [tor-talk] NIST approved crypto in Tor? |date=2013-09-08 |accessdate=2015-07-11 |first=Gregory |last=Maxwell}}</ref>。

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

* [[Botan]]
* {{仮リンク|Bouncy Castle|en|Bouncy_Castle_(cryptography)}}
* {{仮リンク|cryptlib|en|Cryptlib}}
* {{仮リンク|Crypto++|en|Crypto++}}
* {{仮リンク|libgcrypt|en|Libgcrypt}}
* [[OpenSSL]]
* [[GnuTLS]]
* [[wolfCrypt]]

== 脚注 ==
{{reflist}}

== 参考文献 ==
* Accredited Standards Committee [http://www.x9.org 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, [http://www.secg.org/download/aid-780/sec1-v2.pdf ''Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography''], Version 2.0, May 21, 2009.
* López, J. and Dahab, R. [http://citeseer.ist.psu.edu/333066.html ''An Overview of Elliptic Curve Cryptography''], Technical Report IC-00-10, State University of Campinas, 2000.
* Daniel J. Bernstein, [http://cr.yp.to/papers/pippenger.pdf Pippenger's exponentiation algorithm], 2002.
* Daniel R. L. Brown, ''Generic Groups, Collision Resistance, and ECDSA'', Designs, Codes and Cryptography, '''35''', 119–152, 2005. [http://eprint.iacr.org/2002/026 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|year=2004|doi=10.1007/b97644}}

== 関連項目 ==
* [[楕円曲線暗号]]
* [[Digital Signature Algorithm]]

== 外部リンク ==
* [http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf Digital Signature Standard; includes info on ECDSA]

{{cryptography navbox|public-key}}
{{デフォルトソート:たえんきよくせんDSA}}
[[Category:暗号技術]]
[[Category:コンピュータ・ネットワーク・セキュリティ]]
[[Category:数学に関する記事]]
[[Category:楕円曲線暗号]]