X25519 実装の詳細
Curve25519
ライブラリの API は楕円曲線 Curve25519 上の演算を
基礎としています。
Curve25519:
素数の位数
p = 2255 - 19
の有限体における楕円曲線
v2
=
u3
+ Au2
+ u
A = 486662
楕円曲線 Diffie-Hellman 鍵共有 X25519 は
u
座標のみ
のスカラー倍算で構成されています。このスカラー (整
数) は秘密鍵
k
です。基点
G
のスカラー倍算によって
公開鍵
kG
を得ます。定数
_G
は、G
の座標
u = 9
に
対応します。
楕円曲線 Diffie-Hellman 鍵共有:
A と B の通信において、それぞれの秘密鍵を
kA、kB
としたとき、公開鍵
kAG、kBG
を互いに交換し、再度
秘密鍵でスカラー倍算を行うと
kAkBG
=
kBkAG
とな
ります。公開鍵から秘密鍵や共通の値を計算することは
楕円曲線離散対数問題 (ECDLP: Elliptic Curve Discrete
Logarithm Problem) となるため困難です
API は Curve25519 上の演算とスカラー倍算
_X25519
を実装することで構成できます。また、秘密情報の漏洩
を軽減するため、定数時間アルゴリズムで記述します。
有限体上の演算は、p
を法とする剰余
mod
p
を各演算
に適用することにより実装します。_MOD
の内容は
-p
を加えて、負となる場合は元の値、それ以外は元の値に
-p
を加えた値に変更します。実装では、19
を加算して
ビット 255 が 0 の場合は負と判断します。ビット 255
が 0 の場合は既に
2255
未満となっています。-2255
を加算する操作は、ビット 255 を 0 へ変更する操作に
置き換えることができます。_MOD
の入力は
0
以上
2p
未満の前提であり、出力は
0
以上
p
未満です。
_COND
は、三項演算子
?:
の定数時間アルゴリズムです。
条件が 1 の場合に左、0 の場合に右の値に変更されます。
条件入力に -1 を加えることにより、0 (すべてのビット
が 0)、-1 (すべてのビットが 1) のビットマスクを作成
できます。反転したビットマスクも使用して、常にビッ
ト毎の論理和を代入することで、一定の時間で動作する
ようにします。
多倍長整数の加算と減算:
出力先を
A_
とし、L_
+
R_
を計算します。これら 3
個の変数はすべて長さ 16 の配列で、各要素は符号なし
16 ビット整数とします。L_、R_
は
0
以上
p
未満です。
for (u = 0 , s = 0; s < 16; ++ s)
{
u += L_[s];
u += R_[s];
A_[s] = u & 0xFFFF;
u >>>= 16;
}
L_
-
R_
は
L_
+ (
p
-
R_
) とし、符号付きビットシフ
トを使用することで、加算と同様に記述できます。
for (u = -19 , s = 0; s < 16; ++ s)
{
u += L_[s];
u -= R_[s];
A_[s] = u & 0xFFFF;
u >>= 16;
}
A_[15] += 0x8000;
A_[15] &= 0xFFFF;
u
は繰り上がりの数を表します。A_
は加算と減算の両
方で
0
以上
2p
未満です。_MOD
を適用して
0
以上
p
未満になります
多倍長整数の乗算と除算:
_MUL
は乗算です。乗算の各入力は
0
以上
p
未満です。
以下は Comba 法の説明です。L_、R_
は長さ 4 の配列
で、各要素は符号なし 16 ビット整数とします。
L_ [3][2][1][0]
* R_ [3][2][1][0]
------------------------
[0][0] : L_ * R_
[0][1]
[1][0]
[0][2]
[1][1]
[2][0]
[0][3]
[1][2]
[2][1]
[3][0]
[1][3]
[2][2]
[3][1]
[2][3]
[3][2]
[3][3]
------------------------
[7][6][5][4][3][2][1][0]
筆算における各要素の乗算を、位が共通するように並べ
替えて加算します。各列は 16 ビット毎に位を表現して
います。配列要素間の乗算では、上位 16 ビットと下位
16 ビットを個別に加算します。乗算結果を格納する内
部変数は、要素のビット長の 2 倍を一時的に保持する必
要があり、符号なし 32 ビットの値を管理できることが
要件です。この例では長さ 4 の配列の乗算結果を、2 倍
の長さの配列に格納していますが、長さ 16 の配列に置
き換えても同様に実装できます。
乗算結果は、mod p
の剰余にするため
_MOD
を適用し
ますが、2p
未満までは、あらかじめ値を減らす必要が
あります。上位の値は、下位に対して、ビット表現に対
応する剰余を加算するため、その影響を考慮する必要が
あります。まず、p
= 0 mod p
より
2255
= 19 mod p
2256
= 38 mod p
であることから、ビット 255 に対応する
19
と、各要
素に、その
2256
倍の要素に対応して剰余
38
を乗算し
た値を加算します。その後、再度ビット 255 に対応す
る
19
と、繰り上がりの数の
38
倍を加算します。これ
により
2p
未満の値を得ることができ、_MOD
の後、乗
算結果は
0
以上
p
未満となります。
除算は逆数の乗算により実装します。逆数は
_INV
によ
り取得します。入力は
0
以上
p
未満です。Fermat の
小定理
ap
- 1 = 1 mod p
(a
は入力) から
ap
- 2 =
a-1
mod p
となり、ap
- 2
を計算することにより逆数が得られます。
_INV
の実装では
x2n + 1
(x
=
a2n - 1)
と
n
の調整、
2 乗と
a
の乗算の組み合わせで
a2255
- 21
を計算して
います。a の指数において 2 の累乗でない項は、2 乗で
負の方向、a
の乗算で正の方向へ加算するようにします
X25519 のスカラー倍算
_X25519
は秘密鍵
K_
と点の
u
座標
U0_
を入力し、
U_
へスカラー倍算後の点の
u
座標を出力します。秘密
鍵はビット 255 を 0、254 を 1、最下位 3 ビットをす
べて 0 にします。秘密鍵の様式は、ループの長さの固定
と、スカラーを
8
の倍数にすることを意図しています。
Curve25519 には位数
8
までの小さい巡回群があり、
この部分はスカラーの
mod 8
までが適用されます。8
の倍数のスカラー倍算を行うと無限遠点にまとめること
ができます。u
座標への変換では
_INV
を使用し、0
除
算を乗算に置き換え、無限遠点を一意に表現しています。
U0_
も、ビット 255 を 0 にして
_MOD
をとり、任意の
入力を可能とすることが必要です。
スカラー倍算は定数時間の Montgomery Ladder で実
装します。以下は JavaScript コードです。<-
の文は説
明のために表現を置き換えたものです。
p0 <- _P( 1, 0);
p1 <- _P(U0_, 1);
for (r = 0 , s = 254; 0 <= s; -- s)
{
o <- K_(s);
r ^= o;
_SWAP(r, p0.x, p1.x);
_SWAP(r, p0.z, p1.z);
r = o;
(p0, p1) <-
(_U_DBL(p0), _U_ADD(p0, p1));
}
_SWAP(r, p0.x, p1.x);
_SWAP(r, p0.z, p1.z);
U_ <- _A(p0);
_P
は射影座標への変換を表しています。p0
の場合、
_P(p0.x, p0.z)
と対応しています。K_(s)
は秘密
鍵
K_
のビット
s
の値を 0 または 1 で返します。_A
は
p0.x
/
p0.z
によるアフィン座標への変換です。こ
のアルゴリズムは、p0
を無限遠点、p1
を
U0_
に初期
化して、ビットが 0 の場合に無限遠点側、1 の場合に
U0_
側を
_U_DBL
に入力します。既に
p0
に割り当て
られている場合には交換しないようにするため、排他的
論理和
r ^= o
を使用し、r = o
で保存した前段のビ
ットと比較しています。最下位ビットが 1 の場合は、
_U_ADD
の出力を結果とします。
Montgomery Ladder:
1 と底の 2 要素を用いて、指数のビット表現に応じた底
の偶数乗と奇数乗の列を生成します。指数が偶数の場合
は偶数乗を、奇数の場合は奇数乗を結果とします。偶数
乗は 2 乗、奇数乗は前段の出力の乗算とすることで、交
換の有無によらず偶数と奇数の位置を維持します。指数
は 2 乗の入力を選択する要素であり、数の生成を制御し
ます。_U_DBL
は 2 乗、_U_ADD
は乗算に対応します
_U_DBL
は次の式を実行します。
X
=
(X0
+
Z0)2(X0
-
Z0)2
Z
=
((X0
+
Z0)2
-
(X0
-
Z0)2)
((X0
-
Z0)2
+
A
+ 24((X0
+
Z0)2
-
(X0
-
Z0)2))
実装における定数
_A24
は次に対応します。
A
+ 24
=
486662
+ 24
= 121666
_U_ADD
は次の式を実行します。
X
=
((X0
-
Z0)(X1
+
Z1)
+ (X0
+
Z0)(X1
-
Z1))2
Z
=
u((X0
-
Z0)(X1
+
Z1)
- (X0
+
Z0)(X1
-
Z1))2
_SWAP
は定数時間で配列要素を交換するもので、配列
要素のビット毎の排他的論理和と条件値より作成したビ
ットマスクを使用して、常に代入を実行します。条件値
は 0 または 1 で 1 の場合に交換します。排他的論理和
により、相違するビットのみを示す列を取得し、それを
再度排他的論理和で適用することで、該当するビットが
反転して交換が行われます。また、条件値のビットマス
クを使用し、排他的論理和のビット列と常にビット毎の
論理積をとるようにして、条件付き交換を実装できます。
条件値によるビットマスクは、1 の場合、反転して最下
位ビットのみが 0 となり、1 の加算ですべて 1 の列と
なります。0 の場合は、反転後のすべて 1 の列が繰り上
がりで完全な 0 となります。
_X25519
について楕円曲線 Diffie-Hellman 鍵共有で
共通の値を取得する場合に、点の位数の相違を確認しま
す。秘密鍵の修正によって意図しない位数の点が無限遠
点となり、正しい位数の点が含まれない場合には、無限
遠点のみとなるため、u
座標出力がすべて 0 になります。
定数時間の検査では、すべての配列要素でビット毎の論
理和を累積し、巡回後に値が 0 であるか確認します
COPYRIGHT © 2019 mScroll
