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

エドワーズ曲線デジタル署名アルゴリズム（エドワーズきょくせんデジタルしょめいあるごりずむ、、略称：EdDSA）は、公開鍵暗号において、に基づくの一種を用いたデジタル署名の一つである。他のデジタル署名において見つかっている安全性に関する問題を回避した上で、高効率で暗号化処理が行われるように設計されている。エドワーズ曲線電子署名アルゴリズムは、ダニエル・バーンスタインが率いるチームによって開発された 。
概要.
EdDSAのアルゴリズムは以下のように表すことができる。簡単のため、整数や曲線上の点をどのようにビット列に符号化するかといった詳細は省略している。詳細については、引用文献やRFCを参照のこと。
EdDSA方式は、次のパラメータを用いる。
これらのパラメータは、EdDSA署名方式の全てのユーザが共通で使うことができる。ベースポイントの選択は任意だが、その他のパラメータの選択はEdDSA署名方式の安全性に大きく影響を与える。例えば、ポラード・ロー離散対数アルゴリズムを用いて離散対数を計算するのに必要な楕円加算回数はおよそ formula_18 回である。したがって、このアルゴリズムで離散対数を解くことが事実上できないように formula_5 は十分大きくなければならない。典型的には、formula_5 は formula_21 より大きい値を用いる。formula_5 の選択は formula_2 の選択によって制限を受ける。Hasseの定理により、位数formula_7 は、formula_25 から formula_26 以上離れることができないためである。ハッシュ関数 formula_11 は、EdDSAの安全性解析においては通常ランダムオラクルと想定される。HashEdDSAという変種（variant）においては、formula_11 に加え、を持つハッシュ関数formula_29も必要である。
鍵生成、署名生成、署名検証の方法は以下の通りである。formula_30 はビット列の連結を表す。
formula_49formula_50
formula_51
署名の生成方法と、位数が formula_52 であることから、正しく作られた署名は必ず検証を通る。すなわち：
formula_53
Ed25519.
Ed25519は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数としてSHA-512（SHA-2）を使い、曲線としてCurve25519を用いている。各パラメータは以下の通り。
formula_56
曲線 formula_3 は、Curve25519として知られていると双有理同値である。具体的な同値はformula_67 で与えられる 。
性能.
Ed25519は、x86-64 Nehalem/プロセッサファミリー向けに最適化されている。検証は、64個の署名を一括で処理することでよりスループットを向上させることができる。Ed25519 は、128ビット安全性を持つ共通鍵暗号系と同等の攻撃耐性を提供することを目的としている。公開鍵は256ビット、署名は512ビットである。
コーディングの安全性.
安全性に関しては、Ed25519では、秘密のデータに依存した分岐命令と配列参照が用いられておらず、多くのサイドチャネル攻撃に耐性がある。
他の離散対数問題ベースの署名方式と同様に、EdDSAは署名毎に異なるnonceと呼ばれる秘密情報が用いられる。DSAとECDSAにおいては、このnonceは署名生成ごとにランダムに生成されるのが一般的である。しかし、もし脆弱な乱数生成方法が用いられてnonceを推測可能であるときには、署名が秘密鍵の情報を漏らしてしまう。例えば、ソニーのPlayStation 3の署名鍵が漏洩した事例がある。
これに対し、EdDSAでは秘密鍵とメッセージのハッシュ値からnonceを確定的に決めるという方法を取っている。これにより、秘密鍵をランダムに作成すれば、その後の署名生成時には乱数を使う必要がなく、脆弱な乱数生成方法を用いることによる秘密鍵の漏洩のリスクが存在しない。
標準化と実装の矛盾.
EdDSAには2つの標準化が存在する。1つはIETFによる RFC 8032 であり、もう1つはNISTによるFIPS 186-5 (2019).である。これらの標準の間の違いについての解析が既に報告されており、テストベクタも利用可能である
ソフトウェア.
Ed25519の主要な使用例には、OpenSSH, GnuPGとさまざまな代替ソフトウェア 、そして、OpenBSDで提供されているデジタル署名・署名検証ツールsignifyがある 。
Ed448.
Ed448は、エドワーズ曲線デジタル署名の実装の一つであり、ハッシュ関数としてSHAKE256を使い、曲線としてCurve448を用いている。Ed25519と同様に、RFC 8032 に定義され、FIPS 186-5の草稿において推奨されている。