Ed25519 実装の詳細
Curve25519 と Edwards 曲線
Edwards 曲線デジタル署名アルゴリズム Ed25519 で
は、Curve25519 と双有理同値の次の楕円曲線が使用
されます。有限体の位数は、素数
p = 2255 - 19
です。
-x2
+
y2
= 1 +
dx2y2
d
= -
121665121666
d
は実装における定数
_D
に対応します。また、_L
は
基点の位数を表す素数です。
l
= 2252
+ 27742317777372353535
851937790883648493
基点
_B
は、y
=
u
- 1u
+ 1
および
u
= 9
より次の通りと
なります。
B
= (-((45)2
- 1-
121665121666(45)2
+ 1)12,
45)
x
座標と
y
座標に対応したスカラー倍算
_MUL2
は、ス
カラーのビット列の表現に従って、1 の場合に点の加算
_ADD2
を行い、点の和をループの進行に伴い
_DBL2
で
2 の累乗倍する動作内容です。奇数倍の場合は、最下位
ビットが 1 であることを用いて
_ADD2
の出力を結果と
します。T
=
XYZ
を追加した拡張座標を使用して、演
算を実装します。
_DBL2
は次の式を実行します。
X
= 2X0Y0(2Z02
+
X02
-
Y02)
Y
= (X02
+
Y02)(X02
-
Y02)
Z
= (X02
-
Y02)(2Z02
+
X02
-
Y02)
T
= 2X0Y0(X02
+
Y02)
_ADD2
は次の式を実行します。
X
= 4(X0Y1
+
X1Y0)(Z0Z1
-
dT0T1)
Y
= 4(X0X1
+
Y0Y1)(Z0Z1
+
dT0T1)
Z
= 4(Z0Z1
+
dT0T1)(Z0Z1
-
dT0T1)
T
= 4(X0Y1
+
X1Y0)(X0X1
+
Y0Y1)
_2D
は、_ADD2
に使用する式変形の定数
2d
です。
_ENC
と
_DEC
は
x
座標と
y
座標を公開鍵や署名とし
て扱うために使用します。_ENC
では
y
座標の値と
x
座標の最下位 1 ビットを保存します。_DEC
は点を復元
します。y
座標が
0
以上
p
未満であることを確認した
後、x
座標を、y
座標と
x
座標の最下位 1 ビットから
復元します。x
座標は
y
座標のみを含む平方根であり、
値を確定するために
x
座標の最下位 1 ビットを使用し
ます。偶数の場合に正、奇数の場合に負と定義され、こ
のビットが 0 の場合は偶数、1 の場合は奇数です。x
と偶数・奇数が相違する場合には
0
-
x
を割り当てます。
x
= 0
で相違するとき、入力は無効と判断します。また、
x
の解が存在しない場合や、y
座標が範囲外である場合
にも入力が無効となります。_DEC
の戻り値は 0 または
1 で、入力が無効な場合に 1 となります。x
が示す平方
根は次の通りに求めます。
x2
=
y2
- 1dy2
+ 1
mod
p
_SQRT
には、上記の分子と分母を個別に入力します。
p
= 5 mod 8
であることから、以下の特殊な式を使用
できます。定数
_IMG
は
(-1)12
mod
p
です。この値
は、2p
- 14
mod
p
を計算して得ることができます。
x
=
(y2
- 1dy2
+ 1)p
+ 38
mod
p
=
(y2
- 1)(dy2
+ 1)3
((y2
- 1)(dy2
+ 1)7)p
- 58
mod
p
x
=
(-1)12(y2
- 1)(dy2
+ 1)3
((y2
- 1)(dy2
+ 1)7)p
- 58
mod
p
dy2
+ 1
の除算を乗算に変更する際、Fermat の小定理
から
1
の乗算を利用し、指数を
p
- 1 - p
+ 38
にしま
す。p
- 58
= 2252 - 3
は
_INV
と同様に計算できます。
x
は 2 通り考慮し、元の式を満たすものが平方根です。
(dy2
+ 1)x2
=
y2
- 1 mod
p
_SQRT
の戻り値は 0 または 1 です。平方根が存在しな
い場合は 1 を返します。
_NEQ:
入力を比較して等しい場合に 0、等しくない場合に 1 を
返します。定数時間で比較するため、排他的論理和を累
積したビット列と、反転した列に 1 を加算したものの論
理和から最上位ビットを確認します。1 の加算は、最下
位から連続する 1 のビットの一つ先に 1 を追加し、下
位をすべて 0 にします。1 を追加した位置より上位に影
響はなく、反転したビットとの論理和により、常に 1 と
なります。最上位ビットが 0 となる場合は、反転したビ
ット列がすべて 1 であり、加算後に 0 と 0 の論理和と
なる場合に限られます
Ed25519 の署名生成と検証
最初の手順は鍵ペアの生成です。秘密鍵
a
の SHA-512
出力の前半 32 バイトを
_X25519
のスカラー入力と同
様に変更した
H8(a)
を使用して、スカラー倍算を行い
公開鍵
P
=
H8(a)B
を得ます。
署名生成には、秘密鍵
a
の SHA-512 出力の後半 32 バ
イト
H32(a)
も使用します。署名対象のメッセージ
m
を連結した SHA-512 出力の
l
の剰余
H(H32(a)
| m) mod
l
でスカラー倍算した
R
=
(H(H32(a)
| m) mod
l)B
を、署名の前半 32
バイトとします。スカラー倍算で自動的に
mod l
が適
用されますが、内部変数の範囲の制約から、実装におい
ては剰余計算を先に実行します。
次に、署名の前半
R
と公開鍵
P、メッセージ
m
を連結
し、SHA-512 出力の
l
の剰余を求めます。これに秘密
鍵の SHA-512 出力
H8(a)
を乗算、l
の剰余とします。
署名の後半 32 バイトは
R
の導出で使用したスカラーを
用いて次の通りとなります。
s
=
(H(H32(a)
| m) mod
l)
+
((H(R
| P
| m) mod
l)
H8(a) mod
l) mod
l
_SUB3:
戻り値は繰り上がりを管理する内部変数の、配列の範囲
を超える最初の 1 ビットです。負の場合、符号付き右シ
フトで上位から 1 がコピーされる動作を利用します。演
算の結果、負の数となる場合に 1 を返します。条件付き
の代入で利用し、定数時間で実行できます
署名の検証は、入力の確認から開始します。署名の後半
32 バイト
s
が
l
より小さく、公開鍵
P
が有効な座標で
あることを確認します。正しい Ed25519 の署名には次
の式が成立します。s
の生成式の両辺を、B
のスカラー
倍算として比較することが可能で、R
の座標の復元も省
略できます。
sB
=
R
+
(H(R
| P
| m) mod
l)P
sB
-
(H(R
| P
| m) mod
l)P
=
R
Barrett 法:
l
の剰余を求めるために、一部の計算で
p
の剰余の代わ
りに
_MOD3
を適用しています。0
以上
(28)64
未満の
入力
c
と
(28)31
以上
(28)32
未満である
l
を用いて、
剰余を次のように考えます。28
はバイト境界をもとに
決定しています。
cl
=
c(28)31
(28)64l
1(28)33
c
mod
l
=
c
-
floor(cl)l
定数
_MU
は
floor((28)64l)
に対応します。除算毎に小
数点以下の切り捨てを行った場合、
floor(cl)
-
floor(
floor(c(28)31)floor((28)64l)1(28)33)
は
0
以上
2
以下となるため、最大
2l
の減算を追加す
ることで、剰余計算を再現できます。また、c
mod
l
を得る減算では、差のビット表現が
(28)33
未満の範囲
であることから、すべての配列要素を巡回しない演算を
実装することができます
COPYRIGHT © 2019 mScroll
