EdDSA

Edwards-Curve Digital Signature Algorithm (EdDSA)

Ed448-Goldilocks

NIST FIPS 186-5 Digital Signature Standard (DSS)

日本語の資料?

ディジタル署名アルゴリズム EdDSA の実装性能調査

ディジタル署名 EdDSA の構成の安全性に関する調査および評価

利用

一般的なものと、署名に使われている特定の曲線と2段階くらいある

RFC 7748と8032は特定の曲線を使ったもの

実装はRFC 8032だけでも読めば可(ハッシュ関数SHA-512, SHAKE256は別途必要)

署名

ハッシュ込みなので短い固定長データのみ対象ではない

EdDSAでも直接暗号には利用できない

Bは基準になる点 x, y座標が各アルゴリズムで1つ決まっている

ざっくりした解説

鍵の生成

秘密鍵 乱数 dビットの乱数 長さを変えても使えそうだが強度への影響は不明

h 秘密鍵のハッシュ、乱数の代わりに使用する、鍵ごとに特定の値が得られる

h = H(秘密鍵) SHA512(64byte) または SHAKE256(114byte出力)

ha と hb の2つに分ける

h | 前半 s の元 | 後半 prefix |

ha を符号なしlittle endianで数値化し、スカラーs とする

hb は ハッシュの前に入れるprefix として使用する

AのY座標の最上位ビットにX座標の最下位ビットを載せたものが座標をバイト列に符号化したもの

XはY座標から復元可能

秘密鍵と秘密鍵から生成される成分(h，s，prefix)は秘密

公開鍵Aからsは逆算できない

PureEdDSAの場合 (Ed448はprefixの前にdom4が必要)

署名

メッセージ M

r = H( prefix || M ) // DSA, ECDSA では乱数な部分

k = H( R || A || M)

S = (r + k * s) mod L

署名 = R || S

検証

署名からRとS

公開鍵 A

h = H( R || A || M) (mod L)

[S]B = R + [h]A

[r+k*s]B = [r]B + [h][s]B

h = k からMの証明

基準になるBは楕円曲線ごとに指定あり

楕円曲線は掛け算を楕円曲線のPointからの掛け算に置き換えたもの

ECDSAでは例外の計算があったが、EdDSAでは例外的な計算が必要ない曲線を使用する

PureEdDSAとHashEdDSAがある RFC 8419 CMSやRFC 8446 TLS 1.3ではPureEdDSAを使用

リトルエンディアンを採用、Intel系などに最適化

ハッシュアルゴリズムとハッシュサイズが決まっているのでECDSAより署名用OIDも少なかったりする?

table:種類

署名用 暗号用(鍵交換・旧)

秘密鍵長(bit) 256 456 256

公開鍵長(bit) 256 456 256 456

署名長 512 912

秘密鍵はハッシュにかけられるので可変長でもいいのかも

語

有限群 finite groups

群 groups

逆元 reverse element

ぐらいがあればいい?

秘密鍵を作ってみる

EdDSAの鍵はOCTETSTRINGに入れてあるのでそうするだけ

code:Java

package てきとう;

import java.security.SecureRandom;

import net.siisise.iso.asn1.tag.ASN1DERFormat;

import net.siisise.iso.asn1.tag.OCTETSTRING;

public class EdDSA {

// Ed25519 (仮)

static final int b = 256;

public byte[] genPrivateKey() {

try {

SecureRandom srnd = SecureRandom.getInstanceStrong();

srnd.nextBytes(key);

OCTETSTRING oct = new OCTETSTRING(key);

ASN1DERFormat der = new ASN1DERFormat();

return oct.rebind(der);

} catch (NoSuchAlgorithmException e) {

// ないので略

throw new IllegalStateException(e);

}

}

}

公開鍵

Little Endian で数字化 s

y座標をLittle Endianで文字列に変換

x座標の最下位ビットをy最上位ビットにもってくる

