EdWards25519
条件分岐がなく計算できる楕円曲線
加算
RFC 8032 3. の元の式は
$ 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}
このまま実装してみてもよいが逆数の計算に時間がかかるので省エネな方式もある
そのまま実装する場合
d と a は 11個のパラメータの内 7番目、8番目のもの
d = -121665 / 1221666 で計算できる。割り算は逆数にしてから掛け算。 a は p mod 4 が 1らしいので -1 (32-19 = 13 で 1101 なので mod 4 が 1になる)
RFC 8032 5.1.4. ポイント加算?
x, y を (X, Y, Z, T) に変換する
Z は分母側になる数字ということで逆数は最後に計算すればよい
$ x = \frac{X}{Z}
$ y = \frac{Y}{Z}
$ x * y = \frac{T}{Z}
ということなのでとりあえずx, y から変換する場合は Z を 1にする
$ (\frac{x}{Z}, \frac{y}{Z}, Z,\frac{x*y}{Z})
(x, y, 1, x*y) という変換でよさそう
中立元 (natural point) は ( 0, 1 ) なので ( 0, Z, Z, 0 ) 風にできるので ( 0, 1, 1, 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
でいいらしい T1が参照されていない
中立元を加算してみる
(x, y, 1, xy) と ( 0, 1, 1, 0)
A = (y-x)*(1-0) = y-x
B = (y+x)*(1+0) = y+x
C = xy * 2 * d * 0 = 0
D = 1 * 2 * 1 = 2
E = y + x - y + x = 2x
F = 2 - 0 = 2
G = 2 + 0 = 2
H = y+x+y-x = 2y
X3 = 2x * 2 = 4x
Y3 = 2 * 2y = 4y
T3 = 2x * 2y = 4xy
Z3 = 2 * 2 = 4
(x,y,1,xy)
$ P_1 + P_2 = (\frac{x_1y_2+x_2y_1}{c(1+dx_1x_2y_1y_2)}, \frac{y_1y_2 - x_1x_2}{c(1 - dx_1x_2y_1y_2)})
RFC 7748 4.1.の定義
$ -x^2 + y^2 = 1 + dx^2y^2 when p = 1 mod 4
p $ 2^{255} - 19
d 37095705934669439343138083508754565189542113879843219016388785533085940283555
order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
cofactor 8
X(P) 15112221349535400772501151409588531511454012693041857206046113283949847762202
Y(P) 46316835694926478169428394003475163141307993866256225615783033603165251855960
p order cofactor が同じ
(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
(x. y) = (sqrt(-486664)*u/v, (u-1)/(u+1))
RFC 8032
5.1.1. モジュラー演算
逆行列
$ x^{-1} = x^{p-2}(mod p)
point decode (decompression 圧縮解除)
$ x = a^{\frac {p+3}8} mod p
RFC 8928