エドDSA

公開鍵暗号において、エドワーズ曲線デジタル署名アルゴリズム（EdDSA）は、ねじれたエドワーズ曲線に基づくシュノア署名の変形を使用するデジタル署名方式です。^{[1]セキュリティを犠牲にすることなく、既存のデジタル署名方式よりも高速になるように設計されています。Daniel} J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yang を含むチームによって開発されました。 ^[2] 参照実装はパブリックドメインソフトウェアです。^[3]

以下はEdDSAの簡略化された説明であり、整数と曲線点をビット文字列としてエンコードする詳細は無視しています。詳細は論文とRFCに記載されています。^{[4] [2] [1]}

EdDSA署名方式の選択肢は次の通りである: ^{[4] : 1–2  [2] : 5–6  [1] : 5–7}

• 奇数素数累乗上の有限体 の;${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$
• 有理点群の位数が である楕円曲線 の であり、 は大きな素数であり、 は余因子と呼ばれる。${\displaystyle E}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$${\displaystyle \ell}$${\displaystyle 2^{c}}$
• 基点の順序;および${\displaystyle B\in E(\mathbb {F} _{q})}$${\displaystyle \ell}$
• ビット出力を持つ暗号ハッシュ関数 。ここで、の要素と の曲線点は、ビットの文字列で表すことができます。${\displaystyle H}$${\displaystyle 2b}$${\displaystyle 2^{b-1}>q}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle E(\mathbb {F} _{q})}$${\displaystyle b}$

これらのパラメータは、EdDSA 署名方式のすべてのユーザーに共通です。 EdDSA 署名方式のセキュリティは、基点の任意の選択を除き、パラメータの選択に大きく依存します。たとえば、対数に対するポラードのローアルゴリズムは、離散対数を計算する前に約 回の曲線加算が必要になると予想され、 ^{[5] 、}これが実行不可能になるほど大きくする必要があり、通常は2 ^{200 を}超えるとされます。^[6] の選択はの選択によって制限されます。ハッセの定理により、と の差はより大きくできないためです。ハッシュ関数は、通常、EdDSA のセキュリティの正式な分析ではランダムオラクルとしてモデル化されます。 ${\displaystyle {\sqrt {\ell \pi /4}}}$${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle q}$${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$${\displaystyle q+1}$${\displaystyle 2{\sqrt {q}}}$${\displaystyle H}$

EdDSA署名スキームでは、

公開鍵

EdDSA 公開鍵は、ビットでエンコードされた曲線点です。${\displaystyle A\in E(\mathbb {F} _{q})}$${\displaystyle b}$

署名検証

公開鍵によるメッセージの EdDSA 署名は、ビットでエンコードされた曲線点と次の検証方程式を満たす整数のペアです。ここで、 は連結を表します。${\displaystyle M}$${\displaystyle A}$${\displaystyle (R,S)}$${\displaystyle 2b}$${\displaystyle R\in E(\mathbb {F} _{q})}$${\displaystyle 0<S<\ell }$${\displaystyle \parallel}$

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

秘密鍵

EdDSA 秘密鍵はビットの文字列で、一様にランダムに選択されます。対応する公開鍵は です。ここで、 は の最下位ビットであり、リトルエンディアンの整数として解釈されます。${\displaystyle b}$${\displaystyle k}$${\displaystyle A=sB}$${\displaystyle s=H_{0,\dots ,b-1}(k)}$${\displaystyle b}$${\displaystyle H(k)}$

署名

メッセージの署名は次のように決定論的に計算される。ここで、 、これは検証方程式を満たす。${\displaystyle M}$${\displaystyle (R,S),}$${\displaystyle R=rB}$${\displaystyle r=H(H_{b,\dots ,2b-1}(k)\parallel M)}$$${\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.}$$

$${\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 ^[2]を使用したEdDSA署名方式であり、

• ${\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}$
  
  • 「正」の座標は偶数座標です（最下位ビットはクリアされます）
  • 「負の」座標は奇数座標です（最下位ビットが設定されます）
• ${\displaystyle H}$はSHA-512で、 です。${\displaystyle b=256}$

この曲線は、Curve25519として知られるモンゴメリ曲線と双有理的に同値である。同値性は^{[2] [7]である。}${\displaystyle E/\mathbb {F} _{q}}$ $${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

元のチームは、Ed25519をx86-64 Nehalem / Westmereプロセッサフ​​ァミリ用に最適化しました。検証は64個の署名のバッチで実行できるため、スループットがさらに向上します。Ed25519は、高品質の128ビット対称暗号に匹敵する攻撃耐性を提供することを目的としています。^[8]

公開鍵は256ビットの長さで、署名は512ビットの長さです。^[9]

Ed25519は、サイドチャネル攻撃を軽減するために、秘密データに依存する分岐条件や配列インデックスを使用する実装を回避するように設計されています。 ^{[2] : 2  [1] : 40}

他の離散対数ベースの署名方式と同様に、EdDSA は各署名に固有のnonceと呼ばれる秘密値を使用します。署名方式DSAおよびECDSAでは、この nonce は従来、署名ごとにランダムに生成されます。署名の作成時に乱数ジェネレータが壊れて予測可能になると、ソニー PlayStation 3ファームウェア更新署名キーで発生したように、署名から秘密キーが漏洩する可能性があります。^{[10] [11] [12] [13]}

対照的に、EdDSAは、秘密鍵とメッセージの一部のハッシュとして決定論的にノンスを選択します。したがって、秘密鍵が生成されると、EdDSAは署名を作成するために乱数ジェネレータを必要とせず、署名を作成するために使用される壊れた乱数ジェネレータによって秘密鍵が明らかになる危険はありません。^{[2] : 8}

EdDSAには2つの標準化の取り組みがあり、1つはIETFからの情報RFC  8032、もう1つはNISTからのFIPS 186-5の一部であることに注意してください。^[14]標準の違いは分析されており、^{[15] [16]}テストベクトルが利用可能です。^[17]

Ed25519の注目すべき使用法としては、OpenSSH ^[18]、 GnuPG [ ^19]およびさまざまな代替手段、OpenBSDのsignifyツール^[20]などがあります。SSHプロトコルでのEd25519（およびEd448）の使用は標準化されています。^{[21] 2023年に}FIPS 186-5標準の最終バージョンに、決定論的なEd25519が承認された署名スキームとして含まれました。^[14]

• Apple WatchとiPhoneはIKEv2相互認証にEd25519キーを使用する^[22]
• ぼたん
• 暗号++
• CryptoNote 暗号通貨 プロトコル
• ドロップベアSSH ^[23]
• EdDSAのI2Pd実装^[24]
• Java 開発キット15
• ライブラリgcrypt
• macOS用のMinisign ^[25]とMinisign Miscellanea ^[26]
• NaCl / リブナトリウム^[27]
• OpenSSL 1.1.1 ^[28]
• Python - 遅いが簡潔な代替実装であるが、^[29]サイドチャネル攻撃保護は含まれていない^[30]
• Supercopリファレンス実装^[31]（インラインアセンブラ付きC言語）
• Virgil PKIはデフォルトでEd25519鍵を使用する^[32]
• ウルフSSL ^[33]

Ed448は、RFC 8032で定義されているSHAKE256とCurve448を使用したEdDSA署名方式です。 また、FIPS 186-5標準の最終バージョンでも承認されています。^[14]

• Ed25519ホームページ