EdDSA
RFC 8032 エドワーズ曲線デジタル署名アルゴリズム Edwards-Curve Digital Signature Algorithm (EdDSA)
RFC 7748 セキュリティのための楕円曲線 Elliptic Curves for Security Curve25519
Curve448
edwards25519
edwards448
Ed448-Goldilocks
NIST SP 800-186 Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters NIST FIPS 186-5 Digital Signature Standard (DSS)
RFC 9295 Clarifications for Ed25519, Ed448, X25519, and X448 Algorithm Identifiers
RFC 8709 Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol
RFC 6090 基本的な楕円曲線暗号アルゴリズム Fundamental Elliptic Curve Cryptography Algorithms $ v^2 = u^3 + Au^2 + u
Ax^2 + y^2 = 1 + Dx^2y^2
$ x^2 + y^2 = 1 + d*x^2*y^2 for 素数 p p = 3 mod 4の場合
ツイストエドワーズ曲線$ -x^2 + y^2 = 1 + d*x^2*y^2 p = 1 mod 4 の場合
RFC 7748 4.1 Curve25519
$ v^2 = u^3 + Au^2 + u
A 486662
よくわからなパラメータ
table:Ed25519ph, Ed25519ctx, Ed25519
Parameter edwards25519 例
p 2^255 - 19 RFC 7748
b 256
GF(p)の符号化 255-bit little-endian of {0, 1, ... p-1}
H(x) SHA-512(dom2(phflag,context)||x) RFC 6234
c 3
edwards25519の2を底とする対数 RFC 7748
n 254
d 例 -121665/121666 = 370957059346694393431380835087545651895421138798432
19016388785533085940283555 RFC 7748
a -1
B (X(P),Y(P)) RFC 7748
(151122213495354007725011514095885315114540126930418572060
46113283949847762202, 4631683569492647816942839400347
5163141307993866256225615783033603165251855960)
L 2^252+27742317777372353535851937790883648493 RFC 7748
PH(x) x
Ed25519の場合、dom2(f,c)は空文字列です。phflagの値は無関係です。コンテキスト（存在する場合）は空でなければなりません。これにより、スキームは以前に公開されたEd25519スキームと完全に同一になります。
Ed25519
dom2(f,c) は空文字
phflag の値は無関係
Ed25519ctx コンテキストそのまま?
Ed25519ph ハッシュから?
table:Ed448
Parameter edwards448
p 2^448 - 2^224 - 1 RFC 7748
b 456
GF(p)の符号化 455-bit little-endian of {0, 1, ..., p - 1}
H(x) SHAKE256(dom4(phflag,context)||x, 114)
phflag 0
c 2
edwards448の2を底とする対数 RFC 7748
n 447
d -39081 RFC 7748
a 1
B (X(P),Y(P))
(22458004029592430018760433409989603624678964163256413424612
54616869504154674060329090291928693579532825780320751
46446173674602635247710, 2988192100784814926760179304
43930673437544040154080242095928241372331506189835876
003536878655418784733982303233503462500531545062832660)
L 2^446 - 1381806680989511535200738674851542688033669247488217860989
4547503885
PH(x) x
ECDSAと似ているが乱数っぽいもの(nonce)の生成が手順に入っているためより安全? ブラウザではSafari以外が未サポート
table:強度
種類 強度bit 公開鍵長byte 署名byte, ハッシュ長 ハッシュ関数
Ed25519 128 32 (256bit) 64 (512bit) SHA-512 Ed448 224 57 (456bit) 114 (912bit) SHAKE256 パラメータは11あるが多すぎるのでセットで定義されたものを使う
ECDSAでよく使われる曲線(NISTなどが定義しているもの)とは別のEd25519とEd448があるようだ。Ed25519が一般的に使われる
p の値が $ 2^{255} - 19 なところから Ed25519
Ed448 は $ 2^{448} - 2^{224} - 1
訳(仮 わかってない)
RFC 8032 の 2
dom2(int x, byte[] y)
Ed25519の署名・検証で使う空のオクテット列
"SigEd25519 no Ed25519 collisions" || octet(x) || octet(OLEN(y)) || y
x は 0 から 255 の値 y は 255オクテットまでのオクテット列
dom4(int x, byte[] y)
"SigEd448" || octet(x) || octet(OLEN(y)) || y
3. EdDSA アルゴリズム
EdDSA は、11 個のパラメータを持つデジタル署名システムです。
11 個の入力パラメータを持つ汎用 EdDSA デジタル署名システムは、直接実装することを想定していません。パラメータの選択は、安全で効率的な運用のために重要です。代わりに、EdDSA 用の特定のパラメータ（Ed25519 や Ed448 など）を選択して実装します。場合によっては、Ed25519 と Ed448 をカバーするためにコードの再利用性を高めるために、若干の一般化を行うこともあります。
したがって、汎用 EdDSA の正確な説明は、実装者にとって特に有用ではありません。背景情報と完全性を確保するために、ここでは汎用 EdDSA アルゴリズムの簡潔な説明を示します。
n や c などのパラメータの定義は、アルゴリズムの直感的に理解しにくい手順を説明するのに役立つ場合があります。
この説明は EDDSAに厳密に従っています。
EdDSA には 11 個のパラメータがあります。
1. 奇数の素数p, EdDSAは有限体GF(p)上の楕円曲線を使用する。
2. $ 2^{b-1}>pを満たす整数b。EdDSA公開鍵は正確にb bitで署名は正確に2*b bitです。bは8の倍数がおすすめのため公開鍵と署名の長さはオクテットの整数倍になる。
3. 有限体GF(p) の要素の b-1 bit出力
4. 2*b ビット出力のハッシュ関数H Ed448はSHAKE系がひつよう
5. 2 または 3 の整数 c。秘密のEdDSAスカラーは 2^cの倍数。整数cは2を底とする補数の対数。
6. c <= n < b の整数 n。秘密のEdDSAスカラーは n + 1 ビットで、上位ビット(2^nの位置)は常に設定され、下位cビットは常にクリアされます。
7. GF(p)の非正方形要素(non-square element) d。通常の推奨は、許容できる曲線を与えるゼロに最も近い値としてそれをとることです。
8. GF(p)の非ゼロの正方形要素(non-zero square element) a。最高のパフォーマンスを得るための通常の推奨は、 p mod 4 = 1の場合は a = -1, p mod 4 = 3 の場合は a = 1 です。
9. B != (0,1) は 集合 E = { (x,y) は GF(p) x GF(p) の元であり、a * x^2 + y^2 = 1 + d * x^2 * y^2 } が成り立ちます。
10. [L]B = 0 かつ 2^c * L = #E となる奇数素数 L。#E （曲線上の点の数）は、楕円曲線 E に提供される標準データの一部であり、または余因子 * 次数として計算することもできます。
11. 「事前ハッシュ」関数PH。PureEdDSAは、PHが恒等関数であるEdDSA（つまり、PH(M) = M）を意味します。HashEdDSAは、メッセージの長さに関係なく、PHが短い出力を生成するEdDSAを意味します（たとえば、PH(M) = SHA-512(M)）。
曲線上の点は、加法のもとで群を形成し、(x3, y3) = (x1, y1) + (x2, y2)となり、次の式が成り立つ。
$ x3 = \frac{x1 * y2 + x2 * y1}{1 + d * x1 * x2 * y1 * y2} , $ y3 = \frac{y1 * y2 - a*x1*x2}{1 - d *x1* x2*y1*y2}
群の中立元は(0,1)です。
暗号アプリケーションで用いられる他の多くの曲線とは異なり、これらの式は「完全」です。つまり、曲線上のすべての点において、例外なく有効です。特に、すべての入力点において分母は非ゼロです。
3.1. 符号化
整数 0 < S < L - 1 は、リトルエンディアン形式で b ビット列 ENC(S) として符号化されます。
E の要素 (x,y) は、ENC(x, y) と呼ばれる b ビット列として符号化されます。これは、y の (b-1) ビットの符号化に、x が負の場合には 1、負でない場合には 0 となる 1 ビットを連結したものです。
GF(p) の符号化は、GF(p) の「負の」要素を定義するために使用されます。具体的には、x の (b-1) ビット エンコーディングが -x の (b-1) ビット エンコーディングよりも辞書式に大きい場合、x は負になります。
3.2. 鍵
EdDSA秘密鍵はbビットの文字列kです。ハッシュ $ H(k) = (h_0, h_1, ..., h_{(2b-1)}) は整数sを決定します。これは$ 2^n に、すべての整数 i、c <= i < nについて、$ m = 2^i * h_i の和を加えたものです。sは倍数 $ A = [s]B を決定します。EdDSA公開鍵はENC(A)です。ビット $ h_b、...、h_{(2b-1)}は、以下で署名時に使用されます。
3.3. 署名
秘密鍵 k によるメッセージ M の EdDSA 署名は、PH(M) の PureEdDSA 署名として定義されます。言い換えれば、EdDSA は PureEdDSA を用いて PH(M) に署名するだけです。
秘密鍵 k によるメッセージ M の PureEdDSA 署名は、2*b ビットの文字列 ENC(R) || ENC(S) です。R と S は以下のように導出されます。
まず、リトルエンディアン形式の 2*b ビットの文字列を {0, 1, ..., 2^(2*b) - 1} の整数として解釈し、$ r = H(h_b || ... || h_{(2b-1)} || M) と定義します。$ R = [r]B 、S = (r + H(ENC(R) || ENC(A) || PH(M)) * s) mod L とします。ここで使用される s は前のセクションで使用した値です。
3.4. 検証
公開鍵ENC(A)を用いてメッセージMにPureEdDSA署名ENC(R) || ENC(S)を検証するには、以下のようにする。入力を解析し、AとRがEの要素となり、Sが集合{0, 1, ..., L-1}の要素となるようにする。h = H(ENC(R) || ENC(A) || M)を計算し、Eにおける群方程式$ [2^c * S] B = 2^c * R + [2^c * h] A が成立するかどうかを検証する。解析が失敗した場合（Sが範囲外の場合を含む）、または群方程式が成立しない場合、署名は拒否される。
メッセージMに対するEdDSA検証は、PH(M)に対するPureEdDSA検証と定義される。
4. PureEdDSA、HashEdDSA、および命名
EdDSAアルゴリズムのパラメータの一つに「プレハッシュ」関数があります。PureEdDSAというアルゴリズムでは恒等関数の場合もあり、HashEdDSAというアルゴリズムではSHA-512のような衝突耐性ハッシュ関数の場合もあります。
どちらのアルゴリズムを使用するかは、1) 衝突耐性と2) 署名作成のためのシングルパスインターフェースのどちらの特性を重視するかによって決まります。衝突耐性とは、ハッシュ関数の衝突計算が可能である場合でも、EdDSAが安全であることを意味します。シングルパスインターフェースとは、署名作成に入力メッセージに対する1回のパスのみが必要であることを意味します。PureEdDSAでは、入力に対して2回のパスが必要です。既存の多くのAPI、プロトコル、および環境では、デジタル署名アルゴリズムは入力に対して1回のパスのみで済むと想定されており、それ以外のものをサポートするにはAPIや帯域幅の制約がある場合があります。
署名アルゴリズムの選択に関わらず、ほとんどの署名用途ではシングルパス検証は不可能であることに注意してください。これは、ほとんどの場合、署名が検証されるまでメッセージを処理できず、メッセージ全体を検証する必要があるためです。
このドキュメントでは、HashEdDSAバリアントEd25519phおよびEd448ph、およびPureEdDSAバリアントEd25519およびEd448を生成するパラメータを指定します。
5. EdDSAインスタンス
このセクションでは、PureEdDSAおよびHashEdDSAの各変種（およびEd25519スキームのコンテキスト拡張）について、edwards25519曲線およびedwards448曲線の一般的なEdDSAアルゴリズムをインスタンス化します。したがって、5つの異なるパラメータセットについて説明します。
5.1. Ed25519ph、Ed25519ctx、および Ed25519
Ed25519 は、以下の方法で EdDSA インスタンス化されます。
table:表1 Ed25519のパラメータ
Parameter edwards25519 例
p 2^255 - 19 RFC 7748
b 256
GF(p)の符号化 255-bit リトルエンディアン符号化ののののも of {0, 1, ... p-1}
H(x) SHA-512(dom2(phflag,context)||x) RFC 6234
c 3
edwards25519の2を底とする対数 RFC 7748
n 254
d 例 -121665/121666 = 370957059346694393431380835087545651895421138798432
19016388785533085940283555 RFC 7748
a -1
B (X(P),Y(P)) RFC 7748
(151122213495354007725011514095885315114540126930418572060
46113283949847762202, 4631683569492647816942839400347
5163141307993866256225615783033603165251855960)
L 2^252+27742317777372353535851937790883648493 RFC 7748
PH(x) x
Ed25519の場合、dom2(f,c)は空文字列です。phflagの値は無関係です。context（存在する場合）は空でなければなりません。これにより、スキームは以前に公開されたEd25519スキームと完全に同一になります。
Ed25519ctx の場合、phflag=0 です。context入力は空であってはなりません。
Ed25519ph の場合、phflag=1 で、PH は SHA512 です。つまり、入力は Ed25519 で署名される前に SHA-512 でハッシュ化されます。
contextの値は署名者と検証者によって設定され（最大 255 オクテット、デフォルトは空文字列ですが、Ed25519 の場合はcontextを持つことができません）、検証が成功するにはオクテットごとに一致する必要があります。
使用される曲線は、座標変換の下で Curve25519 CURVE25519 と同等です。つまり、離散対数問題の難しさは Curve25519 と同じです。 5.1.1. 剰余演算
$ p = 2^{255} - 19 を法とする演算を効率的かつ安全に実装する方法については、Curve25519 CURVE25519 を参照してください。p を法とする逆元演算については、恒等式 $ x^{-1} = x^{(p-2)} (mod p) を使用することを推奨します。ゼロを反転することは決して行ってはなりません。なぜなら、ゼロを反転すると無効な入力が要求され、その場合は事前に検出されるか、計算エラーとなるからです。 点のデコード、つまり「解凍」には、p を法とする平方根が必要です。これは、Tonelli-Shanks アルゴリズム、または p = 5 (mod 8) の特殊なケースを用いて計算できます。a の平方根を求めるには、まず候補となる根 $ x = a^{((p+3)/8)} (mod p) を計算します。この場合、以下の 3 つのケースが考えられます。
$ x^2 = a (mod p)。この場合、x は平方根です。
$ x^2 = -a (mod p)。すると、$ 2^{((p-1)/4)} * x は平方根になります。
a は p を法とした平方根ではありません。
5.1.2. エンコード
すべての値はオクテット文字列としてエンコードされ、整数はリトルエンディアン方式でエンコードされます。つまり、32オクテット文字列 h $ h[0],...h[31] は、整数 $ h[0] + 2^8 * h[1] + ... + 2^{248} * h[31] を表します。
0 <= x,y < p の範囲の座標を持つ曲線点 (x,y) は、次のようにエンコードされます。まず、y座標を32オクテットのリトルエンディアン文字列としてエンコードします。最後のオクテットの最上位ビットは常に0です。点のエンコードを作成するには、x座標の最下位ビットを最後のオクテットの最上位ビットにコピーします。
---- RFC 訳
ssh では利用できるがhttps TLSでは未対応の環境がまだある 利用
RFC 8419 Use EdDSA署名 in CMS RFC 8420 Using the Edwards-Curve Digital Signature Algorithm (EdDSA) in the Internet Key Exchange Protocol Version 2 (IKEv2)