3. EdDSA Algorithm (EdDSA アルゴリズム)

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

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

したがって, 汎用 EdDSA の正確な説明は, 実装者にとって特に有用ではありません。背景と完全性のため, ここでは汎用 EdDSA アルゴリズムの簡潔な説明を示します。

n や c などの一部のパラメータの定義は, 直感的ではないアルゴリズムのいくつかのステップを説明するのに役立つ場合があります。

この説明は [EDDSA2] に厳密に従っています。

EdDSA には 11 個のパラメータがあります:

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

曲線上の点は加算の下で群を形成します, (x3, y3) = (x1, y1) + (x2, y2), 公式は次の通りです:

         x1 * y2 + x2 * y1                y1 * y2 - a * x1 * x2
x3 = --------------------------,   y3 = ---------------------------
     1 + d * x1 * x2 * y1 * y2          1 - d * x1 * x2 * y1 * y2

群の中性元は (0,1) です。

暗号学的アプリケーションに使用される他の多くの曲線とは異なり, これらの公式は「完全」です; 曲線上のすべての点に対して有効であり, 例外はありません。特に, すべての入力点に対して分母は非ゼロです。

高価な modulo p の逆元演算を避けるために斉次座標を使用する, より効率的な公式があり, それでも完全です。[Faster-ECC] と [Edwards-revisited] を参照してください。

3. EdDSA Algorithm (EdDSA アルゴリズム)​

3. EdDSA Algorithm (EdDSA アルゴリズム)