セキュリティ
\( \def\vector#1{\boldsymbol{#1}} \)

RFC翻訳: Edwards-Curve Digital Signature Algorithm (EdDSA)

Takami Torao RFC 8032 #楕円曲線暗号 #EdDSA #Ed25519 #Ed448
  • このエントリーをはてなブックマークに追加

Abstract

この文書ではエドワーズ曲線デジタル署名アルゴリズム (EdDSA) の楕円曲線署名スキームについて説明している。アルゴリズムは edwards25519 および edwards448 曲線の推奨パラメータで具現化される。この文書ではサンプル実装とテストベクターを提供する。

Status of This Memo

この文書は Internet Research Task Force (IRFT) の成果物である。IRTF はインターネット関連の研究開発の活動結果を公開している。これらの結果は展開に適さない場合がある。この RFC は Internet Research Task Force (IRFT) の Crypto Forum Research Group のコンセンサスを表している。IRSG による公開が承認された文書はいかなるレベルのインターネット標準の候補でもない。RFC 7841 セクション2を参照。

このドキュメントの現在のステータス、Errata、フィードバックの提供方法に関する情報は http://www.rfc-editor.org/info/rfc8032 で入手できる。

Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Table of Contents

  1. Abstract
    1. Status of This Memo
    2. Copyright Notice
  2. 1. 導入
  3. 2. 表記法と規則
  4. 3. EdDSA アルゴリズム
    1. 3.1 エンコーディング
    2. 3.2 鍵
    3. 3.3 署名
    4. 3.4 検証
  5. 4. PureEdDSA, HashEdDSA と Naming
  6. 5. EdDSA インスタンス
    1. 5.1 Ed25519ph, Ed25519ctx と Ed25519
      1. 5.1.1. モジュラー演算 [under construction]
      2. 5.1.2. Encoding
      3. 5.1.3. Decoding
      4. 5.1.4. Point Addtion
      5. 5.1.5. Key Generation
      6. 5.1.6. Sign
      7. 5.1.7 Verify
    2. 5.2. Ed448ph and Ed448
      1. 5.2.1. Modular Arithmetic
      2. 5.2.2. Encoding
      3. 5.2.3. Decoding
      4. 5.2.4. Point Addition
      5. 5.2.5. Key Generation
      6. 5.2.6. Sign
      7. 5.2.7. Verify
  7. 6. Ed25519 Python Illustration
  8. 7. Test Vectors
    1. 7.1. Test Vectors for Ed25519
    2. 7.2. Test Vectors for Ed25519ctx
    3. 7.3. Test Vectors for Ed25519ph
    4. 7.4. Test Vectors for Ed448
    5. 7.5. Test Vectors for Ed448ph
  9. 8. セキュリティ考察
    1. 8.1. サイドチャネルリーク
    2. 8.2. Randomeness Considerations
    3. 8.3. Use of Contexts
    4. 8.4. Signature Malleability
    5. 8.5. Choice of Signature Primitive
    6. 8.6. Mixing Difference Prehashes
    7. 8.7. SIgning Large Amounts of Data at Once
    8. 8.8. Multiplication by Cofactor in Verification
    9. 8.9. Use of SHAKE256 as a Hash Function
  10. 9. References
    1. 9.1. Normative References
    2. 9.2. Informative References
  11. Acknowledgements
  12. Appendix A. Ed25519/Ed448 Python Library
  13. Appendix B. Library Driver
  14. 参照

1. 導入

エドワーズ曲線デジタル署名アルゴリズム (EdDSA; Edwards-curve Digital Signature Algorithm) は (捻れているかもしれない) エドワーズ曲線を持つ Shnorr 署名システムの変種である。EdDSA は特定のパラメータで具現化する必要があり、この文書ではいくつかの推奨される変種について説明する。

インターネットコミュニティでの EdDSA の採用を促進するためにこの文書では実装指向の方向を以て署名スキームについて説明し、サンプルコードとテストベクトルを提供する。

EdDSA の利点は次の通り:

  1. EdDSA は様々なプラットフォームで高いパフォーマンスを提供する。
  2. 署名ごとにユニークな乱数を使用する必要がない。
  3. サイドチャネル攻撃に対してより回復力がある。
  4. EdDSA は Ed25519 と Ed448 の両方で小さな公開鍵 (32 または 57 バイト) と署名 (64 または 114 バイト) を使用する。
  5. 数式が "完全" である。つまり曲線上のすべての点で有効であり例外はない。これにより EdDSA が信頼できない公の値に対して高価な点検証を実行する必要がない。そして
  6. EdDSA は衝突耐性を持つ。これはハッシュ関数の衝突がこのシステムを破壊しないことを意味している (PureEdDSA のみに当てはまる)。

オリジナルの EdDSA 論文 [EDDSA] および "より多くの EdDSA 曲線" [EDDSA2] で説明されている一般化されたバージョンはさらなる背景を提供する。RFC 7748 [RFC7748] は Curve25519 [CURVE25519] および Ed448-Goldilocks [ED448] を含む特定の曲線について説明している。

Ed25519 は約 128 ビットのセキュリティレベルで動作し、Ed448 は約 224 ビットのセキュリティレベルで動作する。十分に強力な量子コンピュータであればこれら両方を破ることができるだろう。しかし古典的なコンピュータの性能を合理的に予測すると Ed25519 は完全に安全であると結論付けられる。Ed448 はパフォーマンス要件を緩和することが可能で、楕円曲線に対する分析攻撃を回避したいアプリケーション向けに提供されている。

2. 表記法と規則

この文書を通じて以下の表記を使用する:

\(p\) 元になる体を定義する素数を示す。
\(GF(p)\) 元 \(p\) を持つ有限体。
\(x^y\) 自分自身が \(y\) 回乗算された \(x\)。
\(B\) 対象の群または部分群の生成元。
\(nX\) 自分自身が \(n\) 回加算された \(X\)。
\(h[i]\) 8ビットバイト列の \(i\) 番目のバイト値。
\(h_i\) \(h\) の \(i\) 番目のビット。
\(a || b\) (ビット) データ列 \(a\) と (ビット) データ列 b を連結したもの。
\(a \le b\) \(a\) は \(b\) 以下。
\(a \ge b\) \(a\) は \(b\) 以上。
\(i+j\) \(i\) と \(j\) の加算。
\(i \ast j\) \(i\) と \(j\) の乗算。
\(i / j\) \(i\) の \(j\) による除算。
\(i \times j\) \(i\) と \(j\) のデカルト積。
\((u,v)\) x座標とy座標をそれぞれ \(u\), \(v\) とする楕円曲線点。
\({\rm SHAKE256}(x,y)\) 入力 \(x\) に対する SHAKE256 [FIPS202] の最初のバイト値 \(y\)。
\({\rm OCTET}(x)\) 値 \(x\) のバイト値。
\({\rm OLEN}(x)\) データ列 \(s\) のバイト数。
\({\rm dim2}(x,y)\) Ed25519 で署名または検証するときの空のバイトデータ列。それ以外の場合のバイトデータ列は: "SigEd25519 no Ed25519 collisions" || \({\rm OCTET}(x)\) || \({\rm OCTET}({\rm OLEN}(y))\) || \(y\)。ここで \(x\) は 0〜255 の範囲、\(y\) は最大で 255 バイトのデータ列、"SigEd25519 no Ed25519 collisions" は ASCII 文字列 (32バイト) である。
\({\rm dim4}(x,y)\) バイト列 "SigEd448" || \({\rm OCTET}(x)\) || \({\rm OCTET}({\rm OLEN}(y))\) || \(y\)。ここで \(x\) は 0〜255 の範囲、\(y\) は最大で 255 バイトのデータ列、"SigEd448" は ASCII 文字列 (8バイト) である。

括弧 (つまり '(' と ')') は演算子の暗黙的な結合順序に説明が依存しないように式をグループ化するために使用する。

ビット列はビットの左から右に取り、各バイト値の最下位ビットから最上位ビットにパックし、各バイト値がいっぱいになると次のバイト値に移動することでバイト列に変換される。バイト列からビット列への変換はこのプロセスの逆である。例えば 16 ビット列 \[ b_0 \ b_1 \ b_2 \ b_3 \ b_4 \ b_5 \ b_6 \ b_7 \ b_8 \ b_9 \ b_{10} \ b_{11} \ b_{12} \ b_{13} \ b_{14} \ b_{15} \] は 2 つのバイト x0 と x1 に (この順序で) 変換される。\[ \left\{ \begin{eqnarray*} x_0 & = & b_7 \ast 128 + b_6 \ast 64 + b_5 \ast 32 + b_4 \ast 16 + b_3 \ast 8 + b_2 \ast 4 + b_1 \ast 2 + b_0 \\ x_1 & = & b_{15} \ast 128 + b_{14} \ast 64 + b_{13} \ast 32 + b_{12} \ast 16 + b_{11} \ast 8 + b_{10} \ast 4 + b_9 \ast 2 + b_8 \end{eqnarray*} \right. \] ビットへのリトルエンディアンエンコーディングは、ビットを左から右へ、最下位から最上位へと配置する。上記で定義したビット列からバイト列への変換と組み合わせるとリトルエンディアンでバイトにエンコードされる (長さが 8 の倍数でない場合、最後のバイトの最上位ビットは未使用のままである)。

この文書のキーワード "しなければならない (MUST)"、"してはいけない (MUST NOT)"、"必要とされる (REQUIRED)"、"SHALL", "SHALL NOT", "すべき (SHOULD)"、"すべきではない (SHOULD NOT)"、"推奨される (RECOMMENDED"、"することがある (MAY)" 及び "オプション (OPTION)" は [RFC2119] で説明されているように解釈される。

3. EdDSA アルゴリズム

EdDSA は 11 個のパラメータを持つデジタル署名システムである。

11 個の入力パラメータを持つ一般的な EdDSA デジタル署名システムは直接実装することを意図していない。安全で効率的な操作を行う上でパラメータの選択が重要である。Ed25519 と Ed448 をカバーするコードに再利用性を持たせるために、読者は代わりに少し一般化した EdDSA の (Ed25519 や Ed448 などの) 特定のパラメータ選択を実装する。

従って、一般的な EdDSA の正確な説明は実装者にとって特に有用ではないが、背景と完全性のために一般的な EdDSA アルル後リズムの簡潔な説明をここで示す。

\(n\) や \(c\) などの一部のパラメータ定義はアルゴリズムの直感的ではないステップを理解するのに役立つかもしれない。

この説明は [EDDSA2] に厳密に従う。

EdDSA は 11 個のパラメータを持つ:

  1. 奇素数 (odd prime) の冪 \(p\)。EdDSA は有限体 \(GF(p)\) 上の楕円曲線を使用する。
  2. \(2^{b-1} \gt p\) となる整数 \(b\)。EdDSA 公開鍵は正確に \(b\) ビットを持ち、EdDSA 署名は正確に \(2 \ast b\) ビットを持つ。\(b\) は 8 の倍数とし公開鍵と署名の長さはバイトの整数倍とすることが推奨される。
  3. 有限体 \(GF(p)\) の元に対する \((b-1\) ビットエンコーディング。
  4. \(b \ast b\) ビット出力を生成する暗号論的ハッシュ関数 \(H\)。保守的なハッシュ関数 (つまり衝突の発生が不可能なハッシュ関数) が推奨され、EdDSA の総コストには大きな影響はない。
  5. 2 または 3 の整数 \(c\)。秘密 EdDSA スカラー値は \(2^c\) の倍数である。整数 \(c\) は、いわゆる補因子 (cofactor) と呼ばれる底が 2 の対数である。
  6. \(c \le n \lt b\) となる整数 \(n\)。秘密 EdDSA スカラー値は正確に \(n+1\) ビットを持ち、(\(2^n\)の) 最上位ビットが常に設定され、下位 \(c\) ビットが常にクリアされる。
  7. \(GF(p)\) の非正方元 \(d\)。通常の推奨事項は、許容可能な曲線を与えるゼロに最も近い値を取ることである。
  8. \(GF(p)\) の非ゼロ正方元 \(a\)。最高のパフォーマンスを得るための通常の推奨事項は、\(p \bmod 4 = 1\) の場合は \(a = -1\)、\(p \bmod 4 = 3\) の場合は \(a = 1\) である。
  9. 集合 \(E = \{ (x, y) \}\) の元 \(B \neq (0,1)\)。\((x,y)\) は \(a \ast x^2 + y^2 = 1 + d \ast x^2 \ast y^2\) となるような \(GF(p) \times GF(p)\) のメンバーである。
  10. \([L]B = 0\) かつ \(2^c \ast L = \#E\) となるような奇素数 \(L\)。数値 \(\#E\) (曲線状の点の数) は楕円曲線 \(E\) に対して提供される標準データの一部か、または補因子 * 位数で計算することができる。
  11. "事前ハッシュ" 関数 (prehash function) \(PH\)。PureEdDSA は \(PH\) が恒等関数、つまり \(PH(M)=M\) となる EdDSA を意味する。HashEdDSA はメッセージの長さに関係なく \(PH\) が短い出力を生成する EdDSA を意味する; 例えば \(PH(M) = {\rm SHA\mbox{-}512}(M)\) である。

曲線上の点は加算、つまり \((x_3,y_3) = (x_1,y_1) + (x_2,y_2)\) の下に群を形成し以下のように変換できる。\[ x_3 = \frac{x_1 \ast y_2 + x_2 \ast y_1}{1 + d \ast x_1 \ast x_2 \ast y_1 \ast y_2}, y_3 = \frac{y_1 \ast y_2 - a \ast x_1 \ast x_2}{1 - d \ast x_1 \ast x_2 \ast y_1 \ast y_2} \] 群の単位元は \((0,1)\) である。

暗号化アプリケーションに使用される他の多くの曲線とは異なり、これらの式は "完全" である。曲線上のすべての点に対して例外なく有効である。特に、任意の入力点に対して分母がゼロになることはない。

完全性を保ったまま同種の座標を使用して高コストなモジュロ \(p\) 逆数演算を回避するより効率的な公式が存在する。[Faster-ECC] および [Edwards-revisited] 参照。

3.1 エンコーディング

整数 \(0 \lt S \lt L-1\) はリトルエンディアン形式の \(b\) ビット列 \({\rm ENC}(S)\) でエンコードされている。

\(E\) の元 \((x,y)\) は \({\rm ENC}(x,y)\) と呼ばれる \(b\) ビット列でエンコードされている。これは \(x\) が負の場合に 1、負でない場合に 0 となる 1 ビットと連結された \(y\) の \((b-1)\) ビットエンコードである。

\(GF(p)\) のエンコードは \(GF(p)\) の "負" の元を定義するために使用される: 具体的には \(x\) の \((b-1)\) ビットエンコードが辞書的に \(-x\) の \((b-1)\) ビットエンコードより大きい場合に \(x\) は負である。

3.2 鍵

EdDSA 秘密鍵は \(b\) ビット列の \(k\) である。ハッシュ \(H(k) = (h_0,h_1,\ldots,h_{2b-1})\) で整数 \(s\) を決定するものとする。\(s\) は \(2^n\) に \(c \le i \lt n\) となるすべての整数 \(i\) に対する \(m=2^i \ast h_i\) の合計を加えたものである※1。\(s\) で乗算 \(A=[s]B\) を決定するものとする。EdDSA 公開鍵は \({\rm ENC}(A)\) である。ビット \(h_b,\ldots,h_{2b-1}\) は以下の署名時に使用される。

3.3 署名

秘密鍵 \(k\) の下のメッセージ \(M\) の EdDSA 署名は \(PH(M)\) の PureEdDSA 署名として定義される。つまり EdDSA は PureEdDSA を使って \(PH(M)\) に署名するだけである。

秘密鍵 \(k\) の下のメッセージ \(M\) の PureEdDSA 署名は \(2 \ast b\) ビットのデータ列 \({\rm ENC(R) || {\rm ENC}(S)\) である。\(R\) と \(S\) は次のように導かれる。まず \(\{0,1,\ldots,2^{2\ast b}-1\}\) の整数のリトルエンディアン形式の \(2 \ast b\) ビットデータ列 \(r=H(h_b || \ldots || h_{2b-1} || M)\) を定義する。\(R=[r]B\) と \(S=(r+H({\rm ENC}(R) || {\rm ENC}(A) || PH(M)) \ast s) \bmod L\) とする。ここで使用されている \(s\) は前のセクションのものである。

3.4 検証

公開鍵 \({\rm ENC}(A)\) の下でメッセージ \(M\) の PureEdDSA 署名 \({\rm ENC}(R) || {\rm ENC}(S)\) を検証するには次のようにする。\(A\) と \(R\) が \(E\) の元であり、\(S\) が集合 \(\{0,1,\ldots,L-1\}\) のメンバーとなるように入力を解析する。\(h = H({\rm ENC}(R) || {\rm ENC}(A) || M)\) を計算し、\(E\) での群方程式 \([2^c \ast S]B = 2^c \ast R + [2^c \ast h]A\) をチェックする。解析が失敗した場足 (\(S\) が範囲外のケースを含む)、あるいは群方程式が成立しない場合、署名は拒否される。

メッセージ \(M\) の EdDSA 検証は \(PH(M)\) の PureEdDSA 検証として定義される。

  1. ※1 \(s=2^n+\sum_{i=c}^{n-1}2^i \ast h_i\)

4. PureEdDSA, HashEdDSA と Naming

EdDSA アルゴリズムのパラメータの一つに "事前ハッシュ" 関数がある。これは PureEdDSA と呼ばれるアルゴリズムをもたらす恒等写像の場合と、HashEdDSA と呼ばれるアルゴリズムをもたらす SHA-512 などの衝突耐性ハッシュ関数をの場合がある。

使用する変種の選択は 1)衝突耐性 2)署名を生成するためののシングルパスインターフェースのどちらがより重要であるかによって異なる。衝突耐性はハッシュ関数の衝突を計算することが可能であっても EdDSA が安全であることを意味する。シングルパスインターフェース特性は署名を作成するために入力メッセージを 1 度だけ走査すればよいことを意味する。PureEdDSA では入力に対して 2 回のパスが必要である。多くの既存の API、プロトコル、および環境はデジタル署名アルゴリズムが入力に対して 1 度のパスしか必要とせず、他の物をサポートする API または帯域幅の問題があるかもしれないと想定している。

度の署名アルゴリズムが選択されても、ほとんどの署名の使用ではシングルパス検証は不可能であることに注意してください。これはほとんどの場合、署名が検証されるまでメッセージを処理できず、メッセージ全体を渡す必要があるためである。この文書では HashEdDSA 変種の Ed25519ph, Ed448ph と PureEdDSA 変種の Ed25519, Ed448 をもたらすパラメータを指定する。

5. EdDSA インスタンス

このセクションでは edwards25519 および edwards448 曲線の一般的な EdDSA アルゴリズムを具現化する。それぞれの曲線は PureEdDSA および HashEdDSA 変種 (加えて Ed25519 スキームのコンテキスト拡張) に対応する。したがって 5 つの異なるパラメータセットについて説明する。

5.1 Ed25519ph, Ed25519ctx と Ed25519

Ed25519 は Table 1 のように具現化した EdDSA である:

パラメータ 値
\(p\) [RFC7748] の edwards25519 の \(p\) (つまり \(2^{255}-19\))
\(b\) 256
\(GF(p)\) のエンコーディング \(\{0,1,\ldots,p-1\}\) の 255 ビットリトルエンディアンエンコーディング
\(H(x)\) \({\rm SHA}\mbox{-}512({\rm dom2}({\it phflag},{\it context}) || x)\) [RFC6234]
\(c\) [RFC7748] での edwards25519 補因子の 2 を底とする対数 (つまり 3)
\(n\) 254
\(d\) [RFC7748] の edwards25519 の \(d\) (つまり -121665/121666 = 37095705934669439343138083508754565189542113879843219016388785533085940283555)
\(a\) -1
\(B\) [RFC7748] の edwards25519 の \((X(P),Y(P))\) (つまり (15112221349535400772501151409588531511454012693041857206046113283949847762202, 46316835694926478169428394003475163141307993866256225615783033603165251855960))
\(L\) [RFC7748] の edwards25519 の位数 (つまり \(2^{252}\)+27742317777372353535851937790883648493)
\(PH(x)\) \(x\) (つまり恒等写像)
Table 1: Ed25519 のパラメータ

Ed25519 の場合、\({\rm dom2}(f,c)\) は空のデータ列である。\({\it phflag}\) 値は何とも関係していない。\({\it context}\) は (もし存在するなら) 空でなければならない。これによってスキームは以前に公開された Ed25519 スキームと同一となる。

Ed25519ctx の場合、\({\it phflag}=0\) であり \({\it context}\) は空にはならない。

Ed25519ph の場合、\({\it phflag}=1\) で \(PH\) は SHA512 となる。つまり入力は SHA-512 を使用してハッシュ化されてから Ed25519 で署名される。

\({\it context}\) の値は署名者と検証者によって設定され (最大 255 バイト; デフォルトは \({\it context}\) を持たない Ed25519 を除き空のデータ列)、検証を成功させるためにバイトごとに一致しなければならない。

使用される曲線は座標を変更した場合の Curve25519 [Curve25519] と等価である。これは離散対数問題の困難性が Curve25519 と同じであることを意味する。

5.1.1. モジュラー演算

算術モジュロー \(p=2^{255}-19\) を法とする計算を効率的かつ安全に実装する方法については Curve25519 [CURVE25519] を参照。\(p\) を法とする逆変換に対しては恒等式 \(x^{-1} = x^{p-2} \pmod{p}\) を用いることが推奨される。ゼロの反転は無効な入力が発生するため発生しない。無効な入力はその前に検出されているか計算エラーとなる。

点の複合化または "圧縮解除" のためには \(p\) を法とする平方根が必要である。これらは Tonelli-Shanks アルゴリズムまたは \(p=5 \pmod{8}\) の特殊なケースを使用して計算できる。\(a\) の平方根を求めるには、まず候補の根 \(x=a^{(p+3)/8} \pmod{p}\) を計算する。次の 3 つの場合がある:

  1. \(x\) が平方根。\(x^2 = a \pmod{p}\)
  2. \(2^{(p-1)/4} \ast x\) が平方根。\(x^2 = -a \pmod{p}\)
  3. \(a\) は \(p\) を法とする二乗ではない。

5.1.2. Encoding

5.1.3. Decoding

5.1.4. Point Addtion

5.1.5. Key Generation

5.1.6. Sign

署名手続きの入力は、秘密鍵、32バイト文字、および任意サイズのメッセージ \(M\) である。Ed25519ctx 及び Ed25519ph についてはさに最大 255 バイトのコンテキスト \(C\) と (Ed25519ctx は 0、Ed25519ph は 0 となる) フラグ \(F\) が存在する。

  1. SHA-512 を用いて 32 バイトの秘密鍵とハッシュ化する。\(h\) は結果のダイジェスト値を表すものとする。前のセクションで説明したように、ダイジェスト値の前半分から秘密スカラー値 \(s\) を作成し、対応する公開鍵 \(A\) を作成する。prefix をハッシュダイジェスト値の後半 \(h_{32},\ldots,h_{63}\) を示すものとする。
  2. \({\rm SHA}\mbox{-}512({\rm dom2}(F,C) || {\rm prefix} || PH(M))\) を計算する。ここで \(M\) は署名されるメッセージである。64 バイトのダイジェストをリトルエンディアンの整数 \(r\) として解釈する。
  3. 点 \([r]B\) を計算する。効率のためにまず\(B\) の群位数 \(L\) を法として \(r\) を減らす。データ列 \(R\) をこの点のエンコーディングとする。Josefsson & Liusvaara Informational [Page 13]
  4. \({\rm SHA512}({\rm dom2}(F,C) || R || A || PH(M))\) を計算し、64 バイトのダイジェスト値をリトルエンディアンの整数 \(k\) として解釈する。
  5. \(S = (r + k \ast s) \bmod L\) を計算する。効率のためにまず \(L\) を法として \(k\) を減らす。
  6. \(R\) (32 バイト) とリトルエンディアンのエンコーディングの \(S\) (32 バイト; 最終バイトの最上位 3 ビットは常にゼロ) を連結して署名を形成する。

4.SHA512(dom2(エフ、シー)||R||A||PH (M))を計算し、64オクテットのダイジェストをリトルエンディアン整数kとして解釈する。5.S=(r+k*sキー)mod Lを計算します。効率を上げるために、まずkモジュロLを減らします。6.R(32オクテット)の連結とS(32オクテット;最後のオクテットの上位3ビットは常に0である)のリトルエンディアン符号化の署名を形成する。

5.1.7 Verify

5.2. Ed448ph and Ed448

5.2.1. Modular Arithmetic

5.2.2. Encoding

5.2.3. Decoding

5.2.4. Point Addition

5.2.5. Key Generation

5.2.6. Sign

5.2.7. Verify

6. Ed25519 Python Illustration

7. Test Vectors

7.1. Test Vectors for Ed25519

7.2. Test Vectors for Ed25519ctx

7.3. Test Vectors for Ed25519ph

7.4. Test Vectors for Ed448

7.5. Test Vectors for Ed448ph

8. セキュリティ考察

8.1. サイドチャネルリーク

署名を行うための実装では秘密鍵を秘匿することが基本である。実装が秘密鍵の任意の値に対して正確に同じ命令シーケンスを実行し正確に同じメモリアクセスを実行することを保証することで一部のサイドチャネル攻撃から防護することができる。

この方法で実装をサイドチャネル対応するためには、モジュロ \(p\) 算術演算はキャリー伝搬に関連するようなデータ依存分岐を使用してはならない。サイドチャネル対応点の追加は統一された数式のおかげで単純である。

8.2. Randomeness Considerations

8.3. Use of Contexts

8.4. Signature Malleability

8.5. Choice of Signature Primitive

8.6. Mixing Difference Prehashes

8.7. SIgning Large Amounts of Data at Once

8.8. Multiplication by Cofactor in Verification

8.9. Use of SHAKE256 as a Hash Function

9. References

9.1. Normative References

  1. [FIPS202] National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, August 2015, <http://dx.doi.org/10.6028/NIST.FIPS.202>.
  2. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.
  3. [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, May 2011, <http://www.rfc-editor.org/info/rfc6234>.
  4. [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, <http://www.rfc-editor.org/info/rfc7748>.

9.2. Informative References

  1. [CURVE25519] Bernstein, D., "Curve25519: new Diffie-Hellman speed records", DOI 10.1007/11745853_14, February 2006, <http://cr.yp.to/ecdh.html>.
  2. [ED25519-LIBGCRYPT-TEST-VECTORS] Koch, W., "Ed25519 Libgcrypt test vectors", July 2014, <http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=blob;f=tests/t-ed25519.inp;h=e13566f826321eece65e02c593bc7d885b3dbe23;hb=refs/heads/master>.
  3. [ED25519-TEST-VECTORS] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. Yang, "Ed25519 test vectors", July 2011,<http://ed25519.cr.yp.to/python/sign.input>.
  4. [ED448] Hamburg, M., "Ed448-Goldilocks, a new elliptic curve", June 2015, <http://eprint.iacr.org/2015/625>.
  5. [EDDSA] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. Yang, "High-speed high-security signatures", DOI 10.1007/978-3-642-23951-9_9, September 2011, <http://ed25519.cr.yp.to/ed25519-20110926.pdf>.
  6. [EDDSA2] Bernstein, D., Josefsson, S., Lange, T., Schwabe, P., and B. Yang, "EdDSA for more curves", July 2015, <http://ed25519.cr.yp.to/eddsa-20150704.pdf>.
  7. [Edwards-revisited] Hisil, H., Wong, K., Carter, G., and E. Dawson, "Twisted Edwards Curves Revisited", DOI 10.1007/978-3-540-89255-7_20, December 2008, <http://eprint.iacr.org/2008/522>.
  8. [EFD-ADD] Bernstein, D. and T. Lange, "Projective coordinates for Edwards curves", The 'add-2007-bl' addition formulas, 2007, <http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#addition-add-2007-bl>.
  9. [EFD-DBL] Bernstein, D. and T. Lange, "Projective coordinates for Edwards curves", The 'dbl-2007-bl' doubling formulas, 2007, <http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl>.
  10. [EFD-TWISTED-ADD] Hisil, H., Wong, K., Carter, G., and E. Dawson, "Extended coordinates with a=-1 for twisted Edwards curves", The 'add-2008-hwcd-3' addition formulas, December 2008, <http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3>.
  11. [EFD-TWISTED-DBL] Hisil, H., Wong, K., Carter, G., and E. Dawson, "Extended coordinates with a=-1 for twisted Edwards curves", The 'dbl-2008-hwcd' doubling formulas, December 2008, <http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#doubling-dbl-2008-hwcd>.
  12. [Faster-ECC] Bernstein, D. and T. Lange, "Faster addition and doubling on elliptic curves", DOI 10.1007/978-3-540-76900-2_3, July 2007, <http://eprint.iacr.org/2007/286>.
  13. [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, June 2005, <http://www.rfc-editor.org/info/rfc4086>.

Acknowledgements

EdDSA and Ed25519 were initially described in a paper due to Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. The Ed448 curve is due to Mike Hamburg.

An earlier draft version of this document was coauthored by Niels Moeller.

Feedback on this document was received from Werner Koch, Damien Miller, Bob Bradley, Franck Rondepierre, Alexey Melnikov, Kenny Paterson, and Robert Edmonds.

The Ed25519 test vectors were double checked by Bob Bradley using three separate implementations (one based on TweetNaCl and two different implementations based on code from SUPERCOP).

Appendix A. Ed25519/Ed448 Python Library

Appendix B. Library Driver

Authors' Addresses

Simon Josefsson
SJD AB
Email: simon@josefsson.org
URI: http://josefsson.org/


Ilari Liusvaara
Independent

Email: ilariliusvaara@welho.com

参照

  1. RFC 8032: Edwards-Curve Digial Signature Algorithm (EdDSA)