結果が公開鍵

同じ鍵長で3種類のあるごりずむ

table:種類

PureEdDSA context拡張 HashEdDSA

符号名的なもの Ed25519 Ed448 Ed25519ctx Ed25519ph Ed448ph

phflag 0 0 1 1

context(最大255) なし (空文字) あり(必須) なし(空文字列)

dom2(phflag, context) 空 dom4(0,"") (0,context) (1,"")

HashEdDSA(Ed25519ph)はアルゴリズム内でハッシュ計算する場合 (1pass?)

PureEdDSA(Ed25519)は事前にハッシュ化されているものを使ったりする場合(アルゴリズムは同じ? 2pass?)

Ed25519ctx は PureEdDSAにAES-GCM(AEAD)やcSHAKEで使うような追加のパラメータに相当するものを使う場合

PureEdDSA Ed448はcontext拡張相当の形でdom4を省略せず動作する Ed448ctxは存在しない

特に何もなければPureEdDSAを使っているよ

id-X25519 OBJECT IDENTIFIER ::= { 1 3 101 110 }

id-X448 OBJECT IDENTIFIER ::= { 1 3 101 111 }

id-Ed25519 OBJECT IDENTIFIER ::= { 1 3 101 112 }

id-Ed448 OBJECT IDENTIFIER ::= { 1 3 101 113 }

code:RFC 8419 2.2. 2.3

sigAlg-Ed25519 ALGORITHM ::= { OID id-Ed25519 }

sigAlg-Ed448 ALGORITHM ::= { OID id-Ed448 }

hashAlg-SHA-512 ALGORITHM ::= { OID id-sha512 }

hashAlg-SHAKE256 ALGORITHM ::= { OID id-shake256 }

hashAlg-SHAKE256-LEN ALGORITHM ::= { OID id-shake256-len

PARAMS ShakeOutputLen }

hashAlgs OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)

country(16) us(840) organization(1)

gov(101) csor(3) nistalgorithm(4) 2 }

id-sha512 OBJECT IDENTIFIER ::= { hashAlgs 3 }

id-shake256 OBJECT IDENTIFIER ::= { hashAlgs 12 }

id-shake256-len OBJECT IDENTIFIER ::= { hashAlgs 18 }

ShakeOutputLen ::= INTEGER -- ビット出力長

秘密鍵

algorithm AlgorithmIdentifier(OIDのみ パラメータはnullもなし)

privateKey PrivateKey

privateKey は中身もOCTETSTRINGなので2重になっている Ed25519は32byte

(ECDSAの場合はOCTETSTRING内にバイナリ直書き?)

$ v^2 = u^3 + Au^2 + u

Ax^2 + y^2 = 1 + Dx^2y^2

RFC 8032 3 EdDSA

よくわからない11のパラメータ

1. 奇数の素数 p 楕円曲線は有限体 GF(p) を使う

3. 有限体GF(p)の要素 A (b-1) bit出力 どれ?

ENCのこと?

4. 2b bit 出力する暗号ハッシュ関数 H SHA512

H SHA512 (Ed25519)

H SHAKE256(114byte) (Ed448)

7. GF(p)のnon-squate element(非正方形要素) d 0に最も近い値?

8. GF(p)の非ゼロのsquate element(正方形要素) a 推奨 p mod 4 = 1 のとき -1 p mod 4 = 3のとき 1

9. 要素 B != (0,1) は セット E = {{x, y} は GF(p)xGF(p)のメンバー a * x^2 + y^2 = 1 + d * x^2 * y^2 } ?

x は yから計算できるのでyだけでもいい

cofactor * order

order とL?はべき乗で元に戻る値

11. プリハッシュ PH(x) PureEdDSAではなにもしない PH(M) = M

PH(x) = SHA512(x) (Ed25519ph)

PH(x) = SHAKE256(x,64byte) (Ed448ph)

