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

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

概要

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

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

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

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

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

署名鍵

一様ランダムに選んだ ${\displaystyle b}$ ビット列 ${\displaystyle k}$。

公開鍵

署名鍵 ${\displaystyle k}$ から ${\displaystyle s=H_{0,\dots ,b-1}(k)}$ （ハッシュ値の下位 ${\displaystyle b}$ ビット）を計算し、楕円曲線上の点 ${\displaystyle A=sB\in E(\mathbb {F} _{q})}$ を公開鍵とする。${\displaystyle b}$ ビット列で表される。

署名

メッセージ ${\displaystyle M}$ に対する署名は、楕円曲線上の点 ${\displaystyle R}$ と ${\displaystyle \ell }$ 未満の正整数 ${\displaystyle S}$ のペア ${\displaystyle (R,S)}$ で表される。（共に ${\displaystyle b}$ ビットで表せるため、署名長は ${\displaystyle 2b}$ ビット。）これを得るためには、まず署名鍵 ${\displaystyle k}$ から ${\displaystyle k'=H_{b,\dots ,2b-1}(k)}$（ハッシュ値の上位 ${\displaystyle b}$ ビット）を計算し、${\displaystyle r=H(k'\parallel M)}$ を計算する。これを用いて以下を計算する。

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

署名の検証

次の式が成り立つことを確認する。

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

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

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

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

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

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

曲線 ${\displaystyle E(\mathbb {F} _{q})}$ は、Curve25519として知られているモンゴメリ型楕円曲線（英語版）と双有理同値である。具体的な同値は$${\displaystyle x={\sqrt {-486664}}u/v,\quad y=(u-1)/(u+1)}$$ で与えられる 。

Ed448

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

脚注

関連項目

• 楕円曲線DSA
• Curve25519
• NaCl (ソフトウェア)

外部リンク

• Ed25519 home page

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

• 表示
• 編集

表 話 編 歴 公開鍵暗号 アルゴリズム Cramer-Shoup暗号 ディフィー・ヘルマン鍵共有 楕円曲線ディフィー・ヘルマン鍵共有 Digital Signature Algorithm 楕円曲線DSA（ecdsa） エドワーズ曲線DSA（Ed25519） ElGamal暗号（ElGamal署名） EPOC (暗号) Merkle-Hellmanナップサック暗号 NTRU暗号 Paillier暗号 Rabin暗号 RSA暗号 ランポート署名 理論 離散対数 素因数分解 楕円曲線暗号 標準化 CRYPTREC IEEE P1363（英語版） NESSIE NSA Suite B（英語版） CNSA 関連項目 デジタル署名 Optimal Asymmetric Encryption Padding 指紋 公開鍵基盤 ゼロ知識証明

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