エドワーズ曲線デジタル署名アルゴリズム

EdDSA
一般
設計者	ダニエル・バーンスタイン、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang、et. al.
初版発行日	2011-09-26
詳細
構造	楕円曲線暗号

エドワーズ曲線デジタル署名アルゴリズム（エドワーズきょくせんデジタルしょめいあるごりずむ、英語: Edwards-curve Digital Signature Algorithm、略称：EdDSA）は、公開鍵暗号において、ツイステッドエドワーズ曲線（英語版）に基づくシュノア署名（英語版）の一種を用いたデジタル署名の一つである^[1]。他のデジタル署名において見つかっている安全性に関する問題を回避した上で、高効率で暗号化処理が行われるように設計されている。エドワーズ曲線電子署名アルゴリズムは、ダニエル・バーンスタインが率いるチームによって開発された ^[2]。

概要

EdDSAのアルゴリズムは以下のように表すことができる。簡単のため、整数や曲線上の点をどのようにビット列に符号化するかといった詳細は省略している。詳細については、引用文献やRFCを参照のこと^[3]^[2]^[1]。

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

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

これらのパラメータは、EdDSA署名方式の全てのユーザが共通で使うことができる。ベースポイントの選択は任意だが、その他のパラメータの選択はEdDSA署名方式の安全性に大きく影響を与える。例えば、ポラード・ロー離散対数アルゴリズムを用いて離散対数を計算するのに必要な楕円加算回数はおよそ ${\sqrt {\ell \pi /4}}$ 回である^[4]。したがって、このアルゴリズムで離散対数を解くことが事実上できないように $\ell$ は十分大きくなければならない。典型的には、 $\ell$ は $2^{200}$ より大きい値を用いる^[5]。 $\ell$ の選択は $q$ の選択によって制限を受ける。Hasseの定理により、位数 $\#E(\mathbb {F} _{q})=2^{c}\ell$ は、 $q+1$ から $2{\sqrt {q}}$ 以上離れることができないためである。ハッシュ関数 $H$ は、EdDSAの安全性解析においては通常ランダムオラクルと想定される。HashEdDSAという変種（variant）においては、 $H$ に加え、衝突耐性（英語版）を持つハッシュ関数 $H'$ も必要である。

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

署名鍵: 一様ランダムに選んだ $b$ ビット列 $k$ 。
公開鍵: 署名鍵 $k$ から $s=H_{0,\dots ,b-1}(k)$ （ハッシュ値の下位 $b$ ビット）を計算し、楕円曲線上の点 $A=sB\in E(\mathbb {F} _{q})$ を公開鍵とする。 $b$ ビット列で表される。
署名: メッセージ $M$ に対する署名は、楕円曲線上の点 $R$ と $\ell$ 未満の正整数 $S$ のペア $(R,S)$ で表される。（共に $b$ ビットで表せるため、署名長は $2b$ ビット。）これを得るためには、まず署名鍵 $k$ から $k'=H_{b,\dots ,2b-1}(k)$ （ハッシュ値の上位 $b$ ビット）を計算し、 $r=H(k'\parallel M)$ を計算する。これを用いて以下を計算する。

R=rB

S=r+H(R\parallel A\parallel M)s{\bmod {\ell }}

署名の検証: 次の式が成り立つことを確認する。

2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A

署名の生成方法と、位数が $\ell 2^{c}$ であることから、正しく作られた署名は必ず検証を通る。すなわち：

{\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}

Ed25519

Ed25519は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数としてSHA-512（SHA-2）を使い、曲線としてCurve25519を用いている。各パラメータは以下の通り。

$q=2^{255}-19$
$E(\mathbb {F} _{q})$ はツイステッドエドワーズ曲線（英語版）

-x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},

