エドワーズ曲線デジタル署名アルゴリズムのソースを表示

{{Infobox Encryption method
| name           = EdDSA
| image          = 
| caption        = 
<!-- General -->
| designers      = [[ダニエル・バーンスタイン]]、Niels Duif、[[:en:Tanja Lange|Tanja Lange]]、Peter Schwabe、Bo-Yin Yang、et. al.
| publish date   = 2011-09-26
| series         = 
| derived from   = 
| derived to     = 
| related to     = 
| certification  = 
<!-- Detail -->
| digest size    = 
| block size     = 
| structure      = [[楕円曲線暗号]]
| rounds         = 
| cryptanalysis  = 
}}

'''エドワーズ曲線デジタル署名アルゴリズム'''（エドワーズきょくせんデジタルしょめいあるごりずむ、{{lang-en|Edwards-curve Digital Signature Algorithm}}、略称：'''EdDSA'''）は、[[公開鍵暗号]]において、{{仮リンク|ツイステッドエドワーズ曲線|en|Twisted Edwards curve}}に基づく{{仮リンク|シュノア署名|en|Schnorr signature}}の一種を用いた[[デジタル署名]]の一つである<ref name="RFC8032">{{cite IETF
| title=Edwards-Curve Digital Signature Algorithm (EdDSA)
| rfc=8032
| issn=2070-1721
| first1=S. | last1=Josefsson
| first2=I. | last2=Liusvaara
|date=January 2017
| publisher=[[Internet Engineering Task Force]]
| access-date=2017-07-31
}}</ref>。他のデジタル署名において見つかっている安全性に関する問題を回避した上で、高効率で暗号化処理が行われるように設計されている。エドワーズ曲線電子署名アルゴリズムは、[[ダニエル・バーンスタイン]]が率いるチームによって開発された <ref name="DJB">{{cite paper|last1=Bernstein|first1=Daniel J.|authorlink1=Daniel J. Bernstein|last2=Duif|first2=Niels|last3=Lange|first3=Tanja|last4=Schwabe|first4=Peter|author5=Bo-Yin Yang|title=High-speed high-security signatures|date=2011-09-26|url=http://ed25519.cr.yp.to/ed25519-20110926.pdf|format=PDF}}</ref>。
<!-- Abstract
In [[public-key cryptography]], '''Edwards-curve Digital Signature Algorithm (EdDSA)''' is a [[digital signature]] scheme using a variant of [[Schnorr signature]] based on [[Twisted Edwards curve]]s. It is designed for high performance while avoiding security problems that have surfaced in other digital signature schemes. It was developed by a team led by [[Daniel J. Bernstein]].<ref name="DJB">{{cite paper|last1=Bernstein|first1=Daniel J.|authorlink1=Daniel J. Bernstein|last2=Duif|first2=Niels|last3=Lange|first3=Tanja|last4=Schwabe|first4=Peter|author5=Bo-Yin Yang|title=High-speed high-security signatures|date=2011-09-26|url=http://ed25519.cr.yp.to/ed25519-20110926.pdf|format=PDF}}</ref> -->

== 概要 ==
EdDSAのアルゴリズムは以下のように表すことができる。簡単のため、整数や曲線上の点をどのようにビット列に符号化するかといった詳細は省略している。詳細については、引用文献やRFCを参照のこと<ref>{{cite techreport |author=Daniel J. Bernstein |author2=Simon Josefsson |author3=Tanja Lange |author4=Peter Schwabe |author5=Bo-Yin Yang|title=EdDSA for more curves|date=2015-07-04|url=https://ed25519.cr.yp.to/eddsa-20150704.pdf|access-date=2016-11-14}}</ref><ref name="DJB"/><ref name="RFC8032"/>。

'''EdDSA'''方式は、次のパラメータを用いる。

* <math>\mathbb{F}_q</math>：奇素数のべきである <math>q</math> を位数として持つ[[有限体]]。
* <math>E(\mathbb{F}_q)</math>：<math>\mathbb{F}_q</math> 上の[[楕円曲線]]．<!-- [[有理点|<math>\mathbb{F}_q</math>-有理点]] --> ただし、位数は大きな素数 <math>\ell</math> と適当な自然数 <math>c</math> によって <math>\#E(\mathbb{F}_q) = 2^c \ell</math> で表せる必要がある。<math>2^c</math> は cofactor と呼ばれる。
* <math>B \in E(\mathbb{F}_q)</math>：ベースポイント。位数が <math>\ell</math> である楕円曲線上の点。
* <math>H</math>：出力が <math>2b</math> ビットである[[ハッシュ関数]]。ただし、<math>b</math> は <math>2^{b - 1} > q</math> を満たす整数。したがって、<math>\mathbb{F}_q</math> と楕円曲線 <math>E(\mathbb{F}_q)</math> 上の点は、<math>b</math> ビットで表すことができる。

これらのパラメータは、EdDSA署名方式の全てのユーザが共通で使うことができる。ベースポイントの選択は任意だが、その他のパラメータの選択はEdDSA署名方式の安全性に大きく影響を与える。例えば、[[ポラード・ロー離散対数アルゴリズム]]を用いて離散対数を計算するのに必要な楕円加算回数はおよそ <math>\sqrt{\ell\pi/4}</math> 回である<ref>{{cite techreport |author=Daniel J. Bernstein |author2=Tanja Lange |author3=Peter Schwabe|title=On the correct use of the negation map in the Pollard rho method|publisher=IACR Cryptology ePrint Archive|number=2011/003|date=2011-01-01|url=https://eprint.iacr.org/2011/003|access-date=2016-11-14}}</ref>。したがって、このアルゴリズムで離散対数を解くことが事実上できないように <math>\ell</math> は十分大きくなければならない。典型的には、<math>\ell</math> は <math>2^{200}</math> より大きい値を用いる<ref>{{cite web |author=Daniel J. Bernstein |author2=Tanja Lange|title=ECDLP Security: Rho|series=SafeCurves: choosing safe curves for elliptic-curve cryptography|url=https://safecurves.cr.yp.to/rho.html|access-date=2016-11-16}}</ref>。<math>\ell</math> の選択は <math>q</math> の選択によって制限を受ける。[[楕円曲線のハッセの定理|Hasseの定理]]により、位数<math>\#E(\mathbb{F}_q) = 2^c \ell</math> は、<math>q + 1</math> から <math>2\sqrt{q}</math> 以上離れることができないためである。ハッシュ関数 <math>H</math> は、EdDSAの安全性解析においては通常[[ランダムオラクル]]と想定される。HashEdDSAという変種（variant）においては、<math>H</math> に加え、{{Ill|衝突耐性|en|Collision resistance}}を持つハッシュ関数<math>H'</math>も必要である。

鍵生成、署名生成、署名検証の方法は以下の通りである。<math>\parallel</math> はビット列の[[連結]]を表す。

; 署名鍵
: 一様ランダムに選んだ <math>b</math> ビット列 <math>k</math>。
; 公開鍵
: 署名鍵 <math>k</math> から <math>s = H_{0,\dots,b - 1}(k)</math> （ハッシュ値の下位 <math>b</math> ビット）を計算し、楕円曲線上の点 <math>A = s B\in E(\mathbb{F}_q)</math> を公開鍵とする。<math>b</math> ビット列で表される。
; 署名
: メッセージ <math>M</math> に対する署名は、楕円曲線上の点  <math>R</math> と <math>\ell</math> 未満の正整数 <math>S</math> のペア   <math>(R, S)</math> で表される。（共に <math>b</math> ビットで表せるため、署名長は <math>2b</math> ビット。）これを得るためには、まず署名鍵 <math>k</math> から <math>k'=H_{b,\dots,2b - 1}(k) </math>（ハッシュ値の上位 <math>b</math> ビット）を計算し、<math>r = H(k'\parallel M)</math> を計算する。これを用いて以下を計算する。
<math display="block">R = r B</math><math display="block">S = r + H(R \parallel A \parallel M) s \bmod \ell</math>
; 署名の検証
: 次の式が成り立つことを確認する。
<math display="block">2^c S B = 2^c R + 2^c H(R \parallel A \parallel M) A</math>

署名の生成方法と、位数が <math>\ell 2^c</math> であることから、正しく作られた署名は必ず検証を通る。すなわち：
<math display="block">
\begin{align}
2^c S B &= 2^c (r + H(R \parallel A \parallel M) s) B \\
        &= 2^c r B + 2^c H(R \parallel A \parallel M) s B \\
        &= 2^c R + 2^c H(R \parallel A \parallel M) A.
\end{align}
</math>

== Ed25519 ==
'''Ed25519'''は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数として[[SHA-2|SHA-512（SHA-2）]]を使い、曲線として[[Curve25519]]を用いている。各パラメータは以下の通り。
* <math>q = 2^{255} - 19</math>
* <math>E(\mathbb{F}_q)</math> は{{仮リンク|ツイステッドエドワーズ曲線|en|Twisted Edwards curve}}
<math display="block">-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2,</math>
* <math>\ell = 2^{252} + 27742317777372353535851937790883648493</math> および <math>c = 3</math>
* <math>B</math> は <math>E(\mathbb{F}_q)</math> 上の点のうち、<math>y</math> 座標が <math>4/5</math> であり <math>x</math> 座標が正である点。<BR>ただし、"正"とは、点を符号化したビット列について次のように定義される：
** "正"：座標が偶数（最下位ビットが0）
** "負"：座標が奇数（最下位ビットが1）
* <math>H</math> は [[SHA-512]]。したがって <math>b = 256</math> である。

曲線 <math>E(\mathbb{F}_q)</math> は、[[Curve25519]]として知られている{{仮リンク|モンゴメリ型楕円曲線|en|Montgomery curve}}と[[双有理幾何学|双有理同値]]である。具体的な同値は<math display="block">x = \sqrt{-486664}u/v, \quad y=(u-1)/(u+1)</math> で与えられる <ref name="DJB" /><ref>{{cite paper|last1=Bernstein|first1=Daniel J.|authorlink1=Daniel J. Bernstein|last2=Lange|first2=Tanja|title=Faster addition and doubling on elliptic curves|date=2007|pages=29–50|url=http://eprint.iacr.org/2007/286}}</ref>。

=== 性能 ===
Ed25519は、[[x86-64]] [[Nehalemマイクロアーキテクチャ|Nehalem]]/{{Ill|Westmere (マイクロアーキテクチャ)|en|Westmere (microarchitecture)|label=Westmere}}プロセッサファミリー向けに最適化されている。検証は、64個の署名を一括で処理することでよりスループットを向上させることができる。Ed25519 は、128ビット安全性を持つ[[共通鍵暗号|共通鍵暗号系]]と同等の攻撃耐性を提供することを目的としている。公開鍵は256ビット、署名は512ビットである<ref>{{cite web
| url=https://ed25519.cr.yp.to/
| title=Ed25519: high-speed high-security signatures
| date=2017-01-22
| author=Daniel J. Bernstein
| quote=This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc.
| access-date=2019-09-27}}</ref>。

=== コーディングの安全性 ===
安全性に関しては、Ed25519では、秘密のデータに依存した分岐命令と配列参照が用いられておらず、多くの[[サイドチャネル攻撃]]に耐性がある。

他の離散対数問題ベースの署名方式と同様に、EdDSAは署名毎に異なる[[nonce]]と呼ばれる秘密情報が用いられる。[[DSA]]と[[ECDSA]]においては、このnonceは署名生成ごとにランダムに生成されるのが一般的である。しかし、もし脆弱な乱数生成方法が用いられてnonceを推測可能であるときには、署名が秘密鍵の情報を漏らしてしまう。例えば、ソニーの[[PlayStation 3]]の署名鍵が漏洩した事例がある<ref>{{cite news|last=Johnston|first=Casey|title=PS3 hacked through poor cryptography implementation|newspaper=Ars Technica|date=2010-12-30|url=https://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/|access-date=2016-11-15}}</ref><ref>{{cite conference|author=fail0verflow|title=Console Hacking 2010: PS3 Epic Fail|conference=[[Chaos Communication Congress]]|date=2010-12-29|url=https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf|access-date=2016-11-15|archive-url=https://web.archive.org/web/20181026183945/https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf|archive-date=2018-10-26|url-status=dead}}</ref><ref>{{cite web
| url=https://www.cs.cmu.edu/~dst/GeoHot/1780_27c3_console_hacking_2010.pdf
| title=27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail
| access-date=2019-08-04}}</ref>。

これに対し、EdDSAでは秘密鍵とメッセージのハッシュ値からnonceを確定的に決めるという方法を取っている。これにより、秘密鍵をランダムに作成すれば、その後の署名生成時には乱数を使う必要がなく、脆弱な乱数生成方法を用いることによる秘密鍵の漏洩のリスクが存在しない。

=== 標準化と実装の矛盾 ===
EdDSAには2つの標準化が存在する。1つは[[IETF]]による {{IETF RFC|8032}} であり、もう1つは[[NIST]]によるFIPS 186-5 (2019).<ref name="FIPS 186-5">{{cite web |title=FIPS 186-5 (Draft): Digital Signature Standard (DSS) |date=October 2019 |publisher=[[NIST]] |doi=10.6028/NIST.FIPS.186-5-draft |url=https://csrc.nist.gov/publications/detail/fips/186/5/draft |access-date=2022-08-03}}</ref>である。これらの標準の間の違いについての解析が既に報告されており<ref>{{cite conference|author=Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko |title=Taming the many EdDSAs|conference=Security Standardisation Research Conference (SSR 2020)|date=2020-10-01|url=https://eprint.iacr.org/2020/1244|access-date=2022-08-03}}</ref><ref>{{cite conference|author=Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao |title=The provable security of ed25519: Theory and practice|conference=IEEE Symposium on Security and Privacy (S&P 2021)|date=2020-07-03|url=https://eprint.iacr.org/2020/823|access-date=2022-08-03}}</ref>、テストベクタも利用可能である<ref>{{cite web|url=https://github.com/novifinancial/ed25519-speccheck| title=ed25519-speccheck| access-date=2022-08-03}}</ref>

=== ソフトウェア ===
Ed25519の主要な使用例には、[[OpenSSH]], [[GnuPG]]とさまざまな代替ソフトウェア <ref>{{cite web|title=Things that use Ed25519|url=http://ianix.com/pub/ed25519-deployment.html|accessdate=6 January 2015}}</ref>、そして、[[OpenBSD]]で提供されているデジタル署名・署名検証ツールsignifyがある <ref>{{cite web|title=マイナビニュース：OpenBSD、デジタル署名付きパッケージシステムに|url=https://news.mynavi.jp/techplus/article/20140120-a240/|accessdate=2 February 2015}}</ref> 。

* SUPERCOPの[http://bench.cr.yp.to/supercop.html リファレンス実装]（インライン[[アセンブリ言語|アセンブリ]]を含む[[C言語]]）
* 速度は遅いが簡潔な[http://ed25519.cr.yp.to/python/ed25519.py 別実装]。ただし、[[サイドチャネル攻撃]]への耐性はない<ref>{{cite web|title=Alternate implementations|url=http://ed25519.cr.yp.to/software.html|accessdate=17 November 2014}}</ref> （[[Python]]） 
* [[NaCl (ソフトウェア)|NaCl]]
* {{Ill|CryptoNote|en|CryptoNote}} [[暗号通貨]][[プロトコル]]

*[[wolfSSL]]<ref>{{Cite news|title=wolfSSL Embedded SSL/TLS Library {{!}} wolfSSL Products|url=https://www.wolfssl.jp/products/wolfssl/|accessdate=2018-11-12|language=ja-JP|work=wolfSSL}}</ref>
*[[OpenSSL]] 1.1.1<ref name="OpenSSL CHANGES">https://www.openssl.org/news/cl111.txt</ref>
<!--
== Software ==

Notable uses of Ed25519 include [[OpenSSH]], [[GnuPG]] and various alternatives, and the signify tool by [[OpenBSD]].<ref>{{cite web|title=Things that use Ed25519|url=http://ianix.com/pub/ed25519-deployment.html|accessdate=6 January 2015}}</ref>
* SUPERCOP [http://bench.cr.yp.to/supercop.html reference implementation] ([[C language]] with inline [[assembler (computing)|assembler]])
* Slow but concise [http://ed25519.cr.yp.to/python/ed25519.py alternate implementation], does not include [[side-channel attack]] protection<ref>{{cite web|title=Alternate implementations|url=http://ed25519.cr.yp.to/software.html|accessdate=17 November 2014}}</ref> ([[Python (programming language)|Python]]) 
* {{仮リンク|NaCl (ソフトウェア)|en|NaCl (software)}}
* [[CryptoNote]] [[cryptocurrency]] [[protocol]]
* [[OpenSSL]] 1.1.1 <ref>https://www.openssl.org/news/cl111.txt</ref>
-->

== Ed448 ==
'''Ed448'''は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数として[[SHA-3|SHAKE256]]を使い、曲線として[[Curve448]]を用いている。Ed25519と同様に、{{IETF RFC|8032}} に定義され、FIPS 186-5の草稿において推奨されている<ref name="FIPS 186-5"/>。

== 脚注 ==
{{reflist}}

== 関連項目 ==
* [[楕円曲線DSA]]
* [[Curve25519]]
* [[NaCl (ソフトウェア)]]

== 外部リンク ==
* [http://ed25519.cr.yp.to/ Ed25519 home page]
{{computer-stub}}
{{cryptography navbox|public-key}}
{{デフォルトソート:えとわあすきよくせんてしたるしよめいあるこりすむ}}
[[Category:暗号]]
[[Category:楕円曲線暗号]]
[[Category:デジタル署名方式]]
[[Category:ダニエル・バーンスタイン]]
[[Category:パブリックドメインソフトウェア]]