秘密鍵の長さは固定ではない? SHA512のブロック長は?

RFC 8032 5.1 表1 Ed25519のパラメータ

table:Ed25519ph, Ed25519ctx, Ed25519

p 2^255 - 19 RFC 8032 1, 7748

b 256 RFC 8032 2

鍵長, 署名/2?

GF(p)の符号化 255-bit little-endian of {0, 1, ... p-1}

H(x) SHA-512(dom2(phflag,context)||x) RFC 8032 4, RFC 6234

c 3 RFC 8032 5

edwards25519のcofactor = 2^c の2を底とする対数 RFC 7748

n 254 RFC 8032 6

d -121665/121666 RFC 8032 7

= 370957059346694393431380835087545651895421138798432

19016388785533085940283555 RFC 7748

a -1 RFC 8032 8 RFC 7748 d

B (X(P),Y(P)) RFC 8032 9 RFC 7748

(151122213495354007725011514095885315114540126930418572060

46113283949847762202, 4631683569492647816942839400347

5163141307993866256225615783033603165251855960)

L 2^252+27742317777372353535851937790883648493 order? RFC 8032 10 RFC 7748

order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed

PH(x) x RFC 8032 11

他

cofactor 8 = 2^c

A 486662 RFC 8032 3

dom2 PureEdDSAでは空文字 RFC 8032 4

符号化が増えてAが減っている?

Ed25519

H(x) 2*b bit出力できる暗号化ハッシュ関数 Ed25519の場合は512bitのSHA-512

整数c 2または3 3固定 EdDSAスカラーは 2^c の倍数らしい スカラー(秘密鍵の値)の下位cビットをクリアする

c <= n < b の整数 n 正確に n + 1 bitの秘密鍵にするための 2^nを設定するための値 n = b - 1 くらい

GF(p)の非正方形要素d 謎の値

2*b 署名長、ハッシュ

p は素数、GF(p)の上でいろいろする

Ed25519の場合、dom2(f,c)は空文字列です。phflagの値は無関係です。コンテキスト（存在する場合）は空でなければなりません。これにより、スキームは以前に公開されたEd25519スキームと完全に同一になります。

Ed25519

dom2(f,c) は空文字

phflag の値は無関係 ( PH(x) で未使用)

Ed25519ctx コンテキストそのまま?

Ed25519ph ハッシュから?

Ed448 は RFC 7748 では4.2.の3つある内の後の方、EdWards448だったりGoldilocks と呼ばれる方を使う d と B が違うので注意

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

ブラウザではSafari以外が未サポート(TLS 1.3以降でサポート可?)

table:強度

種類 強度bit 公開鍵長byte 署名byte, ハッシュ長 ハッシュ関数

パラメータは11あるが多すぎるのでセットで定義されたものを使う

ECDSAでよく使われる曲線(NISTなどが定義しているもの)とは別のEd25519とEd448があるようだ。Ed25519が一般的に使われる

訳(仮 わかってない)

RFC 8032 の 2

GF(p) p要素の有限体

dom2(int x, byte[] y)

Ed25519の署名・検証で使う空のオクテット列

x は 0 から 255 の値 y は 255オクテットまでのオクテット列

PureEdDSAでは省略されている

dom4(int x, byte[] y)

Ed448の署名・検証で使う空のオクテット列

"SigEd448" || octet(x) || octet(OLEN(y)) || y

注) こちらは省略できない

2. 表記法と規則

このドキュメントでは、以下の表記法が使用されています。

(u,v) x 座標が u、y 座標が v の楕円曲線上の点

OCTET(x) 値 x を持つオクテット

OLEN(x) 文字列 x のオクテット数

括弧（つまり「(」と「)」）は式をグループ化するために使用されます。これは、演算子間の結合順序に依存した記述を避けるためです。

