楕円点の加算と減算

有限体上の楕円曲線における楕円点の加算，減算のアルゴリズムを示す．

アフィン座標

加算と減算 (FullAdd)

標数 $p \gt 3$ の体の場合
アフィン座標系を用いた $\mathrm{GF}(p)$ 上の楕円曲線加算アルゴリズム

入力: 素数 $p\ (\gt 3)$，楕円曲線 $E: y^2=x^3+ax+b \bmod p$ の係数 $a$，$b$，$E$ 上の点 $P_0 = (x_0, y_0)$ と $P_1 = (x_1, y_1)$
出力: 点 $P_2 := P_0 + P_1$
1. If $P_0 = {\cal O}$ then return $P_2 \leftarrow P_1$
2. If $P_1 = {\cal O}$ then return $P_2 \leftarrow P_0$
3. If $x_0 \ne x_1$ then
4. 　$\lambda \leftarrow (y_0-y_1) / (x_0- x_1) \bmod p$
5. 　Go to step 9
6. If $y_0 \ne y_1$ then return $P_2 \leftarrow {\cal O}$
7. If $y_1 = 0$ then return $P2 \leftarrow {\cal O}$
8. $\lambda \leftarrow (3 x_1^2 + a) / (2y_1) \bmod p$
9. $x_2 \leftarrow \lambda^2 -x_0 -x_1 \bmod p$
10. $y_2 \leftarrow (x_1-x_2)\lambda-y_1 \bmod p$
11. Return $P_2 \leftarrow (x_2, y_2)$
このアルゴリズムは，3ないし4回の剰余乗算と1回の剰余逆元を必要とする．
点 $P = (x, y)$ の減算は，点 $-P = (x, -y)$ の加算を行えばよい．
標数 2 の体の場合
アフィン座標系を用いた $\mathrm{GF}(2^m)$ 上の楕円曲線の加算アルゴリズム

入力: 有限体 $\mathrm{GF}(2^m)$；$\mathrm{GF}(2^m)$ 上の楕円曲線 $E: y^2+xy=x^3+ax^2+b$ の係数 $a, b$；$E$ 上の点 $P_0 = (x_0, y_0)$ と $P_1 = (x_1, y_1)$
出力: 点 $P_2 := P_0 + P_1$
1. If $P_0 = {\cal O}$, then return $P_2 \leftarrow P_1$
2. If $P_1 = {\cal O}$, then return $P_2 \leftarrow P_0$
3. If $x_0 \ne x_1$ then
4. 　$\lambda \leftarrow (y_0 + y_1)/(x_0 + x_1)$
5. 　$x_2 \leftarrow a + \lambda^2 + \lambda + x_0 + x_1$
6. 　Go to step 11
7. If $y_0 \ne y_1$ then return $P_2 \leftarrow {\cal O}$
8. If $x_1 = 0$ then return $P_2 \leftarrow {\cal O}$
9. $\lambda \leftarrow x_1 + y_1 / x_1$
10. $x_2 \leftarrow a + \lambda^2 + \lambda$
11. $y_2 \leftarrow (x_1 + x_2)\lambda + x_2 + y_1$
12. Return $P_2 \leftarrow (x_2, y_2)$
このアルゴリズムは，2回の乗算，1回の2乗，1回の乗法逆元の演算を必要とする．点 $P = (x, y)$ の減算は，点 $-P = (x, x - y)$ の加算を行えばよい．

プロジェクティブ座標（ヤコビ座標系）

2倍算 (Double)

