エド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}

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

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

EdDSA署名スキームでは、

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

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

秘密鍵: EdDSA秘密鍵はビットの文字列であり、一様にランダムに選択される。対応する公開鍵はである。ここではの最下位ビットであり、リトルエンディアンの整数として解釈される。 $b$ $k$ $A=sB$ $s=H_{0,\dots,b-1}(k)$ $b$ $H(k)$
署名: メッセージの署名は次のように決定論的に計算される。ここで、、これは検証方程式を満たす。 $M$ $(R,S),$ $R=rB$ $r=H(H_{b,\dots ,2b-1}(k)\parallel M)$ $S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.$

${\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に関連する楕円曲線を使用したEdDSA署名方式である[ ^2]。

$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$ は、座標がであり、座標が正である唯一の点です。「正」はビットエンコーディングで定義されます。 $E(\mathbb {F} _{q})$ $y$ $4/5$ $x$
- 「正」の座標は偶数座標です（最下位ビットはクリアされます）
- 「負の」座標は奇数座標です（最下位ビットが設定されます）
$H$ はSHA-512で、です。 $b=256$

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

パフォーマンス

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

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

安全なコーディング

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

他の離散対数署名方式と同様に、EdDSAは署名ごとに固有の「ノンス」と呼ばれる秘密値を使用します。DSAおよびECDSA署名方式では、このノンスは従来、署名ごとにランダムに生成されます。そして、署名作成時に乱数生成器が破られ、予測可能になった場合、ソニーのPlayStation 3ファームウェアアップデートの署名鍵で発生したように、署名から秘密鍵が漏洩する可能性があります。^[11]^[12]^[13]^[14]

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

標準化と実装の不一致

EdDSAには2つの標準化活動があり、1つはIETFによる情報提供RFC 8032、もう1つはNISTによるFIPS 186-5の一部である。^[15]これらの標準の違いは分析されており、^[16]^[17]テストベクトルも利用可能である。^[18]

ソフトウェア

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

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

Ed448

Ed448は、ハッシュ関数SHAKE256と楕円曲線edwards448 （ RFC 7748のCurve448に関連する（ねじれのない）エドワーズ曲線）を使用して RFC 8032で定義されたEdDSA署名方式です。Ed448は、FIPS 186-5標準の最終版でも承認されています。^[15]

参考文献

^ abcde Josefsson, S.; Liusvaara, I. (2017年1月). Edwards-Curve Digital Signature Algorithm (EdDSA). IRTF . doi : 10.17487/RFC8032 . ISSN 2070-1721. RFC 8032. 2022年7月11日閲覧。
^ abcdefg バーンスタイン、ダニエル J. ;デュイフ、ニールス。Lange, タンハ;シュワーベ、ピーター。ボー・イン・ヤン (2012)。「高速・高セキュリティ署名」（PDF）。暗号工学ジャーナル。2 (2): 77–89 .土井: 10.1007/s13389-012-0027-1。S2CID 945254。
^ 「ソフトウェア」 2015年6月11日. 2016年10月7日閲覧. Ed25519ソフトウェアはパブリックドメインです。
^ ab ダニエル・J・バーンスタイン;サイモン・ジョセフソン。タンジャ・ランゲ;ピーター・シュワーベ;ボー・イン・ヤン (2015-07-04)。その他の曲線については EdDSA (PDF) (技術レポート) 。2016 年 11 月 14 日に取得。
^ Daniel J. Bernstein ; Tanja Lange ; Peter Schwabe (2011-01-01). ポラードロー法における否定写像の正しい使用法について（技術報告）. IACR Cryptology ePrint Archive. 2011/003 . 2016年11月14日閲覧。
^ Bernstein, Daniel J. ; Lange, Tanja . 「ECDLPセキュリティ：Rho」。SafeCurves：楕円曲線暗号における安全な曲線の選択。2016年11月16日閲覧。
^ ab Langley, A.; Hamburg, M.; Turner, S. (2016年1月). セキュリティのための楕円曲線. IETF . doi : 10.17487/RFC7748 . ISSN 2070-1721. RFC 7748. 2024年11月12日閲覧.
^ Bernstein, Daniel J. ; Lange, Tanja (2007). 黒澤薫 (編). 楕円曲線上の高速加算と倍算. 暗号学の進歩—ASIACRYPT. コンピュータサイエンス講義ノート. 第4833巻. ベルリン: Springer. pp. 29– 50. doi : 10.1007/978-3-540-76900-2_3 . ISBN 978-3-540-76899-9. MR 2565722。
^ Bernstein, Daniel J. (2017-01-22). 「Ed25519: 高速かつ高セキュリティな署名」. 2019-09-27閲覧。このシステムのセキュリティターゲットは2^128であり、これを破ることはNIST P-256、約3000ビット鍵のRSA、強力な128ビットブロック暗号などを破るのと同程度の困難さである。
^ Bernstein, Daniel J. (2017-01-22). 「Ed25519: 高速・高セキュリティ署名」. 2020-06-01閲覧.署名は64バイトに収まります。[…] 公開鍵はわずか32バイトしか消費しません。
^ Johnston, Casey (2010年12月30日). 「PS3、暗号実装の脆弱性によりハッキングされる」Ars Technica . 2016年11月15日閲覧。
^ fail0verflow (2010年12月29日). Console Hacking 2010: PS3 Epic Fail (PDF) . Chaos Communication Congress . 2018年10月26日時点のオリジナル(PDF)からアーカイブ。 2016年11月15日閲覧。
^ 「第27回カオスコミュニケーション会議：コンソールハッキング2010：PS3の大失敗」（PDF）。2019年8月4日閲覧。
^ Buchanan, Bill (2018年11月12日). 「ランダムにプレイしない：ソニーPS3とビットコイン暗号ハッキング。乱数ジェネレータに注目」Medium . 2018年11月30日時点のオリジナルよりアーカイブ。 2024年3月11日閲覧。
^ abc Moody, Dustin (2023年2月3日). FIPS 186-5: デジタル署名標準 (DSS). NIST . doi : 10.6028/NIST.FIPS.186-5 . S2CID 256480883. 2023年3月4日閲覧。
^ Chalkias, Konstantinos; Garillot, Francois; Nikolaenko, Valeria (2020-10-01). 多数のEdDSAを管理する. セキュリティ標準化研究会議 (SSR 2020) . 2021年2月15日閲覧。
^ Brendel, Jacqueline; Cremers, Cas ; Jackson, Dennis; Zhao, Mang (2020-07-03). ed25519の証明可能セキュリティ：理論と実践. IEEE Symposium on Security and Privacy (S&P 2021) . 2021年2月15日閲覧。
^ "ed25519-speccheck". GitHub . 2021年2月15日閲覧。
^ “OpenSSH 6.4以降の変更点”. 2014年1月3日. 2016年10月7日閲覧。
^ 「GnuPG 2.1の新機能」2016年7月14日. 2016年10月7日閲覧。
^ 「Ed25519 を使うもの」. 2016年10月6日. 2016年10月7日閲覧。
^ Harris, B.; Velvindron, L. (2020年2月). Ed25519およびEd448 Secure Shell (SSH)プロトコルの公開鍵アルゴリズム. IETF . doi : 10.17487/RFC8709 . ISSN 2070-1721. RFC 8709. 2022年7月11日閲覧。
^ 「watchOSのシステムセキュリティ」。 2021年6月7日閲覧。
^ Matt Johnston (2013年11月14日). “DROPBEAR_2013.61test”. 2019年8月5日時点のオリジナルよりアーカイブ。2019年8月5日閲覧。
^ 「ヒューリスティックアルゴリズムと分散コンピューティング」（PDF） . Èvrističeskie Algoritmy I Raspredelennye Vyčisleniâ（ロシア語）: 55– 56. 2015. ISSN 2311-8563. 2016年10月20日時点のオリジナル（PDF）からのアーカイブ。 2016年10月7日閲覧。
^ Frank Denis. 「Minisign: ファイルに署名し、署名を検証するための非常にシンプルなツール」 . 2016年10月7日閲覧。
^ GitHubの minisign-misc
^ Frank Denis (2016年6月29日). 「libsodium/ChangeLog」. GitHub . 2016年10月7日閲覧。
^ “OpenSSL CHANGES”. 2019年7月31日. 2018年5月18日時点のオリジナルよりアーカイブ。2019年8月5日閲覧。
^ "python/ed25519.py: メインサブルーチン". 2011年7月6日. 2016年10月7日閲覧。
^ 「ソフトウェア：代替実装」 2015年6月11日. 2016年10月7日閲覧。
^ 「eBACS: ECRYPT 暗号化システムのベンチマーク: SUPERCOP」2016年9月10日。 2016年10月7日閲覧。
^ 「Virgil Security Crypto Library for C: Library: Foundation」。GitHub 。2019年8月4日閲覧。
^ 「wolfSSL 組み込みSSLライブラリ（旧称CyaSSL）」。 2016年10月7日閲覧。

外部リンク

Ed25519ホームページ