ビット文字列は、ビットを左から右へ取り、各オクテットの最下位ビットから最上位ビットへとパックし、各オクテットがいっぱいになったら次のオクテットに移動することで、オクテット文字列に変換されます。オクテット文字列からビット文字列への変換は、このプロセスの逆です。例えば、16ビットのビット文字列

b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15

は、2つのオクテット x0 と x1 に（この順序で）変換されます。

x0 = b7*128+b6*64+b5*32+b4*16+b3*8+b2*4+b1*2+b0

x1 = b15*128+b14*64+b13*32+b12*16+b11*8+b10*4+b9*2+b8

リトルエンディアン方式によるビットへのエンコードでは、ビットは左から右へ、最下位ビットから最上位ビットへと配置されます。上記で定義したビット文字列からオクテット文字列への変換と組み合わせると、リトルエンディアン方式によるオクテットへのエンコードが行われます（長さが8の倍数でない場合、最後のオクテットの最上位ビットは未使用のままになります）。

3. EdDSA アルゴリズム

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

11 個の入力パラメータを持つ汎用 EdDSA デジタル署名システムは、直接実装することを想定していません。パラメータの選択は、安全で効率的な運用のために重要です。代わりに、EdDSA 用の特定のパラメータ（Ed25519 や Ed448 など）を選択して実装します。場合によっては、Ed25519 と Ed448 をカバーするためにコードの再利用性を高めるために、若干の一般化を行うこともあります。

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

n や c などのパラメータの定義は、アルゴリズムの直感的に理解しにくい手順を説明するのに役立つ場合があります。

この説明は EDDSAに厳密に従っています。

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

1. 奇数の素数p, EdDSAは有限体GF(p)上の楕円曲線を使用する。

3. 有限体GF(p) の要素(element)の b-1 bit出力

4. 2*b ビット出力のハッシュ関数H。衝突が起こりにくいハッシュ関数（保守的なハッシュ関数）が推奨されますが、EdDSA の総コストに大きな影響を与えません。

5. 2 または 3 の整数 c。秘密のEdDSAスカラーは 2^cの倍数です。整数cは2を底とする補数の対数(cofactor)。

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 です。

11. 「事前ハッシュ」関数PH。PureEdDSAは、PHが恒等関数であるEdDSA（つまり、PH(M) = M）を意味します。HashEdDSAは、メッセージの長さに関係なく、PHが短い出力を生成するEdDSAを意味します（たとえば、PH(M) = SHA-512(M)）。

曲線上の点は、加法のもとで群を形成し、(x3, y3) = (x1, y1) + (x2, y2)となり、次の式が成り立つ。