標数 $p \gt 3$ の体の場合
楕円曲線 $y^2 = x^3 + ax + b \bmod p$ 上での点の2倍算
$2 (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は，次の式により求められる．

$M = 3 X_1^2 + a Z_1^4,$
$Z_2 = 2Y_1Z_1,$
$S = 4X_1 Y_1^2,$
$X_2 = M^2 - 2S,$
$T = 8Y_1^4,$
$Y_2 = M (S - X_2)- T.$
標数 $2$ の体の場合
有限体 $\mathrm{GF}(2^m)$ 上の楕円曲線 $y^2 + xy = x^3 + ax^2 + b$ 上での点の2倍算
$2 (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は，次の式により求められる．
$c := b^{2^{m-2}},$
$Z_2 = X_1 Z_1^2,$
$X_2 = (X_1 + c Z_1^2 )^4,$
$U = Z_2 + X_1^2 + Y_1Z_1,$
$Y_2 = X_1^4 Z_2 + UX_2.$

加算 (Add)

標数 $p \gt 3$ の体の場合
楕円曲線 $y^2 = x^3 + ax + b \bmod p$上での点の加算

$(X_0, Y_0, Z_0) + (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は，次の式により求められる．
$ U_0 = X_0 Z_1^2,$
$ S_0 = Y_0 Z_1^3,$
$ U_1 = X_1 Z_0^2,$
$ S_1 = Y_1 Z_0^3,$
$ W = U_0 - U_1,$
$ R = S_0 - S_1,$
$ T = U_0 + U_1,$
$ M = S_0 + S_1,$
$ Z_2 = Z_0Z_1W,$
$ X_2 = R^2 -TW^2,$
$ V = TW^2 - 2X_2,$
$ 2Y_2 = VR - MW^3.$
標数 $2$ の体の場合
有限体 $\mathrm{GF}(2^m)$ 上の楕円曲線 $y^2 + xy = x^3 + ax^2 + b$ 上での点の加算
$X_0, Y_0, Z_0) + (X_1, Y_1, Z_1) = (X_2, Y_2, Z_2)$
は，次の式により求められる．
$ U_0 = X_0 Z_1^2,$
$ S_0 = Y_0 Z_1^3,$
$ U_1 = X_1 Z_0^2,$
$ W = U_0 + U_1,$
$ S_1 = Y_1 Z_0^3,$
$ R = S_0 + S_1,$
$ L = Z_0 W,$
$ V = RX_1 + LY_1,$
$ Z_2 = LZ_1,$
$ T = R + Z_2,$
$ X_2 = a Z_2^2 + TR + W^3,$
$ Y_2 = TX_2 + VL^2.$

加算と減算 (FullAdd)

標数 $p \gt 3$ の体の場合
入力: $q$ 個の要素からなる有限体；$\mathrm{GF}(q)$ 上の楕円曲線を定義する体の要素 $a, b$；$E$ 上の点 $P_0$ と$P_1$ を表す射影座標 $(X_0, Y_0, Z_0)$，$(X_1, Y_1, Z_1)$
出力: 点 $P_2= P_0 + P_1$ に対するプロジェクティブ座標$(X_2, Y_2, Z_2)$
1. If $Z_0 = 0$ then return $(X_2, Y_2, Z_2) \leftarrow (X_1, Y_1, Z_1).$
2. If $Z_1 = 0$ then return $(X_2, Y_2, Z_2) \leftarrow (X_0, Y_0, Z_0).$
3. $(X_2, Y_2, Z_2) \leftarrow \mathrm{Add}\ [(X_0, Y_0, Z_0), (X_1, Y_1, Z_1)].$
4. If $(X_2, Y_2, Z_2) = (0, 0, 0)$ then $(X_2, Y_2, Z_2) \leftarrow \mathrm{Double}\ [(X_1, Y_1, Z_1)].$
5. Return $(X_2, Y_2, Z_2).$
楕円曲線の減算(Subtract)は以下のように行える． \[ \mathrm{Subtract}\ [(X_0, Y_0, Z_0), (X_1, Y_1, Z_1)] = \mathrm{FullAdd}\ [(X_0, Y_0, Z_0), (X_1,U,Z_1)] \] ここで， \[ U = \left\{ \begin{array}{ll} -Y_1\ \bmod\ p & \text{if}\ q = p,\\ X_1 Z_1 + Y_1, & \text{if}\ q = 2^m.\\ \end{array}\right. \] である．

Page Top