$\ell =2^{252}+27742317777372353535851937790883648493$ および $c=3$
$B$ $B$ は $E(\mathbb {F} _{q})$ $E(\mathbb {F} _{q})$ 上の点のうち、 $y$ $y$ 座標が $4/5$ $4/5$ であり $x$ $x$ 座標が正である点。
ただし、"正"とは、点を符号化したビット列について次のように定義される：
- "正"：座標が偶数（最下位ビットが0）
- "負"：座標が奇数（最下位ビットが1）
$H$ は SHA-512。したがって $b=256$ である。

曲線 $E(\mathbb {F} _{q})$ は、Curve25519として知られているモンゴメリ型楕円曲線（英語版）と双有理同値である。具体的な同値は

x={\sqrt {-486664}}u/v,\quad y=(u-1)/(u+1)

で与えられる ^[2]^[6]。

性能

Ed25519は、x86-64 Nehalem/Westmere（英語版）プロセッサファミリー向けに最適化されている。検証は、64個の署名を一括で処理することでよりスループットを向上させることができる。Ed25519 は、128ビット安全性を持つ共通鍵暗号系と同等の攻撃耐性を提供することを目的としている。公開鍵は256ビット、署名は512ビットである^[7]。

コーディングの安全性

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

他の離散対数問題ベースの署名方式と同様に、EdDSAは署名毎に異なるnonceと呼ばれる秘密情報が用いられる。DSAとECDSAにおいては、このnonceは署名生成ごとにランダムに生成されるのが一般的である。しかし、もし脆弱な乱数生成方法が用いられてnonceを推測可能であるときには、署名が秘密鍵の情報を漏らしてしまう。例えば、ソニーのPlayStation 3の署名鍵が漏洩した事例がある^[8]^[9]^[10]。

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

標準化と実装の矛盾

EdDSAには2つの標準化が存在する。1つはIETFによる RFC 8032 であり、もう1つはNISTによるFIPS 186-5 (2019).^[11]である。これらの標準の間の違いについての解析が既に報告されており^[12]^[13]、テストベクタも利用可能である^[14]

ソフトウェア

Ed25519の主要な使用例には、OpenSSH, GnuPGとさまざまな代替ソフトウェア ^[15]、そして、OpenBSDで提供されているデジタル署名・署名検証ツールsignifyがある ^[16] 。

SUPERCOPのリファレンス実装（インラインアセンブリを含むC言語）
速度は遅いが簡潔な別実装。ただし、サイドチャネル攻撃への耐性はない^[17] （Python）
NaCl
CryptoNote（英語版）暗号通貨プロトコル

wolfSSL^[18]
OpenSSL 1.1.1^[19]

Ed448

Ed448は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数としてSHAKE256を使い、曲線としてCurve448を用いている。Ed25519と同様に、RFC 8032 に定義され、FIPS 186-5の草稿において推奨されている^[11]。

脚注

^ ^a ^b Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA) (英語). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070-1721. RFC 8032. 2017年7月31日閲覧。
^ ^a ^b ^c Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2011-09-26) (PDF). High-speed high-security signatures.
^ Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang (4 July 2015). EdDSA for more curves (PDF) (Technical report). 2016年11月14日閲覧。
^ Daniel J. Bernstein; Tanja Lange; Peter Schwabe (1 January 2011). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. 2016年11月14日閲覧。
^ Daniel J. Bernstein. “ECDLP Security: Rho”. 2016年11月16日閲覧。
^ Bernstein, Daniel J.; Lange, Tanja (2007). Faster addition and doubling on elliptic curves. pp. 29–50. http://eprint.iacr.org/2007/286.
^ Daniel J. Bernstein (2017年1月22日). “Ed25519: high-speed high-security signatures”. 2019年9月27日閲覧。 “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.”
^ Johnston, Casey (2010年12月30日). “PS3 hacked through poor cryptography implementation”. Ars Technica 2016年11月15日閲覧。
^ fail0verflow (29 December 2010). Console Hacking 2010: PS3 Epic Fail (PDF). Chaos Communication Congress. 2018年10月26日時点のオリジナル (PDF)よりアーカイブ。2016年11月15日閲覧。
^ “27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail”. 2019年8月4日閲覧。
^ ^a ^b “FIPS 186-5 (Draft): Digital Signature Standard (DSS)”. NIST (2019年10月). doi:10.6028/NIST.FIPS.186-5-draft. 2022年8月3日閲覧。
^ Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (1 October 2020). Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). 2022年8月3日閲覧。
^ Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (3 July 2020). The provable security of ed25519: Theory and practice. IEEE Symposium on Security and Privacy (S&P 2021). 2022年8月3日閲覧。
^ “ed25519-speccheck”. 2022年8月3日閲覧。
^ “Things that use Ed25519”. 2015年1月6日閲覧。
^ “マイナビニュース：OpenBSD、デジタル署名付きパッケージシステムに”. 2015年2月2日閲覧。
^ “Alternate implementations”. 2014年11月17日閲覧。
^ “wolfSSL Embedded SSL/TLS Library | wolfSSL Products” (日本語). wolfSSL 2018年11月12日閲覧。
^ https://www.openssl.org/news/cl111.txt