群の中立元は(0,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 は負になります。

秘密鍵 k によるメッセージ M の EdDSA 署名は、PH(M) の PureEdDSA 署名として定義されます。言い換えれば、EdDSA は PureEdDSA を用いて PH(M) に署名するだけです。

秘密鍵 k によるメッセージ M の PureEdDSA 署名は、2*b ビットの文字列 ENC(R) || ENC(S) です。R と S は以下のように導出されます。

メッセージMに対するEdDSA検証は、PH(M)に対するPureEdDSA検証と定義される。

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のパラメータ

パラメータ edwards25519 例

b 256

GF(p)の符号化 255-bit リトルエンディアン符号化の {0, 1, ... p-1}

H(x) SHA-512(dom2(phflag,context)||x) RFC 6234

c 3

edwards25519の2を底とする対数(cofactor) RFC 7748 cofactor

n 254

d 例 -121665/121666 = 370957059346694393431380835087545651895421138798432

19016388785533085940283555 RFC 7748 d

a -1

B (X(P),Y(P)) RFC 7748 (X(P),Y(P))

(151122213495354007725011514095885315114540126930418572060

46113283949847762202, 4631683569492647816942839400347

5163141307993866256225615783033603165251855960)

L 2^252+27742317777372353535851937790883648493 RFC 7748 order

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を持つことができません）、検証が成功するにはオクテットごとに一致する必要があります。

a は p を法とした平方根ではありません。

0 <= x,y < p の範囲の座標を持つ曲線点 (x,y) は、次のようにエンコードされます。まず、y座標を32オクテットのリトルエンディアン文字列としてエンコードします。最後のオクテットの最上位ビットは常に0です。点のエンコードを作成するには、x座標の最下位ビットを最後のオクテットの最上位ビットにコピーします。

32オクテットの文字列として与えられた点のデコードは、もう少し複雑です。

1. まず、文字列をリトルエンディアン表現の整数として解釈します。この数値のビット255はx座標の最下位ビットであり、この値をx_0とします。このビットをクリアするだけでy座標が復元されます。結果の値がp以上であれば、デコードは失敗します。

$ x = (u/v)^{(p+3)/8} = u(u v)^{(p-5)/8} (\mod p)

3. ここでも、3つのケースがあります。

3. それ以外の場合、p を法とする平方根は存在しないため、デコードは失敗します。

4. 最後に、x_0 ビットを使用して正しい平方根を選択します。x = 0 かつ x_0 = 1 の場合、デコードは失敗します。それ以外の場合、x_0 != x mod 2 の場合、x <-- p - x と設定します。デコードされた点 (x,y) を返します。

点の加算には、以下の方法が推奨されます。点 (x,y) は、拡張同次座標 (X, Y, Z, T) で表され、x = X/Z、y = Y/Z、x * y = T/Z となります。

中立点は (0,1) です。これは、Z が 0 以外の場合、拡張同次座標 (0, Z, Z, 0) と等価です。

A = (Y1-X1)*(Y2-X2)

B = (Y1+X1)*(Y2+X2)

C = T1*2*d*T2

D = Z1*2*Z2

E = B-A

F = D-C

G = D+C

H = B+A

X3 = E*F

Y3 = G*H

T3 = E*H

Z3 = F*G

A = X1^2

B = Y1^2

C = 2*Z1^2

H = A+B

E = H-(X1+Y1)^2

G = A-B

F = C+G

X3 = E*F

Y3 = G*H

T3 = E*H

Z3 = F*G

32バイトの公開鍵は、以下の手順で生成されます。

1. 32バイトの秘密鍵をSHA-512でハッシュし、ダイジェストを64オクテットの大きなバッファ（hと表記）に格納します。公開鍵の生成には、下位32バイトのみが使用されます。

2. バッファの刈り込み：最初のオクテットの下位3ビットをクリアし、最後のオクテットの最上位ビットをクリアし、最後のオクテットの上位から2番目のビットをセットします。

署名手順への入力は、秘密鍵、32オクテットの文字列、および任意サイズのメッセージMです。Ed25519ctxおよびEd25519phの場合、さらに最大255オクテットのコンテキストCとフラグF（Ed25519ctxの場合は0、Ed25519phの場合は1）が存在します。

2. SHA-512(dom2(F, C) || prefix || PH(M))を計算します。ここで、Mは署名するメッセージです。 64オクテットのダイジェストをリトルエンディアンの整数rとして解釈する。

4. SHA512(dom2(F, C) || R || A || PH(M)) を計算し、64オクテットのダイジェストをリトルエンディアン整数 k として解釈する。

5. S = (r + k * s) mod L を計算する。効率を上げるため、まず k を法として減算する。

6. R (32オクテット) と S のリトルエンディアンエンコード (32オクテット。最終オクテットの最上位3ビットは常に0) を連結した署名を作成する。

1. 公開鍵Aを用いてメッセージMの署名を検証する。FはEd25519ctxの場合は0、Ed25519phの場合は1であり、Ed25519ctxまたはEd25519phが使用されている場合はコンテキストCとする。まず、署名を32オクテットの2つの部分に分割する。前半Rを点R'としてデコードし、後半を0 <= S < Lの範囲の整数Sとしてデコードする。公開鍵Aを点A'としてデコードする。いずれかのデコードが失敗した場合（Sが範囲外の場合を含む）、署名は無効である。

2. SHA512(dom2(F, C) || R || A || PH(M))を計算し、64オクテットのダイジェストをリトルエンディアンの整数kとして解釈する。

5.2. Ed448ph と Ed448

Ed448は 以下の方法で EdDSA インスタンス化されます。

table:Ed448のパラメータ

パラメータ 値 RFC 7748

p edwards448のp (例, 2^448 - 2^224 - 1) p

b 456

GF(p)の符号化 455-bit リトルエンディアン符号化の {0, 1, ..., p-1}

H(x) SHAKE256(dom4(phflag,context)||x, 114)

phflag 0

c edwards448の2を底とする対数(cofactor) (例 2) cofactor

n 447

d edwards448 の d (例 -39081) d

a 1

B (例 (224580 (X(P),Y(P))

04029592430018760433409989603624678964163256413424612

54616869504154674060329090291928693579532825780320751

46446173674602635247710, 2988192100784814926760179304

43930673437544040154080242095928241372331506189835876

003536878655418784733982303233503462500531545062832660))

L 2^446 - 138180668098951153520073867485154268803366924

74882178609894547503885 order

PH(x) x (例 恒等関数)

Ed448ph も同様ですが、PH が SHAKE256(x, 64) で phflag が 1 です。つまり、入力は署名前にハッシュ定数を変更した Ed448 でハッシュ化されます。

contextの値は署名者と検証者によって設定され（最大 255 オクテット、デフォルトは空文字列）、検証が成功するにはオクテット毎に一致する必要があります。

この曲線は、基点を変更した Ed448-Goldilocks と同等であり、離散対数の難しさは維持されます。

5.2.2. エンコード

0 <= x,y < p の範囲の座標を持つ曲線点 (x,y) は、次のようにエンコードされます。まず、y座標を57オクテットのリトルエンディアン文字列としてエンコードします。最後のオクテットは常に0です。点のエンコードを作成するには、x座標の最下位ビットを最後のオクテットの最上位ビットにコピーします。

5.2.3. デコード

57オクテットの文字列として与えられた点のデコードは、もう少し複雑です。

1. まず、文字列をリトルエンディアン表現の整数として解釈します。この数値のビット455はx座標の最下位ビットであり、この値をx_0とします。このビットをクリアするだけでy座標が復元されます。結果の値がp以上であれば、デコードは失敗します。

$ x = (u/v)^{(p+1)/4} = u (u v)^{(p-3)/4} (\mod p)

4. 最後に、x_0 ビットを使って正しい平方根を選択します。x = 0 かつ x_0 = 1 の場合、デコードは失敗します。それ以外の場合、x_0 != x mod 2 の場合、x <-- p - x に設定します。デコードされた点 (x,y) を返します。

5.2.4. 点の加算

点の加算には、以下の方法が推奨されます。点 (x, y) は射影座標 (X, Y, Z) で表され、x = X/Z、y = Y/Z となります。

中立点は (0, 1) です。これは、Z が 0 でない任意の点に対して、射影座標 (0, Z, Z) と等価です。

A = Z1*Z2

B = A^2

C = X1*X2

D = Y1*Y2

E = d*C*D

F = B-E

G = B+E

H = (X1+Y1)*(X2+Y2)

X3 = A*F*(H-C-D)

Y3 = A*G*(D-C)

Z3 = F*G

B = (X1+Y1)^2

C = X1^2

D = Y1^2

E = C+D

H = Z1^2

J = E-2*H

X3 = (B-E)*J

Y3 = E*(C-D)

Z3 = E*J

5.2.5. 鍵生成

57バイトの公開鍵は、以下の手順で生成されます。

1. 57バイトの秘密鍵をSHAKE256(x, 114)を用いてハッシュし、ダイジェストを114オクテットの大きなバッファ（hと表記）に格納します。公開鍵の生成には、下位57バイトのみが使用されます。

2. バッファのプルーニング：最初のオクテットの最下位2ビットをクリアし、最後のオクテットの8ビットすべてをクリアし、最後から2番目のオクテットの最上位ビットをセットします。

署名手続きへの入力は、秘密鍵、57オクテットの文字列、フラグF（Ed448の場合は0、Ed448phの場合は1）、最大255オクテットのコンテキストC、および任意サイズのメッセージMである。

2. SHAKE256(dom4(F, C) || prefix || PH(M), 114) を計算します。ここで、M は署名するメッセージ、F は Ed448ph の場合は 1、Ed448 の場合は 0、C は使用するコンテキストです。114 オクテットのダイジェストをリトルエンディアンの整数 r として解釈します。

4. SHAKE256(dom4(F, C) || R || A || PH(M), 114) を計算し、114 オクテットのダイジェストをリトルエンディアンの整数 k として解釈します。

5. S = (r + k * s) mod L を計算します。効率を上げるため、まず k を法として L を法として縮約します。

6. R (57 オクテット) と S のリトルエンディアン符号化 (57 オクテット、最後のオクテットの最上位 10 ビットは常に 0) を連結した署名を作成します。

1. コンテキスト C と公開鍵 A を用いてメッセージ M の署名を検証する。F は Ed448 の場合は 0、Ed448ph の場合は 1 とする。まず、署名を 57 オクテットの 2 つの部分に分割する。前半を点 R として、後半を範囲 0 <= s < L の整数 S としてデコードする。公開鍵 A を点 A' としてデコードする。いずれかのデコードが失敗した場合（S が範囲外の場合を含む）、署名は無効である。

2. SHAKE256(dom4(F, C) || R || A || PH(M), 114) を計算し、114 オクテットのダイジェストをリトルエンディアンの整数 k として解釈する。

6. Ed25519 Python による実装例

本節の残りの部分では、Ed25519 を Python (バージョン 3.2 以降) で実装する方法を例として説明します。完全な実装については付録 A を、テストベクトルで実行するためのテストドライバについては付録 B を参照してください。

このコードは、すべての入力に対して正しいことが証明されておらず、サイドチャネル攻撃に対する防御力も備えていないため、本番環境での使用を想定したものではありません。実装者が独自の実装を行う際に役立つよう、アルゴリズムを説明することを目的としています。

まず、必要な準備事項をいくつか説明します。

code:code

import hashlib

def sha512(s):

return hashlib.sha512(s).digest()

# Base field Z_p

p = 2**255 - 19

def modp_inv(x):

return pow(x, p-2, p)

# 曲線定数 Curve constant

d = -121665 * modp_inv(121666) % p

# Group order

q = 2**252 + 27742317777372353535851937790883648493

def sha512_modq(s):

return int.from_bytes(sha512(s), "little") % q

# Points are represented as tuples (X, Y, Z, T) of extended

# coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

# 点は拡張座標の組（X、Y、Z、T）として表され、

# x = X/Z、y = Y/Z、x*y = T/Zとなります。

def point_add(P, Q):

E, F, G, H = B-A, D-C, D+C, B+A;

return (E*F, G*H, F*G, E*H);

# Computes Q = s * Q

def point_mul(s, P):

Q = (0, 1, 1, 0) # Neutral element

while s > 0:

if s & 1:

Q = point_add(Q, P)

P = point_add(P, P)

s >>= 1

return Q

def point_equal(P, Q):

# x1 / z1 == x2 / z2 <==> x1 * z2 == x2 * z1

return False

return False

return True

# Square root of -1

modp_sqrt_m1 = pow(2, (p-1) // 4, p)

# Compute corresponding x-coordinate, with low bit corresponding to

# sign, or return None on failure

def recover_x(y, sign):

if y >= p:

return None

x2 = (y*y-1) * modp_inv(d*y*y+1)

if x2 == 0:

if sign:

return None

else:

return 0

# Compute square root of x2

x = pow(x2, (p+3) // 8, p)

if (x*x - x2) % p != 0:

x = x * modp_sqrt_m1 % p

if (x*x - x2) % p != 0:

return None

if (x & 1) != sign:

x = p - x

return x

# Base point

g_y = 4 * modp_inv(5) % p

g_x = recover_x(g_y, 0)

G = (g_x, g_y, 1, g_x * g_y % p)

def point_compress(P):

return int.to_bytes(y | ((x & 1) << 255), 32, "little")

def point_decompress(s):

if len(s) != 32:

raise Exception("Invalid input length for decompression")

y = int.from_bytes(s, "little")

sign = y >> 255

y &= (1 << 255) - 1

x = recover_x(y, sign)

if x is None:

return None

else:

return (x, y, 1, x*y % p)

def secret_expand(secret):

if len(secret) != 32:

raise Exception("Bad size of private key")

h = sha512(secret)

a &= (1 << 254) - 8

a |= (1 << 254)

def secret_to_public(secret):

(a, dummy) = secret_expand(secret)

return point_compress(point_mul(a, G))

def sign(secret, msg):

a, prefix = secret_expand(secret)

A = point_compress(point_mul(a, G))

r = sha512_modq(prefix + msg)

R = point_mul(r, G)

Rs = point_compress(R)

h = sha512_modq(Rs + A + msg)

s = (r + h * a) % q

return Rs + int.to_bytes(s, 32, "little")

def verify(public, msg, signature):

if len(public) != 32:

raise Exception("Bad public key length")

if len(signature) != 64:

raise Exception("Bad signature length")

A = point_decompress(public)

if not A:

return False

R = point_decompress(Rs)

if not R:

return False

if s >= q: return False

h = sha512_modq(Rs + public + msg)

sB = point_mul(s, G)

hA = point_mul(h, A)

return point_equal(sB, point_add(R, hA))

7. テストベクトル

このセクションには、Ed25519ph、Ed25519ctx、Ed448ph、Ed25519、およびEd448のテストベクトルが含まれています。

各セクションには、一連のテストベクトルが含まれています。オクテットは16進数でエンコードされ、読みやすさのために空白が挿入されています。Ed25519、Ed25519ctx、およびEd25519phの秘密鍵と公開鍵は32オクテット、署名は64オクテットです。Ed448およびEd448phの秘密鍵と公開鍵は57オクテット、署名は114オクテットです。メッセージの長さは任意です。コンテキストが空でない場合、1～255オクテットで指定されます。

7.1. Ed25519 のテストベクトル

(略)

付録A. Ed25519/Ed448 Pythonライブラリ

以下は、Pythonで記述されたEd25519/Ed448の実装例です。バージョン3.2以上が必要です。

注: このコードは本番環境向けではありません。すべての入力に対して正しい結果を生成しますが、処理速度が遅く、サイドチャネル攻撃の回避策も備えていません。

(略)

付録B. ライブラリドライバー

以下は、上記のライブラリを使用して、対話型使用または自己チェックのための計算を実行するコマンドラインツールです。

(略)

謝辞

EdDSAとEd25519は、Daniel J. Bernstein、Niels Duif、Tanja Lange、Peter Schwabe、Bo-Yin Yangによる論文で最初に説明されました。Ed448曲線はMike Hamburgによるものです。

この文書の初期ドラフト版は、Niels Moellerが共著しました。

この文書に対するフィードバックは、Werner Koch、Damien Miller、Bob Bradley、Franck Rondepierre、Alexey Melnikov、Kenny Paterson、Robert Edmondsからいただきました。

Ed25519のテストベクトルは、Bob Bradleyによって3つの異なる実装（TweetNaClに基づく実装1つとSUPERCOPのコードに基づく実装2つ）を用いて二重チェックされました。

---- RFC 訳