SIDH 実装の詳細
超特異同種写像 Diffie-Hellman 鍵共有 (SIDH)
SIDH は、超特異楕円曲線の点に同種写像を適用して得
られる楕円曲線を、公開鍵または共通の値とする方法で
す。秘密鍵は、同種写像を構成する点のスカラーです。
楕円曲線を共通の値に変換するには、j-不変量を計算し
ます。ライブラリの SIDH 実装では、751 ビットの素数
p
= 23723239
- 1
を使用して、位数
p2
の有限体上の
超特異楕円曲線
y2
=
x3
+
6x2
+
x
を初期値としてい
ます。i2
= -1
を用いて有限体を複素数で表現できます。
A と B の通信において、それぞれ次の点が割り当てられ
ています。点の位数は A、B について
2372、3239
です。
f(x)
=
x3
+
6x2
+
x
とします。
PA
=
3239(zPA
+
i,
f(zPA
+
i)12)
QA
=
3239(zQA
+
i,
f(zQA
+
i)12)
PB
=
2371(zPB,
f(zPB)12)
QB
=
2371(zQB,
f(zQB)12)
zPA、zQA、zPB、zQB
は次の条件に従って与えられる
最小の非負の整数です。
zPA 2371PA
= (-3 ±
2(2)12,
0)
zQA 2371QA
= (0, 0)
zPB ±f(zPB)12
mod
p
が存在
zQB ±f(zQB)12
mod
p
が不存在
A、B の秘密鍵
a、b
は
RA
=
PA
+
aQA
RB
=
PB
+
bQB
の形式で格子を構成する
0
以上の整数で、値の上限は
2372
- 1、3239
- 1
です。b
は 751 - 372 = 379 ビ
ットをすべて使用すると上限を超えるため、378 ビット
にします。複素数の格子は楕円曲線に相当することから、
RA
または
RB
を基に A と B は同種写像を計算するこ
とができます。
複素数の実装:
位数
p
の有限体上の 2 要素により表現され、1 個は
i
の係数です。要素間は、i2
= -1
と
i
の乗算を適用して、
実数の要素による複素数と同様の演算を利用できます。
(z1
+
z2i)
+
(z3
+
z4i)
=
(z1
+
z3)
+
(z2
+
z4)i
(z1
+
z2i)
-
(z3
+
z4i)
=
(z1
-
z3)
+
(z2
-
z4)i
(z1
+
z2i)2
=
(z1
+
z2)(z1
-
z2)
+
2z1z2i
(z1
+
z2i)(z3
+
z4i)
=
(z1z3
-
z2z4)
+
((z1
+
z2)(z3
+
z4)
-
z1z3
-
z2z4)i
1z1
+
z2i
=
z1z12
+
z22
-
z2z12
+
z22i
_BASIS:
Gen_
に代入する定数は、位数
p2
の有限体上にある
P、
Q、P
-
Q
を並べたものを使用します
_LADDER:
秘密鍵のビット表現を下位から参照する Montgomery
Ladder です。この方法では、2 乗側を固定して乗算側
を選択します。2 乗側の式は次の通りです。Q
の射影
座標を更新し、次の位にあたる点
2Q
を生成します。
X
=
(XQ
+
ZQ)2(XQ
-
ZQ)2
Z
=
((XQ
+
ZQ)2
-
(XQ
-
ZQ)2)
((XQ
-
ZQ)2
+
A
+
24((XQ
+
ZQ)2
-
(XQ
-
ZQ)2))
乗算側の式は次の通りです。P
と
P
-
Q
をビットの値
に応じて交換し、P
を
P
+
Q
へ更新します。
X
=
ZP
-
Q((XQ
+
ZQ)(XP
-
ZP)
+
(XQ
-
ZQ)(XP
+
ZP))2
Z
=
XP
-
Q((XQ
+
ZQ)(XP
-
ZP)
-
(XQ
-
ZQ)(XP
+
ZP))2
P
-
Q
はビットが 0 の場合に、更新された
P
を保存し
ます。スカラー倍算の結果は
P
-
Q
側から取得するた
め、最上位ビットが 1 の場合は点を交換します
同種写像は、楕円曲線の点への写像を合成したものとな
ります。各段で楕円曲線の係数を新たに得て、その曲線
上に点を移します。
上図は同種写像のループ部分を表したものです。左上の
頂点は秘密鍵から定義された点
R0
です。垂直、水平の
線は、スカラー倍算と同種写像の適用を表します。この
例では、R0
の位数が
49、スカラー倍算は
4
を単位と
しています。Rn
から
Rn
+ 1
への同種写像を構成する
点は
48
-
nRn
(n
は
0
以上
8
以下) であり、図におい
て線が終端されている位置の点です。最適化はスカラー
倍算を事前に割り当てて実装します。R8
から
R9
への
同種写像によって、公開鍵または共通の値となる楕円曲
線へ移ります。公開鍵は、共通の値を得るために点が必
要となるため、通信の相手方が基礎とする点
P'、Q'、
P'
-
Q'
に同種写像を適用した 3 点とします。公開鍵
による新しい楕円曲線上で、再び秘密鍵から同種写像を
構成することで写像を合成し、楕円曲線を共有します。
楕円曲線の係数:
同種写像の計算では、曲線の係数を射影座標で記述した
By2
=
Cx3
+
Ax2
+
Cx
(A
= 6、B
= 1、C
= 1)
を使用します。射影座標によって有限体の逆数の計算を
削減できます。
スカラー倍算 (アフィン座標) A
+ 24
A のスカラー倍算 (射影座標) A
+ 2C、4C
B のスカラー倍算 (射影座標) A
- 2C、A
+ 2C
アフィン座標に対しては
A
を単体で使用し、射影座標
の場合は、上記について
A24_P、C24
または
A24_N、
A24_P
として保持します。これらの他に計算過程で生
じる中間の値も利用されます。また、j-不変量を求める
_J_INV
には、A
と
C
を等しい比率で分解した
4A、
4C
を代入します
_E4N:
A の同種写像は位数
4
を単位としています。スカラー
倍算は 2 倍算で実装できます。
X
=
4C(XR
+
ZR)2(XR
-
ZR)2
Z
=
((XR
+
ZR)2
-
(XR
-
ZR)2)
(4C(XR
-
ZR)2
+
(A
+
2C)((XR
+
ZR)2
-
(XR
-
ZR)2))
_GET4:
同種写像の適用で得られる曲線の係数を取得します。
_EVAL4
で利用するため、中間の値も保存します。
A'
+
2C'
=
4X44
4C'
=
4Z44
Coeff[0] 4Z42
Coeff[1] X4
-
Z4
Coeff[2] X4
+
Z4
_EVAL4:
_GET4
で求めた楕円曲線へ点を移します。
X'
=
((X4
+
Z4)(X
-
Z)
+
(X4
-
Z4)(X
+
Z))2
(((X4
+
Z4)(X
-
Z)
+
(X4
-
Z4)(X
+
Z))2
+
4Z42(X
+
Z)(X
-
Z))
Z'
=
((X4
+
Z4)(X
-
Z)
-
(X4
-
Z4)(X
+
Z))2
(((X4
+
Z4)(X
-
Z)
-
(X4
-
Z4)(X
+
Z))2
-
4Z42(X
+
Z)(X
-
Z))
_E3N:
B の同種写像は位数
3
を単位とします。
X
=
2XR((A
-
2C)(XR
-
ZR)4
-
(A
+
2C)(XR
+
ZR)4
+
((A
+
2C)(XR
+
ZR)2
-
(A
-
2C)(XR
-
ZR)2)
(4XR2
-
(XR
+
ZR)2
-
(XR
-
ZR)2))2
Z
=
2ZR((A
-
2C)(XR
-
ZR)4
-
(A
+
2C)(XR
+
ZR)4
-
((A
+
2C)(XR
+
ZR)2
-
(A
-
2C)(XR
-
ZR)2)
(4XR2
-
(XR
+
ZR)2
-
(XR
-
ZR)2))2
_GET3:
A'
-
2C'
=
(4X32
-
(X3
-
Z3)2)
(8X32
-
(X3
+
Z3)2
+
2(X3
-
Z3)2)
A'
+
2C'
=
(4X32
-
(X3
+
Z3)2)
(8X32
+
2(X3
+
Z3)2
-
(X3
-
Z3)2)
Coeff[0] X3
-
Z3
Coeff[1] X3
+
Z3
_EVAL3:
X'
=
X((X3
-
Z3)(X
+
Z)
+
(X3
+
Z3)(X
-
Z))2
Z'
=
Z((X3
+
Z3)(X
-
Z)
-
(X3
-
Z3)(X
+
Z))2
_INV3:
アフィン座標に変換するための
1Z
を求めます。計算量
を減らすため、1Z1Z2Z3
を求めて
Z1、Z2、Z3
の乗
算により分解します
_GET_A:
公開鍵の 3 点から楕円曲線の係数 (アフィン座標)
A
を
計算します。
A
=
(xP
-
Q(xP
+
xQ)
+
xPxQ
-
1)24xPxQxP
-
Q
-
xP
-
xQ
-
xP
-
Q
_J_INV:
j-不変量を計算します。次の式は係数を射影座標で表し
た曲線に対して定義されます。
256(A2
-
3C2)3C4(A2
-
4C2)
Montgomery 形式
位数
p
の有限体上の演算について Montgomery 形式の
剰余を使用します。この形式は、(2768)2
mod
p
の乗
算と
(2768)-1
の乗算
_MR
をあわせて、有限体上の値
m
を
m2768
mod
2p
とするものです。乗算は余分な
2768
を除去するための
_MR
が必要です。公開鍵や共通
の値には、_MR
に
_MOD
を追加して
mod
p
にします。
2768
mod
p
の乗算と
_MR
を組み合わせて
2768
を消
去し、Montgomery 形式から元に戻します。
_MO 2768
mod
p
_M2 (2768)2
mod
p
_MR:
0
以上
p2768
未満の入力に対して、0
以上
2p
未満の
値を出力します。入力は乗算部分
_MUL
の出力と同じ型
であり、(2768)-1
を乗算して
2768
の数を調節する作
用を含みます。_MR
は
M
+
(Mp'
mod
2768)p2768
を実
行します。この式は、p
の特性と後述の Comba 法によ
って、M
+
(M
mod
216)(p
+
1)216
を連結して実装で
きます。2768
に対する分子は必ず割り切れて、余りが
発生しません。定数
_P1
は
p
+
1
に対応します。下位
に長く連続する 0 を持ち、部分的に乗算を省略できます。
(3)(2)(1)(0) : A_
* [3][2][1] : _P1
---------------------
(0)[1]
(0)[2]
(1)[1]
(0)[3]
(1)[2]
(2)[1]
(1)[3]
(2)[2]
(3)[1]
(2)[3]
(3)[2]
(3)[3]
[7][6][5][4][3][2][1] [0] : A0d_
--------- ---
(3)(2)(1) (0) : A_
------------
[3][2][1][0] : A_
上図は、実装の配列要素のサイズを変更して記述してい
ます。M
を更新して式を実行する動作は Comba 法で
実装します。A0d_
は入力、2768
以上の範囲で
A_
は
出力に対応します。ループ中で
A_
の参照されない要素
があり、初期化の省略や上書きが可能となります
_MOD:
0
以上
2p
未満の入力について
mod
p
を求めます。
_MR
によって十分に値が削減されるため、_MOD
の実行
を省略できます。定数
_P
は
p
に対応します
SIDH 実装の演算では、乗算で実行される
_MR
に剰余
計算をまとめています。剰余計算の省略は、入力や出力
の範囲を考慮する必要があり、p
- 1
以上
2768
未満で
ビットが保持されるように構成します。_SUB
の右辺は、
L_ + (F_ - R_)
の
F_
によって
2p、4p
(定数
_P2、
_P4)
未満とする上限があります。_ADDM
と
_SUBM
は、
2p
による 1 ビットの値の削減を追加したもので、値の
範囲を調節します。
_NEG:
2p
によって入力の符号を反転します。差の右辺に相当
します
_DSUB:
_MUL
の出力型について
Ad_ - A0d_ - A1d_
を計算
します。この演算結果が正である場合に利用可能で、値
の削減を行うことなく
0
以上
p2768
未満の値が出力さ
れます。_MSUB
は、p2768
による値の削減を含む差の
計算を実行します
_DIV:
ビットシフトを用いて、入力を 2 で割った値を出力しま
す。入力が奇数の場合、p
の加算を利用して偶数へ変換
します
有限体上の逆数を求める
_INV
は、p
のビット表現を使
用した 2 乗と乗算の組み合わせで実装します。乗算は最
大 5 ビットの奇数を単位とするよう
_PM
に割り当てて、
入力の奇数乗を組み合わせます。2 乗の長さは、1 のビ
ットまで乗算を省略するように
_PS
へ割り当てます。p
のビット表現は次の通りです。
0000 6FE5 D541 F71C
0E12 909F 97BA DC66
8562 B504 5CB2 5748
084E 9867 D6EB E876
DA95 9B1A 13F7 CC76
E3EC 9685 49F8 78A8
EEAF FFFF FFFF FFFF
FFFF FFFF FFFF FFFF
FFFF FFFF FFFF FFFF
FFFF FFFF FFFF FFFF
FFFF FFFF FFFF FFFF
FFFF FFFF FFFF FFFF
左上が上位、右下が下位となります。最初に
p
- 34
乗を
求めます。_PS
と
_PM
は、上図の下位 2 ビットを除く
部分から作成します。2 乗 2 回と 1 乗の乗算を追加し
て
p
- 2
乗を求めます
COPYRIGHT © 2019 mScroll
