EdDSA一般
設計者ダニエル・バーンスタイン、Niels Duif、Tanja Lange
エドワーズ曲線デジタル署名アルゴリズム（エドワーズきょくせんデジタルしょめいあるごりずむ、英語: Edwards-curve Digital Signature Algorithm、略称：EdDSA）は、公開鍵暗号において、ツイステッドエドワーズ曲線（英語版）に基づくシュノア署名（英語版）の一種を用いたデジタル署名の一つである[1]。他のデジタル署名において見つかっている安全性に関する問題を回避した上で、高効率で暗号化処理が行われるように設計されている。エドワーズ曲線電子署名アルゴリズムは、ダニエル・バーンスタインが率いるチームによって開発された [2]。 EdDSAのアルゴリズムは以下のように表すことができる。簡単のため、整数や曲線上の点をどのようにビット列に符号化するかといった詳細は省略している。詳細については、引用文献やRFCを参照のこと[3][2][1]。 EdDSA方式は、次のパラメータを用いる。 これらのパラメータは、EdDSA署名方式の全てのユーザが共通で使うことができる。ベースポイントの選択は任意だが、その他のパラメータの選択はEdDSA署名方式の安全性に大きく影響を与える。例えば、ポラード・ロー離散対数アルゴリズムを用いて離散対数を計算するのに必要な楕円加算回数はおよそ ℓ π / 4 {\displaystyle {\sqrt {\ell \pi /4}}} 回である[4]。したがって、このアルゴリズムで離散対数を解くことが事実上できないように ℓ {\displaystyle \ell } は十分大きくなければならない。典型的には、 ℓ {\displaystyle \ell } は 2 200 {\displaystyle 2^{200}} より大きい値を用いる[5]。 ℓ {\displaystyle \ell } の選択は q {\displaystyle q} の選択によって制限を受ける。Hasseの定理により、位数 # E ( F q ) = 2 c ℓ {\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell } は、 q + 1 {\displaystyle q+1} から 2 q {\displaystyle 2{\sqrt {q}}} 以上離れることができないためである。ハッシュ関数 H {\displaystyle H} は、EdDSAの安全性解析においては通常ランダムオラクルと想定される。HashEdDSAという変種（variant）においては、 H {\displaystyle H} に加え、衝突耐性
概要
F q {\displaystyle \mathbb {F} _{q}} ：奇素数のべきである q {\displaystyle q} を位数として持つ有限体。
E ( F q ) {\displaystyle E(\mathbb {F} _{q})} ： F q {\displaystyle \mathbb {F} _{q}} 上の楕円曲線． ただし、位数は大きな素数 ℓ {\displaystyle \ell } と適当な自然数 c {\displaystyle c} によって # E ( F q ) = 2 c ℓ {\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell } で表せる必要がある。 2 c {\displaystyle 2^{c}} は cofactor と呼ばれる。
B ∈ E ( F q ) {\displaystyle B\in E(\mathbb {F} _{q})} ：ベースポイント。位数が ℓ {\displaystyle \ell } である楕円曲線上の点。
H {\displaystyle H} ：出力が 2 b {\displaystyle 2b} ビットであるハッシュ関数。ただし、 b {\displaystyle b} は 2 b − 1 > q {\displaystyle 2^{b-1}>q} を満たす整数。したがって、 F q {\displaystyle \mathbb {F} _{q}} と楕円曲線 E ( F q ) {\displaystyle E(\mathbb {F} _{q})} 上の点は、 b {\displaystyle b} ビットで表すことができる。
鍵生成、署名生成、署名検証の方法は以下の通りである。 ∥ {\displaystyle \parallel } はビット列の連結を表す。
署名鍵
一様ランダムに選んだ b {\displaystyle b} ビット列 k {\displaystyle k} 。
公開鍵
署名鍵 k {\displaystyle k} から s = H 0 , … , b − 1 ( k ) {\displaystyle s=H_{0,\dots ,b-1}(k)} （ハッシュ値の下位 b {\displaystyle b} ビット）を計算し、楕円曲線上の点 A = s B ∈ E ( F q ) {\displaystyle A=sB\in E(\mathbb {F} _{q})} を公開鍵とする。 b {\displaystyle b} ビット列で表される。
署名
メッセージ M {\displaystyle M} に対する署名は、楕円曲線上の点 R {\displaystyle R} と ℓ {\displaystyle \ell } 未満の正整数 S {\displaystyle S} のペア ( R , S ) {\displaystyle (R,S)} で表される。（共に b {\displaystyle b} ビットで表せるため、署名長は 2 b {\displaystyle 2b} ビット。）これを得るためには、まず署名鍵 k {\displaystyle k} から k ′ = H b , … , 2 b − 1 ( k ) {\displaystyle k'=H_{b,\dots ,2b-1}(k)} （ハッシュ値の上位 b {\displaystyle b} ビット）を計算し、 r = H ( k ′ ∥ M ) {\displaystyle r=H(k'\parallel M)} を計算する。これを用いて以下を計算する。
R = r B {\displaystyle R=rB} S = r + H ( R ∥ A ∥ M ) s mod ℓ {\displaystyle S=r+H(R\parallel A\parallel M)s{\bmod {\ell }}}
署名の検証
次の式が成り立つことを確認する。
2 c S B = 2 c R + 2 c H ( R ∥ A ∥ M ) A {\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A}
署名の生成方法と、位数が ℓ 2 c {\displaystyle \ell 2^{c}} であることから、正しく作られた署名は必ず検証を通る。すなわち： 2 c S B = 2 c ( r + H ( R ∥ A ∥ M ) s ) B = 2 c r B + 2 c H ( R ∥ A ∥ M ) s B = 2 c R + 2 c H ( R ∥ A ∥ M ) A . {\displaystyle {\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は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数としてSHA-512（SHA-2）を使い、曲線としてCurve25519を用いている。各パラメータは以下の通り。
Ed25519
q = 2 255 − 19 {\displaystyle q=2^{255}-19}
E ( F q ) {\displaystyle E(\mathbb {F} _{q})} はツイステッドエドワーズ曲線
− x 2 + y 2 = 1 − 121665 121666 x 2 y 2 , {\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}
ℓ = 2 252 + 27742317777372353535851937790883648493 {\displaystyle \ell =2^{252}+27742317777372353535851937790883648493} および c = 3 {\displaystyle c=3}
B {\displaystyle B} は E ( F q ) {\displaystyle E(\mathbb {F} _{q})} 上の点のうち、 y {\displaystyle y} 座標が 4 / 5 {\displaystyle 4/5} であり x {\displaystyle x} 座標が正である点。