外部リンク

Ed25519 home page

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[RFC8032-1] Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA) (英語). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070-1721. RFC 8032. 2017年7月31日閲覧。

[DJB-2] Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Bo-Yin Yang (2011-09-26) (PDF). High-speed high-security signatures.

[3] Daniel J. Bernstein; Simon Josefsson; Tanja Lange; Peter Schwabe; Bo-Yin Yang (4 July 2015). EdDSA for more curves (PDF) (Technical report). 2016年11月14日閲覧。

[4] Daniel J. Bernstein; Tanja Lange; Peter Schwabe (1 January 2011). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. 2016年11月14日閲覧。

[5] Daniel J. Bernstein. “ECDLP Security: Rho”. 2016年11月16日閲覧。

[6] Bernstein, Daniel J.; Lange, Tanja (2007). Faster addition and doubling on elliptic curves. pp. 29–50. http://eprint.iacr.org/2007/286.

[7] Daniel J. Bernstein (2017年1月22日). “Ed25519: high-speed high-security signatures”. 2019年9月27日閲覧。 “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.”

[8] Johnston, Casey (2010年12月30日). “PS3 hacked through poor cryptography implementation”. Ars Technica 2016年11月15日閲覧。

[9] 0verflow (29 December 2010). Console Hacking 2010: PS3 Epic Fail (PDF). Chaos Communication Congress. 2018年10月26日時点のオリジナル (PDF)よりアーカイブ。2016年11月15日閲覧。

[10] “27th Chaos Communication Congress: Console Hacking 2010: PS3 Epic Fail”. 2019年8月4日閲覧。

[FIPS_186-5-11] “FIPS 186-5 (Draft): Digital Signature Standard (DSS)”. NIST (2019年10月). doi:10.6028/NIST.FIPS.186-5-draft. 2022年8月3日閲覧。

[12] Konstantinos Chalkias, Francois Garillot and Valeria Nikolaenko (1 October 2020). Taming the many EdDSAs. Security Standardisation Research Conference (SSR 2020). 2022年8月3日閲覧。

[13] Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao (3 July 2020). The provable security of ed25519: Theory and practice. IEEE Symposium on Security and Privacy (S&P 2021). 2022年8月3日閲覧。

[14] “ed25519-speccheck”. 2022年8月3日閲覧。

[15] “Things that use Ed25519”. 2015年1月6日閲覧。

[16] “マイナビニュース：OpenBSD、デジタル署名付きパッケージシステムに”. 2015年2月2日閲覧。

[17] “Alternate implementations”. 2014年11月17日閲覧。

[18] “wolfSSL Embedded SSL/TLS Library | wolfSSL Products” (日本語). wolfSSL 2018年11月12日閲覧。

[OpenSSL_CHANGES-19] ttps://www.openssl.org/news/cl111.txt

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

概要